La simulation informatique Par Boubetra Abdelhak -département d’informatique -cubba








télécharger 132.98 Kb.
titreLa simulation informatique Par Boubetra Abdelhak -département d’informatique -cubba
page1/3
date de publication31.07.2017
taille132.98 Kb.
typeDocumentos
m.21-bal.com > droit > Documentos
  1   2   3

La simulation informatique Par Boubetra Abdelhak -Département d’informatique -CUBBA

______________________________________________________________________________

Chapitre 3  La simulation informatique
3.1 Introduction 

L’idée de la simulation informatique (computer simulation) est venue de l’utilisation des ordinateurs pour imiter, simuler, les opérations des différents types de facilités ou processus du monde réel. Ces processus sont appelés des systèmes, et dans un but de les étudier scientifiquement nous faisons souvent des formulations sur leur fonctionnement. Ces formulations, qui prennent souvent la forme mathématique où relations logiques, constituent un modèle qui est utilisé pour essayer de comprendre comment le système correspondant se comporte.

Si les relations qui composent le modèle sont simples, il est possible d’utiliser des méthodes mathématiques pour obtenir des informations exactes sur des questions qui nous intéressent. C’est ce qu’on appelle une solution analytique. Cependant, la vaste majorité des systèmes du monde réel sont si complexes pour permettre d’avoir des modèles réalistes afin de les évaluer analytiquement, et ces modèles doivent être étudiés par le moyen de la simulation.
3.2 Les systèmes, les modèles et la simulation

Un système est défini comme étant une collection d’entités, par exemple des personnes où des machines, qui agissent et interagissent ensemble dans un but d’accomplir une fin logique. Cette définition a été propose par [Schmidt et Taylor 1970] :

‘’A system is defined to be a collection of entities, e.g. people and machines, that act and interact together toward the accomplishment of some logical end”.

En pratique, ce qui forme un système dépend des objectifs de l’étude visée. L’ensemble des entités qui composent le système dans une étude peut être un sous ensemble de tout le système dans une autre étude. La description des entités, des attributs et des activités en un point de temps qui est nécessaire pour prédire le comportement futur d’un système définit l’état du système et les variables correspondantes sont appelées les variables d’état. Les variables d’état relient le passé au futur via le présent.

Le choix du nombre et la nature des variables d ‘état sont dictées par les exigences et les besoins de l’étude en cause. Ce choix impose de faire une abstraction sur les composants du système et prendre en considération ceux qui aident et donnent une forte sémantique lors de l’analyse des résultats de l’étude.

Dans l’étude des systèmes on a tendance à les classer en deux catégories : les systèmes discrets et les systèmes continus. Un système discret est celui dont les variables d’état changent en des points de temps séparés. Un système continu est celui dont les variables d’état changent continuellement. En réalité peu de systèmes sont totalement discrets ou totalement continus, mais le fait qu’un type de changement prédomine on classifie le système soit qu’il est continu où discret.

En des moments du cycle de vie d’un grand nombre de systèmes, il y a un besoin de les étudier pour se faire une idée sur leur comportement et cela dans un objectif de les évaluer. La figure 3.1 indique les différentes manières d’étudier un système.




Ainsi, l’étude d’un système se fait au moyen d’un modèle qui est une représentation imaginaire ou abstraite, et dont l’évolution dans une perspective préalablement définie, représente celles de certains aspects du système en cause. Un même système peut être représenté par plusieurs modèles, selon l’aspect concerné par l’étude ; et la valeur du modèle se juge par la contribution qu’il apporte à l’explication du système tout en restant dans le contexte de l’étude.

Les modèles sont utilisés dans la simulation dans le but d’observer les comportements futurs et éventuels d’un système. En d’autres termes, un modèle de simulation a pour fonction de déduire le comportement dans des situations non encore observées, à partir d’une bonne connaissance du système ou de certains de ses aspects. De cette présentation, il ressort que l’étude des systèmes en se basant sur un modèle et en utilisant l’ordinateur forme ce qu’on appelle une simulation informatique (a computer simulation).

La littérature propose plusieurs définitions de la simulation informatique. Ces définitions sont parfois proches, équivalentes ou complémentaires [Pritsker 1986] [Fishwick 1997]. Selon [Shannon 1975] par exemple, elle est définie comme étant le processus de conceptualisation d’un modèle informatique d’un système (où d’un processus) et la conduite d’expériences avec ce modèle dans un but soit de comprendre le comportement du système où d’évaluer les différentes stratégies de fonctionnement du système.

‘’Simulation is the process of designing a computerized model of a system (or a process) and conducting experiments with this model for the purpose either of understanding the behaviour of the system or evaluating various strategies for the operation of the system”.

Du fait de la nécessité d’avoir un bon modèle pour mener à bien une simulation, il est suggéré de classifier les modèles de simulation selon les dimensions suivantes [Law et al. 1991] :

  • Modèle de simulation statique : un modèle de simulation statique est une représentation du système en un point du temps, où simplement celui qui peut être utilisé pour représenter un système où le temps ne joue aucun rôle.

  • Modèle de simulation dynamique : un modèle de simulation dynamique représente un système quand il évolue dans le temps.

  • Modèle de simulation déterministe : un modèle de simulation déterministe ne contient aucun composant aléatoire.

  • Modèle de simulation stochastique : un modèle de simulation stochastique contient des composants aléatoires.

  • Modèle de simulation continu : un modèle de simulation représente un système continu.

  • Modèle de simulation discret : un modèle de simulation discret représente un système discret.

De cette taxonomie et de ce dimensionnement de la modélisation, la simulation est généralement catégorisée comme suit :

    • La simulation continue, où le système se présente sous la forme d'équations différentielles à résoudre. Elle permet de suppléer à la résolution analytique quand celle-ci est impossible. Effectuée au départ sur des calculateurs analogiques.

    • La simulation statistique où de Monte Carlo, où le système en cause présente des phénomènes stochastiques, c'est-à-dire on fait appel à des techniques probabilistes. Le nom de ces méthodes fait allusion aux jeux de hasard pratiqués à Monte-Carlo.

    • La simulation par agents, où la simulation est segmentée en différentes entités qui interagissent entre elles. Elle est surtout utilisée dans les simulations économiques et sociales, où chaque agent représente un individu ou un groupe d'individus. Par nature, son fonctionnement est asynchrone.

    • La simulation discrète dans laquelle le système est soumis à une succession d'évènements qui le modifient. Ces simulations ont vocation à appliquer des principes simples à des systèmes de grande taille.


Dans cette thèse, on s’intéresse aux modèles de simulation discrets d’où le type de la simulation discrète par évènements (Discrete-Event Simulation).

3.3 Processus de simulation 

Quand on fait appel à la simulation pour étudier un problème, les quatre phases suivantes sont appliquées [Shannon 1975] :

  1. Phase d’observation et d’identification du système : elle permet d’établir une certaine relation entre un observateur et un système du monde réel.

  2. Phase de formulation où de modélisation : elle est généralement formulée de deux étapes. La première étape est celle de la représentation du système, ou des images symboliques d’objets, des rapports et des modèles de comportement sont liées dans des structures, des hypothèses et des concepts. La deuxième étape est celle de la conception du modèle. Dans le contexte de la simulation informatique, [Zeigler et al. 1979] considère un modèle comme étant un ensemble d’instructions pour générer un comportement (séquences temporisées de valeurs de variables). D’ici l’étape de conception prend en charge la transformation des images symboliques et les hypothèses sur les objets en des structures de données et des procédures de calcul exprimées par une certaine forme informatique.

  3. Conduite d’expériences : dans le contexte informatique c’est l’exécution de l’ensemble des instructions (computer simulation program) représentant le système en cause.

  4. Phase d’analyse : durant cette phase on essai de comprendre le comportement généré par les expériences en évaluant les différentes stratégies pour le fonctionnement du système en cause.

De manière relativement simplifiée, le processus de simulation peut être présenté selon la figure 3.2. La modélisation fournit un modèle symbolique (modèle de connaissance), la programmation fournit un modèle informatique (modèle d’action), la simulation ou l’expérimentation fournit les résultats obtenus du modèle, l’analyse des résultats permet d’évaluer le processus à modéliser.


3.4 Gestion du temps et des évènements de la simulation discrète 

3.4.1 Introduction

En simulation discrète, nous ne savons pas à l’avance la valeur d’incrémentation du temps; au contraire cette valeur est déterminée individuellement pour chaque pas de temps, en se basant sur les actions qui composent le modèle. Les évènements sont déterminés par la séquence de chaque entité à commencer et à terminer une activité. Les actions globales de la simulation sont la conquête dans ces séquences à avoir ces entités concourantes. La discrétisation du temps est d’ici implicite dans le système lui-même, plutôt que d’être imposer par le simulateur. Le programme de simulation d’ici s’intéresse aux évènements intercalés entre les activités, sans pour autant se soucier des périodes de l’action active, menant à une inversion distinctive du souci.

L’utilisation du mot ‘’évènement’’, dans ce contexte, est une spécialisation de sa sémantique de tous les jours, qui veut dire simplement l’arrivée et la production (happening)  de quelque chose signifiante. Son origine étymologique du mot latin est ex-venire (va venir ; yet to come). Pour nos objectifs, on sépare les idées des arrivées instantanées de celles qui ont une durée significative ; pour les premières se sont des évènements discrets, ou tout simplement des évènements, et les dernières sont les activités. Ce choix nous permet de considérer l’avancement du temps d’un évènement à un autre. [Zeigler 1976] décrit l’avancement du temps dans les systèmes à évènements discrets comme un moyen de liaison des frontières d’un intervalle de temps entre un évènement et un autre en supposant que rien ne se passe dans cet intervalle.
3.4.2 Mécanismes de gestion du temps de la simulation discrète

Dans un modèle de simulation, la variable temps est capitale, car elle intervient pour synchroniser les éléments constitutifs du modèle, et pour ordonner les activités.

Due à la nature dynamique des modèles de simulation discrète, nous devons avoir le moyen de connaître le temps actuel de simulation et avoir aussi un mécanisme d’avancement du temps quand la simulation avance c'est-à-dire quand les évènements apparaissent.

En simulation l’unité de représentation du temps varie de la petite unité qui pourrait être la seconde, la minute, l’heure, le jour, le mois, l’année et même le siècle. La nature du système sous l’étude impose le choix de l’unité du temps. Traditionnellement, La variable temps où l’horloge de simulation peut être gérée de deux façons :

  1. Méthode de l’horloge où à incrément fixe : l’horloge de la simulation (c’est-à-dire la variable qui enregistre le temps courant de la simulation) progresse d’une unité de temps fixe (∆t), tout au long de la simulation, pour explorer la liste des évènements et déterminer si l’un d’eux doit avoir lieu à cette date. Le choix de cette unité (∆t) est très important pour une bonne simulation. En général cette méthode est utilisée dans les systèmes déterministes. Figure 3.3 est une illustration de cette méthode.

  2. Méthode de l’échéancier où à incrément variable: dans cette méthode (Figure 3.4) les seuls temps accessibles sont les dates d’évènements. L’horloge de simulation est avancée du temps (T) au temps (T + δt) si un où plusieurs évènements sont programmés à cette date (T + δt). Ainsi seuls les évènements sont représentés explicitement ; et les temps morts sont traités comme inactifs.






3.4.3 Structure d’une notification d’un évènement futur

Dans une simulation discrète, les évènements proviennent d’un ensemble de notifications d’évènements futurs qui est géré par l’exécutif de la simulation. Une notification d’un évènement futur peut être vue comme une entrée à un calendrier détenant un rendez vous futur. Quand la date et l’heure du rendez vous arrive, celui-ci aura lieu. Naturellement, quand un rendez vous ait lieu on l’enlève du calendrier.

Les opérations sur le calendrier ont des analogies directes dans les opérations de l’exécutif de la simulation. Au lieu d’un ‘calendrier’, nous appelons la collection des notifications des évènements futurs l’ensemble des évènements futurs. Les notifications d’évènements futurs sont recherchées dans l’ensemble des évènements futurs selon l’ordre croissant du temps : la base sur laquelle l’horloge de simulation avance. Par contre, les notifications nouvelles d’évènements futurs, provenant des actions effectuées lors de l’occurrence d’un évènement quelconque, sont insérées dans l’ensemble des évènements futurs (Figure 3.5). Les opérations effectuées sur cet ensemble sont appelées programmation d’évènements futurs.


Activations futures



Insertion d’évènements programmés

Recherche du prochain évènement



Activation courante


Figure 3.5 Relation entre l’ensemble des évènements futurs et l’activation du modèle.


D’ici il y a deux informations essentielles qu’on doit associer à une notification d’évènement futur :

  • Le temps d’occurrence de l’évènement,

  • Un pointeur aux actions de l’évènement de ce temps.

Le parcours des temps d’occurrence des évènements futurs dans le modèle pour choisir le minimum sera certainement suffisant pour exécuter la fonction d’activation d’évènements dans la séquence temporelle correcte. Mais comme le nombre de notifications futures devient grand, cette méthode deviendra consommatrice de temps d’exécution et inefficace. La première amélioration, évitant le parcours de toutes les occurrences futures, est de lier les notifications des évènements futurs dans l’ordre chronologique de leur apparition.

Si l’ordonnancement entre les notifications des évènements futurs est fait d’une manière ascendante comme indiqué dans la figure 3.6, un parcours simple à partir du début de la liste (la notification la plus proche) permettra facilement d’insérer une nouvelle notification d’évènement futur juste avant la première notification qui a juste un temps supérieur à elle.



3.5 Outils de modélisation de la simulation discrète

3.5.1 Introduction

La plupart des applications de la simulation discrète sont des systèmes de files d’attente d’une manière ou d’une autre. La file d’attente est généralement constituée d’un ensemble d’entités qui attendent la satisfaction et la vérification de certaines conditions, ou la disponibilité de certaines ressources, pour commencer et participer dans des activités. Une file d’attente peut être un ensemble de tâches d’un système manufacturier attendant d’être traitées par une ou plusieurs machines, comme elle peut être un ensemble de clients dans un supermarché attendant leur tour pour être servi. On a coutume, dans la littérature, d’appeler ces types de files d’attente par Le modèle clients/serveur ou le modèle producteur/consommateur. La figure 3.7 est une schématisation de ces modèles.

A
Départs
rrivées



Clients ou Producteur

Serveur ou Consommateur


Figure 3.7 Le modèle clients/serveur ou producteur/consommateur


La modélisation des systèmes dans un but de simulation nécessite la prise en compte des systèmes à ressources multiples. Ces structures complexes imposent l’étude et la prise en charge des réseaux de files d’attente, plutôt qu’à celle des files d’attente simples. De ce fait, un ensemble d’outils de modélisation est, généralement, utilisé pour générer le modèle de simulation du système en cause. Les outils et les dispositifs de modélisation qu’on introduit ici, vu leur importance à la simulation, sont les diagrammes de cycles d’activités et les réseaux de Petri.
3.5.2 Les diagrammes de cycles d’activités

Les ACD (Activity Cycle Diagrams) dus à [Tocher 1962] sont un moyen de modélisation des interactions des entités et sont particulièrement utiles pour les systèmes à files d’attente complexes. Leur popularité revient aux travaux de [Hills 1971] qui les a associés au système de simulation à trois phases qui sera développé dans le prochain chapitre. Les ACD font utilisation de trois éléments graphiques, comme c’est indiqué dans la figure 3.8. Un grand cercle représente une file d’attente ou un état oisif d’une classe d’entité, un rectangle représente une activité ou un état actif et un petit cercle représente une ressource.



Le diagramme en lui-même est un schéma du cycle de vie de chaque classe d’entités et montre graphiquement leurs interactions. Chaque classe d’entités a un cycle de vie formé d’un ensemble d’états. Les entités passent d’un état à un autre au fur et à mesure que leur durée de vie s’écoule.

Un état actif englobe souvent la coopération des différentes classes d’entités. La durée de l’état actif est souvent connue à l’avance et déterminée par l’échantillonnage à partir d’une distribution de probabilité si le modèle de simulation est stochastique.

En utilisant les ACD, modélisons les activités quotidiennes d’un enseignant universitaire qui passe sa journée entre les locaux pédagogiques (Amphi, salle de cours, salle de TD, salle de TP ou laboratoire) et son bureau faisant des consultations avec ses étudiants ou dans certaines situations dans une réunion (un comité pédagogique, un conseil scientifique, préparation de manifestations scientifiques etc.).

Pour un objectif visé, on distingue ici 3 classes d’entités ;

  1. un enseignant faisant ses tâches ;

  2. locaux pédagogiques ;

  3. une salle de réunion.


Nous modélisons les activités de chacune de ces classes.

i) L’enseignant :

L

’enseignant a trois activités essentielles  (En cours, En consultation, En Réunion). Quand l’enseignant n’est pas dans une de ces activités on peut le considérer comme il est dans un état oisif. D’ici le diagramme de cycle d’activités de l’enseignant est comme prend la forme de la figure 3.9.

En cours

En consultation









En réunion





Figure 3.9 L’ACD de l’enseignant

ii) Les locaux pédagogiques:

Un local peut être dans une des deux activités (En Cours, En entretien) sinon il est dans un état libre (figure 3.10).


En cours















En entretien





Figure 3.10 L’ACD des locaux pédagogiques

iii) La salle de réunion :

La salle de réunion, comme le montre la figure 3.11, peut être dans une des deux activités (En réunion, En nettoyage) sinon elle est dans un état oisif (fermée).

En réunion


Les trois cycles peuvent être combinés pour former le diagramme des cycles d’activités de ce modèle comme il est illustré dans la figure 3.12.



Dans ce modèle, quand l’enseignant se connecte sur Internet, ou corrige les examens ou prépare son cours est considéré comme une oisiveté ou une activité non concernée par la modélisation.

La logique de modélisation en utilisant les ACD impose le respect de certaines règles de base où une file d’attente contient un seul type d’entités, une activité est toujours précédée et suivie d’une file d’attente (la même ou une autre) et tout le cycle de vie d’une entité doit être fermé.
3.5.3 Les diagrammes de cycles d’activités étendus

Pour plus d’efficacité dans la modélisation des systèmes discrets, [Pooley 1991a, 1991b] et [Pooley et al. 1991] ont proposé des extensions aux ACD qui couvrent certains aspects manquants au niveau des ACD simples. Cette extension est connue sous le nom des X-ACD [Extended Activity Cycle Diagrams). Les X-ACD ont principalement amené une amélioration dans la spécification des producteurs d’entités entrants dans le système en fonction d’une loi et les consommateurs d’entités sortantes du système. En plus une distinction est faite entre les files d’attentes selon que l’attente est conditionnelle ou non conditionnelle. La figure 3.13 résume ces extensions.



Comme illustration de l’utilisation des X-ACD dans un objectif de simulation, considérons un système d’utilité particulière à notre santé qui est celui d’un hôpital. Nous nous intéressons dans ce système aux classes de patients qui sont admis pour suivre un traitement particulier et aux patients qui nécessitent une opération chirurgicale ou une intervention particulière.

Dans ce système, on peut constater qu’il y a deux classes d’entités (Patient 1 et Patient 2) et une entité particulière modélisant le bloc opératoire. La figure 3.14 représente Le modèle X-ACD de l’hôpital.


L’accès à l’hospitalisation n’est conditionné que par la disponibilité d’un lit au sens médical. Il n y a pas de manques de ressources humaines spécialisées. Une hospitalisation de traitement dure une période selon le cas.

Dans une hospitalisation qui nécessite une intervention chirurgicale, le patient doit passer une période avant l’opération à faire un bilan et il doit rester aussi une durée post-opération de convalescence.
3.5.4 Les réseaux de Petri 

En premier lieu, notons que le formalisme des réseaux de Petri [Petri 1962] est un cas particulier du formalisme général des systèmes de transitions. L’exemple le plus connu de systèmes de transitions est celui des automates à états finis où l’on donne explicitement tous les états, et tous les changements possibles d’états. Par rapport aux automates finis, les réseaux de Petri introduisent la possibilité d’avoir un ensemble infini d’états, et une notion de localité : un système est considéré comme composé d’un ensemble de sites. La possibilité d’effectuer une action dépend de conditions locales à certains sites, et cette action modifie uniquement l’état de certains sites.

Le parallélisme, c'est-à-dire le fait que plusieurs actions soient effectuées simultanément, est possible quand ces actions dépendent de sites différents, ou bien que les conditions sur un site commun à certaines de ces actions ne sont pas incompatibles. Les réseaux de Petri permettent ainsi de décrire les relations temporelles existant entre les différentes actions. Un système est vu au travers de ces relations, et les propriétés du système prouvables à partir du réseau qui le représente proviendront de ces relations.

Structurellement, un réseau de Petri est donné par des objets de quatre types :

- Les places qui correspondent à des sites.

- Le marquage d’une place (représentant l’état d’un site) est un nombre pouvant indiquer la satisfaction de conditions, ou plus généralement le nombre de ressources présentes dans le site.

- Les transitions qui correspondent aux actions.

- La fonction de transition donne pour chaque transition (action) les conditions qui doivent être remplies pour chacun des sites afin que cette action soit possible. Elle indique aussi l’effet de chaque transition sur l’état des sites.

Par exemple, dans un atelier d’assemblage de téléviseurs, une action consiste à placer le châssis au tube cathodique et visser avec quatre vis à l’aide d’un tournevis pneumatique. Un site contient les tubes cathodiques, le deuxième contient les châssis, le troisième contient les vis, le quatrième l’élément assemblé. L’un des aspects les plus agréables des réseaux de Petri est qu’il est extrêmement aisé de les visualiser.

En effet, un réseau de Petri utilise la forme géométrique du cercle pour représenter un site avec une appellation de place et le point pour exprimer les éléments du site avec une appellation de jeton. Le trait représente une action appelée ‘une transition’. Les places et les transitions sont reliées par des arcs étiquetés entrants et sortants. L’étiquette sur un arc entrant à une transition provenant d’une place, qui est généralement un nombre naturel, exprime le nombre de ressources nécessaires à l’action. L’étiquette sur un arc sortant d’une transition vers une place, qui est généralement un nombre naturel, exprime l’effet du passage de la transition sur la structure du système. Enfin, un état initial du réseau de Petri est exprimé par un certain nombre initial de jetons dans chaque site.

L’atelier décrit plus haut sera modélisé par le réseau de Petri de la figure 3.15.



3.5.5 Les réseaux de Petri temporisés

La nature dynamique des modèles de simulation discrète impose l’idée qu’on doit avoir un mécanisme qui se charge et contrôle la variable temps qui est primordiale. Le temps est introduit dans les réseaux de Petri pour modéliser la réalité comme un ensemble d’activités en interaction prenant en compte leur temps de début et leur temps de terminaison. Le temps peut être introduit dans les réseaux selon différentes approches [Hillion 1989]. On peut l’associer aux places, aux jetons et aux transitions.

De cela, on peut avoir des places temporisées, des jetons temporisés et des transitions temporisées. Le temps peut être associé aux places où les jetons générés, dans une place de sortie d’une transition, deviennent disponibles pour franchir une transition seulement après l’écoulement d’un certain délai; le délai est un attribut de la place. Par exemple dans la figure 3.16, la place temporisée P1 contient deux jetons prêts à tirer à partir, peut être, des moments différents et elle contient aussi trois autres jetons qui attendent l’écoulement de certains délais peut être différents.



Quand le temps est associé aux jetons, ces derniers prennent des durées comme des étiquettes ou des timbres (Time stamp) comme il est indiqué dans la figure 3.17. Ces temps indiquent les dates de disponibilité de tirer une transition ; ces dates peuvent être incrémentés en cas de besoin.


Dans le cas où le temps est associé avec les transitions (Figure 3.18), on peut assumer qu’une transition correspond à une activité dont le temps de son début correspond à la date de début de franchissement de la transition et sa fin correspond à la fin du franchissement de la transition.

Quand le temps est associé aux transitions, [Azeme et al. 1997] ont proposé plusieurs stratégies de franchissement :

  1. Franchissement à trois phases :

    1. Les jetons sont consommés des places en entrée quand la transition est prête à être franchie.

    2. Ecoulement du délai.

    3. Des jetons sont générés dans les places de sortie.

  2. Franchissement atomique :

Les jetons restent dans places d’entrée jusqu’à écoulement du délai de la transition ; ils sont consommés des places d’entrée et générés dans des places de sortie une fois la transition tire.
3.6 Outils statistiques de la simulation

3.6.1 Introduction

La simulation discrète représente, dans plusieurs situations, une expérimentation statistique contrôlée. Les modèles de simulation incluent généralement des éléments stochastiques de nature. Par exemple, des expériences sont conduites par des séquences d’entrée aléatoires, comme le temps des arrivées à un système, et produisent des séquences de sortie aléatoires, comme le temps de service.

L’utilisation d’une distribution de probabilité pour représenter le temps de service implique que le temps tiré pour un service particulier a deux propriétés. Premièrement, le temps tiré se trouve à l’intérieur des valeurs de cette distribution. Deuxièmement, la probabilité d’apparition de certaines valeurs particulières est guidée par la loi de cette distribution. D’ici, il est connu à l’avance l’intervalle du temps de service mais ce qui n’est pas connu exactement c’est quand est ce que ces valeurs apparaissent. Ces phénomènes sont généralement représentés par une variable aléatoire épuisant ses valeurs à partir d’un générateur de nombres aléatoires.
3.6.2 Les générateurs de nombres aléatoires

Selon l’encyclopédie libre WIKIPEDIA [www.fr.wikipedia.org], un générateur de nombres aléatoires est ‘’un algorithme qui génère une séquence de nombres présentant certaines propriétés du hasard. Cependant, les sorties d'un tel générateur ne sont pas entièrement aléatoires.’’ Elles s'approchent seulement des propriétés idéales des sources complètement aléatoires.

La raison pour laquelle on se contente d’un rendu pseudo-aléatoire est : d’une part qu’il est difficile d’obtenir de « vrais » nombres aléatoires et que, dans certaines situations, il est possible d’utiliser des nombres pseudo-aléatoires, en lieu et place de vrais nombres aléatoires ; d’autre part, que ce sont des générateurs particulièrement adaptés à une implémentation informatique, donc plus facilement et plus efficacement utilisables.

Générer des nombres aléatoires sur ordinateur revient à créer une suite d'entiers:

Sn+1 = f(Sn)

f est une fonction qui doit être choisie judicieusement pour que la répartition des nombres Sn ne puisse pas être distinguée de ce que donnerait le hasard. On parle alors de nombres pseudo aléatoires.

La suite peut fournir M nombres aléatoires dans l'intervalle [0, M-1]. M dépend du type des entiers :

  • entiers 16 bits : M = 216 = 65 536

  • entiers 32 bits : M = 232 = 4 294 967 296 (soit plus de 4 milliards de nombres aléatoires)

La valeur de départ S0, appelée graine (seed), doit être fournie par l'utilisateur. La même graine donnera toujours la même suite de nombres. D'autre part, la suite se reproduit au bout d'un nombre de valeurs appelé période. Cette période doit être la plus grande possible.

Si la fonction f a été correctement choisie, chaque nombre a la même probabilité d'apparaître. On dit que les nombres aléatoires suivent une loi uniforme.

Nous décrivons ici une des méthodes permettant de générer des nombres aléatoires qui est celles des générateurs congruentiels, c'est à dire définis par le choix de la valeur entière initiale S0 (le "random seed") et par la récurrence on aura :

Sj+1 = modp(Sj x a + b, p) c'est-à-dire

Sj+1 = Le reste de [(Sj x a + b)/ p)

Les nombres fournis par le générateur étant les restes de (Sj x a + b)/ p. On peut en effet calculer aisément la période d'un tel générateur.

Examinons les cas réellement utiles : p = 2m et p premier. L'intérêt du premier cas est évident car l'arithmétique modulaire se simplifie considérablement lorsque 2m est égal à la taille du "mot machine" ou est une puissance de celui-ci.

Prenant comme exemple (simpliste) p = 2m = 8 et a= 5, b= 1 on obtient :



Prenant comme exemple (simpliste) p = 7 a= 5, b= 0 on obtient :



Un exemple "réel" de ce procédé est le générateur lgm, proposé par [Lewis et al. 1973] en 1969. On part d'un nombre et l'on calcule ses successeurs par la récurrence Sj+1 = modp(Sj x a + b, p) où le nombre p = 2147483647, le nombre a= 16807 et b= 0. On obtient l'algorithme (figure 2.19) dans lequel lgm_seed contient les instanciations successives de l'entier Sj.

LGM := proc PR( ) global lgm_seed

lgm_seed := modp(lgm_seed X 16807, 214783647)

return evalf(lgm_seed % 214783647)

Figure 3. 19 Générateur lgm(Lewis, Goodman, Miller, 1969)

Si pour un intérêt plus particulier avec plus détail sur les générateurs de nombres aléatoires, nous suggérons le site web [www.random.org].

3.6.3 Quelques générateurs pseudo-aléatoires

Dans cette section on présente quelques pseudo-aléatoires générateurs congruentiels utilisés sur des gammes d’ordinateurs ou par des logiciels connus. Le générateur congruentiel linéaire (linear congruentiel generator) est initialement proposé par [Lehmer 1948].

Le pseudo générateur est de la fome :

Yn+1 = [ayn + b] (mod m) et un seed y0 et on l’exprime par LCG(m,a,b, y0)
  1   2   3

similaire:

La simulation informatique Par Boubetra Abdelhak -département d’informatique -cubba iconCours: inititation a word, initiation a excel
«informatique» date de 1962. IL vient de la contraction des mots «information» et «automatique». L’histoire de l’informatique est...

La simulation informatique Par Boubetra Abdelhak -département d’informatique -cubba iconDÉpartement techniques de l’informatique Campus Gabrielle Roy / Campus Félix-Leclerc

La simulation informatique Par Boubetra Abdelhak -département d’informatique -cubba icon000 – informatique information 04 Informatique

La simulation informatique Par Boubetra Abdelhak -département d’informatique -cubba iconUfr ima grenoble Master 1 Mathématique Informatique Spécialité Informatique
«saturer» le récepteur (remplir son buffer de réception). Par exemple envoyer 6 paquets de 5000 octets, puis essayez de les réceptionner...

La simulation informatique Par Boubetra Abdelhak -département d’informatique -cubba iconNé en 1912, le mathématicien anglais Alan turing est considéré come...
«tête de lecture/écriture» peut lire ou écrire ces cases puis se déplacer en fonction de l’information vers la gauche ou vers la...

La simulation informatique Par Boubetra Abdelhak -département d’informatique -cubba iconRelatif à la consultation portant : Acquisition d’ouvrages de bibliothèque...
«A ne pas ouvrir», au plus tard le 05/09/2011 avant 10h30 au secrétariat général de la faculté du génie électrique et d’informatique...

La simulation informatique Par Boubetra Abdelhak -département d’informatique -cubba iconDéfinitions
«Informatik» est créé par l'ingénieur Karl Steinbuch dans son essai intitulé «Informatik: Automatische Informationsverarbeitung»,...

La simulation informatique Par Boubetra Abdelhak -département d’informatique -cubba iconProgrammes informatiques
«Informatik» est créé par l'ingénieur allemand Karl Steinbuch dans son essai intitulé «Informatik: Automatische Informationsverarbeitung»,...

La simulation informatique Par Boubetra Abdelhak -département d’informatique -cubba iconL'informatique est le domaine d'activité scientifique, technique...

La simulation informatique Par Boubetra Abdelhak -département d’informatique -cubba iconExperiences professionnelles
«maîtrise des notions de base de l’outil Informatique» sanctionnée par l’octroi d’une attestation de l’aref, en faveur du personnel...








Tous droits réservés. Copyright © 2016
contacts
m.21-bal.com