Materialien

Auf dieser Seite finden Sie Texte, Literaturhinweise, Links etc. die mit der Vorlesung inhaltlich zusammenhängen, aber auch darüber hinausgehen. Für Interessierte an Themen der Algorithmik, Komplexität, Analyse, Geschichte, ....
 

• Persönlichkeiten aus der Geschichte der Algorithmik, der Informationsverarbeitung und der Informatik

 
• Claude E. Shannon (1916 - 2001)

Wesentliche Stationen: University of Michigan, MIT, Bell Telephone Laboratories.
Initiierte die Anwendung der Booleschen Algebra auf Schaltkreiseintwurf- und Optimierung in seiner Master Thesis (!!)  A Symbolic Analysis of Relay and Switching Circuits (1938)  --- nach H.H. Goldstine one of the most important master theses ever written --- schuf mit A Mathematical Theory of Communication (1948)  [probably no single work in this century has more profoundly altered man's understanding of communication --- D. Slepian] mit einem Schlag eine ganze Disziplin, die Informations- und Codierungstheorie, begründete mit Communication Theory of Secrecy Systems (1949)  die informationstheoretische Kryptografie, um nur einige ganz herausragende Arbeiten zur Schaltkreistheorie und zur Informationstheorie zu nennen. Das bit als Einheit der digitalen Information und die grundlegenden Begriffe zu seiner mathematische Behandlung (Information, Entropie, Redundanz, Quellen- und Kanalcodierung, Kapazität usw.)  hat er in A Mathematical Theory... eingeführt.
Daneben reichten seine Interessen von schachspielenden Computern, algorithmischen Mäusen in Labyrinthen, bis hin zum Jonglieren und raketengetriebenen Frisbee-Scheiben. Auch eine universelle Turing-Maschine mit nur zwei Zuständen verdanken wir ihm.

Internet-Seiten zu Claude Shannon:
Eine Kurzbiografie.
Ein Nachruf.
Eine ausführliche Biografie , verfasst von Neil Sloane und Aaron Wyner, den Herausgebern der Collected Papers.
Eine Würdigung der Leistungen von Shannon durch A. Wyner.
Die Bibliografie von Claude Shannon.

Einige bibliografische Notizen (und download-Möglichkeit)
zu Claude E. Shannons A Mathematical Theory of Communication,
The Bell System Technical Journal 27 (1948) .
 

• Abu Ja'far Muhammad ibn Musa al-Khwarizmi (etwa 780 - etwa 850)
  Mathematiker am ``Haus der Weisheit'' in Bagdad. Sein Buch Al kitab al mukthasar fi hisab al-jabr w'al-muqabala 
  [Das umfassende Buch vom Rechnen durch Ergänzung und Ausgleich], in dem im wesentlichen das Lösen von quadratischen Gleichungen behandelt wird, kann als das erste oder eines der ersten Lehrbücher der Algebra angesprochen werden. Das Wort Algebra ist denn auch aus dem al-jabr des Titels abgeleitet. Es wurde mehrfach ins Lateinische übersetzt und hat grossen Einfluss auf die arabische und dann auch europäische Mathematik-Entwicklung gehabt. Nur in Latein erhalten ist das ebenfalls einflussreiche Algoritmi de numero Indorum, in dem er das Rechen im indischen Zahlsystem (unser Dezimalsystem, mit der wichtigen Erfindung der "0")  lehrt, das auch auf diesem Weg nach Europa gekommen ist (wobei gesagt werden muss, dass in der Nachfolge von al-Khwarizmi noch weitere arabische Mathematiker gab, die solche Texte verfasst haben, wie Abu-Kamil und al-Karaji). Aus dem latinisierten Autorennamen Algoritmi entstand schliesslich die Bezeichnung Algorithmus, wobei das al-Khwarizmi im Namen des Autors ursprünglich lediglich eine geographische Herkunftsbezeichnung seiner Famileie (in der Nähe des Aral-Sees)  meint.
  Einer der ersten Propagandisten des indischen Zahlsystems in Europa war übrigens Leonardo Pisano, besser bekannt unter dem Namen Fibonacci (filius Bonacci = Sohn des Bonacci, 1170-1250),  der es bei seiner Erziehung und seinen Reisen in Nordafrika kennengelernt hat.

Literaturhinweise:

• Historisches
 
• Martin Davis, The Universal Computer: The Road from Leibniz to Turing, W.W. Norton & Company, 2000, ISBN 0-939-04785-7.

Einer der "Grossen" in der Entwicklung der Theoretischen Informatik, selber von der Logik herkommend,  hat die Entwicklung des Computers aus dieser Perspektive dargestellt. Die Persönlickeiten von Leibniz, Boole, Frege, Gödel,Hilbert, Turing, v. Neumann und deren Beiträgestehen im Mittelpunkt der Darstellung. Sehr lesenswert, wenn man sich für die historischen Wurzeln seines Faches interessiert.
 
• David Berlinski, The Advent of the Algorithm, Harcourt, 1999, ISBN 0-15-100338-6.

Thematisch ähnlich dem Buch von Davis, aber in der Darstellung bisweilen recht eigenwillig und in den Formulierungen provokant.
 
• Georges Ifrah, The Universal History of Computing, Wiley, 2001, ISBN 0-471-39671-0.

Vom Autor des sehr popoulären Buches The Universal History of Numbers, aus dem auch kräftig zitiert wird. Hier geht es mehr um die Geschichte der Rechenmaschinen, also der technischen Seite Seite des Computers. Viel interessantes Material, aber in der Durcharbeitung und Präsentation leider etwas unausgewogen geraten (wohl wegen der vielen Anleihen in anderen Texten).
 
• Jean-Luc Chabert et al. A History of Algorithms, Springer-Verlag, 1999, ISBN 3-540-63369-3.

Dieses Buch enthält viele Originalzitate aus Arbeiten über algorithmische Verfahren, meist numerischer Natur ( arithmetische Operationen, regula falsi, Euklids Algorithmus, Berechnung von Pi, Newtons Tangenten-Methode, Faktorisierung und Primzahltests, Lineare Gleichungssysteme usw.)  Diese Zitate werden aus heutiger Sicht kommentiert und in ihrer Bedeutung gewürdigt. Das letzte Kapitel ist der Präzisierung des Algorithmenbegriffs in den 30er Jahren des vorigen Jahrhunderts gewidmet ( Gödel, Church, Turing, Kleene, Post).
 
• Simon Singh, The Code Book, Taschenbuchausgabe bei Fourth Estate Ltd., 1999, ISBN 1-85702-889-9.

Eine spannend geschriebene Geschichte der kryptografischen Methoden, die sowohl die mathematischen Aspekte wie auch die historischen Umstände und die agierenden Personen gebührend berücksichtigt - von Maria Stuart über Enigma bis zu public-key-Systemen und Quantenkryptografie. Im Zusammenhang mit dieser Vorlesung von besonderem Interesse ist das sechste Kapitel Alice and Bob go Public. Es beschreibt die Entstehungsgeschichte der public-key-Kryptografie mit dem Protokoll von Diffie-Hellmann-Merkle und dem Verfahren von Rivest-Shamir Adleman (RSA). Was man dort auch erfährt: dass der britische secret service GCHQ diese Dinge schon vorher kannte, aber natürlich nie öffentlich dazu Stellung genommen hat. Natürlich kommt auch Alan Turing vor, der eine wesentliche  Rolle beim Brechen der deutschen Verschlüsselungstechniken (Enigma)  im zweiten Weltkrieg in Bletchley Park spielte. Wer sich eingehender für die Person, das Leben und das Werk von Alan Turing interessiert - immerhin in einer Umfrage unter den zwanzig bedeutendsten Wissenschaftlern des 20. Jahrhundert gelistet, wie übigens auch Kurt Gödel - sollte sich das folgende Buch besorgen.
 
• Andrew Hodges, Alan Turing: The Enigma. Vintage, 1992, ISBN 0-09-911641-3. Deutsche Übersetzung ISBN 3-211-82627-0 bei Springer-Wien. Eine amerikanicche Neuauflage ist 2000 bei Walker (New York, ISBN 0-8027-7580-2)  erschienen.

Statt nach eigenen Worten zu suchen, zitiere ich Simon Singh: The life and work of Alan Turing. One of the best scientific biographies ever written. Besuchen Sie auch die Alan Turing home page
• Komplexitätsanalyse

 
• Donald E. Knuth, The Art of Computer Programming, Addison-Wesley.

vol.1 Fundamental Algorithms, 1997, ISBN 0-201-89683-4
vol.2 Seminumerical Algorithms, 1997, ISBN 0-201-89684-2
vol.3 Sorting and Searching, 1998, ISBN 0-201-89685-0
Wenn es um die Analyse von Algorithmen geht, sind diese Bücher die Klassiker schlechthin. Wer sich ernsthaft um die Frage der Komplexitätsabschätzungen bemüht, sei es bei arithmetischen Operationen, sei es beim Sortieren und Suchen, wir nicht darum herum kommen, sich mit den Inhalten dieser Bücher auseinanderzusetzen. Beachten Sie: die ersten Ausgaben dieser Werke reichen bis 1968 zurück, und manches, was man darin über Rechner, Maschinenprogrammierung und Datenstrukturen findet, ist nicht mehr so ganz so dargestellt, wie man diese Dinge heute präsentiert. Was die Methodik und analytischen Resultate angeht, ist TAOCP nie übertroffen worden. Allerdings: dass es sich um eine leichte Lektüre handelt, hat niemals jemand behauptet! Die obigen Angaben der Jahreszahlen beziehen sich auf die aktuellen Überarbeitungen. Falls Sie es noch nicht wussten: weil er mit der typografischen Gestaltung seiner ersten Bücher nicht zufrieden war, hat sich Don Knuth entschlossen, es selber besser zu machen und TEX erfunden und entwickelt. Das hat ihn, nach eigener Aussage, mal gerade so 12 Jahre von der Arbeit auf sein eigentliches Ziel hin, nämlich die Analyse von Algorithmen profundissime darzustellen, abgehalten.

Aus der homepage dieser Bücher zitiert:
At the end of 1999, these books were named among the best twelve scientific monographs of the century by American Scientist, along with: Dirac on quantum mechanics, Einstein on relativity, Mandelbrot on fractals, Pauling on the chemical bond, Russell and Whitehead on foundations of mathematics, von Neumann and Morgenstern on game theory, Wiener on cybernetics, Woodward and Hoffmann on orbital symmetry, Feynman on quantum electrodynamics, Smith on the search for structure, and Einstein's collected papers. Wow!
 

Ganz aktuell: im Springer-Verlage ist unter dem Titel Arithmetik gerade eben das vierte Kapitel (= zweiter Teil des zweiten Bandes)   in deutscher Übersetzung (von R. Loos, Tübingen)  erschienen,  ISBN 3-540-66745-8, zum populären Preis von  DM 69,-.

Wer sich auf die Lektüre der Werke von Knuth geeignet vorbereiten will, findet dazu eine bestens geeignete Möglichkeit in:
 

• R. L. Graham, D. E. Knuth, O. Patashnik, Concrete Mathematics, Addison-Wesley, 1989, ISBN 0-201-14236-8.

Dieses Buch präsentiert in locker geschriebener Darstellung die Mathematik, die man "drauf haben" sollte, wenn man sich ernsthaft an TAOCP wagt, ist aber auch unabhängig davon sehr lesenswert.

Im Rahmen der Vorlesung Einführung in die Theoretische Informatik III kann ich leider nicht auf das Problem der average-case complexity von Algorithmen eingehen. Immerhin gibt es für dieses Gebiet jetzt ein schön geschriebenes einführendes Lehrbuch, das ich denjenigen empfehlen kann, die mal in diese Richtung schnuppern wollen.
 

• Robert Sedgewick, Philippe Flajolet, An Introduction to the Analysis of Algorithms, Addison-Wesley, 1996, ISBN 0-201-40009-X


Hier ist, was der grosse Meister dazu sagt:

"People who analyze algorithms have double happiness. First of all they experience the sheer beauty of elegant mathematical patterns that surround elegant computational procedures. Then they receive a practical payoff when their theories make it possible to get other jobs done more quickly and more economically.... The appearance of this long-awaited book is therefore most welcome. Its authors are not only worldwide leaders of the field, they also are masters of exposition."
--D. E. Knuth