Dossier complet — Algorithmique et structures de données 1

L1 · S1 · Informatique fondamentale

Dossier pédagogique original Matrice MI. Contenu d’entraînement non officiel; il ne remplace pas le support ou la maquette d’un établissement.

Objectifs d’apprentissage

• Décomposer un problème simple en étapes, préciser les entrées, les sorties et les invariants d’un algorithme.

• Écrire et lire des fonctions élémentaires en Python et transposer leur logique en C avec des types explicites.

• Parcourir, rechercher et agréger les éléments d’un tableau en traitant correctement les indices et les cas limites.

• Construire des jeux de tests pertinents et justifier la correction d’un algorithme par un raisonnement structuré.

• Estimer le coût en temps et en mémoire d’un programme à l’aide des notations O, Ω et Θ, sans confondre cas et ordre de grandeur.

Prérequis

• Manipuler les entiers, les comparaisons, les expressions booléennes et les opérations arithmétiques usuelles.

• Savoir lire un pseudo-code et exécuter mentalement une boucle simple avec une trace de variables.

• Disposer d’un environnement Python ou C et connaître les notions élémentaires de fichier, compilation ou interprétation.

Cours

1. Décomposer un problème

Idée directrice

Un algorithme est une suite finie d’instructions non ambiguës qui transforme des entrées en sorties. Avant de coder, on écrit un contrat : préconditions acceptées, résultat . La décomposition en fonctions limite la taille du raisonnement : chaque fonction reçoit des paramètres, calcule une valeur et laisse un état compréhensible. Une fonction explicite son cas limite ; par exemple, le maximum d’une liste vide n’est pas défini.

Méthode. Pour calculer le maximum d’une liste non vide, choisir le premier élément comme résultat provisoire, puis comparer chaque suivant et remplacer si nécessaire. Exemple guidé : pour [3, 8, 2], on initialise m=3, puis 8>3 donne m=8, 2>8 est faux ; la sortie est donc 8. En Python : def maximum(a): m = a[0] for x in a[1:]: if x > m: m = x return m.

Erreurs fréquentes : initialiser à zéro (faux si toutes les valeurs sont négatives), oublier le contrat de non-vacuité, ou mélanger calcul et affichage. Point de contrôle : écrire en une phrase la précondition, la sortie et un test pour [-4, -2].

Points-clés

• Un contrat relie préconditions, calcul et résultat observable.
• Une fonction courte isole une responsabilité et facilite le test.
• L’initialisation doit être compatible avec toutes les valeurs autorisées.

2. Tableaux et parcours

Accéder aux données séquentielles

Un tableau stocke des éléments accessibles par indice ; en Python, les indices vont de 0 à n-1, tandis qu’en C l’accès hors limites produit un comportement indéfini. Un parcours séquentiel visite chaque case au plus une fois. Il permet de rechercher, filtrer, sommer ou compter sans déplacer les données.

Recherche guidée. Pour trouver 7 dans [4, 7, 1], parcourir les indices 0, 1, comparer 4 puis 7, et retourner 1 dès égalité. Si aucune case ne convient, retourner -1. Le coût vaut au plus n comparaisons, donc $T(n)\in O(n)$ ; l’arrêt précoce rend le meilleur cas constant, mais pas le pire cas.

Une méthode robuste sépare l’indice de la valeur et définit le résultat d’absence. Erreurs fréquentes : commencer à 1, confondre valeur et indice, oublier le tableau vide, ou continuer après une trouvaille sans raison. En C, for (int i=0; i<n; i++) respecte la borne supérieure exclusive. Point de contrôle : indiquer l’indice renvoyé pour [9, 3, 3] et la cible 3, puis expliquer pourquoi le doublon n’est pas une erreur.

Points-clés

• Un indice valide appartient à l’intervalle $[0,n-1]$.
• La recherche linéaire renvoie souvent un indice ou une valeur sentinelle.
• Le meilleur cas et le pire cas peuvent avoir des coûts différents.

3. Fonctions et tests

Contrôler le déroulement

Les structures if, for et while choisissent ou répètent des actions. Une condition doit être formulée sur une valeur connue, et une boucle doit avoir une progression qui garantit l’arrêt. L’invariant est une propriété vraie avant et après chaque tour ; il sert à justifier le résultat final. Pour compter les positifs d’un tableau, l’invariant naturel est : après avoir traité les i premières cases, le compteur vaut le nombre de positifs parmi ces cases.

Exemple guidé. Sur [-2, 5, 0, 7], initialiser c=0. À -2, rien ; à 5, c=1 ; à 0, rien si l’on demande strictement x>0 ; à 7, c=2. Le retour est 2. En pseudo-code : c←0; pour x dans A : si x>0 alors c←c+1.

Limites et erreurs : utiliser >=0 au lieu de >0, modifier l’indice dans un for, créer un while sans mise à jour, ou tester seulement une valeur moyenne. Pour while, vérifier initialisation, condition et progression . Point de contrôle : donner l’invariant du comptage des valeurs paires et exécuter l’algorithme sur [1, 4, 6].

Points-clés

• Chaque boucle doit posséder une progression vers une condition d’arrêt.
• Un invariant décrit ce qui est déjà correctement traité.
• Les opérateurs stricts et larges changent le traitement des valeurs frontières.

4. Mesurer la complexité en temps et en mémoire

Comparer des algorithmes

La complexité décrit l’évolution du coût quand la taille d’entrée n augmente. $O(g(n))$ est une borne supérieure asymptotique, $\Omega(g(n))$ une borne inférieure et $\Theta(g(n))$ un encadrement des deux côtés. On ignore les constantes et les petits termes : 3n+5 est en $\Theta(n)$, tandis que deux boucles imbriquées de taille n donnent souvent $\Theta(n^2)$. La mémoire auxiliaire se mesure séparément de l’espace occupé par l’entrée.

Exemple guidé. Dans for i in range(n): for j in range(4): total += 1, l’instruction interne s’exécute 4n fois. Le coût est donc $\Theta(n)$, pas $\Theta(n^2)$, car 4 est une constante. En revanche, comparer chaque paire (i,j) avec deux bornes n produit environ $n^2$ itérations.

Limites et erreurs : annoncer $O(1)$ parce qu’une boucle a peu de lignes, confondre temps moyen et pire cas, ou oublier un tableau auxiliaire de taille n. Méthode : compter les opérations dominantes, simplifier, puis préciser le cas analysé. Point de contrôle : classer 1, log n, n, n log n, n² du plus lent au plus rapide quand n grandit.

Points-clés

• Les constantes disparaissent dans l’ordre asymptotique mais pas dans une mesure concrète.
• Deux boucles imbriquées ne suffisent pas à conclure sans examiner leurs bornes.
• Temps et mémoire auxiliaire sont deux ressources distinctes à analyser.

5. Tests, correction et traduction C/Python

Passer du code à la confiance

Un test vérifie un comportement sur une entrée choisie ; il ne prouve pas seul la correction générale. On combine cas nominal, limites, entrées invalides et propriétés générales. Pour une recherche linéaire, les tests doivent couvrir cible au début, au milieu, absente, tableau vide et doublons. Un raisonnement de correction suit souvent l’initialisation, la conservation d’un invariant, puis la terminaison.

Exemple guidé. Pour maximum, tester [3,8,2]→8, [-4,-2]→-2 et [5]→5. Le troisième test vérifie que la boucle peut ne faire aucun tour. L’assertion Python assert maximum([5]) == 5 échoue si l’algorithme initialise mal. En C, le prototype int maximum(const int a[], int n); rend le contrat visible, mais il faut décider comment signaler n==0 (code d’erreur, pointeur de résultat ou précondition).

Erreurs fréquentes : tester uniquement des exemples favorables, traduire and en &, ou oublier les types et conversions. Point de contrôle : proposer deux tests qui distinguent une recherche d’une première occurrence d’une recherche d’une dernière occurrence, puis nommer l’invariant utilisé.

Points-clés

• Les tests ciblent des classes de comportements, pas seulement des valeurs au hasard.
• Un invariant et la terminaison structurent une preuve de correction.
• Python et C partagent la logique mais pas la gestion des types et erreurs.

6. Récursivité, pile d’appels et décomposition

Cours magistral

Une définition qui se réduit elle-même

La récursivité décrit une fonction qui résout un problème en appelant la même fonction sur une instance plus petite. Elle n’est correcte que si trois conditions sont réunies : un ou plusieurs cas de base directement calculables, une réduction qui se rapproche effectivement d’un cas de base, et une combinaison des résultats qui respecte le contrat initial. Sans réduction stricte, l’exécution peut ne jamais terminer ; sans cas de base, les appels s’empilent jusqu’à l’erreur de pile.

Prenons la factorielle, définie pour un entier $n\geq 0$ par $0!=1$ et $n!=n\times(n-1)!$. Le paramètre est un entier sans unité, et chaque appel diminue $n$ d’une unité. La pile d’exécution conserve les appels suspendus : pour calculer $4!$, il faut attendre $3!$, puis $2!$, puis $1!$, avant de remonter en multipliant. La mémoire auxiliaire est donc proportionnelle à la profondeur, soit $\Theta(n)$, même si chaque étape ne crée qu’une valeur temporaire.

La correction se justifie par induction : le cas $n=0$ donne bien 1 ; si l’appel sur $n-1$ renvoie $(n-1)!$, la multiplication par $n$ renvoie exactement $n!$. Le temps vérifie $T(n)=T(n-1)+\Theta(1)$, donc $T(n)=\Theta(n)$. Une version itérative obtient le même temps avec $\Theta(1)$ mémoire ; la récursivité est choisie ici pour rendre la définition lisible, pas parce qu’elle est toujours moins coûteuse.

Une autre manière de lire cette technique consiste à séparer la descente et la remontée. La descente fabrique des sous-problèmes de plus en plus petits ; la remontée combine leurs réponses dans l’ordre inverse. Cette distinction devient importante lorsque plusieurs appels sont créés : la profondeur peut rester logarithmique si chaque sous-problème est suffisamment réduit, tandis que le nombre total d’appels peut être beaucoup plus grand. Pour analyser une fonction, on écrit donc la récurrence du temps et on mesure séparément la profondeur maximale de la pile.

Exemple résolu

Calculons factorielle(4). L’appel factorielle(4) suspend 4 × factorielle(3), puis 3 × factorielle(2), puis 2 × factorielle(1), puis 1 × factorielle(0). Le cas de base renvoie 1. La remontée donne successivement 1, 2, 6, puis 24. La trace confirme à la fois la terminaison et le résultat attendu. Quatre appels non terminaux ont été effectués ; le coût reste linéaire en $n$.

Erreurs fréquentes

Confondre récursion et répétition automatique, oublier que $0!=1$, réduire un paramètre qui ne tend pas vers le cas de base, ou annoncer une mémoire constante en oubliant les cadres d’appels. Une récursion sur une donnée vide doit aussi avoir un contrat explicite.

À retenir

Une récursion fiable associe base, réduction et combinaison. La pile explique le coût mémoire et la trace rend visibles les appels suspendus. Il faut comparer le coût de cette écriture à celui d’une boucle avant de choisir.

Points-clés

• Un cas de base et une réduction stricte sont nécessaires à la terminaison.
• La pile d’appels consomme une mémoire proportionnelle à la profondeur.
• Une preuve par induction accompagne naturellement la définition récursive.
• La récursivité améliore parfois la lisibilité sans améliorer le coût asymptotique.

7. Recherche dichotomique et invariants d’intervalle

Cours magistral

Réduire l’espace de recherche

La recherche dichotomique trouve une valeur dans un tableau trié par ordre croissant. Sa condition d’application essentielle est donc que le tableau soit déjà trié ; sans cette hypothèse, comparer la cible au milieu ne permet pas d’éliminer une moitié. On maintient un intervalle fermé $[g,d]$ contenant encore toutes les positions possibles. Le milieu est calculé par $m=g+\lfloor(d-g)/2\rfloor$, formule qui évite un dépassement d’entier contrairement à $(g+d)/2$ dans certains langages.

À chaque tour, si $A[m]$ égale la cible, on s’arrête. Si $A[m]$ est trop petit, toutes les positions de $g$ à $m$ sont impossibles et l’on pose $g=m+1$ ; sinon on pose $d=m-1$. L’invariant est : « si la cible apparaît, elle se trouve dans $[g,d]$ ». La largeur de l’intervalle est au moins divisée par deux ; après au plus $\lfloor\log_2 n\rfloor+1$ comparaisons, l’intervalle devient vide ou la cible est trouvée. Le temps est donc $O(\log n)$ et la mémoire auxiliaire $O(1)$ en version itérative.

La correction dépend des bornes exclusives après chaque comparaison. Le choix de retourner un indice ou une sentinelle comme $-1$ doit figurer dans le contrat. Si plusieurs occurrences existent, cette version renvoie une occurrence quelconque ; obtenir la première impose de poursuivre à gauche après une égalité et de mémoriser le meilleur indice.

Le logarithme exprime le nombre de divisions nécessaires, non une durée universelle : une comparaison sur des chaînes longues peut coûter davantage qu’une comparaison d’entiers. De même, le tri préalable n’est pas gratuit. Si le tableau doit être recherché une seule fois et n’est pas trié, un parcours linéaire peut être préférable ; si de nombreuses recherches suivent, le coût du tri peut être amorti. Le choix algorithmique dépend donc du scénario complet, pas du seul coût d’une boucle isolée.

Exemple résolu

Soit $A=[2,5,8,12,16,21,30]$ et la cible 16. Initialement $g=0$, $d=6$, donc $m=3$ et $A[3]=12$ : la cible est à droite, d’où $g=4$. Ensuite $m=5$, $A[5]=21$ : elle est à gauche, d’où $d=4$. Enfin $m=4$, $A[4]=16$ : l’algorithme renvoie 4. Pour la cible 7, les intervalles deviennent successivement $[0,2]$, puis $[2,2]$, puis $[2,1]$ ; l’intervalle vide prouve l’absence et impose $-1$.

Exemple d’application : premier horaire au-dessus d’un seuil

Les températures horaires triées sont $A=[12,15,17,20,24]$ et l’on cherche la première valeur au moins égale à $18$. Pour gérer les doublons et obtenir la première occurrence admissible, on utilise une dichotomie sur l’intervalle demi-ouvert $[g,d)$, initialisé à $[0,5)$. Au milieu $m=2$, $A[2]=17<18$, donc $g=3$. Ensuite $m=4$, $A[4]=24\ge18$, donc $d=4$. Enfin $m=3$, $A[3]=20\ge18$, donc $d=3$. Comme $g=d=3$, l’indice recherché est 3 et l’horaire correspondant vaut 20. L’invariant est que la première valeur admissible, si elle existe, est dans $[g,d)$; l’arrêt renvoie donc la borne inférieure plutôt qu’une occurrence quelconque. Le tableau doit être trié avant la recherche.

Erreurs fréquentes

Utiliser la méthode sur un tableau non trié, recalculer le milieu sans modifier une borne, écrire $g=m$ ou $d=m$ et créer une boucle infinie, ou confondre valeur 16 et indice 4. Les bornes doivent rester cohérentes avec l’invariant.

À retenir

Le gain logarithmique est acheté par une précondition de tri. Une trace des bornes suffit souvent à détecter une erreur d’indice. L’invariant et l’intervalle vide justifient respectivement la conservation et la terminaison.

Points-clés

• La recherche dichotomique exige un tableau trié.
• L’invariant est la conservation de toutes les positions encore possibles.
• Les mises à jour m+1 et m-1 garantissent la progression.
• Le temps est logarithmique et la mémoire itérative constante.

8. Tri par insertion : invariant, stabilité et coût

Cours magistral

Trier en agrandissant une zone ordonnée

Le tri par insertion traite les éléments de gauche à droite. À l’étape $i$, le préfixe $A[0..i-1]$ est déjà trié ; on extrait $A[i]$, décale vers la droite les valeurs strictement plus grandes, puis insère l’élément dans le trou. La condition d’application est un tableau indexable et modifiable, ou une représentation permettant des décalages équivalents. L’algorithme est stable si le test porte sur strictement « plus grand » : deux éléments égaux conservent alors leur ordre initial.

L’invariant de boucle est précisément que le préfixe traité est trié et contient les mêmes éléments qu’avant l’étape. Le décalage préserve le contenu ; l’insertion conserve l’ordre croissant, donc l’invariant est rétabli. À la fin, le préfixe est le tableau entier. Le nombre de décalages vaut $\Theta(n^2)$ dans le pire cas, lorsque les données sont décroissantes, et $\Theta(n)$ dans le meilleur cas déjà trié. La mémoire auxiliaire est $\Theta(1)$, mais le coût réel dépend aussi des écritures et des comparaisons.

Un pseudo-code explicite le raisonnement : `pour i de 1 à n-1, clé←A[i], j←i-1; tant que j≥0 et A[j]>clé, A[j+1]←A[j], j←j-1; A[j+1]←clé`. La boucle interne s’arrête soit au début du tableau, soit devant une valeur qui ne dépasse pas la clé. Il faut donc vérifier simultanément la borne $j\geq0$ et la comparaison, dans cet ordre en C pour ne pas lire une case négative.

Le tri est dit adaptatif lorsqu’il profite de l’état initial des données. Dans un tableau presque ordonné, peu d’éléments traversent une longue distance : le nombre de déplacements est alors proche du nombre d’inversions, c’est-à-dire de paires dans le mauvais ordre. Cette mesure explique pourquoi l’insertion peut battre une méthode théoriquement plus sophistiquée sur de petites entrées. Elle ne change toutefois pas le pire cas quadratique, qui doit rester annoncé pour une garantie générale.

Exemple résolu

Sur $[5,2,4,6]$, le préfixe initial $[5]$ est trié. La clé 2 décale 5 et donne $[2,5,4,6]$. La clé 4 décale 5 puis s’insère avant lui : $[2,4,5,6]$. La clé 6 ne provoque aucun décalage : le tableau reste $[2,4,5,6]$. Chaque étape conserve les éléments et agrandit le préfixe trié ; trois insertions ont donc suffi.

Erreurs fréquentes

Écraser la clé avant de l’avoir sauvegardée, décaler dans le mauvais sens, utiliser $\geq$ et perdre la stabilité, ou oublier le cas d’un tableau vide ou à un seul élément. Confondre « tableau presque trié » avec « coût toujours logarithmique » est également faux.

À retenir

Le tri par insertion est simple, en place et stable avec une comparaison stricte. Son invariant prouve la correction ; son avantage pratique apparaît surtout lorsque les déplacements sont peu nombreux.

Points-clés

• Le préfixe déjà parcouru reste trié à chaque étape.
• Une comparaison strictement supérieure préserve la stabilité.
• Le coût est linéaire dans le meilleur cas et quadratique dans le pire.
• L’algorithme utilise une mémoire auxiliaire constante et travaille en place.

9. Listes chaînées, piles et files : choisir la structure

Cours magistral

Des liens plutôt que des cases contiguës

Une liste chaînée est une suite de nœuds ; chaque nœud contient une valeur et une référence vers le suivant. Une référence nulle marque la fin. Cette représentation ne garantit pas l’accès direct par indice : atteindre le k-ième élément nécessite de suivre k liens, en $O(k)$, mais insérer en tête est $O(1)$ si l’on possède la tête. Elle convient lorsque la taille varie et que les insertions sont fréquentes, moins lorsque l’on veut parcourir rapidement par indice ou bénéficier de la localité mémoire d’un tableau.

Une pile applique LIFO : le dernier élément empilé est le premier dépilé. Une file applique FIFO : le premier arrivé est le premier sorti. Une pile peut être représentée par une tête de liste ; pour une file, on conserve idéalement deux références, tête et queue, afin que l’enfiler en queue et le défiler en tête restent en $O(1)$. Chaque opération doit préserver l’invariant structurel : une liste vide a une tête nulle, et une file vide a tête et queue nulles ensemble. Lorsqu’on retire le dernier élément, il faut remettre les deux références à zéro.

Ces structures modifient l’état, contrairement à une fonction pure qui renvoie seulement une valeur. Le contrat doit préciser le comportement sur une structure vide : erreur explicite, valeur sentinelle ou résultat optionnel. En C, les nœuds alloués doivent être libérés ; en Python, les références devenues inutiles sont récupérées automatiquement, mais une référence conservée par erreur peut prolonger leur durée de vie.

Exemple résolu

Construisons une file vide, puis enfilons 10, 20 et 30. Après 10, tête et queue désignent le même nœud. Après 20 puis 30, la tête reste sur 10 et la queue sur 30 ; les liens forment 10→20→30. Un défilement retire 10 et avance la tête sur 20. Un second retire 20. Le troisième retire 30 et la file redevient vide : tête et queue sont toutes deux nulles. L’ordre de sortie est donc 10, 20, 30, conformément à FIFO.

Erreurs fréquentes

Parcourir une liste comme un tableau, oublier de modifier le lien précédent lors d’une insertion, laisser une queue pointer vers un nœud retiré, ou dépiler une pile vide sans contrat. Une file implémentée par décalage dans un tableau peut devenir $O(n)$ par retrait ; une file circulaire ou deux indices évitent ce coût.

À retenir

Une structure de données est un contrat d’opérations et d’invariants, pas seulement une forme mémoire. Le choix dépend des opérations dominantes, de la mémoire disponible et du coût acceptable. Toujours traiter explicitement les transitions vide/non vide.

Points-clés

• Une liste chaînée privilégie les liens et les insertions locales, pas l’accès par indice.
• Une pile suit LIFO et une file suit FIFO.
• Une file efficace conserve une tête et une queue avec des invariants cohérents.
• Le contrat doit définir les opérations sur une structure vide et la gestion mémoire.

Exercices corrigés

Exercice 1 · Fondamental

Écrire une fonction somme_positifs(A) qui renvoie la somme des éléments strictement positifs d’un tableau d’entiers. Donner le résultat pour [-3, 4, 0, 6, -1] et préciser le cas du tableau vide.

Correction détaillée

1. Initialiser s=0, car la somme vide vaut 0. 2. Parcourir chaque x de A. 3. Ajouter x seulement si x>0. 4. Retourner s. Pseudo-code : s←0; pour x dans A : si x>0 alors s←s+x; retourner s. Sur l’entrée donnée, les ajouts sont 4 puis 6, donc le résultat vaut 10. Pour [], aucun tour n’a lieu et la fonction renvoie 0. L’invariant est : après chaque tour, s est la somme des positifs déjà visités. Le coût est Θ(n) en temps et O(1) en mémoire auxiliaire.

Exercice 2 · Fondamental

Écrire une recherche linéaire premiere_occurrence(A, cible) qui renvoie le premier indice de cible, ou -1 si elle est absente. Calculer le résultat sur A=[5,2,5,9] pour cible=5, puis sur cible=7.

Correction détaillée

1. Parcourir i de 0 à len(A)-1. 2. Dès que A[i]==cible, retourner i; cet arrêt garantit la première occurrence. 3. Après la boucle, retourner -1. Sur [5,2,5,9], l’indice 0 satisfait déjà le test : résultat 0, sans visiter l’indice 2. Pour 7, aucune égalité n’est rencontrée : résultat -1. L’invariant est que les indices strictement inférieurs à i ne contiennent pas la cible. Le meilleur cas est Θ(1), le pire cas Θ(n), et l’espace auxiliaire Θ(1).

Exercice 3 · Intermédiaire

Concevoir une fonction qui reçoit des notes réelles et renvoie la moyenne des notes au moins égales à 10 ainsi que leur nombre. Si aucune note ne vérifie le filtre, renvoyer (None, 0). Évaluer sur [8, 12, 15, 9, 10].

Correction détaillée

1. Initialiser s=0 et c=0. 2. Pour chaque note x, si x>=10, ajouter x à s et incrémenter c. 3. Si c==0, renvoyer (None,0) ; sinon renvoyer (s/c,c). Ici, les notes retenues sont 12, 15 et 10 : s=37, c=3, moyenne 37/3≈12,33. Le traitement de 10 confirme que la borne est large. L’invariant est que s et c décrivent exactement les notes admissibles déjà parcourues. Le temps est Θ(n), la mémoire Θ(1). Il faut documenter le type réel et éviter une division entière en C si l’on veut la moyenne décimale.

Exercice 4 · Intermédiaire

Écrire a_doublon(A) qui renvoie vrai si un tableau d’entiers contient au moins deux valeurs égales, faux sinon. Donner une solution sans structure supplémentaire, sa complexité et le résultat sur [4,1,7,4].

Correction détaillée

1. Comparer chaque paire d’indices avec i allant de 0 à n-2 et j allant de i+1 à n-1. 2. Si A[i]==A[j], retourner vrai immédiatement. 3. Si toutes les paires sont distinctes, retourner faux. Sur [4,1,7,4], la paire (0,3) contient deux 4 : résultat vrai. Il y a au plus n(n-1)/2 comparaisons, donc Θ(n²) dans le pire cas, et O(1) mémoire auxiliaire. L’arrêt anticipé peut améliorer le cas favorable. Une erreur classique consiste à comparer chaque case à elle-même, ce qui rendrait tout tableau non vide « doublonné ».

Exercice 5 · Avancé

Deux tableaux A et B sont triés par ordre croissant. Concevoir un algorithme qui produit un nouveau tableau trié contenant tous leurs éléments, puis justifier sa correction et sa complexité. Appliquer à A=[1,4,8], B=[2,4,7,9].

Correction détaillée

1. Placer deux indices i=j=0. 2. Tant que les deux tableaux ont des éléments, comparer A[i] et B[j], ajouter le plus petit au résultat et avancer l’indice correspondant ; en cas d’égalité, choisir l’un ou l’autre, puis l’autre sera ajouté ensuite. 3. Ajouter le suffixe restant. Application : 1,2,4,4,7,8,9. L’invariant est que le résultat contient exactement les plus petits éléments déjà consommés, dans l’ordre, et que tous les suffixes non parcourus restent supérieurs ou égaux à son dernier élément. À la terminaison, aucun élément n’est oublié : le résultat est trié et contient les deux entrées. Chaque élément est examiné une fois, donc Θ(n+m) temps et Θ(n+m) mémoire pour le nouveau tableau.

Quiz d’autoévaluation

Question 1

Quel indice est valide pour le dernier élément d’un tableau Python de longueur n ?

• n ✓ n-1 • n+1 • 1

Explication : Les indices commencent à 0 ; le dernier est donc n−1.

Question 2

Quelle valeur d’initialisation convient à une somme, y compris pour un tableau vide ?

✓ 0 • -1 • La première case obligatoire • La longueur du tableau

Explication : 0 est l’élément neutre de l’addition et permet de traiter l’entrée vide sans accès hors limites.

Question 3

Quel est le pire cas d’une recherche linéaire sur n éléments ?

• Θ(1) • Θ(log n) ✓ Θ(n) • Θ(n²)

Explication : La cible peut être absente ou être en dernière position : jusqu’à n comparaisons sont nécessaires.

Question 4

À quoi sert principalement un invariant de boucle ?

• À accélérer toujours le programme ✓ À décrire une propriété conservée pendant les tours • À remplacer les tests • À réserver la mémoire

Explication : L’invariant relie l’état courant au résultat partiel et aide à démontrer la correction.

Question 5

Quel ordre correspond à deux boucles imbriquées parcourant chacune n cases ?

• Θ(1) • Θ(log n) • Θ(n) ✓ Θ(n²)

Explication : La boucle interne s’exécute n fois pour chacun des n tours externes, soit n² itérations.

Question 6

Pourquoi tester un tableau vide pour une fonction de maximum est-il important ?

• Pour augmenter n ✓ Parce que le premier accès peut être invalide • Pour rendre le tri stable • Parce que la complexité devient logarithmique

Explication : Un algorithme qui initialise avec A[0] doit préciser une précondition ou traiter l’absence d’élément.

Question 7

Quel résultat renvoie une recherche de première occurrence sur [2,5,5] avec la cible 5 ?

• 0 ✓ 1 • 2 • -1

Explication : Le premier indice où la valeur vaut 5 est 1 ; l’arrêt immédiat préserve cette propriété.

Question 8

Que signifie Θ(n) dans une analyse asymptotique ?

• Une borne exacte pour chaque machine ✓ Un encadrement par des constantes multiples de n à partir d’un seuil • Toujours n opérations • Une complexité indépendante de n

Explication : Θ(n) signifie que le coût est borné supérieurement et inférieurement par des multiples constants de n pour n assez grand.

Glossaire

• Algorithme — Suite finie et non ambiguë d’étapes qui transforme des données d’entrée en résultat.
• Invariant de boucle — Propriété vraie avant et après chaque itération, utilisée pour raisonner sur la correction.
• Tableau — Structure séquentielle dont les éléments sont repérés par des indices, généralement contigus en mémoire en C.
• Précondition — Hypothèse qui doit être satisfaite avant l’appel d’une fonction, par exemple un tableau non vide.
• Complexité — Mesure de l’évolution du temps ou de la mémoire consommée en fonction de la taille de l’entrée.
• Recherche linéaire — Parcours séquentiel comparant successivement les éléments à une cible.
• Cas limite — Entrée située à une frontière du domaine, comme une liste vide, une seule valeur ou une cible absente.
• Test unitaire — Vérification automatisée d’une fonction isolée sur une entrée et une sortie attendue.

TP · Carnet de contacts en mémoire

Une petite association veut rechercher rapidement, dans un tableau de structures, les contacts de ses membres par nom. Le carnet reste en mémoire pendant l’exécution ; aucune base de données ni interface graphique n’est nécessaire.

Objectifs

• Modéliser un contact par un nom, un téléphone et une adresse électronique.

• Implémenter l’ajout borné, l’affichage et la recherche de première occurrence.

• Tester les cas vide, plein, doublon et recherche infructueuse.

• Mesurer et expliquer le coût linéaire de la recherche.

Étapes

1. Définir la structure Contact, la capacité maximale et un compteur nb ; écrire les préconditions de chaque fonction.

2. Implémenter ajouter en refusant un carnet plein et en copiant les champs du nouveau contact.

3. Implémenter rechercher_nom par parcours séquentiel, avec indice valide ou -1.

4. Ajouter un affichage contrôlé et un jeu de six tests couvrant les cas nominaux et limites.

5. Tracer le nombre de comparaisons sur 1, 10 et 100 contacts et rédiger une conclusion sur la complexité.

Livrables attendus

• Un fichier source Python ou C exécutable, commenté et séparant les fonctions de la démonstration.

• Un fichier de tests ou une sortie reproductible montrant les six cas demandés.

• Une note d’une page donnant le contrat, l’invariant de recherche et l’analyse de complexité.

Critères d’évaluation

• Fonctionnalité : ajout, recherche et affichage donnent les résultats attendus, y compris sur carnet vide ou plein.

• Robustesse : aucune lecture hors limites ; les doublons et noms absents sont traités explicitement.

• Raisonnement : contrats, invariant, cas testé et coût Θ(n) sont justifiés par des observations concrètes.

• Lisibilité : noms cohérents, fonctions courtes, tests reproductibles et séparation données/affichage.

Piste de résolution

Utiliser un tableau de capacité fixe et un entier nb. ajouter vérifie nb<capacite, écrit à l’indice nb, puis incrémente ce compteur. rechercher_nom parcourt les indices de 0 à nb-1, retourne le premier indice égal au nom et renvoie -1 après la boucle. L’invariant est que les indices déjà parcourus ne contiennent pas le nom recherché. Les tests doivent notamment vérifier que le sixième ajout est refusé si la capacité vaut cinq et que la recherche ne dépasse jamais nb.

Sujets originaux d’entraînement (non officiels)

Sujet original de préparation — Algorithmique 1, session normale

Sujet original d’entraînement non officiel; il ne provient pas d’une session d’examen antérieure. Ce sujet est une création pédagogique originale non officielle. Il ne s’agit jamais d’une épreuve d’une année passée ni d’une annale ; il sert uniquement à s’entraîner.

Exercice 1

Écrire compter(A, x) qui renvoie le nombre d’occurrences de x dans A. Donner un invariant et analyser le coût.

Correction : Initialiser c à 0, parcourir tous les indices et incrémenter c lorsque A[i]==x, puis retourner c. Après i cases, c est exactement le nombre d’occurrences dans le préfixe traité ; l’invariant est conservé par l’incrément. La boucle termine après n cases. Le coût est Θ(n) et la mémoire auxiliaire Θ(1).

Exercice 2

Pour A=[3,1,4,1,5], écrire un algorithme qui renvoie le minimum et son indice de première occurrence.

Correction : Initialiser m=A[0] et pos=0, puis parcourir i de 1 à n-1. Si A[i]<m, remplacer m et pos ; utiliser < et non <= pour conserver la première occurrence. La trace donne m=1 et pos=1. La précondition est n>0. L’invariant dit que m est le minimum du préfixe traité et pos sa première position. Coût Θ(n), mémoire Θ(1).

Exercice 3

Comparer la complexité de for i in range(n): s+=1 et de for i in range(n): for j in range(i): s+=1.

Correction : Le premier corps s’exécute n fois : Θ(n). Dans le second, le nombre d’exécutions vaut 0+1+...+(n-1)=n(n-1)/2, donc Θ(n²). La différence vient de la borne croissante de la boucle interne, même si elle ne parcourt pas toujours n cases.

Sujet original de préparation — Algorithmique 1, rattrapage

Sujet original d’entraînement non officiel; il ne provient pas d’une session d’examen antérieure. Ce sujet est une création pédagogique originale non officielle. Il ne s’agit jamais d’une épreuve d’une année passée ni d’une annale ; il sert uniquement à s’entraîner.

Exercice 1

Concevoir tous_pairs(A) qui renvoie vrai si chaque élément de A est distinct. Préciser le cas vide.

Correction : Pour chaque paire i<j, comparer A[i] et A[j] ; retourner faux dès égalité, sinon vrai après toutes les comparaisons. Le tableau vide et le tableau à un élément vérifient la propriété par absence de paire : vrai. Le pire cas comporte n(n-1)/2 comparaisons, donc Θ(n²), et la mémoire auxiliaire est Θ(1).

Exercice 2

Fusionner deux tableaux triés A=[0,6,10] et B=[2,6,8] sans trier le résultat après coup.

Correction : Maintenir i et j à zéro ; comparer les têtes et ajouter 0, puis 2, puis 6 de A et 6 de B selon la règle d’égalité choisie, puis 8 et 10. Résultat [0,2,6,6,8,10]. Les suffixes sont ajoutés à la fin. L’invariant garantit que le résultat partiel est trié et contient exactement les éléments consommés. Coût Θ(n+m).

Exercice 3

Une fonction renvoie la moyenne des valeurs positives mais divise par le nombre total de cases. Corriger l’idée et proposer deux tests révélateurs.

Correction : Maintenir simultanément s et c, en ajoutant une valeur seulement si elle est strictement positive et en incrémentant c dans le même cas ; renvoyer s/c si c>0, sinon une valeur explicitement documentée comme None ou une erreur. Les tests [2,-2] doivent donner 2, pas 1, et [-1,0] doit déclencher le traitement « aucune valeur », pas une division par zéro.

Parcours de révision sur quatre semaines

Semaine 1 · Spécification, fonctions et structures de contrôle

Réécrire cinq énoncés en préconditions/sorties, puis tracer des boucles de comptage et de maximum à la main. Avant de terminer, reformule les notions sans tes notes, vérifie les résultats dans le cours et note une difficulté précise à reprendre la semaine suivante.

Semaine 2 · Tableaux, recherches et cas limites

Coder somme, recherche et minimum en Python ou C ; ajouter des tests pour vide, singleton, doublon, absence et valeurs négatives. Avant de terminer, reformule les notions sans tes notes, vérifie les résultats dans le cours et note une difficulté précise à reprendre la semaine suivante.

Semaine 3 · Correction et complexité

Annoter trois algorithmes avec invariants, compter les opérations dominantes et classer leurs coûts en O, Ω ou Θ. Avant de terminer, reformule les notions sans tes notes, vérifie les résultats dans le cours et note une difficulté précise à reprendre la semaine suivante.

Semaine 4 · Synthèse et préparation aux sujets

Réaliser un sujet original en temps limité, corriger avec les invariants et refaire sans notes les questions échouées. Avant de terminer, reformule les notions sans tes notes, vérifie les résultats dans le cours et note une difficulté précise à reprendre la semaine suivante.