Quiz d'auto-évaluation

--- secondary_color: lightgray --- # Algorithme de Dijkstra Lors de l'exécution de l'algorithme de Dijkstra sur un graphe pondéré à partir du sommet $u$, quelles conditions suivantes sont (indépendamment) suffisantes pour garantir que les résultats de l'algorithme de Dijkstra sont les plus courts chemins depuis le sommet $u$ vers les sommets accessibles du graphe ? - [ ] Le graphe d'entrée est connexe. - [x] Le graphe d'entrée contient uniquement des poids non négatifs. - [ ] Le graphe d'entrée ne contient aucun cycle absorbant. # Algorithme de Dijkstra Quelle propriété suivante décrit le mieux le fonctionnement de l'algorithme de Dijkstra, en partant d'un sommet $u$ ? - [ ] Nous explorons les sommets comme nous le ferions pour un BFS. - [ ] Nous explorons les sommets par nombre de sauts croissant depuis $u$ dans le graphe. - [x] Nous explorons les sommets par distance croissante depuis $u$ dans le graphe. # Algorithme de Dijkstra L'algorithme de Dijkstra maintient deux structures de données tout au long du processus. Quelles sont-elles ? - [ ] Une estimation de l'ordre du graphe et une estimation de la taille du graphe. - [x] La liste des sommets explorés et une estimation des distances de $u$ aux autres sommets du graphe. - [ ] La liste des sommets explorés et la liste des arêtes explorées. # Algorithme de Dijkstra Lesquelles des affirmations suivantes s'appliquent à l'algorithme de Dijkstra ? - [ ] C'est un algorithme qui ne fonctionne que sur les arbres. - [x] C'est un algorithme qui garantit de fournir les plus courts chemins depuis un sommet initial lorsque les poids du graphe d'entrée sont non négatifs. - [ ] C'est un algorithme qui donne la taille du graphe d'entrée. - [x] C'est un algorithme de parcours qui explore les sommets par distance croissante depuis un sommet initial. # Algorithme de Dijkstra Dans la version présentée dans la vidéo, où `add_or_replace(...)` garantit qu'un sommet est au plus une fois dans le tas min, quel est le nombre maximum d'itérations de la boucle principale de l'algorithme de Dijkstra, appliqué à un graphe d'ordre $n$ ? - [ ] $n/2$. - [x] $n$. - [ ] $n(n-1)/2$. # Algorithme de Dijkstra Quelle est la table de routage obtenue par l'algorithme de Dijkstra depuis le sommet $v_0$ sur ce graphe ?

 - [ ] $$\left[\begin{array}{cccccc} \\ \textbf{Sommet} & v_0 & v_1 & v_2 & v_3 & v_4 \\ \textbf{Parent} & \cdot & v_0 & v_0 & v_2 & v_1 \end{array}\right]$$ - [x] $$\left[\begin{array}{cccccc} \\ \textbf{Sommet} & v_0 & v_1 & v_2 & v_3 & v_4 \\ \textbf{Parent} & \cdot & v_0 & v_1 & v_2 & v_1 \end{array}\right]$$ - [ ] $$\left[\begin{array}{cccccc} \\ \textbf{Sommet} & v_0 & v_1 & v_2 & v_3 & v_4 \\ \textbf{Parent} & \cdot & v_0 & v_1 & v_1 & v_1 \end{array}\right]$$ # Algorithme de Dijkstra Avec un tas min binaire (`heapq`), quelle est la complexité de l'algorithme de Dijkstra sur un graphe à $n$ sommets et $m$ arêtes ? - [ ] $O(n + m)$. - [x] $O((n + m) \cdot log(n))$. - [ ] $O(n^3)$. # Algorithme de Dijkstra On considère un graphe orienté avec un arc $(u, a)$ de poids 2, un arc $(u, b)$ de poids 3 et un arc $(b, a)$ de poids $-2$. Quelle distance de $u$ à $a$ l'algorithme de Dijkstra lancé depuis $u$ renvoie-t-il ? - [x] 2, alors que le chemin passant par $b$ a une longueur de 1. - [ ] 1, car l'algorithme finit par trouver le chemin passant par $b$. - [ ] Aucune : l'algorithme ne termine pas. # Algorithme de Dijkstra On cherche uniquement un plus court chemin de $u$ vers une cible $t$. À quel moment peut-on arrêter l'algorithme de Dijkstra ? - [ ] Dès que $t$ est ajouté au tas min. - [x] Dès que $t$ est exploré, c'est-à-dire retiré du tas min pour la première fois. - [ ] Jamais : il faut attendre que le tas min soit vide. # Algorithme de Dijkstra Dans un labyrinthe sans boue (toutes les arêtes ont un poids de 1), lesquelles de ces affirmations sont vraies ? - [x] Dijkstra trouve des chemins de même longueur que ceux du BFS. - [x] Le BFS est préférable, car sa complexité est plus faible. - [ ] Dijkstra trouve des chemins strictement plus courts que ceux du BFS.

--- secondary_color: lightgray --- # Tas minimaux Un tas minimal contient les couples `(clé, valeur)` suivants : $\{(A, 25), (B, 37), (C, 5) \}$. Quel est le prochain couple qui sera supprimé ? - [ ] $(B, 37)$. - [x] $(C, 5)$. - [ ] $(A, 25)$. # Tas minimaux Un tas minimal contient les couples `(clé, valeur)` suivants : $\{(A, 55), (B, 22), (C, 32), (D, 87)\}$. Sélectionnez les assertions correctes : - [x] Si on ajoute ou remplace avec $(A, 32)$, l'état résultant sera $\{(A, 32), (B, 22), (C, 32), (D, 87)\}$. - [ ] Si on ajoute ou remplace avec $(B, 53)$, l'état résultant sera $\{(A, 55), (B, 53), (C, 32), (D, 87)\}$. - [x] Le prochain élément à être supprimé est $(B, 22)$. - [ ] Le prochain élément à être supprimé est $(D, 87)$. - [x] Si on ajoute ou remplace avec $(D, 86)$, l'état résultant sera $\{(A, 55), (B, 22), (C, 32), (D, 86)\}$. # Tas minimaux L'algorithme de Dijkstra peut être implémenté... - [ ] En utilisant un tas minimal, en stockant les sommets comme valeurs, et les distances à la position de départ comme clés. - [x] En utilisant un tas minimal, en stockant les sommets comme clés, et les distances à la position de départ comme valeurs. - [ ] En utilisant deux tas minimaux, un pour les arêtes, un pour les sommets. # Tas minimaux Considérons un tas minimal avec les couples `(clé, valeur)` $\{ (A, 5), (B, 3), (C, 7) \}$. Quel est le nombre minimum d'opérations (`add_or_replace(...)` ou `remove(...)`) pour obtenir la configuration $\{ (B, 8), (C, 7)\}$ ? - [ ] 2. - [x] 3. - [ ] 4. # Tas minimaux On exécute `heapq.heappush(heap, ("A", 50))` puis `heapq.heappush(heap, ("B", 22))` sur une liste vide `heap`. Que renvoie ensuite `heapq.heappop(heap)` ? - [x] `("A", 50)`, car les tuples sont comparés d'abord sur leur première composante. - [ ] `("B", 22)`, car `heapq` compare toujours les valeurs numériques. - [ ] Une erreur, car `heapq` ne sait pas comparer des tuples. # Tas minimaux Avec `heapq`, que se passe-t-il si l'on ajoute un sommet déjà présent dans le tas, avec une distance plus petite ? - [ ] L'ancienne entrée est remplacée par la nouvelle. - [ ] L'ajout est ignoré. - [x] Le sommet est présent deux fois dans le tas : dans l'algorithme de Dijkstra, seul son premier retrait compte, et les suivants sont ignorés. # Tas minimaux Un tas contient $k$ éléments. Lesquelles de ces affirmations sont vraies ? - [x] Avec l'implémentation naïve à base de liste, un retrait coûte $O(k)$ opérations. - [x] Avec `heapq` (un tas binaire), un ajout ou un retrait coûte $O(log(k))$ opérations. - [ ] Avec `heapq`, un ajout ou un retrait se fait en temps constant. - [ ] Avec l'implémentation naïve à base de liste, un retrait coûte $O(k^2)$ opérations. # Tas minimaux Lesquelles de ces propriétés sont vraies pour un tas binaire, comme celui de `heapq` ? - [x] La valeur de chaque nœud est inférieure ou égale à celles de ses enfants. - [x] L'élément de plus petite valeur est toujours à la racine. - [ ] À chaque niveau de l'arbre, les éléments sont triés de gauche à droite. - [ ] L'arbre peut prendre la forme d'une longue chaîne.