Table des matières

• Chapitre 1  Listes
  • 1.1  Structure dynamique, structure séquentielle
  • 1.2  Listes chaînées, révisions
    • 1.2.1  Opérations élémentaires sur les listes
    • 1.2.2  Programmation sûre, style dit fonctionnel
    • 1.2.3  Programmation dangereuse, structures mutables
    • 1.2.4  Contrôle de la révision
  • 1.3  Tri des listes
    • 1.3.1  Tri par insertion
    • 1.3.2  Tri fusion
    • 1.3.3  Trier de grandes listes
  • 1.4  Programmation objet
    • 1.4.1  Ensembles non mutables
    • 1.4.2  Ensembles mutables
  • 1.5  Complément : listes bouclées
    • 1.5.1  Représentation des polygones
    • 1.5.2  Opérations sur les polygones
    • 1.5.3  Calcul incrémental de l’enveloppe convexe
    • 1.5.4  Calcul efficace de l’enveloppe convexe
• Chapitre 2  Piles et files
  • 2.1  À quoi ça sert ?
    • 2.1.1  Premier arrivé, premier servi
    • 2.1.2  Utilisation d’une pile
  • 2.2  Implémentation des piles
    • 2.2.1  Une pile dans un tableau
    • 2.2.2  Une pile dans une liste
    • 2.2.3  Les piles de la bibliothèque
  • 2.3  Implémentation des files
    • 2.3.1  Une file dans un tableau
    • 2.3.2  Une file dans une liste
    • 2.3.3  Les files de la bibliothèque
  • 2.4  Type abstrait, choix de l’implémentation
• Chapitre 3  Associations — Tables de hachage
  • 3.1  Statistique des mots
    • 3.1.1  Résolution par une table d’association
    • 3.1.2  Implémentation simple de la table d’association
  • 3.2  Table de hachage
    • 3.2.1  Adressage direct
    • 3.2.2  Table de hachage
    • 3.2.3  Résolution des collisions par chaînage
    • 3.2.4  Adressage ouvert
    • 3.2.5  Tables de hachage de la libraire
    • 3.2.6  Performance
  • 3.3  Choix des fonctions de hachage
    • 3.3.1  En théorie
    • 3.3.2  En pratique
• Chapitre 4  Arbres
  • 4.1  Définitions
    • 4.1.1  Graphes
    • 4.1.2  Arbres libres
    • 4.1.3  Arbres enracinés
    • 4.1.4  Arbres ordonnés
  • 4.2  Union-Find, ou gestion des partitions
    • 4.2.1  Une solution du problème
    • 4.2.2  Applications de l’algorithme Union-Find
  • 4.3  Arbres binaires
    • 4.3.1  Compter les arbres binaires
    • 4.3.2  Arbres binaires et mots
    • 4.3.3  Parcours d’arbre
    • 4.3.4  Une borne inférieure pour les tris par comparaisons
  • 4.4  Arbres de syntaxe abstraite
    • 4.4.1  Les expressions sont des arbres
    • 4.4.2  Implémentation des arbres de syntaxe abstraite
    • 4.4.3  Traduction de la notation postfixe vers la notation infixe
  • 4.5  Files de priorité
    • 4.5.1  Tas
    • 4.5.2  Implantation d’un tas
    • 4.5.3  Arbres de sélection
  • 4.6  Codage de Huffman
    • 4.6.1  Compression des données
    • 4.6.2  Algorithme de Huffman
    • 4.6.3  Algorithme de Huffman adaptatif
• Chapitre 5  Arbres binaires
  • 5.1  Implantation des arbres binaires
    • 5.1.1  Implantation des arbres ordonnés par arbres binaires
  • 5.2  Arbres binaires de recherche
    • 5.2.1  Recherche d’une clé
    • 5.2.2  Insertion d’une clé
    • 5.2.3  Suppression d’une clé
    • 5.2.4  Hauteur moyenne
  • 5.3  Arbres équilibrés
    • 5.3.1  Arbres AVL
    • 5.3.2  B-arbres et arbres a-b
• Chapitre 6  Expressions régulières
  • 6.1  Langages réguliers
    • 6.1.1  Les mots
    • 6.1.2  Syntaxe des expressions régulières
    • 6.1.3  Sémantique des expressions régulières
    • 6.1.4  Filtrage
  • 6.2  Notations supplémentaires
  • 6.3  Programmation avec les expressions régulières
    • 6.3.1  Dans l’interprète de commandes Unix
    • 6.3.2  Recherche de lignes dans un fichier, la commande egrep
    • 6.3.3  En Java
  • 6.4  Implémentation des expressions régulières
    • 6.4.1  Arbres de syntaxe abstraite
    • 6.4.2  Fabrication des expressions régulières
    • 6.4.3  Filtrage
    • 6.4.4  Emploi de notre package regex
  • 6.5  Une autre approche du filtrage
    • 6.5.1  Langage dérivé
    • 6.5.2  Filtrage par la dérivation des motifs
• Chapitre 7  Les automates
  • 7.1  Pourquoi étudier les automates
  • 7.2  Rappel : alphabets, mots, langages et problèmes
  • 7.3  Automates finis déterministes
    • 7.3.1  Fonctionnement d’un automate fini déterministe
    • 7.3.2  Des représentation “compactes” des automates
  • 7.4  Automates finis non-déterministes
    • 7.4.1  Fonctionnement d’un automate fini non-déterministe
    • 7.4.2  Déterminisation d’un automate fini non-déterministe
    • 7.4.3  Les є transitions
  • 7.5  Automates finis et expressions régulières
  • 7.6  Un peu de Java
    • 7.6.1  Modèle
    • 7.6.2  Algorithme de recherche
    • 7.6.3  Mise en œuvre sur un automate
• Annexe A  Le coût d’un algorithme
  • A.1  Une définition très informelle des algorithmes
  • A.2  Des algorithmes “efficaces” ?
  • A.3  Quelques exemples
    • A.3.1  Factorielle
    • A.3.2  Recherche Dichotomique
    • A.3.3  Tours de Hanoi
    • A.3.4  Recherche d’un nombre dans un tableau, complexité en moyenne
  • A.4  Coût estimé vs. coût réel
• Annexe B  Morceaux de Java
  • B.1  Un langage plutôt classe
    • B.1.1  Programme de classe
    • B.1.2  Complément : la méthode main
    • B.1.3  Collaboration de classe
    • B.1.4  Méfiance de classe
    • B.1.5  Reproduction de classe par héritage
  • B.2  Obscur objet
    • B.2.1  Utilisation des objets
    • B.2.2  Fabrication des objets
    • B.2.3  Héritage des objets, sous-typage
  • B.3  Constructions de base
    • B.3.1  Valeurs, variables
    • B.3.2  Types
    • B.3.3  Déclarations
    • B.3.4  Principales expressions et instructions
    • B.3.5  Notations complètes et abrégées
    • B.3.6  Les tableaux
    • B.3.7  Passage par valeur
  • B.4  Exceptions
    • B.4.1  Exceptions lancées par le système d’exécution
    • B.4.2  Lancer une exception
    • B.4.3  Complément : programmer avec les exceptions
  • B.5  Entrées-sorties
    • B.5.1  Le minimum à savoir : une entrée et une sortie standard
    • B.5.2  Un peu plus que le minimum : lire des fichiers
    • B.5.3  Encore un peu plus que le minimum : écrire dans un fichier
    • B.5.4  Toujours plus loin : entrées-sorties bufferisées
    • B.5.5  Entrées-sorties formatées
    • B.5.6  Complément : tout ou presque sur les fichiers texte
  • B.6  Quelques classes de bibliothèque
    • B.6.1  Package java.lang, bibliothèque « standard »
    • B.6.2  Package java.io, entrées-sorties
    • B.6.3  Package java.util : trucs utiles
  • B.7  Pièges et astuces
    • B.7.1  Sur les caractères
    • B.7.2  Opérateurs
    • B.7.3  Connecteurs « paresseux »
• Références
• Index