• Aide
  • Eurêkoi Eurêkoi

Livre

Eléments de mathématiques discrètes

Résumé

Indissociables du monde des ordinateurs et devenues indispensables à tout processus de modélisation informatique, les mathématiques discrètes fédèrent diverses disciplines comme l'algèbre, la logique et la théorie des langages. Organisé en trois parties autonomes : fondements, graphes et algèbres. Exposé sous la forme de deux niveaux de lecture, il est complété de nombreux exercices et problèmes.


  • Éditeur(s)
  • Date
    • 2002
  • Langues
    • Français
  • Description matérielle
    • XIV-378 p. ; 24 x 16 cm
  • Collections
  • Sujet(s)
  • ISBN
    • 2-88074-479-2
  • Indice
    • 518 Calcul et analyse numériques
  • Quatrième de couverture
    • Indissociables du monde des ordinateurs et indispensables à tout processus de modélisation informatique, les mathématiques discrètes fédèrent diverses disciplines telles que l'algèbre, la logique et la théorie des langages, et de façon générale les mathématiques n'utilisant pas la notion de continuité. L'auteur de cet ouvrage introduit cet univers mathématique de manière simple, claire et didactique. Organisé en trois parties autonomes (Fondements, Graphes et Algèbre) avec deux niveaux de lecture et complété de nombreux exercices et problèmes, l'ouvrage s'adresse plus particulièrement aux étudiants en informatique, aux informaticiens et aux modélisateurs.


  • Tables des matières
      • Eléments de mathématiques discrètes

      • Louis Frécon

      • Presses Polytechniques et Universitaires Romandes

      • Département d'informatiqueV
      • SommaireVII
      • Première partie Fondements1
      • Chapitre 0 Mémento de logique3
      • 0.1 Logique des propositions3
      • 0.2 Logique des prédicats11
      • 0.3 Exercices15
      • 0.4 Problèmes17
      • 0.5 Piste de réflexion18
      • 0.6 Lectures18
      • Chapitre 1 Ensembles & éléments21
      • 1.1 Présentation21
      • 1.2 Inclusions23
      • 1.3 Parties d'un ensemble25
      • 1.4 Union26
      • 1.5 Intersection27
      • 1.6 Différence ensembliste28
      • 1.7 Couvertures29
      • 1.8 Différence symétrique31
      • 1.9 Partitions32
      • 1.10 Paires & produits cartésiens34
      • 1.11 Exercices35
      • 1.12 Problèmes37
      • 1.13 Lectures40
      • Chapitre 2 Relations binaires41
      • 2.1 Vue en extension41
      • 2.2 Vue en compréhension44
      • 2.3 Relation inverse45
      • 2.4 Union, intersection, finesse46
      • 2.5 Composition46
      • 2.6 Exercices47
      • 2.7 Problèmes48
      • 2.8 Lectures48
      • Chapitre 3 Fonctions51
      • 3.1 Relations binaires régulières51
      • 3.2 Fonctions51
      • 3.3 Surjection53
      • 3.4 Image & inverse54
      • 3.5 Injection & bijection54
      • 3.6 Synoptiques56
      • 3.7 Composition de fonctions57
      • 3.8 Ensembles dénombrables et finis58
      • 3.9 Relations n-aires59
      • 3.10 Fonctions généralisées61
      • 3.11 Exercices63
      • 3.12 Problèmes64
      • 3.13 Lectures65
      • Chapitre 4 Relations binaires internes67
      • 4.1 Présentation67
      • 4.2 Propriétés des relations binaires internes68
      • 4.3 Restriction72
      • 4.4 Equivalence72
      • 4.5 Ordres75
      • 4.6 Préordre79
      • 4.7 Récapitulatifs84
      • 4.8 Exercices85
      • 4.9 Problèmes87
      • 4.10 Thèmes de réflexion92
      • 4.11 Lectures94
      • Chapitre 5 Fonctions, calculabilité, récurrence95
      • 5.1 Calculabilite, decidabilité95
      • 5.2 Calculabilité et récursivité96
      • 5.3 Récursivités convergente, divergente, stationnaire101
      • 5.4 Ensembles récursifs et récursivement énumérables103
      • 5.5 Aux sources de l'arithmétique et de l'algèbre104
      • 5.6 Exercices106
      • 5.7 Problèmes107
      • 5.8 Pistes de réflexion108
      • 5.9 Lectures109
      • Chapitre 6 Notion de complexité111
      • 6.1 Premier exemple111
      • 6.2 Règles d'estimation de la complexité112
      • 6.3 Préordre de complexité115
      • 6.4 Classes de complexité115
      • 6.5 Optimisation du calcul d'une fonction117
      • 6.6 Représentations d'une table creuse121
      • 6.7 Exercices123
      • 6.8 Problèmes124
      • 6.9 Lectures125
      • Deuxième partie Graphes127
      • Chapitre 7 Des points et des flèches129
      • 7.1 Présentation129
      • 7.2 Degrés & demi-degrés129
      • 7.3 Prédécesseurs, successeurs, adjacents130
      • 7.4 Sommets initiaux, terminaux, isolés130
      • 7.5 Sous-graphe130
      • 7.6 Graphe partiel131
      • 7.7 Graphe complet, cliques131
      • 7.8 Représentations131
      • 7.9 Propriétés des relations binaires et graphes associés133
      • 7.10 Propriété faible / propriété forte135
      • 7.11 Graphe valué135
      • 7.12 Exercices136
      • 7.13 Problèmes136
      • 7.14 Thèmes de réflexion137
      • 7.15 Lectures137
      • Chapitre 8 Chemins & circuits139
      • 8.1 Les chemins139
      • 8.2 Circuits et boucles dans un graphe141
      • 8.3 Chemins élémentaires dans un graphe141
      • 8.4 Recherche de chemins dans un graphe143
      • 8.5 Méthodes matricielles145
      • 8.6 Méthode locale 1 : recherche par niveaux152
      • 8.7 Méthode locale 2 : méthode du meilleur d'abord155
      • 8.8 Méthode locale 3 : recherche en profondeur158
      • 8.9 Problèmes hamiltoniens161
      • 8.10 Problèmes eulériens162
      • 8.11 Exercices164
      • 8.12 Problèmes165
      • 8.13 Thèmes de réflexion169
      • 8.14 Lectures169
      • Chapitre 9 Fermetures transitives171
      • 9.1 Fermeture transitive et descendance stricte171
      • 9.2 Fermeture réflexo-transitive et descendance large171
      • 9.3 Interprétation des relations quelconques172
      • 9.4 Accessibilité dans les systèmes à états174
      • 9.5 Exercices179
      • 9.6 Problèmes179
      • 9.7 Lectures181
      • Chapitre 10 Arbres & connexité183
      • 10.1 Chaînes & cycles183
      • 10.2 Graphe (fortement) connexe184
      • 10.3 Composante connexe d'un graphe184
      • 10.4 Composantes fortement connexes185
      • 10.5 Centres, rayon, diamètre d'un graphe185
      • 10.6 Arbres, forêts, hiérarchies, arborescences187
      • 10.7 Arbre couvrant188
      • 10.8 Arbre couvrant minimal189
      • 10.9 Points, ensembles d'articulation190
      • 10.10 Isthme191
      • 10.11 k-Connexité et robustesse structurelle191
      • 10.12 Multi-graphes192
      • 10.13 Exercices196
      • 10.14 Problèmes197
      • 10.15 Pistes de réflexion198
      • 10.16 Vocabulaire198
      • 10.17 Lectures200
      • Chapitre 11 Graphes multipartis201
      • 11.1 Présentation201
      • 11.2 Tests de multipartisme202
      • 11.3 Jeux & fonctions de Grundy204
      • 11.4 Coloriage de graphes207
      • 11.5 Graphes bipartis212
      • 11.6 Graphes et hypergraphes214
      • 11.7 Exercices218
      • 11.8 Problèmes219
      • 11.9 Pistes de réflexion220
      • 11.10 Lectures220
      • Troisième partie Algèbres221
      • Chapitre 12 Opérateurs & algèbres223
      • 12.1 Opérateurs & signatures223
      • 12.2 Syntaxe des expressions224
      • 12.3 Sémantique formelle des expressions225
      • 12.4 Algèbres225
      • 12.5 Propriétés des opérateurs227
      • 12.6 Eléments remarquables pour un opérateur228
      • 12.7 Déparenthésages231
      • 12.8 Propriétés inter-opérateurs236
      • 12.9 Morphismes237
      • 12.10 Formes normales & canoniques239
      • 12.11 Exercices240
      • 12.12 Problèmes241
      • 12.13 Pistes de réflexion242
      • 12.14 Lectures243
      • Chapitre 13 Monoïdes & groupes245
      • 13.1 Présentation245
      • 13.2 Semi-Groupe248
      • 13.3 Groupe249
      • 13.4 Monoïde finiment engendré251
      • 13.5 Langages formels254
      • 13.6 Grammaires254
      • 13.7 Exercices256
      • 13.8 Problèmes258
      • 13.9 Pistes de réflexion260
      • 13.10 Lectures261
      • Chapitre 14 Dioïdes263
      • 14.1 Présentation263
      • 14.2 Semi-anneau264
      • 14.3 Anneau264
      • 14.4 Corps265
      • 14.5 Graphe valué265
      • 14.6 Calculs matriciels267
      • 14.7 Thèse centrale267
      • 14.8 Taille illimitée267
      • 14.9 Taille limitée269
      • 14.10 Exemples270
      • 14.11 Graphes multivalués273
      • 14.12 Exercices274
      • 14.13 Problèmes277
      • 14.14 Pistes de réflexion277
      • 14.15 Lectures279
      • 14.16 Famille des dioïdes279
      • Chapitre 15 Algèbre de Boole281
      • 15.1 Intérêt281
      • 15.2 Algèbre de boole élémentaire282
      • 15.3 Modélisation booléenne de technologies283
      • 15.4 Fonctions booléennes285
      • 15.5 Géométrie booléenne286
      • 15.6 Bases d'une fonction289
      • 15.7 Des sommes de monômes aux produits de clauses300
      • 15.8 Approches dichotomiques305
      • 15.9 Equations booléennes308
      • 15.10 Anneau de Boole309
      • 15.11 Equivalences majeures312
      • 15.12 Exercices313
      • 15.13 Problèmes313
      • 15.14 Piste de réflexion314
      • 15.15 Lectures314
      • Chapitre 16 Algèbre de Kleene & automates à états finis317
      • 16.1 Notion d'automate à états finis317
      • 16.2 Grammaires de Kleene321
      • 16.3 Algèbre de Kleene322
      • 16.4 Propriété centrale325
      • 16.5 Des expressions régulières aux graphes de transition328
      • 16.6 Synoptique333
      • 16.7 Exercices333
      • 16.8 Problèmes335
      • 16.9 Pistes de réflexion336
      • 16.10 Lectures337
      • Annexe Indications sur les exercices & problèmes339
      • Chapitre 0 : Memento de logique339
      • Chapitre 1 : Ensembles & éléments341
      • Chapitre 2 : Relations binaires344
      • Chapitre 3 : Fonctions345
      • Chapitre 4 : Relations binaires internes348
      • Chapitre 5 : Fonctions, calculabilité, récurrence352
      • Chapitre 6 : Notion de complexité354
      • Chapitre 7 : Des points et des flèches355
      • Chapitre 8 : Chemins & circuits356
      • Chapitre 9 : Fermetures transitives357
      • Chapitre 10 : Arbres & connexité359
      • Chapitre 11 : Graphes multipartis359
      • Chapitre 12 : Opérateurs et algèbres361
      • Chapitre 13 : Monoïdes361
      • Chapitre 14 : Dioïdes363
      • Chapitre 15 : Algèbre de Boole364
      • Chapitre 16 : Algèbres de Kleene & automates à états finis364
      • Index367

  • Origine de la notice:
    • Electre
  • Disponible - 518 FRE

    Niveau 2 - Sciences