Fiche Module

FISE

STI

Sécurité et Technologies Informatiques

Unité d'Enseignement :

Semestre : 8
Crédits ECTS : 6

EA Sécurité Fondamentale

Code UE : S08T_SFO1

Elément Constitutif :

Coefficient : 1

Calculabilité, complexité, Résolution de problèmes

Code EC :

Tronc Commun

L'UE EA Sécurité Fondamentale : 4

Calculabilité, complexité, Résolution de problèmes
Cryptographie avancée et Informatique quantique
Modèles de sécurité et controle d'accès
Vérification formelle

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
Boiret Adrien	Responsable
Boiret Adrien	Intervenant

Lien Celene :

Lien vers ce module sur celene

Objectifs pédagogiques :

Donner quelques aspects avancés de la théorie de la calculabilité et de la complexité. Comprendre différentes techniques d’approximation de problèmes Comprendre le fonctionnement d'un solveur de contraintes et expérimenter sa mise en œuvre sur des cas pratiques.

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

Programme :

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.

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 :

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