Effiziente Programmierung

Hallo, ich studiere an einer Berufsakademie Informationstechnik…
ein Professor hat uns eine Aufgabe gestellt, es ging sao ungefähr darum eine Rechnung auszuführen ohne Multiplikation, also das Ding durch Additionen oder was zu ersetzen.

Jetzt lag für mich nahe die Multiplikation durch eine Schleife nachzubilden, aber der Prof. hat dann eine total geniale Lösung gebastelt, in dem er das ganze etwas mathematisch umgeformelt hat und am Ende stand so ungefähr dran x = x + y + y - 1 oder sowas und das macht genau das gleiche wie mein Loop.

Mich hat das total fasziniert.
Gibt es irgendwo im Web (er hat von einem Buch gesprochen, will ich aber nicht kaufen / lesen) Dokumente, in denen solche Techniken besprochen werden, wie man Algorithmen effizienter gestalten kann, also schnellere Programme entwickeln.
(z.b. QuickSort, Bubblesort, etc.)

Bruno

Na, ja - die Grundlage für effiziente Algorithmen ist unter anderem ein gerüttelt Maß an mathematischem Wissen und Verständnis. Und ich möchte mal bezweifeln, dass man das „mal so eben“ (und ohne viel zu lesen) erwerben kann.

Nichts für ungut…
Reinhard

Ja ok, weisst du wo man das lesen kann? Gibts Dokumente im Web?
Das mathematische Wissen krieg ich zur Zeit zwangsweise vermittelt :wink:

[Bei dieser Antwort wurde das Vollzitat nachträglich automatisiert entfernt]

Ja ok, weisst du wo man das lesen kann?
Gibts Dokumente im Web?
Das mathematische Wissen krieg ich zur
Zeit zwangsweise vermittelt :wink:

Wenn du das Wissen hast (und dann noch die Lust dazu hast) kannst du dir Bücher über Algorithmen (z.B. den guten alten Knuth oder das Buch von Sedgewick) hereinziehen und dich dann mit ungelösten bzw. bislang noch nicht effizient genug gelösten mathematischen Problemen beschäftigen. (Jeder neue Algorithmus ist ja letztendlich nichts anderes). Wobei es natürlich grosse Unterschiede in der Komplexität je nach Anwendungsgebiet des Algorithmus gibt.

Aber ehrlich gesagt: Als Diplominformatiker mit Vordiplom in Mathematik würde ich mich überfordert fühlen, wenn ich beispielsweise einen ähnlich effizienten Sortieralgorithmus wie Bubblesort erfinden sollte. (Das heisst nicht, dass ich die bestehenden Algorithmen nicht verstehe, aber das Neuerfinden hat halt eine gänzlich andere Qualität). Ich gehe aber auch davon aus, dass dein Prof die von dir erwähnte elegante Lösung nicht selbst gefunden hat!

Der Mathematiker, der vor einiger Zeit die Lösung des Vierfarbenproblems gefunden hat, hat sich jahrelang mit nichts anderem beschäftigt. Und ich kenne jemanden, der mehrere Jahre darauf verbracht hat, eben KEINE Lösung (in diesem Fall eines speziellen Problems der Graphentheorie) zu finden - und auch nicht den Gegenbeweis, das es eine derartige Lösung nicht geben kann (der ja für Mathematiker fast genauso gut wie eine Lösung ist…)

Eine Kurzanleitung zum Thema kann ich mir beim besten Willen nicht vorstellen, aber einen Eindruck, worum es geht, kannst du z.B. hier bekommen: http://www.matheprisma.uni-wuppertal.de/

Reinhard

Gibts jetzt eigentlich…
… Seiten mit effektiven Algorithmen im Netz???

Liebe Grüße
Peter

Aber ehrlich gesagt: Als
Diplominformatiker mit Vordiplom in
Mathematik würde ich mich überfordert
fühlen, wenn ich beispielsweise einen
ähnlich effizienten Sortieralgorithmus
wie Bubblesort erfinden sollte.

Naja, Bubblesort ist wohl einer der schlechtesten Sortieralgorithmen ueberhaupt. Ich denke, Du meinst Quicksort :wink:

Niels

Ich will eigentlich auch nicht hier irgendwie den neuen supertollen Suchalgorithmus oder so erfinden, sondern bekanntes Wissen nutzen, also so ne Art Hilfe „machen sie das auf keinen Fall, das kann man so viel besser lösen“ oder so

[Bei dieser Antwort wurde das Vollzitat nachträglich automatisiert entfernt]

Suchalgorithmus oder so erfinden, sondern
bekanntes Wissen nutzen, also so ne Art
Hilfe „machen sie das auf keinen Fall,
das kann man so viel besser lösen“ oder
so

Da hab ich dich wohl missverstanden…

Nun ja - so ziemlich jeder Informatik-Fachbereich bietet eine Vorlesung „Effiziente Algorithmen“ an - z.B. http://ls2-www.cs.uni-dortmund.de/EA98/
(such mal mit Altavista nach „Effiziente Algorithmen“ oder „Software Engineering“)
Leider ist das im Web dazu angebotene meist bestenfalls als Hintergrundinformation zu gebrauchen.

Ganz gut ist die Übersicht von Broy:
http://www.imn.htwk-leipzig.de/~feustel/br4/b4k4.html

Es gibt aber nun ja so viele Algorithmen wie es Problemstellungen in der Informatik gibt - insofern würde ich das immer vom gegebenen Problem aus angehen, und dann zum Buch greifen (wie gesagt: Knuth [ist zwar bald 30 Jahre alt, aber in vielen Bereichen immer noch aktuell: http://www.amazon.de/exec/obidos/ASIN/0201485419. Es wird übrigens demnächst eine deutsche Neuausgabe geben: http://www.amazon.de/exec/obidos/ASIN/3540667458 oder z.B. Sedgewick [http://www.amazon.de/exec/obidos/ASIN/3893193014]](http://www.amazon.de/exec/obidos/ASIN/3893193014]))

Reinhard

Da siehst du, wie gering ich meine Fähigkeiten zum Algorithmendesign einschätze ;=)

Reinhard