Дискретная математика, алгоритмы и структуры данных — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
м (Эйлеровы графы)
м (Откат правок 93.85.153.53 (обсуждение) к версии Vitalik)
(Метки: правка с мобильного устройства, правка из мобильной версии)
 
(не показаны 2 промежуточные версии 2 участников)
Строка 470: Строка 470:
 
* [[Теорема о декомпозиционном барьере]]
 
* [[Теорема о декомпозиционном барьере]]
 
* [[Циркуляция потока]]
 
* [[Циркуляция потока]]
 +
* [[Алгоритм Штор-Вагнера нахождения минимального разреза]]
 
* [[Алгоритм Каргера для нахождения минимального разреза]]<tex>^\star</tex>
 
* [[Алгоритм Каргера для нахождения минимального разреза]]<tex>^\star</tex>
 
* [[Примеры сведения к задачам поиска потока]]
 
* [[Примеры сведения к задачам поиска потока]]

Текущая версия на 20:45, 12 марта 2018

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

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

Содержание

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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