Conception de programmes

ISTC : Editions itineraires scientifiques (2022)

ISBN

978-9931-825-69-2

Texte du rabat:

 

Par conception de programmes, nous entendons la manière d’aborder et de résoudre un problème donné. Diverses manières sont présentées: 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.
L’intelligence artificielle est également introduite. La technique du Min-Max est alors présentée montrant comment une machine peut jouer et gagner un être humain dans les jeux de stratégie. L’algorithme A*, le plus populaire en intelligence artificielle est aussi exhibé montrant comment des solutions optimales à des problèmes complexes sont trouvées.
La classification des problèmes liée à la théorie de la complexité est aussi abordée utilisant le modèle des machines de Turing. Nous nous focaliserons essentiellement sur les classes 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). La classe NP-complet, celle des problèmes les plus difficiles de la classe NP est aussi exposée avec des exemples de réduction de problèmes.
Ce livre couvre le cours ‘Conception de programmes’ tel qu’il est assuré à l’École Supérieure d’Informatique(ESI, Alger) pour les étudiants de graduation. Il rappelle, comme pré-requis, la O-notation et les graphes. Enfin, une bonne partie de ce livre est consacrée aux exercices avec des corrigés types.
 

Domiciliation ISTC:

Douéra, Alger

 

Auteurs:

Walid Khaled HIDOUCI

Djamel Eddine ZEGOUR

 

Nombre de pages:

135

 

Mots-clés:

O notation - Graphes - Diviser pou résoudre - Programmation dynamique - Backtracking - Heuristiques - Min Max - A* - Machine de Turing - Classes de complexité - NP complétude