FI:I059 Kolmogorovova složitost - Informace o předmětu

I059 Kolmogorovova složitost

Fakulta informatiky
léto 1997

Rozsah

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

Vyučující

prof. RNDr. Jozef Gruska, DrSc. (přednášející)

Garance

Kontaktní osoba: prof. RNDr. Jozef Gruska, DrSc.

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

Kolmogorovská a chaitinovská složitost objektů určují maximální míru komprese daného objektu. Na bázi takového jednoduchého a fundamentálního pojmu se podařilo rozpracovat nové a účinné přístupy k mnohým základním problémům vědy a aplikací v celé řadě oblastí i mimo informatiku: náhodnost, (algoritmická) pravděpodobnost, informace, induktivní vyvozování, tvorba teorií, limitace formálních systémů, aplikace ve fyzice, ...
Základní pojmy a výsledky.
Náhodnost konečných a nekonečných řetězců.
Algoritmická teorie informace.
Algoritmická pravděpodobnost.
Induktivní vyvozování.
Časově a pamětově ohraničená kolmogorovská složitost.
Metoda nekompresovatelnosti.
Limity formálních systémů.
Číslo moudrosti
Aplikace kolmogorovské složitosti mimo informatiku.