Дисциплина по направлению
230100.62 – Информатика и вычислительная техника
Лекции
Разработал
ст. преподаватель кафедры ИТИС
________________П.М. Довгалюк
_____ ________________2012 г.
Принято на заседании кафедры
Заведующий кафедрой
______________А.Л. Гавриков
_____ ________________2012 г.
1 Оглавление
2 Стандартная постановка задачи. 4
2.1 Пример постановки задачи. 8
2.2 Пример постановки задачи в стандартной форме. 8
3 Алгоритмы и их сложность. 8
4 Основы анализа программ.. 12
4.1 Пример анализа алгоритмов. 22
5 Выполнение операторов программы.. 23
5.1 Основы доказательства корректности. 25
5.2 Правила вывода. 25
5.2.1 Правило вывода Р1 – усиление предусловия и ослабление постусловия. 25
5.2.2 Правило вывода А1 – получение предусловия оператора присваивания. 26
5.2.3 Правило вывода IF1 - Проверка предусловия условного оператора. 26
5.2.4 Правило вывода IF2 – Получение предусловия условного оператора. 26
5.2.5 Правило вывода IF3 –Условный оператор. 27
5.2.6 Правило вывода IF4 – Условный оператор. 27
5.2.7 Правило вывода S1 – Последовательность операторов. 27
5.2.8 Правило вывода W1 – Цикл с условием продолжения без инициализации. 27
5.2.9 Правило вывода W2 – Цикл с условием продолжения с инициализацией. 28
5.2.10 Правило вывода DC1 – разделяй и властвуй. 29
5.2.11 Правило вывода DC2 – разделяй и властвуй. 29
5.2.12 Правило вывода DC3 – разделяй и властвуй. 29
5.2.13 Правило вывода DC4 – разделяй и властвуй. 29
6 Инвариант цикла. 30
7 Динамическое программирование. 32
7.1 Перемножение нескольких матриц. 32
7.2 Когда применимо динамическое программирование. 37
7.3 Наибольшая общая подпоследовательность. 37
8 Жадные алгоритмы.. 40
8.1 Задача о выборе заявок. 40
9 Абстрактные типы данных. 42
9.1 АТД «Список». 42
9.2 АТД «Стек». 43
9.3 АТД «Очередь». 43
9.4 Множества. 45
10 Хеширование. 46
11 Поиск слова в тексте. 49
12 Сортировка. 51
12.1 Сортировка вставками. 51
12.2 Корневая сортировка. 52
12.3 Пирамидальная сортировка. 53
12.3.1 Переформирование пирамиды.. 54
12.3.2 Построение пирамиды.. 55
12.4 Сортировка слиянием.. 55
13 Управление с помощью таблиц. 58
14 Графы.. 59
14.1 Способы представления графа. 59
14.1.1 Матрица смежности. 59
14.1.2 Матрица инцидентности. 59
14.1.3 Список рёбер. 60
14.2 Алгоритмы обхода графа. 60
14.2.1 Поиск в ширину. 60
14.3 Задача о кратчайшем пути. 62
14.4 Алгоритм Дейкстры.. 66
14.5 Алгоритм Беллмана-Форда. 70
14.6 Задача перекресток. 74
14.7 Максимальный поток. 76
14.8 Метод Форда-Фалкерсона. 77
14.9 Минимальные покрывающие деревья. 84
14.9.1 Алгоритм Крускала. 88
14.9.2 Алгоритм Прима. 89
14.10 Минимальные покрывающие деревья. 90
14.11 Поиск в глубину. 93
14.12 Топологическая сортировка. 101
15 Деревья. 102
15.1 АВЛ-деревья. 103