Lecture outline for week 10 I. Modelling - we want to answer questions about the real world - applications in science, engineering, economics, etc. REAL WORLD ------ (abstraction) ------> MATHEMATICAL MODEL /\ | | | | | | (experiments) (analysis) | | | | | | \/ \/ REAL WORLD <----(Interpretation)------- MATHEMATICAL INTERPRETATIONS CONCLUSIONS - abstraction - we need to simplify the real world - decide what features are important for the questions asked - analysis - we analyze the model to form some mathematical conclusions - these conclusions are interpreted so that we can make statements about the real world - we perform experiments to determine whether the conclusions of our model are accurate in the real world - we often have to rework the model for we find the conclusions are not valid - classifications of a model - deterministic vs. probibalistic (stochastic) = dynamic vs. static - deterministic model - entire future behavior is exactly and explicitly determined by the present state of the system and forces acting on it - probibalistic model - the future system may be in one of several states, each state is given a probability depending on the present state of the system and all forces acting on it - random variables with probabilities used - few real world systems are truly deterministic - deterministic model is still useful for approximating the average case - dynamic model - there is an element of time in the model - static model - time is not a part of the model II. Simulation - analyzing a model can be very difficult - many problems do not have analytic solutions - Ex: Monte Carlo Integration - many functions do not have explicit integrals - ex: sin(x) / x or e^(-x^2) - used in nuclear physics - a Monte Carlo algorithm is one which may return an incorrect answer but only with low probability - Monte Carlo simulation refers to static, probibalistic simulation - let A be the area under the curve of f(x) for a<=x<=b - assume 0<=f(x)<=M for a<=x<=b - consider the rectangle bordered by x=0, y=a, x=M, y=b - the area of this rectangle is M(b-a) - the probability that a random point of this rectangle will lie in A is p = A/[M(b-a)] - to approximate p, pick N points at random and p is asymptotically close to (# points that lie in A) / N III. Dynamic Simulation - we need to keep track of time - time driven vs. event driven - time driven - an internal clock keeps track of simulated time - with each clock tick, we determine which events occur and modify the system - event driven - keep a collection of events - at each step, pull out the next event to occur, update the current simulated time to the time of the event, and modify the system - a priority queue is a good data structure - which method is better - time driven is better if an event is likely to occur with each clock tick or if we need a fine grain manipulation of the system - event driven is better if there may be long periods of time when nothing important occurs - event driven example: a graphical user interface - a state is the current state of the UI - all input to the UI, mouse movement & buttons, keyboard hits, occur as events IV. Components of a simulation - depends on the problem specification - the components are things you must consider when building a simulator - entities - objects in the model - usually implemented with structs or classes - events - what types of things are likely to occur - 3 events for every simulator - start-of-simulation, end-of-simulation - progress-report - groupings - how entities may be collected together -ex: a traffic light is grouped with an intersection - relationships - what is the relation between entities - may be permanent or temporary - ex: a car may be on a specific street - random variables - required for anything using a probability distribution - would be good to use a separate variable for each probability distribution - also beneficial if random choices are repeatable so we can run same experiment with slightly different modifications and accurately judge the affect of the modifications - strategies - often we simulate to discover affect of modifying a system - measurements - need a way to generate meaningful analysis of the simulation