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

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

Текущая версия на 19:06, 4 сентября 2022

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

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

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

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

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. Динамическое программирование по профилю (7)
    1. Англоязычные термины
    2. Заменить умножение на \cdot
    3. Заменить дефисы на тире
    4. Взять переменные и константы в Tex
    5. Отформатировать псевдокоды
    6. Добавить ещё примеров
    7. Оформить правильно источники информации
    8. Добавить нормальное объяснение происходящего (и почему это работает)
  7. Динамика по поддеревьям
Источник — «http://neerc.ifmo.ru/wiki/index.php?title=Динамическое_программирование:Тикеты&oldid=84430»