Cover der Zusammenfassung von „Algorithmen kompakt“

Technologie & Zukunft · 15 Min.

Algorithmen kompakt

Aditya Bhargava · 2016

Für wen ist dieses Buch?

Für Studierende, Programmieranfänger und Neugierige, die verstehen wollen, wie Suche, Routenplanung und Empfehlungen funktionieren, ohne viel Mathematik. Es ist ein Einstiegsbuch, illustriert und leicht zu lesen.

Kostenlos laden · iPhone und Android

Zu dieser Zusammenfassung gibt es in der App auch eine Vertonung.

3 Kernideen zum Mitnehmen

  1. Die Breitensuche erklärt, warum eine Freundschaftsanfrage an den Freund eines Freundes so leicht vorzuschlagen ist.

  2. Gewichtete Verbindungen ändern die Antwort: Der Weg mit den wenigsten Zwischenstopps muss nicht der schnellste sein.

  3. Bei sehr schweren Problemen ist eine Faustregel, die schnell ein gutes Ergebnis liefert, oft mehr wert als die perfekte Lösung, die zu lange dauert.

Die Daten einmal aufzuräumen kann Tausende spätere Suchvorgänge sparen.
Ein Gedanke aus „Algorithmen kompakt“, in den Worten von 15 Minuten

Leseprobe

Die ersten Abschnitte

Ein illustrierter Leitfaden ohne Angst vor Mathematik

Algorithmen kompakt von Aditya Bhargava, erschienen 2016, ist eine Einführung in die Informatik für alle, die Angst vor diesem Thema haben. Statt seitenweise Formeln gibt es Handzeichnungen, Beispiele aus dem Alltag und wenig Mathematik. Der Untertitel des Originals verspricht einen illustrierten Leitfaden für Programmierer und Neugierige, und er hält, was er verspricht.

Ein Algorithmus ist nur ein Rezept: eine Abfolge von Schritten, um ein Problem zu lösen. Das Buch zeigt die klassischen Verfahren, die Probleme, die jedes davon löst, und die Überlegungen dahinter. Die Codebeispiele in Python sind kurz, und wer nicht programmiert, kann den Ideen anhand der Abbildungen folgen.

Der Grundgedanke ist, dass die Kenntnis einiger elementarer Algorithmen hilft, das richtige Werkzeug zu wählen. Zwischen zwei Wegen, dasselbe Problem zu lösen, ist es entscheidend zu wissen, welcher schneller ist und warum, wenn Systeme Tausende von Menschen bedienen.

Binäre Suche: mit Methode raten

Der erste Algorithmus ist die binäre Suche. Als Bild dient das Spiel, bei dem man eine Zahl zwischen 1 und 100 erraten soll. Wenn du zuerst 1, dann 2, dann 3 tippst, können es hundert Versuche werden. Beginnst du in der Mitte und erfährst bei jeder Antwort, ob die Zahl größer oder kleiner ist, streichst du bei jedem Tipp die Hälfte der Möglichkeiten und triffst in wenigen Zügen.

Die binäre Suche funktioniert nur, wenn die Liste sortiert ist. Deshalb sind Wörterbücher und Telefonbücher alphabetisch geordnet. Niemand liest alle Namen, um einen zu finden: Man schlägt in der Mitte auf und passt sich an. Bei einer Liste mit einer Million Einträgen findet die Methode das Ziel in etwa zwanzig Schritten.

Die Lehre lautet, dass sich Ordnung vor der Suche enorm lohnen kann. Oft spart es Tausende späterer Suchvorgänge, wenn man die Daten einmal richtig aufräumt.

Big O: messen, wie die Kosten wachsen

Das Buch stellt die Big-O-Notation vor, die Sprache, um über die Geschwindigkeit von Algorithmen zu sprechen. Sie misst nicht Sekunden, sondern wie die Anzahl der Schritte mit wachsender Datenmenge zunimmt. So lassen sich Verfahren vergleichen, ohne vom Computer abhängig zu sein.

Eine ganze Liste zu durchsuchen, um einen Eintrag zu finden, wächst im gleichen Verhältnis zur Länge der Liste, das nennt man lineare Zeit. Die binäre Suche wächst sehr langsam, die sogenannte logarithmische Zeit. Das einfachste Sortieren wächst viel schneller. Und es gibt Probleme, deren Aufwand explodiert, etwa das Prüfen aller möglichen Routen zwischen vielen Städten.

Die Moral: Bei wenigen Daten taugt jedes Verfahren, bei vielen ist der Unterschied gewaltig. Eine Tabelle, die mit hundert Zeilen gut läuft, kann bei hunderttausend hängen bleiben, und der Grund liegt in der Art, wie die Kosten wachsen.

11 weitere Abschnitte in der App

In der App weiterlesen

Lies die ganze Zusammenfassung oder hör sie dir an und prüfe dich am Ende mit dem Quiz zum Buch. Die App ist kostenlos zu laden, und jeden Tag gibt es eine Gratis-Lektüre.

Über Aditya Bhargava

Aditya Bhargava ist Software-Ingenieur und Autor von Entendendo Algoritmos (Grokking Algorithms), erschienen 2016. Er hat auch die Illustrationen des Buches gezeichnet, was den visuellen Stil des Werks erklärt. Auf seinem Blog veröffentlicht er illustrierte Texte über Programmierung, darunter den bekannten visuellen Leitfaden zu Functors, Applicatives und Monads.