Информация по курсу

В жизни реальным системам часто приходится решать задачи, которые вычислительно являются очень сложными (обычно NP-трудными), но решать их нужно онлайн с минимальными задержками. Например, сетевой коммутатор должен управлять буфером из сетевых пакетов в реальном времени, принимая решения сразу после прибытия очередной порции пакетов. Чтобы оценить качество работы таких онлайн-алгоритмов в худшем случае, часто используют так называемый конкурентный анализ: насколько наш онлайн-алгоритм проигрывает самому лучшему оптимальному алгоритму (который мы, скорее всего, даже и построить не сможем)? В рамках спецсеминара мы последовательно рассмотрим основные результаты конкурентного анализа в применении к сетевым алгоритмам; по итогам семинара можно будет сформулировать направления для дальнейших исследований в этой интересной и быстро развивающейся области информатики.

Семинаристы