| Abstrakt: | Kolmogorovská zložitosť sa ukazuje ako jednoduchý, intuitívny a veľmi silný nástroj na dokazovanie tvrdení z mnohých oblastí matematiky a informatiky.
Práca uvádza niektoré základy a terminológiu potrebnú na pochopenie problematiky. Vysvetľuje Kolmogorovskú zložitosť ako takú, čím buduje aparát na zavedenie pojmu nestlačiteľnosti, čo vyústi do tzv. metódy nestlačiteľnosti, ktorej výklad a ukážky využitia tvoria nosnú časť práce. Záverečná kapitola poskytuje podrobné dôkazy mnohých tvrdení, ktoré demonštrujú niektoré jej dôležité výsledky. Dôkazy tu uvedené pokrývajú oblasť formálnych jazykov a automatov, zložitosti algoritmov a náhodných grafov.
|
|---|