Algorithmique et structures de données : pack de révision

Formulaires, étapes clés de la méthode pour chaque thème et 6 exercices, avec les corrigés complets à la fin.

Nouveaux exercicesRetour au cours

Dans la fenêtre d’impression, choisissez « Enregistrer au format PDF » pour garder une copie sur votre appareil.

1Formules et méthodes

Théorie des graphes

Lemme des poignées de main
Σ deg(v) = 2|E|
Graphes complets
|E(Kn)| = n(n − 1)/2, |E(Km,n)| = m·n
Graphe régulier
|E| = n·k/2
Arbre et forêt
|E| = n − 1, |E| = n − c
Feuilles d’un arbre
L = 2 + Σ (deg(v) − 2) over deg(v) ≥ 3
Euler
circuit : tous les degrés pairs ; chemin : exactement 2 degrés impairs
Circuits hamiltoniens dans Kn
(n − 1)!/2
Mise à jour de Dijkstra
d(v) = min(d(v), d(u) + w(u, v))
Marches de longueur L
(Mᴸ)ij

Méthode

  1. Notez le degré de chaque sommet ; la somme des degrés vaut deux fois le nombre d’arêtes.
  2. Pour les questions d’Euler, vérifiez que le graphe est connexe et comptez les sommets de degré impair.
  3. Pour les arbres, utilisez n − 1 arêtes et le lemme des poignées de main.
  4. Pour Dijkstra, tenez un tableau des distances provisoires et fixez à chaque tour le sommet non fixé de plus petite distance.
  5. Pour un arbre couvrant minimal, triez les arêtes par poids et sautez toute arête qui ferme un cycle (Kruskal), ou faites croître un arbre à partir d’un sommet de départ (Prim).

2Exercices

1.Algorithmes et complexitéMoyen

Le parcours en largeur (BFS) sur un graphe non pondéré trouve :

  1. AUn ordre topologique dans tous les graphes
  2. BL'arbre couvrant de poids minimal
  3. CLes plus courts chemins dans les graphes qui contiennent des poids d'arêtes négatifs
  4. DLes plus courts chemins en nombre d'arêtes depuis le nœud de départ
2.Algorithmes et complexitéDifficile

Quelle définition de la classe NP est correcte ?

  1. ALes problèmes qui ne peuvent pas être résolus en temps polynomial
  2. BLes problèmes de décision dont les réponses « oui » peuvent être vérifiées en temps polynomial à l'aide d'un certificat
  3. CLes problèmes qu'aucun algorithme ne peut résoudre
  4. DLes problèmes qui ne sont pas polynomiaux
3.Structures de donnéesMoyen

Vous avez une référence vers un nœud au milieu d'une liste. Dans quelle liste pouvez-vous le supprimer en O(1) ?

  1. AUn tableau trié
  2. BUne liste doublement chaînée
  3. CUne liste simplement chaînée
  4. DUn tableau dynamique
4.Structures de donnéesDifficile

Pour chaque élément d'un tableau, vous voulez le prochain élément plus grand à sa droite, en O(n) au total. Quelle structure aide ?

  1. AUne file contenant toutes les paires d'éléments
  2. BUne pile qui conserve les éléments en attente de leur réponse
  3. CUne table de hachage de tous les éléments
  4. DUn arbre binaire de recherche reconstruit pour chaque élément
5.Théorie des graphesMoyen
ABCDEFCircuit eulérienChemin eulérien, pas de circuitni l’une ni l’autre

Le graphe connexe a-t-il un circuit eulérien, un chemin eulérien qui n’est pas un circuit, ou ni l’un ni l’autre ? Cliquez sur votre réponse.

|V| = 6|E| = 6
  1. 1Circuit eulérien
  2. 2Chemin eulérien, pas de circuit
  3. 3ni l’une ni l’autre
6.Théorie des graphesDifficile
ABCDE

Combien de marches fermées de longueur 3 partent de C et y reviennent ? Une marche peut répéter des sommets et des arêtes. Appelez ce nombre N.

M = matrice d’adjacenceL = 3
N =

3Solutions

1.Algorithmes et complexité

Réponse: D · Les plus courts chemins en nombre d'arêtes depuis le nœud de départ

Pourquoi c'est la réponse

BFS visite les nœuds par ordre de distance (en arêtes) depuis la source ; il trouve donc les plus courts chemins non pondérés en O(V + E).

Réponse

D · Les plus courts chemins en nombre d'arêtes depuis le nœud de départ
2.Algorithmes et complexité

Réponse: B · Les problèmes de décision dont les réponses « oui » peuvent être vérifiées en temps polynomial à l'aide d'un certificat

Pourquoi c'est la réponse

Pour un problème NP, une solution proposée (certificat) peut être vérifiée rapidement, par exemple vérifier qu'une affectation donnée satisfait une formule booléenne.

Réponse

B · Les problèmes de décision dont les réponses « oui » peuvent être vérifiées en temps polynomial à l'aide d'un certificat
3.Structures de données

Réponse: B · Une liste doublement chaînée

Pourquoi c'est la réponse

Un nœud doublement chaîné connaît son prédécesseur, on peut donc relier directement prev et next ; une liste simplement chaînée doit rechercher le prédécesseur.

Réponse

B · Une liste doublement chaînée
4.Structures de données

Réponse: B · Une pile qui conserve les éléments en attente de leur réponse

Pourquoi c'est la réponse

En parcourant de gauche à droite, on dépile chaque élément plus petit que l'élément courant (l'élément courant est leur réponse), puis on empile celui-ci ; chaque élément est déplacé au plus deux fois.

Réponse

B · Une pile qui conserve les éléments en attente de leur réponse
5.Théorie des graphes

Réponse: Circuit eulérien

Euler, Hamilton et arbres : un graphe connexe a un circuit eulérien (chaque arête une fois, retour au départ) quand tous les sommets ont un degré pair, et un chemin eulérien qui n’est pas un circuit quand exactement deux sommets ont un degré impair ; le chemin va alors d’un sommet impair à l’autre. Un circuit hamiltonien visite chaque sommet une fois ; Kn en a (n − 1)!/2. Un arbre à n sommets a n − 1 arêtes, et un graphe connexe à m arêtes conserve un arbre couvrant après suppression de m − n + 1 arêtes.

Degrés

deg(A) = 2, deg(B) = 2, deg(C) = 2, deg(D) = 2, deg(E) = 2, deg(F) = 2

Sommets impairs

0
Circuit eulérien

Réponse

Circuit eulérien
6.Théorie des graphes

Réponse: N = 4

Degrés : le degré d’un sommet est le nombre d’arêtes qui y aboutissent. Chaque arête a deux extrémités, donc les degrés totalisent deux fois le nombre d’arêtes : Σ deg(v) = 2|E| (le lemme des poignées de main). Le nombre de sommets de degré impair est donc pair. Kn a n(n − 1)/2 arêtes, un graphe k-régulier à n sommets en a nk/2, et un arbre à n sommets a n − 1 arêtes.

Matrice d’adjacence

A: 0 1 1 0 0
B: 1 0 1 1 1
C: 1 1 0 0 1
D: 0 1 0 0 1
E: 0 1 1 1 0

Un pas de plus

(M³)CC = 1·1 + 2·1 + 3·0 + 2·0 + 1·1 = 4

Réponse

N = 4

ExamProblems · examproblems.com/courses/data-structures-and-algorithms