621.500 (21W) Introduction to Automata Theory, Languages, and Computation
Overview
For further information regarding teaching on campus, please visit: https://www.aau.at/en/corona.
- Lecturer
- LV Nummer Südostverbund ING04001UL, ING05001UL
- Course title german Einführung in die Theoretische Informatik
- Type Lecture
- Course model Attendance-based course
- Hours per Week 2.0
- ECTS credits 2.0
- Registrations 106
- Organisational unit
- Language of instruction German
- Course begins on 12.10.2021
- eLearning Go to Moodle course
Time and place
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
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).
Examination information
Modified examination information (exceptional COVID-19 provisions)
Online-Klausur nach Vereinbarung möglich
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-90
2: 62-71
3: 52-61
4: 42-51
5: 0-41
Grading scheme
Grade / Grade grading schemePosition 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
-
ING.005 Einführung in die theoretische Informatik (
2.0h VO / 2.0 ECTS)
-
Subject: Fachspezifische Vertiefungsfächer (AAU)
(Compulsory elective)
- 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
-
ING.005 Einführung in die theoretische Informatik (
2.0h VO / 2.0 ECTS)
-
Subject: Fachspezifische Vertiefungsfächer (AAU)
(Compulsory elective)
- 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
-
ING.004 Einführung in die theoretische Informatik (
2.0h VO / 2.0 ECTS)
-
Subject: Fachspezifische Vertiefungsfächer (AAU)
(Compulsory elective)
- 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
-
3.3 Einführung in die Theoretische Informatik (
2.0h VO / 2.0 ECTS)
-
Subject: Mathematik und Theoretische Grundlagen
(Compulsory subject)
- 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
-
3.4 Einführung in die Theoretische Informatik (
2.0h VO / 2.0 ECTS)
-
Subject: Mathematik und Theoretische Grundlagen
(Compulsory subject)
- 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
-
Einführung in die Theoretische Informatik (
2.0h VO / 2.0 ECTS)
-
Subject: Mathematics and Theoretical Principles
(Compulsory subject)
- 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
-
13.1 Lehrveranstaltungen aus dem Erweiterungscurriculum "Grundlagen der Informatik" (
0.0h XX / 12.0 ECTS)
-
Subject: Informatik
(Compulsory elective)
- 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)
-
Einführung in die Theoretische Informatik (
2.0h VO / 2.0 ECTS)
-
Subject: Informatik
(Compulsory elective)
- 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)
-
Einführung in die Theoretische Informatik (
0.0h VO / 2.0 ECTS)
-
Subject: Erweiterung Algorithmen und Datenstrukturen
(Compulsory elective)
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 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)