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. # Aborder un problème informatique La docstring d'une fonction indique « The graph is assumed to be connected ». À quelle étape cette information appartient-elle ? - [ ] Au codage. - [x] À la spécification : c'est une condition d'utilisation du contrat de la fonction. - [ ] À aucune : c'est un simple commentaire.

--- 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] La séquence de sommets correspondante $(v_1, v_2, v_4, v_6)$ 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. # Graphes & chemins Un graphe possède 5 sommets, de degrés 3, 3, 2, 2 et 2. Combien a-t-il d'arêtes ? - [ ] 5. - [x] 6. - [ ] 12. # Graphes & chemins Un graphe peut-il contenir exactement 3 sommets de degré impair ? - [ ] Oui, s'il contient un cycle. - [x] Non, le nombre de sommets de degré impair est toujours pair. - [ ] Oui, s'il n'est pas connexe. # Graphes & chemins Combien d'arêtes possède un arbre d'ordre 10 ? - [x] 9. - [ ] 10. - [ ] 45. # Graphes & chemins Soit ${\bf A}$ la matrice d'adjacence d'un graphe non pondéré. Que vaut l'entrée ${\bf A}^3[u, v]$ ? - [ ] La distance entre $u$ et $v$. - [x] Le nombre de marches de longueur 3 allant de $u$ à $v$. - [ ] 1 s'il existe un chemin de longueur 3 entre $u$ et $v$, 0 sinon.

--- 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. # Représenter les graphes Un graphe d'ordre $n$ est stocké sous forme de matrice d'adjacence. Quelles propositions sont vraies ? - [x] Tester l'existence d'une arête $\{i, j\}$ demande une seule opération. - [x] Lister les voisins d'un sommet demande de parcourir $n$ cases. - [ ] Lister les voisins d'un sommet demande un temps proportionnel à son nombre de voisins.

--- 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. - [ ] 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$. # Parcours de graphes Quelle est la complexité d'un BFS sur un graphe à $n$ sommets et $m$ arêtes, stocké avec des listes de voisins et utilisant une vraie FIFO ? - [x] $O(n + m)$. - [ ] $O(n^2)$. - [ ] $O(n \times m)$. # Parcours de graphes On veut une FIFO efficace en Python. Quelles propositions sont vraies ? - [x] Avec une liste, `pop(0)` décale tous les éléments restants, donc son coût est proportionnel à la taille de la liste. - [ ] Avec une liste, `pop(0)` retire le dernier élément au lieu du premier. - [x] `collections.deque` et sa méthode `popleft()` retirent le premier élément en temps constant. # Parcours de graphes Le labyrinthe contient de la boue. Le chemin trouvé par un BFS est-il le plus rapide en nombre de tours ? - [ ] Oui, le BFS donne toujours un plus court chemin. - [x] Pas forcément : il minimise le nombre d'arêtes, pas la somme des poids. - [ ] Non, il ne trouve même pas de chemin dans un graphe pondéré. # Parcours de graphes Qu'est-ce qui garantit qu'un parcours termine sur un graphe fini contenant des cycles ? - [ ] L'utilisation d'une FIFO plutôt que d'une LIFO. - [x] L'ensemble des sommets déjà explorés, qui empêche d'explorer deux fois un même sommet. - [ ] Le fait que le graphe soit connexe. # Parcours de graphes Un DFS récursif est lancé dans un labyrinthe en forme de couloir de 5000 cases. Que risque-t-il de se passer en Python avec les réglages par défaut ? - [x] Une `RecursionError`, car la profondeur de récursion est limitée à 1000 appels. - [ ] Rien de particulier, la récursion n'a pas de limite. - [ ] Le parcours renvoie des chemins plus longs.

--- 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\})$ # Tables de routage Dans un couloir de $n$ cases, on veut connaître un plus court chemin depuis une extrémité vers chaque case. Quelle mémoire faut-il ? - [x] $O(n^2)$ si l'on stocke explicitement chaque chemin. - [x] $O(n)$ avec une table de routage. - [ ] $O(n^2)$ dans les deux cas. # Tables de routage On effectue un BFS depuis le morceau de fromage (et non depuis le rat). Que représente le parent de la case du rat dans la table obtenue ? - [ ] La case précédente sur le chemin du rat depuis sa position initiale. - [x] La prochaine case où aller pour se rapprocher du fromage. - [ ] Le fromage lui-même.

--- secondary_color: lightgray --- # Structures de données & Parcours de graphes Lorsqu'on retire un élément d'une 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'une 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] Une LIFO pour stocker les prochains sommets inexplorés à visiter. - [ ] Une LIFO pour stocker la liste de tous les voisins du sommet de départ. - [ ] Une 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 à une 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). # Structures de données & Parcours de graphes Quelle structure les langages de programmation utilisent-ils pour gérer les adresses de retour des appels de fonctions ? - [x] Une pile (LIFO). - [ ] Une file (FIFO). - [ ] Un dictionnaire. # Structures de données & Parcours de graphes Le DFS et le BFS peuvent s'écrire comme un même algorithme. Qu'est-ce qui les distingue alors ? - [ ] La manière de construire la table de routage. - [x] La structure de données utilisée : une LIFO pour le DFS, une FIFO pour le BFS. - [ ] Le fait de marquer ou non les sommets explorés.