Санкт-Петербург, 199178, Россия, 14-ая линия Васильевского острова, дом 29
(812) 363-68-71, (812) 363-68-72
ru

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

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

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

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