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