Shilov22may24

Николай Вячеславович Шилов (Университет Иннополис): "Теория всего": унификация паттернов дизайна алгоритмов (метода отката, ветвей и границ, жадных алгоритмов, метода разделяй и властвуй, и динамического программирования...)
(Первая часть доклада - 22 мая 2025 г., вторая часть доклада 19 июня 2024 г. см. • Shilov19jun24 )
Аннотация: Курс проектирования и анализа алгоритмов является обязательной составляющей учебных программ по информатике всех уровней. В университетах этот курс обязательно включает изучение структур данных, методы проектирования алгоритмов, теорию сложности и т.д. Этот курс знакомит с такими методами проектирования алгоритмов, как жадные алгоритмы, динамическое программирование, метод разделяй и властвуй, метод отката, метод ветвей и границ. Обычно знакомство с этими методами происходит на примерах. Но они могут быть (полу)формализованы в виде рекурсивных "паттернов" (с использованием map и reduce), специфицированы условиями частичной и/или тотальной корректности и обоснованы (доказаны) методом Флойда верификации алгоритмов.