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 [HT]
• Počet míst: neomezen
• Minimální obsazenost: neomezen
• 4EU+: ne
• Virtuální mobilita / počet míst pro virtuální mobilitu: 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.
• Vyučující: doc. RNDr. Antonín Kučera, CSc.
• Třída: DS, teoretická informatika
• Kategorizace předmětu: Informatika > Teoretická informatika
• Je korekvizitou pro: NTIN089

Anotace

čeština

Přednáška pokrývá základy algoritmické náhodnosti a různých přístupů k jejímu studiu.

Poslední úprava: T_KTI (29.04.2015)

angličtina

Algorithmic randomness. Concepts of Kolmogorov complexity, various variants. Algorithmic randomness based on measure theory. A connection to recursion theory.

Poslední úprava: T_KTI (29.04.2015)

Cíl předmětu

čeština

Naučit základy algoritmické náhodnosti

Poslední úprava: Kučera Antonín, doc. RNDr., CSc. (02.11.2019)

angličtina

To learn fundamentals of algorithmic randomness

Poslední úprava: Kučera Antonín, doc. RNDr., CSc. (02.11.2019)

Podmínky zakončení předmětu

čeština

Ústní zkouška

Poslední úprava: Kučera Antonín, doc. RNDr., CSc. (07.06.2019)

angličtina

Oral examination

Poslední úprava: Kučera Antonín, doc. RNDr., CSc. (07.06.2019)

Literatura

čeština

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

Poslední úprava: T_KTI (29.04.2015)

Požadavky ke zkoušce

čeština

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.

Poslední úprava: Kučera Antonín, doc. RNDr., CSc. (09.10.2017)

angličtina

The course is finished by an oral examination.

Requirements at the oral examination correspond to the syllabus of the subject.

Poslední úprava: Kučera Antonín, doc. RNDr., CSc. (09.10.2017)

Sylabus

čeština

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

Poslední úprava: T_KTI (29.04.2015)

angličtina

Typicalness - measure theory, martingales

• Calibration of notion "sets of measure zero"

• Martin-Löf tests, Schnorr tests and their modifications

• Universal Martin-Löf test

• Basic properties of ML-random sets

• Relativization of Martin-Löf randomness, van Lambalgen theorem

• Martingales, randomness defined by various classes of martingales

Incompressibility - Kolmogorov complexity

• Plain and prefix-free Kolmogorov complexity

• Chaitin-randomness, equivalence of Martin-Löf randomness and Chaitin randomness

• Halting probability, Omega-number

• Algorithmic weakness, K-trivial sets

Poslední úprava: T_KTI (30.04.2015)

Vstupní požadavky

Znalosti na úrovni přednášky Rekurze

Poslední úprava: T_KTI (29.04.2015)