«Теория всего»: унификация паттернов дизайна алгоритмов (метода отката, ветвей и границ, жадных алгоритмов, метода разделяй и властвуй, и динамического программирования…) – вторая часть (завершение доклада)

Курс проектирования и анализа алгоритмов является обязательной составляющей учебных программ по информатике всех уровней. В университетах этот курс обязательно включает изучение структур данных, методы проектирования алгоритмов, теорию сложности и т.д. Этот курс знакомит с такими методами проектирования алгоритмов, как жадные алгоритмы, динамическое программирование, метод разделяй и властвуй, метод отката, метод ветвей и границ. Обычно знакомство с этими методами происходит на примерах. Но они могут быть (полу)формализованы в виде рекурсивных «паттернов» (с использованием map и reduce), специфицированы условиями частичной и/или тотальной корректности и обоснованы (доказаны) методом Флойда верификации алгоритмов.
Данное выступление было второй (завершающей) частью доклада, первая часть была представлена на семинаре 22 мая 2024 г.
Есть рабочая записи на YouTube-канале ИСИ СО РАН первой (https://youtu.be/TVHvdbHmxso) и второй (https://youtu.be/SsML27oNwPk) частей доклада, а также полная презентация (https://persons.iis.nsk.su/files/persons/pages/innopolis22may19jun24.pdf).