TÜRKÇE
ENGLISH
Information
| Unit | FACULTY OF ENGINEERING |
| COMPUTER ENGINEERING PR. (ENGLISH) | |
| Code | CEN433 |
| Name | Automata Theory |
| Term | 2015-2016 Academic Year |
| Semester | 7. Semester |
| Duration (T+A) | 3-0 (T-A) (17 Week) |
| ECTS | 3 ECTS |
| National Credit | 3 National Credit |
| Teaching Language | İngilizce |
| Level | Üniversite Dersi |
| Type | Normal |
| Label | C Compulsory |
| Mode of study | Yüz Yüze Öğretim |
| Catalog Information Coordinator | |
| Course Instructor |
Prof. Dr. UMUT ORHAN
(Güz)
(A Group)
(Ins. in Charge)
|
Course Goal / Objective
In this course, the main goal is to define the language classes in the Chomsky hierarchy in terms of grammars and automata.
Course Content
Introduction to Finite Automata, Deterministic Finite Automata, Regular Expressions, Non-Deterministic Finite Automata, Regular Languages and Regular
Course Precondition
Yok
Resources
Notes
Course Learning Outcomes
| Order | Course Learning Outcomes |
|---|---|
| LO01 | Analyze different computational methods using combinatorial methods. |
| LO02 | Apply rigorously formal mathematical methods to prove properties of languages, grammars and automata. |
| LO03 | Construct algorithms for different problems and argue about correctness on different machine models of computation. |
| LO04 | Identify limitations of some computational models and possible methods of proving them. |
| LO05 | Practice computational problems by using software tools |
Relation with Program Learning Outcome
| Order | Type | Program Learning Outcomes | Level |
|---|---|---|---|
| PLO01 | - | Has capability in the fields of mathematics, science and computer that form the foundations of engineering | |
| PLO02 | - | Identifies, formulates, and solves engineering problems, selects and applies appropriate analytical methods and modeling techniques, | |
| PLO03 | - | Analyzes a system, its component, or process and designs under realistic constraints to meet the desired requirements,gains the ability to apply the methods of modern design accordingly. | |
| PLO04 | - | Ability to use modern techniques and tools necessary for engineering practice and information technologies effectively. | |
| PLO05 | - | Ability to design and to conduct experiments, to collect data, to analyze and to interpret results | |
| PLO06 | - | Has ability to work effectively as an individual and in multi-disciplinary teams, take sresponsibility and builds self-confidence | |
| PLO07 | - | Can access information,gains the ability to do resource research and uses information resources | |
| PLO08 | - | Awareness of the requirement of lifelong learning, to follow developments in science and technology and continuous self-renewal ability | |
| PLO09 | - | Ability to communicate effectively orally and in writing, and to read and understand technical publications in at least one foreign language | |
| PLO10 | - | Professional and ethical responsibility, | |
| PLO11 | - | Awareness about project management, workplace practices, employee health, environmental and occupational safety, and the legal implications of engineering applications, | |
| PLO12 | - | Becomes aware of universal and social effects of engineering solutions and applications, entrepreneurship and innovation, and knowledge of contemporary issues |
Week Plan
| Week | Topic | Preparation | Methods |
|---|---|---|---|
| 1 | Discrete Mathematical Structures review | Reading the related chapter in lecture notes. | |
| 2 | Introduction to Finite Automata, Deterministic Finite Automata | Reading the related chapter in lecture notes. | |
| 3 | Regular Expressions, Non-Deterministic Finite Automata | Reading the related chapter in lecture notes. | |
| 4 | Context-Free Languages, Regular Languages and Regular Grammars | Reading the related chapter in lecture notes. | |
| 5 | Push-Down Automata (deterministic & non-deterministic) | Reading the related chapter in lecture notes. | |
| 6 | Context-Free and Non Context-Free Languages | Reading the related chapter in lecture notes. | |
| 7 | Review for midterm exam | Reading the related chapter in lecture notes. | |
| 8 | Midterm exam | Preparing for the exam | |
| 9 | Turing Machines, Church-Turing Thesis | Reading the related chapter in lecture notes. | |
| 10 | Non-Deterministic Turing machines, Universal Turing Machines | Reading the related chapter in lecture notes. | |
| 11 | Recursively Enumerable Languages, Chomsky Hierarchy | Reading the related chapter in lecture notes. | |
| 12 | Undecidability, Reductions and the Halting | Reading the related chapter in lecture notes. | |
| 13 | Some Computable Functions | Reading the related chapter in lecture notes. | |
| 14 | Computational Complexity & NP-Completeness | Reading the related chapter in lecture notes. | |
| 15 | Review for final exam | Reading the related chapter in lecture notes. | |
| 16 | Final exam | Preparing for the exam | |
| 17 | Final exam | Preparing for the exam |
Assessment (Exam) Methods and Criteria
| Assessment Type | Midterm / Year Impact | End of Term / End of Year Impact |
|---|---|---|
| 1. Short Exam | 20 | -4 |
| 2. Short Exam | 20 | -4 |
| 3. Short Exam | 20 | -4 |
| 1. Project / Design | 20 | -4 |
| 2. Project / Design | 20 | -4 |
| 1. Short Exam | 20 | -4 |
| 1. Project / Design | 20 | -4 |
| 2. Short Exam | 20 | -4 |
| 2. Project / Design | 20 | -4 |
| 3. Short Exam | 20 | -4 |
| General Assessment | ||
| Midterm / Year Total | 200 | -20 |
| 1. Final Exam | - | 60 |
| 1. Final Exam | - | 60 |
| Grand Total | - | 100 |
Student Workload - ECTS
| Works | Number | Time (Hour) | Workload (Hour) |
|---|---|---|---|
| Course Related Works | |||
| Class Time (Exam weeks are excluded) | 14 | 3 | 42 |
| Out of Class Study (Preliminary Work, Practice) | 14 | 3 | 42 |
| Assesment Related Works | |||
| Homeworks, Projects, Others | 5 | 8 | 40 |
| Mid-term Exams (Written, Oral, etc.) | 0 | 0 | 0 |
| Final Exam | 1 | 25 | 25 |
| Total Workload (Hour) | 149 | ||
| Total Workload / 25 (h) | 5,96 | ||
| ECTS | 3 ECTS | ||