Zur Startseite der Abteilung Theoretische Informatik

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

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.