Wakacyjne warsztaty "Teoria złożoności"
Zachęceni sukcesem seminarium studenckiego "Teoria złożoności" (przy czym sukces rozumiemy jako "odbywało się regularnie i przyciągało niezerową liczbę słuchaczy" ;) ) planujemy zorganizować w te wakacje warsztaty z teorii złożoności. Więcej informacji (w tym głosowanie w sprawie terminu) tutaj.
Tematy
Na pierwszym seminarium zdecydowaliśmy, że po wprowadzeniu podstawowych pojęć i wyników zajmiemy się różnymi mniej klasycznymi zagadnieniami, żeby nie konkurować z przedmiotem "Teoria złożoności", który odbędzie się w przyszłym semestrze. Poniżej proponowana (wstępna) lista tematów, które warto byłoby poruszyć - dopisujcie, które z tych tematów chcielibyście przygotować, oraz wszelkie uwagi co do doboru tematów.
- alternacja, hierarchia wielomianowa — Marcin Wrochna
- obwodowe klasy złożoności, dolne granice dla obwodów — Adam Witkowski
- teoria złożoności a kryptografia
- kwantowe klasy złożoności
- złożoność komunikacyjna
- interaktywne protokoły (IP=PSPACE)
- czy P=?NP może być niezależne od PA - Janek Szejko
Spotkania
Spotykamy się w pażdy piątek, 14:15-15:45 w sali 5070
27 maja
Michał Dębski opowie o złożoności zliczania.
21 maja
O twierdzeniu PCP i o jego zastosowaniach w dowodzeniu trudności aproksymacji opowie Karolina Sołtys.
14 maja
Karolina Sołtys opowie o tym, dlaczego jeszcze nie umiemy dowieść, że $P \neq NP$ — poznamy parę meta-dowodów, że pewne techniki dowodzenia nie mogą w tym przypadku działać.
7 maja
Juwenalia — nie ma seminarium.
30 kwietnia
Marek Kłocewiak (UKSW) opowie o maszynach Busy Beaver.
23 kwietnia
Dalszy ciąg referatu Adama — dolne granice dla obwodów.
16 kwietnia
Adam Witkowski opowie o obwodowych klasach złożoności i dolnych granicach dla obwodów.
9 kwietnia
Marcin Wrochna opowie o alternujących maszynach Turinga i hierarchii wielomianowej.
26 marca
Na najbliższym spotkaniu podzielimy się rozdziałami książki i omówimy parę spraw organizacyjnych. Rozgrzewkowy wykład wprowadzi kilka podstawowych pojęć i definicji i będzie dotyczył paru klasycznych wyników:
- twierdzenie o hierarchii czasowej/pamięciowej (DTIME($n^k$) $\subsetneq$ DTIME($n^{k+1}$))
- twierdzenie Savitcha (PSPACE=NPSPACE)
- twierdzenie Immermana-Szelepcsenyi (NPSPACE=co-NPSPACE)
Dobór tematów będzie w dużej mierze zależał od wiedzy i zainteresowania słuchaczy.
Ciasteczkami tygodnia będą: Pieguski.
O seminarium
W semestrze letnim 2010 chcemy uruchomić seminarium studenckie "Teoria złożoności", które będzie kontynuowane w latach kolejnych. Pomysł jest o tyle istotny, że w tym roku taki przedmiot nie jest oferowany na naszym wydziale, a dziedzina ta jest jedną z najpiękniejszych i najbardziej istotnych w informatyce teoretycznej. Na seminarium podzielimy się rozdziałami wybranej książki (patrz niżej), które będziemy kolejno referować na cotygodniowych spotkaniach. Pierwsze dwa spotkania będą zapewne poświęcone wstępnym, przekrojowym wykładom, wprowadzającym niezbędne pojęcia i definicje, których celem będzie dostarczenie słuchaczom zgrubnej idei tego, czym właściwie zajmuje się teoria złożoności obliczeniowej. Termin spotkań zostanie ustalony do 20 marca — jeszcze możesz nań wpłynąć (oddając swój głos poniżej)!
Mimo że domyślnie każdy uczestnik powinien wygłosić referat, osoby, które będą chciały tylko słuchać są również mile widzane. Zachęcamy też zainteresowanych studentów młodszych lat — w razie potrzeby przygotujemy 1-2 nadprogramowe wykłady przekazujące niezbędne podstawy.
Organizacja
Wszystkich zainteresowanych proszę, by poprzez komentarz (na dole tej strony)
- zgłosili chęć udziału w seminarium,
- określili, którą z poniższych książek byliby bardziej zainteresowani,
- oszacowali, ile już wiedzą z teorii złożoności (np. na podstawie spisu treści tych książek),
- zgłosili, czy są zainteresowani zaliczaniem tego seminarium na ocenę
oraz aby zagłosowali w sprawie terminu w poniższej tabelce.
Dowolne pytania i uwagi również piszcie w komentarzach.
Książka
Proponuję jedną z następujących książek (posortowane rosnąco względem mojej subiektywnej oceny stopnia trudności)
- Dexter Kozen, "Theory of Computation" — bardzo klasyczna i solidna, dobrze napisana, miejscami nieco przestarzała.
- Boaz Barak, Sanjeev Arora, "Computational Complexity: A Modern Approach" — nowsza, zawiera więcej świeżych wyników i nieco szerszy przekrój przez dyscyplinę (w sensie: przedstawia więcej różnych zagadnień i pod-dziedzin teorii złożoności niż poprzednia książka)
- Lane A. Hemaspaandra, Mitsunori Ogihara. "Complexity Theory Companion" — trudna, bez żadnych wstępów, wyjaśnień, powtórek definicji, zakłada dość dużą wiedzę wstępną. Poza tym bardzo ciekawa, zajmuje się bardziej technikami uzyskiwania wyników niż samymi wynikami, i skierowana jest raczej do naukowców niż studentów. Doskonała, jeśli zbiorą się same osoby bardzo zainteresowane i ze wstępną wiedzą, w przeciwnym przypadku — raczej za trudna.
Zachęcam Was do przejrzenia spisów treści i przykładowych rozdziałów tych książek w celu dokonania świadomego wyboru. Uwaga: jeśli wybierzemy Kozena, to pewnie będziemy brali po 2 rozdziały na osobę (bo rozdziały w tej książce mają średnio 3 strony).
Zaliczenie
Jeśli zbierze się dostatecznie duża liczba osób zainteresowanych, być może uda się załatwić możliwość zaliczania tego seminarium na ocenę (lub za zwolnienie z obowiązku zaliczania jakiegoś przedmiotu monograficznego) — oczywiście wtedy musielibyśmy zdawać jakiś egzamin. Być może udałoby mi się namówić prof. Diksa lub prof. Niwińskiego do przeprowadzenia egzaminu (pewnie ustnego), ale musiałabym wiedzieć, że co najmniej kilka osób jest zainteresowanych zaliczaniem tego seminarium.
Termin
Jeśli jesteś zainteresowany/a uczestnictwem w seminarium, dodaj 1 do liczby w każdej komórce odpowiadającej terminowi, który Ci NIE pasuje. Możesz też dodać dowolne $\alpha \in [0, 1]$, możliwie dokładnie oddające stopień Twojej niechęci do danego terminu.
Pn | Wt | Śr | Cz | Pt | |
---|---|---|---|---|---|
8:30-10:00 | $2{3 \over 4}$ | 0 | 1 | 1 | 2 |
10:15-11:45 | 1 | 1 | 3 | 2 | $2{3 \over 4}$ |
12:15-13:45 | 1 | 2 | 2 | 1 | 2 |
14:15-15:45 | $2{1\over 2}$ | 1 | $1{1 \over 4}$ | 2 | 0 |
16:15-17:45 | 2 | ${3\over 4}$ | 0 | 2 | 1 |
18:15-19:45 | 0 | 0 | 0 | 0 | 1 |
? W roku 06/07 była "Złożoność obliczeniowa", w latach 07/08 i 08/09 "Teoria złożoności". Ciężko to uznać za "bardzo rzadko".
Poza tym, głębokiego przedmiotu monograficznego poświęconego teorii złożoności, w tym współczesnym wynikom, u nas nie ma, bo po prostu nikt się tym nie zajmuje badawczo (jedynie Niwiński ma z tym jakiś związek, ale on też nie zajmuje się stricte złożonością obliczeniową).
MK
Umknęła mi edycja z 07/08 - poprawię tekst na "w tym roku nie jest oferowany" :)
Mi pasuje jedynie w poniedziałki 14-16, czwartki: 16-18 i piątki 14-16. Resztę czasu zajęcia mam - nie wpisałem się w tabelkę, nie chciałbym żeby został ustalony termin ze względu na mnie, podczas gdy okaże się, że i tak nie będę chodził. Zresztą pojawiłbym tylko mnóóóstwo jedynek w tabelce, i zafałszowałbym cały wynik.
Mi pasuje:
poniedziałek 12:15 bądź 16:15
Wtorek 12:15 bądź 14:15
Środa 10:15
Czwartek 12:15
Piątek - cały dzień od 10:15 wzwyż, ale niechętnie, bo czasem mnie nie ma w piątek.
Tak samo jak post wyżej nie wpisałem się w tabelkę, gdyż nie chcę, aby termin został ustalony ze względu na mnie, gdyż wiedzę z teorii złożoności patrząc po spisie treści książek mam prawie zerową (jestem studentem pierwszego roku). Z tego względu jestem zainteresowany pierwszą bądź drugą książką (chętniej drugą). Co do zaliczenia to jestem za.
Mi pasuje pon, wto, śro, czw 12:15. Podobnie jak przedmówcom nie chce mi się wpisywać do tabelki. Jestem za zaliczeniem.
To ja może też nie będę zapełniał ponad połowy tabelki jedynkami.
Pasują mi pon, wt, czw między 16 a 20 , piątek 14-16 (i mniej chętnie później) oraz środa 8:30.
Wygląda na to, że najlepszym terminem będzie piątek, 14-16. Zaczniemy już w tym tygodniu - w planach:
- dzielenie się rozdziałami książki + inne sprawy organizacyjne
- wstępny wykład o kilku podstawowych twierdzeniach
- konsumpcja ciasteczek