Logik und diskrete Strukturen

Termine

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

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
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

Übungen

  • 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
Montag 08:15 - 09:45  AVZ III / A7a  26. Oktober 2015  Florian Gläßer
Montag 10:15 - 11:45  AVZ III / A7a  26. Oktober 2015  Florian Gläßer
Montag 10:15 - 11:45  AVZ III / A301  26. Oktober 2015  Florian Nelles 
Montag 16:15 - 17:45  AVZ III / A7a  26. Oktober 2015  Florian Nelles 
Dienstag 14:15 - 15:45  AVZ III / A7a  27. Oktober 2015  Moritz Wiemker 
Dienstag 16:15 - 17:45  AVZ III / A6b  27. Oktober 2015  Moritz Wiemker 
Mittwoch 10:15 - 11:45  AVZ III / A7a  28. Oktober 2015  Geraldine Reichard 
Mittwoch 14:15 - 15:45  AVZ III / A7a  28. Oktober 2015  Geraldine Reichard 
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)

Literatur

Die Inhalte der Vorlesung finden sich in diesem Skript.

lehre/ws1516/logik-und-diskrete-strukturen.txt · Zuletzt geändert: 2017/04/27 13:47 von roeglin

Benutzer-Werkzeuge