Complexity and Computational Theory
Information Systems Engineering
Institute of Natural and Applied Sciences
Second Cycle (Master's Degree)
| Course Unit Title | Course Unit Code | Type of Course Unit | Level of Course Unit | Year of Study | Semester | ECTS Credits |
|---|---|---|---|---|---|---|
| Complexity and Computational Theory | BTM552 | Elective | Master's degree | 1 | Spring | 10 |
Name of Lecturer(s)
Associate Prof. Dr. Süleyman EKEN
Research Assistant Seda BALTA
Research Assistant M.M. Enes YURTSEVER
Learning Outcomes of the Course Unit
1) To be able to distinguish the problems that can be solved and not solved in practice and theory
2) To be able to define complexity classes and list the problems in these classes
3) To be able to apply alternative calculation models to find solutions to problems
Program Competencies-Learning Outcomes Relation
| Program Competencies | ||||||||
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | ||
| Learning Outcomes | ||||||||
| 1 | No relation | Middle | No relation | No relation | No relation | No relation | No relation | |
| 2 | No relation | No relation | No relation | No relation | No relation | No relation | No relation | |
| 3 | No relation | No relation | No relation | No relation | No relation | No relation | No relation | |
Mode of Delivery
Face to Face
Prerequisites and Co-Requisites
None
Recommended Optional Programme Components
Not Required
Course Contents
Mathematical background, Finite automata: DFA, NFA, DFA = NFA, How to implement? Regular expressions: canonical languages, Regular grammars, Closedness, Pigeonhole principle, Pumping lemma, Context-Free Languages: Decomposition and Uncertainty, Decomposition Trees, Stacked automata, Pumping lemma for Context-Free Languages, Turing Machine: How to calculate?, Turing Machine types, Undecidability: Curch-Turing Thesis, Universal Turing Machine, Recursive Countble Languages, Termination Problem, Unresolved Problems, Computational Complexity: P-set, NP-set, Cook's Theorem
Weekly Schedule
1) Mathematical background2) Sonlu otomata: DFA, NFA, DFA = NFA, Nasıl gerçeklenir?
3) Finite automata: DFA, NFA, DFA = NFA, How to implement?
4) Regular expressions: canonical languages, Regular grammars, Closedness, Pigeonhole principle, Pumping lemma
5) Context-Free Languages: Decomposition and Uncertainty, Decomposition Trees, Stacked automata, Pumping lemma for Context-Free Languages
6) Context-Free Languages: Decomposition and Uncertainty, Decomposition Trees, Stacked automata, Pumping lemma for Context-Free Languages
7) Turing Machine: How to calculate? Turing Machine types
8) Turing Machine: How to calculate? Turing Machine types
9) Midterm exam
10) Undecidability: Curch-Turing Thesis, Universal Turing Machine, Recursive Countble Languages, Termination Problem, Unresolved Problems
11) Undecidability: Curch-Turing Thesis, Universal Turing Machine, Recursive Countble Languages, Termination Problem, Unresolved Problems
12) Undecidability: Curch-Turing Thesis, Universal Turing Machine, Recursive Countble Languages, Termination Problem, Unresolved Problems
13) Computational Complexity: P-set, NP-set, Cook's Theorem
14) Computational Complexity: P-set, NP-set, Cook's Theorem
15) Computational Complexity: P-set, NP-set, Cook's Theorem
16) Final exam
Recommended or Required Reading
1- Elements of the Theory of Computation, by H.R. Lewis and C.H. Papadimitriou, Prentice Hall, 1998
2- Introduction to Theory of Computation, by Michael Sipser, Thomson Course Technology, 2006.
Planned Learning Activities and Teaching Methods
1) Lecture
2) Question-Answer
3) Discussion
4) Drill and Practice
5) Self Study
6) Problem Solving
7) Project Based Learning
Assessment Methods and Criteria
Contribution of Semester Studies to Course Grade |
50% |
|||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|
|
||||||||||||
Contribution of Final Examination to Course Grade |
50% |
|||||||||||
Total | 100% | |||||||||||
Language of Instruction
Turkish
Work Placement(s)
Not Required