The use of discrete mathematics is becoming increasingly more wide-spread in applied mathematics. The motivation for this course is the space and time discrete dynamical system models used in simulation and analysis. Application examples include traffic models of entire cities (Transims), disease dynamics in social networks (Episims), and models of biological systems such as the immune system (Celada-Seiden model).
This course is about the mathematical structures and properties of the discrete dynamical systems used in the simulation models above. Through the framework of sequential dynamical systems and generalized cellular automata the course gives a thorough introduction to mathematical results and techniques that can be used to analyze these systems. In contrast to the continuous dynamical systems you may have seen in other courses, the techniques in this course are based on abstract algebra, combinatorics and graph theory. The course offers a great opportunity to learn how all these areas can be combined to analyze finite dynamical system.
Instructor: | Henning S. Mortveit | ||
Office I: | Corporate Research Center, Building XV, Room 1111 | ||
Office II: | McBryde 419 | ||
Phone: | (540) 231-5327 | ||
Email: | hmortvei@math.vt.edu | ||
Web: | 4983-15748.html |
Time and Place: 9:30-10:45AM TR, McBryde Hall 207
Office Hours: Tuesdays and Thursdays 11:00-12:00 (McBryde 419).
Practical information (subject to change):
Assignments: There course has four written assignments. Additionally there are two computer assignments that can be applied as extra credit.
Text/course material: The course has no required text and is based on lecture notes that will be made available from this page or that will be distributed by email to the students. The following is a list of references that may be helpful as supplementary material. Feel free to ask me about additional references.
Exams, Tests, Assignments, and Grading:
Attendance: Will be taken, and will be kept for Mathematics Department records. It may be applied as extra credit.
Prerequisites:
or equivalents courses, or permission from the instructor. The two last courses can be taken in the same semester as this course.
Having taken 3134 Applied Combinatorics and Graph or some other course in combinatorics or graph theory may be helpful, but is not necessary.
Honor System. The University Honor System is in effect for in-class tests and exams.
Week | Days | Topics | Assignments/Exams |
---|---|---|---|
03 | 01/16, 01/18 | Introduction to finite dynamical systems and applications. Examples of Sequential Dynamical Systems and Cellular automata. Application examples. | |
04 | 01/23, 01/25 | Sequential Dynamical Systems and Generalized Cellular Automata. Definitions, terminology and examples. | |
05 | 01/30, 02/01 | Reversible SDS. Characterization and enumeration of fixed points. | |
06 | 02/06, 02/08 | Functional equivalence. Update graphs. Stanley's enumeration formula for acyclic orientations. | Assignment 1 due 02/06 |
07 | 02/13, 02/15 | Last week ctd. Dynamical Equivalence. Orbit graphs. Combinatorial bounds. | |
08 | 02/20, 02/22 | Last week ctd. | Assignment 2 due 02/22. |
09 | 02/27, 03/01 | Summary and examples. Midterm exam | Computer Assignment 1 due 02/27. Midterm exam 03/01 |
10 | 03/06, 03/08 | Spring break. | |
11 | 03/13, 03/15 | Dynamical equivalence continued. Applications of graph dynamical systems. | |
12 | 03/20, 03/22 | Applications of graph dynamical systems continued. Special systems (Nor, Nand, Parity). | |
13 | 03/27, 03/29 | Special systems continued. SDS with update order independent periodic points. | Computer Assignment 1 due 03/29 |
14 | 04/03, 04/05 | SDS with update order independent periodic points continued. Dynamics groups. | Assignment 3 due 04/05. |
15 | 04/10, 04/12 | Linear graph dynamical systems. | Computer assignment 2 due 04/12 |
16 | 04/17, 04/19 | Reduction of SDS through graph covering maps and examples of graph covering maps. | |
17 | 04/24, 04/26 | To be announced. | Assignment 4 due 04/24 |
18 | 05/01 | Summary | |
19 | 05/08 | Final Exam |
© Copyright 2002 – 2006, Henning S. Mortveit, all rights reserved. Some images may not display correctly in older browsers.