• During the semester, there will be 5 exercise sheets, with a total of 100 (normalized) points.
• 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 Friday, 13 January 2012, 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. In order to be allowed to the final exam, you need to achieve at least 50% of the points from the exercises (i.e. 45.5 points).
• The updated list of points gathered in exercises 1 to 5 is available here.

Schedule

These are the documents from last year. We will upload corrected versions in the course of the semester.

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

Lecture Slides

(this year's slides will be uploaded in the course of the semester)

Formal Languages I
Formal Languages II
Automata Theory I
Automata Theory II
Cellular Automata and Dynamical Systems
Dynamical Systems and Markov Models
Logic I and II
Morphological computation: 1-84, 85-170
Fuzzy Logic and Fractals
Network Theory 1
Network  Theory 2 (the network theory slide sets seem to render improperly on some platforms. If this is the case, please try this link.)

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.