Saint Petersburg, 199178, Russia, Line 14th (Vasilyevsky Island), 29
(812) 363-68-71, (812) 363-68-72
ru en

Сетевые алгоритмы

2019 – 2020, V, VII семестр

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

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