Instructor:
Dr. A. Miner
Office: 233 Atanasoff Hall
Office Hours: By appointment
Lecture: MWF, 3-4, Atanasoff 217
Text: None. (References will be posted.)
The course will focus on techniques for analyzing discrete-state stochastic models, including Markov and Semi-Markov processes. Broadly speaking, topics to be covered include numerical analysis of stochastic processes, model checking of finite state machines and Markov chains, high-level formalisms to describe stochastic models (e.g., Petri nets, queuing networks), formalism-specific analysis algorithms (e.g., Petri net invariants, product-form queuing networks), approaches to handle state explosion (e.g., "symbolic" methods, partial-order reductions, approximations, bounds). Coursework will be a mixture of theory and practice, including programming of some analysis algorithms in C/C++.
Upon completion of this course, students should:
Officially, the prerequisites are ComS 331, Math 307, and Stat 330 or equivalents. These are discussed below.
Students will be expected to have programming experience in a contemporary high-level language, such as C, C++, or Java (any example code will be given in C). Students should also have a working knowledge of algorithm complexity.
Students should be comfortable working with graph algorithms and finite automata (ComS 331).
Students should be familiar with single-variable differential and integral calculus, and their discrete math analogs (difference and summation). However, it will be more important for students to have a basic, working knowledge of linear algebra (Math 307).
Students should have a working knowledge of probability, including random variables, expectation, and conditioning (Stat 330). Some of these topics will be reviewed briefly.
Homework exercises will be assigned regularly. These will include programming assignments, mathematical exercises, and applications. Problem sets are due by 11:59 pm on their due date, subject to a 10% penalty per day late. Students should submit hardcopy solution summaries (see below) and electronic complete solutions (including source code as appropriate).
Problem sets will represent about 40% of your grade.
There will be a midterm take-home exam, worth about 30% of your grade. This will be due at the precise time specified on the exam, and will not be accepted late without prior permission of the instructor.
Students may opt either for a take-home final exam, or a semester-long research project (requiring a written report) on a topic to be developed with the instructor. This will be due at the University-scheduled final exam time, and is worth about 30% of your grade. This will not be accepted late without prior permission of the instructor.
Solutions to problem sets and exam questions consist of two parts.
Hardcopy (written) solutions should consist of a self-contained explanation of your solution, complete with an overview of mathematical derivations (if necessary), algorithm development (if necessary), and/or specification models. The other student viewpoint is a guide to the level of explanation expected for written solutions: another student in the class, who didn't know how to do the exercise/question, should be able to read your solution and learn a correct answer, without asking questions. Solutions may be typeset or neatly hand-written. My personal preference is to use LaTeX as it produces excellent quality with minimal effort, especially for equations. However, content is much more important than style. Point(s) will be deducted for incomplete or poorly-written solutions. An example solution is provided below for illustration.
In addition to written solutions, you must submit a complete solution electronically. Think of this as the appendix to your written solution, containing things like source code and raw data as appropriate. This is necessary for me to replicate your results and check for errors.
This is a tentative schedule of lecture topics. Relevant materials (e.g., lecture notes or suggested reading) will be posted here.
| 8-10 January: | Syllabus and Introduction | intro.pdf |
|---|---|---|
| 10 January: | Review of probability | prob-review.pdf |
| 12, 17, 19 January: | Review of random variables | rvs-review.pdf |
| 22 January: | Discrete-time Markov chains | dtmc-intro.pdf |
| 24 January: | Matrix storage | mc-storage.pdf |
| 26 January: | DTMC properties | dtmc-props.pdf |
| 29 January: | Ergodic DTMCs | dtmc-ergodic.pdf |
| 31 January, 2 February: | Absorbing DTMCs | dtmc-absorb.pdf |
| 5, 7 February: | Solving linear systems | linear.pdf |
| 9 February: | DTMCs in general | dtmc-general.pdf |
| 12 February: | Continuous-time Markov chains | ctmc-intro.pdf |
| 14, 16, 19 February: | Analysis of CTMCs | ctmc-unif.pdf |
| 21 February: | Smart (software) | Example test files: oz_smart.txt bd_smart.txt |
| 23, 26, 28 February, 2 March: | CTL model checking | ctl-fsm.pdf |
| 5, 7, 9, 21 March: | Model checking Markov chains | csl-mcs.pdf |
| 23, 26 March: | Petri nets | pn-intro.pdf |
| 28, 30 March: | Reachability | pn-reach.pdf |
| 2, 4, 6, 9, 11, 13 April: | Stochastic Petri Nets | spns.pdf |
| 16 April: | Infinite Markov Chains | |
| 18, 20, 23 April: | Decision Diagrams |
| Due 22 January: | Homework 1 | |||||||
|---|---|---|---|---|---|---|---|---|
| Due 29 January: | Homework 2 | |||||||
| tiny.dtmc | oz.dtmc | univ.dtmc | loops.dtmc | |||||
| tiny.out | oz.out | univ.out | loops.out | |||||
| Due 5 February: | Homework 3 | |||||||
| Due 12 February: | Homework 4 | |||||||
| two.dtmc | oz.dtmc | univ.dtmc | absorb.dtmc | medium.dtmc | 5phils.dtmc | kan3.dtmc.gz | ||
| two.out | oz.out | univ.out | absorb.out | medium.out | 5phils.out | kan3.out.gz | ||
| Due 19 February: | Homework 5 | |||||||
| Due 26 February: | Homework 6 | |||||||
| oz.dtmc | tiny.ctmc | univ.dtmc | unif.ctmc | birthdeath.ctmc | 5phils.ctmc.gz | fms5.ctmc.gz | ||
| oz.out | tiny.out | univ.out | unif.out | birthdeath.out | 5phils.out | fms5.out | ||
| Due 2 March: | Homework 7 | |||||||
| Due 26 March: | Homework 8 | |||||||
| oz.dtmc | tiny.ctmc | univ.dtmc | unif.ctmc | 2comm1.ctmc | 2comm2.ctmc | 5phils.ctmc | ||
| oz.out | tiny.out | univ.out | unif.out | 2comm1.out | 2comm2.out | 5phils.out | ||
| Due 9 April: | Homework 9 | |||||||
| Due 16 April: | Homework 10 | |||||||
| fork.spn | sqf.spn | |||||||
| fork.out | sqf.out |
Last updated $Date: 2007-04-18 14:47:43 -0500 (Wed, 18 Apr 2007) $