Читайте также:
|
Доцент каф. Вычислительной математики
Механико-Математического ф-та
МГУ им. М.В.Ломоносова
Староверов В.М.
2010г.
Лекция 1. 5
Представление чисел в ЭВМ... 5
Целые. 5
Вещественные. 5
Ошибки вычислений. 7
Лекция 2. 9
Алгоритмы. Сведение алгоритмов. 9
Нижние и верхние оценки. 9
Сортировки. 10
Постановка задачи. 10
Сортировка пузырьком. 11
Сортировка слиянием с рекурсией. 12
Сортировка слиянием без рекурсии. 14
Лекция 3. 15
Алгоритмы. Сведение алгоритмов. 15
Сортировки и связанные с ними задачи. 15
QuickSort. 15
Доказательство корректности работы алгоритма. 18
Оценки времени работы алгоритма. 19
Некоторые задачи, сводящиеся к сортировке. 22
Лекция 4. 25
Алгоритмы. Сведение алгоритмов. 25
Сортировки и связанные с ними задачи. 25
HeapSort или сортировка с помощью пирамиды. 25
Алгоритмы сортировки за время O(N) 27
Сортировка подсчетом.. 27
Цифровая сортировка. 28
Сортировка вычерпыванием.. 28
Лекция 5. 31
Алгоритмы. Сведение алгоритмов. 31
Порядковые статистики. 31
Поиск порядковой статистики за время Q(N) в среднем.. 31
Поиск порядковой статистики за время Q(N) в худшем случае. 33
Язык программирования C. 34
Переменные. 35
Структуры данных. 37
Вектор. 37
Стек. 38
Лекция 6. 41
Структуры данных (+ в языке С: массивы, структуры, оператор typedef). 41
Стек. 41
Стек. Реализация 1 (на основе массива). 41
Стек. Реализация 2 (на основе массива с использованием общей структуры). 42
Стек. Реализация 3 (на основе указателей). 42
Стек. Реализация 4 (на основе массива из двух указателей). 43
Стек. Реализация 5 (на основе указателя на указатель). 43
Очередь. 44
Дек. 45
Списки. 46
Стандартная ссылочная реализация списков. 47
Ссылочная реализация списков с фиктивным элементом.. 49
Реализация L2-списка на основе двух стеков. 50
Реализация L2-списка с обеспечением выделения/освобождения памяти. 51
Лекция 7. 52
Структуры данных. Графы. 52
Графы.. 52
Поиск пути в графе с наименьшим количеством промежуточных вершин. 52
Представление графа в памяти ЭВМ... 57
Лекция 8. 60
Структуры данных. Графы. 60
Поиск кратчайшего пути в графе. 60
Лекция 9. 65
Бинарные деревья поиска. 65
Поиск элемента в дереве. 66
Добавление элемента в дерево. 66
Поиск минимального и максимального элемента в дереве. 67
Удаление элемента из дерева. 67
Поиск следующего/предыдущего элемента в дереве. 67
Слияние двух деревьев. 67
Разбиение дерева по разбивающему элементу. 68
Сбалансированные и идеально сбалансированные бинарные деревья поиска. 69
Операции с идеально сбалансированным деревом.. 70
Операции со сбалансированным деревом.. 71
Поиск элемента в дереве. 71
Добавление элемента в дерево. 71
Удаление элемента из дерева. 75
Поиск минимального и максимального элемента в дереве. 75
Поиск следующего/предыдущего элемента в дереве. 75
Слияние двух деревьев. 75
Разбиение дерева по разбивающему элементу. 77
Лекция 10. 78
Красно-черные деревья. 78
Отступление на тему языка С. Поля структур. 78
Отступление на тему языка С. Бинарные операции. 80
Высота красно-черного дерева. 80
Добавление элемента в красно-черное дерево. 81
Однопроходное добавление элемента в красно-черное дерево. 83
Удаление элемента из красно-черного дерева. 85
Лекция 11. 88
B-деревья. 88
Высота B-дерева. 89
Поиск вершины в B-дереве. 90
Отступление на тему языка С. Быстрый поиск и сортировка в языке С.. 90
Добавление вершины в B-дерево. 92
Удаление вершины из B-дерева. 93
Лекция 12. 97
Хеширование. 97
Метод многих списков. 97
Метод линейных проб. 98
Метод цепочек. 102
Хэш-функции. 104
Хэш-функции на основе деления. 104
Хэш-функции на основе умножения. 104
CRC-алгоритмы обнаружения ошибок. 105
Лекция 14. 109
Поиск строк. 109
Отступление на тему языка С. Ввод-вывод строк из файла. 109
Алгоритм поиска подстроки с использованием хеш-функции (Алгоритм Рабина-Карпа) 110
Конечные автоматы.. 111
Отступление на тему языка С. Работа со строками. 112
Алгоритм поиска подстроки, основанный на конечных автоматах. 112
Лекция 15. 114
Алгоритм поиска подстроки Кнута-Морриса-Пратта (на основе префикс-функции) 114
Алгоритм поиска подстроки Бойера-Мура (на основе стоп-символов/безопасных суффиксов) 116
Эвристика стоп-символа. 116
Эвристика безопасного суффикса. 118
Форматы BMP и RLE.. 121
Лекция 1
Дата добавления: 2015-10-30; просмотров: 149 | Нарушение авторских прав
| <== предыдущая страница | | | следующая страница ==> |
| Stages of construction of algorithm with structural scheme use | | | Представление чисел в ЭВМ |