• Übungen

erstes Übungsblatt (4.Mai 2000)  in LaTeX, PostScript, PDF

zweites Übungsblatt (11. Mai 2000)  in LaTeX, Postscript, PDF
  (Revidiert am 22.5.)

drittes Übungsblatt (25. Mai 2000)   in LaTeX, Postscript, PDF

viertes Übungsblatt (2. Juni 2000)   in LaTeX, Postscript, PDF

fünftes Übungsblatt (13. Juni 2000)  in LaTeX, Postscript, PDF

sechstes Übungsblatt (21. Juni 2000)   in LaTeX, Postscript, PDF

siebtes Übungsblatt (3. Juli 2000) in LaTeX, Postscript, PDF

achtes Übungsblatt (13. Juli 2000) in LaTeX, Postscript, PDF
 

• Texte

Folien: Boolesche Algebra und Boolesche Funktionen (4. Mai 2000)
in LaTeX und Postscript (4 Folien pro Seite)

Folien: Graphentheoretische Terminologie (9.Mai 2000)
in  LaTeX und  Postscript (4 Folien pro Seite)

Folien: Straight-line Programme und Schaltkreise (9. Mai 2000)
in  LaTeX und  Postscript  (4 Folien pro Seite)

Folien: Einige einfache Boolesche Funktionen und ihre Komplexität (11. Mai 2000)
in LaTeX und Postscript (4 Folien pro Seite)

Folien: Berechnung von Reziproken (25. Mai 2000)
in LaTeX und Postscript (4 Folien pro Seite)

Folien: Berechnung von Quadraten mittels Reziproken (29. Mai 2000)
in LaTeX und Postscript (2 Folien pro Seite)

Folien: Matrixmultiplikation nach Strassen (30. Mai 2000)
in LaTeX und Postscript (4 Folien pro Seite)

Folien: Komplexität der Schwellwertfunktionen nach Razborov (8. Juni 2000)
in LaTeX und Postscript (4 Folien pro Seite)

Folien: Inversion von Matrizen - LDU-Zerlegung und Methode von Czanky (19. Juni 2000)
in LaTeX und in Postscript (4 Folien pro Seite)

Folien: Schur-Komplement und LDU-Zerlegung (19. Juni 2000)
in LaTeX und Postscript (4 Folien pro Seite)

Folien: Lösen linearer Gleichungssysteme (19. Juni 2000)
in LaTeX und Postscript (2 Folien pro Seite)

Folien: Schnelle Fourier-Transformation (27. Juni 2000)
in LaTeX und Postscript (4 Folien pro Seite)

Folien: Batcher's Misch- und Sortierverfahren (4. Juli 200)
in LaTeX und Postscript (2 Folien pro Seite)

Folien: Zur Bedeutung des Reachability-Problems (12. Juli 2000)
in LaTeX und Postscript (4 Folien pro Seite)

Folien: Zum Algorithmus von Savitch (12. Juli 2000)
in LaTeX und Postscript ( 4 Folien pro Seite)

Folien: Zum Verfahren von Immermann-Szelepscényi (12. Juli 2000)
in LaTeX und Postscript (2 Folien pro Seite)

Folien: Reduktion und Vollständigkeit (12. Juli 2000)
in LaTex und Postscript (4 Folien pro Seite)

Folien: Komplexität von Entscheidungsproblemen (19. Juli 2000)
in LaTeX und in Postscript

Folien: Vollständigkeit von CircuitValue und CircuitSatisfiability (23. Juli 2000)
in LaTeX und Postscript

Folien: Polynome, Unentscheidbarkeit, Färbungen von Graphen (27. Juli 2000)
in LaTeX und Postscript

Folien: Physik und Komplexität (27. Juli 2000)
in LaTeX und Postscript

Relevante Texte aus früheren Semestern
 

• Schnelle Multiplikation grosser Zahlen
• Divide-and-Conquer-Algorithmen
• Lupanov-Darstellung Boolescher Funktionen
• Komplexität der Matrix-Inversion
• Boolesches Matrixprodukt und transitive Hülle
• Schnelle Fourier-Transformation (Skriptum, 35 Seiten)
• Binärbäume und Sortierkomplexität

• Folien von Abbildungen

Boolesche Algebra über 4 Atomen in  fig und  Postscript

Boolesche Algebra der zweistelligen Funktionen in fig und  Postscript

OBDD-Beispiel 1 in  fig und  Postscript

OBDD-Beispiel 2 in  fig und  Postscript

balancierter Binärbaum für assoziative Operationen in fig und in Postscript

Kaskade für zyklischen Shift um 0-7 Positionen in fig und in Postscript

Zyklischer Shift um 0 oder 2 Positionen in fig und in Postscript

Codierer in fig und in Postscript

Decodierer in fig und in Postscript

Zähler in fig und in Postscript

Rekursive Präfix-Berechnung in fig und in Postscript

Volladdierer in fig und in Postscript

Ripple-Addierer in fig und in Postscript

Carry-Save Addierer in fig und in Postscript

Schema der Carry-Save Addition für mehrere Summanden in fig und in Postscript

Schematische Darstellung der carry-lookahead-Addition in fig und in Postscript

Schema der Lupanov-Darstellung von Booleschen Funktionen : LaTeX-file mit eepic-Figur, Postscript

Maple-worksheet zur LDU-Zerlegung mittels Schur-Komplement in Postscript

Maple-worksheet zum Algorithmus von Csanky in Postscript