Dies ist eine alte Version des Dokuments!


Logik und diskrete Strukturen

Termine

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

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.

Ort Inhalt Literatur
09. OktoberBegrüßung der Erstsemester
1 Einleitung
Foliensatz 1
Foliensatz 2
Skript
11. Oktober2 Mathematische Grundlagen
2.1 Mengen
Skript
16. Oktober2.2 Beweise
2.2.1 Aussagen
2.2.2 Implikationen und Äquivalenzen
2.2.3 Direkte und indirekte Beweise
Skript
18. Oktober2.2.3 Direkte und indirekte Beweise (Fortsetzung)
2.2.4 Vollständige Induktion
Skript
23. Oktober2.3 Quantoren
2.4 Relationen und Abbildungen
2.4.1 Relationen
Skript
25. Oktober2.4.2 Abbildungen \\2.4.3 ÄquivalenzrelationenSkript
30. Oktober2.4.3 Äquivalenzrelationen (Fortsetzung)
3 Endliche Automaten und formale Sprachen
3.1 Sprachen und Grammatiken
Skript
06. November3.1 Sprachen und Grammatiken (Fortsetzung)
3.2 Endliche Automaten
3.2.1 Pumping-Lemma für endliche Automaten
Skript
08. November3.2.1 Pumping-Lemma für endliche Automaten (Fortsetzung)
3.2.2 Das Pumping-Lemma als Spiel
Skript
13.November3.2.3 Nichtdeterministische endliche AutomatenSkript
15. November3.3 Reguläre Sprachen, endliche Automaten und reguläre AusdrückeSkript
20. November3.3 Reguläre Sprachen, endliche Automaten und reguläre Ausdrücke (Fortsetzung)Skript
22. November3.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. November4.1 Abzählbare und überabzählbare Mengen (Fortsetzung)Skript
29. November4.1 Abzählbare und überabzählbare Mengen (Fortsetzung)Skript
04. Dezember4.2 Abzählende Kombinatorik (Fortsetzung)
4.3 Algebraische Strukturen
Skript
06. Dezember4.3.1 Halbgruppen, Monoide und Gruppen
4.3.2 Ringe und Körper
Skript
11. Dezember4.3.2 Ringe und Körper (Fortsetzung)
4.3.3 Euklidischer Algorithmus und chinesischer Restsatz
Skript
13. Dezember4.3.3 Euklidischer Algorithmus (Fortsetzung)
4.3.4 Chinesischer Restsatz
Skript
18. Dezember4.3.5 RSA-KryptosystemSkript
08. Januar5 Einführung in die mathematische Logik
5.1 Aussagenlogik
5.1.1 Syntax
5.1.2 Semantik
Skript
10. Januar5.1.2 Semantik (Fortsetzung) \\5.1.3 NormalformenSkript
15. JanuarBesprechung der Probeklausur
17. JanuarBesprechung der Probeklausur
22. Januar5.1.4 ResolutionskalkülSkript
24. Januar5.1.4 Resolutionskalkül (Fortsetzung)
5.2 Prädikatenlogik
5.2.1 Signaturen und Strukturen
Skript
29. Januar5.2.1 Signaturen und Strukturen (Fortsetzung)
5.2.2 Syntax
5.2.3 Semantik
Skript
31. Januar5.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 Turor
1Montag 8:15 - 9:45AVZ III / A7aDennis den Brok
2Montag 10:15 - 11:45AVZ III / A7aDennis den Brok
3Montag 10:15 - 11:45AVZ III / A301Linus Boes
4Montag 16:15 - 17:45AVZ III / A7aPatrick Loka
5Dienstag 16:15 - 17:45AVZ III / A6bPia Kullik
6Mittwoch 8:15 - 9:45AVZ III / A7aKatharina Bauer
7Mittwoch 10:15 - 11:45AVZ III / A7aLinus Boes
8Mittwoch 14:15 - 15:45AVZ III / A7aPia Kullik
9Mittwoch 14:15 - 15:45AVZ III / A301Klara Reichard
10Mittwoch 16:15 - 17:45AVZ III / A301Klara Reichard
11Donnerstag 14:15 - 15:45AVZ III / A7aKatharina Bauer
12Donnerstag 16:15 - 17:45AVZ III / A7aPatrick Loka
13Freitag 8:15 - 9:45vAVZ III / A301Tobias Brunsch
14Freitag 10:15 - 11:45AVZ III / A301aTobias Brunsch
15Freitag 12:15 - 13:45AVZ III / A7aTobias Brunsch
16Freitag 14:15 - 15:45AVZ III / A7aTobias 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

  • 1. Klausur: 08.02.2013, 17:15 bis 18:45 Uhr, Hauptgebäude
  • Die Klausur findet in den Hörsälen I und X im Hauptgebäude der Universität statt. Vor Ort werden Listen ausgehägt, denen Sie entnehmen können, welchem Hörsaal Sie zugewiesen wurden. Bitte seien Sie spätestens um 17:00 Uhr dort. Denken Sie außerdem bitte daran, einen Lichtbildausweis mitzubringen.
  • 2. Klausur: 18.03.2013, 14:15 bis 15:45 Uhr, Hauptgebäude

Literatur

Die Inhalte der Vorlesung finden sich in diesem Skript, das während des Semesters kontinuierlich erweitert wurde.

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]
lehre/ws1213/logik-und-diskrete-strukturen.1381753924.txt.gz · Zuletzt geändert: 2014/03/21 16:24 (Externe Bearbeitung)

Benutzer-Werkzeuge