EventoWeb
Zürcher Hochschule für Angewandte Wissenschaften
Menu
Home
User Menu
Not registered
Login
[
German (Switzerland)
German (Switzerland)
] [
English
English
]
[
de
de
] [
en
en
]
Not registered
Login
EventoWeb
Kontakt zu Service Desk
Online-Dokumentation
Allgemeiner Zugriff
Module suchen
t.BA.IT.THIN.19HS (Theory of Computation)
Module: Theory of Computation
This information was generated on: 06 December 2024
No.
t.BA.IT.THIN.19HS
Title
Theory of Computation
Organised by
T CAI
Credits
4
Description
Version: 3.0 start 01 February 2022
Short description
Students learn the basic terms and concepts used in theoretical computer science. They will also understand how to build models for assessing the performance of current and future computer systems: formal languages, automata theory and computational complexity
Module coordinator
Olaf Stern, strf
Learning objectives (competencies)
Objectives
Competences
Taxonomy levels
(1) They will acquire knowledge relating to the formal languages/grammatical systems, the types of automatas which use these and the relationships between them. They will be able to design automatas for given formal languages which will accept or define these languages, as well as design languages which given automatas can recognise and define.
(2) The students will be familiar with the major approaches used to formalise concepts of computability and those used to develop algorithms. They will be aware of the equivalences between these various approaches. They will know the concepts of decidable and semidecidable problems and will be aware of the relationship between these two types of problems.
(3) The students will know the most important classes of complexity – particularly P and NP – as well as the simple notations used to describe them (o notation and omega notation). They will understand the question of whether P=NP and be aware of its significance. They will be familiar with the polynomial reduction method and be able to apply it to comparatively simple examples.
Module contents
Motivation applicable to theoretical computer science:
formal calculation models
ability to recognise fundamental principles, irrespective of the hardware or software being used
the limits applicable to automatic calculations
Formal languages / machine theory:
fundamental definitions of formal languages
regular languages, finite-state machines (DFSM, NFSM, e-NFSM)
context-independent languages, pushdown automata
(recursive languages), Turing machines (TM)
Chomsky hierarchy
Computability and algorithm concept:
computable functions. Church’s thesis
Equivalence of TMs and computers
Computability and programming languages: GOTO, while and loop programmes
The algorithm concept
Primitive recursion
Non-decidability and decidability: Ld diagonal language, Rice’s theorem, busy beavers
Semi-decidable problems: halting problem, game of life, (Collatz numbers ?)
Reduction
Complexity theory
the complexity of algorithms
O-notation (omega-notation)
Polynomial and exponential functions
P class, NP class
NP-complete, NP-hard
Polynomial time reduction
Teaching materials
- Ausführlicher Foliensatz, Ergänzungsunterlagen, Aufgabenserien mit Musterlösungen
- John E. Hopcroft, Rajeev Motwani, und Jeffrey D. Ullman:
Einführung in die Automatentheorie, Formale Sprachen und Berechenbarkeit
bzw.
Introduction to Automata Theory, Languages, and Computation
, Pearson Studium, Addison-Wesley Verlag, (auch als Taschenbuch und e-Book verfügbar), 2011 / 2013
Supplementary literature
- Detailed set of slides, supplementary documents, task series with sample solutions
- John E. Hopcroft, Rajeev Motwani, und Jeffrey D. Ullman:
Einführung in die Automatentheorie, Formale Sprachen und Berechenbarkeit
bzw.
Introduction to Automata Theory, Languages, and Computation
, Pearson Studium, Addison-Wesley Verlag, (also available as paperback book and e-Book), 2011 / 2013
Prerequisites
none
Teaching language
(X) German ( ) English
Part of International Profile
( ) Yes (X) No
Module structure
Type 2a
For more details please click on this link:
T_CL_Modulauspraegungen_SM2025
Exams
Description
Type
Form
Scope
Grade
Weighting
Graded assignments during teaching semester
excercises
written
about 9 task series
points
20%
End-of-semester exam
exam
written
grades
grading
80%
Remarks
Legal basis
The module description is part of the legal basis in addition to the general academic regulations. It is binding. During the first week of the semester a written and communicated supplement can specify the module description in more detail.
Note
Additional available versions:
2.0 start 01 February 2019
Course: Theoretische Informatik - Vorlesung
No.
t.BA.IT.THIN.19HS.V
Title
Theoretische Informatik - Vorlesung
Note
No module description is available in the system for the cut-off date of 01 August 2099.