Formal Models and Computation

Course Pre-requisites:

Undergraduate

Automata and

Computability

Theory

course or COI

Course Requirements:

Problem Sets (PSet)

Oral Reports (ORep)

Grade:

40% PSet

60% ORep

must obtained at least 60% in order to gain credit.

References:

1. Maribel Fernández, Models of Computation

An Introduction

to Computability Theory, Springer-Verlag London Limited 2009

2. John E. Savage, Models of Computation

Exploring the Power of Computing

3. Avi Wigderson,

The "P vs. NP" Problem: Efficient Computation, Internet Security, and the Limits of Human Knowledge

[A Public Lecture at IAS, Princeton University]

4. Juraj Hromkovic,

Communication Complexity and Parallel Computing, Springer Verlag, 1997

4. Gheorghe Phaun,

Introduction to Membrane Computing, Springer Verlag, 2000

[This part of the page will grow as we progress our lecture]