Remerciez-le!

Remerciez @Admin pour avoir partagé cet document gratuitement, de la manière la plus simple, en partageant sur les réseaux sociaux.

91 Université Mohammed Seddik Ben yahia‐ Jijel Faculté des Sciences Exactes et

91 Université Mohammed Seddik Ben yahia‐ Jijel Faculté des Sciences Exactes et Informatique Département Informatique 2016 Département d’informatique, université de Jijel BP 98 Ouled Aissa. 18000, JIJEL, ALGERIE Support de Cours Simulation & Prototypage Spécialités Système d’Information et Aide à la Prise de Décision (SIAD) Auteur Dr. KERKOUCHE EL-HILLALI Simulation & Prototypage Ministère de l’Enseignement Supérieure et Recherche Scientifique Université de Jijel Faculté des Sciences Exactes et Informatique Département Informatique Simulation & Prototypage Support de Cours Simulation & Prototypage Spécialité Système d’Information & Aide à la Prise de Décision (SIAD) Présenté par Dr. KERKOUCHE El-Hillali Le cours de Simulation & Prototypage est préparé pour servir comme support pédagogique d’étudiants inscrits en première année Master de spécialités système d’information et aide à la prise de décision (SIAD) filière informatique. Table des Matières i Table des Matières Chapitre 01 : Modélisation & Simulation : une Introduction 1.1 Introduction ————————————————————————————————————————————————————– 1 1.2 Notion de Système –––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––– 2 1.2.1 Définition d’un Système ––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––– 3 1.3 Modélisation et Modèle ––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––– 4 1.3.1 Définition (Modèles) –––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––– 5 1.3.2 Processus de Modélisation –––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––– 5 1.3.3 Classification des Modèles –––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––– 6 1.3.3.1 Les Modèles Physiques ––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––– 6 1.3.3.2 Les Modèles Symboliques ou Analytiques ––––––––––––––––––––––––––––––––––––––––––––––––– 7 1.3.4 Outils de Modélisation ––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––– 9 1.3.5 Evaluation de Modèles –––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––– 10 1.3.5.1 Evaluation Qualitative –––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––– 10 1.3.5.2 Evaluation Quantitative –––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––– 10 1.4 Simulation –––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––– 12 1.4.1 Définition (Simulation) –––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––– 12 1.4.2 Les Langages de Simulation –––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––– 13 1.4.3 Quand Simuler ––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––– 14 1.4.4 Limites (Obstacles) –––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––– 14 1.6 Résumé –––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––– 15 Chapitre 02 : Machines d’Etats Finis 2.1 Introduction –––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––– 16 2.2 Définition –––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––– 16 2.3 Représentation –––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––– 16 2.4 Exemple de Modélisation de Distributeur de Café ––––––––––––––––––––––––––––––––––––––––––– 18 2.5 Propriétés des Machine d’Etats Finis –––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––– 19 2.5.1 Automate fini & Automate infini ––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––– 19 2.5.2 Automate Déterministe –––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––– 19 Table des Matières ii 2.6 Structure de Kripke ––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––– 20 2.7 Sémantique & Exécution ––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––– 20 2.7.1 Chemin d’Exécution ou Trace ––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––– 20 2.7.2 Exécution –––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––– 20 2.7.3 Arbre d’Exécution –––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––– 21 2.7.4 Atteignabilité ––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––– 21 2.8 Raisonnement sur les Machines d’Etats Finis ––––––––––––––––––––––––––––––––––––––––––––––––––– 21 2.9 Exercices ––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––– 22 Chapitre 03 : StateCharts 3.1 Introduction –––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––– 24 3.2 Définition –––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––– 24 3.3 Représentation –––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––– 25 3.3.1 Etat ––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––– 25 3.3.2 Transition ––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––– 26 3.3.3 Etats Composites –––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––– 27 3.3.3.1 Etat Composite Séquentiel (Hiérarchique ou XOR) –––––––––––––––––––––––––––––––––––– 28 3.3.3.2 Etat Historique ––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––– 29 3.3.3.3 Etat Composite Orthogonal (Concurrent ou AND) ––––––––––––––––––––––––––––––––––––– 30 3.4 Sémantique et Exécution ––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––– 32 3.5 Exercices ––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––– 33 Chapitre 04 : Réseaux de Petri 4.1 Introduction –––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––– 34 4.2 Définition –––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––– 34 4.2.1 Définition Informelle ––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––– 34 4.2.2 Définition Formelle –––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––– 35 4.2.3 Représentation Matricielle ––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––– 35 4.3 Sémantique & Exécution ––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––– 36 4.3.1 Dynamique ––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––– 36 4.3.2 Graphe de Marquages –––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––– 37 4.3.3 Graphe de Couverture –––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––– 38 4.3.4 Vecteur d’Occurrence et l’Equation de Changement d’Etat ––––––––––––––––––––––––––– 39 4.4 Propriétés des Réseaux de Petri –––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––– 40 4.4.1 Les Propriétés Structurelles ––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––– 40 Table des Matières iii 4.4.2 Les Propriétés Comportementales ––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––– 41 4.5 Modélisation des Systèmes ––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––– 42 4.5.1 Parallélisme –––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––– 42 4.5.2 Synchronisation ––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––– 43 4.5.3 Partage de ressources ––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––– 44 4.5.4 Mémorisation ––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––– 44 4.6 Exercices –––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––– 45 Chapitre 05 : Chaînes de Markov 5.1 Introduction –––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––– 47 5.2 Rappels de Probabilités ––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––– 47 5.2.1 Evénement –––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––– 47 5.2.2 Probabilité d’un Evènement ––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––– 48 5.2.3 Probabilité Conditionnelle ––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––– 48 5.2.4 Indépendance ––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––– 49 5.2.5 Variable Aléatoires –––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––– 49 5.3 Processus Stochastique –––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––– 50 5.4 Processus Markovien ––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––– 51 5.5 Chaine de Markov à temps discret ––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––– 51 5.5.1 Exemple introductif ––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––– 52 5.5.2 Définition ––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––– 53 5.5.3 Probabilités de Transition –––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––– 53 5.5.4 Représentation ––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––– 53 5.5.4.1 Un Graphe Orienté –––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––– 53 5.5.4.2 Une Matrice des Probabilités de Transition –––––––––––––––––––––––––––––––––––––––––––––––– 54 5.5.5 Probabilités d’Etats –––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––– 55 5.6 Classification des Etats –––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––– 55 5.7 Sémantique & Exécution ––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––– 57 5.7.1 Régime Transitoire –––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––– 57 5.7.2 Régime Stationnaire ––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––– 58 5.8 Chaîne de Markov Absorbante ––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––– 60 5.9 Exercices –––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––– 62 Bibliographie 64 Chapitre 01 : Chapitre 01 Modélisation & Simulation : une Introduction 1 1.1 Introduction Durant la dernière décennie, les systèmes ont connu un développement sans précédent qui s’est accompagné d’un accroissement important de leur complexité. Pour maîtriser la complexité de tels systèmes, il est nécessaire de disposer d’outils performants permettant de comprendre leurs comportements dynamiques, prédire leurs performances, d’évaluer et de comparer les différentes configurations ou stratégies opératoires et de les optimiser. Etudier un système consiste, dans la plupart des cas, à faire un ensemble de suppositions sur son fonctionnement. Ces suppositions, prennent généralement la forme de relations mathématiques ou logiques, constituent ainsi un modèle qui est utilisé comme support pour conduire des expériences afin d’évaluer et de déduire les performances du système qu’il le représente. Si les relations qui composent le modèle sont assez simples il peut être possible d'utiliser des méthodes mathématiques (telle que l'algèbre, la théorie des probabilités) pour obtenir des réponses exactes aux questions qui nous intéressent. Une telle solution s'appelle une solution analytique. Cependant, les systèmes qu'on trouve dans la réalité sont le plus souvent trop complexes pour pourvoir se prêter a une évaluation analytique, et leurs modèles doivent être étudiés au moyen de la simulation. La simulation est reconnue comme une technique puissante pour la conception et l’analyse des systèmes. En générale, elle est perçue comme un outil d’aide à la décision dont le but principal est d’étudier les performances d’un système complexe avant sa construction, ou d’évaluer les performances d’un système existant pour l’améliorer s’il y a une grand différence au niveau de performances. Dans une simulation, on utilise l'ordinateur pour évaluer numériquement un modèle dans le but d'estimer les caractéristiques souhaitées du modèle. La simulation peut être utilisée dans plusieurs domaines d'application, tels que : − Systèmes informatiques et télécommunications • Etude des comportements des systèmes d’exploitation • Evaluation de protocoles de gestion des transactions de bases de données, • Etude de la file d’attente mémoire d’un serveur, • Etude des comportements des utilisateurs, • Conception et dimensionnement de hubs. − Systèmes de flux de production ou de fabrication • Equilibrage de lignes d’assemblage, • Conception de systèmes de transfert entre des postes, • Dimensionnement des stocks d’un atelier, • Comparaison de pilotage, Chapitre 01 Modélisation & Simulation : une Introduction 2 • Evaluation de la charge prévisionnelle, • Etude de la synchronisation entre les réceptions des pièces et l’assemblage. − Systèmes de services • Etude de transactions bancaires, • Gestion de restaurants, • Comparaisons de politiques de maintenance des avions. − Systèmes de transport et Flux logistiques • Conception et dimensionnement d’entrepôts, • Dimensionnement d’une flotte de camions, • Etude de procédures de contrôle des flux de véhicules en circulation. − Les systèmes naturels (biologiques, écologiques,...) 1.2 Notion de Système Le terme système couvre un large champ d’application, car il peut être utilisé dans de nombreux domaines. Il existe de nombreuses définitions qui lui ont été attribuées dans la littérature. En voici une liste non exhaustive : Í Ensemble de composants reliés entre eux. Í Combinaison de parties qui se coordonnent, pour concourir à un résultat de manière à former un ensemble (Larousse). Í Ensemble d'éléments interagissant entre eux selon certains principes ou règles. Í Ensemble d’éléments matériels ou immatériels en interaction, organisés pour l’accomplissement d’une certaine mission. Le plus important ce n’est pas d’énoncer une définition précise du terme mais d’essayer de faire ressortir les mots clés qui semblent bien caractériser la notion de système. De là, on peut dire qu’un système est caractérisé par : ¾ C’est un tout composé de parties ordonnées. ¾ Chaque partie a ses lois et une certaine indépendance. ¾ Les parties ont des liens ou relations entre elles pour atteindre un but. ¾ Cet ensemble change au cours du temps. ¾ Il est influencé par le milieu dans lequel il existe et qui réagit sur lui. ¾ L’ensemble est le plus souvent soumis à des contraintes. Ces caractéristiques font ressortir qu’un système est déterminé par : Chapitre 01 Modélisation & Simulation : une Introduction 3 9 La connaissance de sa frontière, c'est-à-dire le critère d'appartenance au système déterminant si une entité appartient au système ou fait au contraire partie de son environnement. 9 La connaissance de ses interactions avec son environnement. 9 La connaissance de ses parties ou composants (la nature de ses éléments constitutifs). 9 La connaissance des lois propres de chaque composant. 9 La connaissance des lois d’interaction qui déterminent son but. Chaque système est influencé par son environnement. Un système peut être ouvert, fermé, ou isolé selon son degré d’interaction avec son environnement. L’identification des frontières du système avec son environnement (son milieu) permet de délimiter la portée du système c'est-à-dire déterminer ce qui doit être à l'intérieur du système et ce qui doit rester à l’extérieur. Les relations entre un système et son environnement sont des relations de cause à effet. Certains facteurs (paramètres) externes peuvent influencer le comportement du système : ¾ Si ces facteurs contrôlent entièrement la dynamique du système, il n’y a pas d’intérêt à conduire des expérimentations avec ce système, et uploads/Science et Technologie/ simulation-amp-prototypage.pdf