Mathématiques discrètes et informatique

L'informatique a pour vocation de traiter de l'information discrétisée en créant des outils spécifiques. Ce cours est consacré aux fondements de certains de ces outils formels. Il se situe donc aux confins de l'informatique et des mathématiques, la première suscitant les problématiques et les secondes les méthodes de traitement appropriées. L'ouvrage est organisé en trois parties. La première introduit les concepts de base (ensemble, relation, fonction) autour d'une notion centrale : l'induction. Les structures algébriques font ensuite l'objet d'une étude détaillée. La deuxième partie est consacrée à la notion de complexité de calcul. Après une approche formelle du concept d'algorithme, on aborde l'estimation pratique du temps d'exécution d'un programme, puis l'étude des classes de complexité. Enfin, la dernière partie traite d'un mode de modélisation particulièrement pertinente des situations concrètes : les graphes. L'exposé est illustré par de nombreux exemples et figures. Sauf exception, les énoncés sont chacun assortis d'une démonstration complète. En outre, chaque chapitre est suivi d'une série d'exercices, mis au point et appliqués lors de l'enseignement de ce cours, en deuxième cycle d'informatique et de mathématiques appliquées.