Algorithmique et programmation 10.00 / 20

Plan :

1 Structures de donnees 1 1 Notion de pointeur . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 2 Passage par adresse . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 3 Listes cha^nees . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 3.1 Parcours de liste . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 3.2 Insertion en t^ete de liste . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 4 Arbres binaires . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 4.1 Parcours d'un arbre . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 4.2 Construction d'un arbre . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 4.3 Arbres binaires de recherche . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 5 Graphes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9 5.1 Matrices d'adjacences . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 5.2 Listes d'adjacences . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 5.3 Insertion d'une ar^ete . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 5.4 Recherche de plus courts chemins . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 2 Methodes algorithmiques 15 1 Diviser pour regner . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15 1.1 Marquage d'une regle . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15 1.2 Tri par fusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16 2 Programmation dynamique . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16 3 Notions de complexite en temps . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19 3.1 Tri par insertion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20 3.2 Complexite d'un probleme . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21 3.3 Tri rapide . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22 3 Programmation en C 25 1 Developper un logiciel . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25 2 Pointeurs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26 2.1 Tableaux et structures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26 2.2 Passage des parametres . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28 3 Caracteres et cha^nes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28 3.1 Caracteres . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30 3.2 Cha^nes de caracteres . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30 4 Ligne de commande . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32 5 Entrees/sorties en C . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33 5.1 Ouverture d'un chier . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33 5.2 Entrees/sorties formatees . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34 6 Utiliser un debogueur . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35 6.1 Informations de deboguage . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35 6.2 Points d'arr^et . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36 6.3 Manipulation lors du deboguage . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36 7 Allocation dynamique en C . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37 7.1 Description du probleme . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37 7.2 Allouer de la memoire . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37 7.3 Desallouer de la memoire . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38 8 Listes en C . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40 A Visualisation 45 1 Simple Direct Media Layer . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45 1.1 Initialiser la SDL . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45 1.2 Synthese additive . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45 1.3 Double Buering . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46 1.4 Surfaces SDL . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46 1.5 Dessiner dans une surface . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47 1.6 Gestion des evenements . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47 1.7 Programme complet . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47 1.8 Primitives graphiques . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47 1.9 SDL et Dev-C++ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50 1.10 Simple Direct Media Layer et OpenGL . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50 2 OpenGL . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50 2.1 Principe . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50 2.2 Ouverture d'une fen^etre et initialisation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52 2.3 Primitives . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52 2.4 Projections . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53 2.5 Appliquer des transformations aux objets . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54 2.6 D'autres primitives . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56 2.7 Elimination des parties cachees . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57 2.8 Animation automatique . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57 2.9 Un peu de lumiere . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59 2.10 OpenGL, Glut et Dev-C++ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59 2.11 Graphapp et OpenGL ensemble... . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59 3 Champ tournant . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60 4 Champ cree par une spire . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60 5 Champ tournant . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61 6 Comment programmer le tout ? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62 7 Calcul des integrales . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63 8 Visualisation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63