1. Accueil
  2. EN
  3. Studying at ULB
  4. Find your course
  5. UE
INFO-H422

Theory of information coding computing and complexity

academic year
2024-2025

Course teacher(s)

Nicolas CERF (Coordinator) and Jérémie ROLAND

ECTS credits

5

Language(s) of instruction

english

Course content

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

Objectives (and/or specific learning outcomes)

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

Prerequisites and Corequisites

Cours ayant celui-ci comme co-requis

Teaching methods and learning activities

  • 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

Other information

Contacts

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

Campus

Solbosch

Evaluation

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 )

Programmes