 | Study programme 2020-2021 | Français | |
 | Computability and Complexity (List A) | ||
Programme component of Master's in Mathematics à la Faculty of Science |
| Students are asked to consult the ECTS course descriptions for each learning activity (AA) to know what special Covid-19 assessment methods are possibly planned for the end of Q3 |
|---|
| 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 | 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 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.
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 |