621.500 (23W) Introduction to Automata Theory, Languages, and Computation

Wintersemester 2023/24

Registration deadline has expired.

First course session
03.10.2023 12:00 - 14:00 HS 7 On Campus
... no further dates known

Overview

Lecturer
LV Nummer Südostverbund ING04001UL, ING05001UL
Course title german Einführung in die Theoretische Informatik
Type Lecture
Course model Blended learning course
Online proportion 40%
Hours per Week 2.0
ECTS credits 2.0
Registrations 120
Organisational unit
Language of instruction Deutsch
possible language(s) of the assessment German , English
Course begins on 03.10.2023
eLearning Go to Moodle course
University entrance qualification examination Yes
Seniorstudium Liberale Yes

Time and place

List of events is loading...

Course Information

Intended learning outcomes

Was können Computer? Das ist eine der fundamentalen Frage, auf die das Feld der theoretischen Informatik aufbaut. Diese LV bietet einen Überblick über die grundlegenden Techniken, um dieser Frage auf den Grund zu gehen. Hierzu formalisieren wir den Begriff der Berechenbarkeit durch Entwicklung verschiedener Werkzeuge und Modelle, wie formale Sprachen, Registermaschinen, und Turingmaschinen. Für jedes Berechenbarkeitsmodell betrachten wir lösbare und unlösbare Probleme, um die Leistungsfähigkeit von Computern im Allgemeinen verstehen und bewerten zu können.

Teaching methodology including the use of eLearning tools

Vortrag.

Course content

  • Motivation
  • Registermaschinen
  • Turingmaschinen
  • Endliche Automaten
  • Kontextfreie Sprachen
  • Die These von Church
  • Unberechenbarkeit
  • Einführung in die Komplexitätstheorie

Prior knowledge expected

Mathematische Grundkenntnisse (Mengen, Sprachen, ..., einfache Beweistechniken).

Curricular registration requirements

Keine.

Literature

M. Sipser. Introduction to the Theory of Computation, 3rd ed. Cengage Learning, 2012.

Examination information

Im Fall von online durchgeführten Prüfungen sind die Standards zu beachten, die die technischen Geräte der Studierenden erfüllen müssen, um an diesen Prüfungen teilnehmen zu können.

Examination methodology

Klausur am Ende des Semesters, Bearbeitungszeit: 100 Minuten, 90 Punkte.

Examination topic(s)

Inhalt der Vorlesung

Assessment criteria / Standards of assessment for examinations

Note: Punkte

1: >= 72 

2: < 72

3: < 62

4: < 52

5: < 42



Grading scheme

Grade / Grade grading scheme

Position in the curriculum

  • Bachelor-Lehramtsstudium Bachelor Unterrichtsfach Informatik (SKZ: 414, Version: 15W.2)
    • Subject: Fachspezifische Vertiefungsfächer (AAU) (Compulsory elective)
      • ING.005 Einführung in die theoretische Informatik ( 2.0h VO / 2.0 ECTS)
        • 621.500 Introduction to Automata Theory, Languages, and Computation (2.0h VO / 2.0 ECTS)
          Absolvierung im 7. Semester empfohlen
  • Bachelor-Lehramtsstudium Bachelor Unterrichtsfach Informatik (SKZ: 414, Version: 17W.2)
    • Subject: Fachspezifische Vertiefungsfächer (AAU) (Compulsory elective)
      • ING.005 Einführung in die theoretische Informatik ( 2.0h VO / 2.0 ECTS)
        • 621.500 Introduction to Automata Theory, Languages, and Computation (2.0h VO / 2.0 ECTS)
          Absolvierung im 7. Semester empfohlen
  • Bachelor-Lehramtsstudium Bachelor Unterrichtsfach Informatik (SKZ: 414, Version: 19W.2)
    • Subject: Fachspezifische Vertiefungsfächer (AAU) (Compulsory elective)
      • ING.004 Einführung in die theoretische Informatik ( 2.0h VO / 2.0 ECTS)
        • 621.500 Introduction to Automata Theory, Languages, and Computation (2.0h VO / 2.0 ECTS)
          Absolvierung im 7. Semester empfohlen
  • Bachelor's degree programme Applied Informatics (SKZ: 511, Version: 19W.2)
    • Subject: Mathematik und Theoretische Grundlagen (Compulsory subject)
      • 3.3 Einführung in die Theoretische Informatik ( 2.0h VO / 2.0 ECTS)
        • 621.500 Introduction to Automata Theory, Languages, and Computation (2.0h VO / 2.0 ECTS)
          Absolvierung im 3. Semester empfohlen
  • Bachelor's degree programme Applied Informatics (SKZ: 511, Version: 17W.1)
    • Subject: Mathematik und Theoretische Grundlagen (Compulsory subject)
      • 3.4 Einführung in die Theoretische Informatik ( 2.0h VO / 2.0 ECTS)
        • 621.500 Introduction to Automata Theory, Languages, and Computation (2.0h VO / 2.0 ECTS)
          Absolvierung im 3. Semester empfohlen
  • Bachelor's degree programme Applied Informatics (SKZ: 511, Version: 12W.1)
    • Subject: Mathematics and Theoretical Principles (Compulsory subject)
      • Einführung in die Theoretische Informatik ( 2.0h VO / 2.0 ECTS)
        • 621.500 Introduction to Automata Theory, Languages, and Computation (2.0h VO / 2.0 ECTS)
          Absolvierung im 3. Semester empfohlen
  • Bachelorstudium Technische Mathematik (SKZ: 201, Version: 17W.1)
    • Subject: Informatik (Compulsory elective)
      • 13.1 Lehrveranstaltungen aus dem Erweiterungscurriculum "Grundlagen der Informatik" ( 0.0h XX / 12.0 ECTS)
        • 621.500 Introduction to Automata Theory, Languages, and Computation (2.0h VO / 2.0 ECTS)
          Absolvierung im 1., 2., 3., 4., 5., 6. Semester empfohlen

Equivalent courses for counting the examination attempts

Wintersemester 2024/25
  • 621.500 VO Einführung in die Theoretische Informatik (2.0h / 2.0ECTS)
Wintersemester 2022/23
  • 621.500 VO Einführung in die Theoretische Informatik (2.0h / 2.0ECTS)
Wintersemester 2021/22
  • 621.500 VO Einführung in die Theoretische Informatik (2.0h / 2.0ECTS)
Wintersemester 2020/21
  • 621.500 VO Einführung in die Theoretische Informatik (2.0h / 2.0ECTS)
Wintersemester 2019/20
  • 621.500 VO Einführung in die Theoretische Informatik (2.0h / 2.0ECTS)
Wintersemester 2018/19
  • 621.500 VO Einführung in die Theoretische Informatik (2.0h / 2.0ECTS)
Wintersemester 2017/18
  • 621.500 VO Einführung in die Theoretische Informatik (2.0h / 2.0ECTS)
Wintersemester 2016/17
  • 621.500 VO Einführung in die Theoretische Informatik (2.0h / 2.0ECTS)
Wintersemester 2015/16
  • 621.500 VO Einführung in die Theoretische Informatik (2.0h / 2.0ECTS)
Wintersemester 2014/15
  • 621.500 VO Einführung in die Theoretische Informatik (2.0h / 2.0ECTS)
Wintersemester 2013/14
  • 621.500 VO Einführung in die Theoretische Informatik (2.0h / 2.0ECTS)
Wintersemester 2012/13
  • 621.500 VO Einführung in die Theoretische Informatik (2.0h / 2.0ECTS)
Wintersemester 2011/12
  • 621.500 VO Einführung in die Theoretische Informatik (2.0h / 2.0ECTS)
Wintersemester 2010/11
  • 621.500 VO Einführung in die Theoretische Informatik (2.0h / 2.0ECTS)
Wintersemester 2009/10
  • 621.500 VO Einführung in die Theoretische Informatik (2.0h / 2.0ECTS)
Wintersemester 2008/09
  • 621.500 VO Einführung in die Theoretische Informatik (2.0h / 2.0ECTS)