Semestre : 3
Unité d’enseignement : UEF31
Matière : ALGO3 (Algorithmique et structures de données)
Crédits : 5
Coefficient : 3
Objectifs de l’enseignement :
Face à de gros problèmes complexes qui manipulent des ensembles de données importants, un des objectifs de ce cours est d'inclure tous les aspects de la structuration des données dont dépend fortement le choix de l'algorithme. L'algorithme et la structure des données sont indissolublement liés. La conception d'algorithmes est une tâche difficile qui nécessite une grande réflexion. Pour un même problème, il existe souvent plusieurs algorithmes qui conduisent à sa solution. Le choix du "meilleur " algorithme est alors guidé par des critères d'efficacité. L'autre objectif de ce cours est d'initier l'étudiant à l'analyse des algorithmes, c'est à dire à la complexité des algorithmes qui est une mesure théorique (indépendante de l’environnement matériel et logiciel) de ses performances en fonction d’éléments caractéristiques de l’algorithme.
Connaissances préalables recommandées : Algorithmique I et Algorithme II.
Contenu de la matière :
Chapitre I : Rappels sur les Bases de l’Algorithmique (3h00)
1. Définitions
2. Propriétés d’un Algorithme (validité, robustesse, réutilisabilité, …)
3. Langage Algorithmique
3.1. Les déclarations des constantes, types et variables
3.2. Les tableaux à une dimension, à deux dimensions et les chaines de caractères.
3.3. Les instructions de base : affectation, lecture, écriture, les instructions
conditionnelles et les instructions itératives (boucles)
3.4. Les actions paramétrées (les fonctions et les procédures) .
Chapitre II : Introduction à l’Analyse des Algorithmes (4h30)
1. L’analyse d’un algorithme
2. Calcul de la complexité d’un algorithme
2.1 Les types de la complexité
2.2 La complexité asymptotique
2.3 Les notations de Landau.
3. Estimation du coût d’un algorithme
4. Exemples d’algorithmes de recherche
4.1 La recherche séquentielle.
4.2 La recherche dichotomique.
4.3 La recherche avec adressage direct.
5. Exemples d’algorithmes de tri
5.1 Tri par permutation
5.2 Tri par dénombrement
2.4 Propriétés
Chapitre III : Représentation des Données en Mémoire (6h00)
1. Définition d’une structure de donnée
2. Représentation des données
2.1. Représentation contigüe
2.2. Représentation chainée
3. Les variables statiques, les variables dynamiques, les pointeurs
4. Allocation dynamique de la mémoire
4.1. Allocation dynamique de variables simples
4.2. Allocation dynamique de variables structurées
4.3. Allocation dynamique de tableaux (à une dimension et à deux dimensions)
5. Les listes chainées
5.1 Les listes simplement chainées
5.2 Les listes doublement chainées
5.3 Les listes circulaires
5.4 Complexité des opérations appliquées sur les listes.
Chapitre IV : Les Piles (4h30)
1. Définition
2. Représentation contigüe
3. Représentation chainée
4. Les opérations de manipulation pour les deux représentations et leurs complexités
4.1. Ajouter un élément (Empiler)
4.2. Retirer un élément (Désempiler)
4.3. Consulter le sommet de la pile (SommetPile)
4.4. Vérifier si la pile est vide (PileVide)
4.5. Vérifier si la pile est pleine dans le cas contigu (PilePleine)
5. Transformation des expressions
5.1 Présentation du problème
5.3 Transformation des expressions Infixées en Postfixées
5.3 Evaluation des expressions Postfixées
Chapitre V : Les Files (3h00)
1. Définition
2. Représentation contigüe (avec tableau simple et avec tableau circulaire)
3. Représentation chainée
4. Les opérations de manipulation pour les deux représentations et leurs complexités
4.1. Ajouter un élément (Enfiler)
4.2. Retirer un élément (Défiler)
4.3. Consulter la tête de la file (TeteFile)
4.4. Vérifier si la file est vide (FileVide)
4.5. Vérifier si la file est pleine dans le cas contigu (FilePleine)
Chapitre VI : La Récursivité (6h00)
1. Définitions
1.1 Objet récursif
1.2 Programmation récursive
1.3 Fonction récursive
1.4 Algorithme récursif
1.5 Auto-imbrication
2. Principes de construction d’algorithmes récursifs
3. Schémas généraux des fonctions récursives
4. Récursivité directe et récursivité indirecte
5. Différents types de la récursivité
5.1 Récursivité simple
5.2 Récursivité multiple
5.3 Récursivité terminale
5.4 Récursivité non terminale
5.5 Récursivité imbriquée
6. Fonctionnement de la récursivité
7. Elimination de la récursivité
7.1 Elimination de la récursivité terminale
7.2 Elimination de la récursivité non terminale
7.3 Elimination de la récursivité dans le cas de deux appels récursifs
8. Etude de la complexité des algorithmes récursifs
Chapitre VII : Les Arbres (9h00)
1. Définitions
1.1 Arbre
1.3 Sous-arbre
1.4 Arbre étiqueté
1.5 Arbre n-aire
1.6 Arbre binaire
1.6.1 Transformation d’un arbre n-aire vers un arbre binaire
1.6.2 Arbre complet et dégénéré
1.6.2 Arbre équilibré et algorithme d’équilibrage
2. Représentation des arbres dans les deux représentations : contigüe et chainée
2.1 Représentation et déclaration d’un arbre n-aire
2.2 Représentation et déclaration d’un arbre binaire
3. Parcours d’un arbre
3.1 Parcours en préordre (préfixé)
3.2 Parcours en ordre (infixé)
3.3 Parcours en postordre (postfixé)
4. Arbre binaire de recherche (ABR)
4.1 Définition
4.2 Les opérations sur les ABR (fonctions récursives et itératives) et complexités
4.2.1 Les parcours (préfixé, infixé et postfixé)
4.2.2 La recherche d’un élément
4.2.3 L’insertion d’un élément
4.2.4 La suppression d’un élément
4.2.5 La construction d’un ABR
5. Structure de TAS
5.1 Définitions : arbre parfait, arbre partiellement ordonné et tas
5.2 Opérations sur les tas et complexité
5.3 Tri par tas
1.2 Feuille, chemin, hauteur, niveau, profondeur, ascendance, descendance
Chapitre VIII : Les Tables de Hachage (6h00)
1. Principe des tables de hachage
2. Fonctions de hachage
2.1 Hachage par division
2.2 Hachage par multiplication
3. Problème des collisions
3.1 Résolution des collisions par chainage
3.2 Résolution des collisions par adressage ouvert
3.3 Résolution par double-hachage
4. Types de hachage et complexité (statique, dynamique, parfait, distribué)
Mode d’évaluation :
Contrôle continu
Examen semestriel final
Références (Livres et polycopiés, sites internet, …, etc) :
« Introduction to Algorithms », (Second Edition), Thomas H. Cormen, Charles E.
Leiserson, Ronald L. Rivest, Clifford Stein. The MIT Press Cambridge,
Massachusetts London, England, McGraw-Hill Book Company, Boston Burr Ridge,
IL Dubuque , IA Madison , WI New York San Francisco St. Louis, Montréal Toronto.
Eléments d’Algorithmique ; D. Beauquier, J. Berstel, Ph. Chrétienne, 2003.
Première édition par Masson, 1992.
Types de données et algorithmes ; Gaudel, Froidevaux et Soria; INRIA.
- Enseignant: LAACHEMI Abdelouahab LAACHEMI