Дискретная математика:Тикеты — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Новая страница: «== Отношения == *Определение отношения *[[Композиция отношений|Композиция отношений, сте...»)
 
(→‎2 Генерация комбинаторных объектов)
 
(не показана 61 промежуточная версия 5 участников)
Строка 1: Строка 1:
−
== Отношения ==
+
Тикеты индексируются как "X-Y", где X — номер раздела, Y — номер конспекта внутри раздела (например, конспект ДНФ из раздела булевых функций имеет тикет 2-4)
−
*[[Определение отношения]]
 
−
*[[Композиция отношений|Композиция отношений, степень отношения, обратное отношение]]
 
−
*[[Рефлексивное отношение|Рефлексивное отношение. Антирефлексивное отношение.]]
 
−
*[[Симметричное отношение]]
 
−
*[[Антисимметричное отношение]]
 
−
*[[Транзитивное отношение]]
 
−
*[[Отношение порядка]]
 
−
*[[Изоморфизмы упорядоченных множеств]]<tex>^\star</tex>
 
−
*[[Отношение эквивалентности]]
 
−
*[[Транзитивное замыкание|Транзитивное замыкание отношения]]
 
−
*[[Алгоритм Флойда — Уоршелла|Алгоритм Флойда-Уоршалла построения транзитивного замыкания отношения]]
 
−
*[[Транзитивный остов]]
 
  
−
== Булевы функции ==
+
== 1. Отношения ==
−
*[[Определение булевой функции]]
+
# [[Определение отношения]]
−
*[[Побитовые операции]]<tex>^\star</tex>
+
# [[Композиция отношений|Композиция отношений, степень отношения, обратное отношение]]
−
*[[Суперпозиции]]
+
# [[Рефлексивное отношение|Рефлексивное отношение. Антирефлексивное отношение.]]
−
*[[ДНФ]]
+
# [[Симметричное отношение]]
−
*[[Сокращенная и минимальная ДНФ | Сокращенная и минимальная ДНФ, минимизация ДНФ методами гиперкубов, карт Карно, Квайна]]
+
# [[Антисимметричное отношение]]
−
*[[КНФ]]
+
# [[Транзитивное отношение]]
−
*[[2-SAT]]
+
# [[Отношение порядка]]
−
*[[XOR-SAT]]<tex>^\star</tex>
+
# [[Изоморфизмы упорядоченных множеств]]<tex>^\star</tex>
−
*[[Специальные формы КНФ|Специальные формы КНФ: КНФ в форме Хорна и КНФ в форме Крома]]
+
# [[Отношение эквивалентности]]  
−
*[[Полином Жегалкина | Полином Жегалкина, преобразование Мёбиуса]]
+
# [[Транзитивное замыкание|Транзитивное замыкание отношения]]  
−
*[[Полные системы функций. Теорема Поста о полной системе функций]]
+
# [[Алгоритм Флойда — Уоршелла|Алгоритм Флойда-Уоршалла построения транзитивного замыкания отношения]]
−
*[[Представление функции класса DM с помощью медианы]]
+
# [[Транзитивный остов]]
−
*[[Пороговая функция]]
 
−
*[[Троичная логика]]<tex>^\star</tex>
 
  
−
== Схемы из функциональных элементов ==
+
== 2 Булевы функции ==
−
*[[Реализация булевой функции схемой из функциональных элементов]]
+
# [[Определение булевой функции]] 0,5
−
*[[Простейшие методы синтеза схем из функциональных элементов]]
+
## исправить знаки неравенств
−
*[[Метод Лупанова синтеза схем]]
+
# [[Побитовые операции]]<tex>^\star</tex>
−
*[[Cумматор]]
+
# [[Суперпозиции]] 2
−
*[[Каскадный сумматор]]
+
## Дописать раздел про ранги суперпозиций
−
*[[Двоичный каскадный сумматор]]
+
# [[ДНФ]]  
−
*[[Троичный сумматор]]<tex>^\star</tex>
+
#[[Сокращенная и минимальная ДНФ | Сокращенная и минимальная ДНФ, минимизация ДНФ методами гиперкубов, карт Карно, Квайна]]
−
*[[Реализация вычитания сумматором]]
+
# [[КНФ]]  
−
*[[Матричный умножитель]]
+
# [[2-SAT]]
−
*[[Дерево Уоллеса]]
+
# [[XOR-SAT]]<tex>^\star</tex>
−
*[[Контактная схема]]
+
# [[Специальные формы КНФ|Специальные формы КНФ: КНФ в форме Хорна и КНФ в форме Крома]]
−
*[[Триггеры]]<tex>^\star</tex>
+
# [[Полином Жегалкина | Полином Жегалкина, преобразование Мёбиуса]]  
−
*[[Квантовые гейты]]<tex>^\star</tex>
+
# [[Полные системы функций. Теорема Поста о полной системе функций]]  
 +
# [[Представление функции класса DM с помощью медианы]] 2-10
 +
## Добавить см. также
 +
## Правильно оформить источники информации
 +
## Исправить знаки неравенств
 +
## Добавить примеры на конкретный функциях (чем интереснее примеры, тем больше баллов)
 +
# [[Пороговая функция]]  
 +
#[[Троичная логика]]<tex>^\star</tex>
  
−
== Представление информации ==
+
== 3 Схемы из функциональных элементов ==
−
*[[Кодирование информации]]
+
#[[Реализация булевой функции схемой из функциональных элементов]] 5
−
*[[Представление целых чисел: прямой код, код со сдвигом, дополнительный код]]
+
## Добавить информацию о методе построения схемы по функции
−
*[[Представление вещественных чисел]]
+
## Добавить алгоритм вычисления глубины схемы
−
*[[Представление символов, таблицы кодировок]]<tex>^\star</tex>
+
## Добавить картинки к доказательствам
 +
# [[Простейшие методы синтеза схем из функциональных элементов]] 6
 +
## Добавить примеры на каждый метод
 +
# [[Метод Лупанова синтеза схем]] 0.5
 +
## Правильно оформить источники информации
 +
#[[Cумматор]]
 +
#[[Каскадный сумматор]]
 +
#[[Двоичный каскадный сумматор]] 5
 +
## Сделать конспект более понятным
 +
#[[Троичный сумматор]]<tex>^\star</tex>
 +
#[[Реализация вычитания сумматором]]
 +
#[[Матричный умножитель]]
 +
#[[Дерево Уоллеса]]
 +
#[[Контактная схема]] 1
 +
## взяли Перерисовать картинки с построением контактных схем и дерево конъюнктов
 +
#[[Триггеры]]<tex>^\star</tex>
 +
#[[Квантовые гейты]]<tex>^\star</tex>
  
−
== Алгоритмы сжатия ==
+
== 4 Представление информации ==
−
* [[Алгоритм Хаффмана]]
+
# [[Кодирование информации]]
−
* [[Оптимальное хранение словаря в алгоритме Хаффмана]]
+
# [[Представление целых чисел: прямой код, код со сдвигом, дополнительный код]]
−
* [[Алгоритм Хаффмана за O(n)]]
+
# [[Представление вещественных чисел]]
−
* [[Алгоритм Ху-Таккера]]<tex>^\star</tex>
+
# [[Представление символов, таблицы кодировок]]<tex>^\star</tex>
−
* [[Неравенство Крафта]]
 
−
* [[Неравенство Макмиллана]]
 
−
* [[Код Шеннона]]
 
−
* [[Оптимальный префиксный код с длиной кодового слова не более L бит]]<tex>^\star</tex>
 
−
* [[Алгоритмы LZ77 и LZ78]]
 
−
* [[Алгоритм LZW]]
 
−
* [[Алгоритм LZSS]]<tex>^\star</tex>
 
−
* [[Алгоритм LZMA]]<tex>^\star</tex>
 
−
* [[Преобразование Барроуза-Уиллера | Преобразование Барроуза-Уиллера и обратное ему]]
 
−
* [[Преобразование MTF]]
 
−
* [[Расстояние Хэмминга]]
 
−
* [[Избыточное кодирование, код Хэмминга]]
 
−
* [[Гамма-, дельта- и омега-код Элиаса]]<tex>^\star</tex>
 
  
−
== Комбинаторика ==
+
== 5 Алгоритмы сжатия ==
−
=== Комбинаторные объекты ===
+
# [[Алгоритм Хаффмана]]
−
* [[Комбинаторные объекты]]
+
# [[Оптимальное хранение словаря в алгоритме Хаффмана]]
−
* [[Лексикографический порядок]]
+
# [[Алгоритм Хаффмана за O(n)]] 0.5
−
* [[Коды Грея]]
+
## Источники информации
−
* [[Коды Грея для перестановок]]
+
# [[Алгоритм Ху-Таккера]]<tex>^\star</tex>
−
* [[Коды антигрея]]
+
# [[Неравенство Крафта]] 5-10
−
* [[Монотонный код Грея]]
+
## Доказательство вообще не о том, требуется полностью переписать
−
* [[Цепные коды]]
+
# [[Неравенство Макмиллана]] 2-5
−
* [[Правильные скобочные последовательности]]
+
## Доказательство требует косметических правок
 +
# [[Код Шеннона]]
 +
# [[Оптимальный префиксный код с длиной кодового слова не более L бит]]<tex>^\star</tex>
 +
# [[Алгоритмы LZ77 и LZ78]] 2
 +
## Переменные и константы взять в Tex
 +
## Добавить примеры итоговых таблиц
 +
## Рассказать, как декодировать
 +
## Правильно оформить источники информации
 +
## Получше расписать описание алгоритма
 +
## Таблицы сделать красивыми
 +
## Интервики
 +
# [[Алгоритм LZW]] 0,25
 +
## См. также
 +
# [[Алгоритм LZSS]]<tex>^\star</tex>
 +
# [[Алгоритм LZMA]]<tex>^\star</tex>
 +
# [[Преобразование Барроуза-Уиллера | Преобразование Барроуза-Уиллера и обратное ему]]
 +
# [[Преобразование MTF]]
 +
# [[Расстояние Хэмминга]]
 +
# [[Избыточное кодирование, код Хэмминга]] 0,25
 +
## См. также
 +
# [[Гамма-, дельта- и омега-код Элиаса]]<tex>^\star</tex> 0,25
 +
## См. также
  
−
=== Генерация комбинаторных объектов ===
+
== 6 Комбинаторика ==
−
* [[Генерация комбинаторных объектов в лексикографическом порядке]]
+
=== 1 Комбинаторные объекты ===
−
* [[Получение номера по объекту]]
+
# [[Комбинаторные объекты]]
−
* [[Получение объекта по номеру]]
+
# [[Лексикографический порядок]]
−
* [[Получение следующего объекта]]
+
# [[Коды Грея]]
−
* [[Получение предыдущего объекта]]<tex>^\star</tex> 
+
# [[Коды Грея для перестановок]]
−
* [[Метод генерации случайной перестановки, алгоритм Фишера-Йетса]]
+
# [[Коды антигрея]]
−
* [[Методы генерации случайного сочетания]]<tex>^\star</tex>
+
# [[Монотонный код Грея]]
 +
# [[Цепные коды]]
 +
# [[Правильные скобочные последовательности]]
  
−
=== Подсчёт числа объектов ===
+
=== 2 Генерация комбинаторных объектов ===
−
* [[Формула включения-исключения | Формула включения-исключения, подсчет числа беспорядков]]
+
# [[Генерация комбинаторных объектов в лексикографическом порядке]] 0.5
−
* [[Нахождение количества разбиений числа на слагаемые | Нахождение количества разбиений числа на слагаемые. Пентагональная теорема Эйлера]]
+
## Заменить скобки "больше-меньше" на угловые
−
* [[Производящая функция]]
+
## Нормальную красивую картинку нарисовать
−
* [[Лемма Бёрнсайда и Теорема Пойа]]
+
# [[Получение номера по объекту]]
−
* [[Задача об ожерельях]]
+
# [[Получение объекта по номеру]]
−
* [[Числа Стирлинга первого рода]]
+
# [[Получение следующего объекта]]
−
* [[Числа Стирлинга второго рода]]
+
# [[Получение предыдущего объекта]]<tex>^\star</tex> 
−
* [[Числа Эйлера I и II рода | Числа Эйлера первого и второго рода. Подъемы в перестановках]]<tex>^\star</tex>
+
# [[Метод генерации случайной перестановки, алгоритм Фишера-Йетса]]
−
* [[Числа Каталана]]
+
# [[Методы генерации случайного сочетания]]<tex>^\star</tex>
  
−
=== Свойства комбинаторных объектов ===
+
=== 3 Подсчёт числа объектов ===
−
* [[Умножение перестановок, обратная перестановка, группа перестановок]]
+
# [[Формула включения-исключения | Формула включения-исключения, подсчет числа беспорядков]] 1
−
* [[Действие перестановки на набор из элементов, представление в виде циклов]]
+
## в первой теореме в доказательстве по индукции получен результат не тот, что в условии
−
* [[Таблица инверсий]]
+
# [[Нахождение количества разбиений числа на слагаемые | Нахождение количества разбиений числа на слагаемые. Пентагональная теорема Эйлера]]  
−
* [[Теорема Кэли]]
+
# [[Лемма Бёрнсайда и Теорема Пойа]]
−
* [[Матричное представление перестановок]]
+
# [[Задача об ожерельях]]
−
* [[Задача о минимуме/максимуме скалярного произведения]]
+
# [[Числа Стирлинга первого рода]] 5
−
* [[Задача о монотонных подпоследовательностях, теорема о связи длины НВП и НУП]]
+
## <tex>\left[{m+n+1\atop m}\right]=\sum\limits_{k=0}^n (n+k) \left[{n+k\atop k}\right]</tex> то есть результат не зависит от <tex>m</tex>?
 +
## Поправить тех
 +
## доказательства дополнительных тождеств
 +
# [[Числа Стирлинга второго рода]]
 +
# [[Символ Похгаммера]]
 +
# [[Числа Белла]]
 +
# [[Числа Эйлера I и II рода | Числа Эйлера первого и второго рода. Подъемы в перестановках]]
 +
# [[Числа Каталана]] 0,5
 +
## См. также
 +
# [[Конструирование комбинаторных объектов и их подсчет]]
  
−
== [[Динамическое программирование]] ==
+
=== 4 Свойства комбинаторных объектов ===
−
=== Классические задачи динамического программирования ===
+
# [[Умножение перестановок, обратная перестановка, группа перестановок]]  
−
*[[Кратчайший путь в ациклическом графе]]
+
# [[Действие перестановки на набор из элементов, представление в виде циклов]]
−
*[[Задача о числе путей в ациклическом графе]]
+
# [[Таблица инверсий]] 0,25
−
*[[Задача о расстановке знаков в выражении]]
+
## tex в заголовок
−
*[[Задача о порядке перемножения матриц]]
+
# [[Теорема Кэли]]
−
*[[Задача о наибольшей общей подпоследовательности]]
+
# [[Матричное представление перестановок]]
−
*[[Задача о наибольшей возрастающей подпоследовательности]]
+
# [[Задача о минимуме/максимуме скалярного произведения]]  
−
*[[Быстрый поиск наибольшей возрастающей подпоследовательности]]*
+
# [[Задача о монотонных подпоследовательностях, теорема о связи длины НВП и НУП]]
−
*[[Задача коммивояжера, ДП по подмножествам]]
 
−
*[[Задача о редакционном расстоянии, алгоритм Вагнера-Фишера]]
 
−
*[[Задача о рюкзаке]]
 
−
 
 
−
=== Способы оптимизации методов динамического программирования ===
 
−
*[[Метод четырех русских для умножения матриц]]
 
−
*[[Применение метода четырех русских в задачах ДП на примере задачи о НОП]]<tex>^\star</tex>
 
−
*[[Задача об оптимальном префиксном коде с сохранением порядка. Монотонность точки разреза]]
 
−
*[[Meet-in-the-middle]]<tex>^\star</tex>
 
−
*[[Convex hull trick]]
 
−
 
 
−
=== Другие задачи ===
 
−
*[[Задача о расстоянии Дамерау-Левенштейна]]<tex>^\star</tex>
 
−
*[[Задача о выводе в контекстно-свободной грамматике, алгоритм Кока-Янгера-Касами]]
 
−
*[[Задача о наибольшей подпоследовательности-палиндроме]]
 
−
*[[Задача о наибольшей общей возрастающей последовательности]]<tex>^\star</tex>
 
−
*[[Задача о наибольшей общей палиндромной подпоследовательности]]<tex>^\star</tex>
 
−
*[[Динамическое программирование по профилю]]<tex>^\star</tex>
 
−
*[[Динамика по поддеревьям]]
 

Текущая версия на 23:03, 13 декабря 2018

Тикеты индексируются как "X-Y", где X — номер раздела, Y — номер конспекта внутри раздела (например, конспект ДНФ из раздела булевых функций имеет тикет 2-4)

1. Отношения

  1. Определение отношения
  2. Композиция отношений, степень отношения, обратное отношение
  3. Рефлексивное отношение. Антирефлексивное отношение.
  4. Симметричное отношение
  5. Антисимметричное отношение
  6. Транзитивное отношение
  7. Отношение порядка
  8. Изоморфизмы упорядоченных множеств[math]^\star[/math]
  9. Отношение эквивалентности
  10. Транзитивное замыкание отношения
  11. Алгоритм Флойда-Уоршалла построения транзитивного замыкания отношения
  12. Транзитивный остов

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

  1. Определение булевой функции 0,5
    1. исправить знаки неравенств
  2. Побитовые операции[math]^\star[/math]
  3. Суперпозиции 2
    1. Дописать раздел про ранги суперпозиций
  4. ДНФ
  5. Сокращенная и минимальная ДНФ, минимизация ДНФ методами гиперкубов, карт Карно, Квайна
  6. КНФ
  7. 2-SAT
  8. XOR-SAT[math]^\star[/math]
  9. Специальные формы КНФ: КНФ в форме Хорна и КНФ в форме Крома
  10. Полином Жегалкина, преобразование Мёбиуса
  11. Полные системы функций. Теорема Поста о полной системе функций
  12. Представление функции класса DM с помощью медианы 2-10
    1. Добавить см. также
    2. Правильно оформить источники информации
    3. Исправить знаки неравенств
    4. Добавить примеры на конкретный функциях (чем интереснее примеры, тем больше баллов)
  13. Пороговая функция
  14. Троичная логика[math]^\star[/math]

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

  1. Реализация булевой функции схемой из функциональных элементов 5
    1. Добавить информацию о методе построения схемы по функции
    2. Добавить алгоритм вычисления глубины схемы
    3. Добавить картинки к доказательствам
  2. Простейшие методы синтеза схем из функциональных элементов 6
    1. Добавить примеры на каждый метод
  3. Метод Лупанова синтеза схем 0.5
    1. Правильно оформить источники информации
  4. Cумматор
  5. Каскадный сумматор
  6. Двоичный каскадный сумматор 5
    1. Сделать конспект более понятным
  7. Троичный сумматор[math]^\star[/math]
  8. Реализация вычитания сумматором
  9. Матричный умножитель
  10. Дерево Уоллеса
  11. Контактная схема 1
    1. взяли Перерисовать картинки с построением контактных схем и дерево конъюнктов
  12. Триггеры[math]^\star[/math]
  13. Квантовые гейты[math]^\star[/math]

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

  1. Кодирование информации
  2. Представление целых чисел: прямой код, код со сдвигом, дополнительный код
  3. Представление вещественных чисел
  4. Представление символов, таблицы кодировок[math]^\star[/math]

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

  1. Алгоритм Хаффмана
  2. Оптимальное хранение словаря в алгоритме Хаффмана
  3. Алгоритм Хаффмана за O(n) 0.5
    1. Источники информации
  4. Алгоритм Ху-Таккера[math]^\star[/math]
  5. Неравенство Крафта 5-10
    1. Доказательство вообще не о том, требуется полностью переписать
  6. Неравенство Макмиллана 2-5
    1. Доказательство требует косметических правок
  7. Код Шеннона
  8. Оптимальный префиксный код с длиной кодового слова не более L бит[math]^\star[/math]
  9. Алгоритмы LZ77 и LZ78 2
    1. Переменные и константы взять в Tex
    2. Добавить примеры итоговых таблиц
    3. Рассказать, как декодировать
    4. Правильно оформить источники информации
    5. Получше расписать описание алгоритма
    6. Таблицы сделать красивыми
    7. Интервики
  10. Алгоритм LZW 0,25
    1. См. также
  11. Алгоритм LZSS[math]^\star[/math]
  12. Алгоритм LZMA[math]^\star[/math]
  13. Преобразование Барроуза-Уиллера и обратное ему
  14. Преобразование MTF
  15. Расстояние Хэмминга
  16. Избыточное кодирование, код Хэмминга 0,25
    1. См. также
  17. Гамма-, дельта- и омега-код Элиаса[math]^\star[/math] 0,25
    1. См. также

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

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

  1. Комбинаторные объекты
  2. Лексикографический порядок
  3. Коды Грея
  4. Коды Грея для перестановок
  5. Коды антигрея
  6. Монотонный код Грея
  7. Цепные коды
  8. Правильные скобочные последовательности

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

  1. Генерация комбинаторных объектов в лексикографическом порядке 0.5
    1. Заменить скобки "больше-меньше" на угловые
    2. Нормальную красивую картинку нарисовать
  2. Получение номера по объекту
  3. Получение объекта по номеру
  4. Получение следующего объекта
  5. Получение предыдущего объекта[math]^\star[/math]
  6. Метод генерации случайной перестановки, алгоритм Фишера-Йетса
  7. Методы генерации случайного сочетания[math]^\star[/math]

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

  1. Формула включения-исключения, подсчет числа беспорядков 1
    1. в первой теореме в доказательстве по индукции получен результат не тот, что в условии
  2. Нахождение количества разбиений числа на слагаемые. Пентагональная теорема Эйлера
  3. Лемма Бёрнсайда и Теорема Пойа
  4. Задача об ожерельях
  5. Числа Стирлинга первого рода 5
    1. [math]\left[{m+n+1\atop m}\right]=\sum\limits_{k=0}^n (n+k) \left[{n+k\atop k}\right][/math] то есть результат не зависит от [math]m[/math]?
    2. Поправить тех
    3. доказательства дополнительных тождеств
  6. Числа Стирлинга второго рода
  7. Символ Похгаммера
  8. Числа Белла
  9. Числа Эйлера первого и второго рода. Подъемы в перестановках
  10. Числа Каталана 0,5
    1. См. также
  11. Конструирование комбинаторных объектов и их подсчет

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

  1. Умножение перестановок, обратная перестановка, группа перестановок
  2. Действие перестановки на набор из элементов, представление в виде циклов
  3. Таблица инверсий 0,25
    1. tex в заголовок
  4. Теорема Кэли
  5. Матричное представление перестановок
  6. Задача о минимуме/максимуме скалярного произведения
  7. Задача о монотонных подпоследовательностях, теорема о связи длины НВП и НУП
Источник — «http://neerc.ifmo.ru/wiki/index.php?title=Дискретная_математика:Тикеты&oldid=67887»