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

Wintersemester 2020/21

Registration deadline has expired.

First course session
06.10.2020 12:00 - 14:00 online Off Campus
... no further dates known

Overview

Due to the COVID-19 pandemic, it may be necessary to make changes to courses and examinations at short notice (e.g. cancellation of attendance-based courses and switching to online examinations).

For further information regarding teaching on campus, please visit: https://www.aau.at/en/corona.
Lecturer
LV Nummer Südostverbund ING04004UL, ING05001UL
Course title german Einführung in die Theoretische Informatik
Type Lecture
Course model Online course
Hours per Week 2.0
ECTS credits 2.0
Registrations 121
Organisational unit
Language of instruction German
Course begins on 06.10.2020
eLearning Go to Moodle course

Time and place

Please note that the currently displayed dates may be subject to change due to COVID-19 measures.
List of events is loading...

Course Information

Intended learning outcomes

Ausgehend von einigen aus Algorithmen und Datenstrukturen bekannten Problemlösungen erweitern wir in dieser LV die Betrachtung um die Fragestellung nach allgemeiner Berechenbarkeit bzw. Lösbarkeit von Problemen. Hierzu formalisieren wir den Begriff der Berechenbarkeit durch Entwicklung verschiedener Werkzeuge und Modelle, wie etwa formale Sprachen, Registermaschinen, Turingmaschinen u.v.m. Für jedes Berechenbarkeitsmodell betrachten wir (im jeweiligen Modell) 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 mit präsentierten Beispielen.

Course content

  • Motivation und Präliminarien
  • Registermaschinen
  • Turingmaschinen
  • Endliche Automaten
  • Kontextfreie Sprachen
  • Die These von Church
  • Unberechenbarkeit

Prior knowledge expected

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

Literature

Die Vorlesung orientiert sich in Teilen an drei Monographien:

  • A. Asteroth, C. Baier: Theoretische Informatik, Pearson (2002) ISBN 3-8273-7033-7 (eBook, 2008)
  • H.R. Lewis, C.H. Papadimitrou: Elements of the Theory of Compuation (2nd ed.), Prentice Hall (1998) ISBN 0-13-262478-8
  • M. Sipser: Introduction to the Theory of Computation, PWS Publishing (1997) ISBN 0-534-94728-X

Die Vorlesungsunterlagen enthalten alle relevanten Inhalte, die in der Vorlesung entsprechend zu ergänzen sind.

Link to further information

https://www.syssec.at/de/lehre/ws-2020/theoretische-informatik

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

Online-Klausur am Ende des Semesters

Examination topic(s)

gesamter Inhalt der Vorlesung

Assessment criteria / Standards of assessment for examinations

siehe https://www.syssec.at/de/lehre/ws-2020/theoretische-informatik/modalitaeten

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
  • Bachelor's degree programme Technical Mathematics (SKZ: 201, Version: 12W.2)
    • Subject: Informatik (Compulsory elective)
      • 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)
  • Erweiterungscurriculum Grundlagen der Informatik (Version: 16W.1)
    • Subject: Erweiterung Algorithmen und Datenstrukturen (Compulsory elective)
      • Einführung in die Theoretische Informatik ( 0.0h VO / 2.0 ECTS)
        • 621.500 Introduction to Automata Theory, Languages, and Computation (2.0h VO / 2.0 ECTS)

Equivalent courses for counting the examination attempts

Wintersemester 2023/24
  • 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 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)