UE Fundamental Computer Science

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