chapitre 4
Algorithmes (conception et exemples)
Types abstraits de données
Algorithmes de tris, recherche....
Arbres algos, progammes.....
.1 Développement méthodique du logiciel
la production du logiciel
conception structurée descendante et machines abstraites
notion d'algorithme
un langage de description d'algorithmes le LDFA (assistant API Ldfa = )
le dossier de programmation (assistant API ProgAlgo = )
trace formelle d'un algorithme
traducteur LDFA - Pascal
facteurs de qualité du logiciel
4.2.Machines abstraites : exemple de traitement sur les chaînes
cas où la version du pascal contient un type chaîne
cas où la version deu pascal ne contient pas de type chaîne
programme pascal obtenu
autres versions d'implantation en pascal
4.3.Modularité
définition : B.Meyer
la modularité en pascal avec les Unit (assistant API Pascal (exemples.) = )
4.4.Spécification abstraite de données (assistant API TAD = )
- la notion de type abstrait de données (TAD)
- exemples de TAD :
le TAD liste linéaire
le TAD pile LIFO
le TAD file FIFO
- type abstrait de données et Unit en pascal
4.5.TAD et spécification graphique
- application des TAD à la construction d'analyseur
les identificateurs pascal-like
les expressions arithmétiques
un TAD générateur d'analyseur
4.6.Quelques méthodes de tri internes comparées (assistant API Tris = )
- Complexité d'un algorithme
Notions de complexité temporelle et spatiale
Mesure de la complexité temporelle d'un algorithme
Notation de Landau O(n)
- Trier des tableaux en mémoire centrale
Le Tri à bulles
Le Tri par sélection
Le ri par insertion
Le Tri rapide QuickSort
Le Tri par tas HeapSort
- Rechercher dans un tableau
Dans un tableau non trié
Dans un tableau trié
4.7.Structures arborescentes : Arbres binaires
- Notions générales sur les arbres
Vocabulaire employé sur les arbres
Exemples et implémentation d'arbre
- Arbres binaires
TAD d'arbre binaire
Exemples et implémentation d'arbre
Arbres binaires de recherche
Arbres binaires partiellement ordonnés (tas)
4.8.Algorithmes et programmes sur les arbres binaires
- Implantations en Delphi des 4 algorithmes de parcours
Implantations avec variables dynamique et classe
Implantation du parcours en préordre
Implantation du parcours en postordre
Implantation du parcours en ordre infixé
Implantation du parcours en largeur
Programme Delphi complet
- Arbres binaires de recherche
Insertion dans un arbre binaire de recherche
Recherche dans un arbre binaire de recherche
Suppression dans un arbre binaire de recherche
Plus grand et plus petit élément d'un arbre binaire de recherche
Programme Delphi complet
4.9.Arbres binaires et expressions arithmétiques
- Traitement et implantation d'un exemple complet de
construction d'un arbre abstrait d'expressions.