Formal Methods for Computer Science II
| Module: | BINF2100 |
| Type: | Lecture with Exercises |
| ECTS: | 6 points |
| Lecture: | Friday, 08:30-12:00 |
| Venue: | BIN 2.A.01 |
| Lecturers: | Prof. Rolf Pfeifer, Dr. Rudolf Füchslin |
| Target audience: | BSc/3+ |
| Precondition: | Assessment RO 2004 passed, at least provisional |
| Language: | English |
| Assessment: | Exercises & written exam. Exam date: Friday, 10.01.2014, 8:00 - 10:00 |
| Assistants: | Qian Zhao, Konstantinos Dermitzakis, Tobias Klauser |
News
- 09.01.2014: The final exam will take place tomorrow Friday, 10 January 2014, from 08:00 to 10:00 am in BIN 0.K.02. The exam starts at 8:00 sharp! So be there a couple of minutes in advance. The only things you are allowed to take with you are a pen, your student ID card and a dictionary.
- 20.12.2013: The solution sheet for exercise 5 and the final list with exercise points have been uploaded. If you want to fetch your exercise corrections, please send an e-mail to Tobias.
- 13.12.2013: The slides for lecture 13 on Morphological Computing have been uploaded.
- 06.12.2013: The solution sheet for exercise 4 and the updated list with exercise points have been uploaded.
- 02.12.2013: The slides of Helmut Hauser's lecture on Reservoir Computing are now online.
- 29.11.2013: Exercise 5 and the links to the demos shown in today's class have been added to the website. An errata for the lecture script has also been added.
- 28.11.2013: The slides for Graphs & Network II and II have been uploaded.
- 22.11.2013: The solution for exercise 3 are online. There is now also a List with exercise points up to exercise 3.
- 20.11.2013: The slides on Fuzzy Logic (lecture 9) and Fractals/L-Systems (lecture 10) have been uploaded.
- 08.11.2013: The slides for lecture 8 and exercise sheet 4 are online.
- 01.11.2013: Please note that the lecture schedule was slightly changed. As a consequence, the hand out/in dates for exercise 5 were moved forward by one week.
- 01.11.2013: Slides for lecture 7 are online.
- 31.10.2013: The solution sheet, an example solution for the programming task and accompanying correction notes for exercise 2 have been uploaded. Exercise 2 will be handed out and discussed on 1 November 2013.
- 25.10.2013: Exercise 3 and corresponding materials have been uploaded.
- 18.10.2013: The solution to exercise 1 is online.
- 17.10.2013: The slides for lecture 5 & 6 are online.
- 10.10.2013: Exercise 2 and the materials for the Python tutorial are online.
- 09.10.2013: The slides for lecture 4 are online.
- 04.10.2013: The slides for lecture 3 and for the ANTLR demo are online.
- 27.09.2013: The slides for lecture 2 and exercise 1 are online.
- 20.09.2013: The corrected slides for lecture 1 are online.
- 09.09.2013: Lecture script is online.
- 03.09.2013: Tentative schedule and lecture information is online.
Final Examination and Exercises
- During the semester, there will be 5 exercise sheets, with a total of 100 (normalized) points.
- You are allowed to do the exercises in pairs. If you choose to do them in pairs, you are required to submit only one answer sheet per pair, stating clearly each student's name on the answer sheet.
- In order to be eligible for the final exam, you need to achieve at least 50% of the points from the exercises.
- The final exam will take place on Friday, 10 January 2014, from 08:00 to 10:00 am in BIN 0.K.02. The exam starts at 8:00 sharp! So be there a couple of minutes in advance. The only things you are allowed to take with you are a pen and a dictionary.
- Below you can download a list with the current exercise points (currently up to and including exercise 4). If you don't find yourself on the list or spot any error, please send an e-mail to Tobias.
Schedule
| Date | Topic | Hand out | Hand in |
|---|---|---|---|
| 20 September | Introduction, Formal Languages I | ||
| 27 September | Formal Languages II | ||
| 4 October | Automata Theory I | ||
| 11 October | Automata Theory II | Exercise 1 | |
| 18 October | Logic I | ||
| 25 October | Logic II | Exercise 2 | |
| 1 November | Cellular automata | ||
| 8 November | Dynamical systems / Markov models / Hidden Markov models | Exercise 3 | |
| 15 November | Fuzzy logic and other kinds of logics | ||
| 22 November | Fractals / Reservoir computing | ||
| 29 November | Graphs & Networks I | Exercise 4 | |
| 6 December | Graphs & Networks II | ||
| 13 December | Morphological computation / Alternative models of computation | Exercise 5 | |
| 20 December | Wrap-up / Final discussion |
Lecture Script
Errata
The following list contains corrections for errors that where discovered in the lecture script. If you encounter additional errors, please send an e-mail to Tobias.
| Page 3-16 | In example 3.7, there is a semicolon (;) missing after the number rule. |
| Page 4-3 | In formula for the elements of the transition matrix the indices for column and row are switched. The correct formula should read pij = P(Xn = i | Xn-1 = j) instead of pij = P(Xn = j | Xn-1 = i). |
| Page 4-11 | The numbers for (R,S) and (S,S) in the lower right box are wrong. The correct values are (R,S) 0.0063 and (S,S) 0.0648. |
| Page 8-16 | The entries for the commands + and - are switched in Table 8.1. The correct actions are: + turn left and - turn right |
| Page 9-7 | The formula for the maximum number of edges mmax should read mmax = n(n-1) for a directed graph (a), and mmax = ½ n(n-1) for an undirected graph (b). |
Lecture Slides
The complete set of lecture slides will be uploaded in the course of the semester.
Literature
Suggested books and articles
All books are available as Handapparat in the IFI library. Look for "Prof. Pfeifer Handapparat". Study the books in the library or copy the relevant parts.
Automata theory and languages:
- J. E. Hopcroft, R. Motwani and J. D. Ullmann (2003), Introduction to Automata Theory, Languages, and Computation, 2nd Edition
- T.A. Sudkamp (1991), Languages and Machines - An Introduction to the Theory of Computer Science
Logic, models of computation:
- Papadimitriou (1995), Computational complexity, Addison Wesley
- Rechenberg and Pomberger (2002), Informatik-Handbuch, 3. Auflage
Recursion, fractals and chaos:
- Flake (1998), The Computational Beauty of Nature, MIT Press
Graphs and networks:
- M. E. J. Newman (2003), The structure and function of complex networks
- R. Milo et al. (2002), Network Motifs: Simple Building Blocks of Complex Networks. Science, 298, October, 824-827. (available from within the university network)
- O. Sporns and R. Kötter (2004), "Motifs in Brain Networks"
- O. Sporns (2011), Networks of the Brain, Cambridge, Mass.: MIT Press.
- M.E.J. Newman (2010), Networks. An introduction. Oxford University Press.
- D.J. Watts, and S.H. Strogatz (1998), Collective dynamics of 'small-world' networks. Nature, 393, June, 440-442. (the "classic", available from within the university network)
- R. Guimera et al. (2005), The worldwide air transportation network: Anomalous centrality, community structure, and cities' global roles. PNAS, 102, nb. 22, 7794-7799. (a nice example)
- P. Wang, M.C. González, C.A. Hidalgo, A.-L. Barabási (2009), Understanding the spreading patterns of mobile phone viruses. Science, 324, 1071-1076.
Demonstrations shown in class
Links and additional information to the demos shown in class will be published here.