Titre: Mathématiques discrètes
Auteurs: Samuel Fiorini
Ecole: Néant
Résumé: Voir le document
Extrait du sommaire:
1 Comptage élémentaire 4
1.1 Principes de base 4
1.1.1 Rappels sur les fonctions 4
1.1.2 Cardinalité 5
1.2 Factorielles 6
1.3 Coefficients binomiaux : définition et premières identités 7
1.4 Coefficients binomiaux : formule du binˆome, D de Pascal 9
1.5 Coefficients binomiaux : applications 10
1.6 Preuves bijectives 11
1.7 Coefficients multinomiaux : définition et formule du multinˆome 15
1.8 Coefficients multinomiaux : application 16
1.9 Exercices 19
2 Relations de récurrence 22
2.1 Exemples récurrents 22
2.1.1 Nombres de régions délimitées par n droites dans le plan 22
2.1.2 Pavages d’un rectangle 2 n 24
2.1.3 Tri fusion 26
2.2 Récurrences linéaires 27
2.2.1 Récurrences linéaires du premier ordre 27
2.2.2 Récurrences linéaires homogènes à coefficients constants 27
2.2.3 Récurrences linéaires à coefficients constants générales 31
2.3 Récurrences diviser-pour-régner (“divide-and-conquer”) 32
2.3.1 Recherche binaire 32
2.3.2 Retour au tri fusion 32
2.3.3 Rappels sur les comportements asymptotiques 34
2.3.4 Récurrences diviser-pour-régner générales 34
2.4 Application : produit matriciel selon Strassen 36
2.5 Application : recherche d’une plus proche paire 38
2.6 Autres types de récurrences 40
2.6.1 Calcul d’une racine carrée 40
2.6.2 Fractions continuées 42
2.7 Exercices 43
3 Fonctions génératrices 46
3.1 Exemples 46
3.1.1 Les nombres de Catalan 46
3.1.2 Retour sur les nombres de Fibonacci 49
3.2 Fonctions génératrices ordinaires : théorie de base 50
3.3 Fonctions génératrices ordinaires : récurrences linéaires 53
3.4 Fonctions génératrices ordinaires : applications 54
3.4.1 Nombre moyen de comparaisons de Quicksort 54
3.4.2 Un problème de monnaie 57
3.5 Fonctions génératrices exponentielles : théorie de base 58
3.6 Fonctions génératrices exponentielles : application 59
3.7 Exercices 61
4 Comportements asymptotiques 63
4.1 Nombres harmoniques et constante d’Euler 63
4.2 Factorielles et formule de Stirling 65
4.3 Formule d’Euler-Mc Laurin 68
4.4 La méthode analytique : nombres de Bell ordonnés 72
4.4.1 FGE des nombres de Bell ordonnés par la méthode symbolique 72
4.4.2 Formule asymptotique pour les nombres de Bell ordonnés 73
4.5 Exercices 76
5 Introduction à la théorie de l’information 77
5.1 Entropie 77
5.2 Application : compression de données 78
5.2.1 Théorème de Shannon 78
5.2.2 Inégalité de Kraft 79
5.3 Arbres de Huffman 82
Télécharger le fichier PDF: Mathématiques discrètes