Quiz d'auto-évaluation

--- secondary_color: lightgray --- # Heuristiques Un algorithme heuristique est utilisé pour... - [x] Résoudre plus rapidement des problèmes lorsque les méthodes classiques sont trop lentes pour trouver une solution exacte. - [ ] Améliorer la solution optimale produite par un algorithme exact. - [ ] Détériorer la qualité de la solution lorsqu'elle est trop belle pour être vraie. # Heuristiques Une bonne heuristique doit... - [ ] Ne fournir aucune solution lorsque le problème est trop complexe pour être résolu. - [x] Fournir un gain et être de complexité limitée. - [ ] Trouver la solution optimale, même pour les problèmes les plus complexes, en quelques millisecondes. # Heuristiques Dans une recherche exhaustive avec backtracking pour le TSP, on explore d'abord les voisins les plus proches du sommet courant. Laquelle des affirmations suivantes est vraie ? - [x] La solution renvoyée reste optimale : l'heuristique ne change que l'ordre d'exploration, et peut permettre d'élaguer plus de branches. - [ ] La solution renvoyée n'est plus garantie optimale, car on ne teste plus toutes les branches. - [ ] L'algorithme devient un algorithme glouton. # Heuristiques Comment évalue-t-on généralement la qualité d'une heuristique ? - [ ] En prouvant formellement, avant de l'implémenter, qu'elle trouve toujours la solution optimale. - [x] En l'implémentant, puis en comparant ses résultats à ceux d'autres approches sur un grand nombre d'instances du problème. - [ ] En mesurant uniquement son temps d'exécution. # Heuristiques Parmi les méthodes suivantes, lesquelles sont des méta-heuristiques ? - [x] Le recuit simulé. - [x] Les algorithmes génétiques. - [x] Les colonies de fourmis. - [ ] L'algorithme de Dijkstra.

--- secondary_color: lightgray --- # Algorithmes gloutons Quelles affirmations décrivent le mieux un algorithme glouton ? - [x] C'est un algorithme qui suit des solutions localement optimales. - [ ] C'est un algorithme qui ne fonctionne que sur des graphes. - [ ] C'est un algorithme qui a une complexité très limitée. # Algorithmes gloutons Lesquelles des affirmations suivantes sont vraies ? - [ ] Un algorithme glouton n'est jamais optimal. - [x] Pour certains problèmes, un algorithme glouton peut être non optimal. - [ ] Il n'existe qu'un seul algorithme glouton pour résoudre un problème donné. # Algorithmes gloutons Nous considérons l'algorithme glouton qui choisit toujours de sauter vers le sommet non exploré le plus proche pour résoudre le TSP. Laquelle des affirmations suivantes est vraie ? - [ ] La solution trouvée par un algorithme glouton est toujours optimale. - [x] La solution trouvée par un algorithme glouton peut être optimale ou non. - [ ] La solution trouvée par un algorithme glouton n'est jamais optimale. # Algorithmes gloutons Lequel des chemins suivants peut être obtenu en appliquant un algorithme glouton qui saute vers le sommet le plus proche et commence à partir du sommet $v_0$ ?

 - [ ] $(\{v_0, v_1\}, \{v_1, v_2\}, \{v_2, v_3\}, \{v_3, v_4\})$. - [x] $(\{v_0, v_4\}, \{v_1, v_4\}, \{v_1, v_3\}, \{v_2, v_3\})$. - [x] $(\{v_0, v_3\}, \{v_1, v_3\}, \{v_1, v_4\}, \{v_2, v_4\})$. # Algorithmes gloutons Considérons le problème de trouver le chemin le plus long dans un graphe pondéré donné, en commençant au sommet $u$. Pour le résoudre, nous pouvons adopter l'approche gloutonne consistant à choisir systématiquement une arête non explorée $\{v, v'\}$ de poids maximum à partir du sommet actuel $v$, puis sauter au sommet correspondant $v'$, jusqu'à ce qu'il n'y ait plus d'arêtes de ce type. Lesquelles des affirmations suivantes sont vraies ? - [ ] Cet algorithme glouton est optimal (il renvoie toujours le chemin le plus long). - [x] Cet algorithme glouton renvoie un chemin commençant à $u$. - [x] Cet algorithme glouton se termine toujours (il ne peut pas itérer indéfiniment). # Algorithmes gloutons On dispose de pièces de 1, 4 et 9 centimes, et on veut rendre 12 centimes avec le moins de pièces possible. Que fait l'algorithme glouton qui choisit toujours la plus grande pièce possible ? - [ ] Il rend 3 pièces ($4 + 4 + 4$), ce qui est optimal. - [x] Il rend 4 pièces ($9 + 1 + 1 + 1$), alors que 3 pièces suffisent. - [ ] Il est forcément optimal, car chaque pièce vaut au moins le double de la précédente. # Algorithmes gloutons Parmi les algorithmes suivants, lesquels sont des algorithmes gloutons qui trouvent toujours une solution optimale ? - [x] L'algorithme de Dijkstra, avec des poids positifs. - [x] L'algorithme de Prim, pour l'arbre couvrant de poids minimal. - [ ] L'algorithme du plus proche voisin, pour le TSP. # Algorithmes gloutons Que peut-on dire de la longueur du chemin trouvé par l'algorithme du plus proche voisin pour le TSP ? - [ ] Il est toujours au plus deux fois plus long que le chemin optimal. - [x] Sans hypothèse sur le graphe, il peut être aussi long qu'on le veut par rapport au chemin optimal. - [x] Si le graphe vérifie l'inégalité triangulaire, il est au pire de l'ordre de $\log(n)$ fois plus long que le chemin optimal, pour $n$ sommets. # Algorithmes gloutons Sur un graphe qui vérifie l'inégalité triangulaire, on visite les sommets dans l'ordre d'un parcours en profondeur d'un arbre couvrant de poids minimal. Pourquoi le chemin obtenu est-il au plus deux fois plus long que le chemin optimal ? - [x] Le chemin optimal est un arbre couvrant, donc il pèse au moins autant que l'arbre couvrant de poids minimal. - [x] Le parcours en profondeur emprunte chaque arête de l'arbre au plus deux fois, et les raccourcis ne l'allongent pas grâce à l'inégalité triangulaire. - [ ] Parce que le parcours en profondeur trouve le chemin optimal dans l'arbre.

--- secondary_color: lightgray --- # Solutions approchées Une solution approchée est utilisée... - [x] Chaque fois que des solutions exactes ne sont pas réalisables en pratique. - [x] Pour accélérer les calculs par rapport aux solutions exactes. # Solutions approchées Une solution Pareto-optimale est... - [ ] Une solution qui minimise à la fois la vitesse et la précision. - [x] Un compromis optimal entre la vitesse et la précision. - [ ] Une solution qui maximise la précision, indépendamment de la vitesse. - [ ] Une solution qui maximise à la fois la vitesse et la précision. # Solutions approchées Une frontière de Pareto... - [ ] Sépare les algorithmes exacts des algorithmes approchés. - [x] Délimite les compromis entre la complexité et la précision. # Solutions approchées Pour des graphes trop grands, on ne peut pas calculer la solution exacte du problème de coloration. Comment évaluer malgré tout la qualité de l'algorithme glouton de coloration ? - [x] Le tester sur des graphes dont on connaît le nombre chromatique, par exemple des graphes bipartis avec au moins une arête, pour lesquels il vaut 2. - [ ] Ce n'est pas possible : sans solution exacte, on ne peut rien dire. - [ ] Vérifier que la coloration est propre suffit à montrer qu'elle est optimale. # Solutions approchées Votre nouvel algorithme approché est 10 fois plus lent qu'un algorithme glouton, pour des solutions 1 % meilleures. Que faut-il en conclure ? - [ ] Il est forcément meilleur, puisque ses solutions sont meilleures. - [x] Il faut le comparer à l'approche simple sur les deux critères : le gain ne vaut peut-être pas le coût, sauf si ce 1 % fait une différence importante. - [ ] Il est forcément moins bon, puisqu'il est plus lent. # Solutions approchées L'algorithme A est plus rapide que l'algorithme B, et trouve des solutions de même qualité. Que peut-on dire de B ? - [x] B n'est pas Pareto-optimal : A est au moins aussi bon sur les deux critères, et strictement meilleur sur l'un d'eux. - [ ] B est Pareto-optimal, puisqu'il trouve de bonnes solutions. - [ ] On ne peut pas comparer A et B sans connaître la solution exacte.