View syllabus
INFORMATION THEORY
GIOVANNA ROSONE
Academic year2022/23
CourseCOMPUTER SCIENCE
Code262AA
Credits6
PeriodSemester 1
LanguageItalian

ModulesAreaTypeHoursTeacher(s)
TEORIA DELL'INFORMAZIONEINF/01LEZIONI48
GIOVANNA ROSONE unimap
Obiettivi di apprendimento
Learning outcomes
Conoscenze

Acquisizione dei 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.

 

Knowledge

Theoretical foundations of information theory and of methods and tecniques for coding of data sources.

Modalità di verifica delle conoscenze

Esame orale

Assessment criteria of knowledge

oral exam

Modalità di verifica delle capacità

Prova orale preceduta da uno scritto/progetto da svolgersi in aula o a casa.

Assessment criteria of skills

Oral exam preceded by a written / project to be carried out in the classroom or at home.

Prerequisiti (conoscenze iniziali)

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.

Prerequisites

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

Indicazioni metodologiche

Lezioni frontali

Attività di apprendimento:

  • frequenza delle lezioni
  • partecipazione alle discussioni in aula
  • studio individuale e di gruppo

Frequenza: fortemente consigliata

Metodo di insegnamento:

  • Lezioni frontali con slide
Teaching methods

Frontal lessons

Learning activities:

attendance of lessons
participation in classroom discussions
individual and group study
Frequency: strongly recommended

Teaching method:

Frontal lessons with slides

Programma (contenuti dell'insegnamento)

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, LZ87, 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.

Syllabus

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, LZ87, 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.

Bibliografia e materiale didattico
  • Appunti di Teoria dell’Informazione , Pietro Piram e Francesco Romani Versione 2.5, Gennaio 2007
  • Slide del corso

Testi di riferimento

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

Bibliography

- Appunti di teoria dell'informazione, by P. Piram and F. Romani

- Copy of slides

All the material is in italian language.

 

Reference textbooks:

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

Indicazioni per non frequentanti

Nessuna regola particolare

Non-attending students info

No special rules

Modalità d'esame

Esame orale con un'eventuale pre-test da svolgersi in aula o a casa

Assessment methods

Oral exam with a possible pre-test to be held in the classroom or at home

Updated: 07/12/2022 19:09