Cтраница 4
Каждое имя xt принимает значение из пространства имен, на котором определен линейный порядок. Ограничение х х, при lf упрощает анализ без потери общности, ибо и при наличии равных имен корректность идей и алгоритмов не нарушается. В задаче полной сортировки требуется полностью определить П, хотя обычно это делается неявно путем переразмещения имен в порядке возрастания. [46]
Пусть s & - алгоритм, описанный с помощью дерева сравнений Г ( см. разд. Выполнение алгоритма з & при решении любой конкретной индивидуальной задачи соответствует прохождению в дереве Т пути из его корня до некоторого листа. Сведение от задачи сортировки выполняется следующим образом. [47]
Накопленный опыт, образование и имеющиеся решения проблем также существенно влияют на успех дела. Обработка данных в своей эволюции достигла такой точки, когда проектировщик крайне редко сталкивается с задачей, которая уже не была бы решена частично или полностью. Например, разработчик новой операционной системы должен понимать, что уже созданы сотни операционных систем и на эту тему написан не один учебник. Проектировщик, столкнувшись с задачей сортировки, должен знать, что уже придумано и проанализировано множество алгоритмов сортировки. При разумном подходе к решеникузадач начинать следует с анализа своего опыта и опыта других, с тем чтобы проверить, не была ли задача уже решена. [48]
Эталон - это некоторая особая программа и связанные с ней данные, выбранные таким образом, чтобы эта задача имела смысл для автора исследований. Классическими эталонными задачами являются обращение матрицы для класса научных задач и составление платежной ведомости для класса коммерческих задач. Широко используется в качестве эталона и задача сортировки. Для задач, которые не относятся ни к научным, ни к коммерческим, могут быть установлены другие эталоны. [49]
Алгоритм сортировки обменами ( см. алгоритм б) в задаче 628) также имеет свои достоинства. Так как разные слова могут иметь разную длину, то без больших затруднений можно менять местами только слова, стоящие рядом. Но алгоритм сортировки обменами и предписывает только такие обмены. Эта задача не является, конечно, задачей сортировки массива, но тем не менее алгоритм сортировки обменами оказывается здесь полезным. Написать программу, предполагая, что длина слова не превосходит пятнадцати. [50]
Первый этап не требует сравнений, и его можно выполнить за N шагов - по одному шагу на выходной элемент списка. Второй этап также полиномиален: для его выполнения необходимо сделать N - 1 сравнений. Такая процедура подходит под наше определение класса NP, и можно прийти к выводу, что задача сортировки принадлежит как классу Р, так и классу NP. То же самое можно проделать с любым полиномиальным алгоритмом, поэтому все задачи класса Р лежат и в классе NP, т.е. Р является подмножеством в NP. Однако в классе NP есть задачи, для которых мы не знаем полиномиального детерминированного алгоритма их решения. [51]
Технологическая схема нефтеперерабатывающего завода ( НПЗ) должна обеспечивать выпуск товарной продукции на уровне лучших мировых образцов и учитывать перспективы изменения требований со стороны потребителей. Ассортимент продукции должен быть достаточно широким и рассчитанным на изменение спроса в зависимости от сезона. Необходимо также принимать во внимание возможность изменения количества и качества поступающего на завод сырья. Практика показывает, что даже при снабжении заводов нефтью по трубопроводам характеристика сырья может заметно меняться в течение месяца и даже недели. Еще более резкие изменения качества сырья возможны при поступлении нефти по железной дороге. К сожалению, до настоящего времени задача сортировки и оптимального смешения нефтеи еще не решена. [52]