Course Details for A.Y. 2018/2019
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 common-sense 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.
Kraft-McMillan 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 inter-relationships, 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 non-specialist 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 common-sense 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: 08 giugno 2017, 10:38