Was sind die wichtigsten Algorithmen
-
Mechanics schrieb:
Wen interessiert, wie Sortieralgorithmen funktionieren? Hat mich nie interessiert, hab auch nie welche implementieren müssen, gibts Implementierungen für jede Sprache.
Wenn man sich mit Sortieralgoritmen beschaeftigt und einige davon implementiert, dann lernt man ganz spielerisch anhand von sehr einfachen Algorithmen das "Divide&Conquer"-Prinzip kennen, das letztendlich in vielen Bereichen sehr nuetzlich sein kann. Man wird auch bezueglich bestimmter Eigenschaften von solchen Algorithmen sensibilisiert: Zum Beispiel der Stabilitaet des Verfahrens. Und vielleicht versucht man auch mal, so einen Algorithmus zu parallelisieren und merkt dabei, dass in so einem Zusammenhang ploetzlich ein anderer Algorithmus als im rein sequentiellen Fall optimal sein koennte.
Ich denke, dass es durchaus ganz gut ist, am Anfang ein paar Sortieralgorithmen zu implementieren.
-
Citizen42 schrieb:
Ich möchte mich in nächster Zeit ein wenig den Algorithmen und Datenstrukturen widmen. Nun ist die Auswahl groß und daher würde ich gerne von euch in Erfahrung bringen, mit welchen Algos man sich dann auf jeden Fall mal beschäftigt haben sollte.
Generell ist das, was in entsprechenden Büchern über das Thema gebracht wird, vermutlich eine sehr gute Grundlage.
Citizen42 schrieb:
Was sind die wichtigsten Algorithmen
Diese Frage ist schwer zu beantworten, wenn Du nicht sagst, was Du unter "wichtig" verstehst. Letztendlich ist das natürlich abhängig von Deinem generellen Interessensgebiet. Was für Algorithmen man braucht, ist immer davon abhängig.
Ein anderer Ansatzpunkt um eine "Wichtigkeit" zu quantifizieren ist vielleicht zu gucken, auf welche Algorithmen sich Leute besonders häufig beziehen. Zumindest im wissenschaftlichen Umfeld wird so etwas gemessen. Zum Beispiel durch Google Scholar. Dort fällt einem zum Beispiel auf, dass der Originalartikel zur schnellen Fouriertransformation sehr häufig zitiert wird:
http://scholar.google.de/scholar?hl=de&q=Cooley+Tukey&btnG=&lr=
Letzt ist mir auch aufgefallen, dass es im Umfeld des Expectation Maximization Algorithmus sehr viele Zitate gibt:
http://scholar.google.de/scholar?q=EM+algorithm&btnG=&hl=de&as_sdt=0%2C5
Das finde ich interessant, weil es praktisch direkt aussagt, dass solche statistischen oder probabilistischen Ansätze sehr häufig eingesetzt werden.
Natürlich kann man jetzt einwänden, dass Algorithmen, die wirklich häufig benötigt werden, sowieso einfach als Textbuchwissen angenommen werden und von niemandem mehr explizit referenziert werden. Trotzdem würde mich interessieren, ob hier Leuten mal aufgefallen ist, dass irgendeine Veröffentlichung zu einem Algorithmus außergewöhnlich häufig zitiert wird. So häufig, dass man sich fragen muss, ob der dort beschriebene Algorithmus irgendwie besonders zentral ist oder Ideen verwirklicht, die Leute vielfach aufgreifen.
-
Solche Algorithmen braucht man halt sehr oft, wenn man irgendwelche Rohdaten, sprich Bilder, Messkurven, Toene verarbeiten und filtern will und ist zumindest schwer genug, dass man irgendwelches Referenzmaterial braucht.
Solche grundlegenden Sachen wie lineare Suche, binaersuche, Addition, Identitaet braucht natuerlich jeder mal, aber die sind so alltaeglich, dass man sie gar nicht als eigenen Algorithmus wahrnimmt.
-
Ich habe mal mit einem Bekannten geredet, der als Webentwickler arbeitet und der hat in 10 Jahren noch nie irgendeine Datenstruktur oder einen Algorithmus selbst implementiert. Das ist jetzt nicht repräsentativ für die Branche, aber es scheint auch Entwickler zu geben, die einfach nur Frameworks nach Kundenwünschen zusammen klatschen. Da ist dann eher Detailwissen über die hundert Frameworks nötig, als tieferes Informatikwissen.
Wie dem auch sei, ich bin an Informatik durchaus interessiert, da ich es spannend finde wie Sachen funktionieren. Das wollte ich schon seit Kindesbeinen an wissen. Das Streben nach Wissen war schon immer da, die Motivation diesen durch Schule oder Studium zu erlangen nicht.
Bei mir hieß und heißt es halt immer, selbst ist der Mann.Solange ich was nachlesen und ausprobieren kann, solange kann ich wachsen.
-
Citizen42 schrieb:
Ich habe mal mit einem Bekannten geredet, der als Webentwickler arbeitet und der hat in 10 Jahren noch nie irgendeine Datenstruktur oder einen Algorithmus selbst implementiert. Das ist jetzt nicht repräsentativ für die Branche, aber es scheint auch Entwickler zu geben, die einfach nur Frameworks nach Kundenwünschen zusammen klatschen. Da ist dann eher Detailwissen über die hundert Frameworks nötig, als tieferes Informatikwissen.
Und dann erzaehlen sie, dass Programmieren total einfach ist, weil es nur darauf ankommt, die richtigen Befehle hintereinanderzuklatschen. Ich habe mal mit einer Skriptsprache fuer ein Spiel gearbeitet und das war auch so. Man geht die Einzelschritte durch und gibt Aktionen an, aber bei richtigem Programmieren muss man in erster Linie ein Konzept von der Problemloesung entwickeln und sich von sehr abstrakt bis zur konkreten Implementierung durcharbeiten.
-
Citizen42 schrieb:
...Webentwickler "arbeitet"...
-
Citizen42 schrieb:
Ich habe mal mit einem Bekannten geredet, der als Webentwickler arbeitet und der hat in 10 Jahren noch nie irgendeine Datenstruktur oder einen Algorithmus selbst implementiert. Das ist jetzt nicht repräsentativ für die Branche, aber es scheint auch Entwickler zu geben, die einfach nur Frameworks nach Kundenwünschen zusammen klatschen. Da ist dann eher Detailwissen über die hundert Frameworks nötig, als tieferes Informatikwissen.
Auch wenn man Algorithmen nicht selbst implementiert, sondern sie nur durch irgendwelche Bibliotheken nutzt, sollte man wissen, wie sie im Prinzip funktionieren. Ich gebe mal ein Beispiel an, warum man das wissen sollte:
Ich habe vor ein paar Jahren mal die Laufzeit von schnellen 3D Fouriertransformationen in Abhaengigkeit von der Systemgroesse gemessen. Das habe ich sehr bewusst gemacht, weil ich in etwa eine Vorstellung hatte, wie das wohl aussieht. Es kam das da raus (gemessen wurden die FFTW und die FFT in der MKL von Intel):
http://i.imgur.com/RA2yVYQ.png
Man sieht da sofort, dass es bei bestimmten Problemgroessen Sinn machen kann, die Problemgroesse kuenstlich zu vergroessern, um eine bessere Laufzeit zu erhalten. Ich hatte das gemessen, um genau zu sehen, bei welchen Problemgroessen ich das machen sollte. Wenn man nicht weiss, wie schnelle Fouriertransformationen funktionieren, dann hat man keinen Anlass, bezueglich derartiger Aspekte mal nachzugucken und man hat am Schluss vielleicht ein Programm, das alles andere als optimal ist, weil man einfach nur voellig naiv einen Algorithmus in einer Bibliothek genutzt hat, der schon das richtige Ergebnis liefert.
-
Citizen42 schrieb:
Ich habe mal mit einem Bekannten geredet, der als Webentwickler arbeitet und der hat in 10 Jahren noch nie irgendeine Datenstruktur oder einen Algorithmus selbst implementiert.
Das ist bei Webentwicklern auch sehr sehr wahrscheinlich. Kommt vielleicht noch drauf an, wer sich als Webentwickler bezeichnet, aber ich denke, jemand der Backends in J2EE schreibt wird sich nicht unbedingt als Webentwickler bezeichnen. Aber so ein richtiger "Webentwickler" ist so ziemlich das anspruchsloseste, was ein Informatiker machen kann.
-
ich würde mich dem, was Gregor geschrieben hat anschließen.
Als ergänzende Richtlinie noch:
zuerst einfach, später schwerer bzw. "komplexer" (oder chaotischer...).
Und: Spaß hat Vorrang, also Algorithmen, die im Herzen brennen
Aber: Wenn ein so furchtbar interessierender Algorithmus einen überfordert, nicht entmutigen lassen, sondern -> wenn es geht, zerlegen, einfachere Muster finden.
Schritt für Schritt.So hausbacken das auch klingt. Ich kann mich noch recht gut daran erinnern, welche Art von innerer Feierlichkeit-Stimmung bei mir aufkam, als ich beim Ausfüllen einer Quadrierliste ganz intuitiv auf z.b. 16 * 16 = 160 + 60 +36 kam und dann viel schneller quadrieren konnte (23 * 23 = (230+30) * 2 + 3*3 usw.). D.h.: Auch bei einfachen Sachen kann man tolle Methoden entdecken, wenn man sich nur öfter (also i.d.R. mit Lust) damit beschäftigt.
Wenn man versucht, sich Sachen in die Birne zu prügeln, nur weil sie z.B. Insider-Group-Relevant oder im populären Sinne wichtig erscheinen, findet man interessante Zusammenhänge vielleicht weniger wahrscheinlich.Für bestimmte Probleme gibt es im Internet Testprogramme zum Algorithmenvergleich, die dann konkret weiterhelfen
Generelle Materialabhängigkeit kann man mit Sortieralgorithmen gut lernen.
Viele spannende Geschichten gibt es in der Medienwelt mit Bild-und Tonbearbeitung, Verschlüsselung usw.
Recht nützlich und wichtig fände ich ein gutes Verständnis von Zufallszahlengeneratoren, Möglichkeiten und Grenzen (siehe hierzu auch Zitate in Zeitschriften).
Hilfreich für Grafikprogrammierung ist ein gutes Verständnis der linearen Algebra.Relativ wichtig wären auch aktuelle Entwicklungen oder Modeströmungen, sowas wie "Schwarmintelligenz", KI und Roboter(programmier)technik(en) (und->Tauschbörsen).
Bei der Parallelisierung gibt es manchmal große Vorteile, manchmal gar keine.
Das Licht selbst zum Beispiel braucht sich nicht zu parallelisieren, hat, wenn man so will, "alle Zeit der Welt"
-
Citizen42 schrieb:
Ich habe mal mit einem Bekannten geredet, der als Webentwickler arbeitet und der hat in 10 Jahren noch nie irgendeine Datenstruktur oder einen Algorithmus selbst implementiert.
Ich hatte mal einen Kollegen, bei dem war es ähnlich. Wir haben zusammen ein Projekt bearbeitet, bei dem es im Wesentlichen nur darum ging, Daten von A nach B zu schaufeln (wie so oft). Aber es stellte sich heraus, dass man die Abhängigkeiten in einen bestimmten Teilaspekt als Graphenproblem auffassen konnte, und mit dem richtigen Algorithmus war meine Lösung auf einmal Größenordnungen schneller als seine ad-hoc-Lösung. Ich weiß die Details nicht mehr, es war was ganz einfaches, Tiefensuche oder Topologische Sortierung oder sowas. Halt blöd, wenn man davon noch nie was gehört hat.
