 | Study programme 2025-2026 | Français | |
 | Computability and Complexity (List A) | ||
Programme component of Master's in Mathematics (MONS) (day schedule) à la Faculty of Science |
| Code | Type | Head of UE | Department’s contact details | Teacher(s) |
|---|---|---|---|---|
| US-M1-SCMATH-013-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 | 24 | 24 | 0 | 0 | 0 | 6 | 6.00 | 2nd term |
| AA Code | Teaching Activity (AA) | HT(*) | HTPE(*) | HTPS(*) | HR(*) | HD(*) | Term | Weighting |
|---|---|---|---|---|---|---|---|---|
| S-INFO-023 | Computability and Complexity | 24 | 24 | 0 | 0 | 0 | Q2 | 100.00% |
| Programme component |
|---|
Objectives of Programme's Learning Outcomes
- Have integrated and elaborate mathematical knowledge.
- Mobilise the Bachelor's course in mathematics to address complex issues and have profound mathematical expertise to complement the knowledge developed in the Bachelor's course.
- Use prior knowledge to independently learn high-level mathematics.
- Read research articles in at least one discipline of mathematics.
- Apply innovative methods to solve an unprecedented problem in mathematics or within its applications.
- Mobilise knowledge, and research and analyse various information sources to propose innovative solutions targeted unprecedented issues.
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, PSPACE-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 2 Assessment - type
| AA | Type(s) and mode(s) of Q2 assessment |
|---|---|
| S-INFO-023 |
|
Term 2 Assessment - comments
| AA | Term 2 Assessment - comments |
|---|---|
| S-INFO-023 | Written exam 100% |
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 exam 100% |