Algorithmes et Structures de Données Avancées: SDDA1

D’après le cours de Monsieur Wilfred Minfoundi (BTS 2025-2026) – Document C3, 72 pages

1. Liste des questions de cours les plus fréquentes

Exemples : Qu'est-ce qu'un algorithme ? Propriétés. Différences entre variable, constante, type, affectation. Types primitifs. Tableau à une dimension, enregistrement, vecteur. Fichier séquentiel vs accès direct. Liste chaînée, nœud, pointeur. Pile (LIFO) et file (FIFO). Complexités, insertions/suppressions.

2. Généralités et concepts de base

Algorithme : suite finie et non ambiguë d'instructions résolvant un problème.

Structure générale :

Algorithme Nom

Constantes

Types

Sous-programmes (procédures/fonctions)

Variables

Début

  Instructions

Fin.

Règle importante : pas de points-virgules en algorithmique.

Types de données primitifs : Entier, Réel, Chaîne, Booléen.

Variable : emplacement mémoire – déclaration : Var nom : Type.

Plusieurs variables de même type : Var a, b, c : Entier ; types différents sur lignes séparées.

Constante : Const Pi = 3.14 (valeur fixe).

Opérateurs :

- Comparaison : =, , , =

- Arithmétiques : +, -, *, /

- DIV : quotient entier (ex: 10 DIV 3 = 3)

- MOD : reste (10 MOD 3 = 1)

Affectation : Variable  Expression (gauche toujours une variable).

3. Lecture et écriture

Lecture : Lire(variable) ou Lire(v1, v2) pour plusieurs.

Écriture : Ecrire('message'), Ecrire(resultat), ou Ecrire('texte', var).

Variables d'entrée (VE) : lues ; variables de sortie (VS) : affichées.

4. Structures conditionnelles

À un choix :

Si (condition) Alors

  instructions

FinSi

À deux choix :

Si (condition) Alors

  instructions1

Sinon

  instructions2

FinSi

La condition peut être simple ou composée (ET, OU). Autant de Si que de Sinon.

5. Boucles (structures répétitives)

Boucle Pour : nombre de tours connu à l'avance.

Pour i de 1 à N Faire

  instructions

FinPour

i est la variable compteur (Entier).

Boucle TantQue : test avant exécution, nombre inconnu.

i ← 1

TantQue (i Max alors Max ← Tab[i] ; Pos ← i.

- Recherche d'un élément : Utiliser TantQue (non trouvé et pas fin). Variable booléenne Trouve ← Faux. On compare Tab[i] avec l'élément cherché.

- Tri simple (comparaison directe) : Pour i de 1 à N-1 ; Pour j de i+1 à N ; Si Tab[i] > Tab[j] alors permutation avec variable temporaire.

7. Enregistrements

Définition : type structuré regroupant plusieurs champs de types éventuellement différents.

Syntaxe :

Type NomEnreg = Enregistrement

  champ1 : Type1

  champ2 : Type2

Fin

Déclaration : Var varEnreg : NomEnreg

Accès aux champs : varEnreg.champ1.

Lecture : Lire(varEnreg.champ1) ; écriture : Ecrire(varEnreg.champ1).

Type structuré imbriqué : un champ peut être un autre enregistrement. Exemple : Date (Jour, Mois, Année) utilisé dans Personne (DateNaiss). Accès : Personne.DateNaiss.Année.

Exemple Fournisseur-Produit :

Type Fournisseur = Enreg (CodeF, RaisonSo, NumTel)

Type Produit = Enreg (CodeP, LibelleP, DateApprov, PrixP, Fours : Fournisseur)

Accès au téléphone : P.Fours.NumTel.

Principe : la clé du père (Fournisseur) migre dans le fils (Produit).

8. Tableaux d’enregistrements (vecteurs)

Définition : tableau dont chaque élément est un enregistrement.

Type Vect = Tableau [1..Max] NomEnreg

Var Tab : Vect

Accès : Tab[i].champ.

Opérations d’enregistrement dans un vecteur :

- Cas 1 – Enregistrer tous les éléments : Pour i de 1 à Max : Lire(E.champs) ; Tab[i] ← E.

- Cas 2 – Enregistrer un seul élément : Si N = Max alors « Plein » ; Sinon Lire(E) ; N ← N+1 ; Tab[N] ← E.

- Cas 3 – Enregistrer plusieurs éléments (M) : Vérifier que N+M ≤ Max ; puis Pour j de 1 à M : Lire(E) ; N ← N+1 ; Tab[N] ← E.

PCR (Parcours, Condition, Résultat) :

- Pour afficher : Pour i de 1 à N ; Si Tab[i].champ = condition alors Ecrire(Tab[i].champ1, Tab[i].champ2).

- Pour compter : Cpt ← 0 ; Pour i... Si condition alors Cpt ← Cpt+1 ; afficher Cpt.

Tri d’un vecteur : Pour i de 1 à N-1 ; Pour j de i+1 à N ; Si Tab[i].champTri > Tab[j].champTri alors permuter Tab[i] et Tab[j] (avec variable temporaire de type enregistrement).

9. Sous-programmes (procédures et fonctions)

Arguments : formels (dans l’en-tête) et effectifs (lors de l’appel).

Variables locales : définies à l’intérieur du sous-programme.

Variables globales : définies dans l’algorithme principal.

Passage par valeur : le paramètre n’est pas modifié.

Passage par adresse : précédé du mot-clé Var ; la modification est répercutée. Utilisé pour enregistrement, ajout, insertion, suppression, tri.

Structure d’une procédure :

Procédure Nom(Param1 : Type1 ; Var Param2 : Type2)

Var variables locales

Début

  instructions

Fin Procédure

Structure d’une fonction :

Fonction Nom(Paramètres) : TypeRetour

Var locales

Début

  instructions

  Nom ← résultat

Fin Fonction

La fonction retourne toujours un résultat de type simple (Entier, Réel, Booléen).

10. Principes méthodologiques importants

Principe 1 – Date : si manipulation de dates, définir en premier le type Date (Jour, Mois, Année).

Principe 2 – Structure de données : ordre de définition : 1) Date (si nécessaire), 2) Enregistrements, 3) Vecteur (tableau d’enregistrements), 4) Fichier, 5) Liste chaînée.

Principe 3 – Enregistrer dans un vecteur : trois cas selon que l’on remplit tout, un seul ou plusieurs éléments (toujours vérifier la place).

Principe 4 – PCR : Parcours + Condition + Résultat (afficher, compter, sommer).

Principe 5 – Trier : deux boucles imbriquées avec permutation.

Principe 6 – Identification des paramètres : ce qui suit « Prend en entrée / en paramètre » donne les paramètres ; se demander où est stockée la donnée (vecteur, fichier, liste) pour le premier paramètre.

11. Fichiers séquentiels

Définition : collection d’enregistrements homogènes stockée sur support externe. Accès séquentiel : pour lire le n-ième, il faut lire les n-1 précédents.

Déclaration :

Type Fich = Fichier de TypeEnreg

Var F : Fich

Primitives :

- Assigner(F, 'nomPhysique.ext') : lie nom logique et nom physique.

- OuvrirL(F) : ouverture en lecture.

- OuvrirE(F) : ouverture en écriture (écrasement).

- Ouvrir(F) : lecture et écriture.

- Fermer(F).

- Lire(F, Val) : lit un enregistrement dans Val.

- Ecrire(F, Val) : écrit un enregistrement.

- EOF(F) : vrai si fin de fichier.

Traitement de base en lecture :

OuvrirL(F)

Lire(F, Val)

TantQue Non EOF(F) Faire

  // traiter Val

  Lire(F, Val)

FinTantQue

Fermer(F)

PCR sur fichier : même principe que pour vecteur, avec boucle TantQue et condition sur Val.champ.

Création d’un fichier : OuvrirE(F) ; Répéter Lire(Val) ; Si Val.champ1 '' alors Ecrire(F, Val) ; Jusqu’à (Val.champ1 = '').

Taille d’un fichier : compter les enregistrements par parcours.

Transfert Tableau → Fichier : OuvrirE(F) ; Pour i de 1 à N faire Ecrire(F, Tab[i]).

Transfert Fichier → Tableau : OuvrirL(F) ; i ← 1 ; TantQue Non EOF(F) faire Lire(F, Tab[i]) ; i ← i+1.

12. Listes chaînées

Généralités : structure dynamique de taille variable. Chaque élément (nœud) contient une donnée et un pointeur vers le suivant. Dernier pointeur = NIL. Accès uniquement par la tête (premier élément).

Différences : Tableau : taille fixe, accès direct par indice. Liste chaînée : taille variable, accès séquentiel. Pile (LIFO) : ajout/suppression en tête. File (FIFO) : ajout en queue, suppression en tête.

Déclaration :

Type Cellule = Enregistrement

  info : TypeInfo

  suivant : ^Cellule

Fin

Type Liste = ^Cellule

Var Tete : Liste

Exemple avec étudiant (Matricule, Nom, Spécialité, Quartier, puis suivant).

Primitives mémoire : Allouer(P) (réserve un espace pour un nouveau nœud), Libérer(P) (désalloue). Tete et Queue sont des pointeurs spéciaux.

Manipulations :

- Affectation : P^.info ← valeur ; P^.suivant ← adresse.

- Création d’une liste de N éléments : Tete ← NIL ; Pour i de 1 à N : Allouer(P) ; Lire(P^.info) ; P^.suivant ← Tete ; Tete ← P.

- Taille d’une liste : Cpt ← 0 ; P ← Tete ; TantQue P NIL : Cpt ← Cpt+1 ; P ← P^.suivant. Retourner Cpt.

- Insertion en tête : Allouer(P) ; Lire(P^.info) ; P^.suivant ← Tete ; Tete ← P.

- Insertion en queue : Parcourir jusqu’à NIL avec un pointeur, allouer P2, P2^.suivant ← NIL, puis dernier^.suivant ← P2.

- Suppression du premier élément : Si Tete NIL alors P ← Tete ; Tete ← Tete^.suivant ; Libérer(P).

- Suppression du dernier élément : Parcourir avec deux pointeurs (P1 avant-dernier, P dernier) ; P1^.suivant ← NIL ; Libérer(P).

- PCR pour afficher/compter : Parcours avec TantQue, condition sur P^.info, affichage ou comptage.

- Transfert Tableau → Liste : Tete ← NIL ; Pour i de 1 à N : Allouer(P) ; P^.info ← Tab[i] ; P^.suivant ← Tete ; Tete ← P.

- Transfert Liste → Tableau : i ← 1 ; P ← Tete ; TantQue P NIL : Tab[i] ← P^.info ; P ← P^.suivant ; i ← i+1.

- Transfert Fichier → Liste : OuvrirL(F) ; Tete ← NIL ; TantQue Non EOF(F) : Lire(F, Val) ; Allouer(P) ; P^.info ← Val ; P^.suivant ← Tete ; Tete ← P.

- Transfert Liste → Fichier : OuvrirE(F) ; P ← Tete ; TantQue P NIL : Ecrire(F, P^.info) ; P ← P^.suivant.

13. Algorithmes de tri et recherche dans un tableau

Tri par sélection (minimum) : pour Indice de 1 à N-1 : chercher l’indice du minimum dans [Indice..N], puis permuter avec l’élément à Indice.

Tri à bulles : parcours répétés : pour i de 1 à N-1, pour j de i+1 à N, si T[i] > T[j] alors permuter. S’arrête quand aucune permutation après un parcours complet.

Tri par insertion : on prend un élément et on l’insère à sa place dans la partie déjà triée du tableau.

Recherche séquentielle : parcours linéaire en comparant l’élément cherché X avec chaque T[i] jusqu’à trouver ou fin de tableau. Complexité O(N).

Recherche dichotomique : nécessite tableau trié. On compare X avec l’élément du milieu. Si égal → trouvé. Si X < milieu → rechercher dans la moitié gauche ; sinon dans la moitié droite. On répète jusqu’à trouver ou intervalle vide. Complexité O(log N).

Algorithme :

BInf ← 1 ; BSup ← N

Répéter

  Mil ← (BInf+BSup) DIV 2

  Si T[Mil] = X alors trouvé

  Sinon si X < T[Mil] alors BSup ← Mil-1

  Sinon BInf ← Mil+1

Jusqu’à (trouvé ou BInf > BSup)

Fin du résumé complet – couvre l’intégralité du document source (72 pages).