1. Introduction

• 1.1. Pourquoi un cours d'algorithmique
  • 1.1.1. Le mot Algorithme
  • 1.1.2. quels sont les besoins
• 1.2. Buts de ce cours
• 1.3. Langage
• 1.4. Structure des données
  • 1.4.1. types de données
  • 1.4.2. les données
• 1.5. Structures de contrôle
• 1.6. "Notations agorithmiques"
  • 1.6.1. Les commentaires
  • 1.6.2. Les déclarations
  • 1.6.3. Les instructions exécutables et de contrôle
• 1.7. Bibliographie (non exhaustive)
• 1.8. Appendices
  • 1.8.1. Exécution séquentielle
  • 1.8.2. Contenants
  • 1.8.3. Contenu
  • 1.8.4. Contenant et contenu
  • 1.8.5. En avoir ou pas : les pointeurs
  • 1.8.6. "Arguments d'Entrée", "Argument de Sortie"... comment matérialiser ces notions
    • 1.8.6.1. Exemple
    • 1.8.6.2. Exemple en Pascal
    • 1.8.6.3. Exemple en FORTRAN 77
    • 1.8.6.4. Exemple en FORTRAN 90
    • 1.8.6.5. Exemple en C
    • 1.8.6.6. Exemple en C++
• 1.9. Compléments : exemples numériques "surprenants"
  • 1.9.1. Nombre de racines d'une équation du second degré
  • 1.9.2. Influence de l'ordre des opérations
  • 1.9.3. Série en 1/n²
  • 1.9.4. Recherche d'un zéro d'une équation par la méthode de dichotomie
  • 1.9.5. Calcul de π par l'algorithme d'Archimède
  • 1.9.6. Calcul de sin(α) par un développement en série entière

2. Structures linéaires

• 2.1. Les Listes
  • 2.1.1. Première fonction : rechercher la position d'un élément dont on connaît la "valeur-clé"
    • 2.1.1.1. Etape 0 (énoncé du problème)
    • 2.1.1.2. Etape 1 (idée de base)
    • 2.1.1.3. Etape 2 (amélioration)
    • 2.1.1.4. Etape 3 (itération)
    • 2.1.1.5. Etape 4 (débuter)
    • 2.1.1.6. Etape 5 (mise en forme de la procédure)
  • 2.1.2. Les autres fonctions élémentaires : ôter ou insérer un élément
    • 2.1.2.1. Fonction Ôter
    • 2.1.2.2. Fonction Insérer
  • 2.1.3. Complexité
  • 2.1.4. Programmation
    • 2.1.4.1. Représentation "dynamique" en Pascal
    • 2.1.4.2. Représentation "statique" en Pascal
    • 2.1.4.3. Représentation "statique" en FORTRAN 77
    • 2.1.4.4. Représentation "dynamique" en FORTRAN 90
    • 2.1.4.5. Représentation "dynamique" en C
    • 2.1.4.6. Représentation "statique" en C
• 2.2. Les Piles
  • 2.2.1. Empiler
    • 2.2.1.1. Etape 1 (Idée de base)
    • 2.2.1.2. Etape 2 (gestion des cas particuliers)
    • 2.2.1.3. Etape 3 (mise en forme de la procédure)
  • 2.2.2. Dépiler
    • 2.2.2.1. Etape 1 (Idée de base)
    • 2.2.2.2. Etape 2 (mise en forme de la procédure)
  • 2.2.3. Initialiser la pile
• 2.3. Les Files
  • 2.3.1. Ajouter, retirer
    • 2.3.1.1. Etape 1 (idée de base) pour "Ajouter"
    • 2.3.1.2. Etape 1 (idée de base) pour "Retirer"
    • 2.3.1.3. Etape 2 (vérifier que c'est possible et gérer les cas particuliers)
    • 2.3.1.4. Etape 3 (mise en forme de la procédure) pour "Ajouter"
    • 2.3.1.5. Etape 3 (mise en forme de la procédure) pour "Retirer"
  • 2.3.2. Initialiser une file
  • 2.3.3. Réalisation de la fonction "suivant"

3. Les tris simples

• 3.1. Durées d'exécution
  • 3.1.1. Croissance avec n
  • 3.1.2. Notations O, Θ et Ω
• 3.2. Trier
• 3.3. Tri par sélection
  • 3.3.1. Principe
  • 3.3.2. Mise en œuvre
  • 3.3.3. Complexité, stabilité
• 3.4. Tri par insertion directe (tri du joueur de cartes)
  • 3.4.1. Principe
  • 3.4.2. Déterminer la place (où insérer) par recherche séquentielle
  • 3.4.3. Insérer
  • 3.4.4. Déterminer la place où insérer par recherche dichotomique
• 3.5. Tri-Fusion
  • 3.5.1. Ecriture de TriFusion
  • 3.5.2. Ecriture de TriFusLT
  • 3.5.3. Ecriture de Fusion
  • 3.5.4. Complexité de TriFusion
  • 3.5.5. Exemple : en-têtes en Fortran90 (communication automatique des tailles des tableaux)
• 3.6. Tri "indexé"
• 3.7. Conclusion sur les algorithmes présentés

4. Hachage

• 4.1. Ranger et retrouver rapidement l'information
• 4.2. Gestion des collisions
  • 4.2.1. Méthode directe : hachage linéaire
  • 4.2.2. Méthode indirecte avec chaînage séparé
• 4.3. Fonction de hachage

5. Arbres

• 5.1. Origine, notions intuitives, exemples
• 5.2. Vocabulaire et définitions
• 5.3. Représentation des arbres
• 5.4. Arbre binaire de recherche
  • 5.4.1. Définitions
  • 5.4.2. Exemple de construction d'un arbre binaire de recherche
• 5.5. Opérations élémentaires sur les arbres binaires de recherche
  • 5.5.1. Première fonction : rechercher la position d'un noeud dont on connait la "clé"
  • 5.5.2. Seconde fonction : ajouter un noeud
  • 5.5.3. Troisième fonction : supprimer un noeud
  • 5.5.4. fonctions supplémentaires
• 5.6. Traversée de l'arbre

6. Récursion

• 6.1. Définition
• 6.2. Conditions
• 6.3. Exemple : traversée d'un arbre
• 6.4. Méthode de "dérécursification"
  • 6.4.1. Liste des actions
  • 6.4.2. Moteur d'automate
  • 6.4.3. Simulation de la séquence d'appel
  • 6.4.4. Simulation du "stack-frame"
  • 6.4.5. Détail des actions
  • 6.4.6. Procédure itérative Parcourir_rameau
• 6.5. Procédure récursive ou itérative
• 6.6. Appendice : appel de procédure et gestion de la mémoire
  • 6.6.1. Langage FORTRAN
  • 6.6.2. Langage C

7. Tri par tas (Heapsort)

• 7.1. Principe
• 7.2. Définitions
• 7.3. Fonctions de la sélection
• 7.4. Comment recréer une structure pyramidale
• 7.5. Construction de la pyramide
• 7.6. Procédure de tri
• 7.7. Indice du père et des fils
• 7.8. Compléxité
• 7.9. Exercice

8. Tri par partition (Quicksort)

• 8.1. Idée de base1
• 8.2. Choix4
• 8.3. Procédure partitioner
• 8.4. Complexité
• 8.5. Choix du pivot
• 8.6. Procédure QS
• 8.7. Exercice

9. Recherche de texte

• 9.1. Idée de base
• 9.2. Algorithme naïf
• 9.3. Algorithme rusé : l'algorithme de Boyer-Moore