Fehler in Musterlösung von Klausur 2013_04

himbaer
Mausschubser
Mausschubser
Beiträge: 98
Registriert: 28. Apr 2010 19:29
Kontaktdaten:

Fehler in Musterlösung von Klausur 2013_04

Beitrag von himbaer »

Also bei der 8ten Aufgabe in der Klausur soll man ja das größtmögliche M bestimmen.
Ich habe dort 409 raus, was in die Gleichung eingesetzt immernoch kleiner als 8192 ist. Somit kann 49 doch sicher nicht das größte M sein?!
Die Umformung sieht mir auch sehr seltsam aus! :D
meine Testsignatur :!:

Benutzeravatar
JannikV
Nerd
Nerd
Beiträge: 609
Registriert: 24. Apr 2011 12:42

Re: Fehler in Musterlösung von Klausur 2013_04

Beitrag von JannikV »

Ich denke du hast recht. In der vierten Zeile der Musterlösung wird mit 8.192 statt 8.198 weitergerechnet. Und 8192/20 ist auch nicht gleich 40 + 192/20.

VG

himbaer
Mausschubser
Mausschubser
Beiträge: 98
Registriert: 28. Apr 2010 19:29
Kontaktdaten:

Re: Fehler in Musterlösung von Klausur 2013_04

Beitrag von himbaer »

Hätte hier aber nochmal eine Frage zu der Aufgabe 4. Ich verstehe den Beweiß einfach nicht.
Kann mir diesen jemand mal Schritt für SChritt erklären?
Ich verstehe noch, dass b durch e geteilt wird und das n² sich kürzt.
Die anschliessende Ableitung verstehe ich schon nicht mehr und auch der Schritt danach ist mir unverständlich -.-
meine Testsignatur :!:

Benutzeravatar
JannikV
Nerd
Nerd
Beiträge: 609
Registriert: 24. Apr 2011 12:42

Re: Fehler in Musterlösung von Klausur 2013_04

Beitrag von JannikV »

Ok, das Verständnisproblem wird wohl bei der Ableitung liegen.
Laut L'Hôpital ist der Grenzwert des Quotienten von zwei Funktionen (in bestimmten Situationen wie hier) der gleiche wie der Grenzwert des Quotienten der Ableitungen.

Vom zweiten zum dritten Schritt wird also jeweils oben und unten abgeleitet.
Und die Ableitung von log(n) ist eine Konstante geteilt durch n. Und die Ableitung von \(\sqrt{n}\) ist \(\dfrac{1}{2 * \sqrt{n}}\).

himbaer
Mausschubser
Mausschubser
Beiträge: 98
Registriert: 28. Apr 2010 19:29
Kontaktdaten:

Re: Fehler in Musterlösung von Klausur 2013_04

Beitrag von himbaer »

Warum ist
loga(n)' = const/n
Irgendwie steh ich hier auf dem Schlauch. Ich dachte
loga(n)' = 1/(n* ln a)
meine Testsignatur :!:

Benutzeravatar
cofi
Mausschubser
Mausschubser
Beiträge: 86
Registriert: 22. Sep 2009 12:07

Re: Fehler in Musterlösung von Klausur 2013_04

Beitrag von cofi »

Das ist auch richtig.

Mit
\(\ln_a(n)' = \frac{1}{n}\)
und einem Basiswechsel zu e kommt man aber zu
\(\log_a(n)' = const \cdot \frac{1}{n}\)

Malte
Neuling
Neuling
Beiträge: 7
Registriert: 21. Apr 2013 19:19

Re: Fehler in Musterlösung von Klausur 2013_04

Beitrag von Malte »

Ich nutze mal den Thread hier, um eine weitere Frage zur Musterlösung 13_04 zu stellen.

Aufgabe 5:
Ich habe mich recht schwer getan an der Programmieraufgabe und denke, dass die Musterlösung falsch ist!

Wenn wir die Rekursive Hilfsprozedur mit einem Knoten aufrufen, der nur einen linken Nachfolger hat, welcher wiederum zwei Nachfolger hat, aufrufen, gib es keinen Fall, der dies ausgleichen kann.

Es wird rekursiv der linke Teilbaum betrachtet, der allerdings vollständig ist. Der rechte Teil wird nicht mehr betrachtet, da (node.right != null) nicht zutrifft, da er leer ist und damit die Prozedur endet, ohne dass etwas getan wird.


Anders ausgedrückt denke ich liegt der Fehler daran, dass wenn wir die Invariante so formulieren, dass ein Knoten, der mit der Hilfsprozedur aufgerufen wird immer zwei Nachfolger hat. Deshalb greifen wir vom aktuellem Knoten immer auf zwei Ebenen tiefer zu, um dies sicherzustellen und den direkten Nachfolger bei Bedarf zu löschen, wenn der nur einen Nachfolger hat.
Das Problem: Durch das löschen des Nachfolgers, tritt jetzt ein Knoten an dessen Stelle, über dessen Nachfolger wir keine Aussage treffen können und auf den wir trozdem die Hilfsprozedur anwenden.


Ich finde leider keine gute Lösung für die Aufgabenstellung. Was vermutlich funktionieren würde, wäre auf dem aktuellem Knoten zu arbeiten. Abbruchbedingung: Node == Blatt, ansonsten wenn nur eine Nachfolger existiert, den Knoten selber mit dem existierendem Nachfolger zu überschreiben. In diesem Fall müsste man dann aber die Rekursive Prozedur mit dem eigenem Knoten nochmal aufrufen, was ich nicht schön fände und die formulierung einer Variante erschwert.


Übersehe ich irgendwas, oder wie sähe eine Lösung für das Problem aus?
Danke!

himbaer
Mausschubser
Mausschubser
Beiträge: 98
Registriert: 28. Apr 2010 19:29
Kontaktdaten:

Re: Fehler in Musterlösung von Klausur 2013_04

Beitrag von himbaer »

Ich sehe was du meinst. Ich habe es nochmal verdeutlicht und bin es Schritt für SChritt durchgeganen.
Zuerst haben wir folgenden Baum,
baum.png
baum.png (7.12 KiB) 3769 mal betrachtet
In diesem wird nun links der erste Knoten ausgehängt, da er nur einen Nachfolger hat:
baum1.png
baum1.png (7.58 KiB) 3769 mal betrachtet
Und nun wird weiter abgestiegen nach links. Jedoch hat der Knoten auf den Node jetzt zeigt selbst nur ein Nachfolger und das wird sich auch nicht ändern.
baum2.png
baum2.png (7.28 KiB) 3769 mal betrachtet
Ich denke hier ist einfach mal wieder die Musterlösung falsch.
Stellt sich bei mir allerdings die Frage:Wurden nicht sogar diese Klausuren damals anhand dieser Musterlösung bewertet????
meine Testsignatur :!:

himbaer
Mausschubser
Mausschubser
Beiträge: 98
Registriert: 28. Apr 2010 19:29
Kontaktdaten:

Re: Fehler in Musterlösung von Klausur 2013_04

Beitrag von himbaer »

So macht der Code mehr sinn oder?

Code: Alles auswählen

private void reduceToCompletenessRec(BinaryTreeNode node){
		if(node.left!=null){
			if(node.left.left==null&&node.left.right!=null){
				node.left = node.left.right;
				reduceToCompletenessRec(node);
			}
			if(node.left.left!=null&&node.left.right==null){
				node.left=node.left.left;
				reduceToCompletenessRec(node);
			}
			if(node.left.left!=null&&node.left.right!=null)
				reduceToCompletenessRec(node.left);
				
		}
		if(node.right!=null){
			if(node.right.left==null&&node.right.right!=null){
				node.right=node.right.right;
				reduceToCompletenessRec(node);
			}
			if(node.right.left!=null&&node.right.right==null){
				node.right=node.right.left;
				reduceToCompletenessRec(node);
			}
			if(node.right.left!=null&&node.right.right!=null)
				reduceToCompletenessRec(node.right);
		}		
	}
meine Testsignatur :!:

Benutzeravatar
Domac
Endlosschleifenbastler
Endlosschleifenbastler
Beiträge: 160
Registriert: 4. Okt 2010 16:11

Re: Fehler in Musterlösung von Klausur 2013_04

Beitrag von Domac »

Hi.

Kann ich bei Aufgabe 1) davon ausgehen, dass 6 Iteration i=0,…,5 impliziert?
Dabei passiert in der 0.ten Iteration praktisch gar nichts?

Kann ich des Weiteren davon ausgehen, dass Selection Sort genau so laut Wiki zu implementieren wäre?

Grüße

PS.: Außerdem wollte ich anmerken, dass die Aufgabe 2) imho unpräzise formuliert ist. Ist in der Klausur auch mit sowas zu rechnen? Dann muss ich permanent den Tutor zu mir bitte und explizit nachfragen, welche Rekursion jetzt zu behandeln ist… jene in der man sich befindet oder die darauf folgende. Laut MuLö die darauffolgende und laut Aufgabenstellung anscheinend die, in der man sich gerade befindet.
Extend my dropbox space (here).
Thanks!

brjan
Erstie
Erstie
Beiträge: 20
Registriert: 28. Jul 2011 12:21

Re: Fehler in Musterlösung von Klausur 2013_04

Beitrag von brjan »

@himbaer und Aufgabe 5

Deine Korrektur sieht für mich sehr gut aus. Aber das Problem fängt aber schon in der Methode reduceToCompleteness() an.

Z.B. bei folgendem Baum:

Code: Alles auswählen

1
 \
  2
   \
    3
reduceToCompleteness() macht dann

Code: Alles auswählen

  2
   \
    3
draus und übergibt den Knoten mit der 2 an reduceToCompletenessRec().
Diese Methode kann hier aber nichts mehr retten, da sie erst ab der zweiten Ebene reparieren kann.

Der Hinweis zur Aufgabe und die Implementierung von reduceToCompletenessRec() in der Musterlösung scheinen für mich aus dem Denkfehler zu resultieren, dass eine Wurzel, die genau ein Kind hat nur durch dieses Kind ersetzt zu werden bräuchte. Es ist aber nach der Ersetzung keineswegs ausgeschlossen, dass der Fall erneut auftritt.

Ich frage mich, ob diese Aufgabe ohne Schleife überhaupt lösbar ist. Denn so wie du in deinem Code mit einem allgemeinen Knoten verfährst, indem du die Methode mit dem gleichen Knoten einfach so oft erneut aufrufst, bis für diesen Knoten alles in Butter ist, so kann man in reduceToCompleteness() natürlich nicht entsprechend mit der Wurzel verfahren.

So einfach die Java-Aufgabe noch in der Klausur von 2012 war, so verwirrend ist diese hier. :/

xliachbtecmo
Neuling
Neuling
Beiträge: 3
Registriert: 12. Jun 2013 14:32

Re: Fehler in Musterlösung von Klausur 2013_04

Beitrag von xliachbtecmo »

Ja, die Methode lässt sich ohne Schleife lösen.
Invariante: node (der Paramter) hat zwei Kinder.
Man geht zuerst die Fälle durch, dass die Kindknoten, nur einen Nachfolger haben. Dann erst man (potenziell beide oder auch nur einen) durch das eine vorhandene Kind des betreffenden Knoten. Dann ruft man reduceTocompletenessRec erneut mit dem selben Knoten au und macht return.
Haben nun beide Knoten entweder keine oder zwei Kinder, so ruft man für die Knoten mit zwei Kindern die Methode rekursiv auf.
Variante: Es wird (mindestens) ein Knoten, der genau ein Kind hat, entfernt oder zu den Kindern hinabgestiegen.
Break: Ein Kindknoten ist ein Blatt.

Um die Inariante am Anfang sicherzustellen, muss man folgende Fälle abarbeiten:
Wurzel == null => return;
Wurzel.left == null && Wurzel.right == null => return
Wurzel.left == null => Wurzel = Wurzel.right; Rufe reduceToCompleteness erneut auf;return;
Wurzel.right==null => Wurzel = Wurzel.left; Rufe reducoToCompleteness erneut auf; return;
rufe reduceToCompleteness(Wurzel) auf;

Damit werden Ketten von Knoten mit nur einem Kind auch abgebaut und eventuelle folgende Knoten mit zwei Kindern angehangen.

Aus Variante und Invariante kann ich folgern, dass die Methode für alle Knoten, die zwei Kinder haben, (mindestens) einmal aufgerufen wird. Da am Ende nur Knoten übrig bleiben, für die die Methode auch aufgerufen wurde, ist der Binäre Baaum vollständig.
Letzendlich wird der "Trick" mit dem Aufrufen mit dem gleichen Argument in beiden Methoden verwendet.

Hoffe, das funktioniert so :).

PS: Prinzipiell ist alles, das mit Schleifen programmierbar ist, auch mit Rekursion und umgekehrt programmierbar. Wenn man also eine Version mit Schleife hat, gibt es auch eine mit Rekursion.

brjan
Erstie
Erstie
Beiträge: 20
Registriert: 28. Jul 2011 12:21

Re: Fehler in Musterlösung von Klausur 2013_04

Beitrag von brjan »

Du meintest sicher in der letzten Zeile

rufe reduceToCompletenessRec(Wurzel) auf;

Ich hab gestern den Denkfehler gemacht, man könnte ja den ersten Aufruf von reduceToCompletenessRec(Wurzel) nicht unterbinden, was natürlich völliger Blödsinn ist. :|

So sollte es tatsächlich funktionieren.

himbaer
Mausschubser
Mausschubser
Beiträge: 98
Registriert: 28. Apr 2010 19:29
Kontaktdaten:

Re: Fehler in Musterlösung von Klausur 2013_04

Beitrag von himbaer »

Jedoch bleibt die Musterlösung ein absoluter FAIL!!!!! :D
meine Testsignatur :!:

Goma
Erstie
Erstie
Beiträge: 22
Registriert: 22. Apr 2012 13:34

Re: Fehler in Musterlösung von Klausur 2013_04

Beitrag von Goma »

Man kann nur noch von "Muster" sprechen... Lösung würde voraussetzen das da irgendwas drin stimmt, aber selbst die Aufgabenstellung hat gefailed von daher passt die Lösung ja nur dazu... ;D
Und cool wie sich die Verantwortlichen zurück halten.... so viel zum Thema fragen vorher stellen und in der Klausur keine erlaubt...

Antworten

Zurück zu „Archiv“