Bilgisayar Müh. Bölüm Binası, 1. kat, oda 107 Tel.:+90 (224) 294 2792 email: gozcan at uludag.edu.tr
18
Website:
19
Objective of the Course:
Comprehension of formal languages and vending machines, comprehension of which language cluster the problem belongs Lex and syntax analysis, comprehension of complexity
20
Contribution of the Course to Professional Development
21
Learning Outcomes:
1
Ability to understand formal language;
2
Understanding of theoretical concepts;
3
Lex and syntax analysis skills;
4
Ability to understand computational complexity;
5
Ability to grasp the Turing Machine in every direction;
22
Course Content:
Week
Theoretical
Practical
1
Languages, DFA
2
Regular Languages
3
Non Determinism
4
Properties of Regular Languages, regular expresssions
5
pumping lemma for regular languages
6
CFL and Context Free Grammars
7
Grammar normal forms, parsers
8
Midterm exam+general review
9
Push Down Automata, and its relation to CFL
10
Turing machine and its variations
11
Universal Turing machine
12
Decidable Languages / Unecidable Languages
13
Reductions for Decidability/Computational Complexity
14
Cook Theorem/NP Complete Reductions
23
Textbooks, References and/or Other Materials:
Introduction to the Theory of Computation, Michael Sipser
24
Assesment
TERM LEARNING ACTIVITIES
NUMBER
PERCENT
Midterm Exam
1
40
Quiz
0
0
Homeworks, Performances
0
0
Final Exam
1
60
Total
2
100
Contribution of Term (Year) Learning Activities to Success Grade
40
Contribution of Final Exam to Success Grade
60
Total
100
Measurement and Evaluation Techniques Used in the Course
Information
25
ECTS / WORK LOAD TABLE
Activites
NUMBER
TIME [Hour]
Total WorkLoad [Hour]
Theoretical
14
3
42
Practicals/Labs
0
0
0
Self Study and Preparation
0
0
0
Homeworks, Performances
0
0
0
Projects
0
0
0
Field Studies
0
0
0
Midtermexams
1
54
54
Others
0
0
0
Final Exams
1
54
54
Total WorkLoad
150
Total workload/ 30 hr
5
ECTS Credit of the Course
5
26
CONTRIBUTION OF LEARNING OUTCOMES TO PROGRAMME QUALIFICATIONS
