Fiche Module
FISE
STI
Sécurité et Technologies Informatiques
Unité d'Enseignement :
Semestre : 8
Crédits ECTS : 6
EA Sécurité Fondamentale
Elément Constitutif :
Coefficient : 1
Calculabilité, complexité, Résolution de problèmes
Tronc Commun
Volume horaire : 21:20
| Type | Nombre | Durée |
|---|---|---|
| Cours | 8 | 01:20 |
| TD | 8 | 01:20 |
Evaluations : 1
| Type | Coefficient |
|---|---|
| Contrôle Continu | 0.5 |
| Examen Final | 0.5 |
Enseignants : 2
| Enseignant | Type |
|---|---|
| Berthome Pascal | Responsable |
| Berthome Pascal | Intervenant |
Pré-requis :
| UE | Semestre | Module |
|---|---|---|
| Principes de la programmation | 5 | Algorithmique et Complexité |
| Principes de la programmation | 5 | Logique |
| Principes de la programmation | 5 | Théorie des Langages |
| Développement et Mathématiques pour l'ingénieur | 6 | Modélisation et Théorie des graphes |
Le programme se décline en plusieurs aspects
Partie I : calculabilité & Complexité
- Thèse de Church-Turing,
- Modèles de calcul :
- Machines de Turing
- Machines à registres
- 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),
Partie II : Résolution exacte de problèmes
Ce cours décrit les grands principes de la programmation par contraintes et permet de comprendre le fonctionnement général d'un moteur d'inférence.
- 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 :
| Ref. | 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 |