Découvrez notre Chaîne YouTube "Devenir Ingénieur"

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

Mathématique-appliquée-cours-30

Télécharger le fichier PDF: Mathématiques discrètes

Le blog contient des publicités, elles permettent de financer l'hébergement et maintenir le blog en fonctionnement. Vous pouvez utiliser adblock pour une lecture sans publicités.

You have successfully subscribed to the newsletter

There was an error while trying to send your request. Please try again.

FPGA | Arduino | Matlab | Cours will use the information you provide on this form to be in touch with you and to provide updates and marketing.