Programme d’études 2020-2021English
Calculabilité et complexité
Unité d’enseignement du programme de Master en sciences informatiques à la Faculté des Sciences

Les étudiants sont invités à consulter les fiches ECTS des AA pour prendre connaissance des modalités d’évaluation spéciales Covid-19 éventuellement prévues pour la fin du Q3

CodeTypeResponsable Coordonnées
du service
Enseignant(s)
US-M1-SCINFO-004-MUE optionnelleBRUYERE VéroniqueS829 - Informatique théorique
  • BRUYERE Véronique

Langue
d’enseignement
Langue
d’évaluation
HT(*) HTPE(*) HTPS(*) HR(*) HD(*) CréditsPondération Période
d’enseignement
  • Français
Français303000066.001er quadrimestre

Code(s) d’AAActivité(s) d’apprentissage (AA) HT(*) HTPE(*) HTPS(*) HR(*) HD(*) Période
d’enseignement
Pondération
S-INFO-023Calculabilité et complexité3030000Q1100.00%

Unité d'enseignement

Objectifs par rapport aux acquis d'apprentissage du programme

  • Avoir acquis des connaissances hautement spécialisées et intégrées et des compétences larges dans les diverses disciplines des sciences informatiques, qui font suite à celles relevant du niveau de bachelier en sciences informatiques
  • Gérer des projets de développement informatique d'envergure
    • -Etre capable d'appliquer, de mobiliser, d'articuler et de valoriser les connaissances et les compétences acquises en vue de contribuer à la conduite et à la réalisation d'un projet
  • Gérer des travaux de recherche, de développement ou d'innovation
    • -Rechercher de façon méthodique des informations scientifiquement valides, mener une analyse critique, proposer et argumenter des solutions éventuellement innovantes à des problématiques ciblées
  • Développer et intégrer un fort degré d'autonomie
    • -Etre capable d'acquérir seul de nouveaux savoirs

Acquis d'apprentissage UE

Avoir acquis des notions de base en calculabilité et complexité. Etre capable de montrer que certains problèmes sont décidables (ou pas), récursivement énumérables (ou pas). Etre capable de prouver que certains problèmes sont NP-complets.

Contenu de l'UE

Automates, machines de Turing, problèmes décidables, problèmes récursivement énumérables, classes de complexité, NP-complétude.

Compétences préalables

Un cours d'algorithmique et de structures de données

Types d'évaluations Q1 pour l'UE

  • Examen écrit

Commentaire sur les évaluations Q1 de l'UE

Examen écrit 100%

Types d'évaluation Q3 pour l'UE

  • Examen écrit

Commentaire sur les évaluations Q3 de l'UE

Examen écrit 100%

Types d'évaluation rattrapage BAB1 (Q1) pour l'UE

  • Néant

Commentaire sur les évaluations rattr. Q1 de l'UE

Sans objet

Types d'activités

AATypes d'activités
S-INFO-023
  • Cours magistraux
  • Exercices dirigés

Mode d'enseignement

AAMode d'enseignement
S-INFO-023
  • Face à face

Supports principaux

AA
S-INFO-023

Supports principaux non reproductibles

AASupports principaux non reproductibles
S-INFO-023Sans objet

Supports complémentaires

AA
S-INFO-023

Supports complémentaires non reproductibles

AASupport complémentaires non reproductibles
S-INFO-023Sans objet

Autres références conseillées

AAAutres références conseillées
S-INFO-023- Theoretical Computer Science, J. Hromkovic, Springer, 2004
- Introduction to the theory of computation, M. Sipser, PWS publishing company, 2005

Reports des notes d'AA d'une année à l'autre

AAReports des notes d'AA d'une année à l'autre
S-INFO-023Autorisé
(*) HT : Heures théoriques - HTPE : Heures de travaux pratiques encadrés - HTPS : Heures de travaux pratiques supervisés - HD : Heures diverses - HR : Heures de remédiation - Dans la colonne Pér. (Période), A=Année, Q1=1er quadrimestre et Q2=2e quadrimestre
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