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

Материал из Викиконспекты
Перейти к: навигация, поиск
(→‎3 Подсчёт числа объектов)
(→‎2 Генерация комбинаторных объектов)
 
(не показано 25 промежуточных версий 2 участников)
Строка 2: Строка 2:
  
 
== 1. Отношения ==
 
== 1. Отношения ==
−
#[[Определение отношения]] 0.5
+
# [[Определение отношения]]
−
## Оформить правильно источники информации
+
# [[Композиция отношений|Композиция отношений, степень отношения, обратное отношение]]
−
## Английские термины к видам отношений
+
# [[Рефлексивное отношение|Рефлексивное отношение. Антирефлексивное отношение.]]
−
#[[Композиция отношений|Композиция отношений, степень отношения, обратное отношение]] 1
+
# [[Симметричное отношение]]
−
## Английские термины
+
# [[Антисимметричное отношение]]
−
## Источники информации
+
# [[Транзитивное отношение]]
−
## Все формулы в тех
+
# [[Отношение порядка]]
−
## Свойства оформить красиво
+
# [[Изоморфизмы упорядоченных множеств]]<tex>^\star</tex>
−
## Оформить правильно источники информации
+
# [[Отношение эквивалентности]]  
−
# '''взяли''' [[Рефлексивное отношение|Рефлексивное отношение. Антирефлексивное отношение.]] 0,25
+
# [[Транзитивное замыкание|Транзитивное замыкание отношения]]  
−
## См. также
+
# [[Алгоритм Флойда — Уоршелла|Алгоритм Флойда-Уоршалла построения транзитивного замыкания отношения]]
−
#[[Симметричное отношение]]
+
# [[Транзитивный остов]]
−
#[[Антисимметричное отношение]]
 
−
# '''взяли''' [[Транзитивное отношение]] 0,25
 
−
## Добавить См. также
 
−
#[[Отношение порядка]] 0,5
 
−
## Английские термины
 
−
## Добавить см. также
 
−
## Оформить правильно источники информации
 
−
#[[Изоморфизмы упорядоченных множеств]]<tex>^\star</tex>
 
−
# '''взяли''' [[Отношение эквивалентности]] 0,25
 
−
## добавить см. также
 
−
# '''взяли''' [[Транзитивное замыкание|Транзитивное замыкание отношения]] 0,5
 
−
## Добавить см. также
 
−
## Многоточие заменить на \ldots
 
−
#[[Алгоритм Флойда — Уоршелла|Алгоритм Флойда-Уоршалла построения транзитивного замыкания отношения]]
 
−
# '''взяли''' [[Транзитивный остов]] 0,25
 
−
## Английские термины
 
  
 
== 2 Булевы функции ==
 
== 2 Булевы функции ==
−
# [[Определение булевой функции]] 1,5
+
# [[Определение булевой функции]] 0,5
−
## Добавить интервики на термины монотонности, линейности, сохранения <tex>0</tex> и <tex>1</tex>, самодвойственности для булевой функции. (все определения [[Полные_системы_функций._Теорема_Поста_о_полной_системе_функций|здесь]])
+
## исправить знаки неравенств
−
## Добавить кратко про ДНФ, КНФ, полином Жегалкина и схемы из функциональных элементов
+
# [[Побитовые операции]]<tex>^\star</tex>
−
# [[Побитовые операции]]<tex>^\star</tex> 1
+
# [[Суперпозиции]] 2
−
## Добавить краткую суть алгоритмов Флойда и Фенвика
+
## Дописать раздел про ранги суперпозиций
−
# '''взяли''' [[Суперпозиции]] 0,5
+
# [[ДНФ]]  
−
## Добавить см. также
 
−
## Многоточие заменить на \ldots
 
−
#[[ДНФ]] 0,5 {{---}} 2 (зависит от примера)
 
−
## Многоточие заменить на \ldots
 
−
## Добавить пример еще какой нибудь функции
 
 
#[[Сокращенная и минимальная ДНФ | Сокращенная и минимальная ДНФ, минимизация ДНФ методами гиперкубов, карт Карно, Квайна]]
 
#[[Сокращенная и минимальная ДНФ | Сокращенная и минимальная ДНФ, минимизация ДНФ методами гиперкубов, карт Карно, Квайна]]
−
#[[КНФ]] 0,5 {{---}} 2 (зависит от примера)
+
# [[КНФ]]  
−
## Многоточие заменить на \ldots
+
# [[2-SAT]]
−
## Добавить пример еще какой нибудь функции
+
# [[XOR-SAT]]<tex>^\star</tex>
−
## Добавить см. также
+
# [[Специальные формы КНФ|Специальные формы КНФ: КНФ в форме Хорна и КНФ в форме Крома]]
−
#[[2-SAT]]
+
# [[Полином Жегалкина | Полином Жегалкина, преобразование Мёбиуса]]  
−
#[[XOR-SAT]]<tex>^\star</tex>
+
# [[Полные системы функций. Теорема Поста о полной системе функций]]  
−
#[[Специальные формы КНФ|Специальные формы КНФ: КНФ в форме Хорна и КНФ в форме Крома]]
+
# [[Представление функции класса DM с помощью медианы]] 2-10
−
#'''взяли''' [[Полином Жегалкина | Полином Жегалкина, преобразование Мёбиуса]] 0,5
 
−
## Добавить см. также
 
−
## Многоточие заменить на \ldots
 
−
## Добавить интервики на термины монотонности, линейности, сохранения <tex>0</tex> и <tex>1</tex>, самодвойственности для булевой функции. (все определения [[Полные_системы_функций._Теорема_Поста_о_полной_системе_функций|здесь]])
 
−
#'''взяли''' [[Полные системы функций. Теорема Поста о полной системе функций]] 0,25
 
−
## Добавить см. также
 
−
#[[Представление функции класса DM с помощью медианы]] 0.5
 
 
## Добавить см. также
 
## Добавить см. также
 
## Правильно оформить источники информации
 
## Правильно оформить источники информации
−
## Заменить знаки неравенств
+
## Исправить знаки неравенств
−
#'''взяли''' [[Пороговая функция]] 0.5
+
## Добавить примеры на конкретный функциях (чем интереснее примеры, тем больше баллов)
−
## Добавить см. также
+
# [[Пороговая функция]]  
−
## Многоточие заменить на \ldots
 
 
#[[Троичная логика]]<tex>^\star</tex>
 
#[[Троичная логика]]<tex>^\star</tex>
  
 
== 3 Схемы из функциональных элементов ==
 
== 3 Схемы из функциональных элементов ==
−
#[[Реализация булевой функции схемой из функциональных элементов]]
+
#[[Реализация булевой функции схемой из функциональных элементов]] 5
−
#'''взяли''' [[Простейшие методы синтеза схем из функциональных элементов]] 0.5
+
## Добавить информацию о методе построения схемы по функции
−
## Изменить знаки неравенств
+
## Добавить алгоритм вычисления глубины схемы
−
## Ссылку на метод синтеза схем Шэннона сделать примечанием
+
## Добавить картинки к доказательствам
−
## Определение жирным
+
# [[Простейшие методы синтеза схем из функциональных элементов]] 6
−
## Оформить правильно См. также и Источники информации
+
## Добавить примеры на каждый метод
−
## Увеличить дроби
+
# [[Метод Лупанова синтеза схем]] 0.5
−
#'''взяли''' [[Метод Лупанова синтеза схем]] 0.5
+
## Правильно оформить источники информации
−
## Заменить литературу на источники информации
 
−
## Изменить знаки неравенств
 
−
## Запятые криво стоят в определении функции g
 
−
## Увеличить дроби
 
 
#[[Cумматор]]
 
#[[Cумматор]]
 
#[[Каскадный сумматор]]
 
#[[Каскадный сумматор]]
−
#[[Двоичный каскадный сумматор]]
+
#[[Двоичный каскадный сумматор]] 5
 +
## Сделать конспект более понятным
 
#[[Троичный сумматор]]<tex>^\star</tex>
 
#[[Троичный сумматор]]<tex>^\star</tex>
 
#[[Реализация вычитания сумматором]]
 
#[[Реализация вычитания сумматором]]
Строка 87: Строка 55:
 
#[[Дерево Уоллеса]]
 
#[[Дерево Уоллеса]]
 
#[[Контактная схема]] 1
 
#[[Контактная схема]] 1
−
## Перерисовать картинки с построением контактных схем и дерево конъюнктов  
+
## взяли Перерисовать картинки с построением контактных схем и дерево конъюнктов  
 
#[[Триггеры]]<tex>^\star</tex>
 
#[[Триггеры]]<tex>^\star</tex>
 
#[[Квантовые гейты]]<tex>^\star</tex>
 
#[[Квантовые гейты]]<tex>^\star</tex>
Строка 100: Строка 68:
 
# [[Алгоритм Хаффмана]]
 
# [[Алгоритм Хаффмана]]
 
# [[Оптимальное хранение словаря в алгоритме Хаффмана]]
 
# [[Оптимальное хранение словаря в алгоритме Хаффмана]]
−
# '''взяли''' [[Алгоритм Хаффмана за O(n)]] 1
+
# [[Алгоритм Хаффмана за O(n)]] 0.5
−
## Мутное доказательство после разбора случаев, надо понятней написать, а то сейчас не ясно, почему будет всё ок
+
## Источники информации
 
# [[Алгоритм Ху-Таккера]]<tex>^\star</tex>
 
# [[Алгоритм Ху-Таккера]]<tex>^\star</tex>
−
# [[Неравенство Крафта]]
+
# [[Неравенство Крафта]] 5-10
−
# [[Неравенство Макмиллана]]
+
## Доказательство вообще не о том, требуется полностью переписать
 +
# [[Неравенство Макмиллана]] 2-5
 +
## Доказательство требует косметических правок
 
# [[Код Шеннона]]
 
# [[Код Шеннона]]
 
# [[Оптимальный префиксный код с длиной кодового слова не более L бит]]<tex>^\star</tex>
 
# [[Оптимальный префиксный код с длиной кодового слова не более L бит]]<tex>^\star</tex>
Строка 150: Строка 120:
  
 
=== 3 Подсчёт числа объектов ===
 
=== 3 Подсчёт числа объектов ===
−
# [[Формула включения-исключения | Формула включения-исключения, подсчет числа беспорядков]]
+
# [[Формула включения-исключения | Формула включения-исключения, подсчет числа беспорядков]] 1
−
# [[Нахождение количества разбиений числа на слагаемые | Нахождение количества разбиений числа на слагаемые. Пентагональная теорема Эйлера]] 0,5
+
## в первой теореме в доказательстве по индукции получен результат не тот, что в условии
−
## Сделать через tex возведение в степень в заголовках
+
# [[Нахождение количества разбиений числа на слагаемые | Нахождение количества разбиений числа на слагаемые. Пентагональная теорема Эйлера]]  
−
## См. также
 
 
# [[Лемма Бёрнсайда и Теорема Пойа]]
 
# [[Лемма Бёрнсайда и Теорема Пойа]]
 
# [[Задача об ожерельях]]
 
# [[Задача об ожерельях]]
 
# [[Числа Стирлинга первого рода]] 5
 
# [[Числа Стирлинга первого рода]] 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>?
 
## <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 рода | Числа Эйлера первого и второго рода. Подъемы в перестановках]]<tex>^\star</tex> 0,25
+
# [[Символ Похгаммера]]
−
## См. также
+
# [[Числа Белла]]
−
# '''взяли''' [[Числа Каталана]] 0,25
+
# [[Числа Эйлера I и II рода | Числа Эйлера первого и второго рода. Подъемы в перестановках]]
 +
# [[Числа Каталана]] 0,5
 
## См. также
 
## См. также
 +
# [[Конструирование комбинаторных объектов и их подсчет]]
  
 
=== 4 Свойства комбинаторных объектов ===
 
=== 4 Свойства комбинаторных объектов ===
−
# [[Умножение перестановок, обратная перестановка, группа перестановок]] 5
+
# [[Умножение перестановок, обратная перестановка, группа перестановок]]  
−
## Английские термины
 
−
## Определения жирным
 
−
## Тут вообще неправильно описано умножение перестановок (не путать с подстановками)
 
−
## Отформатировать псевдокоды
 
−
## Все переменные и константы взять в Tex
 
−
## Оформить правильно источники информации
 
−
## Добавить примеров из конспекта групп по теории чисел
 
−
## Добавить реккурентную формулу числа инволюций c доказательством
 
 
# [[Действие перестановки на набор из элементов, представление в виде циклов]]
 
# [[Действие перестановки на набор из элементов, представление в виде циклов]]
 
# [[Таблица инверсий]] 0,25
 
# [[Таблица инверсий]] 0,25
Строка 180: Строка 144:
 
# [[Теорема Кэли]]
 
# [[Теорема Кэли]]
 
# [[Матричное представление перестановок]]
 
# [[Матричное представление перестановок]]
−
# [[Задача о минимуме/максимуме скалярного произведения]] 0,25
+
# [[Задача о минимуме/максимуме скалярного произведения]]  
−
## Cм. также
+
# [[Задача о монотонных подпоследовательностях, теорема о связи длины НВП и НУП]]
−
# [[Задача о монотонных подпоследовательностях, теорема о связи длины НВП и НУП]] 0.25
 
−
## См. также
 

Текущая версия на 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»