Was sind die wichtigsten Algorithmen
-
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.
-
wichtigkeit laesst sich verschieden auslegen, aber das ist nicht wirklich das was du lernen musst. du solltest das lernen was am weitesten genutzt ist, denn die chancen sind gross dass du es auch mal imlementierst oder zumindestens anwendest.
schau dir deswegen erstmal die STL an und wie die funktionen oft implementiert werden. da hast du einfache linked lists bis zu red-black trees. zudem hast du z.b. sort, stable sort, maps, mutli maps, hash maps.. daran siehst du dass es nicht nur eine god-like version der dinge gibt, sondern spezialisierungen die dann vorteile haben.
wenn du damit fertig bist und weitere algorithmen kennen moechtest, muesstest du dein themengebiet eingraenzen. es gibt algorithmen zum komprimieren, fuer responsivness von UI, verwaltung von peta-byte datenbanken, zum erkennen von angriffen auf netzwerke, zum analysieren von source qulitaet ... das hat kein ende
-
1. Wie man eine Straße sicher überquert
2. Backanleitung auf der Rückseite von Tiefkühlpizza
3. Schriftliche Addition.
-
Buch macht kluch. "Algorithmen in C" fand ich einen prima Einstieg.
-
@rapso:
Danke erst mal für diese Richtungsweisung.@SeppJ:
Ich wollte erst einmal mit den einfach Sachen anfangen:D Agenten zu schreiben, die mit Sensoren und Aktoren eine Maschine sicher über die Straße gehen lassen, ist bestimmt ähnlich schwer wie einer Maschine das Lesen und Kochen einer Tiefkühlpizza beizubringen. Schriftliche Addition ist mit OCR Algos bestimmt noch am einfachste zu lösen.@Volkard: Meinst du das Buch von Robert Sedgewick?
-
Die Identitaet. Wenn der Algo nicht funktioniert, haben wir ein ernsthaftes Problem.
Sortieralgorithmen sind immer eine gute Sache, weil sie recht einfach sind und man von selectionsort bis bitonic-, intro- oder shellsort eine ganze Reihe von Algorithmen kennenlernt und nebenbei zwanglaeufig auch schonmal den heap.
-
@Citizen42:
Da du Algoritmhen irgendwie auf IT beziehst, hat SeppJ noch einen vergessen:4. besorgen eines koffeinhaltigen Heißgetränkes.
-
Hehe, ja ich impliziere Algorithmen und Datenstrukturen in einem Programmiererforum irgendwie mit IT. So ein Compiler castet auch einiges implizit, der ist da genauso frech wie ich.
Klar, Koffein wird bei mir genug stoffgewechselt, im Kaffe, Schwarzen Tee und auch auch im Grünen Tee ist ja genug davon vorhanden. Ich muss aber zugegeben, dass bei mir ab 40 schon der eine oder andere Melissentee dazu gekommen ist
Wo wir schon bei Programmierergetränken sind. Die Hackerbrause Club Mate schmeckt mir gar nicht, das hat was vom abgerauchten Zigarettenstummeln mit Gummibärchen + Energiedrink. Ich hätte als Hersteller da glatt Kotzbrause aufs Etikett geschrieben.
-
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.
Ein paar Stichpunkte zum Lernen mit C++:
-
lineare Suche (
array,vector,find,find_if,equal,strlenetc) -
Tupel (
pair,tuple, variadic templates) -
Variant (
boost::variantvs Cunion) -
Strategien, um O(N) in O(1) zu verwandeln
-
Caching (
std::string::sizevsstrlen,list::size) -
Entfernen von bestimmten Nachbedingungen (
vector::erasevsmove+vector::pop_back,unordered_map,unordered_set,std::hash,std::partition) -
"Naives" Sortieren in n^2 Schritten implementieren, um das in Zukunft erkennen und vermeiden zu können
-
binäre Suche (
array,vector,sort,binary_search,lower_bound) -
binäre Bäume (
map,set)
-
-
Strategien, um O(N) in O(1) zu verwandeln
--> Komplexitätslehre
* Reguläre Ausdrücke
4. besorgen eines koffeinhaltigen Heißgetränkes.
-
Super, da habe ich schon mal gute Startpunkte.
-
Citizen42 schrieb:
mit welchen Algos man sich dann auf jeden Fall mal beschäftigt haben sollte.
Binäre Suche
depth-first seach, breadth-first search
Bubblesort, Quicksort, Heapsort
Quine-McCluskey-Verfahrenwären mal ein praxisnaher Anfang in der Informatik.
wenn es mehr in mathematische Richtung gehen soll, sind einige
wichtige AlgorithmenFFT
Simplex-Algo, Ellipsoidmethode
Ford-Fulkerson
-
Man braucht ein grundlegendes Verständnis. Wenn du nicht verstehst, was eine verkettete Liste oder Hash Table ist, kommst du als Programmierer nicht weit. Man sollte auch grob verstehen, was Komplexitätsklassen sind.
Alles andere ist dann mehr oder weniger Geschmackssache. Ich würde mich gar nicht mal so intensiv mit den Standardalgorithmen befassen. Wen interessiert, wie Sortieralgorithmen funktionieren? Hat mich nie interessiert, hab auch nie welche implementieren müssen, gibts Implementierungen für jede Sprache. Das lernt man alles hauptsächlich im Studium, damit man die Basis schafft, weitere Algorithmen verstehen und entwickeln zu können. Willst du auch noch so weit kommen, oder gehts dir eher darum, irgendwelche Standardsachen zu kennen, damit du mitreden kannst?
-
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.
