Abo
  • Services:
Anzeige
Auch bei Brettspielen werden die Spieler zu Algorithmikern.
Auch bei Brettspielen werden die Spieler zu Algorithmikern. (Bild: Thane Plambeck/Flickr.com/CC BY 2.0)

Sebastian Stiller: Kombinatorische Probleme sind des Algorithmikers Liebling

Auch bei Brettspielen werden die Spieler zu Algorithmikern.
Auch bei Brettspielen werden die Spieler zu Algorithmikern. (Bild: Thane Plambeck/Flickr.com/CC BY 2.0)

Warum ist jeder, der ein Bücherregal sortieren kann, schon ein Algorithmiker? Die Antwort darauf gibt der Mathematiker Sebastian Stiller in seinem Buch "Planet der Algorithmen - Versteht sie, bevor sie euch verstehen", das ab heute erhältlich ist. Ein Auszug.

Anzeige

Der Mathematiker und Philosoph Sebastian Stiller nimmt den Leser seines Buchs "Planet der Algorithmen - Versteht sie, bevor sie euch verstehen" mit auf eine mehrtägige Tour durch die komplexe Welt der Algorithmen. Der folgende Auszug beschreibt ein kombinatorisches Problem.

Warnung vor kombinatorischen Spielsachen!

Reden wir kurz über Rechenpower: Sind wir großzügig und nehmen an, jedes Atom unseres Planeten wird in einen Superrechner verwandelt. Die rechnen dann, bis die Sonne die Erde verglüht - so in etwa 10 Milliarden Jahren. Setzen wir das zu der Größenordnung des Fahrplanproblems in Relation. Ein Großteil der Menschen, die in Berlin die U-Bahn benutzen, muss umsteigen, um das Ziel zu erreichen. Die Zeit, die eine U-Bahn von Station zu Station braucht, liegt nahezu fest. Zeit verliert man beim Umsteigen, wenn die Linien schlecht aufeinander abgestimmt sind. Die Anzahl der verschiedenen Möglichkeiten, die Linien der Berliner U-Bahn miteinander abzustimmen, ist in der Größenordnung der Anzahl der Atome unseres Planeten. Für ein Verkehrssystem mit doppelt so vielen Linien gibt es Anzahl der Atome mal Anzahl der Atome viele Möglichkeiten. Will man S-Bahn und Bus in Berlin und Brandenburg hinzunehmen, sind es über zehnmal so viele Linien. Anzahl der Atome der Erde hoch 10? (Gegen die Wucht der kombinatorischen Explosion ist auch die fantastischste Rechenpower ein Reizhusten.)

Weil kombinatorische Probleme so schön knallen, gehören sie zu den Lieblingsspielsachen von Algorithmikern und Komplexitätstheoretikern. In einer besonders beliebten Ecke des hiesigen Spielwarenladens stehen Probleme mit Netzwerken. Zum Beispiel die Party-Clique: Du möchtest eine möglichst große Party mit deinen Freunden feiern. Leider mögen sich nicht alle. Stell dir deinen Freundeskreis als ein Netz vor. Die Knoten sind deine Freunde. Zwei Freunde sind mit einer Kante verbunden, wenn die beiden sich hinreichend gut verstehen, um auf dieselbe Party zu kommen. Eine Teilmenge der Knoten, in der alle paarweise miteinander verbunden sind, nennt man - mathematisch - eine Clique. Das mathematische Problem namens Clique besteht darin, in einem gegebenen Netz die größte Clique zu finden. Du suchst aus der Menge aller deiner Freunde eine Teilmenge aus.

  • Planet der Algorithmen - Versteht sie, bevor sie euch verstehen. Sebastian Stiller. Knaus Verlag, 2015. 14,99 Euro. (Bild: Knaus Verlag)
Planet der Algorithmen - Versteht sie, bevor sie euch verstehen. Sebastian Stiller. Knaus Verlag, 2015. 14,99 Euro. (Bild: Knaus Verlag)

Probleme, bei denen man eine Teilmenge - also eine Kombination von Elementen einer Grundmenge - aussucht, nennt man kombinatorische Probleme. Clique ist eines der grundlegenden kombinatorischen Probleme der Algorithmik und der Komplexitätstheorie. Die Geschichte mit der Party ist ein Klassiker, aber sicher keine reale Anwendung. {Viele kombinatorische Probleme sehen eher wie Sandkastenprobleme aus und nicht wie relevante Fragestellungen.} In Wahrheit haben es diese Probleme faustdick hinter den Ohren. Aber dazu später.

Es gibt einen großen Unterschied zwischen Haralds Kleidungsproblemen und deiner Partyplanung. Er hat keine andere Möglichkeit, seine Frage zu beantworten, als alles durchzuprobieren. Deshalb explodiert sein Aufwand, eine Lösung zu finden. Bei der Auswahl der Gästeliste kannst du vielleicht das Netzwerk zu Hilfe nehmen. Das Netz gibt dem Problem Struktur. Anstatt alle Kombinationen durchzuprobieren, könnte ein Algorithmus eventuell diese Struktur nutzen, um mit geringerem Aufwand eine Gästeliste zu finden.

Das Kürzeste-Wege-Problem ist auch ein kombinatorisches Problem: Wähle aus der Menge aller Straßenkanten diejenigen aus, die einen Pfad bilden, der dich am schnellsten zum Ziel bringt. Kürzeste Wege sind kein schwieriges Problem. Das kann dein Navi, können diverse Webseiten, kann dein Smartphone. Aber wie steht es mit Folgendem: Du holst dein Kind vom Geburtstag ab und nimmst noch fünf andere mit. In welcher Reihenfolge fährst du sie nach Hause, um möglichst wenig herumzufahren? Man nennt es das Problem des Handlungsreisenden, das Traveling-Salesperson-Problem, kurz TSP. Es gibt Karten- und Routingwebseiten, die das Problem für fünf oder sechs Zwischenziele optimal lösen. Aber für 20 Ziele geben sie auf. (Das sieht so aus, als würde da etwas kombinatorisch explodieren.) Gibt es einen Algorithmus, der die Struktur des TSP nutzt, um ähnlich effizient zu sein wie der Dijkstra? In welchen Problemen explodiert der kombinatorische Sprengstoff und wann kann ein Algorithmus ihn entschärfen?

Der Text ist ein Auszug aus: "Planet der Algorithmen - Versteht sie, bevor sie euch verstehen" von Sebastian Stiller. Knaus Verlag, 2015. 14,99 Euro.


eye home zur Startseite
Nullmodem 19. Okt 2015

Ich hab mir die Leseprobe vom Ebook (iOS) geholt, 25 Seiten. Das Intro find ich etwas...

der_wahre_hannes 14. Okt 2015

Stimmt. Ich habe das Problem schon ein paar Leuten präsentiert, die mit Algorithmen bzw...

wikwam 13. Okt 2015

Wenn eine Einleitung so viel will und dann so wenig echte Reizpunkte setzt, kann das Buch...

der_wahre_hannes 13. Okt 2015

Man könnte auch den Teaser bis zum Ende lesen und den Satz "Ein Auszug" genau so...

476f6c656d 12. Okt 2015

Die Sinnhaftigkeit mag wahrscheinlich nicht direkt ersichtlich sein, aber vielleicht kann...



Anzeige

Stellenmarkt
  1. Host Europe GmbH, Hürth
  2. Striped Giraffe Innovation & Strategy GmbH, München
  3. Melitta Professional Coffee Solutions GmbH & Co. KG, Minden-Dützen
  4. PHOENIX CONTACT GmbH & Co. KG, Blomberg


Anzeige
Top-Angebote
  1. 62,90€ statt 69,90€
  2. (heute u. a. Fire-Tablets günstiger, DC-Filme und Serien reduziert, Sigma-Objektive reduziert)
  3. (u. a. For Honor Deluxe Edition 29,99€, Farcry Primal 19,99€, Far Cry 4 12,99€, The Crew 12...

Folgen Sie uns
       


  1. Open Routing

    Facebook gibt interne Plattform für Backbone-Routing frei

  2. Übernahme

    Vivendi lässt Ubisoft ein halbes Jahr in Ruhe

  3. Boston Dynamics

    Humanoider Roboter Atlas macht Salto rückwärts

  4. Projekthoster

    Github zeigt Sicherheitswarnungen für Projektabhängigkeiten

  5. Sicherheitslücke bei Amazon Key

    Amazons Heimlieferanten können Cloud Cam abschalten

  6. Luftfahrt

    China plant Super-Windkanal für Hyperschallflugzeuge

  7. Quad9

    IBM startet sicheren und datenschutzfreundlichen DNS-Dienst

  8. Intel

    Ice-Lake-Xeon ersetzt Xeon Phi Knights Hill

  9. Star Wars Jedi Challenges im Test

    Lichtschwertwirbeln im Wohnzimmer

  10. Zertifikate

    Startcom gibt auf



Haben wir etwas übersehen?

E-Mail an news@golem.de


Anzeige
Universal Paperclips: Mit ein paar Sexdezillionen Büroklammern die Welt erobern
Universal Paperclips
Mit ein paar Sexdezillionen Büroklammern die Welt erobern
  1. Disney Marvel Heroes wird geschlossen
  2. Starcraft 2 Blizzard lästert über Pay-to-Win in Star Wars Battlefront 2
  3. Free to Play World of Tanks bringt pro Nutzer und Monat 3,30 Dollar ein

Star Wars Battlefront 2 im Test: Filmreife Sternenkrieger
Star Wars Battlefront 2 im Test
Filmreife Sternenkrieger
  1. Electronic Arts Community empört über freischaltbare Helden in Battlefront 2
  2. Star Wars Mächtiger Zusatzinhalt für Battlefront 2 angekündigt
  3. Star Wars Battlefront 2 angespielt Sammeln ihr sollt ...

Coffee Lake vs. Ryzen: Was CPU-Multitasking mit Spielen macht
Coffee Lake vs. Ryzen
Was CPU-Multitasking mit Spielen macht
  1. Custom Foundry Intel will 10-nm-Smartphone-SoCs ab 2018 produzieren
  2. ARM-Prozessoren Macom verkauft Applied Micro
  3. Apple A11 Bionic KI-Hardware ist so groß wie mehrere CPU-Kerne

  1. Re: Macht ruhig weiter, Vivendi

    Umaru | 18:46

  2. Re: Rücksichtnahme auf kommerziellen Einsatz

    dark_matter | 18:46

  3. Re: Frontantrieb...

    Eheran | 18:43

  4. Re: Vorsicht !

    motzerator | 18:43

  5. Re: Die Zeiten ändern sich

    x2k | 18:42


  1. 17:08

  2. 16:30

  3. 16:17

  4. 15:49

  5. 15:20

  6. 15:00

  7. 14:40

  8. 14:20


  1. Themen
  2. A
  3. B
  4. C
  5. D
  6. E
  7. F
  8. G
  9. H
  10. I
  11. J
  12. K
  13. L
  14. M
  15. N
  16. O
  17. P
  18. Q
  19. R
  20. S
  21. T
  22. U
  23. V
  24. W
  25. X
  26. Y
  27. Z
  28. #
 
    •  / 
    Zum Artikel