Староверов В.М. Конспект лекций по курсу Алгоритмы и алгоритмические языки

Москва: МГУ, 2010. — 59 с.Представление чисел в ЭВМ.
Целые.
Вещественные.
Ошибки вычислений.Алгоритмы. Сведение алгоритмов.
Нижние и верхние оценки.
Сортировки.
Постановка задачи.
Сортировка пузырьком.
Сортировка слиянием с рекурсией.
Сортировка слиянием без рекурсии.Алгоритмы. Сведение алгоритмов.
Сортировки и связанные с ними задачи.
QuickSort.
Доказательство корректности работы алгоритма.
Оценки времени работы алгоритма.
Некоторые задачи, сводящиеся к сортировке.Алгоритмы. Сведение алгоритмов.
Сортировки и связанные с ними задачи.
HeapSort или сортировка с помощью пирамиды.
Алгоритмы сортировки за время O(N).
Сортировка подсчетом.
Цифровая сортировка.
Сортировка вычерпыванием.Алгоритмы. Сведение алгоритмов.
Порядковые статистики.
Поиск порядковой статистики за время Q(N) в среднем.
Поиск порядковой статистики за время Q(N) в худшем случае.
Язык программирования C.
Переменные.
Структуры данных.
Вектор.
Стек.Структуры данных ( + в языке C: массивы, структуры, оператор typedef).
Стек.
Стек. Реализация 1 (на основе массива).
Стек. Реализация 2 (на основе массива с использованием общей структуры).
Стек. Реализация 3 (на основе указателей).
Стек. Реализация 4 (на основе массива из двух указателей).
Стек. Реализация 5 (на основе указателя на указатель).
Очередь.
Дек.
Списки.
Стандартная ссылочная реализация списков.
Ссылочная реализация списков с фиктивным элементом.
Реализация L2-списка на основе двух стеков.
Реализация L2-списка с обеспечением выделения/освобождения памяти.Структуры данных. Графы.
Графы.
Поиск пути в графе с наименьшим количеством промежуточных вершин.
Представление графа в памяти ЭВМ.Структуры данных. Графы.
Поиск кратчайшего пути в графе.Бинарные деревья поиска.
Поиск элемента в дереве.
Добавление элемента в дерево.
Поиск минимального и максимального элемента в дереве.
Удаление элемента из дерева.
Поиск следующего/предыдущего элемента в дереве.
Слияние двух деревьев.
Разбиение дерева по разбивающему элементу.
Сбалансированные и идеально сбалансированные бинарные деревья поиска.
Операции с идеально сбалансированным деревом.
Операции со сбалансированным деревом.
Поиск элемента в дереве.
Добавление элемента в дерево.
Удаление элемента из дерева.
Поиск минимального и максимального элемента в дереве.
Поиск следующего/предыдущего элемента в дереве.
Слияние двух деревьев.
Разбиение дерева по разбивающему элементу.Красно-черные деревья.
Отступление на тему языка C. Поля структур.
Отступление на тему языка C. Бинарные операции.
Высота красно-черного дерева.
Добавление элемента в красно-черное дерево.
Однопроходное добавление элемента в красно-черное дерево.
Удаление элемента из красно-черного дерева.B-деревья.
Высота B-дерева.
Поиск вершины в B-дереве.
Отступление на тему языка C. Быстрый поиск и сортировка в языке C.
Добавление вершины в B-дерево.
Удаление вершины из B-дерева.Хеширование.
Метод многих списков.
Метод линейных проб.
Метод цепочек.
Хэш-функции.
Хэш-функции на основе деления.
Хэш-функции на основе умножения.
CRC-алгоритмы обнаружения ошибок.Поиск строк.
Отступление на тему языка C. Ввод-вывод строк из файла.
Алгоритм поиска подстроки с использованием хеш-функции (Алгоритм Рабина-Карпа).
Конечные автоматы.
Отступление на тему языка C. Работа со строками.
Алгоритм поиска подстроки, основанный на конечных автоматах.Алгоритм поиска подстроки Кнута-Морриса-Пратта (на основе префикс-функции).
Алгоритм поиска подстроки Бойера-Мура (на основе стоп-символов/безопасных суффиксов).
Эвристика стоп-символа.
Эвристика безопасного суффикса.