Computing by Graph Transformation (GRA) 2010/1
Workload - Private Study - Assessment - Description - Learning Outcomes - Content - Teaching Materials - Recommended Books
| Module Code | 0630400 |
|---|---|
| Lecturers | Detlef Plump |
| Taken By | CS 3, CS/Math 3, MMath 3, CSESE 3, CSSE 3, MEng CSSE 3, MEng CSESE 3, MMath 4 |
| Number of Credits | 10 |
| Part | B |
| Teaching | Spr/2-10 |
| Closed Assessment |
[100%] Summer Week 7, 1.50 hours |
Module Prerequisites
Prerequisite knowledge
Students entering this module should be comfortable with basic mathematical concepts such as sets, relations, functions and proofs. These concepts are taught in ICM, MCS and, for CS/M students, in Maths modules. It is helpful, but not strictly necessary, to be familiar with basic concepts of grammars and formal languages as taught in MCS and TOC.
Workload
- Lectures: 18 x 1hr
- Problem Classes: 5 x 1hr
- Practicals: 4 x 1hr
- Private Study: 50hrs
- Assessment: 23hrs
Problem classes and practicals are with tuition, they include pencil-and-paper exercises and (at a later stage) programming exercises in the graph programming language GP. The time shown for assessment includes revision to prepare for the exam.
Private Study
"Private study" comprises unsupervised work on exercises, reviewing lectures and reading articles and textbooks.
Assessment
Closed Assessment
- Summer Week 7, 1.50 hours
An unseen paper worth 50 marks. Candidates are required to answer any two questions from three.
Formative Feedback
Problem classes and practicals are for work on weekly exercises. Solutions are handed in, marked and returned. Additionally, students get oral feedback during the problem classes and practicals.
Description
Graphs are ubiquitous in computer science, they represent and visualise relationships between objects of all kinds. Examples include circuit diagrams, flow diagrams, syntax trees, pointer structures, entity-relationship diagrams, UML diagrams, various forms of networks, etc. Graph transformation is about the dynamic manipulation of graphs by rules, combining the strengths of graphs and rules into a single computational model. Transformation rules which change graphs locally allow a declarative way of computing, with simple syntax and semantics. This course introduces the foundations of computing by graph transformation, and the principles of rule-based programming in domains of graph-like structures.
Learning Outcomes
As a result of studying this module students should: (1) be familiar with the main concepts and results of graph transformation; (2) be able to recognise problems in various areas of computer science as suitable for applying graph transformation; (3) be able to write graph programs for solving problems in domains of graph-like structures.
Content
Why graph transformation? Graphs, rules and derivations. Graph transformation systems, graph grammars and graph languages. Properties of derivations: independence and parallelism, critical pairs and confluence. A complete and minimal programming language for graph transformation. Graph programming in GP. Case studies in graph algorithms.
Teaching Materials
Lecture slides, exercises with solutions, and relevant research papers will be available from the module web page.
Recommended Books
| Rating | Author | Title | Publisher | Year |
|---|---|---|---|---|
| ** | H. Ehrig, K. Ehrig, U. Prange and G. Taentzer | Fundamentals of Algebraic Graph Transformation | Springer-Verlag | 2006 |
| ++ | G. Rozenberg (ed.) | Handbook of Graph Grammars and Computing by Graph Transformation. Volume 1: Foundations | World Scientific | 1997 |
| ++ | H. Ehrig, G. Engels, H.-J. Kreowski and G. Rozenberg (eds.) | Handbook of Graph Grammars and Computing by Graph Transformation. Volume 2: Applications, Languages and Tools | World Scientific | 1999 |
| ++ | H. Ehrig, H.-J. Kreowski, U. Montanari and G. Rozenberg (eds.) | Handbook of Graph Grammars and Computing by Graph Transformation. Volume 3: Concurrency, Parallelism and Distribution | World Scientific | 1999 |
Last updated: 1st June 2011