Self-assessment quiz

--- secondary_color: lightgray --- # Heuristics 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. # Heuristics Une bonne heuristique doit... - [ ] Ne fournir aucune solution lorsque le problème est trop complexe pour être résolu. - [x] Apporter 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 --- # Greedy algorithms Lesquelles des affirmations suivantes décrivent le mieux un algorithme glouton ? - [x] C'est un algorithme qui suit des solutions localement optimales. - [ ] C'est un algorithme qui opère uniquement sur des graphes. - [ ] C'est un algorithme qui a une complexité très limitée. # Greedy algorithms 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é. # Greedy algorithms On considère l'algorithme glouton qui choisit toujours de sauter vers le sommet inexploré 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. # Greedy algorithms Lequel des chemins suivants peut être obtenu en appliquant un algorithme glouton qui saute vers le sommet le plus proche et commence au 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\})$. # Greedy algorithms Considérons le problème de trouver un chemin le plus long dans un graphe pondéré donné, en partant du sommet $u$. Pour le résoudre, on peut adopter l'approche gloutonne consistant à choisir systématiquement une arête inexplorée $\{v, v'\}$ de poids maximal à partir du sommet courant $v$, puis à sauter vers le sommet correspondant $v'$, jusqu'à ce qu'il n'y ait plus de telles arêtes. Lesquelles des affirmations suivantes sont vraies ? - [ ] Cet algorithme glouton est optimal (il donne toujours le chemin le plus long). - [x] Cet algorithme glouton donne un chemin commençant à $u$. - [x] Cet algorithme glouton se termine toujours (il ne peut pas itérer indéfiniment).

--- secondary_color: lightgray --- # Approximate solutions Une solution approximative est utilisée... - [x] Chaque fois que les solutions exactes ne sont pas réalisables en pratique. - [x] Pour accélérer les calculs par rapport aux solutions exactes. # Approximate solutions Un Pareto optimal est... - [ ] Une solution qui minimise à la fois la vitesse et la justesse. - [x] Un compromis optimal entre la vitesse et la justesse. - [ ] Une solution qui maximise la justesse, indépendamment de la vitesse. - [ ] Une solution qui maximise à la fois la vitesse et la justesse. # Approximate solutions Une frontière de Pareto... - [ ] Délimite les algorithmes à complexité élevée et faible. - [x] Délimite les compromis entre complexité et justesse. # Approximate solutions Un Pareto optimal est... - [ ] Une solution qui minimise à la fois la vitesse et la justesse. - [x] Un compromis optimal entre la vitesse et la justesse.