Logo ESI
Bannière
ESI talents

Bienvenue



Retour - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -

Syllabus TPRO
Télécharger



Crédits : 4

TPRO
Théorie de la Programmation
Programming theory

Coef : 4
VH Cours : 30.00
VH TD : 30.00
Pré-requis :
Algorithmique  Logique mathématique  Théorie des langages de programmations et applications Théorie des graphes

Ingénierie des Compétences

Familles de Compétences
  • CF4 : Concevoir, réaliser et maintenir des logiciels de qualité
Type de compétence: TEC : Technique, MET : Méthodologique, MOD : Modélisation, OPE : Opérationnel, 		Niveau de compétence:
Base Intermédiaire Avancé


Famille de Compétence Compétence Elément de Compétence Type
CF4 C4.0: Développer des programmes informatiques C40.A: Mettre en oeuvre différents paradigmes de programmation TEC
C4.A: Analyser et concevoir des algorithmes C4A.1: Etudier les structures de données et de fichiers et analyser l’efficacité des algorithmes MET
C4A.2: Etudier les classes de problèmes et les différents type de résolution de problèmes MET
C4A.3: Etudier les paradigmes de programmation et les transformations de programmes MET

Description du programme de la matière

Objectifs:

Connaître les méthodes de résolution de problèmes
Introduire les algorithmes de l’intelligence artificielle
Savoir évaluer et comparer les performances des solutions algorithmiques
Étudier les classes de complexité, la réduction des problèmes et la NP-complétude
Connaître les fondements et les théories sur lesquels repose la programmation 
Apprendre à raisonner sur les programmes 
Avoir une vue d'ensemble des paradigmes de programmation
Contenu:

I. Concepts préliminaires
1. Notation de Landau 
2. Parcours de graphes 
3. Théorie du point fixe
II. Théorie de la complexité
1. Introduction 
2. Problèmes de décision et langages
3. Modèles de calcul
4. Classes de complexité
5. Réductions polynomiales
6. NP-Complétude
III. Réduction de complexité
1. Méthode descendante (Diviser pour résoudre)
2. Méthode ascendante (Programmation dynamique)
IV. Résolution de problèmes
1. Backtracking
2. Hill-Climbing
3. Best First Search
4. Branch and Bound
5. Algorithme A*
V. Programmation impérative
1. Schémas de programmes
2. Transformations de programmes
3. Preuves formelles
VI. Programmation applicative
1. Lambda-calcul
2. Lisp et fonctions d'ordre supérieur
3. Preuves par induction
4. Interprétation des langages fonctionnels
VII. Programmation déclarative
1. Démonstration automatique de théorèmes
2. Prolog et manipulations symboliques
3. Interprétation des langages logiques
Travail Personnel:

1 Projet
Bibliographie:

Algorithms and Theory of Computation Handbook, General Concepts and
Techniques. Mikhail J. Atallah, Marina Blanton, 2d Edition, CRC Press.

Computational Complexity, A Conceptual Perspective,
Oded Goldreich, Cambridge University.

Programming Language Pragmatics,
Michael L. Scott , ELSEVIER (Morgan Kaufmann Publishers).

The Implementation of Functional Programming Languages, Simon L. Peyton
Jones, Prentice-Hall.

An introduction to logic programming through Prolog,
Michael Spivey, Prentice–Hall International.

Essentials of Logic Programming,
Christopher John Hogger, Clarendon Press.

Artificial Intelligence,
P. H. Winston, Addison-Wesley.

Artificial Intelligence, A Modern Approach,
Stuart Russell, Peter Norvig, Pearson.
- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -