Dans ce
cours, l'accent a été mis sur l'écriture effective
de programmes implémentant les algorithmes étudiés.
Programmer un
algorithme et l'exécuter sur machine permet
de confronter la théorie à la réalité, de détecter et de
corriger les erreurs élémentaires ou les insuffisances d'un
raisonnement ainsi que d'affermir la compréhension du
fonctionnement de l'algorithme. Le langage de
programmation
servant de support à ce cours est le langage
CAML, dont les
éléments nécessaires à l'exposé sont introduits au fur et à
mesure.
Chacun des onze chapitres est suivi d'exercices
corrigés,
en tout plus de 150 sujets. L'ensemble est complété par des
problèmes et des
travaux pratiques également
corrigés.
L'ouvrage recouvre la totalité du programme officiel de
l'option informatique des prépas scientifiques et
conviendra aussi aux étudiants des premiers cycles
universitaires scientifiques.
Sommaire
- Cours et
Exercices
- Méthodes de programmation
- Structure de liste
- Listes triées
- Évaluation d'une formule
- Logique booléenne
- Complexité des algorithmes
- Arbres
- Arbres binaires de recherche
- Manipulation d'expressions formelles
- Langages réguliers
- Automates finis
Problèmes (6 sujets corrigés)
- Tri par distribution
- Interpolation de Lagrange et multiplication rapide
- Plus longue sous-séquence commune
- Arbres de priorité équilibrés
- Compilation d'une expression
- Recherche d'une chaîne de caractères dans un
texte
Travaux pratiques (5 sujets corrigés) :
- Chemins dans Z2
- Files d'attente et suite de Hamming
- Recherche de contradictions par la méthode des
consensus
- Modélisation d'un tableur
- Analyse syntaxique
- Bibliographie