Remerciez-le!

Remerciez @Admin pour avoir partagé cet document gratuitement, de la manière la plus simple, en partageant sur les réseaux sociaux.

MÉTHODES MATHÉMATIQUES POUR L’INFORMATIQUE Cours et exercices corrigés Jacques

MÉTHODES MATHÉMATIQUES POUR L’INFORMATIQUE Cours et exercices corrigés Jacques Vélu Professeur honoraire au Conservatoire national des arts et métiers 5e édition © Dunod, Paris, 2013 ISBN 978-2-10-059452-8 Table des matières AVANT-PROPOS VII CORRIGÉS VIDÉO IX CHAPITRE 1 • LA NOTION D’ENSEMBLE 1 1.1 Ensembles 1 1.2 Éléments 3 1.3 Sur les façons de déﬁnir un ensemble 4 1.4 Fonctions et applications 6 1.5 Diverses propriétés des applications 9 1.6 Exercices sur le chapitre 1 12 CHAPITRE 2 • CONSTRUCTIONS D’ENSEMBLES 17 2.1 Produit d’ensembles 17 2.2 Produit d’une famille d’ensembles 20 2.3 Puissances d’un ensemble 21 2.4 Réunion, intersection, somme disjointe 22 2.5 Exercices sur le chapitre 2 24 CHAPITRE 3 • CARDINAL D’UN ENSEMBLE 27 3.1 Ensembles ﬁnis 27 3.2 Ensembles dénombrables 30 3.3 Cardinaux 31 3.4 Ensembles inﬁnis 35 3.5 Exercices sur le chapitre 3 36 CHAPITRE 4 • ANALYSE COMBINATOIRE 39 4.1 Le principe des choix successifs 39 4.2 Arrangements 42 4.3 Permutations 43 4.4 Combinaisons 45 4.5 Formule du binôme 48 4.6 Exercices sur le chapitre 4 51 IV Table des matières CHAPITRE 5 • RELATIONS 55 5.1 Déﬁnitions 55 5.2 Propriétés des relations binaires 58 5.3 Relations d’équivalence 60 5.4 Exercices sur le chapitre 5 63 CHAPITRE 6 • ENSEMBLES ORDONNÉS 67 6.1 Relations d’ordre 67 6.2 Diagramme de Hasse 69 6.3 Éléments particuliers 71 6.4 Exercices sur le chapitre 6 73 CHAPITRE 7 • CALCUL BOOLÉEN 77 7.1 Treillis 77 7.2 Algèbres de Boole 81 7.3 Le théorème de Stone 87 7.4 Exercices sur le chapitre 7 90 CHAPITRE 8 • PARTIES D’UN ENSEMBLE 93 8.1 Le treillis ℘(E) 93 8.2 Fonctions caractéristiques 97 8.3 Le principe d’inclusion-exclusion 100 8.4 Exercices sur le chapitre 8 102 CHAPITRE 9 • PROBABILITÉS COMBINATOIRES 105 9.1 Épreuves et événements 105 9.2 Fréquences et probabilités 108 9.3 Lois de probabilité 110 9.4 Probabilité conditionnelle et indépendance 115 9.5 Essais répétés 117 9.6 Exercices sur le chapitre 9 119 CHAPITRE 10 • FONCTIONS BOOLÉENNES 125 10.1 Introduction 125 10.2 Fonctions booléennes de n variables 129 10.3 La forme canonique disjonctive 132 10.4 Fonctions et formules 137 10.5 Systèmes d’équations booléennes 140 10.6 Exercices sur le chapitre 10 146 Table des matières V CHAPITRE 11 • SIMPLIFICATION DES FORMULES 149 11.1 Le problème de la simpliﬁcation 149 11.2 Formules polynomiales 150 11.3 La méthode de Karnaugh 154 11.4 La méthode des consensus 164 11.5 Exercices sur le chapitre 11 168 CHAPITRE 12 • CALCUL PROPOSITIONNEL 173 12.1 Propositions 173 12.2 Connexions 175 12.3 Formes propositionnelles 179 12.4 Exercices sur le chapitre 12 186 CHAPITRE 13 • ARITHMÉTIQUE 191 13.1 Division euclidienne 191 13.2 Nombres premiers 193 13.3 PGCD et PPCM 196 13.4 Exercices sur le chapitre 13 203 CHAPITRE 14 • CONGRUENCES 207 14.1 Équation de Bézout 207 14.2 Entiers modulo n 212 14.3 Le groupe (Z/nZ)× 217 14.4 Exercices sur le chapitre 14 221 CHAPITRE 15 • CODES DÉTECTEURS CODES CORRECTEURS 225 15.1 Pourquoi coder ? 225 15.2 Distance de Hamming 226 15.3 Erreurs de transmission 228 15.4 Codage par blocs 231 15.5 Correction et détection 234 15.6 Exercices sur le chapitre 15 238 CHAPITRE 16 • CODAGES LINÉAIRES 241 16.1 Codes linéaires 241 16.2 Représentations matricielles 244 16.3 Syndromes 245 16.4 Construction de codes correcteurs 249 16.5 Codes cycliques 251 16.6 Codes polynomiaux 255 16.7 Exercices sur le chapitre 16 256 c ⃝Dunod – Toute reproduction non autorisée est un délit VI Table des matières CHAPITRE 17 • GRAPHES 261 17.1 Graphes orientés, graphes non orientés 261 17.2 Quelques problèmes classiques 265 17.3 Degrés, chemins, circuits, cycles 269 17.4 Représentations matricielles 273 17.5 Exercices sur le chapitre 17 278 CHAPITRE 18 • ARBRES ENRACINÉS 281 18.1 Arbres 281 18.2 Racine 284 18.3 Arbres binaires 286 18.4 Codes de Huffman 290 18.5 Exercices sur le chapitre 18 294 CHAPITRE 19 • AUTOMATES FINIS 299 19.1 Familiarité avec les automates 299 19.2 Automates 302 19.3 Langages 305 19.4 Langage d’un automate ﬁni 311 19.5 Langages réguliers 320 19.6 Exercices sur le chapitre 19 323 CHAPITRE 20 • CONSTRUCTIONS D’AUTOMATES 327 20.1 Simpliﬁcation d’un automate 327 20.2 Automates ﬁnis non déterministes 337 20.3 Déterminisation 340 20.4 Le théorème de Kleene 345 20.5 Exercices sur le chapitre 20 349 ANNEXE A • CALCUL MATRICIEL 353 A.1 Matrices 353 A.2 Opérations sur les matrices 355 A.3 Matrices booléennes 358 A.4 Quelques applications du calcul matriciel 362 A.5 Exercices sur l’annexe C 366 ANNEXE B • SOLUTIONS DES EXERCICES 369 INDEX 413 Avant-propos Depuis sa première version, des dizaines de milliers de personnes ont utilisé Méthodes mathématiques pour l’informatique ; le livre est présenté ici dans sa nouvelle édition, une fois de plus revue, mise à jour et corrigée. Primitivement destiné à accompagner les deux enseignements de Mathématiques pour l’Informatique du Conservatoire National des Arts et Métiers, ce cours a élargi son audience au ﬁl des années et maintenant il est utilisé autant hors du CNAM que dans le CNAM. Ses lecteurs sont de deux sortes : des débutants ou des curieux, dont c’est le premier et dernier contact avec les Mathématiques discrètes, et des auditeurs qui entreprennent un cycle d’étude plus ou moins long. Citons par exemple les étudiants de DUT, de BTS, de licence STIC (Sciences et techniques de l’information et de la communication) mention informatique et mention mathématiques appliquées, des certiﬁcats inscrits au RNCP (registre national de la certiﬁcation professionnelle). Conçu pour un public protéiforme, il vise cependant un unique objectif : apprendre des méthodes en faisant comprendre les idées qui les ont engendrées. Il y a plus de quinze ans, quand le premier cours a été bâti, on pouvait justement se demander s’il existait des mathématiques de l’informatique, et quelles étaient leurs limites. Fallait-il en faire un enseignement séparé ou, comme cela se faisait jusque là, glisser quelques recettes au gré des cours d’informatique ? Le choix de l’époque, dont la justesse ne s’est pas démentie, a été de remplacer les recettes par des méthodes qui reposent sur des théorèmes de mathématiques ; même si les plus difﬁciles sont plus montrés que démontrés, les théorèmes forment l’ossature du livre. L’enseignement qui repose sur ce livre, est constitué, au CNAM, de deux cours d’une durée de 60 heures chacun (6 ECTS), répartis sur deux semestres. C’est beaucoup et c’est peu ; beaucoup quand l’objectif est avant tout de devenir informaticien, souvent uniquement praticien, mais c’est peu car le domaine est si vaste . . . Le livre a été bâti pour qu’on y retrouve deux types de sujets, avec deux niveaux de dif- ﬁculté. D’abord ceux qui sont inévitables et qu’on enseigne généralement au premier semestre : l’algèbre de Boole, le calcul propositionnel, les dénombrements, etc. Puis d’autres, qui demandant davantage d’efforts, et qui constituent le cours du deuxième semestre. Ceux-là ont pour thème sous-jacent les applications du calcul matriciel : on rencontre des matrices dans les codes, dans les graphes, dans les automates, partout, mais je n’en dis pas plus aﬁn de laisser au lecteur le soin d’en faire lui-même la décou- verte. Leur importance interdit de traiter tout ces sujets en si peu de temps ; il faudra VIII Avant-propos donc en choisir quelques-uns et ne donner que les grandes lignes des autres, le livre venant alors en complément du cours. Je me suis toujours efforcé de commencer par présenter les concepts de la façon la plus intuitive possible avant de procéder à leur mise en forme abstraite ; c’est pourquoi les sujets débutent souvent par une introduction très concrète qui pose les problèmes. Ensuite viennent les théorèmes qui conduisent aux méthodes pratiques permettant de résoudre mécaniquement ces problèmes. Les chapitres ﬁnissent toujours par de nombreux exercices. Beaucoup sont faciles et seront résolus dès qu’on aura trouvé le paragraphe auquel ils se rapportent, mais d’autres, nettement plus difﬁciles, se cachent dans la masse ; c’est donc un exercice supplémentaire de les débusquer. Certains exercices doivent être considérés comme un moment de détente ; souvent écrits en italique, ils adoptent un style qu’on n’a pas l’ha- bitude de trouver dans les livres de Mathématiques ; mais là aussi je laisse au lecteur le plaisir de les découvrir. À la ﬁn du livre, on trouvera les solutions des exercices. Pour certains, le résultat seulement est donné, mais, pour beaucoup d’autres, des indications détaillées sont fournies. Tout au long du livre j’ai posé des jalons dans l’espoir d’exciter votre curiosité. Si je vous ai donné envie de lire un livre de Mathématiques sans y être obligé mon but est atteint. Des parties ont été récrites spécialement pour cette quatrième édition, en tenant compte des questions posées par les élèves. Autre nouveauté, pour ceux qui ont accès à inter- net et qui peuvent lire l’anglais, quelques URL, qui m’ont été demandées, permettront de rechercher un complément d’information ; voici, tout de suite, les trois premières : – pour chercher des renseignements sur l’histoire des mathématiques et les biogra- phies de mathématiciens http ://www-history.mcs.st-and.ac.uk/ – pour parcourir une gigantesque encyclopédie des mathématiques qui donne l’actua- lité des grands résultats http ://mathworld.wolfram.com/ – si vous uploads/S4/ methodes-mathematiques-pour-l-x27-informatique.pdf