Книга является наиболее полным руководством по разработке эффективных ал

Часть I. Практическая разработка алгоритмов 
А на рис. 1.1 показано применение этого алгоритма для сортировки определенного эк-
земпляра — строки INSERTIONSORT. 
Рис. 1.1. 
Пример использования алгоритма сортировки вставками (шкала времени направлена вниз) 
Обратите внимание на универсальность этого алгоритма. Его можно применять как для 
сортировки слов, так и для сортировки чисел, используя соответствующую операцию 
сравнения для определения, какое из двух значений поставить первым. Можно с лег- 
костью убедиться, что этот алгоритм правильно сортирует любой возможный набор 
входных величин в соответствии с нашим определением задачи сортировки. 
Хороший алгоритм должен обладать тремя свойствами: быть корректным, эффектив-
ным и легкореализуемым. Получение комбинации всех трех свойств сразу может ока-
заться недостижимой задачей. В производственной обстановке любая программа, ко-
торая предоставляет достаточно хорошие результаты и не замедляет работу системы,
в большинстве случаев является приемлемой, независимо от того, возможны ли улуч-
шения этих показателей. В этой области вопрос получения самых лучших возможных 
результатов или достижения максимальной эффективности обычно возникает только в 
случае серьезных проблем с производительностью или с законом. 
В этой главе основное внимание уделяется вопросу корректности алгоритмов, а их эф-
фективность рассматривается в 
главе 2
. Способность определенного алгоритма пра-
вильно решить поставленную задачу, т. е. его корректность, редко поддается очевид-
ной оценке. Алгоритмы обычно сопровождаются доказательством их правильности в 
виде объяснения, почему для каждого экземпляра задачи будет выдан требуемый ре-
зультат. Но прежде чем продолжить обсуждение темы, мы продемонстрируем, что ар-
гумент "это очевидно" никогда не является достаточным доказательством правильно-
сти алгоритма. 
1.1. Оптимизация маршрута робота 
Рассмотрим задачу, которая часто возникает на производстве и транспорте. Допустим, 
что нам нужно запрограммировать роботизированный манипулятор, который применя-
ется для припаивания контактов интегральной схемы к контактным площадкам на пе-
чатной плате. Чтобы запрограммировать манипулятор для выполнения этой задачи, 
сначала нужно установить порядок, в котором манипулятор припаивает первый кон-

---