Self-assessment quiz

--- secondary_color: lightgray --- # The traveling salesman problem En théorie des graphes, le TSP correspond à... - [ ] Un problème dans lequel on cherche à trouver le plus court chemin d'un sommet u à un sommet v dans un graphe pondéré. - [ ] L'équipe de soutien PyRat (TSP). - [x] Un problème dans lequel on cherche à trouver le trajet le plus court passant par tous les sommets d'un graphe pondéré à partir d'un sommet initial. # The traveling salesman problem Réduire un problème $P$ à un problème $Q$ consiste à... - [ ] Trouver les entrées du problème $P$ pour lesquelles $Q$ donne les mêmes sorties. - [ ] Garder la partie de $P$ qui est plus simple que $Q$. - [x] Trouver un moyen de résoudre $P$ en utilisant n'importe quel algorithme conçu pour résoudre $Q$. # The traveling salesman problem Le TSP traite une entrée qui se décrit le mieux comme... - [x] Un graphe complet pondéré et un sommet initial. - [ ] Un arbre non pondéré et un sommet racine. - [ ] Un tétraèdre. # The traveling salesman problem Laquelle des affirmations suivantes définit le problème du voyageur de commerce ? - [ ] Trouver le cycle le plus court dans un graphe pondéré à partir d'un sommet initial. - [x] Trouver le trajet le plus court passant par tous les sommets d'un graphe pondéré à partir d'un sommet initial. - [ ] Trouver un arbre couvrant minimal dans un graphe pondéré à partir d'un sommet initial. # The traveling salesman problem Considérons une situation dans laquelle nous nous intéressons à la complexité des algorithmes qui opèrent sur des graphes en fonction de l'ordre $n$ de ces graphes. Cochez les problèmes suivants qui peuvent être réduits à la recherche d'un plus court chemin entre deux sommets $u$ et $v$ dans un graphe pondéré : - [x] Trouver un plus court chemin entre deux sommets $u$ et $v$ dans un graphe non pondéré. - [ ] Le TSP. - [x] Vérifier s'il existe un chemin entre deux sommets $u$ et $v$ dans un graphe pondéré.

--- secondary_color: lightgray --- # Bruteforce and backtracking to solve NP-complete problems Un algorithme de bruteforce... - [x] Est un algorithme qui trouve des solutions en testant toutes les possibilités de manière exhaustive. - [x] Est garanti de trouver des solutions exactes. - [ ] Est un algorithme qui trouve la solution la moins complexe sans vérifier si elle est correcte. # Bruteforce and backtracking to solve NP-complete problems Un algorithme de backtracking pour le TSP... - [x] Examine itérativement les longueurs des trajets et abandonne immédiatement l'examen d'un trajet plus long que le plus court trouvé jusqu'à présent. - [x] Est garanti de trouver le trajet le plus court. - [ ] Explore aléatoirement seulement un sous-ensemble de tous les trajets et renvoie le plus court trajet de ce sous-ensemble, mais n'est pas garanti de trouver le plus court trajet parmi tous les possibles. # Bruteforce and backtracking to solve NP-complete problems Nous considérons l'utilisation d'un algorithme de backtracking pour le TSP. Lesquelles des affirmations suivantes sont vraies ? - [x] La complexité du backtracking peut être linéaire pour certains graphes. - [x] L'ordre dans lequel les sommets sont explorés a une influence importante sur le temps d'exécution global. - [ ] Le backtracking est basé sur un BFS. # Bruteforce and backtracking to solve NP-complete problems Lors de la résolution du TSP avec backtracking, lesquelles des affirmations suivantes sont vraies ? - [x] L'exploration de la branche courante est abandonnée si la longueur du trajet partiel est supérieure au meilleur trajet trouvé jusqu'à présent. - [x] Dans le meilleur des cas, seule la première branche a été entièrement explorée. - [x] Si les branches sont explorées dans l'ordre décroissant de longueur, alors on explore autant de solutions que la recherche exhaustive simple. # Bruteforce and backtracking to solve NP-complete problems Nous considérons l'utilisation d'un algorithme de backtracking pour résoudre le TSP. Lesquelles des affirmations suivantes sont vraies ? - [x] Sur un graphe pondéré où tous les poids sont égaux, le backtracking sera au moins aussi coûteux qu'une recherche bruteforce. - [ ] Si interrompu avant la fin, une solution estimée par backtracking sera toujours strictement inférieure à la vraie réponse. - [x] L'ordre dans lequel les sommets sont explorés a une influence importante sur le temps d'exécution global.

--- secondary_color: lightgray --- # Problem complexity & NP-completeness La complexité d'un problème est définie comme... - [x] La complexité minimale des algorithmes utilisés pour résoudre le problème. - [ ] La complexité maximale des algorithmes utilisés pour résoudre le problème. - [ ] La complexité moyenne des algorithmes utilisés pour résoudre le problème. # Problem complexity & NP-completeness Pour résoudre des problèmes NP, vous devez souvent utiliser des algorithmes avec... - [ ] Une complexité linéaire. - [ ] Une complexité quadratique. - [x] Une complexité exponentielle. # Problem complexity & NP-completeness Le problème du voyageur de commerce est un problème NP-Complet. - [x] Vrai. - [ ] Faux. # Problem complexity & NP-completeness Considérons un problème pour lequel nous avons un algorithme de solution avec une complexité $O(n^2)$. Sélectionnez les affirmations correctes : - [x] La complexité du problème ne peut pas être supérieure à $n^2$. - [ ] Il n'existe pas d'algorithme qui puisse résoudre le problème avec une complexité $O(n)$. - [ ] La complexité du problème est $O(n^2)$. - [ ] Le problème est au moins aussi difficile que le TSP. # Problem complexity & NP-completeness La complexité d'un problème est... - [ ] La complexité maximale d'un algorithme utilisé pour le résoudre. - [x] La complexité minimale d'un algorithme utilisé pour le résoudre.