Algoritmisk kompleksitetsteori
Teorien om algoritmisk kompleksitet eller algoritmisk teori om kompleksitet omhandler studiet av den beskrivende kompleksiteten til algoritmer og ikke av beregningsressursene ( opptatt
minne og datatid) som er nødvendige for å utføre dem.
Derfor bør det ikke forveksles med teorien om beregningskompleksitet .
Den algoritmiske kompleksitetsteorien ble utviklet hovedsakelig av Kolmogorov , Chaitin og Solomonoff , av denne grunn er den også kjent som "KCS-teori" fra initialene til de tre forskerne.
Bibliografi
De historiske artiklene til de tre forfatterne er:
- RJ Solomonoff, En formell teori om induktiv inferens. Informasjon og kontroll, 7: 1-22 og 224-254, 1964.
- ANKolmogorov. Tre tilnærminger til den kvantitative definisjonen av informasjon. Problemer med informasjonsoverføring, 1: 1-17, 1965.
- GJChaitin. Om lengden på programmer for å beregne endelige binære sekvenser. Journal of the Association for Computer Machinery, 13: 547-569, 1966.
En moderne tekst er som følger:
- Ming Li og Paul Vitányi, An introduction to Kolmogorov complexity and its applications (2nd ed.), Springer, 1997. ISBN 0-387-94868-6
På italiensk:
- Chaitin Gregory J., In Search of Omega, Adelphi, 2007, ISBN 9788845922053
- Chaitin Gregory J., Algorithmic Theory of Complexity, Giappichelli, 2006, ISBN 9788834863985
Relaterte elementer
Eksterne lenker