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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Схемы из функциональных элементов: добавлен конспект про контактные схемы)
м (Способы оптимизации методв динамического программирования)
Строка 109: Строка 109:
 
*[[Задача о рюкзаке]]
 
*[[Задача о рюкзаке]]
  
=== Способы оптимизации методв динамического программирования ===
+
=== Способы оптимизации методов динамического программирования ===
 
*[[Метод четырех русских для умножения матриц]]
 
*[[Метод четырех русских для умножения матриц]]
 
*[[Применение метода четырех русских в задачах ДП на примере задачи о НОП]]
 
*[[Применение метода четырех русских в задачах ДП на примере задачи о НОП]]
 
*[[Задача об оптимальном префиксном коде с сохранением порядка. Монотонность точки разреза]]
 
*[[Задача об оптимальном префиксном коде с сохранением порядка. Монотонность точки разреза]]
 
*[[Meet-in-the-middle]]
 
*[[Meet-in-the-middle]]
 +
 
=== Другие задачи ===
 
=== Другие задачи ===
 
*[[Задача о расстоянии Дамерау-Левенштейна]]
 
*[[Задача о расстоянии Дамерау-Левенштейна]]

Версия 00:30, 17 октября 2014


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

Содержание

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

Отношения

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Хеширование

Сортировка

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Матроиды

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

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

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

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