1 - Alice déménage mais à quel coût ?
Qu'est-ce que l'algorithmique ?
Sans doute un des mots les plus mystérieux et opaque dans la tête des personnes qui n'ont jamais été sensibilisées à l'informatique.
On entend souvent 'c'est à cause de l'algorithme", "c'est l'algorithme qui décide"... Ca à l'air bien ennuyeux de laisser l'ordinateur choisir, non ?
Nous allons voir que tous cela est plus ou moins faux, comme avec Parcours sup. Après tout, quelqu'un a bien décidé du fonctionnement, non ?
Après avoir vu cette partie en 1er, vous pourrez répondre à ces questions
- A quoi sert l'algorithmique ?
- Comment savoir si un algorithme fonctionne ?
- Comment garantir qu'un algorithme s'arrête ?
- Comment comparer des algorithmes entre eux pour prendre le "meilleur" ?
D'après une idée originale du groupe Algorithmique de l'IREM de Grenoble et dont je n'utilise qu'une toute petite partie (aujourd'hui) : PDF
Evaluation ✎ : question 13
Documents de cours : open document ou pdf
Documents à imprimer : open document ou pdf
1 - Où est ce carton ?
Alice déménage, malheureusement, elle s'est cassé le bras. Avec un plâtre, elle n'a plus qu'une main pour manipuler tous ces cartons... Elle va appelle ses amis à la rescousse.
Pourquoi ? Pour les ranger proprement et optimiser la place dans le camion !
Avant l'arrivée de ses amis, elle décide de remettre la main sur le carton qui contient les boîtes de gâteaux.
01° Prendre les 24 cartons et les répartir au hasard sur votre table en les retournant pour ne pas pouvoir voir le numéro. Pourquoi ? Tout simplement car un ordinateur ne peut pas avoir une vue d'ensemble comme un humain. Il ne peut lire qu'une variable à la fois.
02° Vous êtes Alice (et vous n'avez qu'un bras valide en ce moment, n'oubliez pas !). Le carton des gâteaux est le carton numéro 9. Vous ne pouvez inspecter qu'un carton à la fois. Pour cela, vous avez uniquement le droit de retourner un carton à la fois :
- Si c'est le bon, vous avez fini, bravo !
- Sinon, il faut replacer le carton face caché exactement au même endroit que là où vous l'avez pris.
Deux questions :
- combien de cartons avez-vous dû regarder avant de trouver le bon ?
- Quel est le problème qu'on pourrait rencontrer en n'étant pas assez attentif (ou si on avait 1000 cartons) ?
...CORRECTION...
Potentiellement entre
- 1 carton (bravo, vous avez de la chance !)
- beaucoup beaucoup de cartons : pas de chance et vous avez oublié quel carton vous avez déjà fouillé. Du coup, vous avez fouillé le même carton plusieurs fois sans vous en rendre compte !
Comme vous n'êtes pas venus ici pour jouer à Memory, et que nous voulons éviter de boucler à l'infini, nous allons plutôt ordonner nos cartons. Cela ne va rien changer à l'aspect "avoir eu de la chance" mais cela va grandement aider du cé de l'aspect "être attentif".
03° Prendre les cartons et les placer aléatoirement (face cachée) mais cette fois alignés les uns à côté des autres.
Vous devriez donc obtenir une ou deux lignes sur votre table.
Questions :
- combien de cartons avez-vous dû regarder avant de trouver le carton portant le numéro 9 ?
- en ayant beaucoup de chance, combien de recherches dans le meilleur des cas ?
- en n'ayant vraiment pas de chance, combien de recherches dans le pire des cas ?
- en n'ayant vraiment pas de chance, combien de recherches dans le pire des cas si on avait 1000 cartons plutôt que 24 ?
- en n'ayant vraiment pas de chance, combien de recherches dans le pire des cas si on avait 1 million de cartons ?
...CORRECTION...
On retrouve presque le même cas qu'auparavant. Entre 1 et 24.
Mais dans le pire des cas, on aura 24 recherches au maximum, jamais plus. Il suffit de suivre l'ordre des cartons : plus moyen d'en louper un ou de chercher dans le même plusieurs fois de suite.
Dans le pire des cas, 1000 recherches pour mille cartons.
Dans le pire des cas, 1 000 000 de recherches pour un million de cartons.
04° Bob, l'ami d'Alice arrive. Il va pouvoir aider Alice à trouver le carton 14 qui contient les clés du camion pendant qu'Alice continue sa propre recherche.
- donner les instructions précises (en français) qu'Alice doit donner à Bob pour chercher le carton numéro 14 en garantissant qu'on ne cherche jamais deux fois à l'intérieur du même carton ?
- en appliquant ces instructions, combien de cartons avez-vous dû regarder pour savoir si le carton 14 existe (ou pas) ?
- combien d'observations aurait-on dû faire si on avait 1000 cartons ?
- combien d'observations aurait-on dû faire si on avait 1 million de cartons ?
...CORRECTION...
Deux solutions utilisant juste des phrases mais où on retrouve les outils de base de l'informatique. Si vous avez pensé à l'écrire ainsi, chapeau.
1er solution
Pour chaque carton (en commençant par celui de gauche), vérifier si ce carton est le bon. Si c'est le cas, ramener le carton immédiatement.
2e solution
Commence par vérifier le premier carton. Tant qu'il reste des cartons à vérifier et que le carton actuel n'est pas le bon, passe au carton suivant.
3e solution
Prendre le premier carton
Lire et mémoriser son numero
TANT QUE vous n'avez pas trouvé le bon numero de carton et qu'il reste un carton à droite
Prendre le carton suivant
Lire et mémoriser son numero
SI c'est n'est pas le bon numero de carton
Reposer le carton face cachée
Fin SI
Fin TANT QUE
Transporter le carton portant le bon numero sur la table
Nombre d'essais
Le carton 14 n'existe pas ! On se retrouve donc dans le pire des cas.
On a donc besoin de 24 essais avec 24 cartons, 1000 essais avec 1000 cartons et 1 million d'essais avec 1 million de cartons.
On voit donc qu'en ordonnant correctement nos cartons, on gagne un peu de temps ET on peut savoir qu'un carton n'existe pas. Ce n'est pas le cas si les cartons sont placés au hasard (difficile dans ce cas de savoir si le carton n'existe pas ou si on ne l'a pas encore trouvé).
2 - Premier bilan
Nous allons maintenant tenter de définir :
- Ce qu'est un algorithme
- Ce qu'est le coût d'un algorithme
Définition d'algorithme
Définition : un algorithme est un ensemble fini (au sens "pas infini") d'instructions précises permettant de résoudre une classe de problèmes.
Le mot classe est ici important : on doit pouvoir résoudre un type de problèmes et pas un cas unique. Si l'algorithme ne fonctionne que pour UN cas particulier, on ne parlera pas d'algorithme.
De façon plus précise, un algorithme est un ensemble fini d'instructions précises effectuant des calculs et/ou des modifications sur des entrées pour produire une sortie.
ENTREE(S) → Algorithme → SORTIE
Comme vous pouvez le voir, cela ressemble fort à ce qu'on pourrait définir comme une fonction. Ce n'est pas un hasard, nous le verrons en Terminale.
Gérard Berry parle des algorithmes comme étant des méthodes à appliquer sans réflechir, en suivant machinalement le déroulement et les ordres.
On sépare réflexion et exécution.
La réflexion est utilisée par l'informaticien ou l'informaticienne lors de l'élaboration de l'algorithme.
Lors du déroulement de l'algorithme, l'ordinateur exécute. Point.
Exemple de ce qui ne sera pas vu comme un algorithme : la multiplication de 5 par 4. C'est une cas unique. Pas de possibilité de modifier quoi que ce soit. Il s'agit juste d'une suite d'instructions.
Exemple de ce qui peut être vu comme un algorithme : la multiplication de a par b, a et b étant des nombres réels (on peut avoir 5*4, 15*99 ...). On pourrait en effet dire qu'on initialise un compteur à 0 et qu'on réalise une boucle a fois : on stocke dans le compteur la somme du compteur et de b.
Exemple : pour 3 x 8, on a donc compteur = 0 + 8 + 8 + 8 = 24.
Pour parvenir à comparer l'efficacité des algorithmes, on cherche souvent à voir comment l'algorithme va gérer l'augmentation des données à traiter.
Coût et complexité d'un algorithme
Définition : le coût d'un algorithme exprime la façon dont l'algorithme réagit à l'augmentation du nombre n de données à traiter.
On évalue d'abord le coût dans le pire des cas car il borne le comportement de l'algorithme : s'il se comporte bien déjà dans le pire des cas, c'est qu'à priori nous allons pouvoir l'utiliser.
Coût constant :
Le nombre d'instructions élémentaires pour répondre ne dépend pas du nombre n de données.
Concrètement, l'algorithme utilise autant d'instructions élémentaires pour répondre avec une entrée de 100 données qu''avec une entrée de 1000 données ou un milliard de données.
Il faudrait par exemple faire
- 6 instructions pour 10 données enregistrées et
- 6 instructions pour 100 données enregistrées et
- 6 instructions pour 10 milliards de données enregistrées.
C'est donc pas mal !
Coût linéaire :
Le nombre d'instructions élémentaires pour répondre dépend directement du nombre n de données.
Si le nombre de données est multiplié par 10, le nombre d'instructions élémentaires à effectuer va globalement être multiplié par 10 aussi.
Il faudrait par exemple faire
- 6 instructions pour 10 données enregistrées,
- 60 instructions pour 100 données enregistrées et
- 6 milliards instructions pour 10 milliards de données enregistrées.
C'est un peu plus long que du coût constant !
05° Voici un algorithme qui permet de demander des notes à un système et qui calcule la moyenne des notes qu'on nous a donné.
S'agit-il d'un algorithme à coût constant ou à coût linéaire ?
Algorithme de notes(n)
somme ← 0
Le POUR ci-dessous permet de faire l'action n fois
POUR x variant de 0 à (n - 1)
note ← demanderUneNote()
on obtient une note valide
somme ← somme + note
on rajoute les notes au fur et à mesure
Fin POUR
Renvoyer somme
...CORRECTION...
Si demanderUneNote() est une fonction à coût constant, alors on voit qu'on exécute :
- 1 fois une affectation (instruction élémentaire)
- n fois la boucle qui contient 2*n opérations élémentaires
- Une instruction élémentaire Renvoyer
On a donc 2n + 2 opérations élémentaires pour un ensemble n de données.
- Pour 10 données, on a besoin de 20 + 2 = 22 opérations.
- Pour 100 données, on a besoin de 200 + 2 = 202 opérations.
- Pour 1000 données, on a besoin de 2000 + 2 = 2002 opérations.
Ces résulats montre donc qu'il s'agit d'un algorithme à coût linéaire :
- Si on veut 100 notes, cela prendra en gros 10 fois plus de temps qu'avec 10 notes.
- Si on veut 1000 notes, cela prendra en gros 100 fois plus de temps qu'avec 10 notes.
Algorithmique
L'algorithmique consiste donc à étudier des problèmes en vue de les résoudre à l'aide d'un algorithme le plus efficace possible.
On cherche donc
- à estimer la rapidité d'exécution de l'algorithme.
- Cela revient à connaître le coût de l'algorithme.
- à vérifier que la réponse éventuelle soit juste.
- Cette vérification se nomme la preuve de correction.
- à vérifier qu'il s'arrête bien sur n'importe quelle entrée fournie.
- Cette vérification se nomme la preuve de terminaison)
3 - Alice triche !
Le déménagement prend du temps car Alice veut ranger les 24 cartons dans un ordre précis.
Comme chercher chaque carton à un coût linéaire par rapport aux cartons restants, c'est long...
06° Calculer le nombre d'opérations pour ce chargement dans le pire des cas (on a pas de chance, le carton qu'on cherche est toujours le dernier qu'on vérifie !). Le premier carton coûte 24 recherches, le deuxième 23...
Faire la même recherche mais avec uniquement 6 cartons.
Le coût est-il constant, linéaire ou ni l'un ni l'autre ?
...CORRECTION...
Il faut faire 24+23+22+21+20+...+2+1. Et ça donne 300.
Sinon, Python c'est bien aussi :
>>> somme = 0↲
>>> for valeur in range(25):↲
somme = somme + valeur↲
↲
>>> somme↲
300
Avec 6 cartons, il faut 6+5+4+3+2+1 soit 21 recherches.
On a 24 = 6 * 4, mais 21 * 4 ne donne vraiment pas 300. Le coût n'est donc pas linéaire visiblement.
Nous montrerons plus tard dans l'année que le coût est alors quadratique : il dépend de n2. Bref, c'est pas top.
Alors que la moitié du chargement est déjà parti, Alice se souvient de ses cours d'informatique : son prof d'informatique lui avait dit qu'on ne stocke jamais une donnée sans la trier si c'est possible. Elle décide donc de trier les cartons restants en fonction de leur numéro.
07° Exécuter ces actions :
- Prendre au hasard 12 cartons parmi les 24.
- Placer les cartons face visible.
- Trier les cartons du plus petit au plus grand numéro.
- Retourner les cartons face cachée pour cacher le numéro.
12 cartons : 12 recherches à faire pour trouver un carton précis dans le pire des cas.
Alice dit qu'elle peut maintenant faire bien mieux : elle peut trouver le bon carton au pire en 4 recherches.
08° Alice dit à Bob d'aller voir si le carton 14 existe et de le ramener si c'est le cas. Pour cela, il faut aller voir le carton du milieu (le 6e dans la séquence) et de regarder sa valeur. Comme ils sont classés par ordre de numéro, trois cas se présentent à vous :
- Vous trouvez 14 juste à cette position : c'est bon, c'est fini.
- Vous trouvez un numéro inférieur à 14 : cela veut dire que le numéro 14 ne peut plus être qu'à droite puisque les cartons sont classés.
- Vous trouvez un numéro supérieur à 14 : cela veut dire que le numéro 14 ne peut plus être qu'à gauche.
Combien de cartons Bob va-t-il pouvoir mettre de côté en fouillant le carton du milieu ? Que doit faire Bob ensuite pour continuer sa recherche ?
...CORRECTION...
Il suffit de regarder la valeur qu'on y trouve. Si ce n'est pas 14, on pourra supprimer au moins la moitié des cartons restants.
On passe donc brutalement de 12 cartons à fouiller à 6 cartons en UNE étape.
Il faut aller voir ensuite le milieu des cartons restants : on passe alors de 6 cartons à 3 cartons.
Puis de 3 cartons à 1 carton.
Il suffit alors de regarder le carton restant.
On peut donc espérer trouver le bon carton (ou savoir qu'il n'existe pas) en 4 étapes plutôt qu'en 12.
Il existe donc un coût qui se situe entre le coût constant et le coût linéaire. Il s'agit ici du coût logarithmique. Nous en parlerons beaucoup cette année.
Du meilleur au moins bon :
- Le coût constant
- Le coût logarithmique
- Le coût linéaire
- Le coût quadratique
Mais il y a aussi des choses pires que le cas quadratique. On en parle dans la partie suivante.
4 - Charger la voiture, c'est compliqué...
Le camion est plein ! Elle a encore quelques affaires qui trainent et espère pouvoir les placer sur le toit de la voiture s'il reste de la place...
09° Récupérer uniquement les cartons numérotés de 1 à 12. Charger alors le toit au mieux : l'objectif est d'avoir la prise au vent la plus faible possible et donc de tasser pour avoir le moins de hauteur possible.
Une solution est meilleur qu'une autre si la hauteur totale sur le toit est plus petite qu'une autre.
ATTENTION : Alice ne veut pas voir ses affaires détruites : il faudra donc que le H soit dans le bon sens. Pas question de casser des verres !
10° Y-a-t-il plusieurs solutions ? Comment pourrions-nous savoir que votre solution est "la" meilleure ?
...CORRECTION...
Il y a beaucoup de solutions : c'est bien ça le problème !
Pour savoir si on a la meilleure solution, il faudrait pouvoir toutes les tester. Mais ce n'est pas possible.
La seule manière de comparer les solutions est de considèrer que celle qui est la moins haute est meilleure que les autres. Une solution sans trou est certainement la meilleur parmi toutes.
Le problème, c'est qu'on a pas accès à toutes les solutions...
Pour vous montrer que le nombre de possibilités est important, nous allons nous limiter à choisir l'ordre de chargement des cartons dans le camion. Nous allons trouver bien plus que le nombre réel de possibilités, mais cela vous éclairera sur le fait que c'est ... beaucoup.
11° Combien de choix parmi les 12 cartons pour prendre le premier ? Combien de choix pour prendre le deuxième ? Le troisième ?
...CORRECTION...
12 pour le premier.
11 pour le deuxième.
10 pour le troisième...
12° Combien de possibilités de choix à tester ?
...CORRECTION...
Si on ne considère que l'ordre de chargement, on obtient 12*11*10*9*8*7*6*5*4*3*2*1, soit 479 001 600 de possibilités.
Ici, nous avons ce qu'on nomme une factorielle. Nous en reparlerons. C'est un des pires cas possibles : un coût factoriel.
On note ce calcul 12! et on le prononce factorielle 12.
Et cela vaut 12*11*10*9*8*7*6*5*4*3*2*1. Mais c'est plus facile à écrire 12!.
Bilan :
Du meilleur coût au moins bon coût:
- Le coût constant
- Le coût logarithmique
- Le coût linéaire (lié à n)
- Le coût quadratique (lié à n2)
- Le coût exponentiel (lié à xn) : avec un tel coût, on estime que l'algorithme n'est pas exploitable à grande échelle. Il va mettre trop de temps pour répondre.
- Le coût factoriel (lié à la fonction factorielle n!) : encore moins exploitable.
Le but de la partie algorithmique va justement de voir comment l'informatique apporte une réponse à ces problèmes très complexes. Parfois en "trichant" un peu, parfois en optimisant les ressources... Travailler sur la recherche de solutions a des problèmes, voilà le coeur de l'algorithmique.
5 - Problème NP
Il existe une catégorie entière de problèmes énormément complexes dits NP-complets, et ils posent problème.
L'exemple typique de ce type de problème est le problème du voyageur de commerce : un commercial doit passer par toutes les villes de son secteur. Il cherche à optimer son parcours de façon à ce qu'il prenne le moins de temps possible. Comment trouver la solution optimale ?
Avec 15 villes, on peut énumérer tous les cas possibles et prendre le meilleur. Mais avec 20 000 villes à parcourir, on obtient un temps de calcul beaucoup trop grand pour être exploitable : les tracés routiers risquent d'avoir changé entre temps !
Les propriétés de ces problèmes complexes ?
- Pour un problème donné, vérifier qu'une proposition répond au problème est plutôt rapide et facile avec un programme
- Par contre, le temps de recherche de toutes les solutions possibles pour trouver la solution optimale varie de façon exponentielle avec la taille de l'entrée : cette recherche est donc non exploitable, sauf pour les problèmes aux données d'entrée très réduites.
- Pourtant
- Personne n'a réussi à démontrer qu'il n'existe pas de solution algorithmique plus rapide : il est donc possible qu'une telle solution existe
- On a réussi à démontrer que s'il existe un algorithme efficace sur l'un des problèmes NP-complets, il existe des solutions similaires pour tous les autres problèmes NP !
- Souvent une petite modification simplificatrice de l'énoncé du problème le rend immédiatement résolvable en un temps correct...
L'algorithmique est donc un domaine d'études très riche en recherches passées et futures. Si vous aimez les maths, l'informatique et les casses-têtes, c'est un domaine fait pour vous !
13° Proposer un algorithme qui permettra de remplir le camion. Ne cherchez pas à obtenir LA solution mais à fournir une solution "acceptable" : le problème du remplissage du toit de la voiture est NP de toute façon.
6 - FAQ
J'ai également vu O(log2 n). C'est quoi ce truc ?
Il s'agit de la fonction logarithme (ici en base 2).
C'est une fonction extrémement utile : on peut la voir en première approximation comme la fonction qui renvoie la puissance de 2 permettant d'écrire le nombre.
Quelques exemples avec Python
>>> import math
>>> math.log2(1)
0.0
Pourquoi ? Simplement car 1 = 20. On renvoie 0.
>>> math.log2(2)
1.0
Pourquoi ? Simplement car 2 = 21. On renvoie 1.
>>> math.log2(4)
2.0
Pourquoi ? Simplement car 4 = 22. On renvoie 2.
>>> math.log2(8)
3.0
Pourquoi ? Simplement car 8 = 23. On renvoie 3.
Le mieux, c'est que cela fonctionne également avec les valeurs qui ne sont pas une puissance entière de 2 !
>>> math.log2(6)
2.584962500721156
Pourquoi ? Simplement car 6 = 22.584962500721156. On renvoie 2.584962500721156. Si vous avez bien compris l'activité sur les floats, vous devriez comprendre qu'il s'agit certainement d'une valeur approximative.
Il existe un logarithme pour toutes les bases possibles et imaginables.
Le logarithme base 10 donne ainsi log10(1000) = 3 puisque 1000 = 103
Ou encore le logarithme népérien ln qui est en lien avec la fonction exponentielle : ln(20) = 2.995732273553991 car on peut écrire
- 20 = e2.995732273553991 ou encore
- 20 = exp(2.995732273553991)
Log et Lg, c'est différent ?
Oui.
Lorsqu'on parle simplement de log, on parle du log dans une base donnée. Si c'est rien n'est précisé, c'est certainement la base 10.
Habituellement, si on note juste log, on parle du log10.
Si on note lg(x), on parle de log2(x) dans un contexte informatique. Cela évite de noter log10(x). On note juste lg(x)
Attention donc au contexte dans lequel apparaît un logarithme.
Activité publiée le 04 11 2020
Dernière modification : 05 11 2020
Auteur : ows. h.