Брэдфорд Такфилд - Алгоритмы неформально. Инструкция для начинающих питонистов

Python..............................50
Реализация алгоритма Курусимы на Python.........................52
Резюме.........................................................64
Глава 3. Максимизация и минимизация................................65
Выбор ставки налога..............................................65
Шаги в правильном направлении.................................66
Преобразование шагов в алгоритм...............................70
Аргументы против градиентного подъема.............................72
Проблема локальных экстремумов...................................73
Образование и пожизненный доход..............................74
Правильный путь к вершинам образования.........................76
От максимизации к минимизации....................................78
О пользе подъема................................................80
Когда не следует применять алгоритм................................81
Резюме.........................................................83
Глава 4. Сортировка и поиск.........................................84
Сортировка методом вставки.......................................85
Вставка в сортировке методом вставки............................85
Сортировка методом вставки....................................88
Оценка эффективности алгоритма...................................89
Почему так важна эффективность................................90
Точное измерение времени.....................................91
Подсчет шагов................................................92
Сравнение с известными функциями..............................95
Повышение теоретической точности..............................98

8   Оглавление
Нотация «О большое».........................................100
Сортировка слиянием............................................102
Слияние....................................................102
От слияния к сортировке.......................................104
Спящая сортировка..............................................108
От сортировки к поиску..........................................110
Бинарный поиск..............................................110
Применение бинарного поиска.................................113
Резюме........................................................114
Глава 5. Чистая математика.........................................115
Непрерывные дроби.............................................115
Компактное представление числа φ..............................116
Подробнее о непрерывных дробях..............................119
Алгоритм генерирования непрерывных дробей.....................120
От десятичных дробей к непрерывным............................125
От дробей к корням..........................................127
Квадратные корни...............................................128
Вавилонский алгоритм........................................128
Квадратные корни на языке Python...............................130
Генераторы случайных чисел......................................131
Возможна ли случайность......................................131
Линейные конгруэнтные генераторы.............................133
Оценка ГПСЧ...............................................134
Тесты Diehard................................................136
Регистры сдвига с линейной обратной связью......................138
Резюме........................................................141
Глава 6. Расширенная оптимизация..................................142
Жизнь коммивояжера............................................143
Постановка задачи...........................................144
Ум против грубой силы........................................148
Алгоритм ближайшего соседа..................................150
Реализация поиска ближайшего соседа..........................150
Проверка дальнейших улучшений...............................152

Оглавление   9

Жадные алгоритмы...........................................154
Температурная функция.......................................155
Имитация отжига................................................158
Настройка алгоритма.........................................161
Предотвращение крупных потерь................................163
Поддержка отмены...........................................164
Проверка эффективности......................................166
Резюме........................................................168
Глава 7. Геометрия................................................169
Задача почтмейстера............................................169
Треугольники: краткий курс........................................172
Продвинутая теория треугольников.................................175
Поиск центра описанной окружности............................175
Расширение графического вывода...............................178
Триангуляция Делоне.............................................180
Инкрементное генерирование триангуляций Делоне................182
Реализация триангуляций Делоне...............................185
От триангуляции Делоне к диаграмме Вороного.......................190
Резюме........................................................195
Глава 8. Язык....................................................196
Почему языковые алгоритмы сложны................................196
Расстановка пробелов...........................................197
Определение списка слов и поиск слов...........................198
Составные слова.............................................200
Проверка потенциальных слов между существующими пробелами.....201
Использование импортированного корпуса для проверки
действительных слов..........................................202
Поиск первой и второй половин потенциальных --">