Important Information

• Due to urgent meetings of Prof. Pfeifer in Shanghai concerning the Shanghai lectures, the class will start on the 25th of September
• Precondition: Assessment RO 2004 passed, at least provisional.
• Registration and cancellation (Modulbuchung)

Final Examination and Exercises

• During the semester, there will be 5 exercise sheets, with a total of 100 (normalized) points (not including bonus points available in some questions).
• You are encouraged 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 in the pair.
• The final exam will take place on January 8 from 08:00 to 09:45 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. In order to be allowed to the final exam, you need to achieve at least 50% of the points from the exercises (i.e. 50 points).
• The final exam is worth 100 points, and the final grade will be based on the number of overall points, calculated as follows: overall points = exam points + 0.25 * exercise points.
• EXTRA EXERCISES: Cellular Automata, Dynamical Systems and Fractals.

Schedule

Lecture Script

• Cover page
• Table of Contents
• Chapter 1 - Introduction
• Chapter 2 - Formal Languages (Lect 2 slides)
• Chapter 3 - Automata Theory (Lect 3. slides) (Lect. 4 slides) (Lect. 5 slides)
• Chapter 4 - Markov Processes
• Chapter 5 - Logic
• Chapter 6 - Cellular Automata
• Chapter 7 - Dynamical Systems (Lect. 7 slides)
• Chapter 8 - Fractals (Lect. 6 slides)
• Chapter 9 - Graphs and Networks
• Bibliography

Literature

Suggested readings

They are available as Handapparat in the IFI library. Look for "Prof. Pfeifer Handapp." Study the books in the library or copy 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: Languages and Machines - An Introduction to the Theory of Computer Science (1991)

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" (available from within the university network)
• O. Sporns and R. Kötter (2004), "Motifs in Brain Networks"
• Buchanan (2002): Nexus, small worlds and the groundbreaking science of networks (popular science)
• Buchanan (2002): Nexus, small worlds and the groundbreaking science of networks (popular science)
• Watts, D.J., and Strogatz, S.H. (1998). Collective dynamics of 'small-world' networks. Nature, 393, June, 440-442. (the "classic")
• Guimera, R. et al. (2005). The worldwide air transporation network: Anomalous centrality, community structure, and cities' global roles. PNAS, 102, nb. 22, 7794-7799. (a nice example)
• Wang, P. Gonzalez, M.C. Barabasi, A.-L. (2009). Understanding the spreading patterns of mobile phone viruses. Science, 324, 1071-1076.

Additional Materials

Automata Theory

• Visual automata simulator: A tool for simulating, visualizing and transforming finite state automata and Turing Machines.
• Files of the "Finite State Automata" demos shown during the lecture.
• Grammar with atomic actions of the simple calculator, which can be processed with yacc, as shown in the lecture.
• ANTLRWorks: Graphical development environment for developing ANTLR grammars. Grammar file for the simple calculator.

Python

• Tutorial slides
• Code for practical exercise 2
• Code for practical exercise 3

ANTLR

• Code for flashback section of exercise 4

Fuzzy Logic

• Course Notes