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 pondéré d'entrée est un arbre. # 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 en augmentant les sauts depuis $u$ dans le graphe. - [x] Nous explorons les sommets en augmentant la distance 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 en augmentant la distance depuis un sommet initial. # Algorithme de Dijkstra Quel est le nombre maximum d'itérations de la boucle principale de l'algorithme de Dijkstra, lorsqu'il est 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]$$

--- 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.