ECTS - University of Pisa
| Modules | Area | Type | Hours | Teacher(s) | |
| TEORIA DELL'INFORMAZIONE | INF/01 | LEZIONI | 48 |
|
Lo studente avrà acquisito i fondamenti teorici della teoria dell'informazione, delle metodologie e delle tecnologie per la codifica di sorgente di segnali, delle tecnologie per la protezione dell'informazione nei confronti di errori, principali metodologie di compressione dati, con particolare riferimento alla teoria matematica della comunicazione di C. Shannon, con particolare attenzione alle nozioni di informazione e di codice.
The student will have acquired the theoretical foundations of information theory, methodologies and technologies for signal source coding, information protection technologies against errors, main data compression methodologies, with particular reference to the theory mathematics of communication by C. Shannon, with particular attention to the notions of information and code.
Lo studente sarà valutato in base alla sua dimostrata capacità di discutere i principali contenuti del corso utilizzando la terminologia appropriata.
The student will be assessed on his/her demonstrated ability to discuss the main course contents using the appropriate terminology.
Il corso si propone di dare agli studenti la consapevolezza della teoria dell'informazione ponendo attenzione alla codifica su un canale, con e senza errore, e sulla compressione dei testi.
The course aims to give students awareness of information theory by paying attention to coding on one channel, with and without error, and text compression.
Le capacità saranno sottoposte a verifica, tramite prove in itinere e l’esame orale finale.
The skills will be verified, through ongoing tests, and the final oral exam.
Alla fine del corso lo studente sarà in grado di riconoscere e interpretare le principali tecniche di codifica e compressione dati.
At the end of the course the student will be able to recognize and interpret the main coding and data compression techniques.
Il grado di conseguimento dei comportamenti sarà osservato durante le prove in itinere e durante l'esame orale.
The degree of attainment of the behaviours will be observed during the ongoing tests and during the oral exam.
Conoscenze di base di usare un linguaggio di programmazione, nozioni di base della teoria degli algoritmi e delle strutture dati, calcolo delle probabilità e algebra.
Le conoscenze necessarie saranno comunque ripetute durante il corso.
Basic knowledge of the use of a programming language, basic notions of algorithm theory and data structures, probability and algebra.
The needed knowledge will be given again during the course
Le lezioni sono erogate in presenza con l’ausilio della proiezione di diapositive.
Attività di apprendimento:
Frequenza: fortemente consigliata.
La lingua del corso sarà l'italiano.
Lessons are delivered face-to-face with the aid of slide projections.
Learning activities:
Frequency: strongly recommended.
The course language will be Italian.
Elementi di teoria dell'informazione: entropia di una sorgente, entropia relativa. Entropia congiunta e entropia condizionata.
Sorgenti con e senza memoria.
Codifica di sorgente senza perdita di informazione: Codici ottimi. Limiti sulla lunghezza delle parole di codice per i codici ottimi. Codici univocamente decifrabili. Codici univocamente decifrabili e con ritardo di decifrazione. Codici prefissi.
Diseguaglianza di Kraft-McMillan. Algoritmo di Sardinas-Patterson. Codificatori di Huffman e di Shannon-Fano-Elias. Codifica di sorgente Universale. Codificatori aritmetici. Codifica Move-To-Front.
Teoremi di Shannon. Complessità di Kolmogorov.
Codificatore di Lempel-Ziv: LZ77, LZ78, LZW.
Metodi di compressione basati su contesto. La trasformata di Burrows e Wheeler (BWT). Invertibilita' della BWT. Proprietà matematiche della BWT. Metodi di compressione e indicizzazione basati su BWT.
Codice a rivelazione o correzione di errori. Classificazione dei codici: codici a ripetizione, a blocchi, lineari, ciclici. Codici a controllo parità. Codici di Hamming. Codici convoluzionali. Algoritmo di Viterbi.
Elements of information theory: entropy of a source, relative entropy. Joint entropy and conditional entropy.
Lossless source coding: Optimal codes. Limits on codeword length for optimal codes. Uniquely decipherable codes with and without delay. Prefix codes.
Source with and without memory.
Kraft-McMillan inequality. Sardinas-Patterson algorithm. Huffman and Shannon-Fano-Elias encoders. Universal source coding. Arithmetic encoders. Move-To-Front encoder.
Shannon theorems. Kolmogorov complexity.
Lempel-Ziv encoder:: LZ77, LZ78, LZW.
Context-based compression methods. The Burrows and Wheeler transform (BWT). Invertibility of the BWT. Mathematical properties of the BWT. BWT-based compression and indexing methods.
Error Detection and correction codes. Code classification: repeating, block, linear, cyclic codes. Parity checking codes. Hamming codes. Convolutional codes. Viterbi algorithm.
Testi di riferimento:
Teoria dell'informazione, codici, cifrari. Front Cover. Francesco Fabris. Bollati Boringhieri
Cover T.M. and Thomas J.A., Elements of Information Theory, Wiley-Interscience, 2006 (per gli argomenti di teoria dell'Informazione/for topics on Information Theory) ISBN 978-0471241959
Robert Ash. Information Theory.
Sayood K., Introduction to Data Compression, Morgan Kauffman, 2017 ISBN 978-0124157965
Salomon D., Motta G. Handbook of Data Compression, Fifth Edition, Springer 2010 ISBN 978-1-84882-902-2
- Appunti di teoria dell'informazione, by P. Piram and F. Romani
- slides
The material is in italian language.
Reference textbooks:
Teoria dell'informazione, codici, cifrari. Front Cover. Francesco Fabris. Bollati Boringhieri
Cover T.M. and Thomas J.A., Elements of Information Theory, Wiley-Interscience, 2006 (per gli argomenti di teoria dell'Informazione/for topics on Information Theory) ISBN 978-0471241959
Robert Ash. Information Theory.
Sayood K., Introduction to Data Compression, Morgan Kauffman, 2017 ISBN 978-0124157965
Salomon D., Motta G. Handbook of Data Compression, Fifth Edition, Springer 2010 ISBN 978-1-84882-902-2
Le slides coprono gli argomenti che debbono essere approfonditi sui libri di testo.
Gli studenti non frequentanti sono pregati di contattare il docente per ulteriori informazioni su libri di testo, materiale didattico, programma d'esame e calendario degli esami. Le modalità degli esami sono identiche per frequentanti e non frequentanti.
The slides cover the topics that need to be explored in textbooks.
Non-attending students are requested to contact the teacher for further information about the textbooks, teaching material, exam program and calendar of exams.
The modalities of exams are identical for attending and non-attending students.
La prova d'esame si svolge in forma orale.
Sono previste due prove in itinere (con modalità da concordare con gli studenti durante il corso) che, se superate con successo, ridurranno l'esame orale finale.
Nel caso in cui si siano presentate delle lacune nelle prove in itinere, l'esame finale sarà l’opportunità per poterle recuperare.
Gli studenti non soddisfatti della propria valutazione delle prove in itinere potranno rifiutare il voto e presentarsi all’esame orale che verrà eseguito in maniera integrale
The exam is oral.
There are two progress tests which, if passed successfully, will reduce the final oral exam. Should these formative evaluations be unsatisfactory, the final exam will be the opportunity to improve on the final mark. Those students who are not satisfied with the assessment of their progress tests will be able to refuse the grade and take the complete oral exam.
Ogni informazione sul corso è reperibile sulla piattaforma Moodle.
Per ulteriori informazioni contattare il docente via email.
Every information about the course can be found on the Moodle platform.
For further information contact the teacher by email.
