Algo Intro

Identification

Infoforall

1 - Alice déménage mais à quel coût ?


Qu'est-ce que l'algorithmique.

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 devrez :

  1. prendre le carton,
  2. regarder son numéro
  3. le reposer à la même place (en cachant encore son numéro)

Deux questions :

  1. combien de cartons avez-vous dû regarder avant de trouver le bon ?
  2. Quel est le problème qu'on pourrait rencontrer en n'étant pas assez attentif (ou si on avait 1000 cartons) ?

...CORRECTION...

Entre

  • 1 carton (bravo, vous avez de la chance !)
  • 24 cartons (pas de chance !)

Mais on peut faire pire ici : il est possible de regarder un carton qu'on avait déjà fouillé ! Dans ce cas, on pourrait monter à plus de 24 cartons SI on a pas de chance ET qu'on n'est pas attentif.

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.

03° Prendre les cartons et les placer aléatoirement (toujours face cachée) les uns à côté des autres. vous devriez obtenir une ou deux lignes.

Questions :

  1. combien de cartons avez-vous dû regarder avant de trouver le carton 9 ?
  2. même en n'ayant vraiment pas de chance, combien de recherches dans le pire des cas ?
  3. même en n'ayant vraiment pas de chance, combien de recherches dans le pire des cas si on avait 1000 cartons plutôt que 24 ?
  4. même 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.

  1. 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 ?
  2. en appliquant ces instructions, combien de cartons avez-vous dû regarder pour savoir si le carton 14 existe (ou pas) ?
  3. combien d'observations aurait-on dû faire si on avait 1000 cartons ?
  4. 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.

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.

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.

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.

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'abord, voyons ce qu'est un algorithme.

Définition d'algorithme

Définition : un algorithme est un ensemble fini (au sens dénombrable) 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 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.

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 lors de la création 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 (même simpliste): 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 (simpliste) : 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. Et même ici, c'est un cas vraiment limite.

Exemple : pour 3 x 8, on a donc compteur = 0 + 8 + 8 + 8.

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.

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.

05° Voici un algorithme que vous avez peut-être implémenté en Python lors des activités précédentes.

S'agit-il d'un algorithme à coût constant ou à coût linéaire ?

Algorithme de notes(n)

    somme0

    Permet de faire l'action n fois

    POUR x variant de 0 à (n - 1)

      notedemanderUneNote()

      on obtient une note valide

      sommesomme + 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 retour

La boucle implique donc qu'il s'agit d'un algorithme à coût linéaire : si on veut 1000 notes, cela prendra 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

  • à limiter les coûts et
  • à obtenir une bonne réponse (la plus optimale possible) : la correction
  • à vérifier qu'il s'arrête : la 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. Le premier carton coûte 24 recherches, le deuxième 23...

...CORRECTION...

Il faut faire 24+23+22+21+20+...+2+1. Et ça donne 300.

Sinon, Python c'est bien aussi

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. Elle décide de trier les cartons en fonction de leur numéros : son prof lui avait dit qu'on ne stocke jamais une donnée sans la trier.

07° Prendre au hasard 12 cartons parmi les 24. Placer les cartons face visible. Trier les cartons du plus petit au plus grand.

Ensuite, retourner à nouveau les cartons pour cacher le numéro.

12 cartons : 12 observations 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 donc) et de regarder sa valeur. Combien de cartons Bob va-t-il pouvoir mettre de côté ? Que doit faire Bob ensuite ?

...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. On parle de 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 le camion, c'est compliqué...

Alice veut maintenant optimiser le chargement du camion. Elle a encore quelques affaires qui trainent et espère pouvoir les placer dans le camion s'il reste de la place...

09° Charger le camion au mieux de votre imagination :l'objectif est de tasser pour avoir le moins de profondeur possible.

10° Y-a-t-il plusieurs solutions ? Comment pourrions-nous savoir que votre solution est "la" meilleur ?

...CORRECTION...

Il y a beaucoup de solutions : c'est bien ça le problème !

Pour savoir si on a la meilleure solution, il faudra 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 profonde 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é, 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. Il s'agit de la fonction factorielle.

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.

Bilan :

Du meilleur au moins bon :

  • 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)
  • Le coût factoriel (lié à la fonction factorielle n!)

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 ?

https://fr.wikipedia.org/wiki/Probl%C3%A8me_du_voyageur_de_commerce#/media/Fichier:TSP_Deutschland_3.png
Voyageur de commerce - Domaine public - Original téléversé par Kapitän Nemo sur Wikipédia allemand. — https://www.cia.gov

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 à tous les autres problèmes NP-complets !
    • 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 permettre de remplir le camion. Ne cherchez pas à obtenir LA solution mais à fournir une solution "acceptable".

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.

Dans la prochaine activité, nous commencerons à étudier plus en détails certains algorithmes et nous verrons comment s'approcher d'une solution "correcte" lorsqu'on ne peut pas faire mieux.

Activité publiée le 04 11 2020
Dernière modification : 05 11 2020
Auteur : ows. h.