Theory of information coding computing and complexity

Information and coding theory

• Shannon entropies
• asymptotic equipartition (typical sequences)
• source coding (e.g., Huffman codes)
• channel capacity
• channel coding and error correcting codes (e.g., Hamming codes)

Computability theory

• computation models
• notions of algorithm and language
• decidable, semi-decidable and undecidable problems
• notion of reduction between problems

Complexity theory

• P and NP classes
• polynomial reduction
• NP-completeness and heuristics

Goal: to develop an understanding of information, coding, computing and complexity theories

At the end of the course, students will be able to:

• rigorously define all studied notions (including tools and related mathematical models)
• illustrate these notions through examples and/or formal proofs
• explain the use and application field of these notions
• solve fundamental problems in information theory such as computing a channel capacity or constructing source codes and error correcting codes

Cours ayant celui-ci comme co-requis

• Theory courses (all sections)
• Exercice sessions (information and coding theory only)

References, bibliography, and recommended reading

• T.M. Cover and J.A. Thomas, Elements of information theory, (John Wiley and Sons, New York, 2006)
• M. Sipser, Introduction to the theory of computation, (Cengage Learning, 2013)

Course notes

• Podcast
• Université virtuelle

Contacts

• Nicolas CERF (Nicolas.Cerf@ulb.be)
• Jérémie ROLAND (Jeremie.Roland@ulb.be)

Campus

Solbosch

Method(s) of evaluation

• Oral examination

Oral examination

Open book oral examination

Mark calculation method (including weighting of intermediary marks)

100% final exam evaluation.

Both parts of the course will be graded on a scale from 0 to 20.

The global grade is the weighted average of these two grades (the part on "Information and coding theory" counts for 60%, while the part on "Computing and complexity theory" counts for 40%), rounded to the closest half integer.

If the credits of the course are not acquired after a given evaluation session, any partial grade (for one part of the course) that is higher or equal to 10/20 will be automatically transferred to the next session. In no circumstances will a grade strictly lower than 10/20 be transferred to another session.

Language(s) of evaluation

• english
• (if applicable french )