07-01-2011, 12:22 PM
[attachment=7989]
What is ToC?
What can or cannot be computed efficiently with given resources
Can it be computed?- Computability Theory
Can it be computed quickly? – Complexity Theory
Computability Theory
Problems
Solvable
Not solvable
Complexity Theory
Computationally Hard Problems
Computationally Easy Problems
Defining ToC
Fundamental ideas & Models on Computing
The branch of computer science and mathematics that deals with how efficiently problems can be solved on a model of computation, using an algorithm.
Computational Model
Automata
Alphabets
Strings
Empty string
Length of a string
Powers of an alphabet
Concatenation of strings
Languages
