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
Links
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.