Self-assessment quiz

--- secondary_color: lightgray --- # Aborder un problème informatique Formaliser signifie... - [ ] Identifier des algorithmes qui résolvent le problème posé. - [x] Exprimer un problème en utilisant une terminologie et des concepts adaptés. - [ ] Écrire des formules pour déterminer le temps nécessaire pour résoudre le problème. # Aborder un problème informatique Spécifier signifie... - [ ] Déterminer si vous jouerez le rat ou le python dans un jeu PyRat. - [x] Identifier des algorithmes ou méthodes bien adaptés pour résoudre le problème formalisé. - [ ] Identifier des problèmes qui peuvent être résolus avec un algorithme donné. # Aborder un problème informatique Ordonnez les étapes que vous devez suivre pour aborder un problème informatique. 1. Formaliser. 2. Spécifier. 3. Coder. # Aborder un problème informatique Considérez le problème suivant : on vous donne une liste de routeurs et des proximités entre certains de ces routeurs. Chaque routeur peut être associé à une fréquence, avec la contrainte que deux routeurs en proximité ne doivent pas être associés à la même fréquence. L'objectif est de trouver le nombre minimum de fréquences distinctes à choisir pour résoudre le problème. Quelle serait la bonne manière d'aborder ce problème ? - [x] Trouver un moyen de formaliser le problème, trouver une solution pour résoudre le problème formalisé, puis coder la solution. - [ ] Trouver une solution pour résoudre le problème, la coder, puis chercher d'autres solutions possibles dans la littérature. - [ ] Coder une première solution, écrire sa spécification, puis trouver un formalisme adéquat pour exprimer le problème.

--- secondary_color: lightgray --- # Graphes et chemins Un graphe est composé de deux éléments clés. Lesquels ? - [x] Un ensemble de sommets. - [ ] Un ensemble de cercles. - [ ] Un ensemble de lignes. - [x] Un ensemble d'arêtes. # Graphes et chemins Les arêtes dans les graphes et dans les digraphes sont différentes. À quoi correspondent-elles respectivement ? - [ ] Couples / paires. - [x] Paires / couples. - [ ] Paires / paires. - [ ] Couples / couples. # Graphes et chemins Considérez la séquence d'arêtes $( \{v_1, v_2\}, \{v_2, v_4\}, \{v_4, v_6\} )$ dans un graphe complet avec les sommets $V = \{v_1, v_2, v_3, v_4, v_5, v_6\}$. Lesquelles des affirmations suivantes sont vraies ? - [x] C'est un chemin. - [ ] C'est un cycle. - [x] C'est une marche. # Graphes et chemins Considérez $V = \{v_1, v_2, v_3, v_4\}$. Pour quelles valeurs suivantes de $E$ est-ce que $G = (V, E)$ est un arbre ? - [ ] $\{ \{v_1, v_2\}, \{v_2, v_3\}, \{v_3, v_4\}, \{v_1, v_4\} \}$. - [x] $\{ \{v_1, v_2\}, \{v_2, v_3\}, \{v_3, v_4\} \}$. - [ ] $\{ \{v_1, v_2\}, \{v_3, v_4\} \}$. - [x] $\{ \{v_1, v_2\}, \{v_1, v_3\}, \{v_1, v_4\} \}$. # Graphes et chemins Quelle est la taille d'un graphe complet d'ordre $n$ ? - [x] $\frac{n(n-1)}{2}$. - [ ] $n^2$. - [ ] $2n$. # Graphes et chemins Un graphe complet peut-il être un arbre ? - [ ] Non, jamais. - [ ] Oui, si l'ordre du graphe est un nombre impair. - [x] Oui, si l'ordre du graphe est 1 ou 2. # Graphes et chemins Considérez un graphe G qui contient les arêtes $\{u, v\}$, $\{u, w\}$ et $\{v, w\}$. Que pouvez-vous dire de la séquence $( \{u, v\}, \{v, w\}, \{w, u\} )$ ? - [ ] Ce n'est pas un cycle, car un cycle est une séquence de sommets, pas d'arêtes. - [ ] Ce n'est pas un cycle, car $\{w, u\}$ n'est pas une arête du graphe. - [x] C'est un cycle. # Graphes et chemins Quelle est la taille d'un graphe avec la matrice d'adjacence suivante ? $$\begin{pmatrix} 0 & 1 & 0 & 0 \\ 1 & 0 & 1 & 0 \\ 0 & 1 & 0 & 1 \\ 0 & 0 & 1 & 0 \end{pmatrix}$$ - [x] 3. - [ ] 4. - [ ] 6.

--- secondary_color: lightgray --- # Représentation des graphes Quelles structures de données nécessitent que le nombre d'éléments soit défini à l'avance ? - [x] Un tableau. - [ ] Une liste. - [ ] Un dictionnaire. # Représentation des graphes On stocke la matrice d'adjacence d'un graphe d'ordre 20 dans un tableau. Combien d'éléments ce tableau contient-il ? - [ ] 4. - [ ] 40. - [x] 400. # Représentation des graphes Considérons une liste de 10 éléments. Combien d'éléments faut-il parcourir pour atteindre le 6ème élément ? - [ ] 1. - [x] 6. - [ ] 10. # Représentation des graphes On utilise des listes pour stocker les voisins des sommets d'un graphe cycle d'ordre 25. Combien d'éléments contient une telle structure ? - [ ] 25. - [x] 50. - [ ] 625. # Représentation des graphes Imaginez que l'on veuille représenter un graphe contenant de nombreux sommets en mémoire. On sait que ce graphe a très peu d'arêtes. Quelles structures de données sont adaptées ? - [ ] Un tableau. - [x] Une liste. - [x] Un dictionnaire.

--- secondary_color: lightgray --- # Parcours de graphe Un parcours de graphe est une manière de... - [ ] Diviser le graphe en deux. - [x] Explorer le graphe, un sommet à la fois, en utilisant la connaissance des voisins des sommets explorés. - [x] Obtenir la liste des sommets accessibles à partir d'un sommet initial. # Parcours de graphe Supposons que l'on utilise un DFS depuis le sommet $v_1$ sur un graphe non pondéré. Lesquelles des propositions suivantes sont vraies ? - [x] On obtient un arbre couvrant, couvrant les sommets accessibles depuis $v_1$. - [ ] On obtient les plus courts chemins de v1 vers les sommets accessibles du graphe. - [x] On suit une piste, tant qu'il y a des sommets inexplorés vers lesquels sauter. - [x] On parcourt chaque arête du graphe exactement une fois. # Parcours de graphe Supposons que l'on utilise un BFS depuis le sommet $v_1$ sur un graphe non pondéré. Lesquelles des propositions suivantes sont vraies ? - [ ] On parcourt chaque arête du graphe exactement une fois. - [ ] On suit une piste, tant qu'il y a des sommets inexplorés vers lesquels sauter. - [x] On obtient les plus courts chemins de $v_1$ vers les sommets accessibles du graphe. - [x] On obtient un arbre couvrant, couvrant les sommets accessibles depuis $v_1$. # Parcours de graphe Imaginez un graphe où $u$ et $v$ sont des sommets, et il n'existe aucun chemin dont $u$ et $v$ sont les extrémités. Si l'on lance un DFS depuis $u$, lesquelles des propositions suivantes sont vraies ? - [x] À la fin du DFS, $v$ n'a pas été exploré. - [ ] Le DFS n'est pas bien défini et ne peut pas être exécuté. - [ ] L'arbre résultant est exclusivement constitué des plus courts chemins de $u$ vers les sommets accessibles du graphe. # Parcours de graphe Imaginez que l'on lance un DFS (respectivement un BFS) depuis n'importe quel sommet $u$ d'un graphe complet d'ordre $n$. Combien de sommets sont voisins de $u$ dans l'arbre résultant ? - [ ] $n-1$ (respectivement 1). - [ ] $\frac{n(n-1)}{2}$ dans les deux cas. - [x] 1 (respectivement $n-1$). # Parcours de graphe Imaginez un graphe avec les sommets $V = \{v_1, v_2, v_3, v_4\}$, dans lequel $\{v_1, v_2\}$, $\{v_1, v_3\}$, et $\{v_1, v_4\}$ sont des arêtes. Lesquelles des affirmations suivantes sont correctes ? - [x] Pour parcourir ce graphe en utilisant un DFS depuis $v_1$, on utilise un LIFO. $v_2$, $v_3$, et $v_4$ (dans cet ordre) sont ajoutés au LIFO, et aucun d'eux n'a été visité auparavant. Par conséquent, le prochain sommet à visiter est $v_4$. - [x] Pour parcourir ce graphe en utilisant un BFS depuis $v_1$, on utilise un FIFO. $v_2$, $v_3$, et $v_4$ (dans cet ordre) sont ajoutés au FIFO, et aucun d'eux n'a été visité auparavant. Par conséquent, le prochain sommet à visiter est $v_2$. - [ ] Pour parcourir ce graphe en utilisant un DFS depuis $v_1$, on utilise un LIFO. $v_2$, $v_3$, et $v_4$ (dans cet ordre) sont ajoutés au LIFO, et aucun d'eux n'a été visité auparavant. Par conséquent, le prochain sommet à visiter est $v_2$.

--- secondary_color: lightgray --- # Tables de routage Le routage nous aide à... - [x] Naviguer entre deux sommets quelconques dans un graphe. - [ ] Déterminer s'il y a des cycles dans l'arbre couvrant d'un graphe. - [ ] Calculer l'ordre du graphe. # Tables de routage Dans un arbre enraciné... - [x] Chaque sommet sauf la racine a un parent unique. - [ ] Tous les enfants ont des cousins. - [ ] Chaque sommet a un enfant unique. # Tables de routage Dans une table de routage, on peut trouver... - [ ] Les poids des arêtes entre deux sommets d'un graphe. - [x] Les parents des sommets dans un arbre couvrant enraciné d'un graphe. - [ ] Les enfants des sommets dans un arbre couvrant enraciné d'un graphe. # Tables de routage Imaginez un graphe avec les sommets $V = \{v_1, v_2, v_3, v_4, v_5\}$. Un algorithme de parcours de graphe depuis $v_1$ a produit la table de routage suivante : $$\left[\begin{array}{cccccc} \\ \textbf{Vertex} & v_1 & v_2 & v_3 & v_4 & v_5 \\ \textbf{Parent} & \cdot & v_3 & v_1 & v_2 & v_1 \end{array}\right]$$ Quel est le chemin correspondant entre $v_1$ et $v_4$ ? - [ ] $(\{v_1, v_2\}, \{v_2, v_3\}, \{v_3, v_4\})$. - [ ] $(\{v_1, v_3\}, \{v_3, v_5\}, \{v_4, v_5\})$. - [ ] $(\{v_1, v_2\}, \{v_2, v_4\})$. - [x] $(\{v_1, v_3\}, \{v_2, v_3\}, \{v_2, v_4\})$.

--- secondary_color: lightgray --- # Structures de file pour les parcours de graphe Lorsqu'on retire un élément d'un LIFO, on obtient... - [ ] Le premier élément qui a été ajouté. - [x] Le dernier élément qui a été ajouté. # Structures de file pour les parcours de graphe Lorsqu'on retire un élément d'un FIFO, on obtient... - [x] Le premier élément qui a été ajouté. - [ ] Le dernier élément qui a été ajouté. # Structures de file pour les parcours de graphe Un DFS peut être implémenté en utilisant... - [x] Un LIFO pour stocker les prochains sommets inexplorés à visiter. - [ ] Un LIFO pour stocker la liste de tous les voisins du sommet de départ. - [ ] Un FIFO pour stocker les prochains sommets inexplorés à visiter. # Structures de file pour les parcours de graphe On ajoute les éléments 10, 25, 52, 40, 20, puis 40 à un LIFO (dans cet ordre). Dans quel ordre sont-ils extraits lors de quatre suppressions consécutives ? - [ ] 40, 20, 40, 10 (on dépile d'abord 40). - [x] 40, 20, 40, 52 (on dépile d'abord 40). - [ ] 10, 25, 52, 40 (on dépile d'abord 10).