- Docente: Mirko Degli Esposti
- Crediti formativi: 6
- SSD: MAT/07
- Lingua di insegnamento: Italiano
- Moduli: Mirko Degli Esposti (Modulo 1) Giampaolo Cristadoro (Modulo 2)
- Modalità didattica: Convenzionale - Lezioni in presenza (Modulo 1) Convenzionale - Lezioni in presenza (Modulo 2)
- Campus: Bologna
- Corso: Laurea Magistrale in Matematica (cod. 8208)
Conoscenze e abilità da conseguire
Al termine del corso, lo studente: - possiede nozioni approfondite di teoria dell'informazione e della complessità algoritmica nei loro principali aspetti applicativi; - è in grado di condurre autonomamente l'approfondimento anche computazionale, delle tematiche sopra citate.
Contenuti
Caos, Complessità ed Informazione: saranno passati in
rassegna alcuni risultati fondamentali all'intersezione tra la
teoria dei sistemi dinamici, la teoria dell'informazione e la
teoria della complessità. Si introdurranno diversi modelli
matematici per dati testuali e si affronteranno alcune problemi
applicativi, quali: l'attribuzione d'autore, la ricerca automatica
del plagio, l'estrazione di parole importanti e l'estrazione di
informazione da dati non strutturati.
Piu' dettagliatamente:
- Concetti base di probabilità e di Teoria
dell'Informazione: spazi di sequenze simboliche,
distribuzioni di probabilità su spazi di sequenze simboliche,
catene di Markov su alfabeti finiti e cenni di teoria del coding
- Entropia, Entropia Relativa e la Mutua informazione:definizioni e proprietà fondamentali, relazioni tra l'entropia e la mutua informazione, diseguaglianza di Jensen e alcune particolari conseguenze.
- Dati Testuali: frequenza delle parole, legge di Zipf e principio del minimo sforzo. Modelli matematici per la generazione di testi artificiali ed emergenza del contesto. Modello di Simons, sue generalizaizoin e la legge di Heap sulla creazione di nuove parole nei linguaggi umani. La legge di Zipf è veramente rilevante ? Eventuale introduzione e uso del software Pyton per sperimentazioni dirette con corpus testuali.
- Lunghe correlazioni in dati testuali: sequenze di caratteri, random walks e diffusione anomale. Proprietà frattali delle sequenze di parole. Burstiness ed algoritmi automatici per l'estrazione delle parole importanti.
-il Teorema dell'equipartizione asintotica: definizione, dimostrazione ed interpretazione. Conseguenze del teorema: la compressione dati e gli insiemi tipici
- La compressione dei dati: esempi di codici, la diseguaglianza fdi Kraft, codici ottimali e stime, il codice di Huffman, codici aritmetici. gli zippatori, il teorema di Lempel-Zibv e il teorema di Mehrav-Ziv. Approssimare l'entropia e l'entropia relativa attraverso i compressori. Applicazioni ai dati testuali: stima dell'entropia di corpus letterari, gerarchie di significato ed estrazioni automatiche di proprietà semantiche
- L'attribuzione d'Autore (authorship attribution): storia dell'authorship attribuito, metodi entropici per l'attribuzione d'autore. Alcuni casi espliciti.
Testi/Bibliografia
1. Cover, T. M. & Thomas, J. A. "Elements of Information Theory". (2006).
2. Zanette, D. H. "Statistical Patterns in Written Language.”
Metodi didattici
- lezioni frontali - python in laboratorio
Modalità di verifica e valutazione dell'apprendimento
La verifica dell'apprendimento avviene attraverso il solo esame finale, che accerta l'acquisizione delle conoscenze e delle abilità attese tramite lo svolgimento di una prova sperimentale definita durante il corso, seguita da una prova orale concentrata sulla discussione della prova sperimentale. La prova è finalizzata a verificare le conoscenze sugli argomenti matematici trattati, quali i processi stocastici, entropia, entropia relativa, mutua informazione e la teoria dei codici, ma anche a verificare, seguendo gli esempi introdotti durante il corso, le competenze nell'implementazione di specifiche applicazioni allo studio del linguaggio e al trattamento di materiale testuale.
Orario di ricevimento
Consulta il sito web di Mirko Degli Esposti
Consulta il sito web di Giampaolo Cristadoro