- •Часть 1. Курс лекций
- •Введение.
- •Цели освоения дисциплины
- •Место дисциплины в структуре ооп впо
- •Компетенции обучающегося, формируемые в результате освоения дисциплины (модуля)
- •Тема 1. Алгоритмы на графах (6 часов).
- •Лекция 1. Начальные понятия теории графов.
- •Определение графа
- •Графы и бинарные отношения
- •Откуда берутся графы
- •Число графов
- •Смежность, инцидентность, степени
- •Некоторые специальные графы
- •Графы и матрицы
- •Взвешенные графы
- •Изоморфизм
- •Инварианты
- •Операции над графами
- •Локальные операции
- •Подграфы
- •Алгебраические операции
- •Лекция 2. Поиск в глубину и ширину. Поиск в ширину
- •Процедура поиска в ширину
- •Процедура поиска в глубину
- •Глубинная нумерация
- •Построение каркаса
- •Шарниры
- •Маршруты, пути, циклы
- •Связность и компоненты
- •Метрические характеристики графов
- •Маршруты и связность в орграфах
- •Эйлеровы пути и циклы
- •Построение эйлерова цикла
- •Гамильтоновы пути и циклы
- •Тема 2. Алгоритмы комбинаторного перебора (6 часов).
- •Размещения с повторениями
- •Перестановки
- •Подмножества
- •Разбиения
- •Лекция 5. Коды Грея. Коды Грея и аналогичные задачи
- •Лекция 6. Применение методов комбинаторного перебора.
- •Подсчет количеств
- •Тема 3. Общие методы разработки алгоритмов (6 часов).
- •Ферзи, не бьющие друг друга: обход дерева позиций
- •Лекция 8. Рекурсия. Примеры рекурсивных программ
- •Рекурсивная обработка деревьев
- •Лекция 9. Построение итеративных алгоритмов по рекурсивным.
- •Стек отложенных заданий
- •Более сложные случаи рекурсии
- •Библиографический список
- •Содержание
- •Тема 1. Алгоритмы на графах. 6
- •Тема 2. Алгоритмы комбинаторного перебора. 48
- •Тема 3. Общие методы разработки алгоритмов. 66
- •Шутов Антон Владимирович Медведев Юрий Алексеевич
- •600014, Г. Владимир, ул. Университетская, 2, тел. 33-87-40
Библиографический список
Кормен Т., Лейзерсон Ч., Ривест Р., Штайн К. Алгоритмы: построение и анализ. М.: Вильямс, 2007.
Ахо А., Хопкрофт Д., Ульман Д. Структуры данных и алгоритмы. М.: Вильямс, 2007.
Окулов С.М. Программирование в алгоритмах. М.: Бином, 2007.
Кнут Д. Искусство программирования. Т. 4 Вып.2. Генерация всех кортежей и перестановок. М.: Вильямс, 2008.
Кнут Д. Искусство программирования. Т. 4 Вып.2. Генерация всех сочетаний и разбиений. М.: Вильямс, 2008.
Кнут Д. Искусство программирования. Т. 4 Вып.2. Генерация всех деревьев. История комбинаторной генерации. М.: Вильямс, 2008.
Седжвик Р. Фундаментальные алгоритмы на С++. М.: Вильямс, 2011.
Ху Т.Ч., Шинг М.Т. Комбинаторные алгоритмы Нижний Новгород: Изд-во Нижегородского госуниверситета им. Н.И. Лобачевского, 2004.
Новиков Ф.А. Дискретная математика для программистов. СПб.: Питер, 2012.
Содержание
Введение 4
Тема 1. Алгоритмы на графах. 6
Лекция 1. Начальные понятия теории графов. 7
Лекция 2. Поиск в глубину и ширину. 21
Лекция 3. Эйлеровы и гамильтоновы циклы. 35
Тема 2. Алгоритмы комбинаторного перебора. 48
Лекция 4. Базовые комбинаторные объекты. 49
Лекция 5. Коды Грея. 55
Лекция 6. Применение методов комбинаторного перебора. 61
Тема 3. Общие методы разработки алгоритмов. 66
Лекция 7. Обход дерева и перебор с возвратом. 67
Лекция 8. Рекурсия. 78
Лекция 9. Построение итеративных алгоритмов по рекурсивным. 90
БИБЛИОГРАФИЧЕСКИЙ СПИСОК 99
Шутов Антон Владимирович Медведев Юрий Алексеевич
СТРУКТУРЫ И АЛГОРИТМЫ КОМПЬЮТЕРНОЙ
ОБРАБОТКИ ДАННЫХ
Курс лекций
Издается в авторской редакции
Подписано в печать 20.12.2013 Усл. п. л. – 7,25 Заказ 07 - 12 |
Формат 84 x 108 1/32 Уч. –изд. л. – 7,45 Тираж 50 экз. |
Отпечатано в отделе оперативной полиграфии ВГГУ
600014, Г. Владимир, ул. Университетская, 2, тел. 33-87-40