Logik in der Informatik Prof. Dr. Nicole Schweikardt

Pandemiebedingt wird die Veranstaltung in diesem Semester online durchgeführt. In diesem Logbuch werden regelmäßig Informationen dazu bereit gestellt, welche Lektüre von allen Teilnehmer*innen bis zum nächsten "Vorlesungstermin" selbständig durchgearbeitet werden soll. Die "Vorlesungstermine" (Di+Do 15-17 Uhr) werden über Zoom als Online-Treffen durchgeführt (die Zugangsdaten werden über Moodle bereit gestellt), in denen Fragen zur Lektüre gestellt werden können und in denen das in der Lektürearbeit erarbeitete Wissen weiter vertieft wird.

Das erste Online-Treffen, für das Sie vorher eine Lektüreaufgabe erledigen müssen, findet am Donnerstag, den 05.11.20 statt.

Zwei Tage vorher, am Dienstag, den 03.11.20, fand die Eröffnungsvorlesung statt, in der eine Einführung ins Thema gegeben und organisatorische Fragen geklärt wurden (Seiten 1-12 des Vorlesungsskripts).

1. bis Do, 05.11.2020:

   Arbeiten Sie Folgendes durch:

   • Seiten 13-27 des Vorlesungsskripts.

   Ergänzende Lektüre, in der Sie bei Interesse weiterlesen können (aber nicht müssen):

   • Teil A und Kapitel 4.1 und 4.2 von [AHV]
   • Abschnitte 19.1 und 19.2 des Artikels [SSS]

2. bis Di, 10.11.2020:

   Arbeiten Sie Folgendes durch:

   • Seiten 28-38 des Vorlesungsskripts.

   Ergänzende Lektüre, in der Sie bei Interesse weiterlesen können (aber nicht müssen):

   • Teil A und Kapitel 4.1 und 4.2 von [AHV]

3. bis Do, 12.11.2020:

   Arbeiten Sie Folgendes durch:

   • Seiten 38-48 des Vorlesungsskripts.

   Ergänzende Lektüre, in der Sie bei Interesse weiterlesen können (aber nicht müssen):

   • Kapitel 4.3 von [AHV]

4. bis Di, 17.11.2020:

   Arbeiten Sie Folgendes durch:

   • Seiten 48-59 des Vorlesungsskripts.

   Ergänzende Lektüre, in der Sie bei Interesse weiterlesen können (aber nicht müssen):

   • Kapitel 4.3 von [AHV]
   • die Originalarbeit [CM] von Chandra und Merlin finden Sie hier

5. bis Do, 19.11.2020:

   Arbeiten Sie Folgendes durch:

   • Seiten 56-68 des Vorlesungsskripts.

   Ergänzende Lektüre, in der Sie bei Interesse weiterlesen können (aber nicht müssen):

   • Kapitel 4.3, 4.4 und 4.5 von [AHV]
   • die Originalarbeit [CM] von Chandra und Merlin finden Sie hier
   • eine Einführung [G] in die Parametrisierte Komplexität für Datenbanktheoretiker*innen ist hier erhältlich

6. bis Di, 24.11.2020:

   Arbeiten Sie Folgendes durch:

   • Seiten 65-73 des Vorlesungsskripts.

   Ergänzende Lektüre, in der Sie bei Interesse weiterlesen können (aber nicht müssen):

   • Kapitel 4.4, 4.5 und 6.2 von [AHV]

7. bis Do, 26.11.2020:

   Arbeiten Sie Folgendes durch:

   • Seiten 74-82 des Vorlesungsskripts (bis zum Ende von Folie 107).

   Ergänzende Lektüre, in der Sie bei Interesse weiterlesen können (aber nicht müssen):

   • Kapitel 6.2-6.4 von [AHV]
   • die Originalarbeit [CM] von Chandra und Merlin finden Sie hier

8. bis Di, 01.12.2020:

   Arbeiten Sie Folgendes durch:

   • Seiten 82-88 des Vorlesungsskripts (bis zum Ende von Folie 110).

   Ergänzende Lektüre, in der Sie bei Interesse weiterlesen können (aber nicht müssen):

   • Kapitel 6.2-6.4 von [AHV]
   • die Originalarbeit [CM] von Chandra und Merlin finden Sie hier

9. bis Do, 03.12.2020:

   Arbeiten Sie Folgendes durch:

   • Seiten 88-92 des Vorlesungsskripts (bis zum Ende von Folie 117).
     Auf Folie 113: Versuchen Sie, selbst Join-Bäume für die Anfragen Q₁ und Q₃ zu konstruieren, und überlegen Sie, warum Q₂ keinen Join-Baum besitzt.
     Auf Folien 116 und 117: Dort, wo "siehe Tafel" steht: Überlegen Sie sich zugehörige Algorithmen.

   Ergänzende Lektüre, in der Sie bei Interesse weiterlesen können (aber nicht müssen):

   • Kapitel 6.2 und 6.4 von [AHV]
   • Die Originalarbeit [Y] von Yannakakis.
   • Einen Überblick über Verallgemeinerungen des Begriffs der azyklischen Anfragen gibt die Arbeit [Sca] von Scarcello.

10. bis Di, 08.12.2020:

    Arbeiten Sie Folgendes durch:

    • Seiten 95-99 des Vorlesungsskripts. ACHTUNG: Es wurde am 03.12.20 eine neue Version des Vorlesungsskripts hochgeladen.

    Ergänzende Lektüre, in der Sie bei Interesse weiterlesen können (aber nicht müssen):

    • Kapitel 6.2 und 6.4 von [AHV]
    • Die Originalarbeit [Y] von Yannakakis.
    • Einen Überblick über Verallgemeinerungen des Begriffs der azyklischen Anfragen gibt die Arbeit [Sca] von Scarcello.

11. bis Do, 10.12.2020:

    Arbeiten Sie Folgendes durch:

    • Seiten 98 bis zum Ende von Kapitel 3.5 des Vorlesungsskripts.

    Ergänzende Lektüre, in der Sie bei Interesse weiterlesen können (aber nicht müssen):

    • Kapitel 6.2 und 6.4 von [AHV]
    • Die Originalarbeit [Y] von Yannakakis.
    • Einen Überblick über Verallgemeinerungen des Begriffs der azyklischen Anfragen gibt die Arbeit [Sca] von Scarcello.

12. bis Di, 15.12.2020:

    Arbeiten Sie Folgendes durch:

    • Kapitel 3.6 und Teile von Kapitel 4.1 des Vorlesungsskripts (bis inkl. Folie 147).

    Ergänzende Lektüre, in der Sie bei Interesse weiterlesen können (aber nicht müssen):

    • Kapitel 6.2 und 6.4 von [AHV]
    • Umfassende Informationen zum Thema Datalog finden sich in Teil D von [AHV] und in dem Überblicksartikel [Datalog] von Dantsin, Eiter, Gottlob und Voronkov

13. bis Do, 17.12.2020:

    Arbeiten Sie Folgendes durch:

    • Kapitel 4.1 und 4.2 des Vorlesungsskripts (bis inkl. Folie 153).

    Ergänzende Lektüre, in der Sie bei Interesse weiterlesen können (aber nicht müssen):

    • Kapitel 12 von [AHV]
    • Umfassende Informationen zum Thema Datalog finden sich in Teil D von [AHV] und in dem Überblicksartikel [Datalog] von Dantsin, Eiter, Gottlob und Voronkov

14. bis Di, 05.01.2021:

    Arbeiten Sie Folgendes durch:

    • Kapitel 4.2 und 4.3 des Vorlesungsskripts; schauen Sie sich dabei bitte auch die handschriftlichen Notizen zum Beweis von Satz 4.13 (Datalog zur Simulation von Turingmaschinen) an

    Ergänzende Lektüre, in der Sie bei Interesse weiterlesen können (aber nicht müssen):

    • Kapitel 12 von [AHV]
    • Umfassende Informationen zum Thema Datalog finden sich in Teil D von [AHV] und in dem Überblicksartikel [Datalog] von Dantsin, Eiter, Gottlob und Voronkov

15. bis Do, 07.01.2021:

    Arbeiten Sie Folgendes durch:

    • bis zum Ende von Kapitel 4.4 des Vorlesungsskripts; schauen Sie sich dabei bitte auch die handschriftlichen Notizen zum Beweis von Satz 4.13 (Datalog zur Simulation von Turingmaschinen) an

    Ergänzende Lektüre, in der Sie bei Interesse weiterlesen können (aber nicht müssen):

    • Kapitel 12 von [AHV]
    • Umfassende Informationen zum Thema Datalog finden sich in Teil D von [AHV] und in dem Überblicksartikel [Datalog] von Dantsin, Eiter, Gottlob und Voronkov

16. bis Di, 12.01.2021:

    Arbeiten Sie Folgendes durch:

    • bis zum Ende von Kapitel 4.4 des Vorlesungsskripts; arbeiten Sie dazu bitte auch Kapitel 12.5 von [AHV] durch.

    Ergänzende Lektüre, in der Sie bei Interesse weiterlesen können (aber nicht müssen):

    • Kapitel 12 von [AHV]
    • Umfassende Informationen zum Thema Datalog finden sich in Teil D von [AHV] und in dem Überblicksartikel [Datalog] von Dantsin, Eiter, Gottlob und Voronkov

17. bis Do, 14.01.2021:

    Arbeiten Sie Folgendes durch:

    • bis zum Ende von Kapitel 4.4 des Vorlesungsskripts; arbeiten Sie dazu bitte auch Kapitel 12.5 von [AHV] durch.

    Ergänzende Lektüre, in der Sie bei Interesse weiterlesen können (aber nicht müssen):

    • Kapitel 12 von [AHV]
    • Umfassende Informationen zum Thema Datalog finden sich in Teil D von [AHV] und in dem Überblicksartikel [Datalog] von Dantsin, Eiter, Gottlob und Voronkov

18. bis Di, 19.01.2021:

    Arbeiten Sie Folgendes durch:

    • bis zum Ende von Kapitel 4.4 des Vorlesungsskripts; arbeiten Sie dazu bitte auch Kapitel 12.5 von [AHV] durch.
    • Kapitel 5.1 und 5.2 des Vorlesungsskripts

    Ergänzende Lektüre, in der Sie bei Interesse weiterlesen können (aber nicht müssen):

    • Kapitel 12 von [AHV]
    • Umfassende Informationen zum Thema Datalog finden sich in Teil D von [AHV] und in dem Überblicksartikel [Datalog] von Dantsin, Eiter, Gottlob und Voronkov
    • Kapitel 8.1, 8.2 und 8.4 von [AHV]

19. bis Do, 21.01.2021:

    Arbeiten Sie Folgendes durch:

    • Kapitel 5.2 des Vorlesungsskripts

    Ergänzende Lektüre, in der Sie bei Interesse weiterlesen können (aber nicht müssen):

    • Kapitel 8.1, 8.2 und 8.4 von [AHV]

20. bis Di, 26.01.2021:

    Arbeiten Sie Folgendes durch:

    • Seiten 143-146 des Vorlesungsskripts

    Ergänzende Lektüre, in der Sie bei Interesse weiterlesen können (aber nicht müssen):

    • Kapitel 8.1, 8.2 und 8.4 von [AHV]

21. bis Do, 28.01.2021:

    Arbeiten Sie Folgendes durch:

    • Seiten 147-156 des Vorlesungsskripts

    Ergänzende Lektüre, in der Sie bei Interesse weiterlesen können (aber nicht müssen):

    • Kapitel 8.1, 8.2 und 8.4 von [AHV]
    • Kapitel 5.1 und 6.1 von [AHV]

22. bis Di, 02.02.2021:

    Arbeiten Sie Folgendes durch:

    • Seiten 157-175 des Vorlesungsskripts

    Ergänzende Lektüre, in der Sie bei Interesse weiterlesen können (aber nicht müssen):

    • Kapitel 5.1, 5.3 und 6.1 von [AHV]

23. bis Do, 04.02.2021:

    Arbeiten Sie Folgendes durch:

    • Seiten 174-180 des Vorlesungsskripts

    Ergänzende Lektüre, in der Sie bei Interesse weiterlesen können (aber nicht müssen):

    • Kapitel 5.3 von [AHV]

24. bis Di, 09.02.2021:

    Arbeiten Sie Folgendes durch:

    • Seiten 179-185 des Vorlesungsskripts

    Ergänzende Lektüre, in der Sie bei Interesse weiterlesen können (aber nicht müssen):

    • Kapitel 5.3 und 5.4 von [AHV]
    • zum Satz von Trakhtenbrot siehe Kapitel 9.1 von [L]

25. bis Do, 11.02.2021:

    Arbeiten Sie Folgendes durch:

    • Seiten 183-188 des Vorlesungsskripts

    Ergänzende Lektüre, in der Sie bei Interesse weiterlesen können (aber nicht müssen):

    • Kapitel 5.4 von [AHV]

26. bis Di, 16.02.2021:

    Arbeiten Sie Folgendes durch:

    • Seiten 192-197 des Vorlesungsskripts. ACHTUNG: Es wurde am 12.02.21 eine neue Version des Vorlesungsskripts hochgeladen (detaillierter Beweis von Lemma 7.17 und eine neue "Folgerung 7.18" inkl. Beweis).

    Ergänzende Lektüre, in der Sie bei Interesse weiterlesen können (aber nicht müssen):

    • Kapitel 5.4 und 6.3 von [AHV]

27. bis Do, 18.02.2021:

    Arbeiten Sie Folgendes durch:

    • Seiten 195-197 (also Kapitel 7.4) und Seiten 122-128 (also Teile von Kapitel 4.5) des Vorlesungsskripts.

    Ergänzende Lektüre, in der Sie bei Interesse weiterlesen können (aber nicht müssen):

    • Kapitel 5.4 und 6.3 von [AHV]
    • Umfassende Informationen zum Thema Datalog finden sich in Teil D von [AHV]

28. bis Di, 23.02.2021:

    Arbeiten Sie Folgendes durch:

    • Seiten 122-133 (also Kapitel 4.5) des Vorlesungsskripts.

    Ergänzende Lektüre, in der Sie bei Interesse weiterlesen können (aber nicht müssen):

    • Kapitel 5.4 und 6.3 von [AHV]
    • Umfassende Informationen zum Thema Datalog finden sich in Teil D von [AHV]

29. bis Do, 25.02.2021:

    Arbeiten Sie Folgendes durch:

    • Seiten 128-133 und Kapitel 8 des Vorlesungsskripts.

    Ergänzende Lektüre, in der Sie bei Interesse weiterlesen können (aber nicht müssen):

    • Kapitel 5.4 und 6.3 von [AHV]
    • Umfassende Informationen zum Thema Datalog finden sich in Teil D von [AHV]