| 1 | 15.04.02 | Wegenerbuch, Kapitel 1.3 bis Seite 11 Def. 1.3.5. Plus Definition 1.2.1 Seite 5. Plus Rechenregeln aus Satz 2.1.2 (Seite 25). Plus Definition symmetrische Funktionen, monotone Funktionen. (Buch: Definition 2.9.1 und 2.9.4. auf Seite 61/62). |
||
| 2 | 17.04.02 | Wegenerbuch, Seite 11 Rest sowie Seite 12 bis zur 6. Zeile von unten. Definition der Komplexitätsklassen P/poly (S. 18, Def. 1.5.1), NCk sowie ACk (Def. 1.5.2, 1.5.4) mit Beispielfkt. Kapitel 2.1 ("Rechenregeln und Normalformen") ohne die Definition/Bemerkung 2.1.7/2.1.8 (duale Fkt. betreffend). Definition 2.2.3 (Monome, sowie Begriffe Verkürzung/echte Verkürzung, sowie Polynome.). | ||
| 3 | 22.04.02 | Beweis, dass RSE eindeutig, beendet. Einfache Vereinfachungsregeln bei Polynomen vorgeführt sowie Kostenmaße definiert, Implikant, Primimplikant definiert, ( vergleiche Wegener-Buch Kapitel 2.2). Gezeigt, dass Funktion, die von x nicht abhängt, die Eigenschaft hat, dass alle PIs von f weder x noch x-quer enthalten. (Nicht im Buch enthalten). Beweis, dass monotone Funktionen nur positive Monome als Primimplikanten haben (Satz 2.9.2 im Buch). Primimplikanten der Parityfunktion untersucht und gezählt. Mit PLAs begonnen. | ||
| 4 | 24.04.02 | Kapitel 2.2 (PLAs) beendet. Kapitel 2.3: Quine-McCluskey-Algorithmus erklärt und als korrekt bewiesen. Beispiellauf von Quine-McCluskey auf Beispielfunktion. | ||
| 5 | 29.04.02 | Implementierung von Quine-McCluskey, Laufzeitanalyse, Funktion Mittleres
Drittel als Bsp. einer Fkt. mit sehr vielen PIs. Definition Pinup-Polynome,
Subfunktion, Shannon-Zerlegung, Beweis des "UND-Lemmas" (siehe Aufschrieb Baummethode) |
||
| - | 01.05.02 | Feiertag | ||
| 6 | 06.05.02 | Wiederholung der Baummethode. Nachgelieferter Beweis des "ODER-Lemmas". (Siehe Begleitmaterial.) Methode des iterierten Konsensus inkl. Korrektheitsbeweis und Beispiel. (Für den Beweis zum iterierten Konsensus siehe Begleitmaterial.) | ||
| 7 | 08.05.02 | Nachweis, dass PI-Berechnung NP-hartes Problem ist. (Da 3SAT sonst lösbar). Satz von McMullen/Shearer: Fkt. mit wenig Monomen dargestellt, aber mit vielen PIs. Fkt., wo Baummethode exponentielle Rechenzeit hat und Fkt., wo Iterierter Konsensus exp. Rechenzeit hat. Def. PI-Tafel, Reduktionsregeln für PI-Tafel, reduzierte PI-Tafel. Untere und obere Schranken für Branch-and-Bound angegeben. (Buch: Satz 2.4.1 S. 39, Satz 2.4.8 S. 43, Satz 2.4.14, Beginn Kapitel 2.5) | ||
| 8 | 13.05.02 | Branch-and-Bound beendet und als Bsp. auf MD3 angewendet. Def. Kernimplikant und Überdeckung von Monomen durch Polynome. Subfunktion fm def. Definition der Mengen U und MU, auch am Beispiel. Rekursiver Algorithmus zur Berechnung von MU beschrieben inkl. Korrektheitsbeweis. | ||
| 9 | 15.05.02 | Definition Überdeckungsfunktion, (UF, UF*), Def. partiell def. Funktion, Erweiterungen von part. def. Fkt., Ampelbeispiel, Minimalpolynomberechnung für partiell definierte Funktionen. | ||
| - | 20.05.02 | Feiertag | ||
| 10 | 22.05.02 | Funktionen mit mehreren Outputs: MPIs definiert, Beweis, dass Minimalpolynome für Fkt. mit mehreren Outputs nur MPIs benutzen, anschließend Definition Intervallfunktionen, Intervalldarstellung von symm. Funktionen, Anzahl PIs im Minimalpolynom für Intervallfunktionen. Im Buch ist das Kapitel 2.8, sowie Kapitel 2.9 ab Def. 2.9.4 einige der Dinge, die bis S. 65 vorkommen. | ||
| 11 | 27.05.02 | Beweis, dass Minpoly für symm. f sich aus Minpolys für die Intervallfunktionen in der Intervalldarst. von f zusammensetzt. Anzahl PIs im Minpoly von MD verglichen mit Anzahl der PIs von MD. Push-Pop-Algorithmus (ohne Korrektheitsbeweis). Minpolyberechnung bei monotonen Funktionen. Entspricht im Buch: Kapitel 2.9. | ||
| 12 | 29.05.02 | Beweis, dass Entscheidung "Polynom stellt monotone Fkt. dar" NP-hart. Bsp., dass manchmal schon Tiefe 3 zu viel besserer Größe führt als Minimalpolynom (Tiefe 2). Schulmethode Addition, Taktzahl bei von-Neumann-Addierwerk. (siehe pdf.) | ||
| 13 | 03.06.02 | Durchschnittliche Taktzahl bei von-Neumann-Addierwerk analysiert. Carry-Look-Ahead-Addierer in Fanin-2-Schaltkreisen und in Unbounded-Fanin- Schaltkreisen. Conditional-Sum-Addierer. | ||
| 14 | 05.06.02 | Größen- und Tiefenabschätzung CondSumAdd, Kapitel 3.5 und 3.6 (S. 83-85): Präfixberechnung. | ||
| 15 | 10.06.02 | Ladner-Fischer-Addierer via Präfixberechnung, Multiplikation: Schulmethode direkt, dann via Wallace-Tree, mit Karatsuba-Ofman-Multiplikationsschaltkreis begonnen. | ||
| 16 | 12.06.02 | Karatsuba-Ofman-Multiplikationsschaltkreis beendet, Größe und Tiefe davon analysiert, Radix-4-Darstellung mit Skizze, wieso diese bei Addition von n Zahlen helfen kann, Umwandlung von Radix-4-dargestellten Zahlen in Binärzahlen und umgekehrt. | ||
| 17 | 17.06.02 | Addition von Radix-4-Zahlen (siehe Aufschrieb), Mult. mit Zweierpotenzen, Argumentation, warum man sich bei Division auf 1/y mit 0.5 <= y < 1 beschränken kann. Newtonmethode beschrieben und quadratisches Konvergenzverhalten bei Kehrwertbildung nachgewiesen. | ||
| 18 | 19.06.02 | Newtonmethode beendet und IBM-Methode komplett vorgeführt. Anschließend (Start mit OBDD-Kapitel im Sielingskript) Liste von Operationen, die eine DS für boolesche Fkt. unterstützen sollte, aufgeführt. | ||
| 19 | 24.06.02 | Fortführung Liste von zu unterstützenden Operationen, warum sind Schaltkreise als DS ungeeignet?, Definitionen BDD, Pi-OBDD, warum kann jede Fkt. f durch Pi-OBDD berechnet werden, Reduktionsregeln und ihre Korrektheit, Definition der Notation va und fsub(a). | ||
| 20 | 26.06.02 | Struktursatz (Anzahl Knoten in OBDD in Beziehung zur Anzahl Subfunktionen) und sein Beweis. Funktion DQF, diese hat bei einer Var.ordnung linear große OBDDs, bei einer anderen (mit Hilfe des Struktursatzes nachgewiesen) exponentielle Größe. Nachweis, daß man das minimale OBDD mit Hilfe der Reduktionsregeln bekommt. Begonnen mit der genauen Implementierung der Reduktionsregeln. | ||
| 21 | 01.07.02 | Detaillierte Implementierung der Reduktionsregeln beendet. OBDDs für ausgewählte Funktionen: Symmetrische Funktionen, die Bits der Addition, Operationen auf OBDDs: Auswertung, Erfüllbarkeit, Erfüllbarkeit-Anzahl. Synthese: Mit "Kreuzproduktkonstruktion" begonnen. | ||
| 22 | 03.07.02 | Synthese: "Kreuzproduktkonstruktion" beendet, anschließend die Variante, die man aus Effizienzgründen tatsächlich macht, inklusive detaillierter Beschreibungen von unique-table und computed-table. MUX als Bsp. für quadratischen Blowup bei Synthese. Implementierung der letzten Operationen auf OBDDs, die übrig waren, nämlich Quantifizierung und Äquivalenztest. | ||
| 23 | 08.07.02 | Achillesfersenfunktion, Beweis, dass diese bei jeder Var.ordnung exp. große OBDDs braucht, Var.ordnungsproblem: Heuristiken, SWAP: lokale Suche/ Sifting, Beginn mit Kapitel 6 des Sielingskripts: Implizite Darstellung von Mengen, Darstellung von Monommengen (=Polynomen) mit OBDDs, Funktion überdeck(m,x), Funktion gleichheit(m,m'). | ||
| 24 | 10.07.02 | Implementierung der Operationen "verkuerz", "Streichen von Verlängerungen", "Implik", "Primimplik", "Kernimplik", "*-Operation" in OBDDs. Implementierung der Baummethode mit OBDDs. Begonnen mit Pentium-Dividierer: Wie funktioniert das Divisionsverfahren? --> Ablauf des Dividierers in jeder Runde. | ||
| 25 | 15.07.02 | Rest des Pentium-Dividierers, Verifikation von sequentiellen Schaltkreisen: Ampelbeispiel, Erreichbarkeitsanalyse. | ||
| 26 | 17.07.02 | "Prüfungsvorlesung". |