 | Study programme 2023-2024 | Français | |
 | Computability and Complexity | ||
Programme component of Master's in Computer Science (MONS) (day schedule) à 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.
UE Content: description and pedagogical relevance
Automata, Turing machines, decidable problems, recursively enumerable problems, complexity classes, NP-completeness.
Prior Experience
A course on algorithms and data structures
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 Learning Resources/Tools
| AA | Required Learning Resources/Tools |
|---|---|
| S-INFO-023 | Not applicable |
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 |
Term 1 Assessment - type
| AA | Type(s) and mode(s) of Q1 assessment |
|---|---|
| S-INFO-023 |
|
Term 1 Assessment - comments
| AA | Term 1 Assessment - comments |
|---|---|
| S-INFO-023 | Written examination 100% |
Resit Assessment - Term 1 (B1BA1) - type
| AA | Type(s) and mode(s) of Q1 resit assessment (BAB1) |
|---|---|
| S-INFO-023 |
|
Term 3 Assessment - type
| AA | Type(s) and mode(s) of Q3 assessment |
|---|---|
| S-INFO-023 |
|
Term 3 Assessment - comments
| AA | Term 3 Assessment - comments |
|---|---|
| S-INFO-023 | Written examination 100% |