PředmětyPředměty(verze: 901)
Předmět, akademický rok 2022/2023
  
Algoritmická náhodnost - NTIN088
Anglický název: Algorithmic Randomness
Zajišťuje: Katedra teoretické informatiky a matematické logiky (32-KTIML)
Fakulta: Matematicko-fyzikální fakulta
Platnost: od 2019
Semestr: letní
E-Kredity: 3
Rozsah, examinace: letní s.:2/0 Zk [hodiny/týden]
Počet míst: neomezen
Minimální obsazenost: neomezen
Virtuální mobilita / počet míst: ne
Stav předmětu: vyučován
Jazyk výuky: čeština, angličtina
Způsob výuky: prezenční
Garant: doc. RNDr. Antonín Kučera, CSc.
Třída: DS, teoretická informatika
Kategorizace předmětu: Informatika > Teoretická informatika
Je korekvizitou pro: NTIN089
Výsledky anket   Termíny zkoušek   Rozvrh   Nástěnka   
Anotace -
Poslední úprava: T_KTI (29.04.2015)
Přednáška pokrývá základy algoritmické náhodnosti a různých přístupů k jejímu studiu.
Cíl předmětu -
Poslední úprava: doc. RNDr. Antonín Kučera, CSc. (02.11.2019)

Naučit základy algoritmické náhodnosti

Podmínky zakončení předmětu -
Poslední úprava: doc. RNDr. Antonín Kučera, CSc. (07.06.2019)

Ústní zkouška

Literatura -
Poslední úprava: T_KTI (29.04.2015)

Nies, Computability and randomness, Oxford University Press, 2009

R. Downey, D. Hirschfeldt, Algorithmic randomness and complexity, Springer, 2010

Ming Li, Paul Vitanyi, An Introduction to Kolmogorov Complexity and Its Applications, 3rd edition, Springer, 2008

Požadavky ke zkoušce -
Poslední úprava: doc. RNDr. Antonín Kučera, CSc. (09.10.2017)

Zkouška sestává z ústní části. Známka ze zkoušky odpovídá hodnocení ústní části.

Požadavky u ústní zkoušky odpovídají sylabu předmětu v rozsahu, který byl prezentován na přednášce.

Sylabus -
Poslední úprava: T_KTI (29.04.2015)

Typičnost - teorie míry, martingaly

  • Kalibrace pojmu množina míry nula
  • Martin-Löf testy, Schnorr testy a jejich modifikace
  • Univerzální Martin-Löf test
  • Základní vlastnosti ML-náhodných množin
  • Relativizace Martin-Löf náhodnosti, van-Lambalgenova věta
  • Martingaly, náhodnost definovaná pomocí různých tříd martingalů

Chaotičnost (incompressibilty) - Kolmogorovská složitost

  • Obyčejná a prefix-free varianta Kolmogorovské složitosti,
  • Chaitin-náhodnost, ekvivalence Martin-Löf náhodnosti a Chaitin náhodnosti
  • Halting probability, Omega-number
  • Algoritmická slabost, K-triviální množiny

Vstupní požadavky
Poslední úprava: T_KTI (29.04.2015)

Znalosti na úrovni přednášky Rekurze

 
Univerzita Karlova | Informační systém UK