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

Практические занятия по языку C на первом курсе МФТИ. Кафедра информатики. На этом занятии мы познакомимся с принципом оптимальности Беллмана и дискретным динамическим программированием. Мы решим несколько классических задач: рюкзак, размен монет, расстояние редактирования в строках. Кроме того мы ещё немного сдвинем пределы регулярности и выясним связь формальных грамматик как с регулярными выражениями, так и с динамическим программированием. В конце будет небольшое объяснение про мемсет. Семинарист: Константин Владимиров. Дата: 19 февраля 2024 года. Съёмка: Владислав Белов. Звук: Юлий Тарасов. Предыдущий семинар: Следующий семинар: TBD Слайды к занятиям: Примеры кода: Задачник: Timeline 00:00 Принцип оптимальности 08:30 Приложение к размену монет 15:49 Прямое и обратное вычисления 24:19 Задача о рюкзаке 33:06 Рассто