Effiziente Algorithmen

[DieDolly]

Als erstes möchte ich mich für den Titel entschuldigen.

Ein Bekannter von mir soll eine Präsentation über einen IT-Studiengang halten. Behandelt werden ganz grob die Themen, die da in all den Semestern abgearbeitet werden.
Er hat sich zusätzlich, da der Beitrag sonst zu kurz ist, das Thema "Effiziente Algorithmen" rausgesucht.
Er soll oder möchte hier ein Beispiel für einen effizienten Algorithmus aufzeigen und auch erklären.

Er ist kein Programmierer und hat auch sonst nix damit zu tun!

Welchen Algorithmus würdet ihr jemanden, der absolut nix mit Programmierung zu tun hat, zur Präsentation vorschlagen?
Ich selber habe BubbleSort vorgeschlagen. Aber der ist nicht effizient.

[freimatz]

Dann halt Quicksort

Noch etwas einfacher wäre die binäre Suche (statt linearer), das sollte dann auch jeder Zuhörer verstehen. (Dass man eine Telefonbuch nicht von vorne bis hinten durchsucht.)

[DieDolly]

Es handelt sich hier um eine Person, sich sich absolut Null mit Programmierung und sonst irgendwelchen Sachen die damit zu tun hat auskennt.
Die Person besucht kein Studium oder so. Eher sowas wie "10. Klasse".

Wer mit BubbleSort schon Probleme hat, wird QuickSort niemals verstehen.

[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.