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

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