Computational Modeling
Fall 2005
 
For today: catching up and optional reading

Today:

1) computer simulation

2) discrete event simulation

3) the heap data structure


Outline of the next couple of weeks:

1) discrete event simulation

2) agent-based simulation

3) flocks, anthills, etc.

4) emergent properties 


The Axes of Simulation
----------------------

(more than one axis, not more than one axe)

1) Continuous and discrete

Continuous models are usually described by differential equations
and solved analytically or numerically.

See MATH 3150 Numerical Methods and Scientific Computing.

Discrete models are usually discrete in space and time.

Example: a train leaves Eliot Station toward Newton Highlands.

A continuous model might simulate the acceleration of the train
and integrate to compute velocity and position as a function of time.

A discrete model might simulate two events (train leaves Eliot,
train arrives at Newton Highlands) each with a time stamp.


2) Deterministic and stochastic

Most models of physical systems are deterministic (which leads
people to conclude that physical systems are deterministic).

So why put randomness into a model?

   a) efficiency (rather than follow individual molecules/people/etc,
      describe populations with random variables)

   b) scope (events from outside the system are modeled as random)

   c) accuracy (the system is truly non-deterministic)


3) Equation-based and agent-based

Equation based systems tend to be populated by identical things
without volition.

Agent-based systems tend to be populated by ... you figure it out.


An implementation detail
------------------------

Continuous models often use time-slicing.

Discrete event models often use event queues.

1. Start with one or more initial events in the queue.

2. Remove the event with the earliest time stamp.

3. Process the event:

   a. update the global system clock

   b. update the state of the system and agents

   c. perform measurement tasks

   d. check for an end condition

   e. add new events to the queue

4. Go to step (2)


Data structures for event queues
--------------------------------

What are the operations we need to perform?

a) add events

b) remove and return the event with the earliest time stamp


Options:

1) unsorted collection

   add is O(1), popmin is O(n)

2) sorted sequence

   add is O(n), popmin is O(1)

3) heap

   add and popmin are O(log n)


How do we get there?

1) think of a tree

2) take away the tree

3) what's left is a heap!



Think of a tree
---------------

1) heap property

2) adding and sifting up

3) removing and sifting down

Note: order of growth depends on bushiness!


Take away the tree
------------------

Storing and updating references takes space and time.

For the operations we need to perform, we can avoid
references and use indices.


See: the heapq module, and the Python Cookbook recipe for
     wrapping the heapq module.