Featured Programs
Experiential Learning Opportunities
Advanced Computation Theory
Engineering & Social Sciences Program
Madrid, Spain
Dates: 1/18/24 - 6/5/24
Advanced Computation Theory
OVERVIEW
CEA CAPA Partner Institution: Universidad Carlos III de Madrid
Location: Madrid, Spain
Primary Subject Area: Mathematics
Instruction in: English
Course Code: 18294
Transcript Source: Partner Institution
Course Details: Level 400
Recommended Semester Credits: 3
Contact Hours: 42
Prerequisites: Discrete Mathematics (Course 1 - Semester 2)
Theory of Automata and Formal Languages (Course 2 - Semester 1)
DESCRIPTION
Description of contents: programme
Relevant contents:
1.- Cost of computational processes
2.- Recursive algorithms complexity
3.- Introduction to computability theory
4.- Introduction to computational complexity theory
5.- Spatial complexity
6.- Kolmogorov complexity
7.- Computation models
8.- Probabilistic algorithms
Programme:
1. Computational Cost of Algorithms.
1.1 Computational Complexity and Computational Cost.
1.2 Computational Cost of Structured Programs
1.3 Computational Cost of Recursive Programs
1.4 Probabilistic Analysis
2. Introduction to Computability Theory
2.1 Definition of Problem. Decision Problems
2.2 Turing Machines and Decidability
2.3 Computability and Decidability
3. Introduction to Complexity Theory
3.1 Problem Reduction
3.2 Classes P, NP and NP-Complete.
3.3 Classes PSpace, NPSpace.
3.3 Classes NP-Hard, Exp, CoP, CoNP
4. Models of Computation
4.1 Turing Machines (Multi-tape, Non deterministic)
4.2 Cellular Automata
4.3 Lindenmayer Systems
Relevant contents:
1.- Cost of computational processes
2.- Recursive algorithms complexity
3.- Introduction to computability theory
4.- Introduction to computational complexity theory
5.- Spatial complexity
6.- Kolmogorov complexity
7.- Computation models
8.- Probabilistic algorithms
Programme:
1. Computational Cost of Algorithms.
1.1 Computational Complexity and Computational Cost.
1.2 Computational Cost of Structured Programs
1.3 Computational Cost of Recursive Programs
1.4 Probabilistic Analysis
2. Introduction to Computability Theory
2.1 Definition of Problem. Decision Problems
2.2 Turing Machines and Decidability
2.3 Computability and Decidability
3. Introduction to Complexity Theory
3.1 Problem Reduction
3.2 Classes P, NP and NP-Complete.
3.3 Classes PSpace, NPSpace.
3.3 Classes NP-Hard, Exp, CoP, CoNP
4. Models of Computation
4.1 Turing Machines (Multi-tape, Non deterministic)
4.2 Cellular Automata
4.3 Lindenmayer Systems