Das Programmieren ist die Kunst, Algorithmen (möglichst die optimalen) auf Daten bzw. deren Strukturen anzuwenden, mehr eigentlich nicht. Man kann eigentlich alles als Datenstruktur darstellen, seien es nun zu regelnde Maschinen oder das Manuskript eines Groschenromans, whatever you like. Wie die Tabellen unten zeigen, ist es sehr von Vorteil, sich Gedanken über die zu wählenden Algorithmen zu machen. Gerade so grundlegende Dinge wie das Sortieren seiner Daten frißt Rechnerzeit und damit Kosten. Man hat wenig davon wenn sich die Sekretärin regelmäßig die Fingernägel lackiert, weil sie auf das Sortieren der Kundendaten wartet, nur weil sich der Programmierer etwas zu wenig Gedanken gemacht hat (wenn überhaupt), welchen Algorithmus er verwenden soll.
Ein weiteres Puzzleteil der Kunst ist es, sich mit den Eigenarten der gewählten Programmiersprache abzufinden. Das ist nicht immer einfach, man sagt z.B. von einem Ingenieur wie mir, der das Programmieren vor über 30 Jahren kennenlernte, daß er wirklich objektorientiert garnicht mehr lernen könne. Ich neige dem zuzustimmen.
Nun steht der Programmierneuling also vor der üblichen Aufgabe, "Hello World" auf den Monitor zu zaubern, und das ist in vielen Fällen auch kein Problem, in Python schreibe man einfach
print "Hello World" (ab Version 3 setzt man das zu schreibende in Klammern), das ist nun wirklich nichts weltbewegendes.
Aber oh weh, man versucht sich in Sprachen wie C++ mit integrierter Entwicklungsumgebung an dem Projekt. Ein solches, also Projekt, wollen diese Dinos dann erstmal von uns haben, man sieht einen Haufen automatisch erzeugter Dateien, alles ganz nützlich für wirklich große Programmieraufgaben, aber unser armer Neuling kann nur abwinkend die Flucht ergreifen, falls in den Tiefen der Einstellungsoptionen der IDE auch nur ein Häkchen falsch gesetzt ist. Der arme Wicht, der davon träumte, in wenigen Wochen seinen eigenen Ego-Shooter mit 100 Charakteren in die Tasten zu hämmern, hängt wahrscheinlich nach kurzer Zeit schon wieder vor einer Playstation und ballert dumm rum.
Leider geht es ohne Mathematik nicht, wer die reale Welt simulieren will muß sich auch noch mit physikalischen Gesetzen rumquälen. Das geht nicht anders, auch wenn es noch so schöne Software geben mag, die mit einigen Mausklicks die tollsten Sachen für uns programmiert. Es hat seine amüsanten Seiten, wenn sich Golfbälle verhalten wie auf dem Mond, von einer Simulation ist da aber nicht mehr zu sprechen. Ohne etwas von Gravitation, Flugbahnberechnung etc. zu verstehen bleibt alles Spielerei ohne je zu einem guten Spiel zu werden.
Es wird schon mehr, Algorithmen, Daten, Mathe, Physik... Intimere Kenntnisse der Hardware habe ich noch vergessen, denn auch dies ist nicht unbedingt einfacher geworden durch die Möglichkeit, auch das Thema Vernetzung in unsere Programmierproblematik miteinzubeziehen... Das 12-jährige Wunderkind, das sich in die Rechner der USAF einhackt bleibt doch wohl eher ein Hollywoodmythos (ganz davon abgesehen daß sich ein Rechner, der weltweite Nuklearkriegsscenarien berechnet kaum von Tic Tac Toe beeindrucken läßt) Wie hieß dieser absurde Film eigentlich, lebensmüder Programmierer, der sich von zwei Teenies in der letzten Sekunde dazu überreden läßt, die Welt zu retten, selbst für Hollywood ein bißchen albern. Es soll aber Leute geben, die sowas als Kultfilm bezeichnen...Deep Thought hilf !!!
The xSortLab Applet stellt ein Java-Applet zur Verfügung, mit dem sich Bubble Sort, Selection Sort, Insertion Sort, Merge- und Quick-Sort vergleichen lassen. Eine graphische Darstellung zeigt die fünf Algorithmen bei der Arbeit, 16 Elemente zu sortieren. Die Ergebnisse habe ich hier tabellarisch zusammengefasst, recht beachtliche Unterschiede bei DER zentralen Aufgabe der EDV.
Es macht wenig Sinn, hier die Zeiten zu messen, da die graphische Darstellung der Sortiervorgänge aus didaktischen Gründen recht langsam abläuft. Man beachte aber, daß etwa Bubble 120 mal vergleicht und 135 mal umkopiert, während Quick-Sort für dasselbe Problem lediglich 44 mal vergleichen und 39 mal umkopieren muß. Etwas eindringlicher wird einem vor Augen geführt, wenn man in einem anderen Modus die Anzahl der zu sortierenden Elemente erhöht.
Gucks du:
Die beiden mit den schnellen Ausführungszeiten lassen einem nicht mal die Zeit, den Kaffee umzurühren, den man bei Bubble gekocht hat.
Ich denke, man kann sich vorstellen, daß es wirklich wichtig ist, in einem großen Datenbestand nach dem optimalen Algorithmus zu suchen.
Leider gibt es den optimalen Algorithmus nicht wirklich, da es immer auch auf die Daten und deren Verteilung bzw. Vorsortierung ankommt. Oft sind ja
nur wenige Datensätze in einen vorhandenen Bestand zu integrieren. Worauf es hier ankommt dürfte klar geworden sein, bei 10 Mio. Daten würde Bubble
etwa 10 Stunden benötigen, Quick hingegen gute 6 Sekunden. Die Elemente müssen natürlich auch in den Hauptspeicher reinpassen, sonst wird´s noch
langsamer.
Neben dem Sortieren gibt es natürlich noch eine Reihe weiterer Standardaufgaben für Computer, über deren Algorithmen man sich Gedanken machen sollte.
Hier seien einige genannt, für genauere Analysen sollte man sich mit guten Lehrbüchern bewaffnen oder das Internet bemühen.
Zufallszahlen sind ein altes Problem der EDV, da diese schwerlich rein zufällig sind, möglichst gleichverteilt sein sollten, möglichst auch noch reproduzierbar und eben schnell berechnet
mathematische Probleme wie z.B. die Lösung von geschlossen nicht lösbaren Integralen, DGLen, nichtlinearen Gleichungssystemen etc.
die Darstellung von Daten in Listen, Bäumen etc. zum schnellen Finden von einzelnen Daten
schnelle Fourier-Transformation (FFT) kommt z.B. zum Einsatz, wenn jemand ein Musikstück übers Internet erkennen lassen möchte, wo man früher den DJ beim Radio anrief. Riesige Datenbanken haben digitale Fingerabdrücke, sprich Spektren, von Millionen Musikstücken. Natürlich spielt hier neben der FFT die Anordnung der Daten, also deren Sortierung, eine sehr wichtige Rolle, um schnelle Ergebnisse zu liefern.
Erkennung von Mustern als Text, also z.B. die Suche nach Namen im Telefonbuch
Verschlüsseln und Entschlüsseln von Daten, die vertraulich bis streng geheim sind. Auch dies kommt standardmäßig bei jeder E-Mail vor, bei Banktransaktionen wird spätestens deutlich wie wichtig gute Verfahren sind (gut heißt hier sicher und schnell)
Diese wenigen Beispiele zeigen eines recht deutlich, im wesentlichen ist das Suchen und Sortieren der Daten immer mit im Spiel und damit zentraler Punkt bei der Programmoptimierung. Zum Schluss noch ein Beispiel für eine Funktion, die man sich anschauen sollte, die von Ackermann. Es ist schnell zu finden, wie die Arbeitet, es ist aber wirklich ratsam, dieses Monster mal händisch zu lösen. Wer Ack(1,1) oder Ack(3,3) noch auf dem Papier berechnet hat, versuche Ack(4,2) und erlebe sein blaues Wunder. In Python programmiert hat mir der Rechner die rund 19700 Dezimalstellen nur so um die Ohren gehauen, ein wirkliches Aha-Erlebnis für jeden, der sich mit Algorithmen und deren Realisierung beschäftigt. Etwas wie Ack(10,10) erscheint mir seitdem irgendwie Außerirdisch, eine Zahl dafür ist kaum vorstellbar, aufschreiben geht gar nicht, und der Algorithmus, der das Monster löst wartet darauf realisiert zu werden. Desgleichen, oder noch erschreckender, ist Grahams Zahl. Wer sich damit beschäftigt (der Wikipedia Artikel ist ein guter Anfang) wird verstehen, warum mir die Ziffernfolge 2464195387 einen ziemlichen Respekt einflößt.