Exercice 1:

Supposons que nous utilisions l’algorithme le plus court chemin de source unique de Dijkstra sur le graphe dirigé pondéré suivant une arête avec le sommet P comme source. Dans quel ordre les nœuds sont-ils inclus dans l'ensemble des sommets pour lesquels les distances de chemin les plus courtes sont finalisées ? 

Exercice 2 :

Une entreprise de réseau utilise une technique de compression pour coder le message avant de le transmettre sur le réseau. Supposons que le message contienne les caractères suivants avec leur fréquence:

character   Frequency

    a           5

    b           9

    c           12

    d           13

    e           16

    f           45

Chaque caractère du message d'entrée prend 1 octet. Si la technique de compression utilisée est le codage de Huffman, combien de bits seront sauvegardés dans le message?

Solution :

Nombre total de caractères dans le message = 100.

Chaque personnage prend 1 octet. Donc, nombre total de bits nécessaires = 800.

Après le codage Huffman, les personnages peuvent être représentés avec:

f: 0

c: 100

d: 101

a: 1100

b: 1101

e: 111

Nombre total de bits nécessaires = 224

Par conséquent, le nombre de bits enregistrés = 800 - 224 = 576

Voir ici pour une explication complète et un algorithme.

Exercice 3 :

Quelle est la complexité temporelle du codage de Huffman?

O (nlogn) où n est le nombre de caractères uniques. Si vous avez n nœuds, extractMin () est appelée 2 * (n - 1) fois. extractMin () prend O (logn) en appelant minHeapify (). Donc, la complexité globale est O (nlogn).

Exercice 4 :

Considérant le graphe non dirigé ci-dessous:

En utilisant l'algorithme de Prim pour construire un arbre couvrant minimal commençant par le noeud A, laquelle des séquences d'arêtes suivantes représente un ordre possible dans lequel les bords seraient ajoutés pour construire l'arbre minimal?

Exercice :

Considérez les poids et les valeurs des éléments énumérés ci-dessous. Notez qu'il n'y a qu'une seule unité de chaque élément.

La tâche consiste à choisir un sous-ensemble de ces éléments, de sorte que leur poids total ne dépasse pas 11 kg et que leur valeur totale soit maximisée. De plus, aucun article ne peut être fractionné. La valeur totale des éléments choisis par un algorithme optimal est notée Vopt. Un algorithme glouton trie les éléments en fonction de leur rapport valeur / poids en ordre décroissant et les emballe avidement à partir du premier élément de la liste ordonnée. La valeur totale des éléments choisis par l'algorithme glouton est notée par Vgreedy. La valeur de Vopt - Vgreedy est ______.