Buchtipps

Die 2. Ausgabe des Sedgewick ist jetzt nur noch in der Pascal-Version erhältlich und wurde 2002 mit neuem Cover von einem neuen Verlag veröffentlicht, damit man das Alter von 10 Jahren nicht so leicht bemerkt (die Beschreibung der dritten Ausgabe kommt gleich unten). Bei einem Grundlagenbuch zu Algorithmen und Datenstrukturen macht dieses Alter aber gar nichts aus. Die zweite Ausgabe hat sich jahrelang bewährt und ist nach mehreren Preiserhöhungen von früher 60 Mark auf jetzt 50 Euro genauso teuer und auch genauso umfangreich wie der erste Band der dritten Ausgabe - also allemal eine empfehlenswerte Alternative, wenn man zum Einstieg lieber etwas weniger Umfang für weniger Geld möchte (und ansonsten kann man genausogut zum Cormen greifen).

Denn der Sedgewick ist und bleibt der Klassiker. Er ist einfach eine Riesenhilfe, wenn man sich ernsthaft mit Informatik beschäftigen will. Von der ersten Runde des Bundeswettbewerbs bis zur IOI und zum Studium war er immer mein treuer Begleiter, in dem ich unzählbar oft Algorithmen und Datenstrukturen nachgeschlagen habe. Zwar geht die zweite Ausgabe leider nicht immer richtig in die Tiefe, deckt aber ein breites Spektrum (Sortieren & Suchen, Graphenalgorithmen, geometrische Algorithmen, NP- Vollständigkeit, ...) ab und ist sehr schön verständlich geschrieben. Wer am BWInf ernsthaft teilnehmen will, sollte sich dieses Buch auf jeden Fall zulegen! In der hier verlinkten Ausgabe sind die Beispielprogramme in Pascal. Sie sind aber kurz genug, dass auch in anderen Sprachen geübte sie leicht verstehen können sollten. Es gab auch einmal eine Paperback-Version, diese ist aber bei Amazon momentan (19.11.2003) nur noch gebraucht über Dritte lieferbar.

Die dritte Ausgabe des Sedgewick hat gegenüber der zweiten den Nachteil, dass sie teurer ist und aus zwei Bänden besteht, von denen erst der erste Band auf Deutsch erschienen ist. Im Gegensatz zur zweiten Ausgabe ist die dritte gerade nicht mit Beispielprogrammen in Pascal, dafür aber in C++ und in Java erhältlich. Der große Vorteil der dritten Ausgabe ist, dass sie ausführlicher ist. Ihr erster Band ist nicht nur genauso teuer wie die gesamte zweite Ausgabe, sondern auch genauso umfangreich.

Der erste Band umfasst inhaltlich die ersten vier von fünf Kapiteln der zweiten Ausgabe und behandelt demnach Grundlagen, Datenstrukturen, Sortieren & Suchen, der zweite Band behandelt Graphenalgorithmen und ist bisher für nur auf Englisch erhältlich (38,20 Euro). Ein dritter Band ist in Planung.

Rund 1200 Seiten dick ist dieses weitere Standardwerk der Informatik, das erst 2004 endlich auf Deutsch erschienen ist. Das englische Original ist eins der besten Bücher dieser Art: Es ist nicht nur hervorragend geschrieben, sondern deckt auch eine gute Themenauswahl ab. Auch wenn ich zur Qualität der deutschen Übersetzung noch nichts weiß, dürfte dieses Buch mittlerweile wohl dem Sedgewick vorzuziehen sein.

Wer sehr gut Englisch kann und ganz sicher gehen will, ein ausgezeichnetes Informatikbuch zu bekommen, kann die englische Hardcover- oder Paperback-Ausgabe kaufen.

Der Turing Omnibus (Untertitel: Eine Reise durch die Informatik mit 66 Stationen) bietet eine leicht zu lesende Reise durch viele interessante, aber sehr unterschiedliche Bereiche der Informatik. Er ist zum Beispiel sehr hilfreich, um vor der BWInf-Endrunde größere Lücken in vielen Bereichen zu schließen. Obwohl das Buch einige Fehler enthält, ist es meiner Meinung nach sehr zu empfehlen. Nirgends sonst habe ich bisher einen so schönen Überblick über so viele Themen gefunden, die man sich sonst aus vielen Büchern mühsam zusammenklauben muss. Leider ist die deutsche Version dieses Buchs mittlerweile vergriffen - 2001 ist aber eine neue, überarbeitete Version auf Englisch erschienen (EUR 23,89).

Eine wunderbar kurze (knapp 200 Din A5 Seiten), präzise und schön geschriebene Einführung in die Theoretische Informatik. Hauptthemen sind die Chomsky-Hierarchie und die daran geknüpften Automatentypen, Berechenbarkeitstheorie (Turing-Berechenbarkeit und primitive Rekursion, Halteproblem, Ackermann, PCP und Satz von Gödel) und Komplexitätstheorie (NP-Vollständigkeit). Einige dieser Themen werden auch im Turing Omnibus schön behandelt, allerdings nicht ganz so fundiert wie im Schöning. Nach dem Sedgewick und dem Turing Omnibus dürfte der Schöning als Endrundenempfehlung daher an der dritten Stelle kommen. Prof. Schöning ist übrigens seit 2001 Vorsitzender des Beirats des Bundeswettbewerbs Informatik.

Dieses Buch dürfte wohl dasjenige sein, das mir am meisten für die Vorbereitung auf die IOI gebracht hat. Es besteht aus zwei Teilen. Im ersten Teil werden ähnlich zu anderen Algorithmenbüchern, aber etwas knapper, viele fundamentale Algorithmen und Datenstrukturen abgehandelt. Besonders der Teil zum dynamischen Programmieren ist hier hervorragend abgehandelt. Im zweiten Teil, dem Algorithmic Catalogue, kann man nachschlagen, wenn man vor einem neuen Problem steht. Hier findet man heraus, wie das Problem heißt, welche ähnlichen bekannten Probleme es gibt, welche Lösungsansätze es gibt, wie schwierig das Problem ist (Laufzeit in O()) und wo man mehr dazu erfahren kann. Das Buch enthält eine Vielzahl von Verweisen auf Ressourcen im Web und hat auch eine Homepage mit Fehlerberichtigungen und weiterem Material. Auf der beiliegenden CD-ROM ist der komplette Text des Buchs in HTML-Form sowie viele nützliche Libraries usw. enthalten, die im Buch erwähnt werden. Wer zur IOI / CEOI will, sollte sich dieses Buch unbedingt kaufen!! Leider ist es für den geringen Umfang recht teuer.

Bemerkung: mir liegt nur die erste Ausgabe dieses Buches vor; der Link und der Preis beziehen sich auf die aktuelle 2nd Edition. Der Preis ist abhängig vom Dollarkurs und auf dem Stand vom 19.7.2002 (amazon.de). Von allen Seiten hochgelobt, weckt dieses Buch in jedem angehenden Informatiker große Erwartungen. Leider kann es diese zumindest meiner Meinung nach nicht erfüllen. Während man eine Vielzahl von unterschiedlichen, interessanten Themen erwartet, findet man tatsächlich doch nur immer wieder das gleiche: dutzende "War Stories", also Geschichten von auftretenden Problemen, die zuerst mit einem ineffizienten Algorithmus angegangen werden, dann aber nach einem Geistesblitz um ein vielfaches effizienter gelöst werden. Die Moral von der Geschicht ist meist nur, dass eigentlich nur die Komplexität in O() zählt und konstante Faktoren unwichtig sind. Da ist sicher was dran, aber dafür muss man sich dieses Buch nicht kaufen. Vielleicht findet ja der eine oder andere die Geschichten unterhaltsam, ein fachlicher Fortschritt ist davon aber weniger zu erwarten.

Was soll man da noch sagen? Dieses 1200 Seiten dicke Buch ist schlicht und einfach die Bibel der polygonalen Computergraphik, auch wenn es mittlerweile auch schon einige Jährchen auf dem Buckel hat (die 2nd Edition erschien 1995). Wer sich für dieses Gebiet interessiert, hat dieses Buch vermutlich sowieso schon im Schrank stehen. Alle anderen brauchen es nicht.

Die offiziellen Beispielbücher zum Bundeswettbewerb. Sie behandeln die älteren Bundeswettbewerbe (bis einschließlich Nr. 11) und enthalten jeweils die Problemstellung sowie Lösungsideen und ein Beispielprogramm (meist in Pascal). Zumindest für den Einsteiger und mittleren Fortgeschrittenen beim Bundeswettbewerb können diese Bücher durchaus recht sinnvoll und hilfreich sein. Zwar sind die Beispielprogramme nicht immer perfekt, aber man kann doch einige Ideen bekommen, auf die man selbst nicht gekommen wäre. Mittlerweile, da es ja schon einige Einsendungen auch von aktuelleren BWInfs zum Download gibt und man in Newsgroups wie fido.ger.bwinf mit Gleichgesinnten diskutieren kann, sind die Bücher vermutlich nicht mehr so wichtig wie früher. Für die IOI- oder Endrunden-Vorbereitung sind sie ohnehin nicht sehr gut geeignet. Das Beispielbuch für die Wettbewerbe Nr. 12 und 13 ist übrigens im Jahr 2000 erschienen, und zwar nunmehr in Form des GMD-Reports Nr. 97 (490 KBytes, geZIPtes PDF, lesbar mit Adobe Acrobat Reader).

Dieses Buch ist kein echtes Wissensbuch in dem Sinne. Es hat kein Din A4 Format, ist deutlich billiger als alle anderen hier aufgeführten Bücher, und der Umschlag erweckt den Eindruck eines eher primitiven pseudowissenschaftlichen Buches. Doch der Schein trügt. Tatsächlich war dieses Buch eine zeitlang mein Lieblingsbuch. Für den Halblaien bietet es einen hervorragenden und stets spannend geschriebenen Überblick über das Gebiet des künstlichen Lebens und der künstlichen Intelligenz und porträtiert wichtige Menschen, deren Leben mit diesen Thematiken verwoben ist. Zu diesem Preis muss man das Buch eigentlich kaufen. Leider war das Buch aber schon recht bald nach seinem Erscheinen wieder vergriffen und ist nun weder bei Amazon noch bei Osiander zu finden. Wer doch noch eine Bestellmöglichkeit für dieses Buch findet, möge sich bitte bei mir melden. Update: Momentan (November 2003, ebenso Oktober 2005) sind bei Amazon wieder gebrauchte Exemplare erhältlich! Ich empfehle Euch unbedingt, zuzugreifen!

Dieses Buch ist aus einer Vortragsreihe entstanden und enthält Papers verschiedener Autoren. Viele Kapitel behandeln aber wirklich ziemlich interessante Themen, z.B. (aus dem Inhaltsverzeichnis): "Zufalls-Primzahlen und Kryptographie", "Interaktive Beweise", "Theoretische Aspekte neuronaler Netzwerke", "Wie man Beweise verifiziert, ohne sie zu lesen", "Molekulare Bioinformatik", "Knight moves - was macht der Springer allein auf dem Schachbrett?", "Automatische Zusammenstellung von Fahrgemeinschaften" und "LEDA - Eine Plattform für kombinatorisches und geometrisches Rechnen". Man muss sich allerdings bewusst sein, dass das Buch verschiedene Themen ganz unabhängig voneinander behandelt. Auch der Stil und die Qualität schwankt, da ja unterschiedliche Autoren beteiligt waren. Die guten Kapitel können das Buch aber durchaus kaufenswert machen. Alles in allem also eine mittelstarke Kaufempfehlung.

Schon am Layout merkt man, dass der Ottmann/Widmayer (O/W) der deutsche Knuth sein will. Leider gelingt ihm das nicht ganz. Der O/W ist sicher ein schönes Informatikbuch und behandelt viele Themen, die im Sedgewick ein wenig zu kurz kommen (z.B. Hashing) ausführlicher. Leider ist der O/W aber deutlich weniger verständlich geschrieben und verwendet teilweise einen unnötigen Formalismus. Auch die Beispielprogramme in Pseudocode sind meiner Meinung nach viel weniger lesbar als die Quellcodes von Sedgewick. Mein Tipp: lieber zum Sedgewick und/oder zum Cormen greifen - um so mehr, da der Ottmann/Widmayer gegenüber der 3. Auflage von 1996 trotz nur kleiner Änderungen um 10 Euro teurer wurde.

Die definitive Bibel der Informatik. Diese Buchreihe ist sehr berühmt und schon (für Informatik-Begriffe) seit einer Ewigkeit das Standardwerk schlechthin. Die Bücher sind voll von Algorithmen und Aufgaben aller Arten, die einen nächtelang fesseln können. Die Aufgaben sehr unterschiedlichen Schwierigkeitsgrads (von der Trivialität bis zu Fermats letztem Satz) sind immer wieder ein Anreiz zum Rumblättern. Manche finden die Aufgaben etwas zu sehr mathematisch angehaucht. Mindestens einen Band vom Knuth sollte eigentlich jeder Informatiker und Mathematiker im Schrank stehen haben, auch wenn man primär eher mit anderen Büchern lernt. Die Volumes 1-3 gibt es als boxed set zum Preis von 94,89 EUR (Stand Septmber 2006).

Ein Informatik-Duden erweist sich immer wieder als praktisch. Viele Begriffe kann man hiermit schnell klären, oder gar beim Stöbern auf ganz neue Begriffe stoßen, die man zuvor noch nie gehört hat.

Dieses Buch ist ebenso wie seine deutsche Übersetzung an die 1000 Seiten dick und wird meist als Standardwerk zu C++ angesehen: ist es doch vom Erfinder von C++ höchstpersönlich geschrieben! Ich persönlich finde das Buch aber nicht sehr gut geschrieben, was aber auch daran liegen mag, dass mir C++ sowieso etwas zuwider ist. Doch die Behandlung der Themen erscheint mir recht wirr sowohl in der Reihenfolge als auch im inneren Aufbau. Oft werden Dinge verwendet, die erst viel später erklärt werden.