# Algorithmique II ## 4. Algorithmes heuristiques ### Solutions des exercices ````{exercise} Voir partie Apprendre. ```` ````{exercise} Voir partie Apprendre. ```` ```{exercise} 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} ```{dropdown} Cliquer ici pour voir la réponse :animate: fade-in-slide-down Une microseconde vaut 10-6 s. La complexité du problème du sac à dos est de 2n. On recherche un `n` pour lequel 2n*10-6 = 14 000 000 000 * 3,154*107 (l'âge de l'univers en secondes) n = log2(1.4 * 3,154*1017 / 10-6) = log2(4.42 * 1023) = 78 objets seulement. ``` ```` ```{exercise} 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} ```{dropdown} Cliquer ici pour voir la réponse :animate: fade-in-slide-down 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 = n2. 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 = n3, ou une complexité cubique. ``` ````