Study programme | Français | ||
Computability and Complexity | |||
Programme component of Master's Degree in Computer Science à la Faculty of Science |
Code | Type | Head of UE | Department’s contact details | Teacher(s) |
---|---|---|---|---|
US-M1-INFO60-004-M | Compulsory UE | BRUYERE Véronique | S829 - Informatique théorique |
|
Language of instruction | Language of assessment | HT(*) | HTPE(*) | HTPS(*) | HR(*) | HD(*) | Credits | Weighting | Term |
---|---|---|---|---|---|---|---|---|---|
| Français | 30 | 30 | 0 | 0 | 0 | 6.00 | 100.00 |
AA Code | Teaching Activity (AA) | HT(*) | HTPE(*) | HTPS(*) | HR(*) | HD(*) | Term | Weighting |
---|---|---|---|---|---|---|---|---|
S-INFO-023 | Computability and Complexity | 30 | 30 | 0 | 0 | 0 | Q1 | 100.00% |
Unité d'enseignement |
---|
Objectives of Programme's Learning Outcomes
Learning Outcomes of UE
To understand the basic notions of calculabiilty and complexity theory. To be able to prove that some problems are either undecidable, or recursively enumerable, or decidable. To be able to prove that some problems are NP-complete.
Content of UE
Automata, Turing machines, undecidable problems, recursively enumerable problems, decidable problems, complexity classes, NP-completeness.
Prior Experience
A course on algorithms and data structures
Type of Assessment for UE in Q1
Q1 UE Assessment Comments
Written examination 100%
Q2 UE Assessment Comments
Not applicable
Type of Assessment for UE in Q3
Q3 UE Assessment Comments
Written examination 100%
Q1 UE Resit Assessment Comments (BAB1)
Not applicable
Type of Teaching Activity/Activities
AA | Type of Teaching Activity/Activities |
---|---|
S-INFO-023 |
|
Mode of delivery
AA | Mode of delivery |
---|---|
S-INFO-023 |
|
Required Reading
AA | |
---|---|
S-INFO-023 |
Required Learning Resources/Tools
AA | Required Learning Resources/Tools |
---|---|
S-INFO-023 | Not applicable |
Recommended Reading
AA | |
---|---|
S-INFO-023 |
Recommended Learning Resources/Tools
AA | Recommended Learning Resources/Tools |
---|---|
S-INFO-023 | Not applicable |
Other Recommended Reading
AA | Other Recommended Reading |
---|---|
S-INFO-023 | - Theoretical Computer Science, J. Hromkovic, Springer, 2004 - Introduction to the theory of computation, M. Sipser, PWS publishing company, 2005 |
Grade Deferrals of AAs from one year to the next
AA | Grade Deferrals of AAs from one year to the next |
---|---|
S-INFO-023 | Autorisé |