Ders Planı

ISTANBUL AYDIN UNIVERSITY

CLASS 1

Lesson plan / THEORY OF COMPUTATION

Lesson Information

Course Credit	3.0
Course ECTS Credit	4.0
Teaching Language of Instruction	İngilizce
Level of Course	Bachelor's Degree, TYYÇ: Level 6, EQF-LLL: Level 6, QF-EHEA: First Cycle
Type of Course	Compulsory
Mode of Delivery	Face-to-face
Does the course require compulsory or optional work experience?	Z
Course Coordinator	Prof. Dr. RAFET AKDENİZ
Instructor (s)
Course Assistant

Purpose and Content

The aim of the course	Introduction to the Theory of Computation is a classical introduction to automata theory, formal grammars and complexity theory known collectively as the theory of computation.
Course Content	General Introduction: Languages, Grammars, Automata (Machines), The Chomsky Hierarchy, Applications. Finite State Machines, Regular Expressions, Regular Grammars, Nondeterminism, Non-regular sets, The Pumping Lemma, Decision Algorithms for Regular Sets

Learning Outcomes

Adequate knowledge in mathematics, physical sciences and the computer engineering subjects of individual branches; the ability to implement theoretical and practical knowledge in the respective areas to modeling and solving computer engineering problems.
Ability to reflect the developments in Information and Communication Technologies to the applications of Information Technology.
Ability to identify, define, formulate and solve complex computer engineering problems; ability to select and implement the appropriate analysis and modeling methods in this respect.
Ability to design experiments for analysing computer engineering problems, to conduct experiments, to collect data, to analyse and interpret the results.
Ability to design a complex informtacis system, process, device or product to meet specific requirements under realistic restrictions and conditions; ability to implement the modern design methods for this purpose.
Ability to use, choose and develop modern techniques and means required for computer engineering applications; ability to use information technologies effectively.
Ability to work effectively in interdisciplinary and multi-disciplinary teams; ability to work individually..
Knowledge of applications in business life like project management, risk management and change management; awareness about entrepreneurship, innovativeness and sustainable development.
Awareness of the necessity of lifelong learning; ability to reach information, follow the latest developments in science and technology; ability to ensure self-renewal perpetually.
Ability to communicate efficiently both in oral and written ways in Turkish; knowledge of at least one foreign language; ability to effectively prepare reports and understand written reports, prepare design and production reports, effective presentation, giving and receiving clear and understandable instructions.
Knowledge on the effects of informatics applications on health, environment and safety in terms of universal and social aspects and information about the problems of the era; awareness on the legal results of informatics solutions.
Acting in line with ethical principles, sense of professional and ethical responsibility; knowledge on the standards of engineering applications.

Weekly Course Subjects

1	Finite State Machines, Design, Non-Determinism
2	Closure Properties, Regular Expressions, Equivalence with Finite State Machines.
3	The Pumping Lemma – Proving a Language is Non-Regular, The Adversary Game, Using Closure Properties.
4	Regular Grammars, Equivalence to FSMs, Other FSM Variations, Minimization of FSM’s.
5	Decision Algorithms for Regular Sets and Undecidability
6	Context-Free Grammars, Semantic and Inductive Design, Examples, Applications.
7	Chomsky Normal Form. Three Applications.
8	Midterm
9	Pushdown Machines, Non-Determinism Adds Power, Equivalence to CFG’s.
10	The Pumping Lemma and Non-Context-Free Sets.
11	Closure Properties, DCFL’s and Decision Algorithms.
12	Turing Machines, Design.
13	Variations and Equivalence: Non-Determinism, MultiTape, Two-Way.
14	Recursive and Recursively Enumerable Sets, Undecidability.

Resources

1-Introduction to the Theory of Computation, Michael Sipser.

EUA Kurumsal Öz değerlendirme Programı İzleme Raporu