Forums d'entraide informatique - Astuces - Conseils

Je vous propose cet excellent ouvrage en téléchargement traitant des Mathématiques dans les algorithmes

Il est téléchargeble ici : http://www.parisdepannage.fr/dossiers/Mathematiques.pdf

voici la table des matières

Table des matieres
1 Calcul matriciel 7
1.1 Notions de matrice . . . . . . . . . . . . . . . . . . . . . . . . . . 7
1.2 Cas particuliers . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
1.3 Operations classiques . . . . . . . . . . . . . . . . . . . . . . . . . 7
1.3.1 Addition . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
1.3.2 Multiplication . . . . . . . . . . . . . . . . . . . . . . . . . 8
1.3.3 Matrices carrees . . . . . . . . . . . . . . . . . . . . . . . 8
1.3.4 Matrice orthogonale . . . . . . . . . . . . . . . . . . . . . 9
1.4 Operations booleennes . . . . . . . . . . . . . . . . . . . . . . . . 9
1.5 Inverse d’une matrice carr´ee . . . . . . . . . . . . . . . . . . . . . 9
1.5.1 d´efinition . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
1.5.2 Calcul de l’inverse d’une matrice carree . . . . . . . . . . 9
1.5.3 Exemple . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
1.6 Applications . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
1.6.1 Matrice de transition . . . . . . . . . . . . . . . . . . . . . 10
1.6.2 transitions de duree minimale . . . . . . . . . . . . . . . . 12
2 Elements de la theorie des graphes 13
2.1 Domaine d’application . . . . . . . . . . . . . . . . . . . . . . . . 13
2.2 Notion de graphe . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
2.2.1 Les types . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
2.2.2 Exemples . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
2.2.3 Representation . . . . . . . . . . . . . . . . . . . . . . . . 13
2.3 Quelques concepts . . . . . . . . . . . . . . . . . . . . . . . . . . 14
2.4 Sous graphe et graphe partiel d’un graphe donn´e . . . . . . . . . 14
2.4.1 Sous graphe . . . . . . . . . . . . . . . . . . . . . . . . . . 14
2.4.2 Graphe partiel . . . . . . . . . . . . . . . . . . . . . . . . 15
2.5 Matrice d’adjacence . . . . . . . . . . . . . . . . . . . . . . . . . 15
2.6 Arbres et arborescence . . . . . . . . . . . . . . . . . . . . . . . . 18
2.6.1 Arbre . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
2.6.2 Arbrorescence . . . . . . . . . . . . . . . . . . . . . . . . . 18
2.7 Parcours de graphes . . . . . . . . . . . . . . . . . . . . . . . . . 19
2.7.1 Pile et file . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
2.7.2 Arborescence . . . . . . . . . . . . . . . . . . . . . . . . . 19
2.7.3 Arbres binaires . . . . . . . . . . . . . . . . . . . . . . . . 21
2.7.4 Graphe orient´e . . . . . . . . . . . . . . . . . . . . . . . . 22
2.7.5 Graphe non orient´e . . . . . . . . . . . . . . . . . . . . . . 23
2.8 Parcours particuliers . . . . . . . . . . . . . . . . . . . . . . . . . 26
34 TABLE DES MATI ` ERES
2.8.1 Parcours Hamiltonien . . . . . . . . . . . . . . . . . . . . 26
2.8.2 Parcours Eul´erien . . . . . . . . . . . . . . . . . . . . . . 27
2.9 Le plus court chemin . . . . . . . . . . . . . . . . . . . . . . . . . 28
2.9.1 Les donn´ees . . . . . . . . . . . . . . . . . . . . . . . . . . 28
2.9.2 Principe d’optimalit´e . . . . . . . . . . . . . . . . . . . . . 28
2.9.3 Circuit absorbant . . . . . . . . . . . . . . . . . . . . . . . 28
2.9.4 D’un sommet `a tous les autres ou Dijkstra . . . . . . . . . 28
2.9.5 Nouvel algorithme . . . . . . . . . . . . . . . . . . . . . . 31
2.9.6 Algorithme de FLOYD . . . . . . . . . . . . . . . . . . . 32
2.9.7 Algorithme de FLOYD . . . . . . . . . . . . . . . . . . . 35
2.10 Graphes sans circuit . . . . . . . . . . . . . . . . . . . . . . . . . 35
2.10.1 Tri topologique . . . . . . . . . . . . . . . . . . . . . . . . 35
2.10.2 Decomposition en niveaux . . . . . . . . . . . . . . . . . . 35
2.10.3 Exercice . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36
2.11 Arbre recouvrant de poids minimal . . . . . . . . . . . . . . . . . 37
2.12 Quelques paradigmes . . . . . . . . . . . . . . . . . . . . . . . . . 37
2.13 Optimisation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38
3 Arbres binaires 45
3.1 Arbres de recherche . . . . . . . . . . . . . . . . . . . . . . . . . 45
3.1.1 D´efinition . . . . . . . . . . . . . . . . . . . . . . . . . . . 45
3.1.2 Exemples et contre-exemples . . . . . . . . . . . . . . . . 45
3.1.3 Intérêt . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45
3.1.4 Representations . . . . . . . . . . . . . . . . . . . . . . . . 45
3.1.5 Arbre binaire ”plein” ou ”complet” . . . . . . . . . . . . . 45
3.1.6 Insertion . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45
3.1.7 Suppression . . . . . . . . . . . . . . . . . . . . . . . . . . 46
3.1.8 Exercices . . . . . . . . . . . . . . . . . . . . . . . . . . . 46
3.2 Arbres equilibres . . . . . . . . . . . . . . . . . . . . . . . . . . . 46
3.2.1 D´efinition . . . . . . . . . . . . . . . . . . . . . . . . . . . 46
3.2.2 Exemples et contre-exemples . . . . . . . . . . . . . . . . 46
3.2.3 Interet . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46
3.2.4 Insertion . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46
3.2.5 Suppression . . . . . . . . . . . . . . . . . . . . . . . . . . 47
3.2.6 Exercices . . . . . . . . . . . . . . . . . . . . . . . . . . . 48
3.3 Tas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48
3.3.1 D´efinition . . . . . . . . . . . . . . . . . . . . . . . . . . . 48
3.3.2 Exemples et contre-exemples . . . . . . . . . . . . . . . . 48
3.3.3 Interet . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49
3.3.4 Construction `a partir d’un AB . . . . . . . . . . . . . . . 49
3.3.5 Insertion . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50
3.3.6 Suppression . . . . . . . . . . . . . . . . . . . . . . . . . . 50
3.3.7 Exercices . . . . . . . . . . . . . . . . . . . . . . . . . . . 50
3.4 Tri arbre . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50
3.4.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . 50
3.4.2 Exemple . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51TABLE DES MATI ` ERES 5
4 Programmation lin´eaire 55
4.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55
4.1.1 Enonce . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55
4.1.2 Mise en forme . . . . . . . . . . . . . . . . . . . . . . . . . 55
4.1.3 Solution graphique . . . . . . . . . . . . . . . . . . . . . . 55
4.2 Un probleme . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55
4.2.1 Enonce . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55
4.2.2 Solution graphique . . . . . . . . . . . . . . . . . . . . . . 57
4.2.3 Remarque . . . . . . . . . . . . . . . . . . . . . . . . . . . 57
4.3 Un autre probleme . . . . . . . . . . . . . . . . . . . . . . . . . . 58
4.4 Resolution . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58
4.4.1 Rappel . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58
4.4.2 Demarche . . . . . . . . . . . . . . . . . . . . . . . . . . . 58
5 Solutions 61
5.1 Exercice 1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61
5.2 Exercice 2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61
5.3 Exercice 3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63
5.4 Exercice 4 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 64
6 Le simplexe 69
6.1 Principe . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 69
6.2 Exemple 1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 69
6.2.1 Forme mathematique . . . . . . . . . . . . . . . . . . . . . 69
6.2.2 Mise sous forme dequations . . . . . . . . . . . . . . . . . 69
6.2.3 Une premiere solution . . . . . . . . . . . . . . . . . . . . 70
6.2.4 Ameliorer F . . . . . . . . . . . . . . . . . . . . . . . . . . 70
6.2.5 Encore ameliorer F . . . . . . . . . . . . . . . . . . . . . . 70
6.3 Exemple 2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71
6.3.1 Le probleme sous forme mathematique . . . . . . . . . . . 71
6.3.2 Mise sous forme d’equations . . . . . . . . . . . . . . . . . 71
6.3.3 Une premiere solution . . . . . . . . . . . . . . . . . . . . 71
6.3.4 Ameliorer F . . . . . . . . . . . . . . . . . . . . . . . . . . 71
6.3.5 Encore ameliorer F . . . . . . . . . . . . . . . . . . . . . . 71
6.3.6 Nouvelle amelioration de F . . . . . . . . . . . . . . . . . 72
6.3.7 En r´esum´e... . . . . . . . . . . . . . . . . . . . . . . . . . 72
6.4 Mise en forme pour l’algorithme : exemple 1 . . . . . . . . . . . . 73
6.5 Mise en forme : exemple 2 . . . . . . . . . . . . . . . . . . . . . . 74
6.6 Les etapes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 76
7 Le voyageur de commerce 77
7.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 77
7.1.1 Parcours particuliers . . . . . . . . . . . . . . . . . . . . . 77
7.1.2 Le voyageur de commerce . . . . . . . . . . . . . . . . . . 77
7.1.3 Separation et evaluation . . . . . . . . . . . . . . . . . . . 77
7.1.4 Algorithme de Little . . . . . . . . . . . . . . . . . . . . . 78
7.1.5 Exemple . . . . . . . . . . . . . . . . . . . . . . . . . . . . 78
7.2 Exemple 2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 82
7.2.1 Donnees . . . . . . . . . . . . . . . . . . . . . . . . . . . . 82
7.2.2 R´eduction initiale . . . . . . . . . . . . . . . . . . . . . . 836 TABLE DES MATI ` ERES
7.2.3 Iteration 1 . . . . . . . . . . . . . . . . . . . . . . . . . . . 83
7.2.4 Iteration 2 . . . . . . . . . . . . . . . . . . . . . . . . . . . 84
7.2.5 Iteration 3 . . . . . . . . . . . . . . . . . . . . . . . . . . . 84
7.2.6 Iteration 4 . . . . . . . . . . . . . . . . . . . . . . . . . . . 84
7.3 Exemple 2 bis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 84
7.4 Exemple 3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 86
7.5 Exemple 3 bis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 88
7.6 Exemple 4 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 89
7.7 Exemple 4 bis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 91
8 Ordonnancement 93
8.1 Exemple . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 93
8.2 Representation graphique . . . . . . . . . . . . . . . . . . . . . . 93
8.2.1 G´en´eralit´es . . . . . . . . . . . . . . . . . . . . . . . . . . 94
8.2.2 Des contraintes . . . . . . . . . . . . . . . . . . . . . . . . 94
8.2.3 Methode MPM (Potentiels/tˆaches) . . . . . . . . . . . . . 94
8.2.4 Methode PERT (Potentiels/´etapes) . . . . . . . . . . . . 95
9 Elements de logique 97
9.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 97
9.1.1 Enonce . . . . . . . . . . . . . . . . . . . . . . . . . . . . 97
9.1.2 Propositions . . . . . . . . . . . . . . . . . . . . . . . . . 97
9.1.3 Connecteurs logiques . . . . . . . . . . . . . . . . . . . . . 97
9.1.4 Lois de De Morgan . . . . . . . . . . . . . . . . . . . . . . 97
10 Test 99
10.1 Dijkstra . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 99
10.1.1 Initialisation . . . . . . . . . . . . . . . . . . . . . . . . . 99
10.1.2 Iteration 1 . . . . . . . . . . . . . . . . . . . . . . . . . . . 99
10.1.3 Iteration 2 . . . . . . . . . . . . . . . . . . . . . . . . . . . 100
10.1.4 Iteration 3 . . . . . . . . . . . . . . . . . . . . . . . . . . . 100
10.1.5 Remarque . . . . . . . . . . . . . . . . . . . . . . . . . . . 100
10.2 Dijkstra 2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 100
10.2.1 Le graphe . . . . . . . . . . . . . . . . . . . . . . . . . . . 100
10.2.2 Initialisation . . . . . . . . . . . . . . . . . . . . . . . . . 100
10.2.3 iteration 1 . . . . . . . . . . . . . . . . . . . . . . . . . . . 100
10.2.4 iteration 2 . . . . . . . . . . . . . . . . . . . . . . . . . . . 101
10.2.5 iteration 3 . . . . . . . . . . . . . . . . . . . . . . . . . . . 101
10.2.6 Solution . . . . . . . . . . . . . . . . . . . . . . . . . . . . 102
10.3 Fermeture transitive . . . . . . . . . . . . . . . . . . . . . . . . . 102
10.4 FLOYD . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 103