Logik und Diskrete Strukturen
Bitte beachten Sie: Aktuelle Hinweise & Termine zur Veranstaltung finden Sie am rechten Rand dieser Vorlesungshomepage. Sie können dazu auch einen RSS-Feed abonnieren.
Wenn Sie jetzt am rechten Rand keine Termine & Nachrichten sehen, dann ändern Sie bitte Ihre Spracheinstellung mit einem Klick auf "Deutsch".
Inhalt
Das Modul führt in grundlegende mathematische Konzepte zum Umgang mit endlichen oder abzählbaren Strukturen ein sowie in grundlegende Konzepte der Logik. Unter anderem werden behandelt: Mengen, Relationen, Ordnungen, Modulare Arithmetik, Gruppen und Körper, Aussagenlogik und Prädikatenlogik, Sequenzenkalkül und Resolution, Gödels Unvollständigkeitssatz.
Organisation
- Umfang: 3+2 Semesterwochenstunden (6 ECTS für Bachelor Informatik und Informatik Nebenfach 30/60)
- Vorlesung: Prof. Dr. Martin Hofmann
- Übungen: Dr. Steffen Jost, Dr. Andreas Abel
- Tutoren/Korrektoren: Sophia Grundner-Culemann, Basil Karadeis, Christoph Kiesl, Christoph-Simon Senjak
Zeit und Ort
Veranstaltung | Zeit | Ort | Beginn |
---|---|---|---|
Vorlesung | Di, 12 - 14 Uhr | Hörsaal B U101 (Oettingenstr. 67) | 16.04.2013 |
Vorlesung | Mi, 8 - 10 Uhr | Hörsaal B U101 (Oettingenstr. 67) | 17.04.2013 |
Übung | Mo, 14 - 16 Uhr | Raum A 022 (Hauptgebäude) | 22.04.2013 |
Übung | Mo, 16 - 18 Uhr | Raum B 046 (Theresienstr. 39) | 22.04.2013 |
Übung | Mi, 16 - 18 Uhr | Raum A 022 (Hauptgebäude) | 24.04.2013 |
Übung | Mi, 18 - 20 Uhr | Raum A 022 (Hauptgebäude) | 24.04.2013 |
Planung
Da die Vorlesung trotz der gebuchten 4 Semesterwochenstunden nur den Umfang 3+2 hat, entfallen einige Vorlesungstermine. Die Übungen finden dagegen durchgehend statt. Zur Zeit ist für die Vorlesung folgende Planung vorgesehen. Die Angaben der Form (Sx.x.x) im ersten Teil beziehen sich auf das Buch von Steger. Der zweite Teil richtet sich nach dem Skriptum zur Vorlesung "Logik fuer Informatiker" im SS2008 http://www2.tcs.ifi.lmu.de/lehre/SS08/Logik/kap1-4.pdf.
Nr. | Datum | Thema | Hinweise |
1. | 16.04. | Organisation. Mengen, Relationen (Wdh. Lin.Alg.)(S0.1,S0.2). Es wurden die Übungsaufgaben 3, 5, 6, 7 aus der Vorlesung Lineare Algebra für Informatiker und Statistiker WS2012/13 vorgerechnet. Angaben und Musterlösungen finden sich dort. |
|
2. | 23.04. | Wdh. Äquivalenzrelationen, Abbildungen (Ü 10, 12). Beweise, vollständige Induktion (S0.3) | |
3. | 24.04. | Bsp zur vollst Induktion. | |
4. | 30.04. | Kombinatorik (S1.3.1-1.3.3), Ordnungen und Verbände. (S1.4) | |
5. | 07.05. | Verbände (S1.4) ohne Distributivität. Graphen (S2.1) Definition und Satz 2.1 | |
6. | 08.05. | Graphen (S2.2, S2.4, ohne Matching). | |
7. | 15.05. | Wdh. Graphen, planare Graphen, Primzahlen, ggT, kgV, Euklidischer Algorithmus (S3.2.2) | |
8. | 28.05. | Modulare Arithmetik, Chinesischer Restesatz. In der Vorlesung wurde konstruktiv durch Induktion ueber k bewiesen, dass stets eine Lsg existiert. Mit dem Argument surj=inj bei gleicher Maechtigkeit wurde daraus die Eindeutigkeit gefolgert (dies analog zum Beweis bei Steger). (S3.2.1, S3.2.3). | |
9. | 29.05. | Polynome (S3.3.1). Gruppen (S5.3.1 1.Teil (Beispiele, aber noch keine Ordnungen) | |
10. | 18.06. | Gruppen: Elementordnungen einschl Korollar 5.56 aber mit einfacherem Beweis (ord(a)=m und ord(b)=n. Falls ggT(m,n)=1, so ist ord(ab)=mn. Ansonsten ist ord(a^ggT(m,n)b)=kgV(m,n). Also existiert stets ein Gruppenelement x mit ord(x)=kgV(m,n). 5.56 folgt unmittelbar. (S5.3.1). Untergruppen (S5.3.2) ohne "Satz von Euler", stattdessen "Satz von Fermat" (S3.2.4). Endliche Koerper: Definitionen und Beispiele (S5.4.1), noch ohne Satz 5.8.4. | |
11. | 19.06. | Endliche Körper in Auszügen: Die Sätze 5.8.4 (Existenz primitiver Elemente). 5.9.2 (Konstruktion von Körpern mit irreduziblem Polynom) und 5.9.3. (Klassifikation der endlichen Körper) wurde behandelt. Die korrigierte Bestimmung eines Inversen zu ax+b in Q[x]/x2-2 findet sich hier. |
|
12. | 25.06. | Aussagenlogik: Einführung, Syntax, Semantik informell. Modellierung mit Aussagenlogik. Skript bis Seite 10 | |
13. | 26.06. | Semantik mit Belegungen, Äquivalenz, Boole'sche Algebra, Allgemeingültigkeit, Erfüllbarkeit, KNF. Skript bis Seite 15, aber noch ohne DNF. | |
14. | 02.07. | DNF, Formel aus Wahrheitstafel konstruieren, Sequenzenkalkül zur Haelfte, Demo PVS. Skript bis Seite 21 + Regeln für \/ und /\. | |
15. | 03.07. | Sequenzenkalkül Korrektheit und Vollständigkeit, Resolution. Skript bis Seite 29. Kompaktheit wurde noch nicht behandelt. | |
16. | 09.07. | Resolution fertig, Kompaktheit anders als im Skript über Resolution bewiesen. Prädikatenlogik: Motivation, Syntax. Skript bis S. 37 | |
17. | 10.07. | Syntax und Semantik der Prädikatenlogik Skript bis S. 41 | |
18. | 16.07. | Sequenzenkalkül für die Prädikatenlogik. Beispiele sowohl an Tafel als auch mit PVS. Korrektheit und Vollständigkeit (Beweise nur mündlich grob skizziert. Kommen nicht in der Klausur dran). | |
19. | 17.07. | Pränex-Normalform, Kompaktheit, Satz von Herbrand, Resolution für die Prädikatenlogik |
Hinweis:
Da sich im Vergleich zum letzten Jahr einige inhaltliche Änderungen an dieser Veranstaltung ergeben haben, sind die Vorlesungsvideos des letzten Jahres leider nur eingeschränkt zu empfehlen.
Übungen
Das wöchentliche Übungsblatt wird jeweils am Freitag per UniworX zum Download erscheinen. Die Aufgaben sind üblicherweise in Präsenzaufgaben und Hausaufgaben unterteilt. Eine aufmerksame Verfolgung der Vorlesung sollte Ihnen als Vorbereitung für die Präsenzaufgaben ausreichen. Die Präsenzaufgaben sind zum herumprobieren gedacht. Falls bei Präsenzaufgaben mal stecken bleiben sollten, was sicher mal vorkommen wird, so diskutieren Sie das Problem mit Ihren Kommilitonen. Bei hartnäckigen Problemen oder Unklarheiten fragen Sie einfach Ihren Übungsgruppen-Tutor oder Assistenten. Lernen Sie daraus!
Die Hausaufgaben müssen Sie dagegen alleine bearbeiten, was ohne größere Schwierigkeiten möglich sein sollte. Ihre Lösungen zu den Hausaufgaben müssen Sie üblicherweise innerhalb einer Woche, also bis Montag 8:00h morgens, mit UniworX abgeben. Zur Abgabe der Hausaufgaben ist eine Anmeldung in UniworX bei der entsprechenden Übungsgruppe Vorlesung notwendig. Ungefähr eine Woche nach Ende des Abgabezeitraums sollte Ihre Abgaben korrigiert worden sein; die Korrektur erhalten Sie ebenfalls uber UniworX. Hinweise zum Klausurbonus finden Sie im Abschnitt Klausur.
Klausur
Erstklausur
Nachholklausur
- Anmeldezeitraum: ab sofort bis spätestens 15.09.2013 per UniworX. Eine Anmeldung ist zur Teilnahme zwingend erforderlich!
- Termin: Montag, 07.10.2013 16-19h. Die Bearbeitungszeit beträgt 120 Minuten.
- Ort: Theresienstr. 39
- Raumeinteilung: Entsprechend des Anfangsbuchstabens Ihres Nachnamens
- A-G: B051
- H-Z: C123
Hinweise zum Klausurablauf
- Eine Klausuranmeldung per UniworX ist zur Teilnahme zwingend erforderlich.
- Jeder Student muss einen gültigen Lichtbildausweis und seinen Studentenausweis mitbringen.
- Es sind keine Hilfsmittel zugelassen. Am Platz darf sich nur Schreibzeug und eventuell ein paar Nahrungsmittel befinden. Papier wird von uns gestellt und darf nicht mitgebracht werden. Taschen und Jacken müssen vorne an der Tafel abgelegt werden. Sollte jemand ein Telefon, mp3-Player, oder Ähnliches am Platz haben, ist das ein Täuschungsversuch, der dem Prüfungsausschuss gemeldet wird. Sollte ein Telefon klingeln, ist das eine Störung des Prüfungsablaufs und hat den Ausschluss von der weiteren Teilnahme zur Folge.
- Gehen Sie rechtzeitig vor Beginn gemäß der Raumeinteilung in Ihren zugewiesenen Raum! Die Raumeinteilung finden Sie etwas weiter oben auf dieser Webseite.
Hausaufgabenklausurbonus
Literatur
- Angelika Steger: Diskrete Strukturen. Band 1: Kombinatorik, Graphentheorie, Algebra.
2. Auflage, Springer 2007, 978-3-540-46660-4
In der Studentenbibliothek sowie in der Mathematik-Bibliothek sind einige Exemplare des Buchs vorhanden. Es gibt auch eine Online-Version. Voraussetzung für die Leseberechtigung der Online-Version ist, dass der Zugriff über eine MWN-Verbindung (Münchner Wissenschaftsnetz) erfolgt und passende Browser-Einstellungen konfiguriert sind. Auf den CIP-Rechnern des Instituts für Informatik sind das normalerweise die Standardeinstellungen. Auf dem eigenen Rechner kann man ein VPN-Client-Programm installieren, um auch von außerhalb über eine MWN-Verbindung zugreifen zu können. - Martin Hofmann: Vorlesungsskript zur Vorlesung "Logik für Informatiker"
Weitere Informationen
- Fragen zur Vorlesung können in einem Diskussionsforum bei die-informatiker.net diskutiert werden.
Artikelaktionen