Графы и алгоритмы. Структуры данных. Модели вычислений: учеб. для студентов, обучающихся по специальности 010200 - Прикладная математика и информатика и по направлению 510200 - Прикладная математика и информатика

Оглавление ......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