■
Team
■
Teaching
Oberseminar der Theorie
■
Winter 2023
■
Summer 2023
■
Winter 2022
■
Summer 2022
■
Winter 2021
■
Summer 2021
■
Winter 2020
■
Summer 2020
■
Winter 2019
■
Summer 2019
■
Winter 2018
■
Summer 2018
■
Winter 2017
■
Summer 2017
■
Winter 2016
■
Summer 2016
■
Winter 2015
Ausgewählte Themen der Theoretischen Informatik
Automaten über unendlichen Objekten
Berechenbarkeit und Komplexität
Ergänzungen zu Mathematik I
Graphentheorie
Logik und Diskrete Strukturen
■
Summer 2015
■
Winter 2014
■
Summer 2014
■
Winter 2013
■
Summer 2013
■
Winter 2012
■
Summer 2012
■
Winter 2011
Former Semester
BSc, Master-, Student-, Diplomathesis
StuPro/ ProjektINF/ SoPra/ FaPra
Exam Archive
Standard Textbooks
Descriptive Theory
■
Research
■
Publications
 

Logik und Diskrete Strukturen

Vorlesung

Prof. Dr. Ulrich Hertrampf

MINT-Kolleg

Im Sommersemester 2016 bietet das MINT-Kolleg die Möglichkeit an den LuDS-Stoff zu wiederholen und den Übungsschein nachzumachen. Mehr Informationen finden sich auf den Seiten des MINT-Kollegs.

Scheinklausur

Die Scheinklausur findet am Mittwoch, den 27. Januar 2016 während des regulären Vorlesungstermins statt. Bitte melden Sie sich über Aufgabenblatt 20 im eClaus bis spätestens 16:00 Uhr am Mittwoch, den 20. Januar 2016 zur Scheinklausur an.

Aufgrund der hohen Teilnehmerzahl findet die Scheinklausur in zwei Hörsälen statt. Teilnehmer, deren Nachname mit A-M beginnt, schreiben im Raum V47.02. Alle anderen Teilnehmer (Nachname mit Anfangsbuchstaben N-Z) schreiben im Raum V57.01.

Die Ergebnisse der Scheinklausur können Sie über den Korrekturtext zu Aufgabenblatt 20 einsehen.

Besondere Ankündigungen

Die endgültige Scheinliste hängt aus. Bitte prüfen Sie, ob Ihre Matrikelnummer darauf aufgeführt ist. Dies ist auch dann wichtig, wenn Sie davon ausgehen den Schein nicht erhalten zu haben. Denn: Treten Sie zu einer angemeldeten Prüfung in der irrtümlichen Annahme die Zulassungsvoraussetzungen nicht zu erfüllen nicht an, kann dies dazu führen, dass die Prüfung als nicht bestanden gewertet wird.

Termine

Zeit Raum Termine
Do 15:45–17:15 V47.01 wöchtl. ab 15.10.
Mi 14:00–15:30 V47.02 wöchtl. ab 21.10    Keine Vorlesung am 20. Januar

Inhalt

Die ersten Vorlesungen sind dem ersten Kapitel aus Uwe Schönings Buch “Logik für Informatiker” gewidmet (Aussagenlogik).

Danach wollen wir uns kurz um die Prädikatenlogik der ersten Stufe kümmern (Kapitel 2 im Schöning-Buch).

Der Rest des Semesters wird durch Diskrete Strukturen (vorwiegend Kapitel 1-4 aus “Elemente der Diskreten Mathematik” von Diekert/Kufleitner/Rosenberg) ausgefüllt.

Vorlesungsplan und Folien

Die Einheiten der nächsten Vorlesung sind stets grün unterlegt.

Die zugreifbaren Folien werden entsprechend in der Vorlesung erarbeitet.

Insgesamt wird es 50 Einheiten geben (ohne Einheit 0) - diese werden durchnummeriert von 1 bis 50 und werden im Laufe des Semesters immer rechtzeitig in der folgenden Tafel erscheinen.

Einheit Datum Inhalt Folien
0 15.10. Vorstellung, Arbeitsweise pdf
1 21.10. Syntax, Semantik der Aussagenlogik, Verknüpfungstafeln pdf
2 21.10. Baumstruktur, Modelle, Gültigkeit und Erfüllbarkeit pdf
3 22.10. Wahrheitswertemethode, Übungen 2+3 pdf
4 22.10. Übungen 4-13 pdf
5 28.10. Semantische Äquivalenz, Ersetzbarkeitstheorem pdf
6 28.10. Äquivalenzen, Assoziativität und Klammerung pdf
7 29.10. KNF und DNF (Definition, Satz, Beweis) pdf
8 29.10. KNF und DNF aus Wahrheitstafel, Übungen pdf
9 04.11. Hornformeln, Markierungsalgorithmus pdf
10 04.11. Übungen, Zusammenfassung, Vorschau pdf
11 05.11. Der Endlichkeitssatz und sein Beweis pdf
12 05.11. Übungen zum Endlichkeitssatz, Vorschau: Resolution pdf
13 11.11. Resolution 1: Die Grundlagen des Verfahrens pdf
14 12.11. Resolution 2: Das Resolutionslemma pdf
15 12.11. Resolution 3: Der Resolutionssatz pdf
16 19.11. Resolution 4: Algorithmus und Herleitungen pdf
17 19.11. Prädikatenlogik: Syntax pdf
18 19.11. Prädikatenlogik: Semantik (NEU: Korrektur auf Folie 18.5) pdf
19 25.11. Beispiele, Modelle, Gültigkeit pdf
20 25.11. Normalformen pdf
21 26.11. Unentscheidbarkeit pdf
22 26.11. Herbrand-Theorie 1 pdf
23 02.12. Herbrand-Theorie 2 pdf
24 02.12. Prädikatenlogische Resolution (1) pdf
25 03.12. Prädikatenlogische Resolution (2) pdf
26 03.12. Zahlen, Strukturen, Homomorphismen pdf
27 09.12. Euklid und Bezout pdf
28 09.12. Modulare Arithmetik, Restklassenringe pdf
29 10.12. Der Chinesische Restsatz pdf
30 10.12. Kleiner Satz von Fermat, Primzahltest pdf
31 16.12. Einschub: Graphen (1: Grundbegriffe) pdf
32 17.12. Einschub: Graphen (2: Wege, Kreise, Euler) pdf
33 17.12. Einschub: Graphen (3: Eulerformel, Satz von Kuratowski) pdf
34 07.01. RSA: Das Verfahren pdf
35 07.01. RSA: Sicherheit, Eulers phi-Funktion pdf
36 13.01. Eigenschaften der phi-Funktion, Primzahlzertifikat pdf
37 13.01. Fibonacci-Zahlen pdf
38 14.01. Aufgaben und Zusammenfassung Kapitel 1 pdf
39 14.01. Wachstumsabschätzungen pdf
40 14.01. Primzahldichte pdf
41 21.01. Aufgaben und Zusammenfassung Kapitel 2 pdf
42 21.01. Diskrete Wahrscheinlichkeitsrechnung (1) pdf
43 21.01. Diskrete Wahrscheinlichkeitsrechnung (2) pdf
  27.01. Scheinklausur  
44 28.01. Binomialkoeffizienten und Partitionszahlen pdf
45 28.01. Catalan-Zahlen und Dyck-Wörter pdf
46 03.02. Saturierte Binärbäume und Catalan-Zahlen pdf
47 03.02. Suchbäume und ihre mittlere Höhe pdf
48 04.02. Der Satz von Ramsey (1) pdf
49 04.02. Der Satz von Ramsey (2) (NEU: Korrektur auf Folie 49.6) pdf
50 04.02. Aufgaben pdf

Ergänzungen

Webseite der Ergänzungen

Übungen

Lukas Fleischer, Jan Philipp Wächter

Die Anmeldung zu den Übungen erfolgt über das eClaus-System https://eclaus.informatik.uni-stuttgart.de/.
Benutzername und Passwort werden in der ersten Vorlesung bekannt gegeben.

Übungsgruppen

Die Übungen beginnen in der dritten bzw. vierten Semesterwoche und finden jeweils alle 14 Tage statt.

Gruppe Tutor Zeit Raum Besprechung
Blatt 1 Blatt 2 Blatt 3 Blatt 4 Blatt 5 Blatt 7
1 D. Tschechlov Mo 08:00-09:30 0.108 26.10. 09.11. 23.11. 07.12. 11.01. 25.01.
2

L. Fleischer
J. Wächter

 Mo 14:00-15:30 0.118 26.10. 09.11. 23.11. 07.12. 11.01. 25.01.
3 N. Wenzler Mi 08:00-09:30 0.118 28.10. 11.11. 25.11. 09.12. 13.01. 27.01.
4 P. Schroth Mi 17:30-19:00 0.124 28.10. 11.11. 25.11. 09.12. 13.01. 27.01.
5 T. Beeh Do 08:00-09:30 0.124 29.10. 12.11. 26.11. 10.12. 14.01. 28.01.
6 T. Dönicke Do 08:00-09:30 0.108 29.10. 12.11. 26.11. 10.12. 14.01. 28.01.
7 V. Klein Do 09:45-11:15 V38.03 29.10. 12.11. 26.11. 10.12. 14.01. 28.01.
8 V. Klein Do 11:30-13:00 0.457 29.10. 12.11. 26.11. 10.12. 14.01. 28.01.
9 T. Böpple Do 14:00-15:30 0.363 29.10. 12.11. 26.11. 10.12. 14.01. 28.01.
10 P. Schroth Fr 09:45-11:15 0.108 30.10. 13.11. 27.11. 11.12. 15.01. 29.01.
11 T. Rodestock Fr 11:30-13:00 0.447 30.10. 13.11. 27.11. 11.12. 15.01. 29.01.
12 T. Mantz Fr 15:45-17:15 0.124 30.10. 13.11. 27.11. 11.12. 15.01. 29.01.
13 D. Tschechlov Mo 08:00-09:30 0.108 02.11. 16.11. 30.11. 14.12. 18.01. 01.02.
14 D. Tschechlov Mo 14:00-15:30 0.118 02.11. 16.11. 30.11. 14.12. 18.01. 01.02.
15 N. Wenzler Mi 08:00-09:30 0.118 04.11. 18.11. 02.12. 16.12. 20.01. 03.02.
16 P. Schroth Mi 17:30-19:00 0.124 04.11. 18.11. 02.12. 16.12. 20.01. 03.02.
17 T. Beeh Do 08:00-09:30 0.124 05.11. 19.11. 03.12. 17.12. 21.01. 04.02.
18 T. Dönicke Do 08:00-09:30 0.108 05.11. 19.11. 03.12. 17.12. 21.01. 04.02.
19 V. Klein Do 09:45-11:15 V38.03 05.11. 19.11. 03.12. 17.12. 21.01. 04.02.
20 V. Klein Do 11:30-13:00 0.457 05.11. 19.11. 03.12. 17.12. 21.01. 04.02.
21 T. Böpple Do 14:00-15:30 0.363 05.11. 19.11. 03.12. 17.12. 21.01. 04.02.
22 P. Schroth Fr 09:45-11:15 0.108 06.11. 20.11. 04.12. 18.12. 22.01. 05.02.
23 T. Rodestock Fr 11:30-13:00 0.447 06.11. 20.11. 04.12. 18.12. 22.01. 05.02.
24 T. Mantz Fr 15:45-17:15 0.124 06.11. 20.11. 04.12. 18.12. 22.01. 05.02.

Übungsblätter

  • Blatt 1 – Die ursprüngliche Variante des Blattes enthielt bei Aufgabe 5b) (iii) einen Fehler: U muss auch die Menge bestehend aus der leeren Menge und 1 enthalten.
  • Blatt 2
  • Blatt 3
  • Blatt 4
  • Blatt 5
  • Blatt 6 (Bonusblatt) – Beachten Sie den Abgabetermin.
  • Blatt 7 – In der aktualisierten Version wurde die Formulierung von Aufgabe 5 präzisiert und es wurden Lösungshinweise hinzugefügt.

MC-Tests

Der siebte und letzte MC-Test steht jetzt im eClaus-System unter Blatt 17 zur Bearbeitung bereit.

Die bisherigen MC-Test finden Sie hier als PDF-Dateien:

Scheinkriterien

  • Bestehen der Scheinklausur am Ende des Semesters.
  • Mindestens 50% der Punkte in den schriftlichen Abgaben.
  • Mindestens 50% der Punkte in den MC-Test im eClaus-System.
  • Regelmäßige Anwesenheit und aktive Teilnahme an den Übungsgruppen (mindestens zweimal vorrechnen).

Hinweis:

Um an der Modulprüfung Theoretische Grundlagen der Informatik teilzunehmen, benötigen Sie einen Übungsschein in Logik und Diskrete Strukturen oder in Formale Sprachen und Automatentheorie (Vorlesung im 2. Semester).

Um an der Modulprüfung Logik und diskrete Strukturen teilzunehmen, benötigen Sie den Übungsschein in Logik und Diskrete Strukturen.

Literatur

Logik:

  • Uwe Schöning: Logik für Informatiker. 5. Auflage, Spektrum Akad. Verlag, 2000.

Diskrete Strukturen:

  • Volker Diekert, Manfred Kufleitner, Gerhard Rosenberger: Elemente der Diskreten Mathematik. Walter de Gruyter, 2013.
  • Angelika Steger: Diskrete Strukturen. Band 1, Springer, 2001.
  • J. K. Truss: Discrete Mathematics. 2. Auflage, Addison-Wesley, 1999.
  • Ronald L. Graham, Donald E. Knuth, Oren Patashnik: Concrete Mathematics. 2. Auflage, Addison-Wesley, 1994.

News

[Jun’23] The paper “Parallel algorithms for power circuits and the word problem of the Baumslag group” by Caroline Mattes and Armin Weiß has been accepted at Computational Complexity.

[Oct’22] The paper “Lower Bounds for Sorting 16, 17, and 18 Elements” by Florian Stober and Armin Weiß has been accepted at ALENEX 2023.

[Sep’22] The paper “Conelikes and Ranker Comparisons” by Viktor Henriksson and Manfred Kufleitner has been accepted at LATIN 2022.

[Sep’22] The paper “Improved Parallel Algorithms for Generalized Baumslag Groups” by Caroline Mattes and Armin Weiß has been accepted at LATIN 2022.

[Apr’22] The paper “Reachability Games and Parity Games” by Volker Diekert and Manfred Kufleitner has been accepted at ICTAC 2022.

[Apr’22] The paper “Satisfiability Problems for Finite Groups” by Pawel M. Idziak, Piotr Kawalek, Jacek Krzaczkowski and Armin Weiß has been accepted at ICALP 2022.

[Mar’22] The paper “The Power Word Problem in Graph Products” by Florian Stober and Armin Weiß was accepted at DLT 2022.

[Nov’20] Volker Diekert is Partner Investigator in the Australian ARC grant “Geodetic groups: foundational problems in algebra and computer science” at University of Technology Sydney.

[Apr’20] The paper “Groups with ALOGTIME-hard word problems and PSPACE-complete circuit value problems” by Laurent Bartholdi, Michael Figelius, Markus Lohrey and Armin Weiß has been accepted at CCC 2020.

[Apr’20] The paper “Hardness of equations over finite solvable groups under the exponential time hypothesis” by Armin Weiß has been accepted at ICALP 2020.

[Dec’19] The paper “An Automaton Group with PSPACE-Complete Word Problem” by Jan Philipp Wächter and Armin Weiß has been accepted at STACS 2020.

[Nov’19] Carlos Camino was awarded the stuvus Special Prize for exceptional commitment in teaching.

[Jun’19] The paper “The power word problem” by Markus Lohrey and Armin Weiß has been accepted at MFCS 2019.

[May’19] The paper “On the Average Case of MergeInsertion” by Florian Stober and Armin Weiß has been accepted at IWOCA 2019.

[Oct’18] The paper “Worst-Case Efficient Sorting with QuickMergesort” by Stefan Edelkamp and Armin Weiß has been accepted at ALENEX 2019.

[Jun’18] At CCC 2018, Lukas Fleischer received a Best Student Paper Award for his submission “On the Complexity of the Cayley Semigroup Membership Problem”.

[Jun’18] The paper “Testing Simon’s congruence” by Lukas Fleischer and Manfred Kufleitner was accepted at MFCS 2018.

[Jun’18] The paper “The Intersection Problem for Finite Semigroups” by Lukas Fleischer was accepted at DLT 2018.

[Apr’18] The paper “The isomorphism problem for finite extensions of free groups is in PSPACE” by Géraud Sénizergues and Armin Weiß was accepted at ICALP 2018.

[Apr’18] The paper “On the Complexity of the Cayley Semigroup Membership Problem” by Lukas Fleischer was accepted at CCC 2018.

[Jan’18] On March 24-29, 2019 Volker Diekert, Markus Lohrey, Olga Kharlampovich and Alexei Miasnikov will organize the Schloss Dagstuhl Seminar “Algorithmic Problems in Group Theory”.

[Dec’17] The paper “The Intersection Problem for Finite Monoids” by Lukas Fleischer and Manfred Kufleitner was accepted at STACS 2018.

[Jun’17] At the 12th International Computer Science Symposium in Russia (CSR), Lukas Fleischer and Manfred Kufleitner received a Best Paper Award for their publication “Green’s Relations in Finite Transformation Semigroups”, and Armin Weiss received a Best Paper Award for “The conjugacy problem in free solvable groups and wreath product of abelian groups is in $\text{TC}^0$ \text{TC}^0 “ which is joint work with Alexei Miasnikov and Svetla Vassileva.