Prüfungseinsicht
Die Ergebnisse hängen am schwarzen Brett des FMI aus. Dieses befindet sich neben Raum 1.101. Bitte beachten Sie den Aushang mit Hinweisen zu Prüfungsergebnissen.
Am Dienstag, den 24. September 2019, finden folgende Prüfungseinsichten im Raum 0.124 statt:
| Nummer | Titel | Termin |
|---|---|---|
| 2353100000 | Automaten und Formale Sprachen | ab 11 Uhr |
| 1207100000 | Automaten und Formale Sprachen (für Mathematiker) | ab 11 Uhr |
| 7281100000 | Formale Sprachen und Automatentheorie für die Maschinelle Sprachverarbeitung | ab 14 Uhr |
| 4569100000 | Logik und Diskrete Strukturen | ab 11 Uhr |
| 1094100000 | Theoretische Grundlagen der Informatik | ab 11 Uhr |
| 7862100000 | Theoretische Informatik I | ab 14 Uhr |
Bitte bringen Sie Ihren Studienausweis mit und beachten Sie den Leitfaden für Prüfungseinsichten der Universität.
Vorlesung
Termine
| Zeit | Raum | Termine |
|---|---|---|
| Mo 14:00–15:30 | V38.04 | 9.4. bis 11.6., 9.7., 16.7. |
| Do 17:30–19:00 | V38.04 | 12.4., 19.4. und 5.7. |
- Mit Nachfragen (und ggf. Korrekturen) zum Scheinstatus wenden Sie sich bitte direkt an Herrn Wächter.
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 27 Einheiten geben (ohne Einheit 0) - diese sind durchnummeriert von 1 bis 27 und stehen bereits jetzt komplett in der folgenden Tafel zur Verfügung.
| Einheit | Datum | Inhalt | Folien |
|---|---|---|---|
| 0 | 09.04. | Vorstellung, Arbeitsweise | |
| 1 | 09.04. | Syntax, Semantik der Aussagenlogik, Baumstruktur, Gültigkeit... | |
| 2 | 12.04. | Wahrheitswertemethode, Übungen | |
| 3 | 12.04. | Semantische Äquivalenz, Ersetzbarkeitstheorem | |
| 4 | 16.04. | Normalformen: KNF und DNF | |
| 5 | 16.04. | Hornformeln, Markierungsalgorithmus | |
| 6 | 19.04. | Der Endlichkeitssatz | |
| 7 | 19.04. | Resolution | |
| 8 | 23.04. | Der Resolutionssatz | |
| 9 | 23.04. | Resolutionsalgorithmus, Grundbegriffe der Prädikatenlogik | |
| 10 | 30.04. | Semantik der Prädikatenlogik | |
| 11 | 30.04. | Normalformen, Substitution, Skolemformel | |
| 12 | 07.05. | Herbrand-Theorie | |
| 13 | 07.05. | Resolution: Grundresolutionssatz, Prädikatenlogische Resolution | |
| 14 | 14.05. | Zahlen, Strukturen, Homomorphismen, Euklid, Bezout | |
| 15 | 14.05. | Modulare Arithmetik | |
| 16 | 28.05. | Chinesischer Restsatz, Kleiner Satz von Fermat | |
| 17 | 28.05. | Graphen, Eulerwege und -kreise | |
| 18 | 04.06. | Eulerformel, Satz von Kuratowski | |
| 19 | 04.06. | RSA-Verfahren, Satz von Euler | |
| 20 | 11.06. | Eulers Phi-Funktion, Fibonacci-Zahlen | |
| 21 | 11.06. | Fibonacci-Zahlen mit goldenem Schnitt, ggT, Aufgaben | |
| 22 | 05.07. | Wachstum, Primzahldichte, Bertrand'sches Postulat | |
| 23 | 05.07. | Diskrete Wahrscheinlichkeitsrechnung (1) | |
| 24 | 09.07. | Diskrete Wahrscheinlichkeitsrechnung (2) | |
| 25 | 09.07. | Kombinatorik | |
| 26 | 16.07. | Binärbäume | |
| 27 | 16.07. | Satz von Ramsey |
Vortragsübung
Die Vortragsübung findet an folgenden Terminen jeweils von 17:30 bis 19:00 im Hörsaal 38.04 statt. Zur Teilname benötigen sie Papier und einen Stift.
| Datum | Themen | Material |
|---|---|---|
| 26.04. | Wahrheitstafeln, Komplexität, Induktion, Äquivalenz, Normalformen | Blatt 1 |
| 03.05. | Hornformeln, AL Resolution, Strukturen und Modelle | Blatt 2 |
| 17.05. | Skolemform, Herbrand-Theorie, Unifikation, PL Resolution | Blatt 3 |
| 07.06. | Gruppen, Untergruppen, Homomorphismen | Blatt 4 |
| 14.06. | Nebenklassen, Quotientengruppen, Satz von Lagrange | Blatt 5 |
| 21.06. | Modulare Arithmetik, Euklidischer Algorithmus, Chinesischer Restsatz | Blatt 6 |
| 28.06. | Probabilistische Primzahl Tests | Blatt 7 |
Praktisches Material zum Selbststudium:
Übungen und Übungsschein
Zur Teilnamhe an Vorlesung oder Vortragsübung brauchen Sie sich nicht anzumelden.
Die Anmeldung zu den Übungen erfolgt über das Campus System.
Diese sind dort als LV 020800501 Theoretische Grundlagen der Informatik: Logik und Diskrete Strukturen hinterlegt.
Der Anmeldezeitraum ist Donnerstag 19.04. 00:00 bis Sonntag 22.04. 23:59.
Die Abgabe der schriftlichen Aufgaben muss bis zum festen Abgabetermin in papierform erfolgen. Abgabeblätter müssen geheftet sein und klar die (bis zu drei) Bearbeiter (Name und Matrikelnummer), die Übungsgruppe (Nummer und Tutorname) und Aufgabennummern nennen. Abgaben, die nicht frist- oder formgerecht erfolgen, werden nicht berücksichtigt. Die Abgabe erfolgt durch Einwurf in das entsprechende Fach der Abgabeschräke (Mitte 1.OG des Informatikgebäudes V38). Lösungen müssen als vollständige Sätze oder Argumentationsketten ausformuliert sein. Bewertet wird der Schrieb Ihres Lösungswegs und nicht nur ein Endergebnis. Plagiate führen zur Bewertung von 0 Punkten aller schriftlichen Aufgaben des Blattes.
Durch votieren von Aufgaben zum Beginn des Besprechungstermins (gegenüber Ihrem Tutor) erklären Sie sich bereit, die jeweilige Aufgabe an der Tafel zu lösen.
Unvermögen, votierte Aufgaben im Besprechungstermin vorzurechnen, führt zur Bewertung von 0 Punkten aller Votieraufgaben des Blattes.
Insbesondere müssen Sie zum Votieren im Besprechungstermin ihrer Übungsgruppe anwesend sein.
| Blatt 1 | Blatt 2 | Blatt 3 | Blatt 4 | Blatt 5 | |
|---|---|---|---|---|---|
| Ausgabe | Blatt 1 | Blatt 2 | Blatt 3 | Blatt 4 | Blatt 5 |
| Abgabe | 13:15 Fr. 4.05. | 8:00 Mo. 28.05. | 13:15 Fr. 8.06. | 13:15 Fr. 22.06. | 13:15 Fr. 06.07. |
Die Übungsgruppentermine finden Sie in der folgenden Tabelle:
| Gr. | Tutor | Zeit | Raum | Besprechung | ||||||
|---|---|---|---|---|---|---|---|---|---|---|
| Blatt 1 | Blatt 2 | Blatt 3 | Blatt 4 | Blatt 5 | ||||||
| 1 | T. Rodestock | Di 8:00-9:30 | 0.124 | 08.05. | 29.05. | 12.06. | 26.06. | 10.07. | ||
| 2 | T. Rodestock | Di 8:00-9:30 | 0.124 | 15.05. | 05.06. | 19.06. | 03.07. | 17.07. | ||
| 3 | T. Rodestock | Mi 8:00-9:30 | 0.108 | 09.05. | 30.05. | 13.06. | 27.06. | 11.07. | ||
| 4 | T. Rodestock | Mi 8:00-9:30 | 0.108 | 16.05. | 06.06. | 20.06. | 04.07. | 18.07. | ||
Scheinkriterien
Wer alle der folgenden Bedingungen erfüllt, erhält einen Übungsschein:
- 60% der maximal erreichbaren Punkte der schriftlich abzugebenden Übungsaufgaben
- 60% der maximal erreichbaren Punkte der Votieraufgaben
- mindestens einmal Vorrechnen im Besprechumgstermin
Hinweise:
Um an der Modulprüfung Theoretische Grundlagen der Informatik teilzunehmen, benötigen Sie einen Übungsschein in Formale Sprachen und Automatentheorie oder in Logik und Diskrete Strukturen.
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.