Ebook Algorithmique
Ebook Algorithmique gratuit
Extrait du cours :
Cet ouvrage présente un cours d’algorithmique dispensé successivement au lycée Carnot de Dijon puis au lycée Poincaré de Nancy en classes préparatoires aux grandes écoles, option informatique. Il s’adresse donc en premier lieu aux étudiants de ces classes préparatoires, mais aussi aux étudiants du premier cycle de l’Université suivant un enseignement d’informatique. Enfin, il peut constituer une base de départ pour un enseignant de l’option informatique voulant construire son propre cours.
Le plan du livre est celui adopté pour l’exposé des cours donnés „a Dijon et „a Nancy, les chapitres 1 „a 5 recouvrent le programme de première année (méthodes de programmation, structure de liste, logique booléenne) et les chapitres 6 „a 11 celui de deuxième année (complexité des algorithmes, structure d’arbre, manipulation d’expressions formelles, langage et automates). A la suite de ces onze chapitres, j’ai inclus quelques sujets de problèmes et quelques sujets de travaux pratiques sélectionnés pour leur originalité parmi les sujets qui ont été donnés aux étudiants de Dijon ou de Nancy (à l’exception du sujet de TP intitulé@@Recherche de contradictions par la méthode des consensus AA qui est inspiré d’un exercice similaire présenté dans le cours de Luc Albert, et qui a été donné aux étudiants du lycée Champollion de Grenoble). Tous les sujets proposés sont accompagnés d’un corrigé plus ou moins détaillé. Ces corrigés sont regroupés en fin d’ouvrage de façon à éviter au lecteur la tentation de s’y reporter trop vite : un corrigé n’est en aucune façon la solution unique et incontournable au problème posé, mais plutôt une réponse possible que le lecteur comparera avec sa propre réponse.
Ebook Algorithmique gratuit
Table des matières :
Préface 6
Cours et exercices
Chapitre 1 Méthodes de programmation . 9
1-1 Description d’un algorithme . 9
1-2 Itération 11
1-3 Récursivité . 14
1-4 Diviser pour régner 17
1-5 Exercices . 20
Chapitre 2 Structure de liste 24
2-1 Définitions . 24
2-2 Représentation en mémoire 25
2-3 Parcours d’une liste 27
2-4 Recherche d’un élément dans une liste . 28
2-5 Insertion et suppression 29
2-6 Exercices . 32
Chapitre 3 Listes triées 34
3-1 Insertion dans une liste triée 34
3-2 Recherche dans une liste triée . 35
3-3 Fusion de listes triées 37
3-4 Tri d’une liste 39
3-5 Tri „a bulles . 41
3-6 Tri par fusion 42
3-7 Tri rapide 46
3-8 Exercices . 50
Chapitre 4 évaluation d’une formule . 53
4-1 Structure de pile . 53
4-2 Représentation linéaire d’une formule . 55
4-3 évaluation d’une formule postfixe 56
4-4 Exercices . 58
Chapitre 5 Logique booléenne . 60
5-1 Propositions 60
5-2 Circuits logiques 63
5-3 Synthèse des fonctions booléennes . 65
5-4 Manipulation des formules logiques 69
5-5 Exercices . 73
Chapitre 6 Complexité des algorithmes 76
6-1 Généralités . 76
6-2 équation de récurrence T(n)= aT(n−1)+f(n) . 79
6-3 Récurrence diviser pour régner 82
6-4 Exercices . 84
Chapitre 7 Arbres 87
7-1 Définitions . 87
7-2 Représentation en mémoire 90
7-3 Parcours d’un arbre 94
7-4 Dénombrements sur les arbres binaires 99
7-5 Exercices . 104
Chapitre 8 Arbres binaires de recherche . 109
8-1 Recherche dans un arbre binaire . 109
8-2 Insertion . 111
8-3 Suppression 113
8-4 Exercices . 114
Chapitre 9 Manipulation d’expressions formelles 115
9-1 Introduction 115
9-2 Représentation des formules . 116
9-3 Dérivation 120
9-4 Simplification . 124
9-5 Exercices . 129
Chapitre 10 Langages réguliers 130
10-1 Définitions . 132
10-2 Opérations sur les langages 133
10-3 Appartenance d’un mot à un langage régulier . 135
10-4 Exercices . 136
Chapitre 11 Automates finis . 138
11-1 Définitions . 138
11-2 Simulation d’un automate fini . 141
11-3 Déterminisation d’un automate 146
11-4 Le théorème deKleene 147
11-5 Stabilité et algorithmes de décision 151
11-6 Langages non réguliers . 152
11-7 Exercices . 153
Travaux pratiques
Chemins dansZ2 171
Files d’attente et suite de Hamming . 174
Recherche de contradictions par la méthode des consensus 176
Modélisation d’un tableur . 182
Analyse syntaxique 184
Solutions des exercices
Chapitre 1 Méthodes de programmation . 190
Chapitre 2 Structure de liste . 199
Chapitre 3 Listes triées 205
Chapitre 4 évaluation d’une formule . 213
Chapitre 5 Logique booléenne . 216
Chapitre 6 Complexité des algorithmes 227
Chapitre 7 Arbres . 230
Chapitre 8 Arbres binaires de recherche 238
Chapitre 9 Manipulation d’expressions formelles . 240
Chapitre 10 Langages réguliers 247
Chapitre 11 Automates finis 250
Solutions des problèmes
Tri par distribution 260
Interpolation de Lagrange et multiplication rapide 261
Plus longue sous-séquence commune . 266
Arbres de priorité équilibrés . 272
Compilation d’une expression 274
Recherche d’une chaîne de caractères dans un texte . 276
Solutions des travaux pratiques
Chemins dansZ2 282
Files d’attente et suite de Hamming . 283
Recherche de contradictions par la méthode des consensus 287
Modélisation d’un tableur . 289
Analyse syntaxique 290
Annexes
Bibliographie . 295
Aide mémoire de caml . 296
Index 300
Ebook Algorithmique gratuit
