|
Logik in der Informatik
Prof. Dr. Nicole Schweikardt |
|
In diesem Logbuch finden Sie (nach den Vorlesungen) Informationen zum Inhalt der einzelnen Vorlesungsstunden, die entsprechenden Teile des Skripts und gelegentlich auch Korrekturen und sonstige ergänzende Bemerkungen.
Am Montag, den 24.10.22, fand die Eröffnungsvorlesung ab 17:15 Uhr statt.
Kapitel 1: Einführung ins Thema; Organisatorisches (entlang der Webseite der Vorlesung);
Start mit Kapitel 2: Mathematische Grundbegriffe und Beweistechniken — heute: einige abkürzende Schreibweisen; Wertebereiche; Cantors naiver Mengenbegriff; die Russellsche Antinomie; der Barbier von Sonnenthal
Material: Kapitel 1 des Skripts zur Vorlesung (komplett) und Seiten 15-18 von Kapitel 2 des Skripts zur Vorlesung
Ergänzende Lektüre, in der Sie bei Interesse weiterlesen können (aber nicht müssen): [B] (komplettes Buch)
Weiter mit Kapitel 2: Mathematische Grundbegriffe und Beweistechniken — heute: extensionale und intensionale Beschreibungen von Mengen, Mengenalgebra, Mächtigkeit/Kardinalität von Mengen, Hilberts Hotel; Demonstration dazu, wie Lösungen von Übungsaufgaben in Moodle eingereicht werden können
Material: Seiten 19-28 von Kapitel 2 des Skripts zur Vorlesung
Ergänzende Lektüre, in der Sie bei Interesse weiterlesen können (aber nicht müssen): Kapitel 1 in [J]
Weiter mit Kapitel 2: Mathematische Grundbegriffe und Beweistechniken — heute: Potenzmenge, kartesische Produkte, Worte und Sprachen, Relationen, Funktionen, die Begriffe "injektiv", "surjektiv", "bijektiv"
Material: Seiten 28-39 von Kapitel 2 des Skripts zur Vorlesung
Ergänzende Lektüre, in der Sie bei Interesse weiterlesen können (aber nicht müssen): Kapitel 1 in [J]
Weiter mit Kapitel 2: Mathematische Grundbegriffe und Beweistechniken — heute: eine bijektive Funktion f: P(M) → Abb(M,{0,1}) von der Potenzmenge einer Menge M auf die Menge der Abbildungen von M nach {0,1}; die Identitätsfunktion, Permutationen und Multimengen; Beweise verstehen und selbst formulieren: Was sind Sätze und Beweise?, die Begriffe "Definition", "Lemma", "Korollar", "Folgerung" und "Proposition"; Beweistechniken "direkter Beweis", "Beweis durch Kontraposition" und "Beweis durch Widerspruch (indirekter Beweis)" (jeweils mit Beispielen solcher Beweise)
Material: Seiten 40-47 (bis direkt vor Satz 2.48) von Kapitel 2 des Skripts zur Vorlesung
Ergänzende Lektüre, in der Sie bei Interesse weiterlesen können (aber nicht müssen): Kapitel 1 in [J]; Kapitel 3, 6 und 7 in [MM] und [B] (komplettes Buch)
Weiter mit Kapitel 2: Mathematische Grundbegriffe und Beweistechniken — heute: Weitere Beispiele für "Beweis durch Widerspruch (indirekter Beweis)"; Cantors zweites Diagonalargument; das Induktionsprinzip sowie Beispiele für Beweise durch vollständige Induktion
Material: Seiten 47-56 (bis zum Ende von Abschnitt 2.4) von Kapitel 2 des Skripts zur Vorlesung
Ergänzende Lektüre, in der Sie bei Interesse weiterlesen können (aber nicht müssen): Kapitel 1 und 2.3-2.4 in [J]; Kapitel 3, 6 und 7 in [MM] und [B] (komplettes Buch)
Weiter mit Kapitel 2: Mathematische Grundbegriffe und Beweistechniken — heute: rekursive Definitionen von Funktionen und Mengen; die Fakultätsfunktion und die Fibonacci-Folge; Induktionsprinzip für rekursiv definierte Mengen; Palindrome
Material: Seiten 56-63 (bis zum Ende von Abschnitt 2.5) von Kapitel 2 des Skripts zur Vorlesung
Ergänzende Lektüre, in der Sie bei Interesse weiterlesen können (aber nicht müssen): Kapitel 1 und 2.3-2.4 in [J]; Kapitel 3, 6 und 7 in [MM] und [B] (komplettes Buch)
Weiter mit Kapitel 2: Mathematische Grundbegriffe und Beweistechniken — heute: Größenvergleich von Mengen: Gleichmächtigkeit von Mengen; Abzählbarkeit von Mengen; Cantors erstes Diagonalargument; Abzählbarkeit der folgenden Mengen: natürliche Zahlen, ganze Zahlen, rationale Zahlen, A* für jedes abzählbare Alphabet A; Überabzählbarkeit der Potenzmenge der natürlichen Zahlen und Überabzählbarkeit der Menge der reellen Zahlen; Nachweis der Existenz von nicht-berechenbaren Funktionen; Darstellung reeller Zahlen: Beweis, dass 0,999999... = 1 ist.
Material: Seiten 63-74 von Kapitel 2 des Skripts zur Vorlesung
Ergänzende Lektüre, in der Sie bei Interesse weiterlesen können (aber nicht müssen): Kapitel 1.4 in [J]
Abschluss von Kapitel 2: Mathematische Grundbegriffe und Beweistechniken — heute:
Details zur Darstellung reeller Zahlen; die geometrische Summenformel; Darstellung natürlicher Zahlen zur Basis n (für jede beliebige natürliche Zahl n > 1) und Eindeutigkeit der Darstellung; "Plus 1"-Rechnen bei Darstellungen von natürlichen Zahlen zur Basis n
Start mit Kapitel 3: Graphen und Bäume — heute: grundlegende Definitionen und Begriffe zu ungerichteten Graphen und gerichteten Graphen
Material: Seiten 74-80 von Kapitel 2 des Skripts zur Vorlesung und Seiten 81-86 von Kapitel 3 des Skripts zur Vorlesung
Ergänzende Lektüre, in der Sie bei Interesse weiterlesen können (aber nicht müssen): Kapitel 1.2 in [J]; Teile von Kapitel 0 und 8 in [D]; Teile von Kapitel 2.1, 2.4, 2.5 in [St]
Weiter mit Kapitel 3: Graphen und Bäume — heute: Beispiel zur Modellierung einer Straßenkarte durch einen gerichteten Graphen; verschiedene Arten zur Darstellung von Graphen (abstrakt, graphisch, durch Adjazenliste, durch Adjazenzmatrix); Wege und Kreise; azyklische Graphen; (starker) Zusammenhang und (starke) Zusammenhangskomponenten; Hamilton-Kreise und Hamilton-Wege; das Travelling Salesman Problem; das Königsberger Brückenproblem; Euler-Kreise und Euler-Wege; Satz über die Existenz von Euler-Kreisen und Euler-Wegen
Material: Seiten 86-97 von Kapitel 3 des Skripts zur Vorlesung
Ergänzende Lektüre, in der Sie bei Interesse weiterlesen können (aber nicht müssen): Kapitel 1.2 in [J]; Teile von Kapitel 0 und 8 in [D]; Teile von Kapitel 2.1, 2.4, 2.5 in [St]
Weiter mit Kapitel 3: Graphen und Bäume — heute: Satz über die Existenz von Euler-Kreisen und Euler-Wegen (Abschluss des Beweises); Begriffe zur Ähnlichkeit zweier Graphen (Teilgraphen, induzierte Teilgraphen, Gleichheit, Isomorphie); markierte Graphen und Multigraphen; Zuordnungsprobleme, Matchings, bipartite Graphen
Material: Seiten 97-106 von Kapitel 3 des Skripts zur Vorlesung
Ergänzende Lektüre, in der Sie bei Interesse weiterlesen können (aber nicht müssen): Kapitel 5 in [KBB]; Kapitel 1.2 in [J]; Teile von Kapitel 0 und 8 in [D]; Teile von Kapitel 2.1, 2.4, 2.5 in [St]
Weiter mit Kapitel 3: Graphen und Bäume — heute: Modellierung mit Hilfe von Konfliktgraphen; konfliktfreie Knotenmarkierung (Färbung), das 4-Farben-Problem; planare Graphen; chromatische Zahl; ungerichtete Bäume, Spannbäume
Material: Seiten 106-115 von Kapitel 3 des Skripts zur Vorlesung
Ergänzende Lektüre, in der Sie bei Interesse weiterlesen können (aber nicht müssen): Kapitel 5 in [KBB]; Kapitel 1.2 in [J]; Teile von Kapitel 0, 1, 3, 4 und 8 in [D]; Teile von Kapitel 2.1, 2.4, 2.5 in [St]
Weiter mit Kapitel 3: Graphen und Bäume — heute: Spannbäume; gerichtete Bäume, Binärbäume, Modellierungsbeispiele; einige spezielle Arten von Graphen: vollständiger Graph, vollständig bipartiter Graph; die Begriffe "reflexiv", "symmetrisch", "antisymmetrisch", "transitiv", "konnex"; Äquivalenzrelationen
Material: Seiten 115-129 von Kapitel 3 des Skripts zur Vorlesung
Ergänzende Lektüre, in der Sie bei Interesse weiterlesen können (aber nicht müssen): Kapitel 5 in [KBB]; Kapitel 1.2 in [J]; Teile von Kapitel 0, 1, 3, 4 und 8 in [D]; Teile von Kapitel 2.1, 2.4, 2.5 in [St]
Abschluss von Kapitel 3: Graphen und Bäume — heute:
Äquivalenzklassen; Ordnungsrelationen; der reflexive und transitive Abschluss der Knotenmenge eines Graphen; der Satz von Cantor-Bernstein-Schröder
Start mit Kapitel 4: Kombinatorik — heute:
Kombinatorische Abzählregeln (Gleichheitsregel, Summenregel, Zerlegungsregel, Produktregel); das Ziehen von Elementen aus einer Menge (mit Zurücklegen, ohne Zurücklegen, mit Berücksichtigung der Reihenfolge, ohne Berücksichtigung der Reihenfolge), Binomialkoeffizienten, Pascal'scher Rekurrenzsatz
Material: Seiten 129-137 von Kapitel 3 des Skripts zur Vorlesung und Seiten 139-144 von Kapitel 4 des Skripts zur Vorlesung
Ergänzende Lektüre, in der Sie bei Interesse weiterlesen können (aber nicht müssen): Kapitel 1 von [St]; Kapitel 3 von [J]; das Lehrbuch [C]
Weiter mit Kapitel 4: Kombinatorik — heute: Pascal'sches Dreieck, binomische Formel, eine Formel zum Ausrechnen des Binomialkoeffizienten, weitere Eigenschaften der Binomialkoeffiziente; Ziehen mit Zurücklegen und ohne Berücksichtigung der Reihenfolge; das Prinzip der Inklusion und Exklusion (Siebformel) inkl. Anwendungsbeispiel
Material: Seiten 144-152 von Kapitel 4 des Skripts zur Vorlesung
Ergänzende Lektüre, in der Sie bei Interesse weiterlesen können (aber nicht müssen): Kapitel 1 von [St]; Kapitel 3 von [J]; das Lehrbuch [C]
Weiter mit Kapitel 4: Kombinatorik — heute: Beweis der Siebformel; das Prinzip des doppelten Abzählens (inkl. Anwendungsbeispiele); das Schubfachprinzip (inkl. Anwendungsbeispiele)
Material: Seiten 150-159 von Kapitel 4 des Skripts zur Vorlesung
Ergänzende Lektüre, in der Sie bei Interesse weiterlesen können (aber nicht müssen): Kapitel 1 von [St]; Kapitel 3 von [J]; das Lehrbuch [C]
Weiter mit Kapitel 5: Diskrete Stochastik — heute: das Geburtstagsproblem (inkl. dessen Bezug zu Kollisionen beim Hashing); Zufallsvariablen; Erwartungswert; Linearität des Erwartungswerts
Material: Seiten 169-177 von Kapitel 5 des Skripts zur Vorlesung
Ergänzende Lektüre, in der Sie bei Interesse weiterlesen können (aber nicht müssen): Kapitel 11 und 12 von [J]
Weiter mit Kapitel 5: Diskrete Stochastik — heute: konkretes Zufallsexperiment zum "Geburtstagsproblem" (Ergebnis: unter den 58 Versuchsteilnehmer:innen gab es einen Tag, an 3 Personen Geburtstag haben und zwei weitere Tage, an denen 2 Personen Geburtstag haben); Varianz; Regeln zum Rechnen mit Varianzen; Nicht-Linearität der Varianz; Markov-Ungleichung; Tschebyscheff-Ungleichung; (stochastische) Unabhängigkeit von Ereignissen und Zufallsvariablen; Erwartungswert und Varianz von paarweise unabhängigen Zufallsvariablen; ein Beispiel zur Verwendung der Tschebyscheff-Ungleichung: "der Frosch" (inkl. Erläuterung des Bezugs zum "Zufallssurfer" und dem Page-Rank-Verfahren)
Material: Seiten 177-187 von Kapitel 5 des Skripts zur Vorlesung
Ergänzende Lektüre, in der Sie bei Interesse weiterlesen können (aber nicht müssen): Kapitel 11 und 12 von [J]
Abschluss von Kapitel 5: Diskrete Stochastik — heute:
Bedingte Wahrscheinlichkeiten, der Satz von Bayes, Anwendungsbeispiel: SARS-CoV-2 Antigen-Schnelltest; einige wichtige Wahrscheinlichkeitsräume: Urnenmodelle "mit/ohne Zurücklegen" und "mit/ohne Berücksichtigung der Reihenfolge", Produktexperimente, Bernoulli-Verteilung, Binomialverteilung, geometrische Verteilung; ein weiteres Beispiel: das Monty Hall Problem
Start mit Kapitel 6: Algebraische Strukturen — heute:
modulare Arithmetik: Teilbarkeitsregeln, Division mit Rest
Material: Seiten 188-197 von Kapitel 5 des Skripts zur Vorlesung; Seiten 199-201 von Kapitel 6 des Skripts zur Vorlesung
Ergänzende Lektüre, in der Sie bei Interesse weiterlesen können (aber nicht müssen): Kapitel 11 und 12 von [J]; Kapitel 4 von [J]
Weiter mit Kapitel 6: Algebraische Strukturen — heute: Kongruenz modulo n, Regeln zum Rechnen mit Kongruenzen, Vielfachsummendarstellung des ggT, Euklid'scher Hilfssatz und einfache Folgerungen daraus (u.a., dass "Wurzel 2" keine rationale Zahl ist), Repräsentantenmengen modulo n, Lösen einer Gleichung modulo n
Material: Seiten 201-207 von Kapitel 6 des Skripts zur Vorlesung
Ergänzende Lektüre, in der Sie bei Interesse weiterlesen können (aber nicht müssen): Kapitel 4 von [J]
Weiter mit Kapitel 6: Algebraische Strukturen — heute: Beispiel zum Lösen einer Gleichung modulo n, Euklidischer Algorithmus zur ggT-Berechnung, Fundamentalsatz der Arithmetik (Primfaktorzerlegung von Zahlen), kleiner Satz von Fermat, der Chinesische Restsatz, der Fingerabdrucksatz, Anwendung in der Kryptographie: RSA-Verschlüsselung
Material: Seiten 207-214 von Kapitel 6 des Skripts zur Vorlesung
Ergänzende Lektüre, in der Sie bei Interesse weiterlesen können (aber nicht müssen): Kapitel 4 von [J]
Abschluss von Kapitel 6: Algebraische Strukturen — heute: Anwendung in der Kryptographie: RSA-Signierung; Abschnitt "Gruppen, Ringe und Körper": Grundbegriffe zu Verknüpfungen, Halbgruppen, Monoide, neutrale Elemente, Inverse, Gruppen, viele Beispiele, die symmetrische Gruppe Sn, Untergruppen und Nebenklassen, der Satz von Lagrange, Ringe, Körper, Beispiele, der Restklassenring modulo n, der Körper mit p Elementen (für Primzahl p), Funktionenring, der Polynomring K[x]
Material: Seiten 214-225 von Kapitel 6 des Skripts zur Vorlesung
Ergänzende Lektüre, in der Sie bei Interesse weiterlesen können (aber nicht müssen): Kapitel 4 von [J]