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

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