Ce cours couvre trois parties distinctes. La première partie est consacrée à la conception de programmes. la seconde partie aborde un domaine très important qui est celui de la complexité des algorithmes. La troisième partie traite de la construction de programmes. Chaque partie exige un pré-requis. Dans la première partie, on commence par rappeler la O-notation et les graphes. Dans la seconde partie, les problèmes de décision et la machine de Turing. Dans la dernière partie, les systèmes formels et la théorie du point fixe.
Conception de programmes Comme pré-requis, la O-notation et les graphes sont d�abord exposées.La O-notation est une notation universelle permettant de mesurer des algorithmes dans le cas le plus défavorable. Après avoir défini mathématiquement la O-notation, on présente toute l�algèbre qui en découle permettant ainsi de faire des calculs. On donnera alors la manière de mesurer des algorithmes structurés ( sans Allera) , des algorithmes récursifs et des algorithmes non structurés (avec Allera )
La plupart des méthodes exposées utilisent des graphes ( ou des arbres ). Aussi, il est vital de les définir. Cette structure de données englobe en fin de compte toutes les structures de données dynamiques ( listes chaînées, arbres ). On s�intéressera à la représentation mémoire, aux types de parcours et à la définition d�une machine abstraite permettant de développer des algorithmes sur les graphes. Quelques algorithmes connus sont présentés comme application ( algorithme de Dijkstra pour le plus court chemin et algorithme de Floyd pour la résolution du problème du voyageur de commerce)
Diverses manières de conception d�algorithmes sont présentées par la suite : la technique �diviser pour résoudre�, la programmation dynamique, la recherche systématique de solutions avec les parcours en profondeur connus sous le terme �backtracking� ou les parcours en largeur, la recherche avec des heuristiques quand le graphe de solutions est exponentiel.
Beaucoup de problèmes bien connus sont présentés et solutionnés. On peut citer : Tour de Hanoi, Organisation d�un tournoi entre plusieurs équipes, Série mondiale, Multiplications chaînées de matrices, Problème des 8 reines, Tic-Tac-Toe, Problème des cruches d�eau, Sortie d�un labyrinthe,�
Cette partie introduit également une forme de l�intelligence artificielle. La technique du Min-Max est alors présentée montrant comment une machine peut jouer et gagner un être humain ( Jeu de dames, jeu d�échecs,..)
Plusieurs algorithmes bien connus pour la recherche guidée, avec des heuristiques, sont présentés et commentés avec des exemples . En particuliers, �Hill Climbing�, �Best First Search�, �Branch and Bound� et l�algorithme A*, le plus populaire en intelligence artificielle.
Complexité
Comme pré-requis, deux notions importantes sont d�abord exposées.
La décidabilité des problèmes consiste à résoudre le défit : "ce qui peut être fait par un ordinateur et ce qui ne peut l�être".
La machine de Turing a pour but d'étudier la décidabilité des programmes et permet donc de distinguer les problèmes possibles ( polynomiales) et non possibles (exponentielles).
L'étude de la complexité a donc pour but de quantifier la mesure d'un algorithme. En général, cette quantification se fait par les paramètres temps et espace.
La complexité a été étudié à travers un modèle de calcul. Bien qu'il en existe plusieurs, le plus utilisé est sans doute la machine de Turing.
D'une manière générale, on définit TIME(t(n)) comme étant la classe de complexité relative à l'ensemble des langages L tels que L peut être décidé en temps t(n) par une machine de Turing déterministe. NTIME(t(n)) est celle relative à l'ensemble des langages L tels que L peut être décidé en temps t(n) par une machine de Turing non déterministe.
Les classes importantes sont celles des problèmes qui peuvent être résolus en temps polynomial par une machine de Turing déterministe (Classe P) et non déterministe (Classe NP).
Une réduction permet de ramener la décidabilité d'un problème à celle d'un autre. Elle fait correspondre à une instance du problème A une instance du problème B avec même réponse et calculable en temps polynomial.
Un problème NP-complet est un problème parmi les plus difficiles de la classe NP. Il est tel que tout autre problème de la classe NP peut se réduire à lui.
Un des plus importants résultats en théorie de la complexité est celui de Stephen Cook (1971) qui montre le premier problème NP-complet ( SAT ) et dont la démonstration est basée sur la machine de Turing.
Construction de programmes
Comme pré-requis, deux notions importantes sont d�abord exposées.
La programmation non procédurale est basée sur des systèmes formels. Aussi, nous présenterons tous ses concepts : morphologie, théorie propre, principes de génération, décidabilité. Quelques systèmes formels sont présentés.
La théorie du point fixe joue un rôle très important dans cette deuxième partie du cours. Après avoir rappelé quelques notions élémentaires de mathématiques, nous définissons le concepts de treuilli sur lequel on définit la croissance et la continuité sur les fonctionnelles ( fonctions de fonctions). Vu l�importance du théorème du point fixe, il sera présenté et démontré.
La construction de programme s�intéresse à la forme des programmes. Diverses manières de programmation sont présentées et étudiées. On distingue la programmation procédurale et celle non procédurale. La première, la plus classique, dérive des machines de Von Neumann. Quant à la seconde, elle est basée sur un système formel. Le Lambda-calcul est le système formel de la programmation fonctionnelle, la logique des prédicats du premier ordre est celui de la programmation logique.
D�abord un état de l�art sur toute la programmation procédurale est abordée. Les différents schémas, les manières de passer d�un schéma à un autre et les différentes formes de preuves sont présentés. Nous présenterons également le projet CONCORDE qui complète fort bien cet aspect de la programmation avec la présentation de tous les travaux qui ont été entrepris.
La programmation fonctionnelle couvre plusieurs parties : la première partie présente le lambda-calcul, le système formel de tous les langages fonctionnels. La seconde présente la machine à réductions permettant d'évaluer une lambda-expression ( programme fonctionnel) ainsi que des détails de mise en �uvre et d�implémentation. La troisième partie introduit les preuves des langages fonctionnels. Lisp, le précurseur des langages fonctionnels est introduit pour la pratique de ce type de programmation.
La programmation logique couvre 3 parties : la première partie présente la logique des prédicats du premier ordre, le système formel de tous les langages logiques. La seconde présente le principe des démonstrateurs automatiques pour interpréter des clauses ( programme logique). Prolog, le précurseur des langages logiques est introduit pour la pratique de ce type de programmation. Ainsi, une deuxième forme de l�intelligence artificielle est présentée. Nous verrons que la machine est capable de démontrer les théorèmes de la forme a, b, c à d gr�ce à la résolution de Robinson, et certains algorithmes présentés.
Le projet ECOLE 2000, faisant une synthèse des programmations logique et fonctionnelle, est exposé. Il complète ainsi tout le cours de la programmation non procédurale.