[PDF] [PDF] Algorithmique et programmation à destination des étudiants dIMSD

View - Download [PDF] Algorithmique et programmation à destination des étudiants dIMSD

Previous PDF

Next PDF

Algorithmique et programmation à destination des étudiants d"IMSD

Université de Lorraine, FST

Cours rédigé par Jean Lieber Dernière version : 1 eraoût 2019 Page du cours :http://homepages.loria.fr/JLieber/cours/algo-prog-M2-IMSD/

Remarques sur ce document

Il rassemble des notes de cours utiles pour l(")(es )interv enant(s)et pour les étudiants mais ne constitue

pas un polycopié complet. Il ne se substitue donc pas à des prises régulières de notes durant les cours. En

particulier, le programme des examens ne se limite pas au contenu de ce polycopié.

Il document contient probablement des erreurs (d"orthographe, de grammaire ou d"autres natures). Merci

de le signaler à son auteur (par exemple, à la fin d"un cours).

Sommaire

1 Introduction2

1.1 Prérequis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

3

1.2 Un survol de quelques types . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

3

1.3 Plan du cours . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

4

1.4 Quelques références . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

4

2 Les arbres5

2.1 Terminologie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

5

2.2 Les arbres binaires . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

6

2.2.1 Type abstrait . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

6

2.2.2 Quelques opérations non primitives sur les arbres binaires . . . . . . . . . . . . . . . . .

6

2.2.3 Parcours d"un arbre binaire . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

7

2.2.4 Trois applications . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

9

2.2.4.1 Les arbres binaires de recherche . . . . . . . . . . . . . . . . . . . . . . . . . .

9

2.2.4.2 La représentation et la manipulation d"expressions . . . . . . . . . . . . . . . .

10

2.2.4.3 Les arbres de décision . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

10

2.2.5 Deux implantations des arbres binaires . . . . . . . . . . . . . . . . . . . . . . . . . . .

11

2.2.5.1 Implantation chaînée . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

11

2.2.5.2 Implantation par un tableau . . . . . . . . . . . . . . . . . . . . . . . . . . . .

13

2.3 Les arbres quelconques et les forêts . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

14

2.3.1 Des arbres aux forêts . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

14

2.3.2 Le type abstraitforêt. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .14

2.4 L"exploration d"espaces d"états . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

15

2.4.1 Problèmes de recherche dans un espace d"états . . . . . . . . . . . . . . . . . . . . . . .

15

2.4.2 Résoudre un problème discret par le parcours d"un arbre de recherche . . . . . . . . . . .

16

2.4.2.1 Parcours en profondeur d"un espace d"états . . . . . . . . . . . . . . . . . . . .

17

2.4.2.2 Parcours en largeur d"un espace d"états . . . . . . . . . . . . . . . . . . . . . .

17

2.4.2.3 Complexité . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

18

3 Les graphes18

3.1 Terminologie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

18

3.1.1 Notions générales relatives aux graphes . . . . . . . . . . . . . . . . . . . . . . . . . . .

18

3.1.2 Notions relatives aux graphes étiquetés . . . . . . . . . . . . . . . . . . . . . . . . . . .

20

3.1.3 Quelques classes de graphes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

20

3.1.3.1 Les graphes non orientés . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

20

3.1.3.2 Les graphes complets et les cliques . . . . . . . . . . . . . . . . . . . . . . . .

21

3.1.3.3 Les graphes planaires . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .21

3.1.3.4 Autres classes de graphes . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

22

3.1.4 Hypergraphes, graphes multiples et graphes emboîtés . . . . . . . . . . . . . . . . . . . .

23

3.2 Représentations des graphes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

24

3.2.1 Représentation par listes d"adjacence . . . . . . . . . . . . . . . . . . . . . . . . . . . .

24

3.2.2 Représentation par des matrices d"adjacence . . . . . . . . . . . . . . . . . . . . . . . .

24

3.2.3 Autres représentations de graphes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

26

3.3 Représentationspardes graphes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .26

3.4 Quelques problèmes algorithmiques liés aux graphes . . . . . . . . . . . . . . . . . . . . . . . .

27

3.4.1 Test de connexité . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

27

3.4.2 Recherche de chemins optimaux dans un graphe . . . . . . . . . . . . . . . . . . . . . .

28

3.4.3 Isomorphisme de graphes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

30

3.4.3.1 Algorithme général . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

30

3.4.3.2 Amélioration du temps de calcul . . . . . . . . . . . . . . . . . . . . . . . . .

32

3.4.3.3 Cas des graphes étiquetés . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

33

3.4.3.4 Problèmes algorithmiques apparentés . . . . . . . . . . . . . . . . . . . . . . .

33

3.4.4 Trouver une chaîne eulérienne ou un cycle eulérien . . . . . . . . . . . . . . . . . . . . .

34

3.4.5 Trouver une chaîne hamiltonienne ou un un cycle hamiltonien . . . . . . . . . . . . . . .

35

3.4.6 Problèmes de coloration de graphes . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

36

3.4.7 Chaîne de caractères décrivant un graphe de façon unique à l"isomorphisme près . . . . .

36

4 Conclusion39

A Algorithme et Python : aide-mémoire 39

A.1 L"encodage des caractères en Python . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

39

A.2 Les commentaires . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

39

A.3 Les variables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

39

A.4 Les constantes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

40

A.5 Les opérations de base sur les booléens, les entiers et les réels . . . . . . . . . . . . . . . . . . .

40

A.6 La génération pseudo-aléatoire de nombres . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

41

A.7 Les entrées/sorties . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

41

A.8 Les conditionnelles . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

41

A.9 Les boucles . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

42

A.10 Les fonctions et les procédures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

42

A.11 Les enregistrements . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

43
A.11.1 Manipulation directe des enregistrements . . . . . . . . . . . . . . . . . . . . . . . . . . 43

A.11.2 Manipulation des enregistrements par fonctions de lecture et d"écriture (préférable) . . . .

43

A.12 Les tableaux . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

44

A.12.1 Les tableaux à une entrée . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

44

A.12.2 Les tableaux à plusieurs entrées . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

44

1 Introduction

L"objectif de ce cours est de donner des notions, méthodes et outils d"algorithmique et programmation à des

étudiants ayant déjà des bases en algorithmique comme en langage Python (voir section 1.1). Ce cours porte

principalement sur les arbres et les graphes. 2

1.1 Prérequis

Les prérequis de ce cours sont :

Les notions de type, de v ariable,d"af fectation,d"initialisation ;

Les types sui vants: booléen,entier naturel,entier,réel(et leur représentation par des flottants),

les types enregistrements, les types tableaux, les types listes 1; Les conditionnelles a vecdes v aleurs,les conditionnelles a vecdes instructions ; Les structures de boucles (" pour»," tantque »,notamment) ;

La récursi vité.

Quelques notions sur la comple xitédes algorithmes et des problèmes.

1.2 Un survol de quelques types

en partant du plus particulier au plus général. La plupart de ces types sont donnés par une définition sur la base de

constructeurs.

Les entiers naturels.L"entier naturel4peut être représenté par le graphe suivant :. On peut de façon générale définir récursivement un entier naturel

comme étant( soitzéro soitsucc(x)oùxest un entier naturel:4 =succ(succ(succ(succ(zéro)))).

Les listes.On se donne un type nommétypélt. Soita,b,c,detede typetypélt. La liste(a b c d e)peut être

représentée par le graphe suivant :abcde. On peut donc voir la notion liste dont les éléments sont de typetypéltcomme étant( soitl_vide(la liste vide) soitcons(x;L)oùxest untypéltetL, une liste: (a b c d e) =cons(a;cons(b;cons(c;cons(d;cons(e;l_vide()))))).

Remarque 1Il ne faut pas confondre les types tableaux et les types listes : l"accès aux éléments se fait pour les

premiers de façon directe, alors que pour les seconds, l"accès est séquentiel. Le typelistde Python est en fait un

intermédiaire entre les types tableaux et listes.

Les arbres binaires.On peut voir les arbres binaires comme des généralisations des listes : dans sa représen-

tation graphique, au lieu d"avoir1arc sortant pour chaque noeud (sauf le dernier) on peut en avoir0,1ou2.

Par exemple,

on a l"arbre binaire suivant :ab ce fd qu"on dessine généralement de façon verticale et sans les flèches :a bc efd. On peut

de façon générale définir récursivement un arbre binaire dont les éléments sont de typetypéltcomme étant1. Pour les entiers naturels, les réels, les enregistrements et les listes, on peut consulter les notes de cours suivantes :http:

//homepages.loria.fr/JLieber/cours/ap2. 3 soita_vide(l"arbre vide) soitcons(r;G;D)oùrest untypéltetGetDsont des arbres binaires(rest laracinede l"arbre,Gest son fils gaucheetD, sonfils droit). Ainsi, l"arbre binaire ci-dessus peut s"écrire : cons(a; cons(b; cons(d;a_vide;a_vide); a_vide); cons(c; cons(e;a_vide;a_vide); cons(f;a_vide;a_vide)))

On notera qu"il y a une information qui est sous-entendue : l"ordre des fils d"un arbre compte en général (le gauche

puis le droit). On pourrait rendre compte de cette information en ajoutant des arcs indiquant cette précédence (en

pointillés dans ce dessin) :a bc efd.

Les arbres.La notion d"arbre généralise la notion d"arbre binaire en enlevant la contrainte sur le nombre maxi-

mum d"arcs sortants pour chaque noeud. On peut aussi donner comme dans les exemples ci-dessus une définition

récursive des arbres.

Les graphes.Un graphe est la donné d"un ensemble desommetset d"un ensemble d"arcs entre les sommets.

Voici un exemple de graphe étiqueté :ab

cde . C"est une notion qui

généralise les précédentes, mais dont la manipulation algorithmique est souvent plus difficile (et souvent d"une

plus grande complexité en terme de temps de calculs).

1.3 Plan du cours

Le cours comprend deux grands chapitres : un chapitre sur les arbres (chapitre 2) et un chapitre sur les graphes

(chapitre 3). Ce document contient en annexe un aide-mémoire sur les notations algorithmiques et Python sur les

prérequis du cours.

1.4 Quelques références

L"ouvrage "Conception d"algorithmes : Principes et150exercices corrigés» de Marc Guyomard, Patrick Bosc

et Laurent Miclet (édité chez Dunod) couvre une grande variété de problèmes algorithmiques selon une approche

pédagogique.

L""Introduction à l"algorithmique» de Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest et Clifford

Stein (édité chez Dunod) est, malgré son nom, très complet et peut être considéré comme un ouvrage de référence.

Parmi mes cours en lien (direct ou non) à l"algorithmique, notons les suivants :

Le cours d"AP2 déjà cité en tête de chapitre ( http://homepages.loria.fr/JLieber/cours/ap2);

4

-La première partie du cours d"introduction à l"intelligence artificielle (L3 informatique) contient des cours

sur les parcours d"espaces d"états (http://homepages.loria.fr/JLieber/cours/iia);

Le cours de logique (L3 informatique) contient la description d"algorithmes utilisés pour f airedes infé-

quotesdbs_dbs16.pdfusesText_22

[PDF] parcours en largeur graphe java

[PDF] conflit de puissance définition

[PDF] parcours lecture acces pas cher

[PDF] parcours lecture pdf

[PDF] parcours lecture le petit chaperon rouge

[PDF] parcours lecture acces avis

[PDF] parcours lecture occasion

[PDF] coexistence pacifique cours

[PDF] archives militaire en ligne

[PDF] livret militaire en ligne

[PDF] la coexistence pacifique de 1953 ? 1962 pdf

[PDF] cornière catnic

[PDF] corniere galva pour brique

[PDF] corniere pour linteau brique

[PDF] cornière support briques