Scheda programma d'esame
INFORMATION THEORY
GIOVANNA ROSONE
Academic year2023/24
CourseCOMPUTER SCIENCE
Code262AA
Credits6
PeriodSemester 1
LanguageItalian

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

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.

 

Knowledge

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.

Modalità di verifica delle conoscenze

Lo studente sarà valutato in base alla sua dimostrata capacità di discutere i principali contenuti del corso utilizzando la terminologia appropriata.

Assessment criteria of knowledge

The student will be assessed on his/her demonstrated ability to discuss the main course contents using the appropriate terminology.

Capacità

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.

Skills

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.

Modalità di verifica delle capacità

Le capacità saranno sottoposte a verifica, tramite prove in itinere e l’esame orale finale.

Assessment criteria of skills

The skills will be verified, through ongoing tests, and the final oral exam.

Comportamenti

Alla fine del corso lo studente sarà in grado di riconoscere e interpretare le principali tecniche di codifica e compressione dati.

Behaviors

At the end of the course the student will be able to recognize and interpret the main coding and data compression techniques.

Modalità di verifica dei comportamenti

Il grado di conseguimento dei comportamenti sarà osservato durante le prove in itinere e durante l'esame orale.

Assessment criteria of behaviors

The degree of attainment of the behaviours will be observed during the ongoing tests and during the oral exam.

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

Le lezioni sono erogate in presenza con l’ausilio della proiezione di diapositive.

Attività di apprendimento:

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

Frequenza: fortemente consigliata.

La lingua del corso sarà l'italiano.

Teaching methods

Lessons are delivered face-to-face with the aid of slide projections.

 

Learning activities:

  • attendance of lessons
  • participation in classroom discussions
  • individual and group study

Frequency: strongly recommended.

The course language will be Italian.

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

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

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:

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

Bibliography

- 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

Indicazioni per non frequentanti

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. 

Non-attending students info

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. 

Modalità d'esame

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

Assessment methods

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.

Altri riferimenti web

Ogni informazione sul corso è reperibile sulla piattaforma Moodle.
Per ulteriori informazioni contattare il docente via email.

Additional web pages

Every information about the course can be found on the Moodle platform.
For further information contact the teacher by email.

Updated: 31/07/2023 23:23