UE Fundamental Computer Science

User information

Please note that you are curently looking at the ongoing Academic Programs. Applications are now closed for this academic year (2020-2021) for licences, professional licences, masters, DUT and regulated health training. If you are interested for an application in 2021-2022, please click on this link for the appropriate Academic Programs.

Degrees incorporating this pedagocial element :


This module introduces the fundamental aspects of computer science and particularly focuses on the notions of computability and complexity. Regarding computability theory, it presents the basic formal model to reason on the notion of computation, i.e., the Turing machine and its variants. Based on this computational model, the notions of decidable and semi-decidable languages will be defined, while the existence of languages which are undecidable will be shown. Regarding complexity theory, it presents the main classes of time complexity such as P, NP, as well as the notion of NP-completeness. Several problems in the domains of propositional logic, graphs and scheduling are studied with respect to their time complexity by proposing either polynomial-time algorithms to solve them efficiently or polynomial-time reductions to prove their hardness.

Course opened in 2018/2019


[1] Harry R. Lewis and Christos H. Papadimitriou, Elements of the Theory of Computation , Prentice-Hall
[2] Mickael Sipser, Introduction to the Theory of Computation, Thomson Course Technology