Pseudo-willekeurige generatoren geschikt voor datacompressie
Promotie Informatica
woensdag 11 januari 12.00 uur
Datacompressie wordt veel gebruikt in het dagelijks leven, bijvoorbeeld in mobiele telefoons en muziekspelers. Met behulp van Kolmogorov-complexiteit kan het gedrag van een theoretische limiet van datacompressie bestudeerd worden - de Kolmogorov-complexiteit van een woord is de grootte van de kortste beschrijving van dat woord. Kolmogorov-complexiteit staat ver af van real world datacompressie. Om dichter bij real world datacompressie te komen, ontwikkelde men de resource-begrensde Kolmogorov-complexiteitstheorie. Troy Lee bestudeerde de vier belangrijke principes van Kolmogorov-complexiteit in de resource-begrensde variant, en keek naar de hoeveelheid resources die nodig is om die principes te laten gelden. Een van de meest interessante resultaten is dat pseudo-willekeurige generatoren ook voor datacompressie gebruikt kunnen worden.
Het onderzoek is gedeeltelijk uitgevoerd aan het Centrum voor Wiskunde en Informatica (CWI) in Amsterdam, een aan NWO gelieerd onderzoeksinstituut
T.J. Lee: Kolmogorov Complexity and Formula Size Lower Bounds. Promotor is prof. dr. H.M. Buhrman.
Universiteit van Amsterdam.
Meer informatie over de items in deze agenda kunt u krijgen bij de afdeling Persvoorlichting, tel. 020 - 525 2695, e-mail:
Universiteit van Amsterdam