Study programme 2020-2021Franç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

CodeTypeHead of UE Department’s
contact details
Teacher(s)
US-M1-SCMATH-013-MOptional UEBRUYERE VéroniqueS829 - Informatique théorique
  • BRUYERE Véronique

Language
of instruction
Language
of assessment
HT(*) HTPE(*) HTPS(*) HR(*) HD(*) CreditsWeighting Term
  • Français
Français303000066.001st term

AA CodeTeaching Activity (AA) HT(*) HTPE(*) HTPS(*) HR(*) HD(*) Term Weighting
S-INFO-023Computability and Complexity3030000Q1100.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

AAType of Teaching Activity/Activities
S-INFO-023
  • Cours magistraux
  • Exercices dirigés

Mode of delivery

AAMode of delivery
S-INFO-023
  • Face to face

Required Reading

AA
S-INFO-023

Required Learning Resources/Tools

AARequired Learning Resources/Tools
S-INFO-023Not applicable

Recommended Reading

AA
S-INFO-023

Recommended Learning Resources/Tools

AARecommended Learning Resources/Tools
S-INFO-023Not applicable

Other Recommended Reading

AAOther 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

AAGrade Deferrals of AAs from one year to the next
S-INFO-023Authorized
(*) HT : Hours of theory - HTPE : Hours of in-class exercices - HTPS : hours of practical work - HD : HMiscellaneous time - HR : Hours of remedial classes. - Per. (Period), Y=Year, Q1=1st term et Q2=2nd term
Date de génération : 09/07/2021
20, place du Parc, B7000 Mons - Belgique
Tél: +32 (0)65 373111
Courriel: info.mons@umons.ac.be