Entwickler-Ecke
Off Topic - Facharbeit - Rekursive Algorithmik
F34r0fTh3D4rk - Mo 13.03.06 15:10
Titel: Facharbeit - Rekursive Algorithmik
Hallo, ich habe vor eine Facharbeit über Rekursive Algorithmik zu schreiben.
Habt ihr Ideen was man da so einbauen könnte, eventuell Problemstellungen etc ?
Klar ist Einleitung, dann Arten (Backtracing etc), Beispiele, Beispielprogramme (Hanoi oder so), aber was noch ?
Vielen Dank schonmal ;)
DaRkFiRe - Mo 13.03.06 15:30
Na wirst sicherlich auf die Abbruchbedingung zu sprechen kommen müssen. Ohne AbbB keine Terminiertheit der Rekursion -> Stackoverflow, wirste ja wissen.
F34r0fTh3D4rk - Mo 13.03.06 15:37
jo das ist klar, aber dann bräuchte ich nochmehr vorteile nachteile etc, vereinfachung usw ist klar, aber ich muss immerhin 12 seiten text vollkriegen :P
jasocul - Mo 13.03.06 15:45
Du kannst ja mal ganz anders rangehen. Ist das menschliche Gehirn überhaupt geeignet rekursive Programmierung nachzuvollziehen?
Ich erinnere mich an eine Anwendung mit einem 4-fachen Gruppenwechsel, den ich rekursiv programmiert habe. Trotz Kommentierung war das später ungeheuer schwierig nachzuvollziehen. War aber auch nicht erforderlich, da es einwandfrei lief.
Tastaro - Mo 13.03.06 15:55
@jasocul: Das kenn ich. Ich geh an Rekursionen immer so heran:
Schreiben, freuen dass es läuft und bloß nicht versuchen zu überlegen, was der Computer da alles tut. :)
Beste Grüße
Tastaro
DaRkFiRe - Mo 13.03.06 15:58
Na der Vorteil von Rekursion ist: sie sind ja obligatorisch, wenn die Anzahl der Durchläufe von vornherein nicht bekannt ist. Beispiel: Scannen einer Ordnerstruktur (unter FAT).
Ich weiß, dass man alle iterativen Algorithmen auch rekursiv lösen kann, aber nicht jeder rekursive Algo ist iterativ lösbar.
Nachteil: Speicherverbrauch (Stack + u.U. globale Variablen); Möglichkeit, dass Algo nicht terminiert (AbbB). Gibt sicher noch mehr - soll ja auch nur als Denkanstoß gelten.
Guck erstma, wieviel Seiten Du mit eigenem Wissen vollkriegst und dann schick mal PDF.
Facharbeit muss doch mit Deckblatt und Inhaltsverzeichnis sein, oder!? Haste schonmal 2 Blätter weg (4 Seiten!?).
Udontknow - Mo 13.03.06 16:25
| Zitat: |
| Ich weiß, dass man alle iterativen Algorithmen auch rekursiv lösen kann, aber nicht jeder rekursive Algo ist iterativ lösbar. |
Öhm, eine Rekursion wird ja vom Prozessor im Endeffekt immer unter Zuhilfenahme von Speicher (Aufruf-Stack) iterativ umgesetzt. Wird da nicht eher umgekehrt ein Schuh draus?
| Zitat: |
| Nachteil: Speicherverbrauch (Stack + u.U. globale Variablen); Möglichkeit, dass Algo nicht terminiert (AbbB). Gibt sicher noch mehr - soll ja auch nur als Denkanstoß gelten. |
Eine Rekursion ohne Abbruch-Bedingung terminiert eher als eine Endlos-Schleife... :wink:
Cu,
Udontknow
alzaimar - Mo 13.03.06 16:34
 DaRkFiRe hat folgendes geschrieben: |
Ich weiß, dass man alle iterativen Algorithmen auch rekursiv lösen kann, aber nicht jeder rekursive Algo ist iterativ lösbar. |
Falsch! ALLE rekursiven Algorithmen sind iterativ lösbar! Ich frage mich, wieso dieser Schmarrn immer wieder verbreitet wird :gruebel: .
Ich würde (wegen der Würze) die Türme von Hanoi und/oder das 8-Dame Problem als exemplarisches Beispiel für rekursive Lösungswege bzw. Backtracking verwenden. Eine Andere Möglichkeit ist 'FloodFill': Ausfüllen eines geschlossenen Bereiches einer Bitmap mit einer bestimmten Farbe, wobei der Rand durch eine andere Farbe definiert ist:
Quelltext
1:
2:
3:
4:
5:
6:
7:
| FloodFill (X,Y):
Wenn X,Y innerhalb der Bitmap und Bitmap (X,Y)=Leer Dann
Bitmap (X,Y) = Zielfarbe
FloodFill (X-1,Y)
FloodFill (X+1,Y)
FloodFill (X,Y-1)
FloodFill (X,Y+1) |
Und eigentlich ist Rekursivität ganz einfach und entspricht auch unserer Denkstruktur: Ein Problem wird auf einen einzigen Schritt reduziert, nämlich den, der die Lösung ein bisschen näher bringt. Eigentlich ganz einfach. Das ist zwar eine Kunst (weil es so simpel ist), und verlangt ein wenig Übung, aber widernatürlich ist das nicht (finde ich, aber vielleicht bin ich ja auch pervers :mrgreen: )
Quelltext
1:
2:
3:
4:
5:
6:
| LaufeVon (A ,B):
Wenn A<>B dann
Neuer Punkt X = Gehe von A einen Schritt in Richtung B
LaufeVon (X,B)
Sonst
Ausgabe"Angekommen" |
Oder, noch blöder:
Quelltext
1:
2:
3:
4:
5:
| Addiere (A,B,C): // C = A + B, B>0
Wenn B>0 Dann
Addiere (A + 1,B - 1,C)
Sonst
C = A |
Wir haben immer ein Abbruchkriterium, einen kleinen Teilschritt und den rekursiven Aufruf.
Beim *Backtracking* (Try and Error, Versuch und Irrtum) verhält sich das ähnlich, nur das ich den Schritt wieder rückgängig machen muss. Damit eignet sich das Backtracking nicht für 'Trapdoors', also für Operationen, die nur in eine Richtung funktionieren.
Rekursivität ist natürlich insbesondere bei rekursiven Datenstrukturen (Bäumen, Graphen allgemein etc.) sinnvoll.
alzaimar - Mo 13.03.06 16:38
| Udontknow hat folgendes geschrieben: |
| Öhm, eine Rekursion wird ja vom Prozessor im Endeffekt immer unter Zuhilfenahme von Speicher (Aufruf-Stack) iterativ umgesetzt. |
Na logisch. Das reicht, um den zu beweisen, das jeder rekursive algo in einen iterativen (eventuell 1000x komplizierteren) Algo zu transformieren.
Es ist aber viel interessanter, einen rekursiv formulierten Algorithmus in einen (auch von der Komplexität=Zeilenanzahl) äquivalenten iterativen Algorithmus zu verwandeln. DAS ist kniffelig und nicht immer ohne weiteres lösbar. Paradebeispiel: Ackermann. Da ist die rekursive Definition irgendwie 3 Zeilen lang, die iterative aber so um die 50...
F34r0fTh3D4rk - Mo 13.03.06 17:03
wow vielen dank schonmal, da sind einige gute sachen dabei, die mich gleich inspiriert haben.
vor allem das mit der gehirnleistung, ich weiß es selbst, ich wollte die türme von hanoi coden, iterativ, das waren ne menge zeilen code, dann finde ich den rekursiven algo und das war ein zwei zeiler, es hat mich schon einige zeit gekostet den zu verstehen, weil er simpel ist, aber alles regeln der türme befolgt, schlichtweg genialste algorithmik.
gibts auch typische beispiele für indirekte rekursion ?
alzaimar - Mo 13.03.06 19:10
| F34r0fTh3D4rk hat folgendes geschrieben: |
| gibts auch typische beispiele für indirekte rekursion ? |
Wasndat?
DaRkFiRe - Mo 13.03.06 19:25
Wusste gar nicht, dass eine Endlosschleife terminiert. Begründe das bitte.
Dass man eine Rekursion auch iterativ lösen kann, sind selbst lt. wikipedia (okay, muss ja nicht stimmen) nur Spezialfälle.
Natürlich geht das mit dem Stack, indem man den PC "nachempfindet". Rekursion sind ja im PC wie schon gesagt: Iterationen mit einem Stack.
Udontknow - Mo 13.03.06 19:43
| Zitat: |
| Wusste gar nicht, dass eine Endlosschleife terminiert. Begründe das bitte. |
Tut sie eben nicht! :lol:
Da eine Rekursion irgendwann mit einer EStackoverflow-Meldung abgebrochen wird, beendet diese sich "eher"... Ja, ich weiss, die Pointe ist mau. :wink:
Was die Wikipedia angeht:
| Zitat: |
| Manche Programmiersprachen (insbesondere in der Funktionalen Programmierung) erlauben keine Iteration, sodass immer die rekursive Umsetzung gewählt werden muss. |
Das ändert nichts daran, daß dem PC als Rechenmaschine gar nichts anderes übrig bleibt, als iterativ vorzugehen.
Cu,
Udontknow
Delete - Di 14.03.06 01:38
DaRkFiRe, jede rekursion kann man auch iterativ auflösen, aber nicht jede iteration auch rekursiv.... das sind grundverschiedene ansätze....
PS: F34r0fTh3D4rk: wenn du was über rekursion lesen willst, so empfehle ich dir die klassiker der algo. theorie... da findest du spielend ein paar 1000 seiten... die du lesen kannst.. und für deine facharbeit werden dann auch noch 10 bis 20 seiten übrig bleiben.. also ruhig mal zur biblio gehen,...
DaRkFiRe - Di 14.03.06 02:28
Jau, dann hab ich das vertauscht - und das mit der Endlosschleife hab ich dann wohl nur überflogen. Ich schieb das jetzt mal auf meinen nicht durchgängigen 4-stündigen Schlaf letzte Nacht.
alzaimar - Di 14.03.06 09:15
| Grenzgaenger hat folgendes geschrieben: |
| DaRkFiRe, jede rekursion kann man auch iterativ auflösen, aber nicht jede iteration auch rekursiv.... das sind grundverschiedene ansätze.... |
Wieso könnte es einen iterativen Algorithmus geben, die man nicht rekursiv lösen kann? Das kann nicht sein, weil die 'Tail recursion' eine äquivalente Umsetzung einer Aufzählung ('Iteration') ist.
digi_c - Di 14.03.06 10:24
Vielleicht magst du darauf eingehen, wie man mit rekursiven Funktionen sehr schön komplexe Grafiken machen kann.
Sowas wird z.B. bei Demos genutzt um die Programme klein zu halten.
http://www.educeth.ch/informatik/leitprog/rekursion/
F34r0fTh3D4rk - Di 14.03.06 15:11
ich brauche noch einen guten syntax highlighter für word 2000, gibts irgendwo sowas ?
digi_c - Di 14.03.06 15:25
Bei den Gexperts ist einer mit drin, der unterstützt HTML,RTF,Zwischenablage
F34r0fTh3D4rk - Di 14.03.06 15:35
gibts auch einen seperaten highlighter ?
alzaimar - Di 14.03.06 15:53
| F34r0fTh3D4rk hat folgendes geschrieben: |
| ich brauche noch einen guten syntax highlighter für word 2000, gibts irgendwo sowas ? |
Sag mir jetzt nicht, das du deine Facharbeit mit Word schreibst. Hmmpff. Wer zuviel Zeit hat, nimmt Word. Alle anderen nehmen LaTex mit den entsprechenden Styles. Word 2000 ist zwar schon einigermaßen stabil, aber trotzdem ist es irgendwie in diesem "§$"§$-Textprogramm eingebaut, das insbesondere Diplom- Fach- und Doktorarbeiten am Abend (wie schafft Microsoft das nur?) VOR der Abgabe mit an Sicherheit grenzender Wahrscheindlichkeit nach guter alter Landsmannart ordendlich zerballert werden. Vielleicht hast Du Glück, vielleicht auch nicht.
Aber zu Deiner Frage: Ich weiss nicht, ob das Teil bei JVCL in RTF exportieren kann. Ich brauchte soetwas neulich und hab mir die SynEdit-Komponenten von Sourceforge installiert. Da ist so ein RTF-Exporter drin. Damit hab ich die Sourcen exportiert und dann in Word importiert...
Oh, geouted.
:bawling: Ich verwende WORD und schäme mich :bawling:
F34r0fTh3D4rk - Di 14.03.06 16:54
ja word ist schon ziemlich schlimm, ein falscher klick lässt sich meist net durch undo rückgänig machen, aber unser lehrer zwingt uns ja fast dazu ^^
alzaimar - Di 14.03.06 16:58
[quote="[user]...aber unser lehrer zwingt uns ja fast dazu ^^[/quote]
Wieso leben wir eigentlich in einem Rechtsstaat, wo Gewalt allein vom Staate ausgeht? Manchmal wünscht man sich doch den Wilden Westen herbei, bei dem das Gesetz des Stärkeren herrscht und man solche Dumpfbacken ordendlich vermöbeln konnte, ohne gleich eins aufs Dach zu bekommen.
Fortschritt hat auch seine Schattenseiten :roll:
F34r0fTh3D4rk - Di 14.03.06 17:07
weil wir das letzte halbe jahr damit verbracht haben formatieren mit word zu lernen, trotzdem bekomme ichs immernoch net hin, allein um ein jpg als deckblatt zu benutzen habe ich ne stunde und gute nerven gebraucht, ich lad das teil was du gesagt hast grad mal, denn viel zeit hab ich nicht :lol:
Delete - Mi 15.03.06 00:33
| alzaimar hat folgendes geschrieben: |
| Grenzgaenger hat folgendes geschrieben: | | DaRkFiRe, jede rekursion kann man auch iterativ auflösen, aber nicht jede iteration auch rekursiv.... das sind grundverschiedene ansätze.... |
Wieso könnte es einen iterativen Algorithmus geben, die man nicht rekursiv lösen kann? Das kann nicht sein, weil die 'Tail recursion' eine äquivalente Umsetzung einer Aufzählung ('Iteration') ist. |
darauf will ich gar nicht erst eingehen. fact ist, dass jeder rekursive algo auch iterativ zu lösen ist. sollt dies nicht so sein, so überlass ich gern
F34r0fTh3D4rk den beweis im rahmen seiner facharbeit. ich hoffe, er wird uns diesem nicht verheimlichen.
F34r0fTh3D4rk - Mi 15.03.06 16:35
ja ein problem besteht bei der Dateiensuche, wenn die Anzahl der Dateien nicht gegeben ist. Rekursiv kein ding, aber mit einer for schleife zB schlecht machbar, eine repeat schleife ginge mit der abbruchbedingung, dass die jetzige datei die gesucht ist, dabei ist eine repeat schleife in sich rekursiv, das gleiche bei asm, man kann mit asm keine einfache for schleife reakisieren, das muss man auch mit primitiver Rekursion lösen.
Aber letztenendes ist das Definitionssache, ob eine repeat schleife rekursiv ist. es ist auf jedenfall keine rekursiver algorithmus, obwohl man jede repeat schleife genauso einfach in einen solchen packen kann.
was meint ihr ? wie genau sind rekursion und iteration zu unterscheiden ?
wie genau wird rekursion und iteration definiert ?
Gausi - Mi 15.03.06 16:47
| F34r0fTh3D4rk hat folgendes geschrieben: |
was meint ihr ? wie genau sind rekursion und iteration zu unterscheiden ?
wie genau wird rekursion und iteration definiert ? |
Man hat eine Rekursion, wenn man etwas mit einer Funktion/Prozedur berechnet/macht, und in dieser Funktion die Funktion selbst benutzt.
Beispiel Türme von Hanoi: Algorithmus: Verschiebe den Turm, der aus allen Scheiben bis auf die unterste besteht, mit diesem hier beschriebenen Verfahren auf die mittlere Position. Anschließend verschiebe die unterste Scheibe auf die rechte Position. Zuletzt verschiebe den mittleren Stapel mit diesem Verfahren auf die rechte Scheibe.
Wenn du die Funktion selbst in deiner Funktion nicht benötigst, hast du keine Rekursion - das Verfahren ist dann iterativ.
alzaimar - Mi 15.03.06 18:31
Rekursion ist 'Selbstbeinhaltung'. Das gibt es auch in der Natur. Fraktale sind selbstbeinhaltend, also auch rekursiv. Schau Dir mal die Kerne einer Sonnenblumenblüte an. Du erkennst ein Muster, das rekursiv ist. Romanesco-Blumenkohl ist eine rekursive Struktur. etc. Bäume mit ihren Verästelungen auch. Am Baum sind Zweige. Am Zweig sind Zweige sind Zweige...
Wirklich lustig.
Rekursivität ist dann also nichts Anderes, als das ein Ding u.a. durch sich selbst erklärt/definiert wird.
"Eine Wendeltreppe, ist eine Treppe, die wendelartig ...." <- Rekursion.
Schau in einen Spiegel. Stell hinter Dir einen Spiegel auf. <- Rekursion.
In der Algorithmik wäre das analog:
Ein rekursiver Algorithmus (=Lösungsstrategie) verwendet sich selbst zur Lösung des Problems.
Wie ich bereits erwähnte, kann ich von A nach B laufen, indem ich von A einen Schritt in Richtung B laufe und dann von dieser neuen Position die Lösungsstrategie 'von A nach B laufen' wieder anwende.
Für formal korrekte Definitionen bin ich aber nicht zuständig.
F34r0fTh3D4rk - Mi 15.03.06 18:58
Die hübschen Tags kann ich in word ja leider nicht nutzen ^^
alzaimar - Mi 15.03.06 19:03
Antwort: Ist verständlich.
Frage: Mit SynEdit nicht klargekommen? Nimm dies..
F34r0fTh3D4rk - Mi 15.03.06 19:06
danke ^^
DaRkFiRe - Mi 15.03.06 21:49
Man kann einen rekursiven Algorithmus auch iterativ darstellen, wenn man sich die Datenstruktur eines Stacks bedient um so (rekursive) Funktionsaufrufe, wie sie im Computer passieren, nachzuempfinden.
Entwickler-Ecke.de based on phpBB
Copyright 2002 - 2011 by Tino Teuber, Copyright 2011 - 2025 by Christian Stelzmann Alle Rechte vorbehalten.
Alle Beiträge stammen von dritten Personen und dürfen geltendes Recht nicht verletzen.
Entwickler-Ecke und die zugehörigen Webseiten distanzieren sich ausdrücklich von Fremdinhalten jeglicher Art!