Author(s): В. Е. Алексеев, В. А. Таланов
Year: 2012
Language: Russian
Pages: 322
Оглавление ......Page 6
Часть I. Графы и алгоритмы ......Page 10
Лекция 1. Начальные понятия теории графов ......Page 12
Лекция 2. Маршруты, связность, расстояния ......Page 28
Лекция 3. Важнейшие классы графов ......Page 35
Лекция 4. Поиск в ширину ......Page 46
Лекция 5. Поиск в глубину ......Page 52
Лекция 6. Блоки ......Page 59
Лекция 7. Пространство циклов графа ......Page 66
Лекция 8. Эйлеровы и гамильтоновы циклы ......Page 73
Лекция 9. Независимые множества, клики, вершинные покрытия ......Page 79
Лекция 10. Раскраски ......Page 87
Лекция 11. Рационализация переборных алгоритмов ......Page 93
Лекция 12. Паросочетания ......Page 98
Лекция 13. Оптимальные каркасы ......Page 107
Лекция 14. Жадные алгоритмы и матроиды ......Page 111
Лекция 15. Кратчайшие пути ......Page 117
Лекция 16. Потоки ......Page 120
Часть II. Структуры данных ......Page 126
Лекция 17. Вводная ......Page 128
Лекция 18. Списки ......Page 136
Лекция 19. Разделенные множества ......Page 153
Лекция 20. Приоритетные очереди ......Page 172
Лекция 21. Объединяемые приоритетные очереди ......Page 190
Лекция 22. Ленивые левосторонние и самоорганизующиеся кучи ......Page 205
Лекция 23. Биномиальные и фибоначчиевы кучи ......Page 210
Лекция 24. Тонкие кучи ......Page 215
Лекция 25. Толстые кучи ......Page 224
Лекция 26. Поисковые деревья ......Page 240
Часть III. Модели вычислений ......Page 254
Лекция 27. Машины Тьюринга ......Page 256
Лекция 28. Абак, алгорифмы Маркова, равнодоступная адресная машина ......Page 277
Лекция 29. Формальные языки ......Page 288
Лекция 30. Логическое профаммирование ......Page 306
Литература ......Page 319
