Einführung in die Theoretische Informatik III 
Sommersemester 1999

apl. Prof. Dr. Volker Strehl
Inhalt der Vorlesung und Literatur Den kompletten Foliensatz zu CS51 finden sie auf der  homepage von CS51 .
Ich empfehle Ihnen, sich dort einmal umzusehen. Sie erfahren, welche homework assignments zu dieser Vorlesung gegeben wurden, welche Rolle die Sprache Scheme in dieser Veranstaltung spielt usw.
Übrigens: auf dem Logo (links oben) sehen Sie das Gesicht eines Mannes -- das ist Alan TURING!

Alan TURING hat eine homepage:  hier!

Folien zur Vorlesung:

Zum letzten Teil der Vorlesung (Komplexitätsklassen)  stelle ich Kopien meiner Folien hier zur Verfügung.
Derzeitig verfügbare Texte:
  Komplexität (latex)  und  Komplexität (postscript)
  Reduktionen (latex) und  Reduktionen (postscript)
  Vollständigkeit (latex)  und  Vollständigkeit (postscript)
  Savitch (latex)  und  Savitch (postscript)
  Illustration (postscript)  zum Algorithmus von Savitch
  Reachability (latex)  und  Reachability (postscript)
  Immerman-Sz. (latex)  und  Immerman-Sz. (Postscript)
  Polynome (latex)  und  Polynome (postscript)
  P-Vollständigkeit (latex) und  P-Vollständigkeit (postscript)
  Resolution und 2-SAT (latex)  und  Resolution und 2-SAT (postscript)
  PSPACE-Vollständigkeit (latex) und  PSPACE-Vollständigkeit (postscript)
 Zum Beweis der PSPACE-Vollständigkeit: QSAT (latex)  und  QSAT (postscript)

Ergänzende Texte zu Themen der Vorlesung:

Zu früheren Durchgängen der Vorlesung existieren zahlreiche Notizen (Teil-Skripten) in Form von latex- und postscript-Dateien. Ich werde sie an dieser Stelle anbieten, sobald sich von dem jetzigen Gang der Vorlesung her anbietet.

Grundbegriffe zum Thema: Problem, Algorithmus, Komplexität( latex  und postscript )

Grundbegriffe zum Thema: asymptotische Notation ( latex  und  postscript)

Zum Thema:  divide-and-conquer Algorithmen (siehe weiter unten)

Zum Thema:  Schnelle Fourier Transformation (siehe weiter unten)

Zum Thema: Schnelle Multiplikation grosser Zahlen (siehe weiter unten)
(mit Nachtrag: Vergleich der Effizienz verschiedener Multiplikationsalgorithmen)

Zum Thema: Die Zahl Pi (siehe weiter unten)

Zum Thema: Polynomgleichungen und Hilberts 10. Problem
  Polynome (latex)  und  Polynome (postscript)

Zum Thema: Primzahlen und Komplexität (siehe weiter unten)

Zum Thema: Quicksort ( latex  und  postscript )

Zum Thema: PRIMES in NP

Ich habe in der Vorlesung wiederholt erwähnt, dass das Problem der Erkennung von Primzahlen sowohl in der Klasse co-NP liegt (klar: für die Zusammengesetzheit von Zahlen gibt es Zeugen: die Faktoren einer Produktzerlegung) als auch in der Klasse NP. Letzteres ist garnicht offensichtlich: wie sollten Zeugen für die Nicht-Zerlegbarkeit denn aussehen? Tatsächlich hilft die Zahlentheorie in der Gestalt des "kleinen Satzes von Fermat" und Verschärfungen davon, die die Primzahlen durch das Vorhandensein gewisser "primitiver Elemente" charakterisieren. Die Aussage "Primes in NP" wurde 1975 von V. Pratt bewiesen ( Every Prime has a Succinct Certificate). Hierzu gibt es einen ausführlicheren Text in  latex und  postscript  sowie die Kopie von Folien (=Kurzfassung), ebenfalls in  latex und  postscript . Die eingangs erwähnte Tatsache spricht nach Meinung vieler Experten dagegen, dass das Problem PRIMES NP-vollständig ist: wäre dies nämlich doch der Fall, so hätte es die Aussage "NP=co-NP" zur Folge.


Zum Thema: Schnelle Multiplikation grosser Zahlen

In der Vorlesung habe ich erwähnt, dass das derzeit schnellste bekannte Multiplikationsverfahren für Binärzahlen von Schönhage und Strassen (1969/71)  auf der Methodik der Schnellen Fourier-Transformation (FFT) beruht. Darauf wird im Verlauf der Vorlesung noch eingegangen, wenn auch die Behandlung des Multiplikationverfahrens wegen der Kompliziertheit der Methode im Rahmen dieser Vorlesung unterbleiben muss. Als Referenz, wo man alle trickreichen Details nachlesen kann, möchte ich auf ein opus magnum der hinweisen, in das jeder Informatiker mal seine Nase stecken sollte (meine Meinung):

Don Knuth hat uns also nicht nur TEX beschert (genauer gesagt: er hat TEX geschaffen, weil er einen guten Schriftsatz für seine TAOCP-Bücher selbst herstellen wollte - das hat ihn mal gerade so zehn, zwölf Jahre von seinem eigenlichen Thema abgelenkt), sondern noch viel mehr, wovon man auf der
homepage von Don Knuth  immerhin eine Ahnung bekommt. Informationen zu den genannten Büchern gibt es auf der Seite TAOCP . Alle drei Bände sind ganz kürzlich in neuer Ueberarbeitung erschienen. Kaufen! Lesen!

Man hat übrigens das Verfahren von Schönhage-Strassen, das in Band 2 von TAOCP dargestellt wird,  bislang für ziemlich esoterisch und unpraktikabel gehalten, weil der immense overhead für "kleine" Argumente den asymptotischen Vorteil nicht erkennen lässt. Bislang hat man deswegen in solchen Grössenordnungen, wenn es etwa um Zahlen mit einer Millon Stellen geht, mit dem Verfahren von Karatsuba oder Varianten davon gerechnet. Nun gibt es aber manische Rechner (Mathematik-Programmierer), die sich für Milliarden Stellen der Kreiszahl Pi interessieren (Rekord im Juli 1997: 51,5 Millarden Stellen). In diesen Dimensionen macht sich der Vorteil der Schönhage-Strassen-Methode nun wirklich drastisch bemerkbar - und zwar so sehr, dass viele der Publikationen, die versuchen, dem Normalverbraucher die Pi-Rekordsucht nahezubringen, auf eine (mehr oder weniger grobe) Darstellung dieser Multiplikationmethode nicht verzichten. Mehr Hinweise dazu im nächsten Punkt.

Nachtrag (30.5.99) : Vergleich der Effizienz verschiedener Multiplikationsalgorithmen

Hier finden Sie ein  postscript file mit grafischen Darstellungen zum Vergleich der Effizienz verschiedener Multiplikationsalgorithmen für Zahlen und Polynome: klassische Methoden, Karatsubas Methode, sowie FFT-basierte Methoden. Diese Darstellungen stammen aus dem gerade erschienen Buch MODERN COMPUTER ALGEBRA von J. von zur Gathen und J. Gerhard (früherer Erlanger Informatik-Student!!)  Das Buch ist bei Cambridge University Press erschienen.

Zum Thema: Pi

Das Beschäftigung mit der Kreiszahl Pi ist eines der faszinierendsten Kapitel der Mathematik von den geschichtlichen Anfängen bis in die Gegenwart - und damit der Kulturgeschichte überhaupt. Ich will das hier nicht einmal ansatzweise versuchen darzustellen, sondern kann nur auf jüngst erschienene Literatur verweisen, die einen Einstieg in das Thema bietet:

In der "Schwarte" von Berggren et al. sind die wichtigsten Arbeiten zu Pi aus allen Jahrhunderten wieder abgedruckt. Die anderen beiden Bücher bieten einen gerafften, leicht lesbaren Ueberblick, der so richtig Appetit machen kann. Das Buch von Arndt und Hänel (aus Bayreuth!) gibt auch einen Einstieg in das mathematische Höchstleistungsrechnen - wer sich dafür interessiert, auch unabhängig von Pi, ist mit der auf CD gelieferten software (+ Tutorial zur FFT!) gut und interessant bedient.
(Gelegentlich werde ich hier einige interessante web-Seiten zu Pi nachtragen).


Zum Thema: Divide-and-Conquer Algorithmen

Das Prinzip des Teilens und Herrschens ist ein fundamentales Prinzip der Algorithmik mit vielen speziellen Ausprägungen. Prominente Beispiele sind

Diese Beispiele habe ich in einem kurzen Text (7 Seiten,  latex  bzw.  postscript ) beschrieben. Eine andere Darstellung des Multiplikationsverfahrens von Karatsuba (in der Version für Polynome) finden Sie in einem Text ( latex  bzw.  postscript ) bei dem auch gezeigt wird, wie man Rekursiongleichungen des Typs analytisch behandelt. Eine kurze Zusammenfassung dieser Analyse findet man hier ( latex bzw.  postscript ).
Ein ausführlicher Text zur Analyse von divide-and-conquer-Rekursionen des Typs ist auch erhältlich ( latex bzw. postscript ) , sowie eine kurze Zusammenfassung davon ( latex bzw.  postscript ) .
Für eine ausführliche Behandlung dieser Analysetechnik (ohne die Verwendung von Potenzreihen und deren Konvergenzradien) verweise aich auf das Buch von Cormen, Leiserson, Rivest: Introduction to Algorithms, MIT Press.
 


Zum Thema: Schnelle Fourier-Transformation
 

Diese Thema hat in früheren Durchgängen dieser Vorlesung breiten Raum eingenommen, vor allem wurde der algebraische Hintergrund der FFT (Polynomrepräsentationen, Polynomarithmetik, modulare Arithmetik in Polynomringen) ausführlich dargestellt, dazu Motivation und Ausblicke auf Anwendungen und Variationen. Das Thema ist ungeheuer reichhaltig. Diese algebraische Seite wird diesmal etwas kurz abgehandelt, das Gewicht liegt auf dem Divide-and-Conquer-Prinzip. Zur breiteren Orientierung stelle ich ein umfangreiches Skriptum zur Verfügung, das ich zu einem früheren Durchgang der Vorlesung geschrieben habe, es ist als  latex file  und als  postscript file hier abrufbar. Die in der Vorlesung gezeigten Folien stellen einen schlagwortartigen Auszug aus diesem Skriptum dar, die entsprechenden files finden Sie hier in  latex und in  postscript. Benötigt werden auch die files fft.texteiler.tex, sowie die style files für A4-Format und für kommutative Diagramme.

Literaturhinweis: Boolesche Funktionen in der Praxis

In der Vorlesung wurde kurz die Darstellung Boolescher Funktionen durch sog. "binäre Entscheidungsdiagramme" (binary decision diagrams, BDD) angesprochen. Insbesondere der Typus der geordneten Entscheidungsdiagramms (OBDD) hat in den letzten Jahren in industriellen Anwendung ein grosses Interesse gefunden. Das hat auch sich nun ganz aktuell auch auf dem Lehrbuchmarkt bemerkbar gemacht. Es liegen nunmehr bereits drei Bücher zu diesem Thema vor:

Drechsler/Becker: Graphenbasierte Funktionsdarstellung, Teubner Verlag, 1998.
Meinel/Theobald: Algorithmen und Datenstrukturen im VLSI-Design, Springer Verlag 1998.
Molitor/Scholl: Datenstrukturen und effiziente Algorithmen für die Logiksynthese kombinatorischer Schaltungen. Teubner Verlag, 1999.
Eine schon "klassische" Darstellung, die das ganze Umfeld der Logiksynthese mit berücksichtigt, ist das Standardwerk
Hachtel/Somenzi: Logic Synthesis and Verification Algorithms, Kluwer 1996/1998.