Année académique 2022-2023
Unité Pédagogique Mathématiques
UE : Complexité des algorithmes et des problèmes Prof. : Prof. DIABY Moustapha
Parcours : Master 1 Dr. BROU Pacôme
Filière : INFO, RTEL, MBDS et IABD
Important à lire :
- Les copies conformes seront automatiquement sanctionnées d’une note de 0/20.
- Tout documents est formellement interdit
- Tout appareil électronique doit être éteint (Téléphone, Ordinateur, Tablette, etc.).
DEVOIR DE NIVEAU / Durée : 2h00 - samedi 12 nov. 2022
Exercice 1 Question de cours
1. On vous demande d’ordonner les expressions suivantes de manière que chacune soit en grand
O de la suivante :
2 0 4
2x ; (2,2x + 1) ; 4x ; e3x ; e2x +x
4
2. Quelles sont les ressources dans un ordinateur qui permettent d’analyser la complexité d’un
algorithme en temps et en espace ?
3. Trouvez f(𝑛) telle que : T1 (𝑛) = (𝑛 + 1)2 soit en O(f). Idem pour T2 (𝑛) = (a𝑛 + b)2
Exercice 2
1. Évaluer (au mieux) la complexité des problèmes suivants :
a. Calcul du déterminant d'une matrice ;
b. Calcul d'un vecteur x solution de A𝑥 = b, où A est une matrice et b un vecteur ;
2. Franck soutien que vu qu’problème de la classe P est également un problème NP, le problème de
tri dans un tableau est aussi difficile que le problème de recherche d’un cycle Hamiltonien dans
un graphe. Qu’en pensez-vous ?
Exercice 3 Autour des graphes
1. On considère l’algorithme suivant permettant de calculer le degré de tous les sommets d’un
graphe non orienté. Déterminez sa complexité
B : matrice d’incidence d’un graphe G non orienté
Degres(A) :
1: pour i de 1 à n faire
2: degres[i] ← 0
3: pour e de 1 à m faire
4: degre[i] ← degre[i] + B[i, e]
5: fin pour
6: fin pour
7: retourner degrés
2. L’algorithme suivant permet de tester si deux sommets sont voisins en utilisant la
représentation d’un graphe par sa liste d’adjacence. Déterminez sa complexité
G : un graphe (non orienté)
u, v : deux sommets de G
Teste si v est voisin de u
SontVoisins(G, u, v) :
1: pour tout w ∈ Adj(u) faire
2: si w = v alors
3: retourner VRAI
4: fin si
5: fin pour
6: retourner FAUX
3. Donnez un algorithme qui utilise la représentation d’un graphe (non orienté) par sa liste
d’adjacence pour déterminer le dégré de tous les sommets et déterminez sa complexité.
4. Donner un algorithme qui utilise la représentation d’un graphe par sa matrice d’adjacence pour
tester si deux sommets sont voisins et déterminez sa complexité.
