Spécifier un problème : entrée, sortie et étapes
Avant d'écrire du code, on décrit le problème avec précision. C'est la spécification.
- Entrée : les données reçues, leur type et leurs limites (par exemple « n nombres entiers, 1 ≤ n ≤ 1000 »).
- Sortie : ce qu'on doit renvoyer (par exemple « le plus grand d'entre eux »).
- Conditions : ce qui est vrai avant (précondition) et après (postcondition).
Écrire les étapes
Un algorithme est une liste finie d'étapes claires qui transforme toute entrée valide en la bonne sortie. On peut l'écrire :
- en langage naturel : « Regarde chaque nombre ; s'il est plus grand que le meilleur jusqu'ici, retiens-le. »
- en liste numérotée : 1. meilleur ← premier nombre. 2. Pour chaque nombre suivant x : si x > meilleur alors meilleur ← x. 3. Afficher meilleur.
- en pseudo-code ou en organigramme pour être plus précis.
Teste-le à la main sur de petites entrées, y compris les cas piégeux (tous égaux, nombres négatifs, un seul nombre).
Conception descendante et ascendante
Descendante (raffinement progressif) : on part de la tâche entière, on la coupe en quelques grandes étapes, puis on recoupe chaque étape jusqu'à ce que chaque partie soit facile à programmer. Exemple : « Faire un bulletin » → lire les notes → calculer les moyennes → donner les appréciations → afficher.
Ascendante : on construit et on teste d'abord de petits morceaux réutilisables (une fonction qui trouve le maximum, une autre qui trie), puis on les assemble en programme complet.
Dans les vrais projets, on mélange les deux : on planifie de haut en bas, on construit et on teste de bas en haut.
Diviser pour régner et la méthode de la dichotomie
Diviser pour régner se fait en trois temps : découper le problème en parties plus petites du même genre, résoudre chaque partie (souvent par récursivité), combiner les réponses.
- Recherche dichotomique (couper en deux) : dans une liste triée, on compare avec le milieu et on jette une moitié. n éléments demandent environ log₂ n vérifications : 16 → 4, 1 000 000 → 20.
- Tri fusion : on coupe la liste en deux, on trie chaque moitié, puis on fusionne : O(n log n).
- Puissance rapide : a⁸ = ((a²)²)² : 3 multiplications au lieu de 7.
- Racine par dichotomie : on coupe en deux un intervalle où la fonction change de signe.
Les algorithmes gloutons
Un algorithme glouton fait le choix qui paraît le meilleur tout de suite et ne le change jamais.
- Rendre la monnaie avec 50, 20, 10, 5, 2, 1 : la plus grosse pièce d'abord. C'est optimal pour ce genre de système de pièces.
- Choisir le plus d'activités possible dans une journée : prendre toujours celle qui finit le plus tôt. Optimal.
- Sac à dos fractionnable : prendre d'abord les objets qui ont la meilleure valeur par kg. Optimal.
Mais le glouton n'a pas toujours raison : avec les pièces 1, 3, 4, payer 6 en glouton donne 4 + 1 + 1 (3 pièces), alors que 3 + 3 n'en utilise que 2. Pour faire confiance à une méthode gloutonne, il faut la prouver, ou la comparer à une méthode sûre.
Programmation dynamique et retour sur trace
Programmation dynamique (PD)
Quand les mêmes petits problèmes reviennent, on résout chacun une seule fois et on range la réponse dans un tableau. Nombre minimal de pièces pour le montant a : best[a] = 1 + min(best[a - c]) sur les pièces c ≤ a, en partant de best[0] = 0. Pour les pièces 1, 3, 4 : best = 0, 1, 2, 1, 1, 2, 2. Remplir le tableau du petit au grand est ascendant ; la récursivité avec une mémoire est descendante (mémoïsation). Voir la leçon séparée sur la programmation dynamique.
Retour sur trace
On construit une solution un choix à la fois. Si un choix casse une règle ou mène à une impasse, on l'annule et on essaie l'option suivante. On l'utilise pour les labyrinthes, le sudoku, le problème des N reines et la liste de tous les sous-ensembles. C'est une force brute soignée : elle saute des branches entières qui ne peuvent pas marcher.
Force brute
On essaie toutes les réponses possibles. Toujours correct, mais souvent beaucoup trop lent (2ⁿ sous-ensembles, n! ordres).
Choisir une technique : correction, efficacité et structures de données
| Technique | À utiliser quand | Exemple | Temps typique |
|---|---|---|---|
| Force brute | l'entrée est minuscule | essayer tous les codes à 3 chiffres | souvent 2ⁿ ou n! |
| Diviser pour régner | les parties sont indépendantes | recherche dichotomique, tri fusion | O(log n), O(n log n) |
| Glouton | un bon choix local est prouvé sûr | choix d'activités, rendu de monnaie | O(n log n) |
| Programmation dynamique | les sous-problèmes se répètent | rendu de monnaie, plus courts chemins | taille du tableau |
| Retour sur trace | recherche avec des règles | labyrinthe, sudoku | exponentiel, mais élagué |
Justifier son choix
Correction : montrer que l'algorithme s'arrête toujours et donne la bonne sortie (un invariant de boucle, une preuve, ou des tests sur les cas limites). Efficacité : compter les étapes quand n grandit (grand O) et comparer avec les autres méthodes.
Les structures de données aident
Les tableaux pour les tables (PD), les piles pour le retour sur trace (se souvenir d'où revenir), les files pour un parcours niveau par niveau. Un arbre binaire range les éléments de façon que chaque nœud ait au plus deux enfants ; dans un arbre binaire de recherche, les clés plus petites vont à gauche et les plus grandes à droite, donc la recherche coupe le travail en deux à chaque niveau, comme la recherche dichotomique.
À toi de jouer : pièces et jeu de devinettes
- Joue au jeu « devine le nombre de 1 à 100 » avec un ami. Demande toujours par rapport au milieu. Peux-tu toujours gagner en 7 questions ? (2⁷ = 128.)
- Avec les pièces 1, 3, 4, écris sur papier le tableau de PD pour les montants de 0 à 10. Où le glouton échoue-t-il ?
- Ouvre la dernière étape 3D. Essaie les pièces 1, 7, 10 et le montant 14. Le glouton donne 10 + 1 + 1 + 1 + 1 ; la PD donne 7 + 7.
- Écris une liste d'étapes pour « trouver le plus petit nombre d'une liste » et teste-la sur 5, 5, 5 et sur un seul nombre.
Formules et définitions clés
- Spécification = entrée + sortie + conditions
- Dichotomie : environ log₂ n étapes (16 → 4, 1024 → 10)
- PD des pièces : best[0] = 0 ; best[a] = 1 + min best[a - c]
- Diviser pour régner = découper + résoudre + combiner
- Le glouton est rapide mais son optimalité doit être prouvée
Exemples résolus
1. Écris une spécification et une liste d'étapes pour trouver le plus grand de n nombres.
Entrée : n ≥ 1 nombres. Sortie : le plus grand. Étapes : 1. meilleur ← premier nombre. 2. Pour chaque autre nombre x : si x > meilleur, meilleur ← x. 3. Afficher meilleur. Pour 4, 9, 2, 7, 12, 5, 10, 3, la sortie est 12 après 7 comparaisons.
2. Combien de questions la dichotomie demande-t-elle pour trouver un nombre de 1 à 1000 ?
Chaque question coupe l'intervalle en deux : 1000 → 500 → 250 → 125 → 63 → 32 → 16 → 8 → 4 → 2 → 1. Cela fait 10 questions (2¹⁰ = 1024 ≥ 1000).
3. Payer 87 en glouton avec les pièces 50, 20, 10, 5, 2, 1.
50 (reste 37), 20 (17), 10 (7), 5 (2), 2 (0) : 50 + 20 + 10 + 5 + 2 = 5 pièces.
4. Remplis le tableau de PD pour les pièces 1, 3, 4 jusqu'au montant 7.
best[0]=0, [1]=1, [2]=2, [3]=1, [4]=1, [5]=min(best4, best2, best1)+1=2, [6]=min(best5, best3, best2)+1=2, [7]=min(best6, best4, best3)+1=2 (3 + 4).
5. Activités (début-fin) : A 9-11, B 10-12, C 11-13, D 12-14, E 13-15. Choisis le plus d'activités qui ne se chevauchent pas.
Glouton par fin la plus tôt : A (finit à 11), puis C (commence à 11, finit à 13), puis E (commence à 13). 3 activités : A, C, E.
6. Planifie de haut en bas : un programme qui donne à une classe sa moyenne et le meilleur élève.
Niveau 1 : lire les données → calculer → afficher. Niveau 2 : lire les noms et les notes dans des listes ; calculer le total et la moyenne ; trouver la note maximale et son nom ; afficher les deux. Chaque morceau est ensuite programmé et testé de bas en haut.
Erreurs fréquentes
- Commencer à coder avant d'avoir dit l'entrée et la sortie. Beaucoup de « bugs » sont en fait une spécification floue.
- Croire que le glouton est toujours optimal. Il ne marche que si on peut le prouver (les pièces 1, 3, 4 le mettent en défaut).
- Utiliser la recherche dichotomique sur une liste non triée. Couper en deux demande des données triées.
- Confondre PD et diviser pour régner. La PD sert pour des sous-problèmes qui se chevauchent et qu'on mémorise ; diviser pour régner découpe en parties indépendantes.