Seminarium studenckie "Teoria złożoności"

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)

  1. Dexter Kozen, "Theory of Computation" — bardzo klasyczna i solidna, dobrze napisana, miejscami nieco przestarzała.
  2. 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)
  3. 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

Dodaj nową wypowiedź
O ile nie zaznaczono inaczej, treść tej strony objęta jest licencją Creative Commons Attribution-ShareAlike 3.0 License