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

Материал из Викиконспекты
Перейти к: навигация, поиск
(→‎3 Подсчёт числа объектов)
(→‎1 Классические задачи динамического программирования)
Строка 174: Строка 174:
 
=== 1 Классические задачи динамического программирования ===
 
=== 1 Классические задачи динамического программирования ===
 
# [[Кратчайший путь в ациклическом графе]]
 
# [[Кратчайший путь в ациклическом графе]]
−
# [[Задача о числе путей в ациклическом графе]]
+
# [[Задача о числе путей в ациклическом графе]] (4)
−
# [[Задача о расстановке знаков в выражении]]
+
## Взять задачу в шаблон
−
# [[Задача о порядке перемножения матриц]]
+
## Отформатировать псевдокод
 +
## Обернуть имя функции в тексте в mathrm
 +
## Заменить дефисы на тире
 +
## Добавить см. также и источники информации
 +
## Добавить пример простого ациклического графа в виде прямоугольной матрицы с препятствиями
 +
# [[Задача о расстановке знаков в выражении]] (6)
 +
## Взять задачу в шаблон
 +
## Исправить знаки неравенств
 +
## Ссылку примечанием оформить нормально
 +
## Взять все переменные и константы в тексте в Tex
 +
## Отформатировать псевдокод
 +
## Табличку нормально оформить
 +
## Описать восстановление ответа
 +
## Источники информации правильно оформить
 +
## Добавить решение задачи без возможности использования скобок
 +
# [[Задача о порядке перемножения матриц]] (3)
 +
## Взять переменные и константы в Tex
 +
## Обернуть задачу в шаблон
 +
## Интервики на конспект правильных скобочных последовательностей
 +
## Написать, почему нас не устраивает число Каталана в асимптотике
 +
## Отформатировать псевдокоды
 +
## Оформить правильно источники информации
 +
## Убрать про мемоизацию
 
# [[Задача о наибольшей общей подпоследовательности]]
 
# [[Задача о наибольшей общей подпоследовательности]]
 
# [[Задача о наибольшей возрастающей подпоследовательности]]
 
# [[Задача о наибольшей возрастающей подпоследовательности]]
Строка 182: Строка 204:
 
# [[Задача коммивояжера, ДП по подмножествам]]
 
# [[Задача коммивояжера, ДП по подмножествам]]
 
# [[Задача о редакционном расстоянии, алгоритм Вагнера-Фишера]]
 
# [[Задача о редакционном расстоянии, алгоритм Вагнера-Фишера]]
−
# [[Задача о рюкзаке]]
+
# [[Задача о рюкзаке]] (8)
 +
## Взять задачу в шаблон
 +
## Отформатировать псевдокоды
 +
## Заменить дефисы на тире
 +
## Исправить знаки неравенств
 +
## Написать, что метод динамического программирование всё равно не повзволяет решать задачу за полиномиальное время и написать почему
 +
## Сделать итоговую формулу для А c помощью фигурной скобки
 +
## Предложить вариант замены картинок на вики-таблички с сохранением обозначения пути
 +
## Понизить уровень заголовков первого уровня
 +
## Оформить правильно источники информации
  
 
=== 2 Способы оптимизации методов динамического программирования ===
 
=== 2 Способы оптимизации методов динамического программирования ===

Версия 23:06, 19 мая 2017

1. Отношения

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

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

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

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

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. Производящая функция 0,25
    1. См. также
  4. Лемма Бёрнсайда и Теорема Пойа
  5. Задача об ожерельях
  6. Числа Стирлинга первого рода 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. доказательства дополнительных тождеств
  7. Числа Стирлинга второго рода
  8. Числа Эйлера первого и второго рода. Подъемы в перестановках[math]^\star[/math] 0,25
    1. См. также
  9. Числа Каталана 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. См. также

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

1 Классические задачи динамического программирования

  1. Кратчайший путь в ациклическом графе
  2. Задача о числе путей в ациклическом графе (4)
    1. Взять задачу в шаблон
    2. Отформатировать псевдокод
    3. Обернуть имя функции в тексте в mathrm
    4. Заменить дефисы на тире
    5. Добавить см. также и источники информации
    6. Добавить пример простого ациклического графа в виде прямоугольной матрицы с препятствиями
  3. Задача о расстановке знаков в выражении (6)
    1. Взять задачу в шаблон
    2. Исправить знаки неравенств
    3. Ссылку примечанием оформить нормально
    4. Взять все переменные и константы в тексте в Tex
    5. Отформатировать псевдокод
    6. Табличку нормально оформить
    7. Описать восстановление ответа
    8. Источники информации правильно оформить
    9. Добавить решение задачи без возможности использования скобок
  4. Задача о порядке перемножения матриц (3)
    1. Взять переменные и константы в Tex
    2. Обернуть задачу в шаблон
    3. Интервики на конспект правильных скобочных последовательностей
    4. Написать, почему нас не устраивает число Каталана в асимптотике
    5. Отформатировать псевдокоды
    6. Оформить правильно источники информации
    7. Убрать про мемоизацию
  5. Задача о наибольшей общей подпоследовательности
  6. Задача о наибольшей возрастающей подпоследовательности
  7. Быстрый поиск наибольшей возрастающей подпоследовательности*
  8. Задача коммивояжера, ДП по подмножествам
  9. Задача о редакционном расстоянии, алгоритм Вагнера-Фишера
  10. Задача о рюкзаке (8)
    1. Взять задачу в шаблон
    2. Отформатировать псевдокоды
    3. Заменить дефисы на тире
    4. Исправить знаки неравенств
    5. Написать, что метод динамического программирование всё равно не повзволяет решать задачу за полиномиальное время и написать почему
    6. Сделать итоговую формулу для А c помощью фигурной скобки
    7. Предложить вариант замены картинок на вики-таблички с сохранением обозначения пути
    8. Понизить уровень заголовков первого уровня
    9. Оформить правильно источники информации

2 Способы оптимизации методов динамического программирования

  1. Метод четырех русских для умножения матриц
  2. Применение метода четырех русских в задачах ДП на примере задачи о НОП[math]^\star[/math]
  3. Задача об оптимальном префиксном коде с сохранением порядка. Монотонность точки разреза
  4. Meet-in-the-middle[math]^\star[/math]
  5. Convex hull trick

3 Другие задачи

  1. Задача о расстоянии Дамерау-Левенштейна[math]^\star[/math]
  2. Задача о выводе в контекстно-свободной грамматике, алгоритм Кока-Янгера-Касами
  3. Задача о наибольшей подпоследовательности-палиндроме
  4. Задача о наибольшей общей возрастающей последовательности[math]^\star[/math]
  5. Задача о наибольшей общей палиндромной подпоследовательности[math]^\star[/math]
  6. Динамическое программирование по профилю[math]^\star[/math]
  7. Динамика по поддеревьям
Источник — «http://neerc.ifmo.ru/wiki/index.php?title=Дискретная_математика:Тикеты&oldid=60810»