Moses - Einführung in die Logik und deskriptive Komplexität

Zur Modulseite PDF generieren

Modul / Version
#40421 / #2

Gültigkeit
WS 2015/16 - WS 2019/20

Verfügbare Sprache(n)
Deutsch

Titel des Moduls
Einführung in die Logik und deskriptive Komplexität

Leistungspunkte
9

Modulverantwortliche*r
Kreutzer, Stephan

Benotung
Benotet

Prüfungsform
Mündliche Prüfung

Lehrsprache(n)
Deutsch

Zugehörigkeit

Fakultät
Fakultät IV

Institut
Institut für Softwaretechnik und Theoretische Informatik

Fachgebiet
34352200 FG Logik und Semantik

Prüfungsausschuss
Keine Angabe

Kontakt

Sekretariat
TEL 7-3

Ansprechpartner*in
Keine Angabe

E-Mail-Adresse
stephan.kreutzer@tu-berlin.de

Webseite
Keine Angabe

Diese Modulbeschreibung gilt nicht im aktuellen Semester.

Die Modulbeschreibung gilt nur für den Zeitraum WS 2015/16 - WS 2019/20.

Lernergebnisse

Die Studierenden kennen die verschiedenen Anwendungen der Logik in der Informatik. Sie haben das methodische Rüstzeug um die Ausdrucksstärke eines logischen Systems zu analysieren und verstehen den engen Zusammenhang zwischen Logik und algorithmischer Komplexität. Sie werden im Rahmen dieses Moduls im Schnittgebiet zwischen Logik und Algorithmik bis an den aktuellen Stand der Forschung herangeführt und somit auf eigene Arbeiten in diesem Gebiet vorbereitet.

Lehrinhalte

Aufbauend auf der Grundvorlesung über Logik im Bachelorstudiengang (z.B. TheGI3 an der TU Berlin) behandelt dieses Modul weiterführende Themen der Logik in der Informatik. Es werden zunächst verschiedene Anwendungsgebiete der Logik eingeführt, besonders Anwendungen in der Datenbanktheorie, der Algorithmik und Komplexitätstheorie, sowie der automatischen Verifikation. Im Zentrum des ersten Teils der Vorlesung stehen Fragen zur Ausdrucksstärke verschiedener Logiken und Datenbankabfragesprachen. Es werden Methoden eingeführt um nachzuweisen, dass bestimmte Abfragen nicht in der Prädikatenlogik definiert werden kann. Aufbauend darauf werden dann sogenannte „Lokalitätssätze" bewiesen, die die Ausdrucksstärke der Prädikatenlogik auf sehr überraschende Art charakterisieren. Thema des zweiten Teils der Vorlesung ist der Zusammenhang zwischen Logik und Komplexität. Hier steht zunächst die Frage im Vordergrund, wie schwierig es ist, Formeln einer gegebene Logik in einer Struktur auszuwerten. Vor allem aber werden wir den Bereich der „deskriptiven Komplexitätstheorie" behandeln, in dem algorithmische Probleme nicht anhand der zu ihrer Lösung benötigten Ressourcen wie Speicherplatz und Laufzeit klassifiziert werden, sondern der zu ihrer Beschreibung nötigen Art und Zahl logischer Quantoren und Operatoren. Es stellt sich heraus, dass es einen erstaunlich engen Zusammenhang zwischen diesen beiden Arten der Beschreibung von Problemen gibt, in dem Sinne, dass Probleme, die in natürlichen Komplexitätsklassen wie PTIME oder NP berechnet werden können, auch Beschreibungen in natürlichen Logiken haben. Die Logik bietet demnach einen alternativen und sehr eleganten Zugang zur Komplexitätstheorie, den wir in diesem Teil der Vorlesung behandeln werden. Im letzten Teil des Moduls wird auf die Rolle der Logik um Zusammenhang mit sogenannten Constraint-Satisfaction-Problemen eingegangen, die im Bereich der künstlichen Intelligenz sehr intensiv untersucht werden. Auch hier hat die Logik wichtige Anwendungsmöglichkeiten, die im Rahmen der Vorlesung behandelt werden.

Modulbestandteile

Pflichtbereich

Die folgenden Veranstaltungen sind für das Modul obligatorisch:

Lehrveranstaltungen	Art	Nummer	Turnus	Sprache	SWS	ISIS	VVZ
Logik und Komplexität	SEM		k.A.	de	2
Logik und Komplexität	IV	0432 L 673	k.A.	de	4

ISIS-Kurssuche nach Veranstaltungen des Moduls

Arbeitsaufwand und Leistungspunkte

Logik und Komplexität (SEM):

Aufwandbeschreibung	Multiplikator	Stunden	Gesamt
Präsenzzeit	15.0	2.0h	30.0h
Vor-/Nachbereitung	15.0	4.0h	60.0h
			90.0h(~3 LP)

Logik und Komplexität (IV):

Aufwandbeschreibung	Multiplikator	Stunden	Gesamt
Präsenzzeit	15.0	4.0h	60.0h
Vor-/Nachbereitung	15.0	8.0h	120.0h
			180.0h(~6 LP)

Der Aufwand des Moduls summiert sich zu 270.0 Stunden. Damit umfasst das Modul 9 Leistungspunkte.

Beschreibung der Lehr- und Lernformen

Die Veranstaltungen bestehen aus einer flexiblen Abfolge von Vorlesungen und Übungen. Zusätzlich werden weitere Themen im Tutorium sowie zum Teil in Gruppenarbeit von den Studierenden selbst erarbeitet.

Voraussetzungen für die Teilnahme / Prüfung

Wünschenswerte Voraussetzungen für die Teilnahme an den Lehrveranstaltungen:

Interesse an theoretischer Informatik sowie Grundkenntnisse in Logik und Komplexitätstheorie, wie sie in den Modulen „Berechenbarkeit und Komplexität“ sowie „Logiken und Kalküle“ vermittelt werden.

Verpflichtende Voraussetzungen für die Modulprüfungsanmeldung:

Dieses Modul hat keine Prüfungsvoraussetzungen.

Abschluss des Moduls

Benotung

Benotet

Prüfungsform

Mündliche Prüfung

Sprache(n)

Deutsch

Dauer/Umfang

30 Minuten

Prüfungsbeschreibung (Abschluss des Moduls)

Mündliche Prüfung Zulassung zur Prüfungsanmeldung auf der Basis eines Nachweises über jeweils bestandene Hausaufgaben.

Dauer des Moduls

Für Belegung und Abschluss des Moduls ist folgende Semesteranzahl veranschlagt:
1 Semester.

Dieses Modul kann in folgenden Semestern begonnen werden:
Winter- und Sommersemester.

Maximale teilnehmende Personen

Die maximale Teilnehmerzahl beträgt 50.

Anmeldeformalitäten

Modulanmeldung gemäß TU-Standard.

Literaturhinweise, Skripte

Skript in Papierform

Verfügbarkeit: verfügbar

Skript in elektronischer Form

Verfügbarkeit: nicht verfügbar

Literatur

Empfohlene Literatur
Keine empfohlene Literatur angegeben

Zugeordnete Studiengänge

Semester:

Zeige auch ausgelaufene Studiengänge und StuPOs

Diese Modulversion wird in folgenden Studiengängen verwendet:

	Studiengang / StuPO	StuPOs	Verwendungen	Erste Verwendung	Letzte Verwendung
Dieses Modul findet in keinem Studiengang Verwendung.

Sonstiges

Literatur: Die Vorlesung orientiert sich am Skript Logik und Komplexität. Ergänzende Literaturangaben zu den einzelnen Kapiteln werden in der Vorlesung bekannt gegeben.