Effiziente Algorithmen

[Sherlock]

Also wenn sortieren zu kompliziert ist, dann schließe ich mich dem Vorschlag "binäres Suchen" an.

Man kann sehr leicht demonstrieren, wie "klassische Suche" sich gegenüber einer binären Suche verhält.

Sherlock

[Luckie]

Muss es denn was aus dem Bereich Programmierung sein? Algorithmen kommen ja fast überall vor. Zum Beispiel Wechselgeld beim Coca Cola Automaten. Ein Kochrezept wäre auch ein Algorithmus. Denn ein Algorithmus ist ja eigentliche nur eine Vorschrift (von Einzelschritten), wie etwas zu tun ist, um zum gewünschten Ergebnis zu kommen. Guck doch mal in der Wikipedia unter dem Stichwort "Algorithmus".

[ngott2]

A + B = C wäre doch per Definition auch ein Algorithmus oder nicht? Das schöne ist da gibt es nichts was man nicht verstehen kann.

[Gausi]

Ich finde das Thema "Sortieren" eigentlich ganz gut dafür. Das ist nicht trivial, aber richtig aufgezogen auch interessant - zur Anschauung kann man ja ein Kartenspiel mitnehmen.

Ich würde allerdings nicht Bubblesort und/oder Quicksort nehmen. Als Beispiel zum Einstieg für einen nicht besonders effizienten Sortieralgorithmus würde ich mit "Sortieren durch Auswahl" anfangen. Also "Suche das kleinste Element, und packe es nach vorne. Dann im Rest das kleinste, und packe es an die zweite Stelle." usw.

Als Spaß-Einstieg ggf. noch Bogosort vorweg: "Mische und schaue nach, ob die Reihenfolge stimmt. Wenn nicht, probiere es nochmal."

Und dann würde ich eine Mergesort-Variante nehmen. Die ist auch in O(n*log(n)), und zwar auch im Worst-Case (das ist bei Quicksort nämlich nicht so!).
Der funktioniert so, dass ich schaue, welche Teilfolgen bereits passend sortiert sind. Je zwei aufeinanderfolgende sortierte Teilfolgen werden dann zu einer sortierten Teilfolge "gemischt", in dem jeweils die kleinere Zahl in die neue Folge eingefügt wird. (Kleiner Nachteil dabei: Benötigt mehr Platz).

Suchverfahren gehen natürlich auch. Hier würde ich zusätzlich zur linearen und binären Suche noch die Interpolationssuche hinzunehmen.

Als Bonus könnte man dann noch am Ende die Frage in den Raum werfen, ob es für "jedes Problem" einen "effizienten Algorithmus" gibt, oder ob es zumindest für jedes Problem, bei dem man die richtige Lösung schnell überprüfen kann, einen effizienten Algorithmus zur Findung der Lösung gibt.

Kann man auch als Abstimmung machen Ja/Nein/Weiß-Ich-Nicht. Und die, die sich dann bei "Weiß-Nicht" gemeldet haben, bekommen den Bonuspunkt, denn das weiß noch niemand. Stichpunkt: P-NP-Problem. Aber da ist dann die Definition von "effizient" eine etwas andere (und Bubblesort wäre dann auch in diesem Sinne effizient).

Und falls es doch Quicksort sein soll: Den kann man auch vortanzen.

https://www.youtube.com/watch?v=ywWBy6J5gz8

[EdAdvokat]

wie wäre es denn mit den Fibronacci-Zahlen?

Delphi-Quellcode:

function TForm1.fibonit(n:integer): integer;
var
  x,y,z,i:integer;
begin
  x:=1;
  y:=1;
  i:=0;
  repeat
    i:=i+1;
    z:=x+y;
    y:=x;
    x:=z;
  until i=(n-2);
  result:=z;
end;

mit dem Algorithmus "Neu=Uralt+Alt"
erscheint doch recht einfach und übersichtlich

[jobo]

Als Teeny hatte ich meine ersten Erfahrungen mit "Zahlenraten" gesammelt. Das konnte man aus dem Handbuch eines TI57 abtippen. (ohne Ahnung zu haben) Das war mein erstes Computerspiel.

Der Rechner hat sich eine Zahl ausgedacht zwischen 1 und 1000
Die geratene (eingetippte) Zahl hat er mit +, - oder Blinken beantwortet:
zu groß, zu klein, Treffer

Das gebe ich heute auch Praktikanten als Programmieraufgabe.

Wo ist dabei der Algorithmus?
Auf den kommt man am besten selbst, wenn man die Eingebung hat, dass es bessere Möglichkeiten als "Raten" geben könnte. Der Algorithmus wird also nicht implementiert, sondern intuitiv oder zielgerichtet ersonnen.
Erst wenn man heute "Computergegner" implementieren würde, würde man den Algorithmus schreiben müssen.

An diesem Beispiel ist relativ einfach zu verstehen, was der Unterschied zwischen Raten und Algorithmus ist, im Nebel stochern und zielgerichtetem, effizientem und vorhersehbarem Vorgehen.
Natürlich nur, wenn man auf einen Algorithmus gekommen ist, der ja im Kern in vielen Sortieralgorithmen verwendet wird. Nebenbei ist es auch eine sehr bildliche Nutzung der Strategie Device & Conquer.

Eine Zahl zwischen 1 und 1000 ist sehr schwierig zu raten, aber
Eine Zahl zwischen 1 und 500 ist schon etwas einfacher zu raten...
usw.

[Gausi]

Zitat von jobo:

Nebenbei ist es auch eine sehr bildliche Nutzung der Strategie Device & Conquer.

Die Methode nennt sich Divide & Conquer - Teile und Herrsche.

[jobo]

Richtig!

Ich könnte ja jetzt behaupten, das war die Autokorrektor, aber ich bin wahrscheinlich mit was anderem beschäftigt gewesen.

"Devide and Conquer"
Kannte ich zu TI57 Zeiten noch nicht, gab's aber spät in der Schule. Ich weiß nicht mehr, wo zuerst: Latein oder Informatik

[Andreas13]

Das Horner-Schema zur effizienten Polynomberechnung und die rekursive Berechnung der Fakultät (n!) sind recht verständlich und einfach zu erklären. Wesentlich komplexer ist das KMP-Muster-Suchverfahren (Knuth, Morris und Pratt).

Gruß, Andreas

[p80286]

"Divide et impera"

Ich stelle mich zu den "Binäre-Suche-Leuten". Das einzig dumme daran ist, daß die Daten sortiert sein müssen. Bei Spielkarten mußman sich vorher noch über die Wertigkeit der Bilder und des Asses einigen. MMn ein schönes Beispiel für einen mfassenden Algo.

Gruß
K-H