SUBJECT

Title

Models of computation

Type of instruction

lecture + practical

Level

master

Faculty

Faculty of Informatics

Part of degree program

Credits

Recommended in

Semester 1

Typically offered in

Autumn semester

Course description

The aim of the course is to to provide a better understanding of the concept of computation and computational modelling by presenting different computational models. We discuss basic classical models as finite automata, pushdown automata, Turing machines and their variants (for example, register machines), partial recursive functions, random access machines, circuits, cellular automata, Petri nets. We also survey some emergent models of computation, as membrane systems and some models from DNA computing. We provide information on the computational power and efficiency of these constructs, examine their computational and descriptional complexity, and compare the different models with each other. We also discuss how these models can be used in solving theoretical and practical problems.

Readings

J. E. Savage, Brown University, Models of Computation, 1998. (www.cs.brown.edu/~jes/book/pdfs/ModelsOfComputation.pdf)
M. Fernandez, Models of Computation: An Introduction to Computability Theory (Undergraduate Topics in Computer Science), Springer, 2009
M. Sipser, Introduction to the Theory of Computation, 2nd edition, Thomson Course of Technology, 2006
Gh. Paun, G. Rozenberg, A. Salomaa: DNA Computing –New Computing Paradigms. Springer, 1998
Gh. Paun, Membrane Computing. An Introduction. Springer, 2002
G. Rozenberg, T. Back, J.N. Kook (eds), Handbook of Natural Computing, Springer, 2012.

Recommended literature:

J.E. Hopcroft, R. Motwani, J. D. Ullman, Introduction to Automata Theory, Languages and Computation, 2nd edition, Addison-Wesley,2001
J. Hromkovic, Theoretical Computer Science: Introduction to Automata, Computability, Complexity, Algorithmics, Randomization, Communication, and Cryptography (Texts in Theoretical Computer Science). Springer, 2007
J. Hromkovic, Algorithmic Adventures: From Knowledge to Magic. Springer, 2009
4.Gh. Paun, G. Rozenberg, A. Salomaa (eds.), The Oxford Handbook of Membrane Computing. Oxford University Press, 2010.