Seminario de I+D
del Departamento de Informática e Ingeniería de Sistemas
de la Universidad de Zaragoza
|
Seminario de I+D
|
|
|---|
La complejidad de Kolmogorov y sus aplicaciones
Dra. Elvira Mayordomo (DIIS, Universidad de Zaragoza)
Fecha: 2003-01-17
Hora: 12:00
Lugar: Seminario del DIIS en el Edificio Ada Byron, María de Luna 1, Zaragoza
Resumen:
La complejidad de Kolmogorov de un objeto es la longitud de la descripción más corta de
dicho objeto. Por ejemplo, si x es 111111111111111 una descripción corta sería "15
unos".
En esta charla veremos la definición y propiedades básicas de la complejidad de
Kolmogorov y sus aplicaciones como método de demostración. Se trata del método de
incompresibilidad, basado en que la mayoría de los objetos son incompresibles. Demostraremos por ejemplo cotas inferiores de tiempo y cotas inferiores de número de
estados de una autómata.
Alguna cita "gancho": "Kolmogorov Complexity Justifies Software Engineering Heuristics" - Ann Gates (1998).