Дискретная математика:Тикеты

Материал из Викиконспекты
Версия от 13:18, 13 декабря 2017; 31.193.122.170 (обсуждение) (→‎5 Алгоритмы сжатия)
Перейти к: навигация, поиск

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

1. Отношения

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

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

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

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

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

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

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

  1. Алгоритм Хаффмана
  2. Оптимальное хранение словаря в алгоритме Хаффмана
  3. взяли Алгоритм Хаффмана за O(n) 1
    1. Мутное доказательство после разбора случаев, надо понятней написать, а то сейчас не ясно, почему будет всё ок
  4. Алгоритм Ху-Таккера[math]^\star[/math]
  5. Неравенство Крафта
  6. Неравенство Макмиллана
  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. Формула включения-исключения, подсчет числа беспорядков
  2. Нахождение количества разбиений числа на слагаемые. Пентагональная теорема Эйлера 0,5
    1. Сделать через tex возведение в степень в заголовках
    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. доказательства дополнительных тождеств
  6. Числа Стирлинга второго рода
  7. Числа Эйлера первого и второго рода. Подъемы в перестановках[math]^\star[/math] 0,25
    1. См. также
  8. Числа Каталана 0,25
    1. См. также

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

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