 | Study programme 2018-2019 | 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-SCINFO-004-M | Optional 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 | 6.00 | 1st term |
| 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% |
| Programme component |
|---|
Objectives of Programme's Learning Outcomes
- Have acquired highly specialised and integrated knowledge and broad skills in the various disciplines of computer science, which come after those within the Bachelor's in computer science.
- Manage large-scale software development projects.
- Apply, mobilise, articulate and promote the knowledge and skills acquired in order to help lead and complete a project.
- Manage research, development and innovation.
- Methodically research valid scientific information, lead a critical analysis, propose and argue potentially innovative solutions to targeted problems.
- Develop and integrate a high degree of autonomy.
- Aquire new knowledge independently.
Learning Outcomes of UE
To understand the basic notions of calculabiilty and complexity theory. To be able to prove that some problems are decidable (or not), recursively enumerable (or not). To be able to prove that some problems are NP-complete.
Content of UE
Automata, Turing machines, decidable problems, recursively enumerable problems, complexity classes, NP-completeness.
Prior Experience
A course on algorithms and data structures
Type of Assessment for UE in Q1
- Written examination
Q1 UE Assessment Comments
Written examination 100%
Type of Assessment for UE in Q3
- Written examination
Q3 UE Assessment Comments
Written examination 100%
Type of Resit Assessment for UE in Q1 (BAB1)
- N/A
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 | Authorized |