Fiche pédagogique du chapitre

Objectifs d’apprentissage

À la fin de ce chapitre, l’étudiant devra être capable de :

• transformer un besoin exprimé en langage naturel en spécifications fonctionnelles et techniques ;

• sélectionner les structures de données et les algorithmes les plus adaptés à un contexte donné ;

• découper une application en modules cohérents, testables et faiblement couplés ;

• rédiger des pseudo-codes précis avant de commencer l’implémentation ;

• construire des jeux de tests couvrant les cas normaux, limites et erronés ;

• justifier la correction et la complexité des opérations essentielles ;

• produire une documentation technique et utilisateur claire ;

• présenter et défendre les choix algorithmiques réalisés.

Prérequis

• tableaux, listes chaînées, piles, files, deques et tables de hachage ;

• arbres, tas et files de priorité ;

• algorithmes de tri et de recherche ;

• récursivité, programmation dynamique, méthodes gloutonnes et retour sur trace ;

• représentation et parcours de graphes ;

• analyse de complexité temporelle et spatiale ;

• fonctions, procédures, structures et modularité.

Organisation indicative

Plan du chapitre

18.1 — Démarche générale d’un projet algorithmique

Un projet de synthèse mobilise plusieurs notions du cours dans une application cohérente. La réussite dépend moins de la quantité de code que de la qualité de la démarche suivie. Une solution simple, correctement structurée et soigneusement testée est préférable à une application très ambitieuse mais fragile ou mal documentée.

18.1.1 Analyse du besoin

L’analyse transforme une idée générale en objectifs observables. Elle doit préciser les utilisateurs, les opérations qu’ils pourront effectuer, les données manipulées, les règles de gestion et les contraintes techniques.

18.1.2 Spécifications fonctionnelles

Une fonctionnalité doit être formulée comme une action vérifiable. Par exemple, « rechercher un étudiant par numéro » est plus précis que « gérer les étudiants ». Chaque fonctionnalité doit indiquer ses entrées, son résultat, ses préconditions et les erreurs possibles.

18.1.3 Choix des structures de données

Le choix doit partir des opérations dominantes. Une table de hachage convient aux recherches exactes fréquentes, un tas à l’extraction répétée de la meilleure priorité, une file à l’ordre d’arrivée, un graphe aux relations entre entités, et un tableau trié aux recherches dichotomiques et aux parcours séquentiels.

18.1.4 Découpage modulaire

Chaque module doit avoir une responsabilité principale. Le module de données ne doit pas gérer l’affichage, et l’interface ne doit pas contenir directement les algorithmes complexes. Cette séparation améliore les tests, la maintenance et la réutilisation.

18.1.5 Cycle progressif de réalisation

1. Produire une version minimale avec une structure vide, un menu et une opération simple.

2. Ajouter une fonctionnalité à la fois et la tester immédiatement.

3. Séparer les fonctions longues en opérations plus petites.

4. Introduire les contrôles d’erreurs et les cas limites.

5. Mesurer les performances sur des tailles croissantes.

6. Refactoriser sans modifier le comportement observable.

7. Finaliser la documentation et préparer la démonstration.

18.2 — Gestion d’un réseau de transport

Contexte et objectif

L’application représente un réseau de bus, de tramway ou de navettes. Chaque arrêt constitue un sommet et chaque liaison une arête ou un arc. Le système doit permettre d’ajouter des arrêts, de déclarer des liaisons et de rechercher un itinéraire entre deux points.

Objectifs pédagogiques

• mobiliser les graphes et les listes d’adjacence ;

• utiliser BFS pour un itinéraire contenant un nombre minimal de liaisons ;

• reconstruire un chemin avec un tableau de prédécesseurs ;

• gérer les arrêts inconnus, les réseaux déconnectés et les doublons.

Fonctionnalités minimales

• ajouter, modifier et supprimer un arrêt ;

• ajouter ou retirer une liaison entre deux arrêts ;

• afficher les voisins directs d’un arrêt ;

• tester l’existence d’un chemin ;

• retourner un itinéraire minimisant le nombre de correspondances ;

• afficher les composantes du réseau ou les arrêts inaccessibles.

Structures de données recommandées

Découpage en modules

Jeux d’essai essentiels

Analyse de complexité attendue

Extensions possibles

• associer un temps ou une distance aux liaisons ;

• gérer des lignes et des correspondances ;

• importer les données depuis un fichier ;

• proposer plusieurs itinéraires ;

• visualiser le réseau de manière graphique.

18.3 — Moteur de recherche dans un dictionnaire

Contexte et objectif

Le système stocke des mots accompagnés d’une définition, d’une catégorie ou d’exemples. Il doit permettre la recherche exacte, la consultation alphabétique et éventuellement les suggestions par préfixe.

Objectifs pédagogiques

• combiner table de hachage et structure ordonnée ;

• comparer recherche exacte, recherche dichotomique et parcours par préfixe ;

• normaliser les chaînes pour gérer casse et espaces ;

• concevoir une interface de recherche robuste.

Fonctionnalités minimales

• ajouter un mot et empêcher les doublons ;

• modifier ou supprimer une entrée ;

• retrouver exactement un mot ;

• afficher les mots dans l’ordre alphabétique ;

• rechercher tous les mots commençant par un préfixe ;

• afficher un message clair lorsqu’aucun résultat n’est trouvé.

Structures de données recommandées

Découpage en modules

Jeux d’essai essentiels

Analyse de complexité attendue

Extensions possibles

• ajouter un historique des recherches ;

• proposer des corrections pour une faute simple ;

• calculer les mots les plus consultés ;

• gérer plusieurs langues ;

• ajouter des synonymes et des relations entre mots.

18.4 — Gestionnaire de tâches avec priorités

Contexte et objectif

L’application gère des tâches caractérisées par un identifiant, une description, une priorité, une échéance et un état. L’utilisateur doit pouvoir insérer des tâches et extraire rapidement celle qui doit être traitée en premier.

Objectifs pédagogiques

• utiliser un tas comme file de priorité ;

• définir une règle de comparaison multicritère ;

• maintenir la cohérence lors des mises à jour de priorité ;

• conserver un historique des tâches terminées.

Fonctionnalités minimales

• créer une tâche avec priorité et échéance ;

• consulter la prochaine tâche à exécuter ;

• extraire et marquer la tâche prioritaire comme terminée ;

• modifier la priorité d’une tâche ;

• annuler une tâche ;

• afficher les tâches en attente et l’historique.

Structures de données recommandées

Découpage en modules

Jeux d’essai essentiels

Analyse de complexité attendue

Extensions possibles

• gérer des dépendances entre tâches sous forme de graphe ;

• détecter les tâches en retard ;

• ajouter des catégories et filtres ;

• sauvegarder automatiquement l’état ;

• simuler un ordonnanceur de processeur.

18.5 — Système de réservation avec file d’attente

Contexte et objectif

Le système gère un événement ou une ressource de capacité limitée. Lorsque toutes les places sont occupées, les nouvelles demandes sont placées en file d’attente. Une annulation libère une place et déclenche la promotion de la première demande admissible.

Objectifs pédagogiques

• appliquer correctement le principe FIFO ;

• combiner file, dictionnaire et ensembles pour garantir l’unicité ;

• maintenir des invariants de capacité ;

• traiter les annulations et promotions de manière atomique.

Fonctionnalités minimales

• créer une ressource avec une capacité ;

• enregistrer une réservation confirmée si une place existe ;

• placer la demande en attente sinon ;

• annuler une réservation ou une demande en attente ;

• promouvoir automatiquement la première personne en attente ;

• afficher le nombre de places et la position dans la file.

Structures de données recommandées

Découpage en modules

Jeux d’essai essentiels

Analyse de complexité attendue

Extensions possibles

• gérer plusieurs événements ;

• introduire une priorité pour certains profils ;

• ajouter une date limite de confirmation ;

• produire des statistiques de remplissage ;

• simuler les arrivées et annulations.

18.6 — Analyse d’un réseau social

Contexte et objectif

Les utilisateurs sont représentés par des sommets et les relations par des arêtes. Le programme doit permettre de gérer les relations, de rechercher des chemins de connaissance et d’analyser la structure du réseau.

Objectifs pédagogiques

• modéliser un domaine réel par un graphe ;

• appliquer DFS et BFS à des questions concrètes ;

• calculer degrés, composantes et distances ;

• protéger la cohérence des relations symétriques.

Fonctionnalités minimales

• ajouter et supprimer un utilisateur ;

• ajouter ou retirer une relation ;

• afficher les contacts directs ;

• calculer le nombre minimal d’intermédiaires entre deux personnes ;

• déterminer si le réseau est connexe ;

• identifier les composantes et les utilisateurs les plus connectés.

Structures de données recommandées

Découpage en modules

Jeux d’essai essentiels

Analyse de complexité attendue

Extensions possibles

• suggérer des contacts par amis communs ;

• calculer un coefficient de proximité simplifié ;

• gérer des relations orientées « suivre » ;

• importer un réseau volumineux ;

• visualiser les composantes.

18.7 — Gestion d’un catalogue avec table de hachage

Contexte et objectif

Le catalogue peut contenir des livres, produits, composants ou ressources pédagogiques. Chaque élément est identifié par une clé unique. Le projet doit rendre visibles les bénéfices et limites du hachage, notamment les collisions et le redimensionnement.

Objectifs pédagogiques

• implémenter une table de hachage ou instrumenter une structure existante ;

• gérer collisions, suppression et redimensionnement ;

• comparer plusieurs fonctions ou stratégies de hachage ;

• mesurer le facteur de charge et les performances.

Fonctionnalités minimales

• ajouter, rechercher, modifier et supprimer un article ;

• détecter les clés dupliquées ;

• afficher le facteur de charge ;

• redimensionner la table au-delà d’un seuil ;

• produire des statistiques sur les collisions ;

• filtrer ou trier les articles pour l’affichage.

Structures de données recommandées

Découpage en modules

Jeux d’essai essentiels

Analyse de complexité attendue

Extensions possibles

• comparer chaînage séparé et adressage ouvert ;

• tester plusieurs tailles de table ;

• ajouter un cache des recherches fréquentes ;

• gérer les seuils de stock ;

• produire un rapport expérimental sur les collisions.

18.8 — Résolution automatique d’un labyrinthe

Contexte et objectif

Le labyrinthe est une matrice contenant des cases libres, des obstacles, une entrée et une sortie. Chaque case libre est un sommet implicite relié à ses voisines accessibles. Le système doit rechercher un chemin et afficher sa trace.

Objectifs pédagogiques

• modéliser un graphe sans construire explicitement toutes ses arêtes ;

• comparer DFS et BFS ;

• reconstruire un chemin à partir des prédécesseurs ;

• gérer les limites de la grille et les labyrinthes sans solution.

Fonctionnalités minimales

• charger ou saisir une grille ;

• valider l’existence d’une entrée et d’une sortie ;

• rechercher un chemin quelconque avec DFS ;

• rechercher un chemin minimal avec BFS ;

• marquer et afficher les cases du chemin ;

• comparer le nombre de cases explorées.

Structures de données recommandées

Découpage en modules

Jeux d’essai essentiels

Analyse de complexité attendue

Extensions possibles

• générer aléatoirement des labyrinthes ;

• autoriser des déplacements diagonaux ;

• associer un coût à certaines cases ;

• animer l’exploration ;

• comparer avec une méthode heuristique en extension.

18.9 — Comparateur d’algorithmes de tri

Contexte et objectif

L’application exécute plusieurs algorithmes sur les mêmes données, vérifie les résultats et mesure le nombre de comparaisons, d’échanges, de déplacements, le temps et la mémoire auxiliaire.

Objectifs pédagogiques

• relier analyse théorique et mesures expérimentales ;

• concevoir une instrumentation non ambiguë ;

• générer des jeux de données reproductibles ;

• interpréter les résultats sans se limiter au temps brut.

Fonctionnalités minimales

• implémenter au moins quatre tris parmi sélection, bulles, insertion, fusion, rapide et tas ;

• copier le tableau initial avant chaque essai ;

• mesurer comparaisons et déplacements ;

• tester des données aléatoires, triées, inversées et presque triées ;

• vérifier automatiquement que le résultat est trié ;

• produire un tableau ou un fichier récapitulatif.

Structures de données recommandées

Découpage en modules

Jeux d’essai essentiels

Analyse de complexité attendue

Extensions possibles

• produire des graphiques de performance ;

• concevoir un choix automatique de l’algorithme ;

• tester la stabilité avec des enregistrements ;

• analyser l’effet du pivot dans le tri rapide ;

• comparer une version récursive et une version itérative.

18.10 — Éléments attendus dans chaque projet

18.10.1 Analyse du besoin

Le dossier doit présenter le contexte, les utilisateurs, les fonctionnalités, les entrées et sorties, les règles de gestion, les erreurs et les limites du périmètre. Une fonctionnalité non demandée mais ajoutée doit être clairement identifiée comme extension.

18.10.2 Choix des structures de données

Chaque structure choisie doit être reliée aux opérations les plus fréquentes. Le dossier doit également mentionner au moins une alternative et expliquer pourquoi elle a été écartée.

18.10.3 Découpage en modules

Le découpage doit être visible dans l’organisation du code et dans un diagramme simple. Les dépendances entre modules doivent être orientées vers des interfaces stables.

18.10.4 Pseudo-code

Les opérations importantes doivent être décrites en pseudo-code avant leur traduction. Le pseudo-code doit expliciter les entrées, sorties, conditions d’arrêt, invariants et erreurs. Il ne doit pas reproduire mot à mot la syntaxe d’un langage particulier.

18.10.5 Implémentation

• respecter une convention de nommage constante ;

• éviter les variables globales non justifiées ;

• limiter la taille des fonctions ;

• séparer les calculs de l’affichage ;

• centraliser les validations répétées ;

• documenter les interfaces publiques ;

• utiliser un système de versions et des commits compréhensibles.

18.10.6 Jeux de tests

Les tests doivent couvrir les opérations isolées et les scénarios complets. Ils doivent indiquer les données, le résultat attendu, le résultat obtenu et le statut du test.

18.10.7 Analyse de complexité

L’analyse doit porter sur les opérations principales, dans le meilleur cas et le pire cas lorsque la distinction est utile. Les hypothèses doivent être explicites : table de hachage bien répartie, graphe représenté par listes d’adjacence, tas équilibré par définition, etc.

18.10.8 Documentation

18.11 — Planification et organisation du travail

18.11.1 Jalons recommandés

18.11.2 Travail individuel ou en équipe

Le projet peut être réalisé individuellement ou par groupes de deux à quatre étudiants. Dans une équipe, les tâches doivent être distribuées sans créer des sous-projets indépendants qui ne seraient assemblés qu’à la fin.

18.11.3 Journal de suivi

18.12 — Validation, qualité et performance

18.12.1 Invariants à vérifier

• un identifiant unique n’apparaît pas deux fois ;

• la taille annoncée correspond au nombre réel d’éléments ;

• les indices d’un tas restent cohérents après un échange ;

• une relation non orientée est présente dans les deux listes de voisins ;

• le nombre de places confirmées ne dépasse jamais la capacité ;

• un chemin retourné relie réellement le départ à l’arrivée ;

• un tri conserve exactement les mêmes éléments que l’entrée.

18.12.2 Validation automatique

18.12.3 Mesure des performances

1. Choisir une opération et définir précisément ce qui est mesuré.

2. Générer plusieurs tailles de données et fixer les graines aléatoires.

3. Répéter chaque essai pour réduire l’influence du bruit.

4. Séparer le temps de génération des données du temps de l’algorithme.

5. Présenter les résultats sous forme de tableau ou de graphique.

6. Comparer la tendance mesurée à la complexité théorique.

7. Interpréter les écarts en tenant compte du langage et de l’implémentation.

18.12.4 Erreurs fréquentes

18.13 — Évaluation du projet

18.13.1 Grille proposée sur 100 points

18.13.2 Critères éliminatoires ou plafonnants

• projet non exécutable ou dépendances non documentées ;

• absence de contribution identifiable d’un membre ;

• pseudo-code ou code copié sans compréhension démontrée ;

• données de test absentes ou résultats falsifiés ;

• fonctionnalité centrale non implémentée ;

• rapport ne correspondant pas à la version livrée.

18.13.3 Déroulement conseillé de la soutenance

18.14 — Ateliers préparatoires

Atelier 1 — Transformer un besoin en fonctionnalités

Pour le système de réservation, rédiger cinq fonctionnalités sous la forme « acteur + action + résultat observable », puis préciser une erreur possible pour chacune.

Correction indicative

Atelier 2 — Choisir une structure

Associer chaque besoin à une structure et justifier le choix : historique d’annulation, utilisateurs par identifiant, tâches urgentes, relations sociales, demandes en attente, résultats triés.

Correction indicative

Atelier 3 — Décomposer un module trop long

Une fonction TraiterCommande lit une saisie, valide les données, modifie la structure, sauvegarde un fichier et affiche un message. Proposer un découpage modulaire.

Correction indicative

Atelier 4 — Construire une matrice de tests

Pour une fonction de recherche d’itinéraire, proposer au moins six tests appartenant à des catégories différentes.

Correction indicative

Atelier 5 — Analyser la complexité

Dans un réseau social représenté par listes d’adjacence, analyser : ajout d’un utilisateur, ajout d’une relation, calcul des composantes, tri des utilisateurs par degré.

Correction indicative

Checklist de livraison

Synthèse du chapitre

Glossaire

Auto-évaluation