Mathématiques à l'usage des informaticiens
Cet ouvrage s'adresse en priorité aux étudiants en informatique qu'ils soient en DUT, second cycle ou écoles d'ingénieurs, mais également aux praticiens qui souhaitent retrouver les fondements de leur discipline.Chacun pourra y trouver, selon ses besoins, les outils mathématiques fondamentaux qu'il sera amené à utiliser tout au long de son cursus.Sont ainsi développés la plupart des [...]
[lire le résumé du livre]
Auteur : Thierry BRUYÈRE , Alain MOLLARD
Editeur : Ellipses
Date parution : 08/2003CB Google/Apple Pay, Chèque, Virement
Quel est le sujet du livre "Mathématiques à l'usage des informaticiens"
Cet ouvrage s'adresse en priorité aux étudiants en informatique qu'ils soient en DUT, second cycle ou écoles d'ingénieurs, mais également aux praticiens qui souhaitent retrouver les fondements de leur discipline.Chacun pourra y trouver, selon ses besoins, les outils mathématiques fondamentaux qu'il sera amené à utiliser tout au long de son cursus.Sont ainsi développés la plupart des concepts sur lesquels reposent les différents secteurs de l'informatique que sont les méthodes de spécifications formelles, les bases de données, les réseaux, les structures de données, l'architecture des machines...Ce cours expose en détail la théorie des ensembles et des relations, le calcul booléen, la logique des propositions et des prédicats, les langages et les automates, une initiation à la théorie des graphes, le calcul matriciel et l'algèbre linéaire, les polynômes et l'arithmétique ainsi que les codes correcteurs et des éléments de cryptographie.Les auteurs se sont attachés, lors du traitement de notions parfois difficiles, à les introduire de façon claire et originale sans sacrifier à la rigueur.Des annexes permettent au lecteur d'accéder rapidement à des résultats classiques qui ne font pas l'objet d'un développement dans le corps du texte.Thierry Brugère et Alain Mollard, agrégés de mathématiques, enseignent tous deux les mathématiques pour l'informatique, aussi bien en formation continue qu'en formation initiale, à l'université de Nantes.
Auteurs :Préfacier Thierry Brugère et Alain Mollard, agrégés de mathématiques, enseignent tous deux les mathématiques pour l'informatique, aussi bien en formation continue qu'en formation initiale, à l'université de Nantes.
En suivant ce lien, retrouvez tous les livres dans la spécialité Maths pour l'informatique.Sommaire et contenu du livre "Mathématiques à l'usage des informaticiens"
Table des matières1 Théorie naïve des ensembles, calcul booléen 17
1.1
Ensembles, éléments, appartenance 17
1.2
Inclusion,ensembledes parties............................... .. 19
1.2.1
Les patates 21
1.2.2
Ensemble des parties 22
1.3
Opérations usuelles dans P (E) 23
1.3.1
Intersection. . .................................. . . . . ... ... 23
1.3.2
Union ou réunion 23
1.3.3
Différence, différence symétrique, complémentaire 24
1.3.4
Application caractéristique 26
1.3.5
Partition 29
1.4
Produit cartésien 29
1.4.1
Couples, n-uplets 29
1.4.2
Produit cartésien 30
1.4.3
Propriétés 31
1.5
Cardinaux 31
1.6
Calcul booléen 33
2 Relations binaires 49
2.1
Relations binaires entre deux ensembles 49
2.1.1
Domaine, codomaine 50
2.1.2
Représentation d'une relation 51
2.1.3
Relation réciproque 53
2.1.4
Image, contre image d'une partie 54
2.1.5
Égalité de deux relations 54
2.1.6
Restriction, prolongement 55
2.1.7
Négation, inclusion, union, intersection 55
2.1.8
Composition 58
2.2
Fonctions, applications 62
2.2.1
Notion de famille d'éléments 63
2.2.2
Fonctions particulières 64
2.3
Relations n-aires 70
2.4
Relations binaires sur un ensemble 72
2.4.1
Représentations 72
2.4.2
Inclusion, union, intersection et négation 73
2.4.3
Composition 74
2.4.4
Propriétés particulières 79
2.5
Relations d'équivalence 83
2.6
Relations d'ordre 84
2.6.1
Ensembles ordonnés 85
2.7
Treillis 93
2.7.1
Treillis distributif 94
2.7.2
Treillis complémenté 94
2.8
Algèbre de Boole a~
3 Logique des propositions 99
3.1
Introduction 99
3.2
Généralités sur la logique des propositions 99
3.3
Le langage de la logique des propositions , 100
3.3.1
Levocabulaire........................................ .. 100
3.3.2
Les formules 101
3.3.3
Démonstration par induction 102
3.3.4
Sous-formule, arbre de décomposition d'une formule 103
3.4
La sémantique de la logique des propositions 104
3.4.1
Les connecteurs et leur interprétation , 104
3.4.2
Distribution des valeurs de vérité, tables de vérité 105
3.4.3
Calcul booléen, dans Z /2Z et distribution des valeurs
de vérité 107
3.4.4
Classement des formules, les tautaulogies 110
3.4.5
L'équivalence sémantique 112
3.4.6
Système complet de connecteurs 114
3.4.7
Formenormaleconjonctive,clauses.................... .. 116
3.4.8
Conséquence logique ou sémantique 118
3.5
Un système de preuve 122
3.5.1
La méthode de résolution 122
3.5.2
Brève initiation au langage Prolog 131
4 Logique des prédicats 137
4.1
Introduction 137
4.2
Le langage de la logique des prédicats 139
4.2.1
Le vocabulaire 139
4.2.2
Les termes 141
4.2.3
Les formules 143
4.2.4
Substitution dans une formule 147
4.3
La sémantique de la logique des prédicats 147
4.3.1
Réalisation d'un langage 148
4.3.2
Interprétation d'un terme 149
4.3.3
Satisfaction d'une formule 150
4.3.4
Formules universellement valides, équivalence
sémantique 152
4.3.5
Forme prénexe 154
4.3.6
Forme de Skolem 156
4.3.7
Conséquence sémantique 157
4.4
Méthode de résolution 158
5 Langages et automates 163
5.1
Langages 163
5.1.1
Alphabet 163
5.1.2
Chaîne de caractères, mots 163
5.1.3
Monoïde libre 164
5.1.4
Langages 166
5.1.5
Opérations sur les langages 167
5.2
Langages et expressions rationnels 168
5.2.1
Langages rationnels ou réguliers 169
5.2.2
Expressions rationnelles " . 169
5.3
Grammaires, systèmes formels 171
5.4
Automates à états finis 173
5.4.1
Calculs 176
5.4.2
Automates équivalents 177
5.4.3
Union 177
5.4.4
Produit cartésien 177
5.4.5
États accessibles, coaccessibles 178
5.4.6
Automates émondés 179
5.4.7
Automates complets 180
5.4.8
Automates déterministes 182
5.4.9
Complémentation 184
5.4.10Automates
normalisés 185
5.4.11Automates
avec transitions spontanées 188
5.5
LethéorèmedeKleene...................................... ..189
5.6
Retour aux grammaires 197
5.7
Opérations sur les automates 199
6 Graphes, arbres 201
6.1
Généralités 201
6.2
Graphes simples orientés 203
6.3
Graphes simples non orientés 220
6.4
Arbres, arborescences 221
6.4.1
Arbres 221
6.4.2
Arborescences .. .. .......... ... . . . . . •.. .. . . . ... . .. .. . ... 222
6.4.3
Arborescences ordonnées 224
6.4.4
Arbres binaires (ordonnés) 225
7 Polynômes 235
7.1
Définitions 235
7.2
Fonction polynôme 236
7.3
Opérations 237
7.4
Schéma de Homer 240
7.5
Division euclidienne 244
7.6
Décalage circulaire 246
7.7
Polynômes irrêcluctibles " 248
7.8
Zéros des polynômes 248
7.9
Anneau quotient 249
7.9.1
Idéaux de K [X] 249
7.9.2
Relation d'équivalence dans ]K [X] 249
7.9.3
L'anneau K [X] [M 250
7.10
Extension de corps 251
8 Calcul matriciel, systèmes linéaires, algèbre linéaire 255
8.1
Définition et notation 255
8.1.1
Opérations élémentaires sur les lignes ou colonnes " 256
8.1.2
Transposition 257
8.1.3
Matrices particulières 257
8.2
Opérations 259
8.2.1
Addition 259
8.2.2
Multiplication d'une matrice par un élément de ]K....• ... 259
8.2.3
Multiplication de deux matrices 260
8.3
Anneau des matrices carrées 263
8.3.1
Puissance d'une matrice carrée 263
8.3.2
Formule du binôme 263
8.3.3
Matrices carrées inversibles 263
8.4
Rang d'une matrice......................................... .. 265
8.4.1
Matrices ligne-équivalentes 265
8.4.2
L réduite échelonnée 266
8.4.3
Algorithme de Gauss-Jordan 268
8.5
Systèmes linéaires 272
8.5.1
Généralités 272
8.5.2
Systèmes équivalents et résolution 274
8.6
Les vecteurs de K" 279
8.6.1
Famille, combinaison linéaire 280
8.6.2
Sous espace vectoriel , 281
8.6.3
Familles libres, liées, génératrices 282
8.6.4
Bases 283
8.6.5
Matrice d'une famille 286
8.6.6
Changement de base 291
8.6.7
Produit scalaire canonique 293
8.6.8
Sous espaces orthogonaux 294
8.7
Applicationslinéaires...... .......... .... ...... .... ........... 296
8.7.1
Matrice d'une application linéaire 297
8.7.2
Image et contre image d'un sev, noyau 300
8.7.3
Applications linéaires et familles 301
8.8
Endomorphismesde ]Kn.........•..................•........ .. 304
9 Codes correcteurs d'erreurs 307
9.1
Généralités 307
9.1.1
Distance de Hamming 309
9.1.2
Distance minimale 310
9.1.3
Code t-correcteur 312
9.2
Codes linéaires 313
9.2.1
Décodage , première technique 314
9.2.2
Décodage, deuxième technique 318
9.2.3
Décodage, troisième technique 319
9.204
Codes cycliques 321
9.2.5
Codes de Hamming binaires 330
9.2.6
Code de Golay, de Reed-Solomon 332
10Arithmétique 333
10.1
Propriétés de N et de Z 333
10.2
Divisibilité dans Z 334
1O.2.1Propriétés
de la relation divise 334
1O.2.2Division
euclidienne 335
10.3
PPCM 338
1O.3.1Ppcm
de deux entiers 338
10.3.2Ppcm
de plusieurs entiers 339
10.4
PGCD 339
lOA.1Propriétés
immédiates 341
lOA.2Algorithme
d'Euclide 342
lOA.3Algorithme
d'Euclide étendu 345
lOAACalcul du ppcm de deux entiers 351
10.5
Nombres premiers 352
10.6
Congruences 355
10.6.1Propriétés
356
10.6.2Congruences
et opérations 358
10.6.3Codes
de contrôle 360
1O.6AExponentiation
modulaire 361
10.7
Calculs modulo n 362
10.8
Fonction indicatrice d'Euler 370
10.9
Problèmes difficiles . . . . .. .. . . . . .. .. . .. .. 375
Il Cryptographie civile 377
11.1
Terminologie ................................................. 379
11.2
Difficulté calculatoire 381
Il.3
Le code Vernam 383
1104 Crytosystèmes à clefsecrètes .... .......... .......... ..... ..... 384
11.4.1Le
DES 384
11.4.2Skip
Jack 384
11A.3Rinjdael
384
11.5
Cryptosystèmes à clefs publiques 385
11.5.1Le
R.S.A 385
11.5.2EI
Gamal 387
11.6
Signatures numériques 388
11.7
Stockage de mots de passe 389
11.8
Authentification , 390
A Raisonnement, récursion et induction 391
A.1
Le raisonnement 391
A.2
Principe de démonstration par récurrence 393
A.3
Induction. 00 0 00 0.. 0 0 394
A.4
Système formel. 0. 0.. 0.. 0.. 00.. 0.. 0. 0 0. 0 0. 00. 00. 00. 00 396
B Les logarithmes 397
B.1
La fonction logarithme népérien .. 0 00000 0 0.. 00. 0397
B.2
Les fonctions logarithmes et exponentielles de base a 0. .. 397
B.2.1
La fonction logarithme décimal ou de base 10 .. 0. 00.. 0. o. 398
Bo202 La fonction logarithme de base 2 00 0 00. 0. 00. 000398
B.2.3
Quelques utilisations 0000. 00. 0 0 00 398
C Dénombrement 401
Col Cardinaux 0 0 0 0. 00 00 .00. 0.0.. 00000.0.0 401
C.2
p-listes. 0.. 00 000 0.. 00. 0. 00 0. 00. 0. 00 0. o. 403
C.3
p-listes d'éléments distincts o.. 0 o 0. . 0. . 0o. o 404
C.4
Combinaisons, nombre de parties 0. 00 0.. 0.. 0.. 0 405
C.5
Combinaisons avec répétitions 00.. 0 0o. 407
C.6
Partages 0. 00 0 0. 000000. 0000 00 0 o. 408
Co7 Nombre de surjections 0 0 0 408
C.8
Nombre de partitions 0. 000 0. 0.. 0410
C.9
Permutations, dérangements o 0o.o.. o 0o. 412
D Modélisation du hasard 415
D.1
Suites aléatoires .. 0. 0 0. 0.0 0 00 415
D.2
Simulation de variables aléatoires .0 0 0. 0 0 416
E Structures 417
E.1
Loi de composition interne (lei) 00. . 0 0.. 417
E.1.1
Propriétés et vocabulaire 00 0.. 0 0. 0 417
E.2
Groupes . 00.. 0. 0 0 00 000. 0. 0.. 0. 00. 00. 0418
Eo2.1
Soustraction 0 0.0 0000.0 0.0.. 00.. 0418
E.2.2
Sous groupe 0 0 0o' 419
E.2.3
Produit de groupes '" 0.. 0 0 00 0.. 0.. 0 419
Eo2.4
Goupes finis 0o o 00000 0000 419
Eo3 Anneaux
0.000 0 0 000 0000 0.419
E.301
Éléments neutres d'un anneau 0 0 o. 420
E.3.2
Diviseurs de zéro 0 0 0. 0 00 420
E.3.3
Formule du binôme de Newton .. 0.00.0.0 0 0 420
Eo3.4
Produit d'anneaux 0 0.. 0 421
E.3.5
Idéaux .. 0. 0. 00000. 0.. 00 0 00 0 00 421
E.4
Corps 0000 0 000 0 0.0 0 0.00 421
Eo5 Espace vectoriel 0 0 421
Eo5.1
Espace vectoriel fondamental .. 00 000. 0. 00 00.. 0421
E.6
Homomorphismes. 0... 0.0.... o.... 0 000.0 .. 00 0.00. 0.0. o' 422
E.7
Le corps fini à p éléments, p premier o' o.. 0o 422
E.7.1
Relation =n 422
E.7.2
Propriétés 423
E.7.3
Opérations 423
E.7.4
Pratique 424
E.7.5
Cas de F2 424