D120.de/forum

Hi, kann mir jemand erklären was die Invariante des Kruskal Algorithmus fordert? (https://hermes.algo.informatik.tu-darmstadt.de/mediawiki/index.php/Kruskal_for_maximum_spanning_forest) Bisher habe ich mir folgendes überlegt, bin mir da aber nicht sicher: 1.) Der Graph F_i = (V,E_i), der aus den bis...

Danke, genau das wollte ich wissen.

Hi, die Iteration ist ja eigentlich ein Prozess, man kann also nur sagen was i vor bzw. nach der Iteration ist. Bezogen auf die Klausuraufgabe (Infoblatt) würde das bedeuten, man soll zeigen das die Invariante für i=6 (nach der Iteration ist i=6) und die Variante beim Übergang von i=5 (vor der Itera...

Hallo, leider verstehe ich nicht ganz was man bei einem rekursiven Algorithmus in der Klausur alles machen müsste. Deshalb poste ich hier einfach mal eine mögliche Aufgabe mit einem Lösungsansatz und hoffe auf Kritik. Aufgabenstellung: Algorithmus Mergesort https://hermes.algo.informatik.tu-darmstad...

Hallo, meiner Meinung nach gilt die von mir gepostete Version nach der achten Iteration, da S[8-4+2] - S[8] = S[6] - S[8] und somit max. 3 Zeichen für ein Präfix möglich sind. Würde man S[8-4+1] - S[8] wählen, währen 4 Zeichen für ein Präfix möglich, was aber bei |T| = 4 keinen Sinn macht. (Präfix h...

Danke für die schnelle Antwort, jetzt habe ich gleich noch eine Frage zum eigentlichen Thema:
Müsste die Begründung, wieso die Invariante für I hier erfüllt ist nicht lauten "da I alle Indexe von S[8-4+2] - S[8] enthält."?

Hallo,
man müsste also bei diesem Algorithmus keine zeichnerische Darstellung in der Klausur machen?

Danke für die schnelle Antwort, ich habe wohl die Definition von Kandidat falsch verstanden.
Um sicher zu gehen: Um mehr als einen Kandidaten pro Schritt zu haben, muss ein Präfix des gesuchten Strings in dem gesuchten
String selbst enthalten sein, richtig?

Hallo, in der Aufgabenstellung steht "ein Beispiel, sodass während der Ausführung in mindestens einem Schritt mindestens zwei Kandidaten gleichzeitig betrachtet werden". Und zusätzlich noch "nach Terminierung mindestens vier Vorkommen gefunden wurden". Ist es jetzt nicht so, dass wenn man in einem S...

Wer hat gesagt, dass wir hier eine rein abstrakte Sichtweise einnehmen? Nur für,die Spezifikation der Scleife war von der abstrakten Sequenz die Rede! :roll: Am Ende jedes Methodenaufrufs muss die Implementationsinvariante wieder erfüllt sein. Dafür ist das Wiki die entscheidende Autorität. :twiste...

Hallo, normalerweise bezieht sich der Induktionsschritt ja darauf, was bei einem Schleifendurchlauf passieren soll. In der Aufgabe läuft die Schleife aber nur einmal durch, sollen wir jetzt im Induktionsschritt beschreiben was bei einem Schritt eines Elements auf das nächste passiert? EDIT: Wir soll...

Das würde ich auch gerne wissen.

@bagwell
Ich vermute mal du hast eine Methode isDigit(), diese Methode sollte aber eine isNumber() sein, da in den Tests z.B. folgendes gemacht wird: list.addElement(new MathElement("42.0"));

VG

Hallo,
nur kurz um sicher zu gehen, wird nächste Woche wirklich nur die theoretische Übung testiert?
Ich glaube gestern war es noch anders.

Eine grundsätzliche Frage zu der Aufgabe 4b, wieso ist hier eigentlich eine physische Speicheradresse in einer Seitentabelle gespeichert?
Eigentlich ist in der Seitentabelle doch nur die physische Seitennummer und das Valid-Bit.