Практика языка C (МФТИ, 2023-2024). Семинар 5.3. Динамическое программирование.

Практические занятия по языку C на первом курсе МФТИ. Кафедра информатики.

На этом занятии мы познакомимся с принципом оптимальности Беллмана и дискретным динамическим программированием. Мы решим несколько классических задач: рюкзак, размен монет, расстояние редактирования в строках. Кроме того мы ещё немного сдвинем пределы регулярности и выясним связь формальных грамматик как с регулярными выражениями, так и с динамическим программированием. В конце будет небольшое объяснение про мемсет.

Для полноты картины рекомендую после этого видео посмотреть также видео по матроидам с прошлого года (в этом году увы не укладывается, но я добавлю в плейлист). А именно вот это:    • Матроиды (доп. семинар для первого ку...  

Семинарист: Константин Владимиров.
Дата: 19 февраля 2024 года.
Съёмка: Владислав Белов.
Звук: Юлий Тарасов.

Предыдущий семинар:    • Практика языка C (МФТИ, 2023-2024). С...  
Следующий семинар:    • Практика языка C (МФТИ, 2023-2024). С...  

Слайды к занятиям: http://cs.mipt.ru/wp/?page_id=7775
Примеры кода: https://github.com/tilir/c-graduate
Задачник: http://olymp1.vdi.mipt.ru/

Timeline
00:00 Принцип оптимальности
08:30 Приложение к размену монет
15:49 Прямое и обратное вычисления
24:19 Задача о рюкзаке
33:06 Расстояние редактирования
39:03 Время решать задачи
41:55 Грамматики
50:26 Нормальная форма Хомского
56:20 Алгоритм Кока-Янгера-Касами
01:03:58 Travelling salesman и литература
01:09:15 Ревью кода
01:16:56 Интересный вопрос про мемсет.

См. также: https://godbolt.org/z/MKc4ha95e

Errata
* пока пусто