I018 Výpočetní složitost II

Fakulta informatiky
léto 1996
Rozsah
0/0. 2 kr. 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
Kontaktní osoba: prof. RNDr. Ivana Černá, CSc.
Předpoklady
Předpokladem pro zápis je absolvování přednášky I005 Formální jazyky a automaty 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.
Informace učitele
http://www.fi.muni.cz/usr/cerna/i018.html
Předmět je zařazen také v obdobích léto 1997, jaro 1999, podzim 2000.