Wyklad Zlozonosc komunikacyjna, Miroslaw Kutylowski

Złożoność Komunikacyjna,

studia doktoranckie zima 2005, kod: MAP9805

Mirosław Kutyłowski

Instytut Matematyki i Informatyki, Wydział Podstawowych Problemów Techniki, Politechnika Wrocławska

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:

Communication Complexity, Eyal Kushilevitz, Noam Nisan, Cambridge University Press, ISBN 0-521-56067-5, informacje autora o książce
artykuł przeglądowy Eyala Kushilevitza

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.