Upload
cain-perin
View
132
Download
2
Embed Size (px)
Citation preview
IN302 – Chapitre 1
Notions de base, connexité
Rappels sur la complexité
Rappel sur la complexité
• Algorithme A
• Données caractérisées par une taille n
• On note CA(n) le coût d’exécution de l’algorithme A sur un jeu de données de taille n
Rappel sur la complexité
n
t
CA(n)
Rappel sur la complexité
• Considérons une fonction f(n), par exemple : f(n)=n, f(n)=n2 …
• On dit que l’algorithme A possède une complexité en O(f(n)) si :
la fonction CA(n) est dominée asymptotiquement par k.f(n)
c.a.d : il existe deux constantes k et n0 telles que pour tout n > n0, on ait k.f(n) > CA(n)
Rappel sur la complexité
n
t
CA(n)
k.f(n)
n0
Rappel sur la complexité
• Propriété : si P(n) est un polynome en n de degré d, alors
A est en O(P(n))
équivaut à
A est en O(nd)
Algorithmes : successeurs d’une partie de E
Algo 1
• Données (E,), X E
• Résultat Y E
0/ Y = 1/ Pour tout (x,y) 2/ Si x X
3/ Y = Y {y}
Algo 1
1
3
4
5
2
6
7
8
= {(1,4), (3,4), (1,3), (3,5), ...}
Algo 1
1
3
4
5
2
6
7
8
= {(1,4), (3,4), (1,3), (3,5), ...}X = {3, 5, 6}
Algo 1
1
3
4
5
2
6
7
8
= {(1,4), (3,4), (1,3), (3,5), ...}X = {3, 5, 6}Y = {}
Algo 1
1
3
4
5
2
6
7
8
= {(1,4), (3,4), (1,3), (3,5), ...}X = {3, 5, 6}Y = {}
Algo 1
1
3
4
5
2
6
7
8
= {(1,4), (3,4), (1,3), (3,5), ...}X = {3, 5, 6}Y = {}
Algo 1
1
3
4
5
2
6
7
8
= {(1,4), (3,4), (1,3), (3,5), ...}X = {3, 5, 6}Y = {4}
Algo 1
1
3
4
5
2
6
7
8
= {(1,4), (3,4), (1,3), (3,5), ...}X = {3, 5, 6}Y = {4}
Algo 1
1
3
4
5
2
6
7
8
= {(1,4), (3,4), (1,3), (3,5), ...}X = {3, 5, 6}Y = {4}
Algo 1
1
3
4
5
2
6
7
8
= {(1,4), (3,4), (1,3), (3,5), ...}X = {3, 5, 6}Y = {4, 5}
Algo 1
1
3
4
5
2
6
7
8
= {(1,4), (3,4), (1,3), (3,5), ...}X = {3, 5, 6}Y = {4, 5, 7}
Algo 2
• Données (E,), X E
• Résultat Y E
0/ Y = 1/ Pour tout x X
2/ Pour tout y (x)
3/ Y = Y {y}
Algo 2
1
3
4
5
2
6
7
8
(1) = {2,3,4} ; (2) = {3,5} ; (3) = {4,5} …X = {3, 5, 6}Y = {}
Algo 2
1
3
4
5
2
6
7
8
(3) = {4,5} ; (5) = {4,7} ; (6) = {5} …X = {3, 5, 6}Y = {}
Algo 2
1
3
4
5
2
6
7
8
(3) = {4,5} ; (5) = {4,7} ; (6) = {5} …X = {3, 5, 6}Y = {4,5}
Algo 2
1
3
4
5
2
6
7
8
(3) = {4,5} ; (5) = {4,7} ; (6) = {5} …X = {3, 5, 6}Y = {4,5}
Algo 2
1
3
4
5
2
6
7
8
(3) = {4,5} ; (5) = {4,7} ; (6) = {5} …X = {3, 5, 6}Y = {4,5,7}
Algo 2
1
3
4
5
2
6
7
8
(3) = {4,5} ; (5) = {4,7} ; (6) = {5} …X = {3, 5, 6}Y = {4,5,7}
Connexité, chemins
Small world
Reconnaissance de caractères
Logiciel de reconnaissance
optique de caractères
(OCR)
Graphes d’adjacence
4 - adjacence 8 - adjacence
Composantes fortement connexes