AGB  ·  Datenschutz  ·  Impressum  







Anmelden
Nützliche Links
Registrieren

Effiziente Algorithmen

Ein Thema von DieDolly · begonnen am 3. Dez 2019 · letzter Beitrag vom 4. Dez 2019
Antwort Antwort
Seite 1 von 2  1 2   
DieDolly

Registriert seit: 22. Jun 2018
2.173 Beiträge
 
#1

Effiziente Algorithmen

  Alt 3. Dez 2019, 13:54
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.
  Mit Zitat antworten Zitat
freimatz

Registriert seit: 20. Mai 2010
1.377 Beiträge
 
Delphi 11 Alexandria
 
#2

AW: Effiziente Algorithmen

  Alt 3. Dez 2019, 13:56
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.)
  Mit Zitat antworten Zitat
DieDolly

Registriert seit: 22. Jun 2018
2.173 Beiträge
 
#3

AW: Effiziente Algorithmen

  Alt 3. Dez 2019, 13:57
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.
  Mit Zitat antworten Zitat
Benutzerbild von Sherlock
Sherlock

Registriert seit: 10. Jan 2006
Ort: Offenbach
3.753 Beiträge
 
Delphi 11 Alexandria
 
#4

AW: Effiziente Algorithmen

  Alt 3. Dez 2019, 14:01
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
Oliver
Geändert von Sherlock (Morgen um 16:78 Uhr) Grund: Weil ich es kann
  Mit Zitat antworten Zitat
Benutzerbild von Luckie
Luckie

Registriert seit: 29. Mai 2002
37.621 Beiträge
 
Delphi 2006 Professional
 
#5

AW: Effiziente Algorithmen

  Alt 3. Dez 2019, 15:15
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".
Michael
Ein Teil meines Codes würde euch verunsichern.

Geändert von Luckie ( 3. Dez 2019 um 15:37 Uhr)
  Mit Zitat antworten Zitat
ngott2

Registriert seit: 26. Aug 2013
81 Beiträge
 
Delphi 10 Seattle Professional
 
#6

AW: Effiziente Algorithmen

  Alt 3. Dez 2019, 15:33
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.
  Mit Zitat antworten Zitat
Benutzerbild von Gausi
Gausi

Registriert seit: 17. Jul 2005
845 Beiträge
 
Delphi 11 Alexandria
 
#7

AW: Effiziente Algorithmen

  Alt 3. Dez 2019, 15:42
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
The angels have the phone box.

Geändert von Gausi ( 3. Dez 2019 um 15:48 Uhr)
  Mit Zitat antworten Zitat
EdAdvokat

Registriert seit: 1. Mai 2016
Ort: Berlin
414 Beiträge
 
Delphi 10.2 Tokyo Professional
 
#8

AW: Effiziente Algorithmen

  Alt 3. Dez 2019, 16:17
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
Norbert
  Mit Zitat antworten Zitat
jobo

Registriert seit: 29. Nov 2010
3.072 Beiträge
 
Delphi 2010 Enterprise
 
#9

AW: Effiziente Algorithmen

  Alt 3. Dez 2019, 16:17
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.
Gruß, Jo
  Mit Zitat antworten Zitat
Benutzerbild von Gausi
Gausi

Registriert seit: 17. Jul 2005
845 Beiträge
 
Delphi 11 Alexandria
 
#10

AW: Effiziente Algorithmen

  Alt 3. Dez 2019, 16:45
Nebenbei ist es auch eine sehr bildliche Nutzung der Strategie Device & Conquer.
Die Methode nennt sich Divide & Conquer - Teile und Herrsche.
The angels have the phone box.
  Mit Zitat antworten Zitat
Antwort Antwort
Seite 1 von 2  1 2   

Themen-Optionen Thema durchsuchen
Thema durchsuchen:

Erweiterte Suche
Ansicht

Forumregeln

Es ist dir nicht erlaubt, neue Themen zu verfassen.
Es ist dir nicht erlaubt, auf Beiträge zu antworten.
Es ist dir nicht erlaubt, Anhänge hochzuladen.
Es ist dir nicht erlaubt, deine Beiträge zu bearbeiten.

BB-Code ist an.
Smileys sind an.
[IMG] Code ist an.
HTML-Code ist aus.
Trackbacks are an
Pingbacks are an
Refbacks are aus

Gehe zu:

Impressum · AGB · Datenschutz · Nach oben
Alle Zeitangaben in WEZ +1. Es ist jetzt 16:06 Uhr.
Powered by vBulletin® Copyright ©2000 - 2024, Jelsoft Enterprises Ltd.
LinkBacks Enabled by vBSEO © 2011, Crawlability, Inc.
Delphi-PRAXiS (c) 2002 - 2023 by Daniel R. Wolf, 2024 by Thomas Breitkreuz