Конспект лекций

по курсу

Алгоритмы и алгоритмические языки

Доцент каф. Вычислительной математики

Механико-Математического ф-та

МГУ им. М.В.Ломоносова

Староверов В.М.

2010г.

Лекция 1 5

Представление чисел в ЭВМ 5

Целые 5

Вещественные 5

Ошибки вычислений 8

Лекция 2 11

Алгоритмы. Сведение алгоритмов. 11

Нижние и верхние оценки. 11

Сортировки 13

Постановка задачи 13

Сортировка пузырьком. 14

Сортировка слиянием с рекурсией. 16

Сортировка слиянием без рекурсии. 18

Лекция 3 19

Алгоритмы. Сведение алгоритмов. 19

Сортировки и связанные с ними задачи. 19

QuickSort. 19

Доказательство корректности работы алгоритма. 22

Оценки времени работы алгоритма. 23

Некоторые задачи, сводящиеся к сортировке. 26

Лекция 4 30

Алгоритмы. Сведение алгоритмов. 30

Сортировки и связанные с ними задачи. 30

HeapSort или сортировка с помощью пирамиды. 30

Алгоритмы сортировки за время O(N) 32

Сортировка подсчетом 32

Цифровая сортировка 33

Сортировка вычерпыванием 33

Лекция 5 36

Алгоритмы. Сведение алгоритмов. 36

Порядковые статистики. 36

Поиск порядковой статистики за время (N) в среднем 36

Поиск порядковой статистики за время (N) в худшем случае 38

Язык программирования C. 40

Переменные 40

Структуры данных. 42

Вектор. 42

Стек. 43

Лекция 6 47

Структуры данных ( + в языке С: массивы, структуры, оператор typedef). 47

Стек. 47

Стек. Реализация 1 (на основе массива). 47

Стек. Реализация 2 (на основе массива с использованием общей структуры). 48

Стек. Реализация 3 (на основе указателей). 48

Стек. Реализация 4 (на основе массива из двух указателей). 49

Стек. Реализация 5 (на основе указателя на указатель). 49

Очередь. 50

Дек. 51

Списки 52

Стандартная ссылочная реализация списков 53

Ссылочная реализация списков с фиктивным элементом 55

Реализация L2-списка на основе двух стеков 56

Реализация L2-списка с обеспечением выделения/освобождения памяти 57

Лекция 7 58

Структуры данных. Графы. 58

Графы 58

Поиск пути в графе с наименьшим количеством промежуточных вершин 58

Представление графа в памяти ЭВМ 63

Лекция 8 66

Структуры данных. Графы. 66

Поиск кратчайшего пути в графе 66

Лекция 9 71

Бинарные деревья поиска 71

Поиск элемента в дереве 72

Добавление элемента в дерево 72

Поиск минимального и максимального элемента в дереве 73

Удаление элемента из дерева 73

Поиск следующего/предыдущего элемента в дереве 73

Слияние двух деревьев 73

Разбиение дерева по разбивающему элементу 74

Сбалансированные и идеально сбалансированные бинарные деревья поиска 75

Операции с идеально сбалансированным деревом 76

Операции со сбалансированным деревом 77

Поиск элемента в дереве 77

Добавление элемента в дерево 77

Удаление элемента из дерева 81

Поиск минимального и максимального элемента в дереве 81

Поиск следующего/предыдущего элемента в дереве 81

Слияние двух деревьев 81

Разбиение дерева по разбивающему элементу 83

Лекция 10 84

Красно-черные деревья 84

Отступление на тему языка С. Поля структур. 84

Отступление на тему языка С. Бинарные операции. 86

Высота красно-черного дерева 86

Добавление элемента в красно-черное дерево 87

Однопроходное добавление элемента в красно-черное дерево 89

Удаление элемента из красно-черного дерева 91

Лекция 11 94

B-деревья 94

Высота B-дерева 95

Поиск вершины в B-дереве 96

Отступление на тему языка С. Быстрый поиск и сортировка в языке С 96

Добавление вершины в B-дерево 98

Удаление вершины из B-дерева 99

Лекция 12 103

Хеширование 103

Метод многих списков 103

Метод линейных проб 104

Метод цепочек 108

Хэш-функции 111

Хэш-функции на основе деления 111

Хэш-функции на основе умножения 111

CRC-алгоритмы обнаружения ошибок 112

Лекция 14 116

Поиск строк 116

Отступление на тему языка С. Ввод-вывод строк из файла 116

Алгоритм поиска подстроки с использованием хеш-функции (Алгоритм Рабина-Карпа) 117

Конечные автоматы 118

Отступление на тему языка С. Работа со строками 119

Алгоритм поиска подстроки, основанный на конечных автоматах 119

Лекция 15 121

Алгоритм поиска подстроки Кнута-Морриса-Пратта (на основе префикс-функции) 121

Алгоритм поиска подстроки Бойера-Мура (на основе стоп-символов/безопасных суффиксов) 123

Эвристика стоп-символа 123

Эвристика безопасного суффикса 125

Форматы BMP и RLE 128