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 le plus court chemin passant une et une seule fois par tous les sommets d'un graphe pondéré, à partir d'un sommet initial (avec ou sans retour à ce sommet). # 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 Dans PyRat, le méta-graphe utilisé pour attraper tous les morceaux de fromage... - [x] A pour sommets la position initiale du joueur et les cases contenant un morceau de fromage. - [x] Est un graphe complet, dont le poids de chaque arête est la longueur d'un plus court chemin entre ses extrémités dans le labyrinthe. - [ ] A pour sommets toutes les cases du labyrinthe, et pour arêtes les passages entre cases voisines. - [ ] Suffit pour déplacer le joueur : il n'est plus nécessaire de garder les chemins trouvés dans le labyrinthe. # 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é. # Le problème du voyageur de commerce Le rat part d'une case fixée et doit ramasser $k$ morceaux de fromage, sans revenir à son point de départ. Combien d'ordres de ramassage différents existe-t-il ? - [ ] $k^2$. - [ ] $2^k$. - [x] $k!$. - [ ] $\frac{(k-1)!}{2}$. # Le problème du voyageur de commerce Pourquoi les poids du méta-graphe vérifient-ils l'inégalité triangulaire $d(a, c) \leq d(a, b) + d(b, c)$ ? - [x] Parce que mettre bout à bout un plus court chemin de $a$ à $b$ et un plus court chemin de $b$ à $c$ donne un chemin de $a$ à $c$, qui ne peut pas être plus court que le plus court chemin de $a$ à $c$. - [ ] Parce que le labyrinthe ne contient pas de boue. - [ ] Parce que le méta-graphe est un graphe complet. # Le problème du voyageur de commerce Concernant l'algorithme de Held-Karp avec $k$ morceaux de fromage, lesquelles des affirmations suivantes sont vraies ? - [x] Il trouve toujours un chemin optimal. - [x] Sa complexité en temps est $O(k^2 \cdot 2^k)$ : elle reste exponentielle, mais bien plus petite que $k!$. - [x] Sa consommation de mémoire, en $O(k \cdot 2^k)$, devient vite sa vraie limite. - [ ] Sa complexité est polynomiale, ce qui montre que P = NP.

--- 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 chemins et interrompt immédiatement l'examen d'un chemin plus long que le plus court trouvé jusqu'à présent. - [x] Est garanti de trouver le chemin le plus court. - [ ] Explore aléatoirement seulement un sous-ensemble de tous les chemins et renvoie le plus court chemin de ce sous-ensemble, mais n'est pas garanti de trouver le plus court chemin 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 ? - [ ] La complexité du backtracking est polynomiale, car il coupe des branches. - [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 chemin partiel est supérieure à celle du meilleur chemin 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] Le backtracking trouve toujours un chemin optimal, comme la recherche exhaustive. # Bruteforce & backtracking pour résoudre les problèmes NP-complets Dans l'algorithme de branch-and-bound pour le TSP, lesquelles des affirmations suivantes sont vraies ? - [x] La borne inférieure d'une branche ne doit jamais dépasser la longueur du meilleur chemin qui la prolonge, sinon on risque de couper la solution optimale. - [x] Compléter une branche de manière gloutonne donne une borne supérieure. - [x] Une borne plus fine coupe plus de branches, mais peut coûter plus cher à calculer. - [ ] C'est un algorithme approché, qui ne garantit pas de trouver la solution optimale. # Bruteforce & backtracking pour résoudre les problèmes NP-complets Quelle est la complexité (dans le pire des cas) de la résolution du TSP à $n$ villes par backtracking ? - [ ] Polynomiale, car le backtracking coupe des branches. - [x] La même que celle de la recherche exhaustive, en $O(n!)$ à un facteur polynomial près. - [ ] Linéaire, si l'on explore d'abord les voisins les plus proches.

--- 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(|V| + |E|)$, où $V$ et $E$ sont les ensembles des sommets et des arêtes du graphe. - [ ] $O(|E| \cdot log(|V|))$, où $V$ et $E$ sont les ensembles des sommets et des arêtes 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)$. - [x] $O(n^3)$. # Complexité des algorithmes 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)$. # Complexité des algorithmes On parcourt une liste `path` de $n$ sommets, et pour chacun, on teste `if vertex not in visited`, où `visited` est une liste qui grandit à chaque tour. Lesquelles des affirmations suivantes sont vraies ? - [ ] Le code est en $O(n)$, car il ne contient qu'une seule boucle. - [x] Le code est en $O(n^2)$, car `in` parcourt toute la liste `visited` à chaque tour. - [ ] La complexité reste quadratique si `visited` est un ensemble (`set`). # Complexité des algorithmes Un ordinateur 1000 fois plus rapide permet de traiter, dans le même temps... - [x] Environ 10 éléments de plus avec un algorithme en $O(2^n)$. - [x] Seulement 2 ou 3 éléments de plus avec un algorithme en $O(n!)$. - [ ] 1000 fois plus d'éléments avec un algorithme en $O(n!)$.

--- 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-complets, 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 La version de décision du TSP (existe-t-il un chemin de longueur au plus $L$ ?) 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 forcément de l'ordre de $n^2$, et pas moins. - [ ] Le problème est au moins aussi difficile que le TSP. # Complexité des problèmes & NP-complétude Lesquelles des affirmations suivantes sont vraies ? - [x] La version de décision du TSP (existe-t-il un chemin de longueur au plus $L$ ?) est NP-complète. - [x] La version d'optimisation du TSP est NP-difficile. - [ ] La version d'optimisation du TSP est NP-complète, car elle est dans NP. - [ ] Un problème NP-difficile est forcément dans NP. # Complexité des problèmes & NP-complétude Lesquelles des affirmations suivantes sur la classe NP sont vraies ? - [x] Elle contient des problèmes de décision, dont la réponse est « oui » ou « non ». - [x] Lorsque la réponse est « oui », il existe un certificat que l'on peut vérifier en temps polynomial. - [x] Tout problème de P est aussi dans NP. - [ ] C'est la classe des problèmes qui ne peuvent pas être résolus en temps polynomial. # Complexité des problèmes & NP-complétude Pour montrer qu'un problème $Q$ est NP-complet, il faut... - [x] Montrer que $Q$ est dans NP. - [x] Réduire en temps polynomial à $Q$ un problème déjà connu pour être NP-complet. - [ ] Réduire $Q$ à un problème déjà connu pour être NP-complet. - [ ] Montrer qu'aucun algorithme polynomial ne résout $Q$. # Complexité des problèmes & NP-complétude On dispose d'un algorithme qui résout la version de décision du TSP. Comment obtenir la longueur du meilleur chemin ? - [x] Par dichotomie sur la longueur $L$, en $O(log(W))$ appels, où $W$ est la somme de tous les poids. - [ ] C'est impossible : la version de décision ne donne qu'une réponse « oui » ou « non ». - [ ] En appelant l'algorithme pour toutes les valeurs de $L$ entre 0 et $W$, ce qui reste polynomial en la taille de l'entrée.