FI:I018 Komunikace a komunikační složi

I018 Komunikace a komunikační složitost

Fakulta informatiky
podzim 2000

Rozsah

2/0. 2 kr. (plus ukončení). Doporučované ukončení: zk. Jiná možná ukončení: k, z.

Vyučující

prof. RNDr. Ivana Černá, CSc. (přednášející)

Garance

Předpoklady

I005 FJA I
Doporučuje se absolvování přednášky I012 Složitost.

Omezení zápisu do předmětu

Předmět je nabízen i studentům mimo mateřské obory.

Mateřské obory/plány

Osnova

Na počítač se můžeme dívat jako na třídu procesů, které spolu na různých úrovních komunikují. Komunikační složitost je matematická teorie zkoumající komunikující procesy. Často se používá i jako abstraktní model pro zkoumání jiných aspektů výpočtů. Přednáška začíná uvedením jednoduchých modelů komunikace a pokračuje až k prezentaci nejnovějších výsledků a jejich aplikacím.
Základní model komunikace dvou procesů a pojem komunikační složitosti. Metody pro získávání dolních odhadů komunikační složitosti (metoda "fooling set", metoda ranku matice, metoda pokrytí). Jednosměrná komunikační složitost.
Jiné modely komunikace. Nedeterministické a pravděpodobnostní komunikace. Komunikační složitost relací. Komunikace více procesů. Model s jiným rozdělením vstupu.
Aplikace. VLSI obvody. Rozhodovací stromy. Booleovské obvody a jejich hloubka. Časová a prostorová složitost.

Literatura

Hromkovič Juraj. Communication complexity and parallel computing. Springer, 1997. ISBN 3-540-57459.
KUSHILEVITZ, Eyal a Noam NISAN. Communication complexity. Cambridge: Cambridge University Press, 1997, xiii, 189. ISBN 0521560675. info

Metody hodnocení

Během semestru studenti samostatně řeší zadané problémy. Řešení jsou základem pro určení závěrečného hodnocení.

Informace učitele

http://www.fi.muni.cz/usr/cerna/i018.html

Další komentáře

Předmět je vyučován jednou za dva roky.
Výuka probíhá každý týden.

Předmět je zařazen také v obdobích léto 1996, léto 1997, jaro 1999.