Stocasticità e incomprimibilità algoritmica

Wehrstedt, Luca (2014) Stocasticità e incomprimibilità algoritmica. [Laurea], Università di Bologna, Corso di Studio in Matematica [L-DM270]
Documenti full-text disponibili:
[img]
Anteprima
Documento PDF
Download (291kB) | Anteprima

Abstract

Partiamo dal lavoro di Kolmogorov per definire una misura della quantità di informazione contenuta in una stringa tramite un approccio computazionale: la complessità di una stringa è la lunghezza del più corto programma capace di produrla. Vediamo poi gli sviluppi moderni di questa teoria, in particolare i contributi di Chaitin, e notiamo subito i forti legami con la teoria della probabilità e con l'entropia di Shannon. Successivamente proponiamo di identificare le stringhe casuali (nel senso intuitivo) con quelle algoritmicamente incomprimibili, seguendo l'idea che minore comprimibilità significhi minore regolarità e dunque maggiore casualità. Infine vediamo che, in effetti, le stringhe incomprimibili soddisfano tutte le proprietà stocastiche effettivamente verificabili, cioè le proprietà che la teoria della probabilità attribuisce a successioni di variabili aleatorie indipendenti e identicamente distribuite. Facciamo ciò in maniera generale utilizzando la notevole teoria di Martin-Löf e poi vediamo in dettaglio l'aspetto della normalità di Borel.

Abstract
Tipologia del documento
Tesi di laurea (Laurea)
Autore della tesi
Wehrstedt, Luca
Relatore della tesi
Scuola
Corso di studio
Ordinamento Cds
DM270
Parole chiave
complessità di Kolmogorov complessità di Chaitin probabilità algoritmica incomprimibilità algoritmica stocasticità test di Martin-Löf normalità di Borel
Data di discussione della Tesi
26 Settembre 2014
URI

Altri metadati

Statistica sui download

Gestione del documento: Visualizza il documento

^