- Accueil
- EN
- Studying at ULB
- Find your course
- UE
-
Share this page
Theory of information coding computing and complexity
Course teacher(s)
Nicolas CERF (Coordinator) and Jérémie ROLANDECTS 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 )