Original title: Kolmogorovovská složitost a Shannonova informace
Translated title: Kolmogorov complexity and Shannon information
Authors: Sekerka, Michal ; Koucký, Michal (advisor) ; Šámal, Robert (referee)
Document type: Bachelor's theses
Year: 2020
Language: cze
Abstract: [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
Keywords: entropy; Kolmogorov complexity; Shannon information; entropie; Kolmogorovovská složitost; Shannonova informace

Institution: Charles University Faculties (theses) (web)
Document availability information: Available in the Charles University Digital Repository.
Original record: http://hdl.handle.net/20.500.11956/118901

Permalink: http://www.nusl.cz/ntk/nusl-415419


The record appears in these collections:
Universities and colleges > Public universities > Charles University > Charles University Faculties (theses)
Academic theses (ETDs) > Bachelor's theses