Kompresija entropije : magistrsko delo

Trojer, Klarisa (author), Fijavž, Gašper (mentor)

Kompresija entropije je tehnika dokazovanja, ki pokaže, da se nek naključnostni algoritem zaustavi v končnem času. V delu predstavimo algoritem, ki brezizgubno stisne nek naključen vhod v niz zapisov zgodovine po posameznih korakih poteka algoritma. S tem pristopom lahko zagotovimo ustavitev algoritma, če se število bitov entropije, ki so prebrani iz naključnega vhoda, veča hitreje kot število bitov informacij, ki so shranjeni v našem zapisu zgodovine. V delu najprej definiramo nekaj osnovnih konceptov iz teorije informacij in predstavimo pojem izračunljivih problemov. Pokažemo, da Kolmogorova kompleksnost ni izračunljiva. Nato predstavimo in dokažemo Lovaszovo lokalno lemo ter jo uporabimo za dokaz, da je podrazred izračunljivega problema k-SAT pozitivno rešljiv. Isti problem nato rešimo z metodo kompresije entropije, ki za svoj vir naključnosti vzame Kolmogorov slučajni niz. Analogni pristop, resda z dodatnimi tehničnimi podrobnostmi, uporabimo na dveh problemih iz teorije grafov - na acikličnem barvanju povezav in barvanju brez ponavljanja.

• Language: Slovenian
• Keywords: kompresija entropije, teorija informacij, Kolmogorova kompleksnost, lokalna lema, k-SAT, aciklično barvanje, barvanje brez ponavljanj
• Work type: Master's thesis/paper
• Typology: 2.09 - Master's Thesis
• Organization: FMF - Faculty of Mathematics and Physics; FRI - Faculty of Computer and Information Science
• Year: 2022
• PID: 20.500.12556/RUL-141588
• UDC: 004.42
• COBISS.SI-ID: 124431363
• Publication date in RUL: 01.10.2022

Secondary language

• Language: English
• Title: Entropy compression

Abstract

Entropy compression is a proof technique used to show that some random algorithm terminates in finite time. We present an algorithm that compresses in a lossless manner a random input string into a string of history records at each step. With this algorithm, we can guarantee termination if the number of entropy bits read from the random input increases faster than the number of information bits stored in our history record. In our work we first define some necessary basic concepts from information theory and present the notion of computable problems. We show that Kolmogorov complexity of a structure is not computable. Next we present and prove the Lovasz local lemma and use it for a proof that a certain subclass of satisfiability problem k-SAT is positively solvable. The very same problem is then positively solved with the entropy compression argument which uses a Kolmogorov random structure as its probability source. An analogous approach, albeit with further technical complications, is then used to study a pair of graph theoretical problems — acyclic edge colorings and nonrepetitive colorings.

• Keywords: entropy compression, information theory, Kolmogorov complexity, local lemma, k-SAT, acyclic coloring, nonrepetative coloring