Решение задач на тему: Динамическое программирование, алгоритмы графах

Введение

Существует целый класс задач по программированию, которые проще решаются, если ученик владеет определенным набором знаний, умений и навыков в области алгоритмов на графах. Это происходит потому, что такие задачи могут быть переформулированы в терминах теории графов.

Теория графов содержит огромное количество определений, теорем и алгоритмов. И поэтому данный материал не может претендовать, и не претендует, на полноту охвата материала. Однако, по мнению автора, предлагаемые сведения являются хорошим компромиссом между объемом материала и его "коэффициентом полезного действия" в практическом программировании и решении олимпиадных задач.

Иногда решение основной задачи приходится формулировать в терминах несколько модифицированных подзадач. Именно такие проблемы рассматриваются в данной работе.

Оглавление

- Введение

- Алгоритмы, использующие решение дополнительных подзадач

- Основные определения теории графов

- Поиск пути между парой вершин невзвешенного графа

- Пути минимальной длины во взвешенном графе Заключение

- Литература

Список литературы

1. Андреева Е., Фалина И. Системы счисления и компьютерная арифметика. М.: Лаборатория базовых знаний, 2000.

2. Станкевич А.С. Решение задач I Всероссийской командной олимпиады по программированию. "Информатика", №12, 2001.

3. Окулов С.М. 100 задач по информатике. Киров: изд-во ВГПУ, 2000.

4. Андреева Е.В. Решение задач XIII Всероссийской олимпиады по информатике. "Информатика", №19, 2001.

5. Ахо А.А., Хопкрофт Д.Э., Ульман Д.Д. Структуры данных и алгоритмы. М.: "Вильямс", 2000.

6. Кормен Т., Лейзерсон Ч., Ривест Р. Алгоритмы. Построение и анализ. М.: МЦНМО, 2000.

7. Липский В. Комбинаторика для программистов. М.: "Мир", 1988.

8. Вирт Н. Алгоритмы и структуры данных. Санкт-Петербург: "Невский диалект", 2001.