Algorithmique II

4. Algorithmes heuristiques

Solutions des exercices

Exercice 1

Voir partie Apprendre.

Exercice 2

Voir partie Apprendre.

Exercice 3 – L’univers dans un sac à dos

L’âge estimé de l’univers est de 14 milliards d’années. Si le calcul d’une combinaison d’objets dans le problème du sac à dos prenait une microseconde, pour quel nombre d’objets serait-il possible de trouver une solution exacte sans dépasser l’âge de l’univers ?

Solution 3 – L’univers dans un sac à dos

Cliquer ici pour voir la réponse

Une microseconde vaut 10^-6 s. La complexité du problème du sac à dos est de 2ⁿ.

On recherche un n pour lequel 2ⁿ10^-6 = 14 000 000 000 * 3,15410⁷ (l’âge de l’univers en secondes)

n = log₂(1.4 * 3,154*10¹⁷ / 10^-6) = log₂(4.42 * 10²³) = 78 objets seulement.

Exercice 4 – Parcours du parcours du parcours de listes

Quelle est la complexité d’un algorithme qui pour chacun des éléments d’une liste de \(n\) éléments, doit parcourir tous les éléments d’une autre liste de \(n\) éléments, puis pour chacune des combinaisons de deux éléments doit encore parcourir une troisième liste de \(n\) éléments ?

Si vous avez besoin de travailler sur un exemple plus concret, quelle est complexité de l’algorithme qui calcule tous les menus possibles à partir d’une liste de \(n\) entrées, une liste de \(n\) plats et une liste de \(n\) desserts ?

Solution 4 – Parcours du parcours du parcours de listes

Cliquer ici pour voir la réponse

Pour chaque élément de la première liste (premier parcours) on doit parcourir la deuxième liste une fois, ce qui fait une complexité de n * n = n². Pour chacune des combinaisons de deux éléments des deux premières listes, il nous faut parcourir la troisième liste : on a donc une complexité de n * n * n = n³, ou une complexité cubique.