Вопросы по ОП.08 Теория алгоритмов

Задачи из теории графов

Одной из самых старых и, пожалуй, наиболее интересных областей алгоритмики является обработка графов. Нестрого граф можно определить как набор точек, называемых вершинами, часть из которых соединена отрезками, называемыми ребрами. (Более строгое определение графа будет дано в следующем разделе.)

Графы являются довольно интересным объектом для изучения как с теоретиче­ской, так и с практической точек зрения. С помощью графов можно смоделировать довольно большое количество процессов, происходящих в реальной жизни, на­пример функционирование транспортных и коммуникационных сетей, календар­ное планирование проекта и т.д. Одна из последних интересных задач — оценка "диаметра" Web, заключающаяся в определении максимального количества ссы­лок, которые нужно пройти от одной Web-страницы до другой по оптимальному маршруту.

К числу основных алгоритмов теории графов относят следующие:

ü алгоритмы обхода графа (этот класс алгоритмов позволяет ответить на
такие вопросы, как каким образом можно объехать все узлы железно­
дорожной сети);

ü алгоритмы определения кратчайшего пути (этот класс алгоритмов поз­-
воляет ответить на вопросы наподобие следующего: каков кратчайший
путь между двумя городами);

ü алгоритмы топологической сортировки для ориентированных графов
ребрами (этот класс алгоритмов позволяет выяснить, не является ли
множество читаемых студентам курсов внутренне противоречивым).

1. Алгоритмы. Общие сведения. Основные требования к алгоритмам. Свойства алгоритмов. Способы представления алгоритмов.

2. Основные алгоритмические структуры.

3. Машина Поста.

4. Машина Тьюринга.

5. Алгоритмически неразрешимые проблемы.

6. Арифметика многоразрядных целых чисел.

7. Комбинаторные алгоритмы. Классические задачи комбинаторики.

8. Генерация комбинаторных объектов.

9. Перебор и методы его сокращения.

10. Сортировка. Метод грубой силы.

11. Исчерпывающий перебор. Задача коммивояжора. Задача о рюкзаке.

12. Методдекомпозиции. Сортировка слияние.

13. Быстрая сортировка. Двоичный поиск.

14. Алгоритмы на графах. Представление графа в памяти компьютера.

15. Поиск в графе(в глубину, в ширину).

16. Кратчайшие пути.

17. Динамическое программирование.

18. Алгоритмы вычислительной геометрии.

19. Сравнительные оценки алгоритмов. Классификация алгоритмов по виду функции трудоёмкости.

20. Теория сложности вычислений и сложностные классы задач.

21. Рекурсивные алгоритмы и методы их анализа.

ЛИТЕРАТУРА:

Основная:

1. Верещагин, Н.К. Лекции по математической логике и теории алгоритмов. Часть 3. Вычислимые функции [Электронный ресурс]/ Верещагин Н.К., Шень А.— Электрон. текстовые данные.— М.: МЦНМО, 2012.— 160 c.ISBN:978-5-4439-0014-8

2. Ершов Ю.Л. Математическая логика [Электронный ресурс]: учебное пособие/ Ершов Ю.Л., Палютин Е.А.— Электрон. текстовые данные.— М.: ФИЗМАТЛИТ, 2011.— 356 c ISBN:978-5-9221-1301-4

Дополнительная:

1. Алексеев В.Е. Графы и алгоритмы. Структуры данных. Модели вычислений [Электронный ресурс]: учебник/ Алексеев В.Е., Таланов В.А.— Электрон. текстовые данные.— М.: БИНОМ. Лаборатория знаний, Интернет-Университет Информационных Технологий (ИНТУИТ), 2012.— 320 c. ISBN:5-9556-0066-3

2. Окулов, С. М. Программирование в алгоритмах / С. М. Окулов. — М.: БИНОМ. Лаборатория знаний, 2002. — 341 с: ил. ISBN 5-94774-010-9

Дата добавления: 2017-01-13