Zadanie nr 1 za 1 punkt (5 punktow = 5 z egzaminu).

Termin rozwiazania: wtorek 25.10 godz. 23:59
Rozwiazania mozna nadsylac wylacznie droga elektroniczna

niwinski@mimuw.edu.pl

Dlugoscia strategii skonczenie-wygrywajacej nazwiemy dlugosc najdluzszej rozgrywki zgodnej z ta strategia.
Zaprojektowac algorytm, ktory dla danej skonczonej areny znajduje najkrotsza strategie pozycyjna skonczenie
wygrywajaca dla Ewy. Strategie mozna reprezentowac jako funkcje czesciowa lub jako zbior krawedzi.

Nalezy uzasadnic poprawnosc algorytmu i oszacowac jego zlozonosc.
Pozytywnie beda ocenione tylko algorytmy o optymalnej zlozonosci.

Uwaga. Rozwiazanie zadania nie jest obowiazkowe.
W przyszlosci beda podane zadania za lacznie co najmniej 10 pt.