Degrees incorporating this pedagocial element :
Description
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.
Courses offered by :
In brief
Period : Semester 8Credits : 3
Number of hours
- Lectures (CM) : 16.5h
- Tutorials (TD) : 16.5h
Language(s) : English
Contact(s)
Alastair Abbott
