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

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