4.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

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)

- 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

- Traitement et implantation d'un exemple complet de
   construction d'un arbre abstrait d'expressions.