Kompresija entropijeTrojer, Klarisa (Avtor) Fijavž, Gašper (Mentor) kompresija entropijeteorija informacijKolmogorova kompleksnostlokalna lemak-SATaciklično barvanjebarvanje brez ponavljanjKompresija 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.20222022-10-01 08:15:08Magistrsko delo/naloga141588UDK: 004.42VisID: 128474COBISS_ID: 124431363sl