| CMU 15-671 | ||
| ||
| Garlan |
| Who | e-mail address | Office, Phone |
Office Hours (or by appointment) |
|
Instructor |
David Garlan | garlan@cs.cmu.edu | WeH 8020 (x8-5056) |
Mon 12:00-1:00 |
Teaching Assistant |
Shawn Hurley | shawnh@cs.cmu.edu | WeH 4615-4 (x8-3759) |
Fri 10:30-11:30 |
Secretary |
Heather Marko | heatherm@cs.cmu.edu | WeH 8120, (x8-2568) |
Scientific foundations for software engineering depend on the use of precise, abstract models and logics for characterizing and reasoning about properties of software systems. There are a number of basic models and logics that over time have proven to be particularly important and pervasive in the study of software systems. This course is concerned with that body of knowledge. It considers many of the standard models for representing sequential and concurrent systems, such as state machines, algebras and traces. It shows how different logics can be used to specify properties of software systems, such as functional correctness, deadlock freedom, and internal consistency. Concepts such as composition mechanisms, abstraction relations, invariants, non-determinism, inductive and denotational descriptions are recurrent themes throughout the course.
By the end of the course you should be able to understand the strengths and weaknesses of certain models and logics, including state machines, algebraic and trace models, and temporal logics. You should be able to apply this understanding to select and describe abstract formal models for certain classes of systems. Further, you should be able to reason formally about the elementary properties of modeled systems.
Lectures. Class meet Monday & Wednesday, 10:30-11:50 am, in Doherty 1211.
Computing. Some of the assignments may make use of tools that are part of the SCS software engineering environment. You will need an account on an SCS SunOS machine to use these tools. If you are an MSE student you will already have such an account. Other students should see the instructor after the first class to get an application form. There are a set of documents that describe the MSE tool facilities.
On-line materials. Most of our course materials will be available electronically via the Web. To access this material point your favorite web browser to
There is also a class afs directory: /afs/cs/academic/class/15671-f97. It will contain various templates and documents that can be helpful in completing your homework.
Communication. We have set up three mechanisms for out-of-class interaction.
1. The Course Bulletin Board. We will use cmu.cs.class.cs671 to post questions/answers about homework and lectures. So you should plan to read it regularly. Feel free to use it yourself to post about topics of general interest for the other students.
2. Office Hours: The instructor and the TA has weekly office hours, listed above.
3. Email: We welcome email about the course at any time.
Readings. Most lectures will have a reading assignment
that we expect you to complete before you come to
class. Many of the reading assignments will be drawn from the
the required textbook for the course: An Introduction
to Formal Specification and Z, by Potter, Sinclair, Till [PST].
Additionally, the course has an optional reference book: The
Z Notation: A Reference Manual, Second Edition, by J. M.
Spivey. Some readings are in the form of handouts to supplement
some lectures; other additional readings are technical
papers. These will be distributed as needed throughout
the course.
Homeworks and Lab Exercises. The course is organized around
(roughly) weekly homeworks. The purpose of the assignments is
to give you practice in using the models and logics of the course.
In some cases where a model is supported by tools we may also
assign one or more ungraded lab exercises. These are intended
to give you practice in using the tools before you have to apply
them on the homework problems. We encourage you to discuss your
homework with other students, but the final write-up must be your
own work.
Homeworks will be graded on a pass/fail basis. Occasionally,
we will take special note of a homework that is exceptionally
well done. Homework assignments will typically be assigned on
a Monday and due at the beginning of class a week later. To give
you the most opportunities to learn from the homework assignments,
we will allow you to redo a homework that didn't receive a passing
grade. A redone homework must be turned in at the class following
the one on which it is handed back.
Extra copies of handout materials. Extra copies of lecture
slides, handouts, homework assignments, etc. will be available
from Heather Marko, WeH 8120 and in the shelves next to the door
to WeH 4615.
Exams. There will be a (take-home) mid-term (handed
out October 11, due October 13) and a (in-class) final examination.
Homework Presentations. For some homework assignments we
will ask students to present their results on the day it is due.
The purpose of this is to give the presenter practice at explaining
a solution to others and to give the rest of the class a chance
to see how someone else solved the problem. These presentations
will be assigned on a rotating basis, as necessary and will be
ungraded.
Grading. The course grade will be determined as a combination
of four factors: homework exercises (50%), midterm exam (15%)
final exam (25%), instructorsí judgment (10%).
(Go to the current version of the syllabus with links)
Finally, there a number of additional books that will be put on
reserve. These are noted in References at the end of this document.
Schedule
| # | Date | Topic | Subtopic | Reading | Homework |
| 1 | M 8/25 | Introduction | Course info; whatís a model? | ||
| 2 | W 8/27 | Foundations | Logic | [Handout 1, 1-2] | |
| 3 | *W 9/3 | Sets, Relations, Functions | [4.1-3,5] | HW 1 | |
| 4 | M 9/8 | Proof Techniques I | [Handout 2, 9.5-6] | HW 2 | |
| 5 | W 9/10 | Proof Techniques II | [Handout 3,4] | ||
| 6 | M 9/15 | State Machines | Basic concepts | [Handout 5] | HW 3 |
| 7 | W 9/17 | Variations | [Handout 6] | ||
| 8 | M 9/22 | Reasoning | [Handout 7] | HW 4 | |
| 9 | W 9/24 | Statecharts | [Ha87] | ||
| 10 | M 9/29 | Z | Introduction to Z | [4.4-6,130-155] | HW 5 |
| 11 | W 10/1 | Reasoning about Z Specs | [7-8(skim),6.5.8,9.1-4] | ||
| 12 | M 10/6 | Examples | [Handout 8,DG90] | HW 6 | |
| 13 | W 10/8 | Abstraction in Z | [Handouts 9-11, 10] | ||
| Midterm out | |||||
| 14 | *W 10/15 | Larch | Algebras | [SEM, Ch 11] | |
| 15 | M 10/20 | Interfaces | [GH93] | HW 7 | |
| 16 | W 10/22 | Concurrency | Introduction to Concurrency | [AS83, Handouts 12-13] | |
| 17 | M 10/27 | Petri Nets | Introduction to Petri Nets | [Pet77] | HW 8 |
| 18 | W 10/29 | Reasoning about Petri Nets | [Jen91] | ||
| 19 | M 11/3 | CSP | Introduction to CSP | [] | HW 9 |
| 20 | W 11/5 | Reasoning with CSP | [] | ||
| 21 | M 11/10 | Nondeterminism | [] | HW 10 | |
| 22 | W 11/12 | Case Study | [AGI97, Handout13] | ||
| 23 | M 11/17 | Temporal Logic | Linear Temporal Logic | [] | HW 11 |
| 24 | W 11/19 | Other Temporal Logic | [] | ||
| 25 | M 11/24 | Temporal Logic of Actions | [] | HW 12 | |
| 26 | *M 12/1 | Applications | [12] | HW 13 | |
| 27 | W 12/3 | Review for Final |
Bold refers to PST
* marks classes that follow a holiday