 | Study programme | Français | |
 | Computability and Complexity (List A) | ||
Programme component of Master's Degree in Mathematics à 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 | 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
- 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 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
- Written examination
Q1 UE Assessment Comments
Written examination 100%
Q2 UE Assessment Comments
Not applicable
Type of Assessment for UE in Q3
- Written examination
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é |