lehre:ws1516:logik-und-diskrete-strukturen

Art	Wann	Wo	Beginn	Dozent
V4	Dienstag 10:15 - 11:45 Donnerstag 10:15 - 11:45	AVZ III / HS 1, HS 2 AVZ III / HS 1, HS 2	20. Oktober 2015	Röglin

Bei dieser Vorlesung handelt sich um die erste von drei Pflichtvorlesungen im Bereich der theoretischen Informatik, die im Bachelorstudiengang an der Universität Bonn vorgesehen sind. Die wesentlichen Themen dieser Vorlesung sind Logik, Automatentheorie und formale Sprachen. Zunächst werden wir aber einige mathematische Grundlagen besprechen, die für ein Studium der Informatik unerlässlich sind. Viele davon sind Ihnen wahrscheinlich bereits in der Schule begegnet. Dennoch werden wir uns hier die Zeit nehmen, sie zu wiederholen und zu vertiefen, da die sichere Beherrschung dieser Grundlagen eine wichtige Voraussetzung für jede Lehrveranstaltung der Informatik ist.

Datum	Inhalt	Literatur
20. Oktober	1 Einleitung 2 Mathematische Grundlagen 2.1 Mengen	Folien Skript
22. Oktober	2.1 Mengen (Fortsetzung) 2.2 Beweise 2.2.1 Aussagen 2.2.2 Implikationen und Äquivalenzen	Skript
27. Oktober	2.2.3 Direkte und indirekte Beweise 2.2.4 Vollständige Induktion	Skript
29. Oktober	2.2.4 Vollständige Induktion (Fortsetzung) 2.3 Quantoren 2.4 Relationen und Abbildungen 2.4.1 Relationen	Skript
3. November	2.4.1 Relationen (Fortsetzung) 2.4.2 Abbildungen	Skript
5. November	2.4.3 Äquivalenzrelationen	Skript
10. November	3 Endliche Automaten und formale Sprachen 3.1 Sprachen und Grammatiken 3.2 Endliche Automaten	Skript
12. November	3.2 Endliche Automaten (Fortsetzung) 3.2.1 Pumping-Lemma für endliche Automaten	Skript
17. November	3.2.2 Das Pumping-Lemma als Spiel	Skript
19. November	3.2.3 Nichtdeterministische endliche Automaten	Skript
24. November	3.2.3 Nichtdeterministische endliche Automaten (Fortsetzung) 3.2.4 Minimierung endlicher Automaten	Skript
26. November	3.2.4 Minimierung endlicher Automaten (Fortsetzung) 3.3 Reguläre Sprachen, endliche Automaten und reguläre Ausdrücke	Skript
01. Dezember	3.3 Reguläre Sprachen, endliche Automaten und reguläre Ausdrücke (Fortsetzung)	Skript
03. Dezember	3.3 Reguläre Sprachen, endliche Automaten und reguläre Ausdrücke (Fortsetzung) 4 Ausgewählte Themen der Mathematik 4.1 Abzählbare und überabzählbare Mengen	Skript
08. Dezember	4.1 Abzählbare und überabzählbare Mengen (Fortsetzung)	Skript
10. Dezember	4.1 Abzählbare und überabzählbare Mengen (Fortsetzung) 4.2 Abzählende Kombinatorik	Skript
15. Dezember	4.2 Abzählende Kombinatorik (Fortsetzung)	Skript
17. Dezember	4.3 Algebraische Strukturen	Skript
22. Dezember	4.3.1 Halbgruppen, Monoide und Gruppen	Skript
07. Januar	4.3.2 Ringe und Körper 4.3.3 Euklidischer Algorithmus	Skript
12. Januar	4.3.3 Euklidischer Algorithmus (Fortsetzung) 4.3.4 Chinesischer Restsatz	Skript
14. Januar	4.3.4 Chinesischer Restsatz (Fortsetzung) 4.3.5 RSA-Kryptosystem	Skript
19. Januar	4.3.5 RSA-Kryptosystem (Fortsetzung) 5 Einführung in die mathematische Logik 5.1 Aussagenlogik 5.1.1 Syntax 5.1.2 Semantik	Skript
21. Januar	5.1.2 Semantik (Fortsetzung)	Skript
26. Januar	5.1.3 Normalformen 5.1.4 Resolutionskalkül	Skript
28. Januar	5.1.4 Resolutionskalkül (Fortsetzung)	Skript
02. Februar	5.1.4 Resolutionskalkül (Fortsetzung) 5.2 Prädikatenlogik 5.2.1 Signaturen und Strukturen 5.2.2 Syntax	Skript
04. Februar	5.2.3 Semantik 5.2.4 Ausblick	Skript
09. Februar	Besprechung der Probeklausur	Skript
11. Februar	Besprechung der Probeklausur	Skript

Für das Bestehen der Übungen müssen insgesamt mindestens 50% der zu erreichenden Punkte bei den Übungsaufgaben erreicht werden und Lösungen von zwei Aufgaben müssen im Laufe des Semesters erfolgreich in den Tutorien präsentiert werden.
Eine Abgabe der Übungsaufgaben in Gruppen bis zu drei Studierenden ist möglich.
Die Übungszettel werden immer dienstags ausgegeben. Die Lösungen müssen eine Woche später um 10:15 Uhr im entsprechenden Briefkasten in der Römerstraße 164 abgegeben sein.
Die Lösungen müssen auf dem vorderen Blatt die Namen der Studierenden und deutlich erkennbar die Nummer der Übungsgruppe enthalten. Falls eine Abgabe aus mehreren Blättern besteht, müssen diese zusammen getackert sein.

	Wann	Wo	Beginn	Tutor
1	Montag 08:15 - 09:45	AVZ III / A7a	26. Oktober 2015	Florian Gläßer
2	Montag 10:15 - 11:45	AVZ III / A7a	26. Oktober 2015	Florian Gläßer
3	Montag 10:15 - 11:45	AVZ III / A301	26. Oktober 2015	Florian Nelles
4	Montag 16:15 - 17:45	AVZ III / A7a	26. Oktober 2015	Florian Nelles
5	Dienstag 14:15 - 15:45	AVZ III / A7a	27. Oktober 2015	Moritz Wiemker
6	Dienstag 16:15 - 17:45	AVZ III / A6b	27. Oktober 2015	Moritz Wiemker
7	Mittwoch 10:15 - 11:45	AVZ III / A7a	28. Oktober 2015	Geraldine Reichard
8	Mittwoch 14:15 - 15:45	AVZ III / A7a	28. Oktober 2015	Geraldine Reichard
9	Mittwoch 14:15 - 15:45	AVZ III / A301	28. Oktober 2015	Jan Hoeckendorff
10	Mittwoch 16:15 - 17:45	AVZ III / A301	28. Oktober 2015	Jan Hoeckendorff
11	Donnerstag 14:15 - 15:45	AVZ III / A7a	29. Oktober 2015	Lukas Heidemann
12	Donnerstag 16:15 - 17:45	AVZ III / A7a	29. Oktober 2015	Lukas Heidemann
13	Freitag 08:15 - 09:45	AVZ III / A301	30. Oktober 2015	Jannik Boos
14	Freitag 10:15 - 11:45	AVZ III / A301a	30. Oktober 2015	Jannik Boos
15	Freitag 12:15 - 13:45	AVZ III / A7a	30. Oktober 2015	Danny Rademacher
16	Freitag 14:15 - 15:45	AVZ III / A7a	30. Oktober 2015	Danny Rademacher

Präsenzblatt (Besprechung in KW 44, keine Abgabe)
Übungsblatt 1 (Besprechung in KW 45, Abgabe bis 27.10., 10:15 Uhr, im Briefkasten in der Römerstraße)
Übungsblatt 2 (Besprechung in KW 46, Abgabe bis 03.11., 10:15 Uhr, im Briefkasten in der Römerstraße)
Übungsblatt 3 (Besprechung in KW 47, Abgabe bis 10.11., 10:15 Uhr, im Briefkasten in der Römerstraße)
Übungsblatt 4 (Besprechung in KW 48, Abgabe bis 17.11., 10:15 Uhr, im Briefkasten in der Römerstraße)
Übungsblatt 5 (Besprechung in KW 49, Abgabe bis 24.11., 10:15 Uhr, im Briefkasten in der Römerstraße)
Übungsblatt 6 (Besprechung in KW 50, Abgabe bis 01.12., 10:15 Uhr, im Briefkasten in der Römerstraße)
Übungsblatt 7 (Besprechung in KW 51, Abgabe bis 08.12., 10:15 Uhr, im Briefkasten in der Römerstraße)
Übungsblatt 8 (Besprechung in KW 02, Abgabe bis 15.12., 10:15 Uhr, im Briefkasten in der Römerstraße)
Übungsblatt 9 (Besprechung in KW 03, Abgabe bis 12.01., 10:15 Uhr, im Briefkasten in der Römerstraße)
Übungsblatt 10 (Besprechung in KW 04, Abgabe bis 19.01., 10:15 Uhr, im Briefkasten in der Römerstraße)
Übungsblatt 11 (Besprechung in KW 05, Abgabe bis 26.01., 10:15 Uhr, im Briefkasten in der Römerstraße)
Übungsblatt 12 (Besprechung in KW 06, keine Abgabe)
Übungsblatt 13 (Besprechung in der Vorlesung, keine Abgabe)

Probeklausur (Besprechung in der Vorlesung, keine Abgabe)

Die Inhalte der Vorlesung finden sich in diesem Skript.

Logik und diskrete Strukturen

Termine

Inhalt

Übungen

Literatur