Oferta dydaktyczna Instytutu Informatyki

Poniższa lista przedstawia przedmioty, które są uczone w Instytucie Informatyki, niektóre z nich co roku, niektóre z mniejszą częstotliwością Każdy student Instytutu Informatyki studiuje wg indywidualnego toku studiów, wybierając (zgodnie z pewnymi zasadami) z tej listy swoje przedmioty.

Jeżeli zastanawiasz się nad studiami u nas, jeżeli chcesz wiedzieć, czy na Uniwersytecie można zostać inżynierem, jeżeli interesuje Cię 1000 zł stypendium miesięcznie - zapraszamy na naszą stronę główną

Seminarium: Złożoność komunikacyjna

Nazwa angielska (title in English): Seminar: Communication complexity
Prowadzący (lecturer): Piotr Gogol
Liczba punktów (ECTS): 4
Liczba punktów 2007 (ECTS since 2007): 3
Rodzaj (type): seminarium
Rodzaj od 2007 (type since 2007): seminarium
Liczba godzin (hours in semester):
seminarium:30
Egzamin (exam): nie
Możliwe zajęcia w języku angielskim (can be taught in English): nie
Przedmiot zostal uaktualniony na biezacy rok (updated): nie
Semestr (semester): zimowy

Wymagania (prerequisites)

Opis (description)

Złożoność komunikacyjna zajmuje się badaniem protokołów komunikacyjnych. W najprostszym modelu mamy Alicję i Boba próbujących obliczyć pewną funkcję f(x,y) (np. czy x=y ?), przy czym Alicja zna x, a Bob y. Pytanie brzmi ile najmniej bitów muszą wymienić aby się to udało. To naturalne pytanie prowadzi do całej poddziedziny złożoności obliczeniowej, gdyż istnieje wiele wariacji tego modelu np. obliczenia mogą być też niedeterministyczne lub losowe, możemy wprowadzić większą liczbę osób czy ograniczać liczbę rund komunikacji i jest oczywiście wiele ciekawych funkcji f.

Złożoność komunikacyjna jest bardzo często używana jako narzędzie, dla dowodzenia twierdzeń dla innych modeli np. struktur danych, obliczeń strumieniowych, sieci, automatów skończonych czy obwodów boolowskich. Ta motywacja dostarcza niezliczoną ilość problemów otwartych.

Aby uczestniczyć w seminarium nie jest wymagana wstępna znajomość tematu, Pierwsze kilka zajęć zostanie poświęconych na zapoznanie się z podstawowymi pojęciami i technikami przy pomocy monografu Kushilevitza i Nisana. Poza tym ostatnio ukazało się wiele prac z dziedziny, które są ciekawe i stosunkowo proste. One dostarczą nam materiału na dalszą część semestru.

Literatura (references)

Jeżeli jesteś zainteresowany studiowaniem w naszym instytucie, zapraszamy na stronę poświęconą tegorocznej rekrutacji.

Nazwa użytkownika (user name):
Hasło (password):