Нижние оценки сложности и оптимальные алгоритмы

В курсе излагаются основные принципы разработки и применения современных методов оптимизации. Во вводной лекции обсуждаются приоритеты алгоритмической Теории Оптимизации, учитывая ее связующее положение между математикой и инженерными науками. Далее мы подробно останавливаемся на нижних оценках сложности и оптимальных методах в модели "черный ящик". В то же время приводятся примеры преодоления теоретических пределов эффективности этой теории за счет использования структуры оптимизационных задач (методы внутренней точки, сглаживание, минимизация составных функций). Затем мы обсудим специальные подходы к решению задач очень больших размеров. Завершается курс двумя нестандартными разделами: применение выпуклой оптимизации для решения комбинаторных задач и алгоритмическими моделями, объясняющих возможность рационального поведения в живой и неживой природе.