Introduction aux mathématiques discrètes
Coll. IRIS

Auteurs :

Directeur de Collection : PUECH Nicolas

Langue : Français

46,00 €

En stock : expédition en 24h !

Ajouter au panierAjouter au panier
Date de parution :
Ouvrage 476 p. · 16x24 cm · Broché
ISBN : 9782287200106 EAN : 9782287200106
Springer
Cet ouvrage propose une initiation simple et complète aux fondements des mathématiques discrètes. Il encourage une approche active de la matière, fondée sur la résolution de nombreux exercices, et le style utilisé pour sa rédaction ne peut que stimuler l'intérêt du lecteur pour les mathématiquesL'exposé aborde des thèmes aussi variés que la combinatoire, la théorie des graphes, les méthodes probabilistes élémentaires, les plans projectifs finis, les applications combinatoires de l'algèbre linéaire et de l'analyse ainsi que les fonctions génératrices. Les lecteurs apprécieront les quelques deux cents figures et quatre cents exercices qui illustrent le propos. Ce livre s'adresse aux étudiants des premier et deuxième cycles universitaires (informatique et mathématiques). Il comporte des rappels sur les notions de mathématiques générales utilisées dans l'exposé, ne supposant ainsi pratiquement aucun prérequis.

1 Introduction et notions fondamentales

1.1 Quelques problèmes

1.2 Nombres et ensembles

1.3 Récurrence mathématique et autres types de démonstration

1.4 Fonctions

1.5 Relations

1.6 Relations d’équivalence

1.7 Ensembles ordonnés

2 Dénombrement combinatoire

2.1 Fonctions et sous-ensembles

2.2 Permutations et factorielles

2.3 Coefficients binomiaux

2.4 Estimations : une introduction

2.5 Estimations : la fonction factorielle

2.6 Estimations : les coefficients binomiaux

2.7 Le principe d’inclusion-exclusion

2.8 La responsable du vestiaire

3 Graphes : une introduction

3.1 Notion de graphe ; isomorphisme

3.2 Sous-graphes, composantes et matrice d’adjacence

3.3 Score d’un graphe

3.4 Graphes eulériens

3.5 Un algorithme qui permet de trouver un cycle eulérien

3.6 Graphes eulériens orientés

3.7 2-connexité

4 Les arbres

4.1 Définition et caractérisations des arbres

4.2 Isomorphismes d’arbres

4.3 Arbres couvrants d’un graphe

4.4 Problème de l’arbre couvrant de poids minimal

4.5 Algorithmes de Jarnik et de Boruvka

5 Dessiner des graphes dans le plan

5.1 Dessiner dans le plan et sur d’autres surfaces

5.2 Cycles dans les graphes planaires

5.3 La formule d’Euler

5.4 Coloriages de cartes : le problème des quatre couleurs

6 Double décompte

6.1 Arguments de parité

6.2 Théorème de Sperner concernant les familles indépendantes

6.3 Un résultat en théorie extrémale des graphes

7 Le nombre d’arbres couvrants

7.1 Le résultat

7.2 Une preuve via le score

7.3 Une preuve avec des vertébrés

7.4 Une preuve qui utilise le code de Prüfer

7.5 Ce qui est peut-être la preuve la plus simple

7.6 Une preuve qui utilise les déterminants

8 Plans projectifs finis

8.1 Définitions et propriétés fondamentales

8.2 Existence de plans projectifs finis

8.3 Carrés latins orthogonaux

8.4 Applications combinatoires

9 Probabilité et preuves probabilistes

9.1 Preuves par le dénombrement

9.2 Espaces probabilisés finis

9.3 Variables aléatoires et espérance

9.4 Quelques applications

10 Fonctions génératrices

10.1 Applications combinatoires des polynômes

10.2 Intervention des séries entières

10.3 Nombres de Fibonacci et nombre d’or

10.4 Arbres binaires

10.5 Sur le lancement de dés

10.6 Marche aléatoire

10.7 Partitions d’entiers

11 Applications de l’algèbre linéaire

11.1 Blocs

11.2 Inégalité de Fisher

11.3 Recouvrement par des graphes bipartis complets

11.4 Espace cyclique d’un graphe

11.5 Circulations et coupures : retour sur l’espace cyclique

11.6 Vérification probabiliste

Annexe : Prérequis d’algèbre

Bibliographie

Indications pour certains exercices

Index

Les deux auteurs sont professeurs à l'université Charles de Prague, respectivement en informatique et en mathématiques.
Traduit de l’anglais par Delphine Hachez
Retrouvez tous les ouvrages de la collection IRIS.