Logik und diskrete Strukturen

Logik und diskrete Strukturen (BA-INF 011)

Termine

Art	Wann	Wo	Beginn	LP	Dozent
V4	Dienstag 10:15 - 11:45 Dienstag 12:30 - 14:00	AVZ III / HS 1 AVZ III / HS 2	9. Oktober 2012	5,5	Röglin
	Donnerstag 10:15 - 11:45 Donnerstag 12:30 - 14:00	AVZ III / HS 1 AVZ III / HS 2			Röglin
Ü2	Termine		15. Oktober 2012	3,5	Bauer, Boes, Brunsch, den Brok, Israels, Kullik, Loka, Reichard

Aufgrund der großen Teilnehmerzahl wurde die Vorlesung dienstags und donnerstags an jeweils zwei Terminen angeboten.

Inhalt

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
9. Oktober	Begrüßung der Erstsemester 1 Einleitung	Foliensatz 1 Foliensatz 2 Skript
11. Oktober	2 Mathematische Grundlagen 2.1 Mengen	Skript
16. Oktober	2.2 Beweise 2.2.1 Aussagen 2.2.2 Implikationen und Äquivalenzen 2.2.3 Direkte und indirekte Beweise	Skript
18. Oktober	2.2.3 Direkte und indirekte Beweise (Fortsetzung) 2.2.4 Vollständige Induktion	Skript
23. Oktober	2.3 Quantoren 2.4 Relationen und Abbildungen 2.4.1 Relationen	Skript
25. Oktober	2.4.2 Abbildungen 2.4.3 Äquivalenzrelationen	Skript
30. Oktober	2.4.3 Äquivalenzrelationen (Fortsetzung) 3 Endliche Automaten und formale Sprachen 3.1 Sprachen und Grammatiken	Skript
6. November	3.1 Sprachen und Grammatiken (Fortsetzung) 3.2 Endliche Automaten 3.2.1 Pumping-Lemma für endliche Automaten	Skript
8. November	3.2.1 Pumping-Lemma für endliche Automaten (Fortsetzung) 3.2.2 Das Pumping-Lemma als Spiel	Skript
13. November	3.2.3 Nichtdeterministische endliche Automaten	Skript
15. November	3.3 Reguläre Sprachen, endliche Automaten und reguläre Ausdrücke	Skript
20. November	3.3 Reguläre Sprachen, endliche Automaten und reguläre Ausdrücke (Fortsetzung)	Skript
22. November	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
27. November	4.1 Abzählbare und überabzählbare Mengen (Fortsetzung)	Skript
29. November	4.2 Abzählende Kombinatorik	Skript
04. Dezember	4.2 Abzählende Kombinatorik (Fortsetzung) 4.3 Algebraische Strukturen	Skript
06. Dezember	4.3.1 Halbgruppen, Monoide und Gruppen 4.3.2 Ringe und Körper	Skript
11. Dezember	4.3.2 Ringe und Körper (Fortsetzung) 4.3.3 Euklidischer Algorithmus und chinesischer Restsatz	Skript
13. Dezember	4.3.3 Euklidischer Algorithmus (Fortsetzung) 4.3.4 Chinesischer Restsatz	Skript
18. Dezember	4.3.5 RSA-Kryptosystem	Skript
08. Januar	5 Einführung in die mathematische Logik 5.1 Aussagenlogik 5.1.1 Syntax 5.1.2 Semantik	Skript
10. Januar	5.1.2 Semantik (Fortsetzung) 5.1.3 Normalformen	Skript
15. Januar	Besprechung der Probeklausur
17. Januar	Besprechung der Probeklausur
22. Januar	5.1.4 Resolutionskalkül	Skript
24. Januar	5.1.4 Resolutionskalkül (Fortsetzung) 5.2 Prädikatenlogik 5.2.1 Signaturen und Strukturen	Skript
29. Januar	5.2.1 Signaturen und Strukturen (Fortsetzung) 5.2.2 Syntax 5.2.3 Semantik	Skript
31. Januar	5.2.3 Semantik (Fortsetzung) 5.2.4 Ausblick	Skript

Übungen

Für den Erhalt des Übungsscheins müssen insgesamt mindestens 50% der zu erreichenden Punkte bei den Übungsaufgaben erreicht werden und Lösungen von drei 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.

	Wann	Wo	Tutor
1	Montag 8:15 - 9:45	AVZ III / A7a	Dennis den Brok
2	Montag 10:15 - 11:45	AVZ III / A7a	Dennis den Brok
3	Montag 10:15 - 11:45	AVZ III / A301	Linus Boes
4	Montag 16:15 - 17:45	AVZ III / A7a	Patrick Loka
5	Dienstag 16:15 - 17:45	AVZ III / A6b	Pia Kullik
6	Mittwoch 8:15 - 9:45	AVZ III / A7a	Katharina Bauer
7	Mittwoch 10:15 - 11:45	AVZ III / A7a	Linus Boes
8	Mittwoch 14:15 - 15:45	AVZ III / A7a	Pia Kullik
9	Mittwoch 14:15 - 15:45	AVZ III / A301	Klara Reichard
10	Mittwoch 16:15 - 17:45	AVZ III / A301	Klara Reichard
11	Donnerstag 14:15 - 15:45	AVZ III / A7a	Katharina Bauer
12	Donnerstag 16:15 - 17:45	AVZ III / A7a	Patrick Loka
13	Freitag 8:15 - 9:45	AVZ III / A301	Rafel Israels
14	Freitag 10:15 - 11:45	AVZ III / A301a	Rafel Israels
15	Freitag 12:15 - 13:45	AVZ III / A7a	Tobias Brunsch
16	Freitag 14:15 - 15:45	AVZ III / A7a	Tobias Brunsch

Präsenzblatt (Besprechung in KW 42, keine Abgabe)
Übungsblatt 1 (Besprechung in KW 43, Abgabe bis 16.10., 14:00 Uhr, im Briefkasten in der Römerstraße)
Aufgabe 1.4 ist eine Zusatzaufgabe.
Übungsblatt 2 (Besprechung in KW 44, Abgabe bis 23.10., 14:00 Uhr, im Briefkasten in der Römerstraße)
Die Aufgaben 2.2, 2.3 (b) und 2.4 sind Zusatzaufgaben.
Übungsblatt 3 (Besprechung in KW 45, Abgabe bis 30.10., 14:00 Uhr, im Briefkasten in der Römerstraße)
Aufgabe 3.4 (b) ist eine Zusatzaufgabe.
Übungsblatt 4 (Besprechung in KW 46, Abgabe bis 06.11., 14:00 Uhr, im Briefkasten in der Römerstraße)
Übungsblatt 5 (Besprechung in KW 47, Abgabe bis 13.11., 14:00 Uhr, im Briefkasten in der Römerstraße)
Übungsblatt 6 (Besprechung in KW 48, Abgabe bis 20.11., 14:00 Uhr, im Briefkasten in der Römerstraße)
Übungsblatt 7 (Besprechung in KW 49, Abgabe bis 27.11., 14:00 Uhr, im Briefkasten in der Römerstraße)
Übungsblatt 8 (Besprechung in KW 50, Abgabe bis 04.12., 14:00 Uhr, im Briefkasten in der Römerstraße)
Übungsblatt 9 (Besprechung in KW 51, Abgabe bis 11.12., 14:00 Uhr, im Briefkasten in der Römerstraße)
Übungsblatt 10 (Besprechung in KW 02, Abgabe bis 18.12., 14:00 Uhr, im Briefkasten in der Römerstraße)
Übungsblatt 11 (Besprechung in KW 03, Abgabe bis 08.01., 14:00 Uhr, im Briefkasten in der Römerstraße)
Übungsblatt 12 (Besprechung in KW 04, Abgabe bis 15.01., 14:00 Uhr, im Briefkasten in der Römerstraße)
Übungsblatt 13 (Besprechung in KW 05, Abgabe bis 22.01., 14:00 Uhr, im Briefkasten in der Römerstraße)

Klausuren

Probeklausur
1. Klausur: 08.02.2013, 17:15 bis 18:45 Uhr, Hauptgebäude

Notenspiegel
2. Klausur: 18.03.2013, 14:15 bis 15:45 Uhr, Hauptgebäude

Literatur

Die Inhalte der Vorlesung finden sich in diesem Skript.

Weitere empfohlene Literatur:

[Blum10] Norbert Blum. Skript zur Vorlesung "Logik und diskrete Strukturen".
Universität Bonn, Wintersemester 2010/11.
[DK07] Hans Delfs, Helmut Knebl. Introduction to Cryptography: Principles and Applications.
ISBN 978-3540492436, 2. Auflage, Springer, 2007.
[HMU11] John E. Hopcroft, Rajeev Motwani, and Jeffrey D. Ullman. Einführung in Automatentheorie, Formale Sprachen und Berechenbarkeit. ISBN 978-3868940824, Pearson Studium, 2011.
[Grädel12] Erich Grädel. Skript zur Vorlesung „Mathematische Logik“
RWTH Aachen, Sommersemester 2011.
[Räsch09] Thoralf Räsch. Skript zur Vorlesung "Logik und diskrete Strukturen".
Universität Bonn, Wintersemester 2009/10.
[Schöning00] Uwe Schöning. Logik für Informatiker.
ISBN 978-3827410054, 5. Auflage, Spektrum Akademischer Verlag, 2000.
[Schöning08] Uwe Schöning. Theoretische Informatik - kurz gefasst.
ISBN 978-3827418241, 5. Auflage, Spektrum Akademischer Verlag, 2008.
[Schweikardt12] Nicole Schweikardt. Skript zur Vorlesung „Diskrete Modellierung“
Goethe-Universität Frankfurt am Main, Wintersemester 2012/13.
[Steger07] Angelika Steger. Diskrete Strukturen.
ISBN 978-3540466604, 2. Auflage, Springer, 2007.
[Wegener05] Ingo Wegener. Theoretische Informatik - eine algorithmenorientierte Einführung.
ISBN 978-3835100336, 3. Auflage, Teubner, 2005.

Literatur für die einzelnen Kapitel:

Kapitel 2: [Blum10], [Räsch09], [HMU11]
Kapitel 3: [HMU11], [Wegener05]
Kapitel 4: [Räsch09], [Steger07], [DK07]
Kapitel 5: [Grädel12], [Schöning00], [Schweikardt12]