KTGiZU

Środy, 10:15-11:45

Gmach MiNI PW, Sala 431, ul. Koszykowa 75, Warszawa

Seminaria odbywają się stacjonarnie z transmisją na platformie MS Teams.

Jeśli chcesz dołączyć do spotkania, to napisz do sekretarza seminarium.

Najbliższy referat

14.10.2026	Hubert Grochowski	PW
Najkrótsza ścieżka z atakującym - aspekty złożonościowe i probabilistyczne
\(\quad\)W problemach praktycznych, nierzadko musimy zmierzyć się z niepewnością danych. Jednym z podejść do modelowania tego typu problemów jest przedstawienie ich jako gry dwuosobowej, gdzie jeden gracz stara się rozwiązać problem, a drugi zaburza dane, symulując ich niepewność. W trakcie referatu, skupimy się na grze typu min-max "Shortest Path under the Attacks", granej na ważonym grafie pomiędzy dwoma graczami - Ścieżkowcem (Pather), który chce wybrać możliwie najtańszą ścieżkę pomiędzy dwoma ustalonymi wierzchołkami i Atakującym (Attacker), który dysponuje budżetem, który może rozdzielić na krawędzie grafu, zwiększając przy tym wagi niektórych z nich. \(\quad\)Szczegółowo skupimy się na wariancie mieszanym tej gry, gdzie gracze szukają optymalnych rozkładów prawdopodobieństwa na przestrzeni swoich ruchów, aby uzyskać optymalny średni wynik gry. Pokażemy, że w pewnych szczególnych przypadkach tej gry, optymalne rozkłady można znaleźć w czasie wielomianowym. Ponadto przedstawimy wyniki probabilistyczne dotyczących struktury optymalnych rozkładów dla Ścieżkowca. \(\quad\)Współautorzy: Armin Fügenschuh, Konstanty Junosza-Szaniawski

Zespół prowadzący