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

Материал из Викиконспекты
Перейти к: навигация, поиск
м (Правки Dgerasimov (обсуждение) откачены к версии Павел Рождественский)
(черт)
Строка 49: Строка 49:
  
 
== Алгоритмы сжатия ==
 
== Алгоритмы сжатия ==
*[[Алгоритм Хаффмана]]
+
# [[Алгоритм Хаффмана]]
*[[Алгоритм LZW]]
+
## "Использует только частоту появления одинаковых байт в изображении." што
*[[Алгоритмы LZ77 и LZ78]]
+
## ссылки на википедию, русскую и английскую
*[[Преобразование Барроуза-Уиллера | Преобразование Барроуза-Уиллера и обратное ему]]
+
## внутренние ссылки на префиксный код и все такое.
*[[Преобразование MTF]]
+
# [[Алгоритм Ху-Таккера]]
*[[Расстояние Хэмминга]]
+
# [[Неравенство Крафта]]
*[[Избыточное кодирование, код Хэмминга]]
+
## Зачем-то дублируются определения с статьей про кодирование информации. Убедиться, что они совпадают, выпилить и сделать внутренние ссылки.
*[[Неравенство Крафта]]
+
## А зачем оно нужно? Просто интересный факт?
*[[Неравенство Макмиллана]]
+
# [[Неравенство Макмиллана]]
*[[Алгоритм Ху-Таккера]]
+
## Зачем-то дублируются определения с статьей про кодирование информации. Убедиться, что они совпадают, выпилить и сделать внутренние ссылки.
 +
## А зачем оно нужно? Просто интересный факт?
 +
# [[Алгоритм LZW]]
 +
# [[Алгоритмы LZ77 и LZ78]]
 +
# '''взяли''' [[Преобразование Барроуза-Уиллера | Преобразование Барроуза-Уиллера и обратное ему]]
 +
# [[Преобразование MTF]]
 +
# [[Расстояние Хэмминга]]
 +
# [[Избыточное кодирование, код Хэмминга]]
  
 
== Комбинаторика ==
 
== Комбинаторика ==
*[[Комбинаторные объекты]]
+
* [[Комбинаторные объекты]]
*[[Лексикографический порядок]]
+
* [[Лексикографический порядок]]
*[[Формула включения-исключения]]
+
* [[Формула включения-исключения]]
*[[Генерация комбинаторных объектов в лексикографическом порядке]]
+
* [[Генерация комбинаторных объектов в лексикографическом порядке]]
*[[Получение номера по объекту]]
+
* [[Получение номера по объекту]]
*[[Получение объекта по номеру]]
+
* [[Получение объекта по номеру]]
*[[Получение следующего объекта]]
+
* [[Получение следующего объекта]]
*[[Коды Грея]]
+
* [[Коды Грея]]
*[[Коды Грея для перестановок]]
+
* [[Коды Грея для перестановок]]
*[[Коды антигрея]]
+
* [[Коды антигрея]]
*[[Цепные коды]]
+
* [[Цепные коды]]
*[[Правильные скобочные последовательности]]
+
* [[Правильные скобочные последовательности]]
*[[Действие перестановки на набор из элементов, представление в виде циклов]]
+
* [[Действие перестановки на набор из элементов, представление в виде циклов]]
*[[Метод генерации случайной перестановки, алгоритм Фишера-Йетса]]
+
* [[Метод генерации случайной перестановки, алгоритм Фишера-Йетса]]
*[[Методы генерации случайного сочетания]]
+
* [[Методы генерации случайного сочетания]]
*[[Таблица инверсий]]
+
* [[Таблица инверсий]]
*[[Умножение перестановок, обратная перестановка, группа перестановок]]
+
* [[Умножение перестановок, обратная перестановка, группа перестановок]]
*[[Теорема Кэли]]
+
* [[Теорема Кэли]]
*[[Матричное представление перестановок]]
+
* [[Матричное представление перестановок]]
*[[Задача о минимуме/максимуме скалярного произведения]]
+
* [[Задача о минимуме/максимуме скалярного произведения]]
*[[Задача о монотонных подпоследовательностях, теорема о связи длины НВП и НУП]]
+
* [[Задача о монотонных подпоследовательностях, теорема о связи длины НВП и НУП]]
*[[Нахождение количества разбиений числа на слагаемые | Нахождение количества разбиений числа на слагаемые. Пентагональная теорема Эйлера]]
+
* [[Нахождение количества разбиений числа на слагаемые | Нахождение количества разбиений числа на слагаемые. Пентагональная теорема Эйлера]]
*[[Производящая функция]]
+
* [[Производящая функция]]
*[[Лемма Бёрнсайда и Теорема Пойа]]
+
* [[Лемма Бёрнсайда и Теорема Пойа]]
*[[Задача об ожерельях]]
+
* [[Задача об ожерельях]]
 +
* [[Числа Стирлинга первого рода]]
 +
* [[Числа Стирлинга второго рода]]
  
 
== [[Динамическое программирование]] ==
 
== [[Динамическое программирование]] ==

Версия 14:32, 6 ноября 2013


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

Содержание

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

Отношения

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

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

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

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

  1. Алгоритм Хаффмана
    1. "Использует только частоту появления одинаковых байт в изображении." што
    2. ссылки на википедию, русскую и английскую
    3. внутренние ссылки на префиксный код и все такое.
  2. Алгоритм Ху-Таккера
  3. Неравенство Крафта
    1. Зачем-то дублируются определения с статьей про кодирование информации. Убедиться, что они совпадают, выпилить и сделать внутренние ссылки.
    2. А зачем оно нужно? Просто интересный факт?
  4. Неравенство Макмиллана
    1. Зачем-то дублируются определения с статьей про кодирование информации. Убедиться, что они совпадают, выпилить и сделать внутренние ссылки.
    2. А зачем оно нужно? Просто интересный факт?
  5. Алгоритм LZW
  6. Алгоритмы LZ77 и LZ78
  7. взяли Преобразование Барроуза-Уиллера и обратное ему
  8. Преобразование MTF
  9. Расстояние Хэмминга
  10. Избыточное кодирование, код Хэмминга

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

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

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

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

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

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

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

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

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

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

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

Хеширование

Сортировка

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Матроиды

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

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

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