Název: Kolmogorovovská složitost a Shannonova informace
Překlad názvu: Kolmogorov complexity and Shannon information
Autoři: Sekerka, Michal ; Koucký, Michal (vedoucí práce) ; Šámal, Robert (oponent)
Typ dokumentu: Bakalářské práce
Rok: 2020
Jazyk: cze
Abstrakt: [cze] [eng]
V průběhu dvacátého století vznikly dvě úspěšné formalizace kvantitativního aspektu informace spojeným s komunikací zprávy: Shannonova informace a Kolmogorovovská slo- žitost. Obě zmíněné definice vyplývají ze dvou separátních odvětví matematiky. Shan- nonova informace vznikla jako aplikace elementární teorie pravděpodobnosti a statistiky. Je definovaná jako funkce v pravděpodobnosti s tím, že určuje jakýsi spodní odhad na binární kompresi. Kolmogorovovská složitost má na druhou stranu kořeny ve formální lo- gice a teorii řešitelnosti. Jedná se o délku minimálního algoritmického popisu zprávy. Je překrásným důsledkem, že za určitých podmínek tyto dvě veličiny vycházejí až na zane- dbatelnou chybu asymptoticky stejně. Moje práce má za úkol formálně zavést obě veličiny, porovnat jejich nedostatky, zaměřit se na jejich podobnosti a rozdíly a v neposlední řadě dokázat jejich zmíněný vztah. 1 There arose two successful formalisations of the quantitative aspect of information over the course of the twentieth century: Shannon information and Kolmogorov complexity. Both afore mentioned definitions are rooted in mostly separate parts of mathematics. Shannon's information came to existence as an application of the elementary theory of probability and statistics. It is defined as a function in probability, with it being a lower bound on binary compression. Kolmogorov complexity, on the other hand, springs from formal logic and theory of computability. Kolmogrov defined it as the length of a minimal algorithmic description of a message. It is a beautiful result that when certain conditions do apply then those two functions behave asymptotically equivalently. My thesis is concerned with formally defining both measures of information, comparing their drawbacks, highlighting their similarities and differences and at last but not least proving their coveted asymptotic relationship. 1
Klíčová slova: entropie; Kolmogorovovská složitost; Shannonova informace; entropy; Kolmogorov complexity; Shannon information

Instituce: Fakulty UK (VŠKP) (web)
Informace o dostupnosti dokumentu: Dostupné v digitálním repozitáři UK.
Původní záznam: http://hdl.handle.net/20.500.11956/118901

Trvalý odkaz NUŠL: http://www.nusl.cz/ntk/nusl-415419


Záznam je zařazen do těchto sbírek:
Školství > Veřejné vysoké školy > Univerzita Karlova > Fakulty UK (VŠKP)
Vysokoškolské kvalifikační práce > Bakalářské práce