FR
EN
Calculabilité, complexité, Résolution de problèmesEA Sécurité Fondamentale (STI)
Calculabilité, complexité, Résolution de problèmes
Unité d'enseignement EA Sécurité Fondamentale · S08T_SFO1 | Code EC S08A_SF1-1
6ECTS (UE)
1Coefficient
21:20Heures
Séquencement
Objectifs pédagogiques
Donner quelques aspects avancés de la théorie de la calculabilité et de la complexité. Comprendre les notions d'indécidabilité et d'intractabilité. Comprendre la notion de réduction. Comprendre différentes techniques d’approximation de problèmes.
Pré-requis
| Module | Unité d'enseignement | Semestre |
|---|---|---|
| Algorithmique et Complexité | Principes de la programmation | S5 |
| Logique | Principes de la programmation | S5 |
| Théorie des Langages | Principes de la programmation | S5 |
| Modélisation et Théorie des graphes | Développement et Mathématiques pour l'ingénieur | S6 |
Programme
Le programme se décline en plusieurs aspects
- Machines de Turing
- Thèse de Church-Turing,
- Simulations
- Décidabilité, Indécidabilité et Réduction,
- Théorème de la Halte
- Mesure de complexité,
- La classe P (Polynomiale),
- La classe NP (Polynomiale Non Déterministe),
- NP-Complétude (Réduction polynomiale, Théorème de Cook-Levin),
- Problèmes NP-complets
Références bibliographiques
- M.R. Garey, D.S. Johnson, “Computers and Intractactability, A guide to the theory of NP-Completeness”, W. H. Freeman and Company, 1978
- Apt, Krzysztof R., "Principles of constraint programming", Cambridge University Press
Compétences
3| Réf. | Verbe | Description | Niveau |
|---|---|---|---|
| C2_1 | reconnaître | Connaître les limites de la programmation et les notions associées (calculabilité, NP-Complétude) | 1 |
| C2_1 | démontrer | Déterminer la difficulté d'un problème algorithmique | 2 |
| C2_1 | analyser | Modéliser un problème et utiliser les méthodes adéquates pour le résoudre | 3 |