Entstehung der Algorithmen?
-
ich frag mich schon seit längerem, wie all die coolen algorithmen gefunden wurden, die wir heutzutage alle fast selbstverständlich benutzen(beispiel: sort algorithmen).
Dass die Leute einfach mal was ausprobiert haben und das war dann toll glaub ich irgendwie nicht, oder dies trifft wenn dann nur auf eine Minderheit der algorithmen zu, oder?
-
Ne, die meisten Sachen hat sich halt jemand ausgedacht. Ideen werden meist aus der Not heraus geboren. Wenn irgendwas zu langsam oder zu schlecht ist, dann macht man sich halt Gedanken wie man es schneller bzw. besser machen kann. Und wenn man gut ist, dann findet man nachher ein Verfahren, was eine bestimmte Klasse von Problemen gut behandelt. Wenn man sehr gut ist, dann kann man die Lösung auch so formulieren, dass jemand anders sie begreift
.
-
Die meisten Algos sind doch logischer Natur, die man doch erstmal 1:1 umsetzt. So mache ich das jedenfalls immer, ich "denke" und spiele es im Kopf durch und notfalls mit Papier und Bleistift... yo, und das setz ich dann 1:1 in Code um. Wichtig ist das es erstmal funzt. Das beste Beispiel ist doch der Boublesort. Wie aus dem Leben gegriffen.
Find ich einfach nur genial und kann ich mir sogar bildlich vorstellen. OK, ob es performant ist, ist dann erst die zweite Frage. 
Da muß man sich dann halt was anderes ausdenken und so gibts halt mehrere Algos.
-
Artchi schrieb:
Das beste Beispiel ist doch der Boublesort. Wie aus dem Leben gegriffen.
genau. ich bringe gerade ein paar realschülern programmieren bei. vorletzte woche habe ich ein paar kartenspiele gekauft und sie sortieren lassen. so lange, bis was ausreichend einfaches rauskam, was sie programmieren können. es war bubblesort.
ganz normale leute erfinden bubblesort. und viele viele andere algos. das problem ist nur, daß jemand anderes die algos schon vorher erfunden hat. um sachen zu erfinden, die noch keiner vorher erfunden hat, muss man extrem viel glück haben, weil so viel schon erfunden ist. passiert aber trotzdem immer wieder.
-
ich hab mal Speichern und Wiederherstellen von Binärbäumen erfunden *stolz auf mich bin
* leider gabs das schon so dass ich es nicht patentieren und damit Millionen machen konnte 
Wenn ich mich so an unsere Klausuren entsinne (sortierung von 2 Stapeln mithilfe von einem dritten) und ähnliches so denke ich dass vieles ziemlich oft "neuerfunden" wird. Im kleinen Ramhen macht das einfach Spass - auch wenn es schon 1000 mal gibt.
Im Prinzip wie schon erwähnt: es gibt ein Problem und das löst man - aber am besten nicht direkt im Compiler sondern mit Papier und Stift ;). Dann setzt man es um, dann verbessert man es oder jemand sieht es und wird dadurch "inspiriert" so dass er eine stark verbesserte oder gar eine neue Version findet.Wenn man das Problem und die Lösung auch noch mathematisch Formulieren kann, kann diese "direkt" auf der mathematischen Ebene gelöst bzw. verbessert werden.
-
Vor kurzem hab ich mal ein "Ich denke mir eine Zahl aus zwischen 0 und 100, ratte sie. Nein, sie ist grösser. Nein kleiner. Richtig 60." Spiel für mein Taschenrechner geschrieben und mal meine Mitschüler (13 Jahre Schule, keine Ahnung was das in Deutschland entspricht) ein paar Runden spielen gelassen. Manche haben einfach geraten und andere haben systematisch immer den Suchbereich halbiert und dabei wissen sie noch nicht einmal was binäres Suchen ist.
Anderes Beispiel: Es geht darum festzustellen ob ein Kartenspiel komplet ist. Da gehen die meisten Leute so vor, dass sie Karten mit gleichem Bild beieinanderlegen und dann alle Stappel auf Vollständigkeit überprüfen. Ist eine Art Hashtable die da aufgebaut wird.
Ein weiteres Beispiel ist der fortgeschrittene UnokartenSpieler. Man kann ja wenn man mehrere Karten mit der gleichen Nummer hat sie alle auf einmal legen. Er sortiert dann als erstes sein Anfangsblatt. Hierzu werden entweder sämtliche Karten genommen und dann immer die kleinste verschoben, was ein Selektionsort ist, oder es wird Karte für Karte genommen und sie jeweis an der richtigen Stelle eingefügt, was ein Insertionsort wäre. Jede neue Karte wird dann an der entsprechenden Stelle eingefügt was wieder ein Insertionsort wäre. Wenn nun eine Karte gelegt wird schaut er, ob er ihre Nachbaren auch mitlegen kann, was einem Elimineren von mehrfach Einträgen gleichkommt.
Es gibt sicher noch unzählige andere Beispiele die mir im Moment nicht einfallen.
-
Ben04 schrieb:
Anderes Beispiel: Es geht darum festzustellen ob ein Kartenspiel komplet ist. Da gehen die meisten Leute so vor, dass sie Karten mit gleichem Bild beieinanderlegen und dann alle Stappel auf Vollständigkeit überprüfen. Ist eine Art Hashtable die da aufgebaut wird.
ich zähle einfach die karten.
fall sich feststellen will, welche karte fehlt, mache ich einen schritt radix-sort, wo ich nach farben trenne, und dann einen schritt auf-die-hand-steck-sort (im wesentlichen insertion-sort) und sehe dann die lücke.
-
volkard schrieb:
Ben04 schrieb:
Anderes Beispiel: Es geht darum festzustellen ob ein Kartenspiel komplet ist. Da gehen die meisten Leute so vor, dass sie Karten mit gleichem Bild beieinanderlegen und dann alle Stappel auf Vollständigkeit überprüfen. Ist eine Art Hashtable die da aufgebaut wird.
ich zähle einfach die karten.
Da die meisten Leute aber nicht bis 52 zählen können ohne sich zu verzählen (kein Witz) scheidet diese Vorgehensweise für den normalen Anwender aus. Meinen Beobachtungen zufolge gehen die mit meisten Menschen wirklich mit der von mir beschriebenen Weise vor, ob diese jetzt optimal ist, ist natürlich eine andere Frage.
-
Ben04 schrieb:
Da die meisten Leute aber nicht bis 52 zählen können ohne sich zu verzählen (kein Witz) scheidet diese Vorgehensweise für den normalen Anwender aus.
ok, man ist normalerweise besoffen, wenn man ein kartenspiel checken muss.
dann kann man aber zur sicherung feine zwischenschritte machen. zum beispiel 4-er-stapel legen. also immer nur bis 4 zahlen und dann einen stapel mit 4 ablegen. wenn's zum schluss aufgeht, zählt man noch die stapel. wenn's nicht aufgeht, ist das deck kaputt. wenn man sich bei einem 4-zählen ablengen ließ und nicht ganz sicher ist, zählt man nochmal.Meinen Beobachtungen zufolge gehen die mit meisten Menschen wirklich mit der von mir beschriebenen Weise vor, ob diese jetzt optimal ist, ist natürlich eine andere Frage.
du spielst meistens mit nicht-informatikern karten. ging mir auch so. inzwischen spiele ich gar nicht mehr karten. aber ich brauche natürlich immer wieder mal karten, um algorithmen, die auf arrays arbeiten, zu erfinden.
-
Ich frage mich, ob es gute Bücher gibt mit Algorithmensammlungen, damit man nicht alles neu erfinden muss. Am besten wären weiterführende Algorithmen, die man nicht im Cormen findet.
Zum Kartenspiel: Die Methode Haufen mit vier oder acht Karten zu legen ist besonders dann gut, wenn man doppelte Karten vermutet, oder genau wissen will welche fehlt. Ob eine fehlt kann mit Nachzählen einfacher ermittelt werden.
-
Ponto schrieb:
Ich frage mich, ob es gute Bücher gibt mit Algorithmensammlungen, damit man nicht alles neu erfinden muss. Am besten wären weiterführende Algorithmen, die man nicht im Cormen findet.
kenne keinen Cormen.
aber es gibt eine umfassende sammlung namens
The Art Of Computer Programming
da steht einfach alles drin.
-
volkard schrieb:
Ponto schrieb:
Ich frage mich, ob es gute Bücher gibt mit Algorithmensammlungen, damit man nicht alles neu erfinden muss. Am besten wären weiterführende Algorithmen, die man nicht im Cormen findet.
kenne keinen Cormen.
aber es gibt eine umfassende sammlung namens
The Art Of Computer Programming
da steht einfach alles drin.Ich meinte Cormen/Leiserson/Rivest - Introduction to Algorithms
Die ersten Teile von TAOCP ist schon alt und der Rest noch nicht geschrieben.
So habe ich darin k-dimensionale Bäume oder Rect-Trees nicht auf Anhieb gefunden.
-
Such' mal nach "Robert Sedgewick: Algorithmen", da sind die meisten Standardverfahren drin beschrieben, und halbwegs verständlich dazu.
-
Ponto schrieb:
Die ersten Teile von TAOCP ist schon alt und der Rest noch nicht geschrieben.
So habe ich darin k-dimensionale Bäume oder Rect-Trees nicht auf Anhieb gefunden.ok. das ist ein problem. ich lese auch in jedem neuen algorithmenbuch 5 neue datenstrukturen oder algos. und mein weg für ein umfassendes bild ist, viel zu googlen. immer, wenn hier einer über ein verfahren spricht, das ich nicht kenne. in "communications of the acm" hab ich früher einige sehr interessante sachen gelesen, die nirgends sonst zu finden waren.
ich hab aber auch mal zusammenstellungen im netz gefunden, die total vollständig aussahen. aber man musste für jeden artikel löhnen, das hat mich nicht begeistert und ich hab niux davon gebookmarkt.