Такой книги пока нет. И я не знаю, когда я ее напишу.
Она будет полной противоположностью книге Рода Стивенса. Алгоритмы. Теория и практическое применение
1. Моя книга не для программистов, а "для блондинок".
2. Моя книга не про программы, а про алгоритмы и алгоритмические предписания.
3. Моя книга позволяет описать не программы, а человеческую работу. Сюда относятся потоки работ (workflows), бизнес-процессы, любые пошаговые процессы. В том числе алгоритмическую часть программ.
4. Новизна в том, что я показываю ЕДИНУЮ ПРИРОДУ следующих сущностей:
— любые пошаговые процессы.
5. Эту единую природу позволяет выявить и продемонстрировать язык ДРАКОН.
А теперь информация о моем антиподе — книге Рода Стивенса.
Rod Stephens
Essencial Algorithms: Practical Approach to Computer Algorithms
© 2013 by John Wiley & Sons, Inc., Indianapolis, Indiana. All rights reserved.
Authorised translation from the English language edition published by John Wiley & Sons Limited, 2016. — 544 .
ISBN 978-5-699-81729-0
КРАТКОЕ ОГЛАВЛЕНИЕОглавление ........................................................................................... 6
Об авторе ............................................................................................ 16
Благодарности .................................................................................... 16
Введение ............................................................................................ 17
Глава 1. Основы алгоритмизации .......................................................... 24
Глава 2. Численные алгоритмы ............................................................. 45
Глава 3. Связные списки ...................................................................... 72
Глава 4. Массивы ................................................................................. 96
Глава 5. Стеки и очереди .....................................................................119
Глава 6. Сортировка ...........................................................................136
Глава 7. Поиск ....................................................................................163
Глава 8. Хеш-таблицы .........................................................................168
Глава 9. Рекурсия ...............................................................................181
Глава 10. Деревья ...............................................................................215
Глава 11. Сбалансированные деревья ...................................................257
Глава 12. Деревья принятия решений ...................................................274
Глава 13. Основные сетевые алгоритмы ...............................................296
Глава 14. Дополнительные сетевые алгоритмы ......................................324
Глава 15. Строковые алгоритмы ...........................................................345
Глава 16. Криптография ......................................................................365
Глава 17. Теория вычислительной сложности .......................................387
Глава 18. Распределенные алгоритмы ..................................................402
Глава 19. Головоломки, встречающиеся на собеседованиях ..................432
Приложение А ....................................................................................442
Приложение Б ....................................................................................453
Глоссарий ........................................................................................ 522
Указатель ..........................................................................................536
Глава 1
ОСНОВЫ АЛГОРИТМИЗАЦИИПрежде чем приступить к изучению алгоритмов, рассмотрим несколько важных моментов. Для начала вы должны знать, что алгоритм — это набор команд, необходимых для решения той или иной задачи.
Он определяет шаги, согласно которымона будет выполняться.
Такое определение кажется довольно простым, однако никто не станет писать
алгоритмы для выполнения примитивных задач или создавать инструкции, чтобы получить доступ к четвертому элементу массива (подразумевается, что вы уже владеете минимальными навыками программирования и знаете, как это делается).
Как правило, алгоритмы пишутся только для сложных задач, например в том случае, когда нужно найти кратчайший путь через сеть из сотен улиц или отыскать наилучший вариант инвестиций для оптимизации прибыли.
В этой главе объясняются некоторые основные положения алгоритмизации,
о которых вам следует иметь полное представление, особенно если есть желание извлечь максимальную пользу от чтения книги.
Возможно, вы захотите пропустить приведенную здесь информацию и сразу приступить к изучению специальных алгоритмов. Однако лучше хотя бы поверхностно ознакомиться с изложенным материалом.
Подробно изучите подраздел «Асимптотическая сложность алгоритма»
в разделе «Алгоритм и структура данных» текущей главы, поскольку понимание времени существенно для выбора нужного алгоритма. Очень важно, справится он с заданием за секунды, часы или не справится вообще.
МетодЧтобы понять работу алгоритма, недостаточно просто рассмотреть его шаги.
Нужно выяснить еще несколько важных моментов.
Поведение алгоритма. Находит ли он наилучшее из возможных или просто
хорошее решение? Может ли быть несколько наилучших решений? Есть ли
смысл отдать предпочтение одному из них?
Скорость алгоритма. Быстрый он или нет? Замедляет ли работу только с некоторыми входными данными?
Требования к памяти алгоритма. Сколько компьютерных ресурсов ему необходимо? Является ли такой объем приемлемым? Нужны ли алгоритму мил
лионы терабайтов памяти, которыми компьютер не располагает (по край-
ней мере, сейчас)?
Основные методы, используемые в алгоритме. Можно ли задействовать их
повторно для решения подобных задач?
Основы алгоритмизацииВ данном издании затрагиваются все вышеперечисленные темы. Вместе с тем
я не ставлю целью детально рассмотреть каждый алгоритм — используется преимущественно интуитивный подход, без излишне детального анализа его работы.
Подробное изучение отнимает много времени, к тому же не требуется большинству программистов. Тем не менее книга ориентирована в первую очередь на профессионалов, которым нужны действенные и эффективные решения.
Все приведенные алгоритмы классифицированы определенным образом. Объединяющим признаком может выступать, например, задача, которую они выполняют (сортировка, поиск), используемые структуры данных (связные списки, массивы, хеш-таблицы, деревья) или методы (рекурсия, деревья решений, распределяемые алгоритмы).
Иногда объединение алгоритмов в группы может показаться странным, но
по мере накопления информации вы убедитесь, что такой выбор сделан не случайно.
Многие алгоритмы включают несколько общих моментов, которые упомина-
ются в разных главах. Например, древовидные алгоритмы (главы 10–12) обычно имеют высокую степень рекурсивности (глава 9).
Связные списки (глава 3) могут использоваться для формирования массивов (глава 4), хеш-таблиц (глава
, стеков (глава 5) и очередей (глава 5).
Ссылки и указатели применяются для построения связных списков (глава 3), деревьев (главы 10–12) и сетей (главы 13 и 14).
При чтении книги обращайте внимание на подобную связь. В приложении А обобщены используемые в программах стратегии. Это сделано для того, чтобы следовать им было легче.
Алгоритм и структура данныхКак сказано выше, алгоритм представляет собой набор команд для выполнения какой-либо задачи. При этом все данные, необходимые для ее решения, организуются особым образом в так называемую структуру.
Это может быть массив, связный список, дерево, граф, сеть или что-то более замысловатое.
Алгоритмы не могут существовать без структур данных. Например, алгоритм
редакторского расстояния, который описывается в главе 15 и устанавливает схожесть двух строк, тесно связан с сетью и без нее не работает. Точно так же нет смысла строить структуру данных, если вы не планируете использовать ее вместе с алгоритмом.
ПсевдокодДля описания алгоритмов в книге используются интуитивно понятные английские термины. Это сделано для того, чтобы рассматриваемые примеры можно было применять в большинстве языков программирования.
Однако часто использование алгоритма связано с некоторыми нюансами, которые приводятся в псевдокоде.
Псевдокод — это текст, похожий на язык программирования, но не являющийся таковым. Он описывает структуры и детали, которые вам понадобятся для применения алгоритма в полноценном коде вне зависимости от используемого языка программирования.
В следующем фрагменте показан пример псевдокода для вычисления наиболь
шего общего делителя (НОД) двух целых чисел.
// Находим наибольший общий делитель для a и b.
// GCD(a, b) = GCD(b, a Mod b).
Integer: Gcd(Integer: a, Integer: b)
While (b != 0)
// Вычисляем остаток.
Integer: remainder = a Mod b
// Находим наибольший общий делитель для b и остатка.
a = b
b = remainder
End While
// Наибольший общий делитель для a и 0 — это a.
Return a
End Gcd
ОПЕРАТОР MODОператор mod используется для нахождения остатка от деления по модулю.
Например, 13 mod 4 = 1, поскольку если 13 разделить на 4, получится целое
число 3 и 1 в остатке. Само уравнение обычно читается как «13 мод 4» или
«13 по модулю 4».
Псевдокод начинается с комментария, который предваряется символом //.
В первой строке кода происходит объявление алгоритма. В нашем случае
это алгоритм Gcd, который возвращает результат в виде целого числа и прини
мает два параметра с именами a и b, каждый из которых также является це-
лым числом.
ЗАМЕЧАНИЕЧасти кода, которые выполняют задачу и по требованию возвращают результат, обычно называются подпрограммами, методами, процедурами, субпроцедурами или функциями.
Далее следует сам метод. Его начинает строка While, открывающая цикл. Код,
идущий после этого оператора, будет исполняться до тех пор, пока действует заданное условие.
Цикл заканчивается оператором End While. Использовать последний не
обязательно — на конец цикла уже указывает отступ, но все же лучше обозначить блок команд.
О завершении метода свидетельствует оператор Return. Рядом с ним указана
величина, которую должен вернуть приведенный алгоритм. Если целью алгоритма является не получение конкретного значения, а, например, систематизация величин или построение структуры данных, то после оператора Return возвращаемая величина не ставится.
Рассмотренный код ничем не отличается от обычного программного.
В последующих примерах вы можете встретить описание инструкции либо величины, приведенное на русском языке в угловых скобках (< >). Это значит, что программный код на основе инструкций вам нужно дописать самостоятельно.
После объявления параметра или переменной (в алгоритме Gcd это параметры a и b, а также переменная remainder) задается их тип с обязательным использованием двоеточия. Например, Integer: remainder.
Для простых циклических переменных с целыми числами подобной процедурой можно пренебречь, достаточно написать For i = 1 To 10.
Еще одно отличие псевдокода от других языков программирования — возмож-
ность использовать цикл For вместе с оператором Step, указывающим на вели
чину, по которой изменяется циклическая переменная.
В конце цикла не забудьте написать Next i (где i — переменная цикла), чтобы напомнить о его окончании.
Обратите внимание на следующий псевдокод:
For i = 100 To 0 Step -5
// Вычисляем…
Next i
Он равнозначен нижеприведенному коду C#:
for (int i = 100; i >= 0; i -= 5)
{
// Вычисляем…
}
В псевдокодах из этой книги вы встретите If-Then-Else, Case и некоторые
другие выражения. Они являются базовыми для всех языков программирования и должны быть вам знакомы.
Остальное, что может понадобиться для кода, записывается в комментариях.
Структура данных, которая может быть вам незнакома (в некоторых языках
программирования ее нет), — это List. Она подобна саморасширяющемуся мас
сиву. С помощью метода Add к концу имеющегося списка данных можно добавить еще один элемент.
Например, следующий псевдокод создает List Of Integer,
в котором содержатся числа от 1 до 10.
List Of Integer: numbers
For i = 1 To 10
numbers.Add(i)
Next i
После того как список объявлен, псевдокод может работать с ним, как с обыч-
ным массивом, и обращаться к любому его элементу. Однако в отличие от массивов, списки позволяют удалять какой бы то ни было элемент и добавлять его в какую угодно позицию.
Многие алгоритмы в книге написаны в виде методов и функций, возвращающих результат. В этом случае в объявлении функции нужно указать тип получаемых данных.
Если функция выполняется без возвращения результата, тип данных не
задается.
рассматриваются темы, которые обычно отсутствуют в профессиональных учебниках: работа с числами, массивы, списки.
Но в книге есть темы, которые обычно не рассматриваются в книгах по алгоритмам и структурам данных: деревья решений (рассматривается минимакс, метод ветвей и границ, эвристики), криптография (перестановочные шифры, подстановки, блочные шифры, RSA).
Весьма полезна для начинающих глава о рекурсии, где помимо традиционных задач (8 ферзей, обход конем и т.п) рассматривается проблема удаления рекурсии (и хвостовой, и общей).
Есть главы и об алгоритмах на графах, и строковые алгоритмы (не только поиск подстрок, но и вычисление расстояния, и анализ арифметических выражений).
Естественно, есть глава о вычислительной сложности.
И весьма полезна для начинающих глава о параллельных вычислениях - рассмотрены все основы.
В общем, очень рекомендую как первую книгу по алгоритмам и структурам данных.