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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Основные определения теории графов: добавлен конспект про род и толщину графов)
м (Третий семестр)
Строка 315: Строка 315:
 
* [[Рёберное ядро]]
 
* [[Рёберное ядро]]
 
* [[Факторизация графов]]<tex>^\star</tex>
 
* [[Факторизация графов]]<tex>^\star</tex>
* [[Род, толщина, крупность, число скрещиваний]]<tex>^\star</tex>
 
  
 
== Связность в графах ==
 
== Связность в графах ==
Строка 371: Строка 370:
 
* [[Укладка графа с планарными компонентами реберной двусвязности]]
 
* [[Укладка графа с планарными компонентами реберной двусвязности]]
 
* [[Укладка графа с планарными компонентами вершинной двусвязности]]
 
* [[Укладка графа с планарными компонентами вершинной двусвязности]]
 +
* [[Род, толщина, крупность, число скрещиваний]]<tex>^\star</tex>
 
* [[Теорема Понтрягина-Куратовского]]
 
* [[Теорема Понтрягина-Куратовского]]
 
* [[Двойственный граф планарного графа]]
 
* [[Двойственный граф планарного графа]]

Версия 20:44, 5 января 2016

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

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

Содержание

Первый семестр

Отношения

Булевы функции

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

Представление информации

Алгоритмы сжатия

Комбинаторика

Комбинаторные объекты

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

Подсчёт числа объектов

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

Динамическое программирование

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

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

Другие задачи

Теория вероятностей

Марковские цепи

Второй семестр

Амортизационный анализ

Персистентные структуры данных

Приоритетные очереди

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

Поисковые структуры данных

Дерево отрезков

Дерево Фенвика

Хеширование

Сортировки

Квадратичные сортировки

Сортировки на сравнениях

Многопоточные сортировки

Другие сортировки

Сортирующие сети

Алгоритмы поиска

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

Третий семестр

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

Связность в графах

Остовные деревья

Построение остовных деревьев

Свойства остовных деревьев

Обходы графов

Эйлеровы графы

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

Укладки графов

Раскраски графов

Обход в глубину

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

Задача о паросочетании

Задача о максимальном потоке

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

Четвертый семестр

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

Поиск подстроки в строке

Точный поиск

Нечёткий поиск

Суффиксное дерево

Суффиксный массив

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

Матроиды

Основные факты теории матроидов

Пересечение матроидов

Объединение матроидов

Теория расписаний