Quiz d'auto-évaluation

--- secondary_color: lightgray --- # Aborder un problème informatique Formaliser signifie... - [ ] Identifier des algorithmes qui résolvent le problème donné. - [x] Exprimer un problème en utilisant une terminologie et des concepts adaptés. - [ ] Écrire des formules pour estimer 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 une partie de PyRat. - [x] Identifier des algorithmes ou méthodes adaptés pour résoudre le problème formalisé. - [ ] Identifier des problèmes qu'un algorithme donné peut résoudre. # Aborder un problème informatique Ordonnez les étapes à suivre pour aborder un problème informatique. 1. Formaliser. 2. Spécifier. 3. Coder. # Aborder un problème informatique Considérons le problème suivant : on dispose d'une liste de routeurs et des distances entre ces routeurs. Chaque routeur doit être associé à une fréquence, avec la contrainte que deux routeurs proches ne peuvent pas avoir la même fréquence. Le but est de trouver le nombre minimal de fréquences distinctes nécessaires pour résoudre le problème. Quelle est la bonne façon de procéder ? - [x] Formaliser le problème, trouver une solution au problème formalisé, puis coder la solution. - [ ] Trouver une solution au problème, la coder, puis rechercher d'autres solutions possibles dans la littérature. - [ ] Coder une première solution, écrire sa spécification, puis trouver un formalisme adapté pour exprimer le problème.

--- secondary_color: lightgray --- # Graphes & 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 & chemins Les arêtes dans les graphes et dans les graphes orientés sont différentes. À quoi correspondent-elles respectivement ? - [ ] Couples / paires. - [x] Paires / couples. - [ ] Paires / paires. - [ ] Couples / couples. # Graphes & chemins Considérons la séquence d'arêtes $( \{v_1, v_2\}, \{v_2, v_4\}, \{v_4, v_6\} )$ dans un graphe complet de sommets $V = \{v_1, v_2, v_3, v_4, v_5, v_6\}$. Parmi les affirmations suivantes, lesquelles sont vraies ? - [x] C'est un chemin. - [ ] C'est un cycle. - [x] C'est une marche. # Graphes & chemins Considérons $V = \{v_1, v_2, v_3, v_4\}$. Pour quelles valeurs suivantes de $E$ le graphe $G = (V, E)$ est-il 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 & chemins Quelle est la taille d'un graphe complet d'ordre $n$ ? - [x] $\frac{n(n-1)}{2}$. - [ ] $n^2$. - [ ] $2n$. # Graphes & 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 & chemins Considérons un graphe G qui contient les arêtes $\{u, v\}$, $\{u, w\}$ et $\{v, w\}$. Que peut-on 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 & chemins Quelle est la taille d'un graphe dont la matrice d'adjacence est la 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ésenter les 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ésenter les 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ésenter les graphes Considérons une liste avec 10 éléments. Combien d'éléments doivent être parcourus pour atteindre le 6ᵉ élément ? - [ ] 1. - [x] 6. - [ ] 10. # Représenter les graphes Nous utilisons des listes pour stocker les voisins des sommets d'un graphe cycle d'ordre 25. Combien d'éléments une telle structure contient-elle ? - [ ] 25. - [x] 50. - [ ] 625. # Représenter les graphes On veut représenter en mémoire un graphe contenant beaucoup de sommets. Ce graphe possède 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 graphes Un parcours de graphe permet de... - [ ] Couper 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 depuis un sommet initial. # Parcours de graphes Supposons que nous utilisions un DFS depuis le sommet $v_1$ sur un graphe non pondéré. Quelles propositions sont vraies ? - [x] On obtient un arbre couvrant, qui couvre les sommets accessibles depuis $v_1$. - [ ] On obtient les plus courts chemins depuis $v_1$ vers les sommets accessibles du graphe. - [x] On suit un chemin tant qu'il existe des sommets non explorés où aller. - [x] On parcourt chaque arête du graphe exactement une fois. # Parcours de graphes Supposons que nous utilisions un BFS depuis le sommet $v_1$ sur un graphe non pondéré. Quelles propositions sont vraies ? - [ ] On parcourt chaque arête du graphe exactement une fois. - [ ] On suit un chemin tant qu'il existe des sommets non explorés où aller. - [x] On obtient les plus courts chemins depuis $v_1$ vers les sommets accessibles du graphe. - [x] On obtient un arbre couvrant, qui couvre les sommets accessibles depuis $v_1$. # Parcours de graphes Imaginons un graphe où $u$ et $v$ sont deux sommets, et qu'il n'existe aucun chemin reliant $u$ à $v$. Si on lance un DFS depuis $u$, quelles propositions 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 obtenu est composé uniquement de plus courts chemins depuis $u$ vers les sommets accessibles du graphe. # Parcours de graphes Imaginons que nous lançons un DFS (respectivement un BFS) depuis un sommet $u$ d'un graphe complet d'ordre $n$. Combien de sommets sont voisins de $u$ dans l'arbre obtenu ? - [ ] $n-1$ (respectivement 1). - [ ] $\frac{n(n-1)}{2}$ dans les deux cas. - [x] 1 (respectivement $n-1$). # Parcours de graphes Imaginons un graphe avec 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. Quelles propositions sont correctes ? - [x] En parcourant ce graphe avec un DFS depuis $v_1$, on utilise une LIFO. $v_2$, $v_3$ et $v_4$ (dans cet ordre) sont ajoutés à la LIFO, et aucun n'a été visité auparavant. Par conséquent, le prochain sommet visité est $v_4$. - [x] En parcourant ce graphe avec un BFS depuis $v_1$, on utilise une FIFO. $v_2$, $v_3$ et $v_4$ (dans cet ordre) sont ajoutés à la FIFO, et aucun n'a été visité auparavant. Par conséquent, le prochain sommet visité est $v_2$. - [ ] En parcourant ce graphe avec un DFS depuis $v_1$, on utilise une LIFO. $v_2$, $v_3$ et $v_4$ (dans cet ordre) sont ajoutés à la LIFO, et aucun n'a été visité auparavant. Par conséquent, le prochain sommet visité est $v_2$.

--- secondary_color: lightgray --- # Tables de routage Le routage nous aide à... - [x] Naviguer entre deux sommets quelconques d'un graphe. - [ ] Déterminer s'il existe des cycles dans l'arbre couvrant d'un graphe. - [ ] Calculer l'ordre du graphe. # Tables de routage Dans un arbre avec une racine... - [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é. - [ ] Les enfants des sommets dans un arbre couvrant enraciné. # Tables de routage Imaginons 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 : $$\begin{array}{c|ccccc}\textbf{Sommet} & v_1 & v_2 & v_3 & v_4 & v_5 \\\hline\textbf{Parent} & \cdot & v_3 & v_1 & v_2 & v_1\end{array}$$ 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 données & Parcours de graphes 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 données & Parcours de graphes 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 données & Parcours de graphes 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 données & Parcours de graphes 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 retraits consécutifs ? - [ ] 40, 20, 40, 10 (on retire d'abord 40). - [x] 40, 20, 40, 52 (on retire d'abord 40). - [ ] 10, 25, 52, 40 (on retire d'abord 10).