Stud.IP Uni Oldenburg
University of Oldenburg
26.06.2022 03:59:05
inf401 - Foundations of Theoretical Computer Science (Complete module description)
Original version English Download as PDF
Module label Foundations of Theoretical Computer Science
Module code inf401
Credit points 6.0 KP
Workload 180 h
Institute directory Department of Computing Science
Applicability of the module
  • Bachelor's Programme Computing Science (Bachelor) > Aufbaumodule
Responsible persons
Fleischhack, Hans (Module responsibility)
Habel, Annegret (Authorized examiners)
Best, Eike (Authorized examiners)
Olderog, Ernst-Rüdiger (Authorized examiners)
Prerequisites
Skills to be acquired in this module
Einführung in Berechenbarkeits-, Automaten-, Komplexitätstheorie
Module contents
Im ersten Teil der Vorlesung werden verschiedene Sprachklassen (z.B. reguläre und kontextfreie Sprachen) eingeführt, die u.a. deswegen wichtig sind, weil sie zur Beschreibung der Syntax von Programmiersprachen verwendet werden. Parallel dazu werden je Sprachklasse dazugehörige Automatenmodelle (z.B. endliche Automaten, Kellerautomaten, Turingmaschinen) vorgestellt, die als abstrakte Algorithmenbeschreibung, wie die jeweiligen Sprachen akzeptiert werden, aufgefaßt werden können. Zur Klassifikation dieser Sprachen dienen Grammatiken.

Im zweiten Teil der Vorlesung wird untersucht, welche Funktionen algorithmisch berechenbar bzw.
welche Probleme algorithmisch entscheidbar sind. Dazu wird der Begriff des Algorithmus formalisiert. Turingmaschinen und Grammatiken stellen sich als äquivalente Ansätze heraus. Es wird gezeigt, daß es Probleme gibt, die nicht algorithmisch entscheidbar sind. Dazu gehören leider auch viele Probleme von praktischem Interesse.

Im dritten Teil der Vorlesung geht es um die Komplexität von Algorithmen, d.h. wieviel Zeit und Speicherplatz zum Lösen einer Aufgabe benötigt wird. Insbesondere werden Probleme betrachtet, die deterministisch oder nichtdeterministisch in polynomieller Zeit lösbar sind. Diese Problemklassen sind unter den Namen P und NP bekannt.
Reader's advisory
  • essentiell: Skriptum "Grundbegriffe der Theoretischen Informatik"
  • empfohlen: Schöning: "Theoretische Informatik - kurzgefasst", 4. Auflage, Spektrum
  • gute Sekundärliteratur: Hopcroft, Motwani, Ullman: "Einführung in die Automatentheorie, Formale Sprachen und Komplexitätstheorie", Pearson (ein Klassiker...)
Links
Language of instruction German
Duration (semesters) 1 Semester
Module frequency jährlich
Module capacity unlimited
Modullevel / module level AC (Aufbaucurriculum)
Modulart / typ of module Pflicht
Lehr-/Lernform / Teaching/Learning method
Vorkenntnisse / Previous knowledge
Course type Comment SWS Frequency Workload of compulsory attendance
Lecture
3 42
Seminar
Total time of attendance for the module 42 h
Examination Time of examination Type of examination
Final exam of module
Am Ende der Vorlesungszeit
KL