Course Details for A.Y. 2015/2016
Name:
Teoria dell'Informazione / Information Theory
Basic information
Credits:
: Master Degree in Computer Science 6 CFU (b)
: Bachelor Degree in Computer Science 6 CFU (b)
Degree(s):
Bachelor Degree in Computer Science curriculum General Elective
Master Degree in Computer Science curriculum GSEEM Elective
Master Degree in Computer Science curriculum General Elective
Language:
Italian
Course Objectives
Knowledge of the fondamental concepts of Information Theory and ability to manipulate them
formally.
Deep understanding of commonsense concepts like "information", "representation",
"learning", "model". Ability to translate intuitive solutions constructed with such concepts into
concrete applications in different technological areas
Course Content
 Information and entropy: joint, conditional, and mutual.
 Relative measures, AEP and its consequences.
 Representation and codes: uniform, variable length, and adaptive.
KraftMcMillan Inequality and its consequences.
 Souce Coding and Compression algorithms
(Shannon, Arithmetic, Huffmann, Ziv and Lempel coding,
integer encoding, gamma and omega Elias coding)
 Basic concepts of channel coding, channel capacity.
 Basic concepts of modern Cryptography.
Learning Outcomes (Dublin Descriptors)
On successful completion of this course, the student should

understand and explain fundamental concepts such as entropy, mutual information, capacity,
compression, coding theorem, coding theory, coding and Cryptography;
compute entropy and mutual information of random variables;
formulate and prove The main theorems treated such as: i) AEP and its consequences,
ii) Optimality of Huffmann coding, and of arithmetical coding,
iii) the entropy is a lower bound for the expected length of a u.d block code,
iv) if P is different from NP then there exists no perfectly secret encryption scheme
with key shorter than the message.

understand and apply fundamental concepts in information theory such as probability,
entropy, information content and their interrelationships, AEP, data compression;
implement and analyze basic coding and compression algorithms;

be able to evaluate the aspects of information theory that can be applied in the real world. The student
should also be able to link the theoretical aspect of the discipline to the practical ones (such as
data compression)

explain how information theory and coding contributes to modern communications technology;
be able to describe the main results of information theory to other nonspecialist people
in the scientific community.

Be able to read and understand books and papers concerning the arguments treated in the course.
Solve advanced problems in the area.
Prerequisites and Learning Activities
Basic probability and discrete mathematics.
Ability to develop software applications.
Assessment Methods and Criteria
Written and oral.
Textbooks
 Arora, Barak, Computational Complexity: A Modern Approach, , Cambridge University press . 2009. Chapter 9: Cryptography
 Cover e Thomas, Elements of Information Theory 2006. L'ultima edizione. Il corso tratterà di argomenti selezionati dai capitoli 1,2,3,4,5,6,7 e 13
Notes
 This Module provides the students with: Knowledge of the basic concepts of Information
Theory and ability to manipulate them formally, Deep understanding of commonsense concepts like
"information", "representation", "model" and Ability to translate intuitive solutions constructed
with such concepts into concrete applications in different technological areas (in particular, the methods of data compression ), Acquisition of tools for reading the basic aspects of the literature of the discipline.
Course page updates
This course page is available (with possible updates) also for the following academic years:
To read the current information on this course, if it is still available, go to the university course catalogue .
Course information last updated on: 24 novembre 2014, 18:14