htw saar
Back to Main Page

Choose Module Version:


Theoretical Informatics Seminar

Module name (EN): Theoretical Informatics Seminar
Degree programme: Computer Science and Communication Systems, Master, ASPO 01.04.2016
Module code: KI848
Hours per semester week / Teaching method: 4V (4 hours per week)
ECTS credits: 6
Semester: 2
Mandatory course: no
Language of instruction:
Practice talk, talk
Curricular relevance:
KI848 Computer Science and Communication Systems, Master, ASPO 01.04.2016, semester 2, optional course, informatics specific
KIM-STI Computer Science and Communication Systems, Master, ASPO 01.10.2017, semester 2, optional course, informatics specific
PIM-STI Applied Informatics, Master, ASPO 01.10.2011, semester 2, mandatory course
PIM-STI Applied Informatics, Master, ASPO 01.10.2017, semester 2, mandatory course
60 class hours (= 45 clock hours) over a 15-week period.
The total student study time is 180 hours (equivalent to 6 ECTS credits).
There are therefore 135 hours available for class preparation and follow-up work and exam preparation.
Recommended prerequisites (modules):
Recommended as prerequisite for:
Module coordinator:
Prof. Dr. Thomas Kretschmer
Lecturer: Prof. Dr. Thomas Kretschmer

[updated 18.02.2008]
Learning outcomes:
After successfully completing this module, students will be able to independently analyze, prepare and present the content of a challenging scientific topic pertaining to theoretical computer science in an understandable way within a given period of time. In addition, they will be able to participate actively in a technical discussion and concisely summarize the lectures they have heard.

[updated 24.02.2018]
Module content:
Advanced topics pertaining to the computability theory, complexity theory and algorithms, e. g. probabilistic algorithms, alternating automata, zero-knowledge proofs, approximation algorithms.

[updated 24.02.2018]
Teaching methods/Media:
Practice talk, talk by student, discussion, summary by listeners

[updated 24.02.2018]
Recommended or required reading:
Berstel, Boasson, Carton, Fagnot: Minimization of automata,
Berstel, Perrin, Reutenauer: Codes and Automata, Cambridge University Press 2010.
Cormen, Leiserson, Rivest: Introduction to Algorithms, The MIT Press 1997.
Hopcroft, Ullman: Ullman: Einführung in die Automatentheorie, Formale Sprachen und Komplexitätstheorie, Addison-Wesley, 1994.
Moore, Christopher; Mertens, Stefan: The Nature of Computation, Oxford University Press 2011.
Motwani, Rajeev; Raghavan, Prabhakar: Randomized Algorithms, Cambridge University Press 2007.
Sipser: Introduction to the Theory of Computation, Second Edition, Thomson 2006.
Vazirani, Vijay: Approximation Algorithms, Springer 2003.
and other articles

[updated 24.02.2018]
Module offered in:
SS 2020, SS 2019, SS 2018, SS 2017, SS 2016, ...
[Sat Jul 11 13:24:05 CEST 2020, CKEY=psti, BKEY=kim, CID=KI848, LANGUAGE=en, DATE=11.07.2020]