вт, 27.10 | Online Event

Tuesday Afternoon Club/Session 4: Апроксимиращи алгоритми

Registration is Closed
Tuesday Afternoon Club/Session 4: Апроксимиращи алгоритми

Time & Location

27.10.2020 г., 18:30 – 20:00
Online Event

About the Event

Презентатор: доц. Минко Марков

Модератор: доц. Петър Армянов

Резюме: Сесията разглежда един начин за “заобикаляне” на алгоритмичната неподатливост (intractability): конструиране на апроксимиращи алгоритми.

В началото ще разгледаме оптимизационни изчислителни задачи по принцип и в частност NP-трудни оптимизационни задачи. След това ще разгледаме примери за ефикасни алгоритми за неподатливи оптимизационни задачи, които връщат не непременно оптимални решения, но дават гаранции за неоптималността. Ще разгледаме различни техники за конструиране на такива алгоритми.

После ще въведем формални определения и няколко изчислителни класове. Накрая ще разгледаме относителната спрямо недоказаната хипотеза, че P≠NP - невъзможност за апроксимиране на няколко задачи.

Registration is Closed

Share This Event