Złożoność Komunikacyjna,
studia doktoranckie zima 2005, kod: MAP9805
Terminy:
środa, godz. 9:15-11:00, sala 211, C-11
(bezpośrednio po wykładzie jest seminarium na podobne
tematy
Bieżące informacje:
- pierwsze zajęcia 5 października!
Orientacyjny program wykładu
-
- model złożoności komunikacyjnej - dla dwóch uczestników
- fundamentalne techniki
- pokrycia
- randomizacja komunikacji
- zaawansowane metody: sumy proste, modele asymetryczne...
- złożoność obliczeniowa relacji
- złożoność dla protokołów z wieloma uczestnikami
- zastosowania dla układów VLSI
- złożoność dla drzew decyzyjnych
- zagadnienia sieci boolowskich
- tradeoff dla złożoności czasowej i pamięciowej
Literatura podstawowa:
Wymagania:
- Do wykładu nie są prowadzone ćwiczenia.
- Podstawą do zaliczenia przedmiotu będzie kolokwium pisemne, które odbędzie się
na końcowych zajęciach.
- Zadania na kolokwium będą testowały rozumienie materiału z wykładu
i umiejętność twórczego wykorzystania zdobytych wiadomości.
-
Wszelkie materiały pisemne będzie można przynieść na kolokwium.
Cel wykładu:
Zapoznanie z technikami szacowania złożoności problemów o
charakterze komunikacyjnym. Jest to ta część złożoności obliczeniowej, która
odgrywa bodaj najważniejszą rolę w kontekście algorytmów równoległych i
rozproszonych i odnosi się do powszechnej sytuacji "waskiego gardła" jakim jest
pojemność kanałów komunikacyjnych i problemów związanych np. z czasem
oczekiwania informację.
Dalsze plany i możliwości kontynuacji:
- myślimy o zorganizowaniu zaawansowanego wykładu dotyczącym algorytmów dla systemów rozproszonych,
- w bieżącym semestrze prowadzony jest wykład na temat programowania w systemach
rozproszonych (studia magisterskie)
Grono słuchaczy:
Jakkolwiek wykład przeznaczony jest w pierwszym rzedzie dla doktorantów,
studenci informatyki i matematyki są mile widziani. Wykład będzie stosunkowo ambitny,
ale w zasadzie nie wymaga wstępnej wiedzy oprócz dosyć ogólnej orientacji.
Wiedza w zakresie wykładu ze złożoności obliczeniowej, algorytmów rozproszonych
nie jest warunkiem wstępnym.