Защита курсовой работы. К защите допускаются отчёты, имеющие все перечисленные рубрики с приложением текста программы на машинном носителе в виде

К защите допускаются отчёты, имеющие все перечисленные рубрики с приложением текста программы на машинном носителе в виде, пригодном для компиляции. На защите следует продемонстрировать работу программы, обосновать решения, принятые при реализации алгоритма и выводы о его временной сложности.

3.3.4. Варианты индивидуальных заданий к теме «Графы»

№ вари- анта	Алгоритм для исследования
	Получение множества двудольных компонент неориентированного графа
	Проверка ориентированного графа на ацикличность
	Поиск кратчайшего пути между заданной парой вершин в не­о­ри­ен­ти­рованном графе с нагруженными рёбрами
	Обнаружение всех элементарных циклов ориентированного графа. Подсказка: элементарными будут все фундаментальные циклы графа и их линейные комбинации при непустых пересечениях
	Подсчёт расстояний от произвольной вершины до всех остальных вершин в ори­ен­ти­ро­ванном ненагруженном графе
	Получение множества компонент сильной связности в ориентированном графе
	Проверка неориентированных графов на изо­мор­физм
	Отыскание кратчайшего пути между произвольной парой вершин в ори­ен­­ти­ро­ван­ном графе с нагруженными рёбрами (веса рёбер неотрицательные)
	Отыскание клики наибольшей мощности в неориентированном графе
	Отыскание максимального паросочетания в произвольном неориентированном графе
	Построение полного множества циклов для ориентированного графа
	Алгоритм Краскала для нахождения стягивающего дерева наименьшей стоимости не­о­ри­ен­ти­ро­ван­но­го гра­фа с нагруженными рёбрами
	Вычисления матрицы расстояний между всеми парами вершин в о­ри­ен­ти­ро­ван­ном графе с нагруженными рёбрами
	Проверка на изо­мор­физм двух ориентированных графов
	Построение эйлерова пути в неориентированном графе
	Рас­краска минимальным числом цветов вершин неориентированного гра­фа с соблюдением условия: никакое ребро не соединяет вершины одного цве­та
	Проверка наличия цикла отрицательной стоимости в ориентированном графе с нагруженными рёбрами
	Отыскание минимального вершинного покрытия неориентированного графа
	Алгоритм Прима для нахождения стягивающего дерева наименьшей стоимости не­о­ри­ен­ти­ро­ван­но­го гра­фа с нагруженными рёбрами
	Нахождения гамильтонова пути в неориентированном графе
	Вычисление матрицы расстояний между всеми парами вершин не­о­ри­ен­ти­ро­ван­ного графа с нагруженными рёбрами
	Построение глубинного стягивающего леса для произвольного ­о­ри­ен­ти­ро­ван­ного графа
	Построение фундаментального множества циклов в неориентированном графе
	Построение эйлерова цикла в ориентированном графе
	Поразрядная сортировка произвольной последовательности целых чисел
	Построение ширинного стягивающего леса для неориентированного графа
	Построение трансверсали максимальной мощности для произвольного набора частично пересекающихся подмножеств
	Построение глу­бинного стягивающего леса для неориентированного графа

Окончание таблицы

№ вари- анта	Алгоритм для исследования
	Топологическая сортировка вершин ориентированного ациклического графа
	Получение ширинного стягивающего леса для ориентированного графа
	Получение множества компонент двусвязности для произвольного неориентированного графа
	Построение максимального паросочетания в двудольном неориентированном графе
	Получение минимального вершинного покрытия для двудольного неориентированного графа
	Проверка на изоморфизм произвольных корневых деревьев
	Отыскание кратчайшего пути между заданной парой вершин в произвольном ориентированном графе с нагруженными рёбрами
	Отыскание кратчайшего пути между заданной парой вершин в произвольном ациклическом ориентированном графе с нагруженными рёбрами
	Отыскание элементарного кратчайшего пути через все вершины произвольного неориентированного графа с нагруженными рёбрами (задача коммивояжёра)
	Пирамидальная сортировка произвольной последовательности целых чисел
	Сортировка слиянием для произвольной последовательности целых чисел
	Сортировки произвольного набора цепочек (строк) из букв латинского алфавита
	Оптимальная упаковка рюкзака заданного объёма грузами, объёмы которых заданы произвольной последовательностью целых чисел
	Оптимальная раскладка по ящикам заданного объёма набора грузов, объёмы которых заданы произвольной последовательностью целых чисел
	Нахождение в неориентированном графе компоненты, изоморфной заданному графу
	Нахождение минимального рёберного покрытия неориентированного графа
	Нахождение максимального независимого множества вершин неориентированного графа
	Нахождение раскраски вершин неориентированного графа минимальным числом цветов
	Нахождение минимального множества вершин неориентированного графа, разрезающих циклы
	Нахождение минимального множества рёбер неориентированного графа, разрезающих циклы
	Проверка неориентированного графа на планарность
	Построение множества точек сочленения неориентированного графа

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

1. Седжвик Р. Алгоритмы на С++.: Пер. с англ. — М.: ООО «И. Д. Вильямс», 2011. — 1156 с.: ил.

2. Новиков Ф. А. Дискретная математика: Учебник для вузов, 2-е изд. Стандарт третьего поколения. — СПб.: Питер, 2013. — 432 с.: ил.

3. Седжвик Р. Фундаментальные алгоритмы С++. — М., 2002. — 484 с.

4. С/С++. Программирование на языке высокого уровня / Т. А. Павловская. — СПб.: Питер, 2013. — 461 с.: ил.

5. Прата С. Язык программирования C++. Изд. 6‑е. — М.: Вильямс, 2011. — 1244 с.

6. Макконелл Дж. Основы современных алгоритмов. — Изд. 2-е. — М., 2004. — 368 с.

7. Ахо Дж., Хопкрофт А., Ульман Дж. Структуры данных и алгоритмы. — СПб., 2001. — 382 c. (доп. тир. 2003, 2007).

8. Кормен Т., Лейзерсон Ч., Ривест Р., Штайн К. Алгоритмы: построение и анализ, 2-е изд.: Пер. с англ. — М., 2005. — 1296 с.: ил.

9. Липский В. Комбинаторика для программистов. — М., 1978. — 213 с.

10. Вирт Н. Алгоритмы и структуры данных. — СПб., 1989 (доп. тир. 2001).

11. Ахо Дж., Хопкрофт А., Ульман Дж. Построение и анализ вычислительных алгоритмов. — М., 1979.

12. Страуструп Б. Язык программирования С++. Второе дополненное издание. — М., 2001. – 1098 с. (доп. тир. 2002, 5, 6, 7).

13. Шилдт Г. Искусство программирования наС++. — СПб., 2005. — 474 с.

14. Шилдт Г. Самоучитель C++. 3-е изд. — СПб., 2000. — 683 с. (доп. тир. 2002, 2004, 2005, 2006 г.).

15. Новиков Ф. А. Дискретная математика для программистов. — СПб.: Питер, 2000. — 304 с.: ил.

16. Гэри М., Джонсон Д. Вычислительные машины и трудно решаемые задачи. — М.: Мир, 1982. — 419 с.

СОДЕРЖАНИЕ

ВВЕДЕНИЕ........................................................................................................................... 3

1. МНОЖЕСТВА................................................................................................................... 5

1.1. Представление множества набором элементов.................................................. 5

1.1.1. Практикум по теме........................................................................................... 7

1.1.2. Варианты индивидуальных заданий к теме «Множества».......................... 7

Контрольные вопросы.................................................................................................. 10

1.2. Представление множества отображением на универсум................................ 11

1.2.1. Практикум по теме.............................................................................................. 13

1.3. Генерация тестов....................................................................................................... 13

1.3.1. Генерация последовательности всех подмножеств заданного множества 13

1.3.2. Генерация перестановок.................................................................................... 14

1.3.3. Генерация случайного подмножества.............................................................. 15

1.3.4. Случайное подмножество заданной мощности.............................................. 16

1.3.5. Практикум по теме............................................................................................ 17

1.3.6. Контрольные вопросы........................................................................................ 17

1.4. Измерение времени решения задачи с помощью ЭВМ........................................ 17

1.4.1. Использование функции clock ().......................................................................... 17

1.4.2. Практикум по теме............................................................................................ 18

1.4.3. Контрольные вопросы........................................................................................ 18

1.5. Множество как объект.............................................................................................. 18

1.5.1. Практикум по теме............................................................................................ 26

1.5.2. Контрольные вопросы........................................................................................ 26

1.6. Отчёт по теме.......................................................................................................... 26

2. ДЕРЕВЬЯ......................................................................................................................... 27

2.1. Обходы дерева как рекурсивной структуры данных............................................ 29

2.2. Создание дерева........................................................................................................ 30

2.3. Вывод изображения дерева на экран монитора..................................................... 31

2.4. Шаблоны классов для очереди и стека и нерекурсивные алгоритмы обхода дерева 33

2.4.1. Практикум по теме............................................................................................ 35

2.4.2. Варианты индивидуальных заданий к теме «Деревья».................................. 35

2.4.3. Контрольные вопросы........................................................................................ 37

Отчёт по теме................................................................................................................. 38

3. ГРАФЫ............................................................................................................................. 39

3.1. Обходы графов.......................................................................................................... 41

3.2. Некоторые задачи на графах.................................................................................... 41

3.3. Переборные алгоритмы на графах.......................................................................... 45

3.3.1. Практикум по теме............................................................................................ 54

3.3.2. Содержание пояснительной записки к курсовой работе............................... 54

Защита курсовой работы.............................................................................................. 54

3.3.4. Варианты индивидуальных заданий к теме «Графы».................................... 55

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

Приложение. Оценка временной сложности алгоритмов........................................... 59