Introduction : problématique et résultats obtenus 7
1. Problématique et positionnement de la présente thèse 7
Contexte de l'étude entreprise (7); Un équilibre 26/27 (7); Un équilibre théorie-pratique (8)
2. Contenus originaux de cette thèse 8
Méthode hiérarchisée et auto régulée de simulation des événements rares (8);
Fonctions splines et structures de données (8); Inversion de la transformation de
Laplace (9); Modélisation des transitions d'un système à files d'attente par des
états "excités" (9); Obtention des probabilités temporelles à l'aide de la chaîne de
Markov des transitions (9)
Chapitre I. Structures de données et convolutions de fonctions splines 11
1. Fonctions définies par morceaux 11
Présentation (11); Implémentation d'origine (12); Une autre implémentation (14);
Actions simples sur les fonctions par morceaux (15); Difficulté intrinsèque de
l'opération de convolution (16)
2. Variables qualifiées : une première approche 17
Pose du problème (17); Le mécanisme de surcharge (17); Gestion des conflits de
dénomination (18); Comparaison effective de deux variables qualifiées (19)
3. Qualification temporaire d'une variable 20
Nécessité d'un mécanisme de qualification temporaire (20); Implémentation du
système de qualification (21); La solution proposée (21)
4. Convolution de deux fonctions 23
Présentation : somme de variables indépendantes (23); Quelques résultats sur les
convolutions (24); Points anguleux et complexité (26); Implémentation des
convolutions (26)
5. Compléments 27
Manipulations d'intégrales (27); Règle de l'Hôpital et calcul formel (29); Décalage
d'une variable de sommation (30); Programmation des dessins (32); Exercices
complémentaires (33)
Chapitre II. Formule de Pollaczek-Khintchine 35
1. Files d'attente GI/GI/1 35
Description du problème (35); Quelques (!) notations (35); Service ordinaire et
services spéciaux (36)
2. Files M/GI/1 et formule de Pollaczek-Khintchine 38
Inter-arrivées exponentielles (39); Loi de Poisson (39); Formalisme des séries
génératrices (40); Nombre moyen de clients dans une file M/GI/1 (42); Formule
de Pollaczek-Khintchine (44)
3. Inversion de la formule de Pollaczek-Khintchine 44
Paramètres de dispersion du temps de séjour (44); Introduction des fonctions
auxiliaires (45); Loi du service résiduel (46); Loi du temps d'attente conditionnel
(46); Description de la méthode proposée (47); Paramètres de dispersion des
variables auxiliaires (48)
4. Trois exemples 49
Services déterministes (49); Services uniformes (49); Services exponentiels :
théorème des débits de Poisson. (50); Exercices (50)
5. Résolution exacte de la file M/D/1 51
Spécificité du cas des services déterministes (51); Résolution explicite (52); Loi
du temps d'attente conditionnel dans une file M/D/1 (56); Queue de la fonction
de répartition (57)
Chapitre III. Une méthode semi-numérique d'inversion de la transformation de Laplace 61
1. Reprise du cas déterministe 61
Premières itérations (61); Comparaison avec la solution exacte (65); Un
encadrement pour les événements pas trop rares (66)
2. Services de loi uniforme. 69
Description du problème (69); File M/U/1 : résultats intermédiaires (70); File
M/U/1 : résultats (72); Compléments (73)
3. Modélisation d'un disque dur 73
Description du problème (73); Données matérielles (74); Modélisation du temps
de positionnement (76); Premiers résultats (77)
4. Références 79
Articles archivés (79)
Chapitre IV. Techniques d'accélération 81
1. Techniques d'accélération 81
Exponentiation rapide : un échec (81); Théorème central limite (82); Polynômes
d'interpolation de Lagrange (84); Poursuite des calculs (86); Quelques remarques
(88); Complément : services uniformes (89); Poursuite des calculs (89)
2. Quelques remarques sur la stabilité des algorithmes 91
Gestion de projets (91); Mesure de l'efficacité numérique (91)
3. Méthode de compensation des points anguleux 94
Description de la méthode (94); Choix des termes de compensation (95)
4. Résolution du modèle de disque dur 98
Approximations et temps de calcul (98); Exemple simplifié (calcul direct) (102);
Exemple simplifié (approximation triangulaire) (103)
Chapitre V. Méthode hiérarchique de simulation pour événements rares 105
1. Le modèle du réparateur 105
Présentation du modèle (105); Décomposition d'une réparation (déterministe)
individuelle (106); Formule générale des durées moyennes (108); Distribution du
nombre de pannes survenant pendant une réparation (110); Nombre de machines
originellement en service connaissant le nombre de pannes (112)
2. Chaîne de Markov incluse 113
Chaîne des périodes du réparateur (113); Redéploiement temporel du vecteur
stationnaire (115)
3. Chaîne de Markov : variance du nombre de passages 116
Formalisme matriciel et valeurs propres (116); Puissances itérées et sommations
(117); Chemins markoviens et espérances des nombres de visites (118);
Variances des nombres de visites (119)
4. Estimation des espérances et des variances par simulation 122
Un premier programme de simulation (122); Comparaison théorie/simulation
(125); Simulation par lots (126); Un estimateur de la variance (127); Modification
du programme (127); Un exemple de résultats (129)
5. Chaînes des transitions 131
Chaîne des transitions de la chaîne de Markov (131); Déploiement temporel
(132); La chaîne des niveaux (133); Chaîne des transitions de niveaux (135);
Déploiement temporel de la chaîne des niveaux (136)
6. Comparaison avec le cas exponentiel 137
La chaîne du réparateur (137); Déploiement temporel (138); La chaîne des
niveaux d'indisponibilité (140)
7. Méthode hiérarchique pour le réparateur exponentiel 143
Simulations préférentielles (143); Un exemple (143); Pondération des échelons
(144); Pour un choix quasi optimal des échelons (145); Discussion (146)
8. Application au réparateur déterministe 147
Difficulté intrinsèque du problème (147)
9. Références 148
Chapitre VI. Etats excités et pertes de cellules dans un système à capacité limitée 149
1. Introduction. 149
L'ATM (149); Le problème générique à résoudre (150); Organisation de ce
chapitre (150)
2. Un réseau de Clos à trois étages 150
L'architecture choisie (150); Hypothèses sur la géométrie (151); A propos des
entrées et de l'indépendance (151)
3. Une méthode pour évaluer le taux de perte 152
Présentation (152); Processus de naissance et de mort (152); Tampons avec des
arrivées multiples (153); Interprétation matricielle (153); Système d'attente
symétrique (154)
4. Résultats supplémentaires 155
Système dissymétrique (155); Occupation moyenne d'un commutateur (156)
5. Conclusion 157
Travaux à venir (157); Résumé (157)
6. Références 158
Annexe I. Maple, un outil de calcul formel 159
1. De la sémantique à la syntaxe 159
La saisie d'une expression (159); Analyse syntaxique d'une expression (160);
Elagage et DAGU (161); Affichage d'une expression (162)
2. De la syntaxe aux octets 163
Le DAGM d'une expression (163); Stockage effectif d'un DAGM (164);
Désassemblage d'une expression (165); Les cellules de données (167); Règles
d'évaluation (170)
3. Tables de hachage 171
Tables, arrays et matrices (171); Copier une matrice (172); Description des tables
de hachage. (173)
4. Programmation 175
Le noyau en assembleur (175); Les cellules de commandes (175); Manipulations
de procédures (177)
5. Deux logiques, et leurs conflits 178
6. Références : calcul formel 181
Livres (181); Articles archivés (181)
Annexe II. Transformée de Laplace inverse : quelques méthodes usuelles 183
1. Transformation de Laplace 183
Définition (183); Propriétés élémentaires (184); Exemple 1 : calcul d'une
intégrale (185); Exemple 2 : une équation différentielle (186); Exemple 3 : un
demi-échec (187); Transformation inverse : résultats généraux (188)
2. Transformation inverse : méthodes élémentaires 188
Tabulation (188); Décomposition en éléments simples (189); Formule de
Bromwich (190); Exemple de recherche des pôles (190)
3. Polynômes orthogonaux (Widder-Weeks) 193
Polynômes de Laguerre (193); Coefficients de Fourier (194); Un cas d'école
(196); Application aux services déterministes (198)
4. Quadrature de Gauss (Salzer) 200
5. Loi des grands nombres (Gaver-Stehfest) 200
Description de la méthode (200); Exemple des services déterministes (202); Le
noyau de Gaver (204); Application de la loi des grands nombres (207); Une
accélération de Romberg (208)
6. Transformée de Fourier rapide (Dubner-Cooley) 210
7. Approximants de Padé (Kautz) 210
8. Références 211
Articles fondateurs (211); Articles de synthèse (211); Articles archivés (212);
Livres (214); Autres références (215)
Annexe III. Simulations sur ordinateur 217
1. Hypothèses implicites 217
Modèle probabiliste (217); Modèle utilisé lors d'une simulation (218); Théorème
central limite (218); La règle des deux sigmas (219)
2. Estimateurs et estimation de la validité d'un estimateur 220
L'exemple du jeu de pile ou face (220); Découpage en blocs (221); Variance de
l'estimateur de la moyenne (222); Blocs et erreurs de troncature (222);
Estimateurs de la variance (222); Encadrement, au risque de 95%, de l'espérance
(223); Un autre exemple : la somme de deux dés (224)
3. Le package 'stats' de Maple 225
Présentation (225); Statistique descriptive (226); Les lois usuelles (227);
Générateurs pseudo-aléatoires (228); Générateur normal (230); Visualisation des
résultats (231)
4. Importance sampling 232
5. Références (simulations) 233
Articles de synthèse (233); Articles archivés (233); Livres (233)
6. Références (importance sampling) 234
Articles de synthèse (234); Articles archivés (234)
Conclusion 239
1. Transformée de Laplace inverse d'une fonction spline 239
2. Modélisation du temps de réponse d'un disque dur 239
3. Utilisation systématique de M/D/1 pour controler les raisonnements M/M/1 240
4. Méthode de simulation d'événements rares 240
5. L'inévitable lien entre la recherche et l'enseignement 241
Une déformation professionnelle (241); Choix de l'exemple-type pour illustrer les
problèmes de files d'attente (241); Utilisation du calcul formel (241)
Figures 243
Sessions 245
Index 251