Читайте также:
|
Доцент каф. Вычислительной математики
Механико-Математического ф-та
МГУ им. М.В.Ломоносова
Староверов В.М.
2010г.
Лекция 1............................................................................................................................. 5
Представление чисел в ЭВМ....................................................................................... 5
Целые.......................................................................................................................... 5
Вещественные............................................................................................................ 5
Ошибки вычислений.................................................................................................... 9
Лекция 2........................................................................................................................... 11
Алгоритмы. Сведение алгоритмов........................................................................... 11
Нижние и верхние оценки......................................................................................... 11
Сортировки.................................................................................................................. 13
Постановка задачи................................................................................................... 13
Сортировка пузырьком........................................................................................... 14
Сортировка слиянием с рекурсией........................................................................ 16
Сортировка слиянием без рекурсии...................................................................... 18
Лекция 3........................................................................................................................... 19
Алгоритмы. Сведение алгоритмов........................................................................... 19
Сортировки и связанные с ними задачи................................................................... 19
QuickSort.................................................................................................................. 19
Доказательство корректности работы алгоритма............................................... 22
Оценки времени работы алгоритма...................................................................... 23
Некоторые задачи, сводящиеся к сортировке..................................................... 26
Лекция 4........................................................................................................................... 31
Алгоритмы. Сведение алгоритмов........................................................................... 31
Сортировки и связанные с ними задачи................................................................... 31
HeapSort или сортировка с помощью пирамиды................................................ 31
Алгоритмы сортировки за время O(N)................................................................. 33
Сортировка подсчетом............................................................................................ 33
Цифровая сортировка............................................................................................ 34
Сортировка вычерпыванием................................................................................. 34
Лекция 5........................................................................................................................... 37
Алгоритмы. Сведение алгоритмов........................................................................... 37
Порядковые статистики.............................................................................................. 37
Поиск порядковой статистики за время Q(N) в среднем.................................... 37
Поиск порядковой статистики за время Q(N) в худшем случае........................ 39
Язык программирования C........................................................................................... 40
Переменные................................................................................................................ 41
Структуры данных.......................................................................................................... 43
Вектор........................................................................................................................... 43
Стек............................................................................................................................... 44
Лекция 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
........................................................................................................................................... 66
Лекция 8........................................................................................................................... 67
Структуры данных. Графы............................................................................................ 67
Поиск кратчайшего пути в графе......................................................................... 67
Лекция 9........................................................................................................................... 72
Бинарные деревья поиска............................................................................................... 72
Поиск элемента в дереве........................................................................................ 73
Добавление элемента в дерево............................................................................... 73
Поиск минимального и максимального элемента в дереве................................ 74
Удаление элемента из дерева................................................................................. 74
Поиск следующего/предыдущего элемента в дереве.......................................... 74
Слияние двух деревьев........................................................................................... 74
Разбиение дерева по разбивающему элементу..................................................... 75
Сбалансированные и идеально сбалансированные бинарные деревья поиска........ 76
Операции с идеально сбалансированным деревом............................................. 77
Операции со сбалансированным деревом............................................................ 78
Поиск элемента в дереве........................................................................................ 78
Добавление элемента в дерево............................................................................... 78
Удаление элемента из дерева................................................................................. 82
Поиск минимального и максимального элемента в дереве................................ 82
Поиск следующего/предыдущего элемента в дереве.......................................... 82
Слияние двух деревьев........................................................................................... 82
Разбиение дерева по разбивающему элементу..................................................... 84
Лекция 10......................................................................................................................... 86
Красно-черные деревья.................................................................................................. 86
Отступление на тему языка С. Поля структур......................................................... 86
Отступление на тему языка С. Бинарные операции............................................... 88
Высота красно-черного дерева.................................................................................. 88
Добавление элемента в красно-черное дерево......................................................... 89
Однопроходное добавление элемента в красно-черное дерево............................. 91
Удаление элемента из красно-черного дерева......................................................... 93
Лекция 11......................................................................................................................... 96
B-деревья......................................................................................................................... 96
Высота B-дерева.......................................................................................................... 97
Поиск вершины в B-дереве........................................................................................ 98
Отступление на тему языка С. Быстрый поиск и сортировка в языке С.............. 98
Добавление вершины в B-дерево............................................................................ 100
Удаление вершины из B-дерева............................................................................... 101
Лекция 12....................................................................................................................... 105
Хеширование................................................................................................................. 105
Метод многих списков............................................................................................. 105
Метод линейных проб.............................................................................................. 106
Метод цепочек........................................................................................................... 110
Хэш-функции............................................................................................................. 113
Хэш-функции на основе деления........................................................................ 113
Хэш-функции на основе умножения.................................................................. 113
CRC-алгоритмы обнаружения ошибок....................................................................... 114
Лекция 14....................................................................................................................... 118
Поиск строк.................................................................................................................... 118
Отступление на тему языка С. Ввод-вывод строк из файла................................. 118
Алгоритм поиска подстроки с использованием хеш-функции (Алгоритм Рабина-Карпа) 119
Конечные автоматы.................................................................................................. 120
Отступление на тему языка С. Работа со строками............................................... 121
Алгоритм поиска подстроки, основанный на конечных автоматах................... 121
Лекция 15....................................................................................................................... 123
Алгоритм поиска подстроки Кнута-Морриса-Пратта (на основе префикс-функции) 123
Алгоритм поиска подстроки Бойера-Мура (на основе стоп-символов/безопасных суффиксов) 125
Эвристика стоп-символа...................................................................................... 125
Эвристика безопасного суффикса....................................................................... 127
Форматы BMP и RLE................................................................................................ 130
Лекция 1
Дата добавления: 2015-10-30; просмотров: 123 | Нарушение авторских прав
| <== предыдущая страница | | | следующая страница ==> |
| The form the schedule of performance and delivery of works | | | Typedef struct CVertex2_ |