Course Information
SemesterCourse Unit CodeCourse Unit TitleT+P+LCreditNumber of ECTS CreditsLast Updated Date
1BBM402THEORY OF COMPUTATION3+0+03606.09.2024

 
Course Details
Language of Instruction English
Level of Course Unit Bachelor's Degree
Department / Program COMPUTER ENGINEERING
Type of Program Formal Education
Type of Course Unit Elective
Course Delivery Method Face To Face
Objectives of the Course The objective of this course is to teach computability theory concepts which are important concepts of computer science discipline.
Course Content Automata theory and formal languages.
Properties of formal languages and pumping lemma for formal languages.
Church-Turing thesis, Turing machines, and models of computability theory.
Decidable and undecidable problems.
Halting problem.
Reducibility and undecidable problems of language theory.
Measuring time-complexity.
P, NP, NP-Completeness concepts and Cook-Levin theorem.
Course Methods and Techniques Lecture, Problem Solving
Prerequisites and co-requisities ( BBM102 ) and ( BBM104 )
Course Coordinator None
Name of Lecturers Associate Prof.Dr. Lale Özkahya
Assistants None
Work Placement(s) No

Recommended or Required Reading
Resources M. Sipser, "Introduction to The Theory of Computation", 2nd Edition, Course Technology, 2006.
Course Notes M. Sipser, “Introduction to The Theory of Computation”, 2nd Edition, Course Technology, 2006.


Planned Learning Activities and Teaching Methods
Activities are given in detail in the section of "Assessment Methods and Criteria" and "Workload Calculation"

Assessment Methods and Criteria
In-Term Studies Quantity Percentage
Midterm Exam 2 % 60
Final examination 1 % 40
Total
3
% 100

 
ECTS Allocated Based on Student Workload
Activities Quantity Duration Total Work Load
Course Duration 14 3 42
Hours for off-the-c.r.stud 14 5 70
Preparation for Midterm Exam 2 15 30
General Exam Preparation 1 20 20
Total Work Load   Number of ECTS Credits 5,4 162

 
Course Learning Outcomes: Upon the successful completion of this course, students will be able to:
NoLearning Outcomes
1 After completing the course, the students learn properties of formal languages and their relationships with computability theory.
2 Learn Turing machines and models of computability.
3 Learn decidable and undecidable problems.
4 Learn reducibility concept.
5 Learn time-complexity concepts.
7  
8  

 
Weekly Detailed Course Contents
WeekTopicsStudy MaterialsMaterials
1 Formal languages and introduction to computability theory.
2 Properties of regular languages and pumping lemma for regular languages.
3 Properties of context-free languages and pumping lemma for context-free languages.
4 Turing machines and models of computability.
5 Church-Turing thesis.
6 Midterm exam
7 Decidable and undecidable problems.
8 Halting problem.
9 Reducibility.
10 Undecidable problems in language theory.
11 Midterm exam
12 Measuring time-complexity.
13 P, NP and NP-completeness concepts .
14 Cook-Levin Theorem.
15 Final Exam Preparation
16 Final Exam

 
Contribution of Learning Outcomes to Programme Outcomes
P1 P2 P3 P4 P5 P6 P7 P8 P9 P10 P11 P12
All 4 4 2 3 2 2 2 3 2 2 2
C1
C2
C3
C4
C5
C7
C8

  Contribution: 1: Very Slight 2:Slight 3:Moderate 4:Significant 5:Very Significant

  
  https://bilsis.hacettepe.edu.tr/oibs/bologna/progCourseDetails.aspx?curCourse=2687428&lang=en