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

Практические занятия по языку C на первом курсе МФТИ. Кафедра информатики. На этом занятии мы познакомимся с принципом оптимальности Беллмана и дискретным динамическим программированием. Мы решим несколько классических задач: рюкзак, размен монет, расстояние редактирования в строках. Кроме того мы ещё немного сдвинем пределы регулярности и выясним связь формальных грамматик как с регулярными выражениями, так и с динамическим программированием. В конце будет небольшое объяснение про мемсет. Для полноты картины рекомендую после этого видео посмотреть также видео по матроидам с прошлого года (в этом году увы не укладывается, но я добавлю в плейлист). А именно вот это:    • Матроиды (доп. семинар для первого курса п...   Семинарист: Константин Владимиров. Дата: 19 февраля 2024 года. Съёмка: Владислав Белов. Звук: Юлий Тарасов. Предыдущий семинар:    • Практика языка C (МФТИ, 2023-2024). Семина...   Следующий семинар:    • Практика языка C (МФТИ, 2023-2024). Семина...   Слайды к занятиям:
Примеры кода:
Задачник:
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 Интересный вопрос про мемсет. См. также:
Errata пока пусто