37
IN302 – Chapitre 1 Notions de base, connexité

IN302 – Chapitre 1 Notions de base, connexité. Rappels sur la complexité

Embed Size (px)

Citation preview

Page 1: IN302 – Chapitre 1 Notions de base, connexité. Rappels sur la complexité

IN302 – Chapitre 1

Notions de base, connexité

Page 2: IN302 – Chapitre 1 Notions de base, connexité. Rappels sur la complexité

Rappels sur la complexité

Page 3: 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

Page 4: IN302 – Chapitre 1 Notions de base, connexité. Rappels sur la complexité

Rappel sur la complexité

n

t

CA(n)

Page 5: IN302 – Chapitre 1 Notions de base, connexité. Rappels sur la complexité

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)

Page 6: IN302 – Chapitre 1 Notions de base, connexité. Rappels sur la complexité

Rappel sur la complexité

n

t

CA(n)

k.f(n)

n0

Page 7: IN302 – Chapitre 1 Notions de base, connexité. Rappels sur la complexité

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)

Page 8: IN302 – Chapitre 1 Notions de base, connexité. Rappels sur la complexité

Algorithmes : successeurs d’une partie de E

Page 9: IN302 – Chapitre 1 Notions de base, connexité. Rappels sur la complexité

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}

Page 10: IN302 – Chapitre 1 Notions de base, connexité. Rappels sur la complexité

Algo 1

1

3

4

5

2

6

7

8

= {(1,4), (3,4), (1,3), (3,5), ...}

Page 11: IN302 – Chapitre 1 Notions de base, connexité. Rappels sur la complexité

Algo 1

1

3

4

5

2

6

7

8

= {(1,4), (3,4), (1,3), (3,5), ...}X = {3, 5, 6}

Page 12: IN302 – Chapitre 1 Notions de base, connexité. Rappels sur la complexité

Algo 1

1

3

4

5

2

6

7

8

= {(1,4), (3,4), (1,3), (3,5), ...}X = {3, 5, 6}Y = {}

Page 13: IN302 – Chapitre 1 Notions de base, connexité. Rappels sur la complexité

Algo 1

1

3

4

5

2

6

7

8

= {(1,4), (3,4), (1,3), (3,5), ...}X = {3, 5, 6}Y = {}

Page 14: IN302 – Chapitre 1 Notions de base, connexité. Rappels sur la complexité

Algo 1

1

3

4

5

2

6

7

8

= {(1,4), (3,4), (1,3), (3,5), ...}X = {3, 5, 6}Y = {}

Page 15: IN302 – Chapitre 1 Notions de base, connexité. Rappels sur la complexité

Algo 1

1

3

4

5

2

6

7

8

= {(1,4), (3,4), (1,3), (3,5), ...}X = {3, 5, 6}Y = {4}

Page 16: IN302 – Chapitre 1 Notions de base, connexité. Rappels sur la complexité

Algo 1

1

3

4

5

2

6

7

8

= {(1,4), (3,4), (1,3), (3,5), ...}X = {3, 5, 6}Y = {4}

Page 17: IN302 – Chapitre 1 Notions de base, connexité. Rappels sur la complexité

Algo 1

1

3

4

5

2

6

7

8

= {(1,4), (3,4), (1,3), (3,5), ...}X = {3, 5, 6}Y = {4}

Page 18: IN302 – Chapitre 1 Notions de base, connexité. Rappels sur la complexité

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}

Page 19: IN302 – Chapitre 1 Notions de base, connexité. Rappels sur la complexité

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}

Page 20: IN302 – Chapitre 1 Notions de base, connexité. Rappels sur la complexité

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}

Page 21: IN302 – Chapitre 1 Notions de base, connexité. Rappels sur la complexité

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 = {}

Page 22: IN302 – Chapitre 1 Notions de base, connexité. Rappels sur la complexité

Algo 2

1

3

4

5

2

6

7

8

(3) = {4,5} ; (5) = {4,7} ; (6) = {5} …X = {3, 5, 6}Y = {}

Page 23: IN302 – Chapitre 1 Notions de base, connexité. Rappels sur la complexité

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}

Page 24: IN302 – Chapitre 1 Notions de base, connexité. Rappels sur la complexité

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}

Page 25: IN302 – Chapitre 1 Notions de base, connexité. Rappels sur la complexité

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}

Page 26: IN302 – Chapitre 1 Notions de base, connexité. Rappels sur la complexité

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}

Page 27: IN302 – Chapitre 1 Notions de base, connexité. Rappels sur la complexité

Connexité, chemins

Page 28: IN302 – Chapitre 1 Notions de base, connexité. Rappels sur la complexité

Small world

Page 29: IN302 – Chapitre 1 Notions de base, connexité. Rappels sur la complexité

Reconnaissance de caractères

Logiciel de reconnaissance

optique de caractères

(OCR)

Page 30: IN302 – Chapitre 1 Notions de base, connexité. Rappels sur la complexité
Page 31: IN302 – Chapitre 1 Notions de base, connexité. Rappels sur la complexité

Graphes d’adjacence

4 - adjacence 8 - adjacence

Page 32: IN302 – Chapitre 1 Notions de base, connexité. Rappels sur la complexité
Page 33: IN302 – Chapitre 1 Notions de base, connexité. Rappels sur la complexité
Page 34: IN302 – Chapitre 1 Notions de base, connexité. Rappels sur la complexité
Page 35: IN302 – Chapitre 1 Notions de base, connexité. Rappels sur la complexité
Page 36: IN302 – Chapitre 1 Notions de base, connexité. Rappels sur la complexité
Page 37: IN302 – Chapitre 1 Notions de base, connexité. Rappels sur la complexité

Composantes fortement connexes