Behörighetskrav

Matematik 15 poäng och datavetenskap 20 poäng inklusive Algoritmer och datastrukturer

DV2 eller motsvarande kunskaper.

Syfte

Kolmogorov Complexity är ett centralt begrepp

och ett kraftfullt verktyg för att förstå kvantitativa

egenskaper hos information båda vad gäller omvandling

och överföring. Kursens mål är att introducera

deltagarna i generell Kolmogorovkomplexitet och några

av dess avancerade tillämpningar.

Innehåll

Innehållet täcker Kolmogorov komplexitet och

algoritmisk informationsteori. Vi användar teorin

för algoritmer för att definiera komplexiteten i en enda sträng

(i motsats till stokastiska variabler som i

Shannons informationsteori) och begreppet

slumpobjekt.

Kolmogorov komplexitet: grundläggande begrepp

villkorlig komplexitet och dess egenskaper

slumpsekvenser

monoton komplexitet och andra komplexitetsmått

komplexitet och slumpmässighet

slumpsekvenser och sannolikhetsteori

Shannon entropi och Kolmogorov komplexitet

frekvensanalys av slumpmässighet

Kolmogorov komplexitet och kombinatoriska olikheter.

Undervisning

Föreläsningar och lektioner.

Examination

Obligatoriska uppgifter och ett skriftligt prov.