Prof. Dr.-Ing. Anni-Yasmin Turhan

About this lecture:

Description Logics (DLs) have a long tradition in computer science and knowledge representation, being designed so that domain knowledge can be described and so that computers can reason about this knowledge. DLs have recently gained increased importance since they form the logical basis of widely used ontology languages, in particular the web ontology language OWL. Starting from a basic DL, this course introduces the students to their syntax, semantics, reasoning problems and model theory, and discusses the computational complexity of these reasoning problems and algorithms to solve them.

Organization:

The lecture takes place on Monday and the accompanying tutorial on Wednesday. In the tutorial the content presented in the lecture is covered by exercises. The idea is that students present their solutions to the exercises and discuss the applied methods in class.

Language: Englisch

About this seminar:

In this seminar, students should learn to present research results in a competent and concise manner. The results are first presented in writing in the seminar report and in speaking in the seminar presentation. Additionally, students practice to how to ask technical questions about a talk and to give helpful feedback on the presentation of other students in this seminar.

Language: English

For the seminar, the students have to

• Pick a scientific paper from the pool of papers (or propose a scientific paper) to work on
• Read the paper and discuss the content of it with the seminar tutor
• Design a little "addendum" that goes beyond the content of the paper.
• Discuss the outline of the seminar report with the tutor
• Write the seminar report.
• Discuss the outline of the seminar talk with the tutor
• Prepare slides for the seminar talk
• Give the seminar talk, listen to all the other talks in the seminar and participate in the discussion.

The student topics for this seminar are now available in the Panda course of the seminar (course L.079.08014).

In diesem Proseminar behandeln wir Themen aus der theoretischen Informatik. Die Grundlage ist das Buch "Perlen der theoretischen Informatik" von Uwe Schöning. Die Idee ist, dass sich Teilnehmende ein Kapitel aus dem Buch aussuchen und dieses bearbeiten mit dem Ziel einen Proseminar Report und einen Vortrag zu über das Thema zu erstellen.

Sprache: Deutsch

Das Proseminar beginnt am Montag den 15.4. um 11:00 Uhr im Raum F1. 310.

Die Teilnehmenden sollen

• ein Kapitel des Buches aussuchen, dass sie bearbeiten möchten
• das Kapitel durcharbeiten und mit dem Proseminar-Tutor diskutieren
• die Gliederung für den Proseminar-Report mit dem Tutor diskutieren
• den Seminar-Report schreiben
• die Gliederung für den Proseminar-Vortrag mit dem Tutor diskutieren
• Folien für den Seminar-Vortrag erstellen
• den Proseminar-Vortrag halten, alle anderen Vorträge des Proseminars besuchen und sich an der anschliessenden Diskusion beteiligen

Der Proseminar-Report

Dieser Report soll 5 Seiten umfassen. In dem Report wird das bearbeitete Kapitel (und ggf. die Ergebnisse der zugehörigen Übungen) zusammengefasst und die dort präsentierten Ergebnisse aufbereitet. Die Verwendung KI-generierten Texten ist untersagt.

Der Proseminar-Vortrag

Der Vortrag dauert 30 Minuten. Durch den Vortrag soll das Publikum einen Überblick über den Inhalt des Kapitels gewinnen und es soll im Vortrag auf einzelne Resultate aus dem Kapitel im Detail eingegangen werden.

Zeitplanung

Die Teilnahme am ersten Treffen ist obligatorisch. Am Ende des ersten Treffens werden die Themen an die Teilnehmenden vergeben. Die Proseminar-Vorträge finden am Ende der Vorlesungszeit als Blockseminar statt. Der Termin (ggf die Termine) hierfür werden noch bekannt gegeben.

Fristen:

• bis letzte Aprilwoche
  Treffen mit den PS-Tutor und Diskussion des Kapitels
• bis 8. Mai
  einreichen der Gliederung für den Report
• bis Ende Mai
  einreichen der ersten vollständigen Version des Reports
• bis 25 Juni
  einreichen des ersten vollständigen Foliensatzes für den Proseminar-Vortrag
• Ende der Vorlesungszeit:
  Block-Proseminar mit allen Vorträgen

Themen:

Das Proseminar basiert auf dem Buch "Perlen der theoretischen Informatik" von von Uwe Schöning (BI Wissenschaftsverlag 1995). Die Themen des Proseminars sind einzelen Kapitel dieses Buches. Das Buchkann über die Bibliothek entliehen werden. Es werden aus diesem Buch die folgenden Kapitel als Proseminarsthemen angeboten:

Kapitel 2: Das zehnte Hilbertsche Problem

Kapital 3: Das Äquivalenzproblem für LOOP(1) und LOOP(2) Programme

Kapitel 4: Das zweite LBA-Problem

Kapitel 5: LOGSPACE, Zufallsirrfahrten auf Graphen und universelle Durchlaufsequenzen

Kapitel 6: Exponentielle untere Schranke für die Länge von Resolutionsbeweisen

Kapitel 7: Spektralproblem und deskriptive Komplexitätstheorie

Kapitel 8: Kolmogoroff-Komplexität, universelle Wahrscheinlichkeitsverteilung, worst-case vs. average-case

Kapitel 10: PAC-Lernen und Occam’s Razor

Kapitel 11: Untere Schranke für die Paritätsfunktion

Kapitel 13: Komplexität von Craig-Interpolanten

Kapitel 20: Interaktive Beweise und Zero Knowledge

Kapitel 23: Superkonzentratoren und der Heiratssatz

Kapitel 24: Pebble Game

Die Vergabe der Themen erfolgt in beim ersten Treffen des Proseminars (am 8.4.) nach first come first serve.