Self-assessment quiz

--- 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 du sommet $u$ vers les sommets accessibles du graphe ? - [ ] Le graphe d'entrée est connexe. - [X] Le graphe d'entrée ne contient que 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$ ? - [ ] On explore les sommets comme on le ferait pour un BFS. - [ ] On explore les sommets en augmentant le nombre de sauts depuis $u$ dans le graphe. - [X] On explore 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. Lesquelles ? - [ ] 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 des arbres. - [X] C'est un algorithme qui garantit de fournir les plus courts chemins à partir d'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 maximal 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 Quel est le tableau de routage obtenu en utilisant l'algorithme de Dijkstra à partir du sommet $v_0$ sur le graphe suivant ?  - [ ] $$\left[\begin{array}{cccccc} \\ \textbf{Vertex} & 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{Vertex} & 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{Vertex} & 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 minimum (min-heaps) Un tas minimum contient les couples (clé, valeur) suivants : $\{(A, 25), (B, 37), (C, 5) \}$. Quel est le prochain couple qui sera retiré ? - [ ] $(B, 37)$. - [X] $(C, 5)$. - [ ] $(A, 25)$. ## Tas minimum (min-heaps) Un tas minimum contient les couples (clé, valeur) suivants : $\{(A, 55), (B, 22), (C, 32), (D, 87)\}$. Sélectionnez les affirmations correctes : - [X] Si on effectue add ou replace avec $(A, 32)$, le statut résultant sera $\{(A, 32), (B, 22), (C, 32), (D, 87)\}$. - [ ] Si on effectue add ou replace avec $(B, 53)$, le statut résultant sera $\{(A, 55), (B, 53), (C, 32), (D, 87)\}$. - [X] Le prochain élément à être retiré est $(B, 22)$. - [ ] Le prochain élément à être retiré est $(D, 87)$. - [X] Si on effectue add ou replace avec $(D, 86)$, le statut résultant sera $\{(A, 55), (B, 22), (C, 32), (D, 86)\}$. # Tas minimum (min-heaps) L'algorithme de Dijkstra peut être implémenté... - [ ] En utilisant un tas minimum, en stockant les sommets comme valeurs, et les distances à la position de départ comme clés. - [X] En utilisant un tas minimum, en stockant les sommets comme clés, et les distances à la position de départ comme valeurs. - [ ] En utilisant deux tas minimum, un pour les arêtes, un pour les sommets. # Tas minimum (min-heaps) Considérons un tas minimum 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.

--- secondary_color: lightgray --- # Complexité algorithmique La complexité d'un algorithme est une mesure de... - [X] Le nombre maximal d'opérations élémentaires nécessaires à son exécution, en fonction de la taille de l'entrée. - [ ] Le nombre minimal d'opérations élémentaires nécessaires à son exécution, en fonction de la taille de l'entrée. - [ ] Le nombre moyen d'opérations élémentaires nécessaires à son exécution, en fonction de la taille de l'entrée. # Complexité algorithmique La notation big-O (ou comportement asymptotique) nous permet d'ignorer... - [ ] Les constantes et termes de bas ordre car ils sont trop difficiles à calculer précisément. - [ ] Le micro. - [X] Les constantes et termes de bas ordre car ils ne comptent pas lorsque la taille du problème devient suffisamment grande. # Complexité algorithmique 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é algorithmique Pour une taille d'entrée $n$, un algorithme donné effectue exactement $3n^2 + 4n + 17$ opérations élémentaires. Lesquelles des notations big-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 requiert 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 ? - [ ] Comme cela dépend du nombre d'arêtes, elle ne peut pas être définie. - [ ] $O(n)$. - [X] $O(n^2)$.