Quiz d'auto-évaluation

--- secondary_color: lightgray --- # Le problème du voyageur de commerce En théorie des graphes, le TSP correspond à... - [ ] Un problème où l'on cherche à trouver le plus court chemin entre un sommet u et un sommet v dans un graphe pondéré. - [ ] The Team Supporting PyRat (TSP). - [x] Un problème où l'on cherche à trouver le plus court circuit passant par tous les sommets d'un graphe pondéré à partir d'un sommet initial. # Le problème du voyageur de commerce Réduire un problème $P$ à un problème $Q$ implique... - [ ] De trouver les entrées du problème $P$ pour lesquelles $Q$ donne les mêmes sorties. - [ ] De conserver la partie de $P$ qui est plus simple que $Q$. - [x] De trouver un moyen de résoudre $P$ en utilisant un algorithme conçu pour résoudre $Q$. # Le problème du voyageur de commerce Le TSP traite une entrée qui est mieux décrite comme... - [x] Un graphe complet pondéré et un sommet initial. - [ ] Un arbre non pondéré et un sommet racine. - [ ] Un tétraèdre. # Le problème du voyageur de commerce Lesquelles des affirmations suivantes définissent le problème du voyageur de commerce ? - [ ] Trouver le plus court cycle dans un graphe pondéré à partir d'un sommet initial. - [x] Trouver le plus court circuit 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. # Le problème du voyageur de commerce Considérons une situation où nous nous intéressons à la complexité des algorithmes opérant 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 & backtracking pour résoudre les problèmes NP-complets 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 & backtracking pour résoudre les problèmes NP-complets Un algorithme de backtracking pour le TSP... - [x] Examine de manière itérative les longueurs des circuits et interrompt immédiatement l'examen d'un circuit plus long que le plus court trouvé jusqu'à présent. - [x] Est garanti de trouver le circuit le plus court. - [ ] Explore aléatoirement seulement un sous-ensemble de tous les circuits et retourne le plus court circuit de ce sous-ensemble, mais n'est pas garanti de trouver le plus court circuit parmi tous les possibles. # Bruteforce & backtracking pour résoudre les problèmes NP-complets 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 une recherche en largeur (BFS). # Bruteforce & backtracking pour résoudre les problèmes NP-complets Lors de la résolution du TSP à l'aide du backtracking, lesquelles des affirmations suivantes sont vraies ? - [x] L'exploration de la branche actuelle est interrompue si la longueur du circuit partiel est supérieure à celle du meilleur circuit 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 leur longueur, alors nous explorons autant de solutions que dans une recherche exhaustive simple. # Bruteforce & backtracking pour résoudre les problèmes NP-complets 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 exhaustive. - [ ] Si interrompu avant la fin, une solution estimée par backtracking sera toujours strictement inférieure à la réponse exacte. - [x] L'ordre dans lequel les sommets sont explorés a une influence importante sur le temps d'exécution global.

--- secondary_color: lightgray --- # Complexité des algorithmes La complexité d'un algorithme est une mesure du... - [x] Nombre maximum d'opérations élémentaires nécessaires à son exécution, en fonction de la taille de l'entrée. - [ ] Nombre minimum d'opérations élémentaires nécessaires à son exécution, en fonction de la taille de l'entrée. - [ ] Nombre moyen d'opérations élémentaires nécessaires à son exécution, en fonction de la taille de l'entrée. # Complexité des algorithmes La notation grand-O (ou comportement asymptotique) nous permet de négliger... - [ ] Les constantes et les termes de faible ordre car ils sont trop difficiles à calculer précisément. - [ ] Le micro. - [x] Les constantes et les termes de faible ordre car ils n'ont pas d'importance lorsque la taille du problème devient suffisamment grande. # Complexité des algorithmes La complexité de l'algorithme BFS est... - [x] $O(|E|)$, où $E$ est l'ensemble des arêtes du graphe. - [ ] $O(|V|)$, où $V$ est l'ensemble des sommets du graphe. - [ ] $O(|V| \cdot |E|)$, où $V$ est l'ensemble des sommets et $E$ est l'ensemble des arêtes du graphe. # Complexité des algorithmes Étant donné une taille d'entrée $n$, un algorithme donné effectue exactement $3n^2 + 4n + 17$ opérations élémentaires. Lesquelles des notations grand-O suivantes sont valides pour sa complexité ? - [ ] $O(n)$. - [ ] $O(n \cdot log(n))$. - [x] $O(n^2)$. - [ ] $O(n^3)$. Considérons un algorithme qui opère sur des graphes. Le nombre d'opérations élémentaires qu'il nécessite est exactement le nombre d'arêtes dans le graphe. Quelle est la complexité de l'algorithme, exprimée en fonction de l'ordre $n$ du graphe ? - [ ] Puisqu'elle dépend du nombre d'arêtes, elle ne peut pas être définie. - [ ] $O(n)$. - [x] $O(n^2)$.

--- secondary_color: lightgray --- # Complexité des problèmes & NP-complétude 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. # Complexité des problèmes & NP-complétude 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. # Complexité des problèmes & NP-complétude Le problème du voyageur de commerce est un problème NP-Complet. - [x] Vrai. - [ ] Faux. # Complexité des problèmes & NP-complétude 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 pouvant 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. # Complexité des problèmes & NP-complétude 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.