Дискретная математика, алгоритмы и структуры данных

Материал из Викиконспекты
Перейти к: навигация, поиск

Убедительная просьба читать правила оформления вики-конспектов.

Символом [math] \star [/math] помечены дополнительные темы (возможно, сложные), которые не были подробно рассмотрены (или вообще рассмотрены) в рамках курса.

Содержание

Первый семестр[править]

Отношения[править]

Булевы функции[править]

Схемы из функциональных элементов[править]

Представление информации[править]

Алгоритмы сжатия[править]

Комбинаторика[править]

Комбинаторные объекты[править]

Генерация комбинаторных объектов[править]

Подсчёт числа объектов[править]

Свойства комбинаторных объектов[править]

Динамическое программирование[править]

Классические задачи динамического программирования[править]

Способы оптимизации методов динамического программирования[править]

Другие задачи[править]

Теория вероятностей[править]

Марковские цепи[править]

Второй семестр[править]

Амортизационный анализ[править]

Персистентные структуры данных[править]

Приоритетные очереди[править]

Система непересекающихся множеств[править]

Поисковые структуры данных[править]

Дерево отрезков[править]

Дерево Фенвика[править]

Хеширование[править]

Сортировки[править]

Квадратичные сортировки[править]

Сортировки на сравнениях[править]

Многопоточные сортировки[править]

Другие сортировки[править]

Сортирующие сети[править]

Алгоритмы поиска[править]

Связь между структурами данных[править]

Третий семестр[править]

Основные определения теории графов[править]

Связность в графах[править]

Остовные деревья[править]

Построение остовных деревьев[править]

Свойства остовных деревьев[править]

Обходы графов[править]

Эйлеровы графы[править]

Гамильтоновы графы[править]

Укладки графов[править]

Раскраски графов[править]

Обход в глубину[править]

Кратчайшие пути в графах[править]

Задача о паросочетании[править]

Задача о максимальном потоке[править]

Задача о потоке минимальной стоимости[править]

Четвертый семестр[править]

Основные определения. Простые комбинаторные свойства слов[править]

Поиск подстроки в строке[править]

Точный поиск[править]

Нечёткий поиск[править]

Суффиксное дерево[править]

Суффиксный массив[править]

Задача о наименьшем общем предке[править]

Матроиды[править]

Основные факты теории матроидов[править]

Пересечение матроидов[править]

Объединение матроидов[править]

Теория расписаний[править]

Общая теория[править]

Задачи с одним станком[править]

Специальные случаи задач для двух станков[править]

Задачи для произвольного числа станков[править]