Information Theory

Code:

CC4019

Acronym:

CC4019

Level:

400

Keywords
Classification	Keyword
OFICIAL	Computer Science

Instance: 2021/2022 - 1S

Active?	Yes
Web Page:	https://brunoloff.wordpress.com/teoria-da-informacao-2021/
Responsible unit:	Department of Computer Science
Course/CS Responsible:	Master in Computer Science

Cycles of Study/Courses

Acronym	No. of Students	Study Plan	Curricular Years	Credits UCN	Credits ECTS	Contact hours	Total Time
M:CC	12	Study plan since 2014/2015	1	-	6	42	162
M:ECAD	0	Study plan since 2021/2022.	2	-	6	42	162
M:ENM	3	Official Study Plan since 2013-2014	1	-	6	42	162
			2
M:ERSI	4	Official Study Plan since 2021_M:ERSI.	1	-	6	42	162
M:M	0	Plano Oficial do ano letivo 2021	2	-	6	42	162

Teaching language

Portuguese

Objectives

The goal of this course is to serve as an introduction to information theory.

Information theory is the study of what information is, and how it can be stored and transmitted.

This raises three fundamental questions:

Compression: How can we store information using the least possible amount of space?

Error-correction: How can we transmit information reliably, over an imperfect communication channel that is prone to errors?

Encryption: How can we transmit information privately over a public communication channel?

This course will deal with the first two questions. The last one is covered in the cryptography course offered by our department.

Learning outcomes and competences

• 
  The ability to reason about distributions and random variables.
  


• 
  The ability to reason about the basic concepts of information theory: entropy, mutual information, channels, etc.
  


• 
  Knowledge about the capacities and limitations of storing and sending information.
  


• 
  Knowledge about some compression methods and error-correcting codes.
  

Working method

Presencial

Pre-requirements (prior knowledge) and co-requirements (common knowledge)

Basic probability theory.

Program

• Probability theory refresher.


• Entropy and Mutual information.


• Shannon's source coding theorem.


• Compression methods: Huffman, Lempel-Ziv.


• Shannon's noisy channel coding, and its inverse.


• Error correcting codes: Hamming, LDPC.

Mandatory literature

David J. C. MacKay; Information theory, inference, and learning algorithms. ISBN: 0-521-64298-1

Complementary Bibliography

David Salomon; A Concise Introduction to Data Compression

Teaching methods and learning activities

Lectures with the theory, and problem-solving lectures.

Evaluation Type

Distributed evaluation without final exam

Assessment Components

designation	Weight (%)
Teste	60,00
Trabalho prático ou de projeto	40,00
Total:	100,00

Amount of time allocated to each course unit

designation	Time (hours)
Estudo autónomo	106,00
Frequência das aulas	56,00
Total:	162,00

Eligibility for exams

Attendance is mandatory in at least 75% of theory classes and 75% of problem classes.

Calculation formula of final grade

There will be 2 tests and two programming assigments. The tests are worth 6 points each, and the programming assignments 4 points each. The sum of your scores will be your final grade.

Examinations or Special Assignments

Internship work/project

Special assessment (TE, DA, ...)

The special season evaluation will consist of an exam and two programming assignments.

Classification improvement

The grades of any test, as well as the programming assignment, can be improved during the second exam season.

Observations