Veranstaltung
Die hier angezeigten Termine und Veranstaltungen werden dynamisch aus Stud.IP heraus angezeigt.
Daher kontaktieren Sie bei Fragen bitte direkt die Person, die unter dem Punkt Lehrende/Dozierende steht.
Veranstaltung
Semester:
Wintersemester
2020
2.01.401 Grundlagen der Theoretischen Informatik -
Veranstaltungstermin | Raum
- Dienstag, 20.10.2020 10:00 - 12:00
- Donnerstag, 22.10.2020 14:00 - 16:00
- Dienstag, 27.10.2020 10:00 - 12:00
- Donnerstag, 29.10.2020 14:00 - 16:00
- Dienstag, 3.11.2020 10:00 - 12:00
- Donnerstag, 5.11.2020 14:00 - 16:00
- Dienstag, 10.11.2020 10:00 - 12:00
- Donnerstag, 12.11.2020 14:00 - 16:00
- Dienstag, 17.11.2020 10:00 - 12:00
- Donnerstag, 19.11.2020 14:00 - 16:00
- Dienstag, 24.11.2020 10:00 - 12:00
- Donnerstag, 26.11.2020 14:00 - 16:00
- Dienstag, 1.12.2020 10:00 - 12:00
- Donnerstag, 3.12.2020 14:00 - 16:00
- Dienstag, 8.12.2020 10:00 - 12:00
- Donnerstag, 10.12.2020 14:00 - 16:00
- Dienstag, 15.12.2020 10:00 - 12:00
- Donnerstag, 17.12.2020 14:00 - 16:00
- Dienstag, 22.12.2020 10:00 - 12:00
- Donnerstag, 7.1.2021 14:00 - 16:00
- Dienstag, 12.1.2021 10:00 - 12:00
- Donnerstag, 14.1.2021 14:00 - 16:00
- Dienstag, 19.1.2021 10:00 - 12:00
- Donnerstag, 21.1.2021 14:00 - 16:00
- Dienstag, 26.1.2021 10:00 - 12:00
- Donnerstag, 28.1.2021 14:00 - 16:00
- Dienstag, 2.2.2021 10:00 - 12:00
- Donnerstag, 4.2.2021 14:00 - 16:00
- Freitag, 12.2.2021 16:30 - 18:30
- Freitag, 12.2.2021 16:30 - 18:30
- Freitag, 12.2.2021 16:30 - 18:30
- Donnerstag, 25.3.2021 13:00 - 15:00
- Donnerstag, 25.3.2021 13:00 - 15:00
Beschreibung
Lehrende
TutorInnen
Studienbereiche
- Informatik
SWS
4
Art der Lehre
Ausschließlich Online
Hinweise zum Inhalt der Veranstaltung für Gasthörende
Im ersten Teil der Vorlesung werden verschiedene Sprachklas-
sen (z. B. reguläre und kontextfreie Sprachen) eingeführt, die u. a. deswegen wichtig
sind, weil sie zur Beschreibung der Syntax von Programmiersprachen verwendet wer-
den. 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, aufgefasst
werden können. Zur Klassifikation dieser Sprachen dienen Grammatiken.
Im zweiten Teil der Vorlesung wird untersucht, welche Funktionen algorithmisch be-
rechenbar bzw. welche Probleme algorithmisch entscheidbar sind. Dazu wird der Be-
griff des Algorithmus formalisiert. Turingmaschinen und Grammatiken stellen sich als
äquivalente Ansätze heraus. Es wird gezeigt, dass es Probleme gibt, die nicht algorith-
misch 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.