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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Основные определения. Простые комбинаторные свойства слов)
(Четвертый семестр)
Строка 364: Строка 364:
 
* [[Алгоритм Укконена]]
 
* [[Алгоритм Укконена]]
  
== Задача о наименьшем общем предке ==
+
=== Суффиксный массив ===
* [[Метод двоичного подъема]]
 
* [[Сведение задачи LCA к задаче RMQ]]
 
* [[Решение RMQ с помощью разреженной таблицы]]
 
* [[Алгоритм Фарака-Колтона и Бендера]] (решение +/-1 RMQ с помощью метода четверых русских)
 
* [[Сведение задачи RMQ к задаче LCA]]
 
 
 
== Суффиксный массив ==
 
 
* [[Суффиксный массив]]
 
* [[Суффиксный массив]]
 
* [[Построение суффиксного массива с помощью стандартных методов сортировки]]
 
* [[Построение суффиксного массива с помощью стандартных методов сортировки]]
Строка 379: Строка 372:
 
* [[Алгоритм Каркайнена-Сандерса]]
 
* [[Алгоритм Каркайнена-Сандерса]]
 
* [[Алгоритм поиска подстроки в строке с помощью суффиксного массива]]
 
* [[Алгоритм поиска подстроки в строке с помощью суффиксного массива]]
 +
 +
== Задача о наименьшем общем предке ==
 +
* [[Метод двоичного подъема]]
 +
* [[Сведение задачи LCA к задаче RMQ]]
 +
* [[Решение RMQ с помощью разреженной таблицы]]
 +
* [[Алгоритм Фарака-Колтона и Бендера]] (решение +/-1 RMQ с помощью метода четверых русских)
 +
* [[Сведение задачи RMQ к задаче LCA]]
  
 
== Матроиды ==
 
== Матроиды ==

Версия 06:29, 29 марта 2012


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

Содержание

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

Отношения

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

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

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

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

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

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

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

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

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

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

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

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

Деревья поиска

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

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

Хеширование

Сортировка

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Словарные структуры данных

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

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

Матроиды