Disclaimer: Dieser Thread wurde aus dem alten Forum importiert. Daher werden eventuell nicht alle Formatierungen richtig angezeigt. Der ursprüngliche Thread beginnt im zweiten Post dieses Threads.
Terminierungsfunktion
Da scheinbar einige beim Aufstellen der Terminierungsfunktion Probleme haben (inklusive ich),
hab ich mal den Thread hier eröffnet.
Vielleicht erklärt sich einer der Wissenden bereit um uns Anfängern das ganze Vorgehen zu erläutern.
Ich und auch viele andere wären euch sehr dankbar!
Grüße!
Ich probiers mal.
Ihr braucht eine Funktion t(n), die:
- von der Eingabegroesse abhaengt, mit der die rekursive Funktion aufgerufen wird
- ganzzahlige Werte liefert
- bei jedem Rekursionsaufruf streng monoton faellt
- nach unten beschraenkt ist
- nach Moeglichkeit nicht zu kompliziert aussieht
zu 1. unsere rekursive Funktion ist cn(long n), die offensichtlich long n als Argument hat, also ist unser n, welches t(n) erhaelt eben dieses long n.
zu 2. da unsere Eingabegroesse n ganzzahlig ist, erreicht man die ganzzahligen Funktionswerte von t(n), indem man Brueche, Sinusfunktionen und aehnliches vermeidet
zu 3. da wir das Monotonieverhalten von n kennen (waechst oder schrumpft n bei jedem Rekursionsaufruf?), koennen wir damit eine Funktion t(n) erstellen, die immer schoen faellt
zu 4. Unser n kann nur bestimmte Werte annehmen (warum?). Deshalb kann unser t(n) auch nicht beliebige Werte annehmen und es gibt vor allem einen kleinsten moeglichen, wenn wir t richtig konstruieren.
zu 5. Probiert mal die einfachsten Funktionen aus, die euch so einfallen. Man koennte z.B. mit der konstanten Funktion t(n)=1 anfangen, merkt dann aber schnell, dass sie 3. nicht erfuellt. War also wohl etwas zu einfach.
Okay, danke.
Also n wird ja sowieso bei jedem rekursionsaufruf kleiner. Dann würde es doch reichen, wenn man eine funktion nimmt bei der auf der andren seite das n auch steht und somit bei kleinerem n auch ein kleineres t(n) ensteht, oder nich?
Also was ich nicht ganz verstehe… gibt es nur EINE richtige Funktion für diese Aufgabe oder wäre jede monoton fallende Funktion ohne Brüche, Sinus etc. geeignet? Und muss diese Funktion unseren Rekursionsschritt wiederspiegeln?
(Aus irgendeinem Grund ist meine t-Funktion aber monoton steigend… aber es erschien mir gerade noch logisch…)
EDIT: Wenn ich mir das Vorlesungsbeispiel nocheinmal anschaue… dann steht da ???(???)=??? sei streng monoton fallend - weil die Rekursionsschritte nach unten gehen, und nicht weil die Funktion per Definition fallend sei.
Dieser Beitrag wird in Kürze dem Plagiatschecktool bereitgestellt. Bitte warten…
welcher Beitrag?
Er hat ja eigentlich nur das selbe wiedergegeben, was auf der Vorlesungsfolie stand.
Und die Lösung der Aufgabe hat sich mir gerade als so einfach herausgestellt, dass das lesen dieses Threads eher viel mehr verwirrt hat…
ja eigentlich schon.
Find es bescheuert, wenn es nun schon “strafbar” ist, wenn Jemand es anderen erklärt, sodass auch nicht ganz so matheversierte das ganze begreifen können.
Ist es die Kunst es sich zu bemühen, es zu verstehen, und es anwenden zu lernen oder ist es doch scheinbar die Kunst heimlich an Informationen zu kommen und aus rätseln zu lesen, damit es ja viele nicht verstehen können?
Die Vorlesung erklärt das Vorgehen „generisch“ und an einfachen Beispielen, so dass man mit etwas Transferleistung die Aufgabe selbständig meistern können sollte. Was MalteM hier gemacht hat, kommt der Veröffentlichung eines Lösungsvorschlags zu dieser konkreten Aufgabe nahe. Schreiben hinreichend viele (also >= 2) diesen Beitrag ab, schlägt der automagische Plagiatscheck an - und dazu braucht es nicht mal http://de.guttenplag.wikia.com/wiki/GuttenPlag_Wiki…
Ja, es ist tatsächlich die Kunst [quote]sich zu bemühen, es zu verstehen, und es anwenden zu lernen[/quote] - und das schafft man sicher nicht, indem man aus diesem Forum c&p betreibt…
Wenn ihr meint, dass das zu offensichtlich war, dann loescht doch bitte den Beitrag, statt irgendwelche Plagiatjaeger loszulassen… Ich hab mich bemueht, die Loesung nicht zu offensichtlich werden zu lassen und trotzdem die Fragen des parallel laufenden Threads gleich mitzubeantworten bzw. die dort schon gegebenen Antworten in einem Beitrag (einigermassen) uebersichtlich zusammenzufassen.
Aber ich kann mich natuerlich trotzdem bemuehen, in Zukunft nicht so konkrete Antworten zu liefern.
Also auch von mir die Warnung: nicht abschreiben! Mir kanns, was die Punkte angeht, eigentlich egal sein, aber darum gehts ja nicht. Und ich habe auch nicht vor, Loesungen zu posten, nur weil mir punktemaessig (momentan noch) nicht viel passieren kann.
Also mal ganz ehrlich - ich glaube nicht dass das Plagiatserkennungstool aus Nichtfließtext in pdfs wenn man sie stichpunktartig umformuliert Ähnlichkeiten herauslesen kann - käme auf einen Versuch an 
(Riskiert man damit irgendwas außer Null Punkten?)
PS:http://www.heise.de/ix/meldung/Plagiaterkennungssysteme-auf-dem-Pruefstand-1250787.html
[quote=bulsa]
Also mal ganz ehrlich - ich glaube nicht dass das Plagiatserkennungstool aus Nichtfließtext in pdfs wenn man sie stichpunktartig umformuliert Ähnlichkeiten herauslesen kann - käme auf einen Versuch an
(Riskiert man damit irgendwas außer Null Punkten?)
PS:http://www.heise.de/ix/meldung/Plagiaterkennungssysteme-auf-dem-Pruefstand-1250787.html
[/quote]Ich glaubs auch nicht, aber ich will mir natuerlich nicht nachher das Gegenteil anhoeren von Leuten, die erwischt wurden (auch wenns dann deren Problem ist).
So ein elendiges Plagiatsgetrolle die ganze Zeit.
Also die Beschreibung “Terminierungsfunktion finden” finde ich auch etwas knapp, vor allem da alle Beispiele gleich sind (t(x) = x). Hat jemand zufällig ein halbwegs einfaches Beispiel für eine Funktion, deren Terminierungsfunktion nicht x ist?
Vielleicht, wenn dein n nicht 1 kleiner wird bei jedem Aufruf, sondern halbiert wird, z.B. bei mergeSort. Dann koennte meiner Meinung nach t(n)=floor(lb(n)) sein.
Und bei kaskadenartiger Rekursion zählen dann nur die einzelnen “Stränge”, die kaskadierung selbst wirkt sich eigentlich garnicht aus? (Vgl. Hanoi Folie 4-56)
Stellt sich nur noch die Frage, was bei einer linearen Rekursion passiert, bei der in zwei verschiedenen if-Zweigen der rekursive Aufruf verschiedene "n"s als Rekursionsparameter hat (n-1 und n-2), wenn es sowas geben kann. Andererseits kann man da vielleicht auch einfach hoffen, dass sowas erst in den späteren Vorlesungen zur theoretischen Informatik drankommt :D.