Theoretische Grundlagen der Informatik

Theoretische Grundlagen der Informatik
Type: Vorlesung (V)
Semester: WS 15/16
Time: 20.10.2015
11:30 - 13:00 wöchentlich
30.21 Gerthsen 30.21 Gerthsen-Hörsaalgebäude


22.10.2015
11:30 - 13:00
30.21 Gerthsen 30.21 Gerthsen-Hörsaalgebäude

27.10.2015
11:30 - 13:00 wöchentlich
30.21 Gerthsen 30.21 Gerthsen-Hörsaalgebäude

03.11.2015
11:30 - 13:00 wöchentlich
30.21 Gerthsen 30.21 Gerthsen-Hörsaalgebäude

05.11.2015
11:30 - 13:00
30.21 Gerthsen 30.21 Gerthsen-Hörsaalgebäude

10.11.2015
11:30 - 13:00 wöchentlich
30.21 Gerthsen 30.21 Gerthsen-Hörsaalgebäude

17.11.2015
11:30 - 13:00 wöchentlich
30.21 Gerthsen 30.21 Gerthsen-Hörsaalgebäude

19.11.2015
11:30 - 13:00
30.21 Gerthsen 30.21 Gerthsen-Hörsaalgebäude

24.11.2015
11:30 - 13:00 wöchentlich
30.21 Gerthsen 30.21 Gerthsen-Hörsaalgebäude

01.12.2015
11:30 - 13:00 wöchentlich
30.21 Gerthsen 30.21 Gerthsen-Hörsaalgebäude

03.12.2015
11:30 - 13:00
30.21 Gerthsen 30.21 Gerthsen-Hörsaalgebäude

08.12.2015
11:30 - 13:00 wöchentlich
30.21 Gerthsen 30.21 Gerthsen-Hörsaalgebäude

15.12.2015
11:30 - 13:00 wöchentlich
30.21 Gerthsen 30.21 Gerthsen-Hörsaalgebäude

17.12.2015
11:30 - 13:00
30.21 Gerthsen 30.21 Gerthsen-Hörsaalgebäude

22.12.2015
11:30 - 13:00 wöchentlich
30.21 Gerthsen 30.21 Gerthsen-Hörsaalgebäude

29.12.2015
11:30 - 13:00 wöchentlich
30.21 Gerthsen 30.21 Gerthsen-Hörsaalgebäude

31.12.2015
11:30 - 13:00
30.21 Gerthsen 30.21 Gerthsen-Hörsaalgebäude

05.01.2016
11:30 - 13:00 wöchentlich
30.21 Gerthsen 30.21 Gerthsen-Hörsaalgebäude

12.01.2016
11:30 - 13:00 wöchentlich
30.21 Gerthsen 30.21 Gerthsen-Hörsaalgebäude

14.01.2016
11:30 - 13:00
30.21 Gerthsen 30.21 Gerthsen-Hörsaalgebäude

19.01.2016
11:30 - 13:00 wöchentlich
30.21 Gerthsen 30.21 Gerthsen-Hörsaalgebäude

26.01.2016
11:30 - 13:00 wöchentlich
30.21 Gerthsen 30.21 Gerthsen-Hörsaalgebäude

28.01.2016
11:30 - 13:00
30.21 Gerthsen 30.21 Gerthsen-Hörsaalgebäude

02.02.2016
11:30 - 13:00 wöchentlich
30.21 Gerthsen 30.21 Gerthsen-Hörsaalgebäude

09.02.2016
11:30 - 13:00 wöchentlich
30.21 Gerthsen 30.21 Gerthsen-Hörsaalgebäude

11.02.2016
11:30 - 13:00
30.21 Gerthsen 30.21 Gerthsen-Hörsaalgebäude


Lecturer: Prof.Dr. Peter Sanders
Julian Arz
Lorenz Hübschle-Schneider M.Sc.
Tobias Maier
SWS: 3/1
Lv-No.: 24005
BeschreibungInhalt der Vorlesung sind die Grundlagen der Theoretischen Informatik: Berechnungsmodelle, Determinismus und Nichtdeterminismus, Fragen der Berechenbarkeit, Komplexitätstheorie, NP-Vollständigkeit, Grammatiken, formale Sprachen.
LiteraturhinweiseWeiterführende Literatur
  • Uwe Schöning: Theoretische Informatik - kurz gefasst. Sprektrum (2001).
  • Ingo Wegener: Theoretische Informatik. Teubner (1999)
  • Ingo Wegener: Kompedium theoretische Informatik. Teubner (1996).
LehrinhaltEs gibt wichtige Probleme, deren Lösung sich zwar klar definieren läßt, aber die man niemals wird systematisch berechnen können. Andere Probleme lassen sich "vermutlich" nur durch systematisches Ausprobieren lösen. Andere Themen dieser Vorlesungen legen die Grundlagen für Schaltkreisentwurf, Compilerbau, uvam. Die meisten Ergebnisse dieser Vorlesung werden rigoros bewiesen. Die dabei erlernten Beweistechniken sind wichtig für die Spezifikation von Systemen der Informatik und für den systematischen Entwurf von Programmen und Algorithmen.
Das Modul gibt einen vertieften Einblick in die Grundlagen und Methoden der Theoretischen Informatik. Insbesondere wird dabei eingegangen auf grundlegende Eigenschaften Formaler Sprachen als Grundlagen von Programmiersprachen und Kommunikationsprotokollen (regulär, kontextfrei, Chomsky-Hierarchie), Maschinenmodelle (endliche Automaten, Kellerautomaten, Turingmaschinen, Nichtdeterminismus, Bezug zu Familien formaler Sprachen), Äquivalenz aller hinreichend mächtigen Berechnungsmodelle (Churchsche These), Nichtberechenbarkeit wichtiger Funktionen (Halteproblem,...), Gödels Unvollständigkeitssatz und Einführung in die Komplexitätstheorie (NP-vollständige Probleme und polynomiale Reduktionen).
ArbeitsbelastungVorlesung mit 3 SWS + 1 SWS Übung.

6 LP entspricht ca. 180 Stunden

ca. 45 Std. Vorlesungsbesuch
ca. 15 Std. Übungsbesuch
ca. 90 Std. Nachbearbeitung und Bearbeitung der Übungsblätter
ca. 30 Std. Prüfungsvorbereitung

ZielDer/die Studierende besitzt einen vertieften Einblick in die Grundlagen der Theoretischen Informatik und hat grundlegende Kenntnis in den Bereichen Berechenbarkeitstheorie, Komplexitätstheorie, formale Sprachen und Informationstheorie. Er/sie kann die Beziehungen dieser Gebiete erörtern und in einen Gesamtzusammenhang bringen. Außerdem kennt er/sie die fundamentalen Definitionen und Aussagen aus diesen Bereichen und ist in der Lage geführte Beweise zu verstehen sowie Wissen über erlangte Beweistechniken auf ähnliche Probleme anzuwenden.

Er/sie versteht die Grenzen und Möglichkeiten der Informatik in Bezug auf die Lösung von definierbaren aber nur bedingt berechenbare Probleme. Hierzu beherrscht er verschiedene Berechnungsmodelle, wie die der Turingmaschine, des Kellerautomaten und des endlichen

Automaten. Er/sie kann deterministische von nicht-deterministischen Modellen unterscheiden und deren Mächtigkeit gegeneinander abschätzen. Der/die Studierende kann die Äquivalenz aller hinreichend mächtigen Berechnungsmodelle (Churchsche These), Nichtberechenbarkeit wichtiger Funktionen (z.B. Halteproblem) und Gödels Unvollständigkeitssatz erläutern.

Er/sie besitzt einen Überblick über die wichtigsten Klassen der Komplexitätstheorie. Darüber hinaus kann er/sie ausgewählte Probleme mittels formaler Beweisführung in die ihm/ihr bekannten Komplexitätsklassen zuordnen. Insbesondere kennt er/sie die Komplexitätsklassen P und NP sowie das Konzept NP-vollständiger Probleme (polynomielle Reduktion). Er/sie kann erste grundlegende Techniken anwenden, um NP-schwere Probleme zu analysieren. Diese

Techniken umfassen unter anderem polynomielle Näherungsverfahren (Approximationsalgorithmen mit absoluter/relativer Güte, Approximationsschemata) als auch exakte Verfahren (Ganzzahlige Programme).

Im Bereich der formalen Sprachen ist es ihm/ihr möglich, Sprachen als Grammatiken zu formulieren und diese in die Chomsky-Hierarchie einzuordnen. Somit besitzt er/sie erste Kenntnisse im Compilerbau. Zudem kann er/sie die ihm/ihr bekannten Berechnungsmodelle den einzelnen Typen der Chomsky-Hierarchie zuordnen, so dass er/sie die Zusammenhänge zwischen formalen Sprachen und Berechnungstheorie identifizieren kann.

Der/die Studierende besitzt einen grundlegenden Überblick über die Informationstheorie und kennt damit Entropie, Kodierungsschemata sowie eine formale Definition für Information. Er/sie besitzt zudem die Fähigkeit, dieses Wissen anzuwenden.

PrüfungDie Erfolgskontrolle erfolgt in Form einer schriftlichen Prüfung nach § 4 Abs. 2 Nr. 1 SPO. Es besteht die Möglichkeit, einen Übungsschein (Erfolgskontrolle anderer Art nach §4 Abs. 2 Nr. 3 SPO) zu erwerben. Für diesen werden Bonuspunkte vergeben, die auf eine bestandene Klausur angerechnet werden. Die Modulnote ist die Note der Klausur.

Kursbeschreibung

Beschreibung Inhalt der Vorlesung sind die Grundlagen der Theoretischen Informatik: Berechnungsmodelle, Determinismus und Nichtdeterminismus, Fragen der Berechenbarkeit, Komplexitätstheorie, NP-Vollständigkeit, Grammatiken, formale Sprachen.
Literaturhinweise Weiterführende Literatur
  • Uwe Schöning: Theoretische Informatik - kurz gefasst. Sprektrum (2001).
  • Ingo Wegener: Theoretische Informatik. Teubner (1999)
  • Ingo Wegener: Kompedium theoretische Informatik. Teubner (1996).
Lehrinhalt Es gibt wichtige Probleme, deren Lösung sich zwar klar definieren läßt, aber die man niemals wird systematisch berechnen können. Andere Probleme lassen sich "vermutlich" nur durch systematisches Ausprobieren lösen. Andere Themen dieser Vorlesungen legen die Grundlagen für Schaltkreisentwurf, Compilerbau, uvam. Die meisten Ergebnisse dieser Vorlesung werden rigoros bewiesen. Die dabei erlernten Beweistechniken sind wichtig für die Spezifikation von Systemen der Informatik und für den systematischen Entwurf von Programmen und Algorithmen.
Das Modul gibt einen vertieften Einblick in die Grundlagen und Methoden der Theoretischen Informatik. Insbesondere wird dabei eingegangen auf grundlegende Eigenschaften Formaler Sprachen als Grundlagen von Programmiersprachen und Kommunikationsprotokollen (regulär, kontextfrei, Chomsky-Hierarchie), Maschinenmodelle (endliche Automaten, Kellerautomaten, Turingmaschinen, Nichtdeterminismus, Bezug zu Familien formaler Sprachen), Äquivalenz aller hinreichend mächtigen Berechnungsmodelle (Churchsche These), Nichtberechenbarkeit wichtiger Funktionen (Halteproblem,...), Gödels Unvollständigkeitssatz und Einführung in die Komplexitätstheorie (NP-vollständige Probleme und polynomiale Reduktionen).
Arbeitsbelastung Vorlesung mit 3 SWS + 1 SWS Übung.

6 LP entspricht ca. 180 Stunden

ca. 45 Std. Vorlesungsbesuch
ca. 15 Std. Übungsbesuch
ca. 90 Std. Nachbearbeitung und Bearbeitung der Übungsblätter
ca. 30 Std. Prüfungsvorbereitung

Ziel Der/die Studierende besitzt einen vertieften Einblick in die Grundlagen der Theoretischen Informatik und hat grundlegende Kenntnis in den Bereichen Berechenbarkeitstheorie, Komplexitätstheorie, formale Sprachen und Informationstheorie. Er/sie kann die Beziehungen dieser Gebiete erörtern und in einen Gesamtzusammenhang bringen. Außerdem kennt er/sie die fundamentalen Definitionen und Aussagen aus diesen Bereichen und ist in der Lage geführte Beweise zu verstehen sowie Wissen über erlangte Beweistechniken auf ähnliche Probleme anzuwenden.

Er/sie versteht die Grenzen und Möglichkeiten der Informatik in Bezug auf die Lösung von definierbaren aber nur bedingt berechenbare Probleme. Hierzu beherrscht er verschiedene Berechnungsmodelle, wie die der Turingmaschine, des Kellerautomaten und des endlichen

Automaten. Er/sie kann deterministische von nicht-deterministischen Modellen unterscheiden und deren Mächtigkeit gegeneinander abschätzen. Der/die Studierende kann die Äquivalenz aller hinreichend mächtigen Berechnungsmodelle (Churchsche These), Nichtberechenbarkeit wichtiger Funktionen (z.B. Halteproblem) und Gödels Unvollständigkeitssatz erläutern.

Er/sie besitzt einen Überblick über die wichtigsten Klassen der Komplexitätstheorie. Darüber hinaus kann er/sie ausgewählte Probleme mittels formaler Beweisführung in die ihm/ihr bekannten Komplexitätsklassen zuordnen. Insbesondere kennt er/sie die Komplexitätsklassen P und NP sowie das Konzept NP-vollständiger Probleme (polynomielle Reduktion). Er/sie kann erste grundlegende Techniken anwenden, um NP-schwere Probleme zu analysieren. Diese

Techniken umfassen unter anderem polynomielle Näherungsverfahren (Approximationsalgorithmen mit absoluter/relativer Güte, Approximationsschemata) als auch exakte Verfahren (Ganzzahlige Programme).

Im Bereich der formalen Sprachen ist es ihm/ihr möglich, Sprachen als Grammatiken zu formulieren und diese in die Chomsky-Hierarchie einzuordnen. Somit besitzt er/sie erste Kenntnisse im Compilerbau. Zudem kann er/sie die ihm/ihr bekannten Berechnungsmodelle den einzelnen Typen der Chomsky-Hierarchie zuordnen, so dass er/sie die Zusammenhänge zwischen formalen Sprachen und Berechnungstheorie identifizieren kann.

Der/die Studierende besitzt einen grundlegenden Überblick über die Informationstheorie und kennt damit Entropie, Kodierungsschemata sowie eine formale Definition für Information. Er/sie besitzt zudem die Fähigkeit, dieses Wissen anzuwenden.

Prüfung Die Erfolgskontrolle erfolgt in Form einer schriftlichen Prüfung nach § 4 Abs. 2 Nr. 1 SPO. Es besteht die Möglichkeit, einen Übungsschein (Erfolgskontrolle anderer Art nach §4 Abs. 2 Nr. 3 SPO) zu erwerben. Für diesen werden Bonuspunkte vergeben, die auf eine bestandene Klausur angerechnet werden. Die Modulnote ist die Note der Klausur.