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.

--- 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 pas optimal dans tous les cas. - [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).

--- 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... - [ ] Délimite les algorithmes avec une complexité élevée et faible. - [x] Délimite les compromis entre la complexité et la précision. # 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.