Module: TYPES DE DONNEES ET
ALGORITHMES
Volume Horaire
Hebdomadaire
Objectifs
Coefficient
Recommandations
Contenu
Partie
1: STRUCTURES DE DONNEES
(40%)
Chapitre 1:
NOTIONS DE BASE D’ALGORITHMIQUE
(5%)
Chapitre 2:
TYPES ABSTRAITS
(5%)
Chapitre
3: STRUCTURES SEQUENTIELLES
(5%)
Chapitre
4: ENSEMBLES
(5%)
Chapitre
5: STRUCTURES ARBORESCENTES
(15%)
Chapitre
6: LES GRAPHES (5%)
Partie 2: ALGORITHMES
(40%)
Chapitre 7:
INTRODUCTION A L’ANALYSE DES ALGORITHMES (10%)
Chapitre 8: ALGORITHMES DE RECHERCHE
(15%)
Chapitre 9:
ALGORITHMES DE TRI
(10%)
Chapitre
10: QUELQUES ALGORITHMES SUR LES GRAPHES (5%)
Coefficient: 5 Recommandations:
Il est necessaire d’inculquer a l’etudiant la separation entre l’aspect Abstraction et l’aspect Implementation des donnees et des algorithmes.
Partie 1: STRUCTURES DE DONNEES (40%)
Definitions et Motivations
Notions de Signature et d’Operations
Le Type Abstrait "LISTE "
Representation des Listes
Les Types Abstraits " PILE " et " FILE "
Representation des Piles et des Files
Le Type Abstrait " ENSEMBLE "
Representation des Ensembles par des Tableaux
Representation des Ensembles par des Listes
Arbres Binaires
Le Type Abstrait " ARBRE BINAIRE "
Representation des Arbres Binaires
Arbres Planaires Generaux
Le Type Abstrait " ARBRE PLANAIRE GENERAL "
Representation des Arbres Generaux
Chapitre 6: LES GRAPHES (5%)
Le Type Abstrait " GRAPHE "
Representation des Graphes
Parmodule des Graphes
Partie 2: ALGORITHMES (40%)
Chapitre 7: INTRODUCTION A L’ANALYSE DES ALGORITHMES (10%)
Notion d’Algorithmes
Techniques du raffinement successif (Step Wise Refinement)
Complexite des Algorithmes
Exemples
Chapitre 8: ALGORITHMES DE RECHERCHE (15%)
Methodes Simples
Arbres Binaires de Recherche
Arbres Equilibres
Methodes de Hachage
Recherche Externe
Chapitre 9: ALGORITHMES DE TRI (10%)
Methodes Simples
Tri rapide et Tri par tas
Autres methodes
Tri externe
Chapitre 10: QUELQUES ALGORITHMES SUR LES GRAPHES (5%)
Partie 3: IMPLEMENTATION DES ALGORITHMES (20%)
Chapitre 11: NOTIONS DE BASE (10%)Variables, expressions, instructions....
Scope
Bloc
Procedures/Fonctions
Recursivite
Entrees-Sorties
Problematiques du Test et de la Preuve
Techniques de Test et de Preuve
Compromis Test /Preuve
Christine Froidevaux, Marie Claude Gaudel, :Michele Soria " Types de Donnees et Algorithmes ", Mc Graw Hill, 1990
Ellis Horowitz, Sartaj Sahni " Fondamentals of Data Structures ", Computer Science Press
Ellis Horowitz, Sartaj Sahni " Fondamentals of Computer Algorithms ", Computer Science Press
Ellis Horowitz " Fondamentals of Programming Languages ", Computer Science Press, 1983
Knuth" The Art of Computer programming ", Addison Wesley, 1973
Robert H.Dunn" Software Defect Removal ", Mc Graw Hill, 1984
N.Wirth " Algorithms and Data Structures
B.Meyer and C.Baudoin " Methodes de Programmation "
A.V.Aho, J.E.Hopcroft, J.D.Ullman " The Design and Analysis of Computer Algorithms "