INF.00882.08 - Automaten und Berechenbarkeit (Complete module description)

INF.00882.08 - Automaten und Berechenbarkeit (Complete module description)

Original version English
INF.00882.08 10 CP
Module label Automaten und Berechenbarkeit
Module code INF.00882.08
Semester of first implementation
Faculty/Institute Institut für Informatik
Module used in courses of study / semesters
  • Bioinformatik (180 LP) (Bachelor) > Bioinformatik Bioinformatik180, Version of accreditation valid from SS 2021 > Informatik (mindestens 10 LP)
  • Bioinformatik (180 LP) (Bachelor) > Bioinformatik Bioinformatik180, Version of accreditation (WS 2007/08 - SS 2012) > Informatik
  • Bioinformatik (180 LP) (Bachelor) > Bioinformatik Bioinformatik180, Version of accreditation (WS 2012/13 - SS 2016) > Informatik
  • Bioinformatik (180 LP) (Bachelor) > Bioinformatik Bioinformatik180, Version of accreditation (WS 2016/17 - SS 2018) > Informatik
  • Bioinformatik (180 LP) (Bachelor) > Bioinformatik Bioinformatik180, Version of accreditation (WS 2018/19 - WS 2022/23) > Informatik
  • Informatik (180 LP) (Bachelor) > Informatik Informatik180, Version of accreditation valid from SS 2021 > Pflichtmodule
  • Informatik (180 LP) (Bachelor) > Informatik Informatik180, Version of accreditation (WS 2006/07 - SS 2012) > Pflichtmodule
  • Informatik (180 LP) (Bachelor) > Informatik Informatik180, Version of accreditation (WS 2012/13 - SS 2016) > Pflichtmodule
  • Informatik (180 LP) (Bachelor) > Informatik Informatik180, Version of accreditation (WS 2016/17 - SS 2018) > Pflichtmodule
  • Informatik (180 LP) (Bachelor) > Informatik Informatik180, Version of accreditation (WS 2018/19 - WS 2022/23) > Pflichtmodule
  • Informatik (Gymnasium) (ELF) (Lehramt) > Informatik Inform (Gymnasium) (ELF), Version of accreditation valid from WS 2012/13 > Pflichtmodule
  • Informatik (Gymnasium) (ELF) (Lehramt) > Informatik Inform (Gymnasium) (ELF), Version of accreditation (WS 2007/08 - SS 2012) > Pflichtmodule
  • Informatik (Gymnasium) (ELF, WLF) (Lehramt) > Informatik Inform (Gymnasium) (ELF, WLF), Version of accreditation (WS 2007/08 - SS 2012) > Pflichtmodule
  • Informatik (Gymnasium) () (Lehramt) > Informatik Inform (Gymnasium), Version of accreditation valid from WS 2012/13 > Pflichtmodule
  • Informatik (Gymnasium) () (Lehramt) > Informatik Inform (Gymnasium), Version of accreditation (WS 2007/08 - SS 2012) > Pflichtmodule
  • Informatik (Gymnasium) (WLF) (Lehramt) > Informatik Inform (Gymnasium) (WLF), Version of accreditation valid from WS 2012/13 > Pflichtmodule
  • Informatik (Gymnasium) (WLF) (Lehramt) > Informatik Inform (Gymnasium) (WLF), Version of accreditation (WS 2007/08 - SS 2012) > Pflichtmodule
  • Informatik (Sekundarschule) (ELF) (Lehramt) > Informatik Informatik (Sekundar) (ELF), Version of accreditation (WS 2007/08 - SS 2012) > Pflichtmodule
  • Informatik (Sekundarschule) (ELF) (Lehramt) > Informatik Informatik (Sekundar) (ELF), Version of accreditation (WS 2007/08 - WS 2015/16) > Pflichtmodule
  • Informatik (Sekundarschule) (ELF, WLF) (Lehramt) > Informatik Informatik (Sekundar) (ELF, WLF), Version of accreditation (WS 2007/08 - SS 2012) > Pflichtmodule
  • Informatik (Sekundarschule) (ELF, WLF) (Lehramt) > Informatik Informatik (Sekundar) (ELF, WLF), Version of accreditation (WS 2007/08 - WS 2015/16) > Pflichtmodule
  • Informatik (Sekundarschule) () (Lehramt) > Informatik Informatik (Sekundar), Version of accreditation (WS 2007/08 - SS 2012) > Pflichtmodule
  • Informatik (Sekundarschule) () (Lehramt) > Informatik Informatik (Sekundar), Version of accreditation (WS 2007/08 - WS 2015/16) > Pflichtmodule
  • Informatik (Sekundarschule) (WLF) (Lehramt) > Informatik Informatik (Sekundar) (WLF), Version of accreditation (WS 2007/08 - SS 2012) > Pflichtmodule
  • Informatik (Sekundarschule) (WLF) (Lehramt) > Informatik Informatik (Sekundar) (WLF), Version of accreditation (WS 2007/08 - WS 2015/16) > Pflichtmodule
  • Mathematik (180 LP) (Bachelor) > Mathematik Mathematik180, Version of accreditation valid from WS 2019/20 > Anwendungsfach Informatik
  • Mathematik (180 LP) (Bachelor) > Mathematik Mathematik180, Version of accreditation (WS 2013/14 - SS 2022) > Anwendungsfach Informatik
  • Mathematik mit Anwendungsfach (180 LP) (Bachelor) > Mathematik Mathematik m. Anw.fach180, Version of accreditation (WS 2006/07 - SS 2013) > Anwendungsfach Informatik
  • Physik und Digitale Technologien (180 LP) (Bachelor) > Physik Physik u. Dig. Tech. 180, Version of accreditation valid from WS 2019/20 > Wahlobligatorische Ergänzungsfächer
Responsible person for this module
Further responsible persons
apl. Prof. Dr. Klaus Reinhardt
Prerequisites
Modul "Mathematische Grundlagen der Informatik und Konzepte der Modellierung" (Besuch)
Skills to be acquired in this module
Studierende sollen durch dieses Modul die folgenden Kompetenzen erwerben:
  • Sie können Sprachen mit Automaten, Grammatiken und Regulären Ausdrücken formalisieren.
  • Sie können von einer Formalisierungsmethode zu einer anderen übersetzen und die Korrektheit beweisen. Die dabei verwendeten Konstruktionen können sie an Beispielen durchführen und mathematisch allgemein formalisieren.
  • Sie können Sprachen in der Chomsky-Hierarchie klassifizieren und Nichtzugehörigkeiten zu Klassen beweisen.
  • Sie kennen die Grenzen der Machbarkeit bezüglich der Berechenbarkeit und Komplexität und können Vollständigkeiten beweisen.
Module contents
  • Abstrakte Spezifikation und Verifikation sind grundlegende intellektuelle Fähigkeiten eines Informatikers. Daher ist es für angehende Informatiker unerlässlich, die Fähigkeit zum logischen Denken, zur Abstraktion sowie Verständnis für kausale Zusammenhänge zu entwickeln.
  • Demgemäß werde in dieser Vorlesung an Hand abstrakter Berechnungsmodelle deren Fähigkeiten und Grenzen analysiert. Basis und Methode dieser Analyse sind Verifikations- (Beweis-)verfahren, wie sie in der Mathematik, insbesondere der mathematischen Logik entwickelt wurden. Ein wesentlicher Bestandteil des Moduls sind daher das Vorstellen von Beweisverfahren in der Vorlesung und deren selbständiges Üben durch die Teilnehmer. Die Gegenstände an Hand derer dies erfolgen soll sind der Informatik entnommen, es werden in der Vorlesung die folgenden Gebiete behandelt.
  • Endliche Automaten und reguläre Sprachen
  • Kellerautomaten und kontextfreie Sprachen
  • Algorithmenbegriffe: Turing-Maschinen, partiell-rekursive Funktionen
  • Berechenbarkeitstheorie, unentscheidbare Probleme
Effiziente Algorithmen, P-NP-Problem
Chomsky-Hierarchie formaler Sprachen
Forms of instruction Lecture (4 SWS)
Exercises (2 SWS)
Course
Languages of instruction German, English
Duration (semesters) 1 Semester Semester
Module frequency jedes Sommersemester
Module capacity unlimited
Time of examination
Credit points 10 CP
Share on module final degree Course 1: %; Course 2: %; Course 3: %.
Share of module grade on the course of study's final grade 1
Module course label Course type Course title SWS Workload of compulsory attendance Workload of preparation / homework etc Workload of independent learning Workload (examination and preparation) Sum workload
Course 1 Lecture Vorlesung 4 0
Course 2 Exercises Übung 2 0
Course 3 Course Bearbeiten der Übungsausgaben 0
Workload by module 300 300
Total module workload 300
Examination Exam prerequisites Type of examination
Course 1
Course 2
Course 3
Final exam of module
Korrekte Bearbeitung der theoretischen Übungsaufgaben in Höhe von mindestens 60% der maximal erreichbaren Punkte, 5 Kurzvorträge über Lösungen von Übungsaufgaben
mündl. Prüfung oder Klausur
Exam repetition information
Prerequisites and conditions Prerequisites Frequency Compulsory attendance Share on module grade in percent
Course 1 Summer semester No %
Course 2 Summer semester No %
Course 3 Summer semester No %