> Le Site du Zéro - Informatique

> Cours

> Tutoriels

> Programmation

> Algorithmique

> Algorithmique pour l'apprenti programmeur

> Présentation de la notion de complexité algorithmique

> Les grenouilles partent en vacances

> Lecture du tutoriel

Les grenouilles partent en vacances

Par

bluestorm et Avatar

lastsseldon et Avatar

Cygal

Mise à jour : 12/06/2010

Difficulté : Facile Facile

3 427 visites depuis 7 jours, dont 208 sur ce chapitre classé 47/786

Pour vous faire comprendre la notion de complexité, nous avons choisi un exemple simple, de la vie de tous les jours. Aquatique.

Retour en haut

Sommaire du chapitre :

Situation
Les deux possibilités
Comparaison

Retour en haut

Situation

Haskell est un gentil fermier, qui élève des grenouilles. Il a des relations très chaleureuses avec celles-ci, qui peuvent se promener à leur guise dans leur champ pendant toute l'année, et ont droit à une petite cahute avec chauffage pendant l'hiver. Mais ce qui fait véritablement la joie des grenouilles de Haskell, ce sont les vacances : tous les ans, juste avant de s'occuper des moissons, il les amène dans les marécages près de sa ferme pour qu'elles puissent y passer des vacances aquatiques.

Le détail compliqué est le départ en vacances. Haskell charge toutes ses grenouilles dans une grande caisse, qu'il met sur son camion, et part vers les nombreux marécages pour les y déposer. Le problème vient du fait que les grenouilles, surtout pendant les vacances, n'apprécient pas la foule : elles veulent aller dans un des marécages les moins peuplés.

Plus précisément, la caisse est un carré en forme de quadrillage de N cases de large par N cases de long (N est un nombre inconnu de nous, mais fixé). Chaque case de la caisse contient une grenouille. Il y aussi N marécages vides, dans lesquels les grenouilles pourront se répartir.

Retour en haut

Les deux possibilités

Tous les ans : choix personnalisé

Jusqu'à présent, Haskell le fermier, qui ne voulait pas se prendre la tête, utilisait la méthode suivante : après avoir chargé le carré de grenouilles sur son camion, il choisissait l'une d'entre elles, et lui demandait de lui désigner le marécage dans lequel elle voulait passer ses vacances, puis l'y amenait.

Après l'avoir déposée, il demandait à une seconde grenouille de choisir son marécage. Celle-ci, préférant les marécages les moins peuplés, choisissait systématiquement un autre marécage encore vide. Il l'y amenait, puis demandait à la grenouille suivante, et ainsi de suite.

Les marécages se remplissaient petit à petit. Dès qu'un marécage était un peu moins peuplé que les autres, les grenouilles suivantes s'y rendaient et sa population augmentait. Globalement, à la fin de la distribution des grenouilles, tous les marécages étaient également peuplés : ils contenaient N grenouilles chacun.

Cette année : choix de groupe

Cette année, Haskell le fermier en a un peu marre des interminables voyages en camion pour satisfaire chaque grenouille. Il a décidé d'appliquer une autre méthode : il va au premier marécage, et y dépose la première rangée de N grenouilles. Celles-ci protestent vigoureusement puisqu'elles sont entassées à N dans un seul marécage, alors que tous les autres sont vides. Mais il les quitte pour aller déposer la deuxième rangée de N grenouilles dans le deuxième marécage, et ainsi de suite jusqu'à avoir vidé chacune des N rangées, et donc rempli les N marécages. À la fin, les grenouilles (qui s'étaient communiqué leur indignation par SMS) se calment, puisqu'elles sont toutes dans un marécage peuplé de N grenouilles, et qu'il n'y a donc plus aucun marécage moins peuplé disponible.

Retour en haut

Comparaison

Dans les deux cas, les conditions de départ sont respectées : les grenouilles sont réparties de façon à ce qu'aucun marécage ne soit plus peuplé que les autres, et sont donc satisfaites. Les deux méthodes de Haskell le fermier résolvent bien le problème correctement.

La différence vient du fait que dans la première méthode, chaque grenouille ou presque lui demandait de changer de marécage. Il faisait donc environ autant de voyages en camion qu'il y a de grenouilles. Dans le deuxième cas, il déposait les grenouilles par blocs d'une rangée, et donc faisait moins de voyages : seulement le nombre de rangées de grenouilles.

La différence n'a pas l'air importante, mais cela dépend beaucoup du nombres de rangées. Pour N rangées, comme la caisse est carrée, il y a N grenouilles par rangée, soit au total N*N, ou N² grenouilles. La méthode habituelle demande environ N² voyages à Haskell le fermier, alors que la deuxième méthode n'en demande que N.

La deuxième méthode est plus rapide, et surtout le temps gagné en l'appliquant augmente plus il y a de grenouilles. S'il y a 6 rangées de grenouilles et que le déplacement en camion d'un marécage à l'autre dure 5 minutes environ, il faut 6 * 5 = 30 minutes, soit une demi-heure avec la nouvelle méthode, alors qu'il fallait auparavant 6 * 6 * 5 = 180 minutes, soit 3 heures pour répartir le même nombre de grenouilles. Et l'écart se creuse quand il y a plus de rangées : s'il y en a 20, avec le même calcul, il faut un peu moins de 2 heures avec la deuxième méthode, mais 33 heures avec l'ancienne !

Clairement, la nouvelle méthode de Haskell le fermier est bien meilleure. En termes informatiques, on dira que l'algorithme qu'il a choisi est plus performant. On peut même quantifier cette performance en termes de "complexité", c'est ce que l'on verra dans le prochain chapitre.

Retour en haut

Retour en haut

15 commentaires pour "Les grenouilles partent en vacances"

Note moyenne : 3.89 / 4 (127 votes)

Pseudo	Commentaire
yougataga	# Posté le 02/05/2009 à 14:23:30
Un homme avertit en vaut deux	Super l'exemple ^^c'est vrai que des grenouilles qui envoient des sms j'aimerais voir sa sinon bien joué ^^. <a href="http://www.humainavendre.com" title="Combien valez-vous ?">Je vaux 4 375 330 € sur HumainAVendre.com, et vous ?</a>
christophetd	# Posté le 23/05/2009 à 08:37:47
Regardez-moi ! Blog Twitter close Ville : Gap Pays : France métropolitaine	J'adore l'exemple des grenouilles qui s'envoient des SMS pour protester Sinon ce chapitre est très bien expliqué, je passe à la suite. -> Mes tutoriels : Empêcher le téléchargement direct de fichiers multimédia Utilisation d'un ORM : les bases de Doctrine Un système de news sans base de données Petit guide d'utilisation de Twitter
nebneo	# Posté le 30/12/2009 à 21:34:56
	Bonsoir! Je suis en train de commencer ce tuto somme toute très intéressant, mais un point flou m'interpelle. Vous dites qu'il y a N grenouilles, et N marécages. Ca suppose qu'il y a autant de grenouilles que de marécages non? Ce serait peut être mieux de dire N grenouilles et M marécages. Après c'est peut être moi qui ai pas encore compris l'exemple Edit: Je viens de comprendre, je suis un boulet... Je posterai plus directement sur le vif désolé
bluestorm	# Posté le 31/12/2009 à 00:14:28
dont ask to ask Groupe : Anciens Blog Twitter close	J'utilise bien un nombre de marécages égal au nombre de grenouilles, parce que ça simplifie le problème. Si ce n'est pas assez clair, je le préciserai explicitement. big tuto algorithmique \| tuto récursivité [PHP] \| tuto typage \| textes divers Ours & Hippy — le blog
Rubik	# Posté le 28/02/2011 à 04:09:26
Avis : Très bon Ville : Paris Pays : France métropolitaine	Super cette introduction aux algorithmes ! J'adore cette approche ludique digne du SDZ et elle m'a bien fait marrer cette histoire d'Haskell et ses grenouilles Ça donne franchement envie de lire la suite. Bravo à tous et bonne continuation.