Редактирование: Дискретная математика и алгоритмы

Перейти к: навигация, поиск

Внимание! Вы не авторизовались на сайте. Ваш IP-адрес будет публично видимым, если вы будете вносить любые правки. Если вы войдёте или создадите учётную запись, правки вместо этого будут связаны с вашим именем пользователя, а также у вас появятся другие преимущества.

Правка может быть отменена. Пожалуйста, просмотрите сравнение версий, чтобы убедиться, что это именно те изменения, которые вас интересуют, и нажмите «Записать страницу», чтобы изменения вступили в силу.
Текущая версия Ваш текст
Строка 1: Строка 1:
#перенаправление [[Дискретная математика, алгоритмы и структуры данных]]
 
 
[[Категория:Дискретная математика и алгоритмы]]
 
[[Категория:Дискретная математика и алгоритмы]]
 +
== Отношения ==
 +
*[[Определение отношения]]
 +
*[[Степень отношений]]
 +
*[[Рефлексивное отношение|Рефлексивное отношение. Антирефлексивное отношение.]]
 +
*[[Симметричное отношение]]
 +
*[[Антисимметричное отношение]]
 +
*[[Композиция отношений|Композиция отношений. Обратное отношение]]
 +
*[[Транзитивное отношение]]
 +
*[[Транзитивное замыкание|Транзитивное замыкание отношения]]
 +
*[[Алгоритм Флойда — Уоршелла|Алгоритм Флойда-Уоршалла построения транзитивного замыкания отношения]]
 +
 +
== Булевы функции ==
 +
*[[Определение булевой функции]]
 +
*[[Примеры булевых функций|Примеры булевых функций: все функции от нуля, одной и двух переменных]]
 +
*[[Подстановка одной функции в другую, отождествление переменных]]
 +
*[[Представление функции формулой, полные системы функций]]
 +
*[[СДНФ]]
 +
*[[СКНФ]]
 +
*[[Полином Жегалкина]]
 +
*[[Теорема Поста о полной системе функций]]
 +
*[[Сокращенная и минимальная ДНФ]]
 +
*[[Минимизация ДНФ с помощью покрытий гиперкуба и карт Карно]]
 +
*[[Специальные формы КНФ|Специальные формы КНФ: КНФ в форме Хорна и КНФ в форме Крома]]
 +
*[[Преобразование Мёбиуса для получения коэффициентов полинома Жегалкина]]
 +
*[[Представление функции класса DM с помощью медианы]]
 +
*[[Пороговая функция]]
 +
 +
== Схемы из функциональных элементов ==
 +
*[[Реализация булевой функции схемой из функциональных элементов]]
 +
*[[Изменение размера оптимальной схемы при переходе к другому базису]]
 +
*[[Cумматор]]
 +
*[[Каскадный сумматор]]
 +
*[[Двоичный каскадный сумматор]]
 +
*[[Матричный умножитель]]
 +
*[[Дерево Уоллеса]]
 +
 +
== Представление информации ==
 +
*[[Кодирование информации]]
 +
*[[Представление целых чисел: прямой код, код со сдвигом, дополнительный код]]
 +
*[[Представление вещественных чисел]]
 +
*[[Представление символов, таблицы кодировок]]
 +
*[[Алгоритм Хаффмана]]
 +
 +
== Алгоритмы сжатия ==
 +
*[[Алгоритм LZW]]
 +
*[[Алгоритмы LZ77 и LZ78]]
 +
*[[Преобразование Барроуза-Уиллера]]
 +
*[[Обратное преобразование Барроуза-Уиллера]]
 +
*[[Преобразование MTF]]
 +
*[[Расстояние Хэмминга]]
 +
*[[Избыточное кодирование, код Хэмминга]]
 +
 +
== Комбинаторика ==
 +
*[[Комбинаторные объекты]]
 +
*[[Лексикографический порядок]]
 +
*[[Формула включения-исключения]]
 +
*[[Генерация комбинаторных объектов в лексикографическом порядке]]
 +
*[[Получение номера по объекту]]
 +
*[[Получение объекта по номеру]]
 +
*[[Получение следующего объекта]]
 +
*[[Коды Грея]]
 +
*[[Коды Грея для перестановок]]
 +
*[[Цепные коды]]
 +
*[[Действие перестановки на набор из элементов, представление в виде циклов]]
 +
*[[Метод генерации случайной перестановки, алгоритм Фишера-Йетса]]
 +
*[[Таблица инверсий]]
 +
*[[Умножение перестановок, обратная перестановка, группа перестановок]]
 +
*[[Теорема Кэли]]
 +
*[[Матричное представление перестановок]]
 +
*[[Задача о минимуме/максимуме скалярного произведения]]
 +
*[[Задача о монотонных подпоследовательностях, теорема о связи длины НВП и НУП]]
 +
*[[Поиск наибольшей возрастающей подпоследовательности и т. д.]]
 +
*[[Нахождение количества разбиений числа на слагаемые | Нахождение количества разбиений числа на слагаемые. Пентагональная теорема Эйлера]]
 +
 +
== Динамическое программирование ==
 +
*[[Кратчайший путь в ациклическом графе]]
 +
*[[Задача о расстановке знаков в выражении]]
 +
*[[Задача о наибольшей общей подпоследовательности]]
 +
*[[Задача о перемножении матриц]]
 +
*[[Задача о наибольшей возрастающей подпоследовательности]]
 +
*[[Задача о паросочетании максимального веса в дереве, амортизированные оценки для ДП на дереве]]
 +
*[[Метод четырех русских для умножения матриц]]
 +
*[[Применение метода четырех русских в задачах ДП на примере задачи о НОП]]
 +
*[[Задача коммивояжера, ДП по подмножествам]]
 +
*[[Задача о выводе в контекстно-свободной грамматике, алгоритм Кока-Янгера-Касами]]
 +
*[[Задача о редакционном расстоянии, алгоритм Левенштейна]]
 +
*[[Задача об оптимальном префиксном коде с сохранением порядка. Монотонность точки разреза]]
 +
 +
== Теория вероятности ==
 +
*[[Вероятностное пространство, элементарный исход, событие]]
 +
*[[Независимые события]]
 +
*[[Условная вероятность]]
 +
*[[Формула Байеса]]
 +
*[[Формула полной вероятности]]
 +
*[[Дискретная случайная величина]]
 +
*[[Независимые случайные величины]]
 +
*[[Линейность математического ожидания]]
 +
*[[Ковариация случайных величин]]
 +
*[[Дисперсия случайной величины]]
 +
*[[Энтропия случайного источника]]
 +
*[[Симуляция одним распределением другого]]
 +
*[[Арифметическое кодирование]]
 +
 +
== [[Марковская цепь|Марковские цепи]] ==
 +
 +
* [[Теорема о поглощении]]
 +
* [[Фундаментальная матрица]]
 +
* [[Математическое ожидание времени поглощения]]
 +
* [[Расчет вероятности поглощения в состоянии]]
 +
* [[Эргодическая марковская цепь]]
 +
* [[Регулярная марковская цепь]]
 +
 +
== Амортизационный анализ ==
 +
* [[Амортизационный анализ. Метод предоплаты]]
 +
* [[Саморасширяющийся массив]]
 +
* [[Массив с увеличением/уменьшением размера]]
 +
* [[Стек]]
 +
* [[Очередь]]
 +
* [[Список]]
 +
 +
== Приоритетные очереди ==
 +
* [[Двоичная куча|Двоичная куча]]
 +
* [[Биномиальная куча|Биномиальная пирамида]]
 +
 +
== Система непересекающихся множеств ==
 +
* [[СНМ(наивные реализации) | Наивные реализации]]
 +
* [[СНМ(списки с весовой эвристикой) | Списки с весовой эвристикой]]
 +
* [[СНМ(реализация с помощью леса корневых деревьев) | Реализация с помощью леса корневых деревьев]]
 +
* [[Анализ реализации с ранговой эвристикой  | Анализ реализации с ранговой эвристикой]]
 +
 +
== Деревья поиска ==
 +
* [[Упорядоченное множество]]
 +
* [[Дерево поиска, наивная реализация]]
 +
* [[АВЛ-дерево]]
 +
* [[2-3 дерево]]
 +
* [[B-дерево]]
 +
* [[Красно- черное дерево]]
 +
* [[Декартово дерево]]
 +
* [[Splay-дерево]]
 +
 +
== Дерево отрезков ==
 +
* [[Статистики на отрезках. Корневая эвристика]]
 +
* [[Дерево отрезков. Построение]]
 +
* [[Реализация запроса в дереве отрезков сверху]]
 +
* [[Реализация запроса в дереве отрезков снизу]]
 +
* [[Несогласованные поддеревья. Реализация массового обновления]]
 +
 +
== Дерево Фенвика ==
 +
* [[Дерево Фенвика]]
 +
* [[Встречное дерево Фенвика]]
 +
* [[Дерево Фенвика, запрос изменения элемента]]
 +
* [[Многомерное дерево Фенвика]]
 +
 +
== Хеширование ==
 +
* [[Различные алгоритмы хеширования]]
 +
* [[Открытое и закрытое хеширование]]
 +
* [[Поиск свободного места при закрытом хешировании]]
 +
* [[Хеширование кукушки]]
 +
* [[Двойное хэширование]]
 +
 +
== Сортировка ==
 +
* [[Сортировка пузырьком]]
 +
* [[Сортировка слиянием]]
 +
* [[Сортировка вставками]]
 +
* [[Сортировка подсчетом]]
 +
* [[Сортировка подсчетом сложных объектов]]
 +
* [[Поиск k-ой порядковой статистики]]

Пожалуйста, учтите, что любой ваш вклад в проект «Викиконспекты» может быть отредактирован или удалён другими участниками. Если вы не хотите, чтобы кто-либо изменял ваши тексты, не помещайте их сюда.
Вы также подтверждаете, что являетесь автором вносимых дополнений, или скопировали их из источника, допускающего свободное распространение и изменение своего содержимого (см. Викиконспекты:Авторские права). НЕ РАЗМЕЩАЙТЕ БЕЗ РАЗРЕШЕНИЯ ОХРАНЯЕМЫЕ АВТОРСКИМ ПРАВОМ МАТЕРИАЛЫ!

Чтобы изменить эту страницу, пожалуйста, ответьте на приведённый ниже вопрос (подробнее):

Отменить | Справка по редактированию (в новом окне)