 | Programme d’études 2022-2023 | English | |
 | Calculabilité et complexité | ||
Unité d’enseignement du programme de Master en sciences informatiques (MONS) (Horaire jour) à la Faculté des Sciences |
| Code | Type | Responsable | Coordonnées du service | Enseignant(s) |
|---|---|---|---|---|
| US-M1-SCINFO-004-M | UE optionnelle | BRUYERE Véronique | S829 - Informatique théorique |
|
| Langue d’enseignement | Langue d’évaluation | HT(*) | HTPE(*) | HTPS(*) | HR(*) | HD(*) | Crédits | Pondération | Période d’enseignement |
|---|---|---|---|---|---|---|---|---|---|
| Français | 30 | 30 | 0 | 0 | 0 | 6 | 6.00 | 1er quadrimestre |
| Code(s) d’AA | Activité(s) d’apprentissage (AA) | HT(*) | HTPE(*) | HTPS(*) | HR(*) | HD(*) | Période d’enseignement | Pondération |
|---|---|---|---|---|---|---|---|---|
| S-INFO-023 | Calculabilité et complexité | 30 | 30 | 0 | 0 | 0 | Q1 | 100.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 de l'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 : descriptif et cohérence pédagogique
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'activités
| AA | Types d'activités |
|---|---|
| S-INFO-023 |
|
Mode d'enseignement
| AA | Mode d'enseignement |
|---|---|
| S-INFO-023 |
|
Supports principaux non reproductibles
| AA | Supports principaux non reproductibles |
|---|---|
| S-INFO-023 | Sans objet |
Supports complémentaires non reproductibles
| AA | Support complémentaires non reproductibles |
|---|---|
| S-INFO-023 | Sans objet |
Autres références conseillées
| AA | Autres 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
| AA | Reports des notes d'AA d'une année à l'autre |
|---|---|
| S-INFO-023 | Autorisé |
Evaluation du quadrimestre 1 (Q1) - type
| AA | Type(s) et mode(s) d'évaluation du Q1 |
|---|---|
| S-INFO-023 |
|
Evaluation du quadrimestre 1 (Q1) - commentaire
| AA | Commentaire sur l'évaluation Q1 |
|---|---|
| S-INFO-023 | Examen écrit 100% |
Evaluation de l'épreuve de rattrapage du quadrimestre 1 (Q1) pour B1BA - type
| AA | Type(s) et mode(s) d'évaluation rattrapage Q1(BAB1) |
|---|---|
| S-INFO-023 |
|
Evaluation du quadrimestre 3 (Q3) - type
| AA | Type(s) et mode(s) d'évaluation du Q3 |
|---|---|
| S-INFO-023 |
|
Evaluation du quadrimestre 3 (Q3) - commentaire
| AA | Commentaire sur l'évaluation Q3 |
|---|---|
| S-INFO-023 | Examen écrit 100% |