Scribd
Importer
2 vues4 pages

Algorithmique Avancée Et Complexité Corrigé Examen Du Janvier 2026

Le document présente un corrigé d'examen sur l'algorithmique avancée et la complexité, comprenant des exercices sur la notation asymptotique, la complexité des algorithmes, le tri rapide et l'alignement de chaînes. Il détaille les méthodes de comparaison de fonctions, les algorithmes itératifs et récursifs, ainsi que la programmation dynamique. Les résultats incluent des analyses de complexité et des exemples d'implémentation.

Transféré par

TIGER GAMER
Copyright
© All Rights Reserved
Nous prenons très au sérieux les droits relatifs au contenu. Si vous pensez qu’il s’agit de votre contenu, signalez une atteinte au droit d’auteur ici.
Formats disponibles
Téléchargez aux formats PDF, TXT ou lisez en ligne sur Scribd
2 vues4 pages

Algorithmique Avancée Et Complexité Corrigé Examen Du Janvier 2026

Le document présente un corrigé d'examen sur l'algorithmique avancée et la complexité, comprenant des exercices sur la notation asymptotique, la complexité des algorithmes, le tri rapide et l'alignement de chaînes. Il détaille les méthodes de comparaison de fonctions, les algorithmes itératifs et récursifs, ainsi que la programmation dynamique. Les résultats incluent des analyses de complexité et des exemples d'implémentation.

Transféré par

TIGER GAMER
Copyright
© All Rights Reserved
Nous prenons très au sérieux les droits relatifs au contenu. Si vous pensez qu’il s’agit de votre contenu, signalez une atteinte au droit d’auteur ici.
Formats disponibles
Téléchargez aux formats PDF, TXT ou lisez en ligne sur Scribd

Université d’El Oued

Département d’informatique

Algorithmique avancée et Complexité


Corrigé – Examen du 20 Janvier 2026

Exercice 1 – Notation asymptotique (3 points)


1) Comparaison des fonctions (2 pts)
Le terme dominant de 𝑓(𝑛) est 𝑛3 et celui 𝑔(𝑛) est 𝑛2 log 𝑛.
Comme 𝑛3 croît plus vite que 𝑛2 log 𝑛 , on a
𝑓(𝑛) ∈ Θ(𝑛3 ), g(n) ∈ Θ(𝑛2 log 𝑛), et
𝑓(𝑛) ∈ Ω(𝑔(𝑛)) et 𝑔(𝑛) ∈ O(𝑓(𝑛))

2) Affirmation vraie ou fausse (1 pt)


𝑛 log 𝑛 ∈ 𝑂(𝑛1.5 )
Vrai
Justification :
𝑛 log 𝑛 log 𝑛
lim = lim =0
𝑛→+∞ 𝑛1.5 𝑛→+∞ √𝑛

Donc 𝑛 log 𝑛 croît strictement moins vite que 𝑛1.5 , d’où : 𝑛 log 𝑛 ∈ 𝑂(𝑛1.5 ).

Exercice 2 – Calcul de 𝒙𝒏 : algorithmes et complexité (3 points)


1) Complexité temporelle (1 pt)
• Algorithme 1 (itératif)
→ Une boucle de 𝑛 itérations

𝑂(𝑛)
• Algorithme 2 (récursif linéaire)
→ Un appel récursif par décrément de 𝑛

𝑂(𝑛)
• Algorithme 3 (exponentiation rapide)
→ Division du problème par 2

𝑂(log 𝑛)
2) Équation de récurrence (1 pt)
Pour l’algorithme 3 :
𝑛
𝑇(𝑛) = 𝑇 ( ) + 𝑂(1)
2
avec condition initiale :
𝑇(0) = 𝑂(1)

3) Comparaison des algorithmes (1 pt)


• Algorithmes 1 et 2 : complexité linéaire 𝑂(𝑛)
• Algorithme 3 : complexité logarithmique 𝑂(log 𝑛)
Conclusion : L’algorithme 3 est le plus efficace pour de grandes valeurs de 𝑛.

Exercice 3 – Tri rapide (QuickSort) (6 points)


Tableau initial : 𝐴 = [15, 9, 17, 3, 12, 27, 6, 20]
Pivot = premier élément

1) Application pas à pas (2 pts)


Étape 1
Pivot = 15
Partition :
• Gauche : [9, 3, 12, 6]
• Droite : [17, 27, 20]

Étape 2 (Sous-tableau gauche [9, 3, 12, 6])


Pivot = 9
Partition :
• Gauche : [3, 6]
• Droite : [12]

Étape 3 (Sous-tableau [3, 6])


Pivot = 3
Partition :
• Gauche : []
• Droite : [6]

Étape 4 (Sous-tableau droit initial)


Pivot = 17
Partition :
• Gauche : []

2
• Droite : [27, 20]
Étape 5 (Sous-tableau [27, 20])
Pivot = 27
Partition :
• Gauche : [20]
• Droite : []

Résultat final : [3, 6, 9, 12, 15, 17, 20, 27]

2) Pseudo-code de QuickSort (2 pts)


QuickSort(A, low, high):
if low < high:
p ← Partition(A, low, high)
QuickSort(A, low, p - 1)
QuickSort(A, p + 1, high)

3) Complexité temporelle (2 pts)


• Meilleur cas (partition équilibrée) : 𝑂(𝑛 log 𝑛)

• Pire cas (tableau déjà trié, pivot extrême) : 𝑂(𝑛2 )

Exercice 4 – Programmation dynamique : Alignement de chaînes (8 points)


1) Sous-problème et principe (1 pt)
On définit :
𝑫𝑷[𝒊][𝒋] = coût minimal pour aligner 𝑿[𝟏. . 𝒊] et 𝒀[𝟏. . 𝒋]
La programmation dynamique est adaptée car :
• les sous-problèmes se recouvrent
• le problème possède une structure optimale

2) Relation de récurrence (2 pts)


𝐷𝑃[𝑖 − 1][𝑗] + 𝑔𝑎𝑝 (Suppression)
𝐷𝑃[𝑖][𝑗] = 𝑚𝑖𝑛 {𝐷𝑃[𝑖][𝑗 − 1] + 𝑔𝑎𝑝 (insertion)
𝐷𝑃[𝑖 − 1][𝑗 − 1] + 𝑐𝑜𝑠𝑡(𝑥𝑖 , 𝑦𝑗 ) (match/substitution)

Conditions initiales :
𝐷𝑃[0][𝑗] = 𝑗 ⋅ 𝑔𝑎𝑝, 𝐷𝑃[𝑖][0] = 𝑖 ⋅ 𝑔𝑎𝑝

3
3) Diagramme de programmation dynamique (2 pts)

i\j 0 G C A T G C U

0 0 1 2 3 4 5 6 7

G 1 0 1 2 3 4 5 6

A 2 1 1 1 2 3 4 5

T 3 2 2 2 1 2 3 4

T 4 3 3 3 2 2 3 4

A 5 4 4 3 3 3 3 4

C 6 5 4 4 4 4 3 4

A 7 6 5 4 5 5 4 4

→ Coût minimal d’alignement :

𝐷𝑃[7][7] + 4

4) Alignement optimal (1 pt)


Par backtracking à partir de 𝐷𝑃[𝑚][𝑛], on obtient un alignement optimal possible, par exemple
(4 substitution):
G A T T A C A
G C A T G C U

5) Implémentation Top-Down avec mémoïsation (2 pts)


Align(i, j):
if i = 0: return j
if j = 0: return i
if memo[i][j] existe: return memo[i][j]

cost ← 0 si X[i] = Y[j], sinon 1

memo[i][j] ← min(
Align(i-1, j-1) + cost,
Align(i-1, j) + 1,
Align(i, j-1) + 1
)

return memo[i][j]

Vous aimerez peut-être aussi