Teoria complexității algoritmice
Salt la navigare Salt la căutare
Teoria complexității algoritmice sau teoria algoritmică a complexității se ocupă cu studiul complexității descriptive a algoritmilor și nu a resurselor de calcul ( memoria ocupată și timpul de calcul) necesare pentru executarea lor.
Prin urmare, nu trebuie confundat cu teoria complexității de calcul .
Teoria complexității algoritmice a fost dezvoltată în principal de Kolmogorov , Chaitin și Solomonoff , din acest motiv este cunoscută și sub denumirea de „teoria KCS” din inițialele celor trei oameni de știință.
Bibliografie
Articolele istorice ale celor trei autori sunt:
- RJ Solomonoff, O teorie formală a inferenței inductive. Informații și control, 7: 1-22 și 224-254, 1964.
- ANKolmogorov. Trei abordări ale definiției cantitative a informațiilor. Problemele transmiterii informațiilor, 1: 1-17, 1965.
- GJChaitin. Cu privire la lungimea programelor pentru calculul secvențelor binare finite. Jurnalul Asociației pentru Mașini pentru Calculatoare, 13: 547-569, 1966.
Un text modern este după cum urmează:
- Ming Li și Paul Vitányi, Introducere în complexitatea Kolmogorov și aplicațiile sale (ediția a II-a), Springer, 1997. ISBN 0-387-94868-6
In italiana:
- Chaitin Gregory J., În căutarea Omega, Adelphi, 2007, ISBN 9788845922053
- Chaitin Gregory J., Teoria algoritmică a complexității, Giappichelli, 2006, ISBN 9788834863985
Elemente conexe
linkuri externe
- Site dedicat lui Kolmogorov , pe kolmogorov.com . Adus la 25 octombrie 2007 (arhivat din original la 15 ianuarie 2005) .
- Site-ul lui Chaitin , pe cs.umaine.edu . Adus la 25 octombrie 2007 (arhivat din original la 15 februarie 2015) .
- Site-ul Solomonoff , pe idsia.ch .
- Site-ul Schmidhuber , pe idsia.ch .