Die häufigsten Fehler beim 5. Übungsblatt

Beim Korrigieren Eurer Übungsblätter sind uns einige Fehler aufgefallen, die wieder und wieder gemacht worden sind. Wir haben im Folgenden versucht, die besonders häufig aufgetretenen Fehler zusammenzustellen.

Heaps/Prioritätswarteschlangen

• "Die Kinder sind immer kleiner als der Vater!"

Das stimmt beinahe. Also eigentlich nicht. ;-) In einem Heap sind die Kinderknoten kleiner oder gleich dem Vaterknoten. Das "gleich" ist hierbei sehr wichtig! (Denn was wuerde man sonst machen, wenn der Heap aus n gleichen Elementen besteht?!?)

• "Jeder Knoten ist kleiner als sein rechtes Geschwister!"

Nein, nein, und nochmal nein! Die Tatsache, dass ein Baum Heap-Struktur und Heap-Ordnung besitzt, sagt rein gar nichts über die Sortierung der Knoten in einer Ebene (also der Geschwister) aus!

• "Alle Blätter sind in der Tiefe t!"

Nicht wirklich. Die Blätter eines Heap-Baumes sind entweder alle in der selben Ebene, oder sie sind über genau zwei Ebenen verteilt!

• "Wenn ein Heap-Baum Blätter in den Ebenen t und t+1 besitzt, dann ist der Knoten/das Blatt mit der niedrigsten Priorität in der Ebene t+1!"

Nööö, es kann auch in der Ebene t sein.

Bäume und Pflanzen

• "Der Vater von dem Kind in Ebene t ist in der dritten Schicht, und die Wurzel in der ersten Generation!"

Ääääh, o.k., alles klar ;-) Was uns dieses Beispiel sagen möchte: Bitte, bitte, bitte halte die Terminologie ein, wie Du sie in der Vorlesung oder aus Fachbüchern gelernt habt! Die "Tiefe" eines Knotens, seine "Ebene" oder "Generation" sind ein- und dasselbe! (Allerdings ist die "Höhe" eines Knotens etwas Anderes! Und stets ist es so, dass die Wurzel den Wert 0 besitzt! Aussagen wie "die Wurzel ist in der ersten Generation" bewirken beim Tutor und Klausurkorrektor einen Schluckauf! ;-) Und wenn Du Dich genötigt siehst, neue Begriffe ("Schicht", "Level", ...) zu benutzen, dann erkläre sie einfach! Im Zweifelsfall bringt es uns mehr Spaß, und Dir mehr Punkte! ;-)

• "In dem Baum B wird der Wert xxx von einer Wurzel gespeichert!"

Von einer der vielen Wurzeln?!? Es gibt doch nur eine einzige Wurzel in einem Baum! Nicht, dass wir Dir unterstellen, Du wüsstest das nicht - aber es erweckt auch nicht grade den Eindruck, dass Du den Umgang mit Bämen wirklich geübt bist... ;-)

Sonstige Anmerkungen

• Wenn man einen Widerspruchsbeweis macht, sollte die Aussage, die ganz am Ende rauskommt, im Widerspruch stehen zu der Behauptung, die man ganz am Anfang gemacht hat. Es ist vergeudete Mühe, einen müßigen und kräftezehrenden Widerspruchsbeweis führen zu wollen, nur um dann eine Aussage zu schlußfolgern, die zu Allem im Widerspruch steht, außer zu der Behauptung vom Anfang des Beweises!

• Bei der Korrektur der Aufgaben kam ein Bischen der Eindruck auf, nach den durchlebten Induktionsbeweisen der Vorrunde fühlen sich einige Teilnehmer der Tutorien genötigt, "auf Teufel komm 'raus" jeden Beweis durch vollständige Induktion lösen zu müssen - dem ist nicht so: Beweise lassen sich auch durch einen "direkten Beweis" oder einen "Widerspruchsbeweis" erbringen! Speziell bei der Aufgabe 5.1.a.i) war die vollständige Induktion eher einer der längeren Wege... ;-)

• Irgendjemand hat mal gesagt, dass es ausreicht, ein Gegenbeispiel zu finden, um einen Beweis zu widerlegen. Dem ist richtig! Aber bitte schön, nichts desto trotz freut sich ein Tutor auch, wenn neben einem gemalten Baum auch noch ein oder zwei Worte der Erklärung stehen! ;-) (Speziell Aufgabe 5.1.a.iii))

• t ist ungleich t+1! Und doch gibt es Beweise mit vollständiger Induktion, wo beim Induktionsschritt genau das steht: t=t+1. (Oder auch: k=k*2.) Wer uns denjenigen Wert für t zeigt, bei dem diese Gleichung erfüllt ist, bekommt eine Flasche Sekt! ;-) Diese Gleichung ist natürlich falsch; es muss t -> t+1 lauten. (t ist nicht gleich t+1, sondern t geht über nach t+1, soll heißen: t verändert sich, indem sein Wert um 1 erhöht wird.)

Klicke hier, um zurück zur Hauptseite zu gehen.