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

Материал из Викиконспекты
Перейти к: навигация, поиск
(→‎Второй семестр)
Строка 176: Строка 176:
 
* [[Амортизационный анализ]]
 
* [[Амортизационный анализ]]
 
* [[Динамический массив]]
 
* [[Динамический массив]]
−
* [[Hashed Array Tree]]
+
* [[Hashed Array Tree]]<tex>^\star</tex>
 
* [[Список]]
 
* [[Список]]
 
* [[Стек]]
 
* [[Стек]]
Строка 194: Строка 194:
 
* [[Тонкая куча]]
 
* [[Тонкая куча]]
 
* [[Толстая куча на избыточном счетчике]]
 
* [[Толстая куча на избыточном счетчике]]
−
* [[Куча Бродала-Окасаки]]
+
* [[Куча Бродала-Окасаки]]<tex>^\star</tex>
  
 
== Система непересекающихся множеств ==
 
== Система непересекающихся множеств ==
Строка 200: Строка 200:
 
* [[СНМ (списки с весовой эвристикой) | Списки с весовой эвристикой]]
 
* [[СНМ (списки с весовой эвристикой) | Списки с весовой эвристикой]]
 
* [[СНМ(реализация с помощью леса корневых деревьев) | Реализация с помощью леса корневых деревьев]]
 
* [[СНМ(реализация с помощью леса корневых деревьев) | Реализация с помощью леса корневых деревьев]]
−
* [[СНМ с операцией удаления за О(1)]]
+
* [[СНМ с операцией удаления за О(1)]]<tex>^\star</tex>
  
 
== Поисковые структуры данных ==
 
== Поисковые структуры данных ==
Строка 212: Строка 212:
 
* [[Декартово дерево по неявному ключу]]
 
* [[Декартово дерево по неявному ключу]]
 
* [[Splay-дерево]]
 
* [[Splay-дерево]]
−
* [[Tango-дерево]]
+
* [[Tango-дерево]]<tex>^\star</tex>
 
* [[Рандомизированное бинарное дерево поиска]]
 
* [[Рандомизированное бинарное дерево поиска]]
 
* [[Дерево ван Эмде Боаса]]
 
* [[Дерево ван Эмде Боаса]]
Строка 218: Строка 218:
 
* [[Fusion tree]]
 
* [[Fusion tree]]
 
* [[Сверхбыстрый цифровой бор]]
 
* [[Сверхбыстрый цифровой бор]]
−
* [[Rope]]
+
* [[Rope]]<tex>^\star</tex>
  
 
== Дерево отрезков ==
 
== Дерево отрезков ==
Строка 251: Строка 251:
 
* [[Сортировка вставками]]
 
* [[Сортировка вставками]]
 
=== Сортировки на сравнениях ===
 
=== Сортировки на сравнениях ===
−
* [[Сортировка Шелла]]
+
* [[Сортировка Шелла]]<tex>^\star</tex>
 
* [[Сортировка кучей]]
 
* [[Сортировка кучей]]
 
* [[Быстрая сортировка]]
 
* [[Быстрая сортировка]]
 
* [[Сортировка слиянием]]
 
* [[Сортировка слиянием]]
 
* [[Cортировка слиянием с использованием O(1) дополнительной памяти]]
 
* [[Cортировка слиянием с использованием O(1) дополнительной памяти]]
−
* [[Терпеливая сортировка]]
+
* [[Терпеливая сортировка]]<tex>^\star</tex>
−
* [[Timsort]]
+
* [[Timsort]]<tex>^\star</tex>
 
* [[Теорема о нижней оценке для сортировки сравнениями]]
 
* [[Теорема о нижней оценке для сортировки сравнениями]]
 
=== Многопоточные сортировки ===
 
=== Многопоточные сортировки ===
−
* [[Многопоточная сортировка слиянием]]
+
* [[Многопоточная сортировка слиянием]]<tex>^\star</tex>
−
* [[PSRS-сортировка]]
+
* [[PSRS-сортировка]]<tex>^\star</tex>
 
=== Другие сортировки ===
 
=== Другие сортировки ===
 
* [[Поиск k-ой порядковой статистики]]
 
* [[Поиск k-ой порядковой статистики]]
Строка 269: Строка 269:
 
* [[Цифровая сортировка]]
 
* [[Цифровая сортировка]]
 
* [[Карманная сортировка]]
 
* [[Карманная сортировка]]
−
* [[Сортировка Хана]]
+
* [[Сортировка Хана]]<tex>^\star</tex>
  
 
== Сортирующие сети ==
 
== Сортирующие сети ==
 
* [[Сортирующие сети]]
 
* [[Сортирующие сети]]
 
* [[0-1 принцип | Проверка сети компараторов на то, что она сортирующая. 0-1 принцип]]
 
* [[0-1 принцип | Проверка сети компараторов на то, что она сортирующая. 0-1 принцип]]
−
* [[Сортировочные сети с особыми свойствами]]
+
* [[Сортировочные сети с особыми свойствами]]<tex>^\star</tex>
 
* [[Сортирующие сети для квадратичных сортировок]]
 
* [[Сортирующие сети для квадратичных сортировок]]
 
* [[Сеть Бетчера]]
 
* [[Сеть Бетчера]]

Версия 15:46, 11 января 2015


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

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

Содержание

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

Отношения

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Хеширование

Сортировка

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Матроиды

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

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

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

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

Источник — «http://neerc.ifmo.ru/wiki/index.php?title=Дискретная_математика,_алгоритмы_и_структуры_данных&oldid=44135»