Złożoność Obliczeniowa
(Seminarium)
Tematy (i źrodła)
¡ Temat 1: Języki
McNaughtona (A.Jeż)
·
M.Beaudry, M.Holzer.
G.Niemann, F.Otto, McNaughton Languages
¡ Temat 2: Algorytmy
kwantowe (rez.: A.Mądry: Slajdy)
·
Materiały pomocnicze:
¡ Temat 3: Złożoność deterministycznych języków bezkontekstowych
·
S.Cook, Deterministic
CFL's are accepted simultaneously in polynomial time and log squared space
¡ Temat 4: Kompresja
przy pomocy gramatyk (rez.: J.Otop: Slajdy)
¡ Temat 5: Rosnące języki kontekstowe
¡ Temat 6: Problem
spójności grafów nieskierowanych (A.Jeż: Slajdy)
¡ Temat 7:
Deterministyczna symulacja obliczeń zrandomizowanych z LOGSPACE (A.Wasylkowski: Slajdy)
¡ Temat 8: Ograniczony niedeterminizm (rez.:
J.Straszewski)
¡
Temat 9: Problem spójności grafów nieskierowanych cz.II (M.Wrona)
·
Materiały pomocnicze:
¡
Temat 10: Hierarchie czasowe
dla obliczeń probabilistycznych
·
Materiały pomocnicze:
¡
Temat 11: „Zgadywanie
sekretów”
·
Materiały pomocnicze:
i.
F.Chung, R.Graham, T.Leighton, Guessing secrets
Komunikaty
·
20 października (środa) na seminarium ZZOiAA (godz. 14-16) będziemy gościć
prof. Friedricha Otto z Uniwersytetu Kassel.
·
Powyższą listę propozycji tematów będę sukcesywnie uzupełniał. Kolejność
prezentowania tematów na seminarium nie jest implikowana kolejnością liście
(oczywiście poza pierwszym tematem)
·
22 października na seminarium wystąpi prof. F.Mraz z Pragi. Temat odczytu: Learning Analysis by Reduction.