Fachrat Informatik - Forum

Ich hätte auch noch eine Frage.
Im Skript auf Seite 38 steht:

„Ein geordneter Baum, bei dem alle Knoten einen Grad kleiner gleich zweibesitzen ist nicht notwendig ein binärer Baum!“

Vielleicht stehen wir nur auf dem Schlauch, aber uns ist nicht eingefallen, wie ein geordneter Baum, bei dem jeder Knoten höchstens 2 Nachfolger haben soll, aussieht, wenn es dabei kein Binärbaum sein soll.
Kann uns da wer weiterhelfen?

Ich würde mal tippen dass das mit den Elementen selbst zu tun hat, nicht mit der "Zeichenweise" des Baumes.
In Binären Bäumen ist explizit gefordert dass die Element-Mengen disjunkt sind (s.S.37 unten), ein Element also nicht mehrfach vorkommen kann.
2 Mengen sind dann disjunkt, wenn die in der einen Menge enthaltenen Elemente nicht in der anderen Menge auftauchen. {1,2,3} ist also disjunkt zu {4,5,6}, aber die Menge {7,8,9} ist nicht disjunkt zu {7,10,11}, weil die 7 beide male vorkommt. In einem binären Baum gibt es also keine 2 Teilbäume, deren Elemente nicht disjunkt sind.
Bei geordneten Bäumen hingegen ist nur eine Ordnung innerhalb der Teilbäume, aber nicht über den ganzen Baum gegeben, es müssten also Elemente mehrfach vorkommen können, obwohl die Knoten nur vom Grad <= 2 sind.
Keine Ahnung ob das so stimmt, ist nur laut gedacht.

HAVE PHUN!

Quoted from "hamena314"

Bei geordneten Bäumen hingegen ist nur eine Ordnung innerhalb der Teilbäume, aber nicht über den ganzen Baum gegeben, es müssten also Elemente mehrfach vorkommen können, obwohl die Knoten nur vom Grad <= 2 sind.

Ein Knoten mehrmals im Baum? Auch wenn die Definition eines geordneten Baums am Anfang des Skripts etwas merkwürdig ist (Warum nicht erst Graphen und dann Bäume definieren?), gehe ich mal stark davon aus, dass man sich auch hier die Wurzeln aus einer Knotenmenge V denken soll. V ist aber keine Multimenge, von daher kann es jede Wurzel bzw. dann als Knoten nur einmal in einem geordneten Baum geben.

In meinen Augen sollte man auch den Begriff "Grad" nur in der Bedeutung der Graphentheorie und nicht für die Anzahl der direkten Nachfolger verwenden bzw. wenigstens Verzweigungsgrad sagen dann.

Hallo,

also ich schließe mich in diesem Thread mal der Fragerunde an. Muss allerdings im Vorfeld dazu sagen, dass ich als Nebenfachstudent und Nicht-Informatiker mit Sicherheit einige Fragen stellen werde, die „Fachleute“ eher zum Schmunzeln bringen…

Und dann wollen wir mal anfangen…

Fragen zu Übung 3, Aufgaben 1 & 2: Wie ist denn der richtige Pseudocode der Lösung? Wie greife ich korrekt auf meine „Ursprungsliste“ zu? Es ist doch quasi eine Methode für meine Klasse ADTList, oder? Wie greife ich denn auf die Werte meiner „internen“ Liste zu (also auf meine „Klassenvariable“)? Über this? Über L.first()? Wie dann Differenzierung zwischen übergebener Liste L aus dem Parameter und der „internen“ Liste?

Fragen zu Stundenübung 6, allgemein: Leider war ich bei der Übung nicht da und habe dafür keine Lösung. Darum habe ich zu quasi allem eine Frage:

• Wie sieht denn der Heap in Aufgabe 1 aus wenn die Wurzel entfernt wurde?
  B C F E D H I G (in Stufenordnung)?
  
• Wie sieht der Heap nach dem Einfügen der 4 Knoten in Aufgabe 2 aus?
  A C B E D F I G N M Z H (in Stufenordnung)?
  
• Wie ist der korrekte Huffman-Code mit der mitteleren Codewortlänge? Ich habe s = 1, t = 000, u = 01 und v = 001 mit einer mittleren Codewortlänge von 1,65. Ist das richtig?

Fragen zu Stundenübung 11: Leider sind mir die Sortierverfahren noch nicht so ganz klar – und meine Mitschrift der Stundenübung 11/Aufgabe 2 hilft mir auch nicht wirklich weiter. Hat jemand eine voll ausformulierte Lösung und kann die posten?

Frage zu Übung 1, Aufgabe 3: Wie wird die Laufzeit eines solchen Programms berechnet, in dem eine If-Anweisung zwischen O(n) und O(n) verantwortlich ist?

Frage zu Übung 3, Aufgabe 3: Was ist hier die Lösung? Ich hätte jetzt gedacht, dass eine Queue durch zwei Stacks realisiert werden kann und umgekehrt bei einer Laufzeit von O(2n) oder so. Hab aber nicht wirklich Ahnung…

Übung 4, Aufgabe 1: Ich hab folgende Lösungen – sind die richtig?

• 1a)
  
• Stufenordnung: A B C D E F G H I
  
• Präordnung: A B E C F G D H I
  
• Postordnung: E B F G C H I D A
  
• 1b)
  
• Stufenordnung: A B E C F D G H I
  
• Präordnung: A B E C F G D H I
  
• Postordnung: E G F I H D C B A
  
• 1c)
  
• Symmetrische Ordnung: E D F G C H I D C B A

Übung 4, Aufgabe 2: Kann ich nicht… Kann mir das jemand zufällig erklären?

Übung 5, Aufgabe 1c: Was ist die Lösung? Ich habe: 1 ( 2 ( 5 ( 9 10 11) 3 ( 6 7 (12) ) 4 ( 8 ( 13 )). Ist das richtig?

So – der Rest meiner Fragen kommt nach ner Pause ;-).

LG Timo

Und hier kommt Teil 2 meiner Fragen…

Übung 5, Aufgabe 2: Wie sieht der Baum aus Aufgabe 2a aus? Ich habe meine Lösung mal als Bild mit angehängt. Ist das richtig?

Übung 5, Aufgabe 3: Was ist hier die Lösung. Mit solche mathematischen Sachen hab ich es nicht so ;-).

Übung 6, Aufgabe 1:

1a) Wie sieht der Heap aus? Ist die folgende Stufenordnung richtig? 1 4 2 7 5 10 3 11 9 13 8 12 14 6

1c) Sieht der Heap nach 1b und 1c gleich aus? Ist die Lösung wieder die Stufenordnung, die ich unter 1a angegeben habe?

Übung 6, Aufgabe 3: Was ist die richtige Lösung? Ich habe folgende Codes:

g 1
b 01
e 001
c 0001
h 00001
d 000001
f 0000001
a 00000001

Als mittlere Codewortlänge habe ich 2,83. Wer hat weniger? ;-)

Übung 7, Aufgabe 1: Ich würde hier gerne mal die Ergebnisse abgleichen. Ich habe:
1a) 5,081
1b) 3,649
1c) 9,351

Übung 7, Aufgabe 2: Auch hier würde ich gerne mal die Ergebnisse abgleichen. Ich habe:
2a) 4,64
2b) Letzte Zeile meiner Tabelle (ohne den Tausch des letztes Auf, weil da Auf! steht): Bau Auf Für Dino Caro Innen Emil Gas Julia Hans
2c) Wieder ohne das letzte Auf!-Vertauschen: 4,4

Übung 8, Aufgabe 2: Wie errechnet man die mittlere Zugriffszeiten bei erfolgreicher und nicht erfolgreicher Suche? Was sind hier die richtigen Ergebnisse?

Übung 8, Aufgabe 3: Was ist hier die korrekte Lösung?

Übung 9, Aufgabe 1:
1a) Was ist hier der Lösungsansatz. Ich hätte jetzt an so was wie h(k) = asci(k, 0) + substr(k, strlen(k)-1, 1) – ascr(a) gedacht, also eine Kombination aus dem ersten Buchstaben und der letzten Ziffer der Worte.
1b) Keine Ahnung! Ich hätte gesagt, dass es auch hier eine perfekte Hashfunktion geben kann. Diese müsste halt nur zwischen „Sehnde59“ und „schlecht“ differenzieren, also z.B. nicht nur auf das erste Zeichen achten.
1c) Keine Ahnung! Was ist hier die Lösung?

Übung 9, Aufgabe 2: Anscheinend wird meine Ratlosigkeit mit fortgeschrittenen Übungen größer… Was ist denn hier der Lösungsansatz?

Übung 9, Aufgabe 3: Würde hier gerne mal meine Lösungen abgleichen:
3a) Präordnung mit Klammern: List ( Hashtable Stack (Queue (Set) Table (Tree) ) )
3b) Mittlere Suchzeit bei erfolgreicher Suche: 19/7
3c) Präordnung mit Klammern: Stack ( Queues ( List ( Hashtable ) Set ) Table (Tree) ); mittlere Suchzeit: 18/7

Übung 10, Aufgabe 1: Also ich hätte jetzt gedacht, dass es sich beim Baum in 1a um einen B+-Baum handelt (weil er alle Kriterien erfüllt), bei 1b jedoch nicht, weil es Knoten mit weniger als m Schlüsseln gibt und die Wege von der Wurzel zu den Blättern nicht alle die gleiche Länge haben. Ist das richtig? Und noch ne andere Frage: Welche Ordnung hat der Baum in 1b? 3? Wenn nein – warum?

Übung 10, Aufgabe 2: Hmm – die übermittel ich jetzt mein Ergebnis hierzu. Also nach den drei Aktionen sieht mein Baum so aus:

• 4 30 45
  
• 1 2 3
  
• 21 24 28
  
• 30 40 44
  
• 49 50 59

Ist das richtig?

Übung 10, Aufgabe 3: Wieso hat der Baum die Ordnung 2??? Ich raffe das nicht. Der läuft doch auf 3 „Ebenen“…

Übung 11: Mein Problem mit den Sortierverfahren habe ich ja schon gepostet…

So – das wars fürs erste. Mal gucken ob ich morgen noch ein paar Fragen zusammenkriege ;-).

LG Timo

Quoted from "timo96"

Übung 6, Aufgabe 1:
1a) Wie sieht der Heap aus? Ist die folgende Stufenordnung richtig? 1 4 2 7 5 10 3 11 9 13 8 12 14 6

Ja, kommt hin.

Quoted from "timo96"

1c) Sieht der Heap nach 1b und 1c gleich aus? Ist die Lösung wieder die Stufenordnung, die ich unter 1a angegeben habe?

Nein, bei 1b wird die 1 gelöscht und der sieht dann ca so aus 6 4 2 7 5 10 3 11 9 13 8 12 14. Nach 1c sollte er wieder so wie in 1a aussehen.

Quoted from "timo96"

Übung 6, Aufgabe 3: Was ist die richtige Lösung? Ich habe folgende Codes:

g 1
b 01
e 001
c 0001
h 00001
d 000001
f 0000001
a 00000001

Als mittlere Codewortlänge habe ich 2,83. Wer hat weniger? ;-)

Ich komme da auf folgenden Code
a 01010
b 11
c 0111
d 0100
e 10
f 01011
g 00
h 0110

Mit einer Länge von 2,62.

Dein Code für a ist schon relativ lang. Da werden schon zu viele Bits verbraucht, die im Normalfall für eine Codierung gar nicht nötig sind.

Sind leider nur ein paar Antworten, aber die konnte ich gerade mal eben beantworten

Quoted from "hyperion"

Quoted from "timo96"

1c) Sieht der Heap nach 1b und 1c gleich aus? Ist die Lösung wieder die Stufenordnung, die ich unter 1a angegeben habe?

Nein, bei 1b wird die 1 gelöscht und der sieht dann ca so aus 6 4 2 7 5 10 3 11 9 13 8 12 14. Nach 1c sollte er wieder so wie in 1a aussehen.

Heißt "rekonstruiere" hier nicht etwa wieder einen Min-Heap daraus machen? denn deiner mit 6 4 2 7 ... entspricht nicht der Min-Heap Eigenschaft. Da muss man doch noch ein paar Umformungen machen, oder?

ich bin bei 1b auf 2 4 3 7 5 10 6 11 9 13 8 12 14 gekommen.

Quoted from "Cipher"

Heißt "rekonstruiere" hier nicht etwa wieder einen Min-Heap daraus machen? denn deiner mit 6 4 2 7 ... entspricht nicht der Min-Heap Eigenschaft. Da muss man doch noch ein paar Umformungen machen, oder?

ich bin bei 1b auf 2 4 3 7 5 10 6 11 9 13 8 12 14 gekommen.

Stimmt natürlich. Sorry, war im Heap verrutscht.

Quoted from "timo96"

• 1a)
  
• Stufenordnung: A B C D E F G H I
  
• Präordnung: A B E C F G D H I
  
• Postordnung: E B F G C H I D A
  
  
• 1b)
  
• Stufenordnung: A B E C F D G H I
  
  
• Präordnung: A B E C F G D H I
  
  
• Postordnung: E G F I H D C B A
  
  
• 1c)
  
• Symmetrische Ordnung: E D F G C H I D C B A 2 mal D ???
  

Übung 5, Aufgabe 1c: Was ist die Lösung? Ich habe: 1 ( 2 ( 5 ( 9 10 11) 3 ( 6 7 (12) ) 4 ( 8 ( 13 )). Ist das richtig?

Quoted from "timo96"

Übung 7, Aufgabe 1: Ich würde hier gerne mal die Ergebnisse abgleichen. Ich habe:
1a) 5,081
1b) 3,649 nicht gerechnet... aber könnte hinkommen
1c) 9,351 nicht gerechnet... aber könnte hinkommen




Übung 9, Aufgabe 3: Würde hier gerne mal meine Lösungen abgleichen:
3a) Präordnung mit Klammern: List ( Hashtable Stack (Queue (Set) Table (Tree) ) )
3b) Mittlere Suchzeit bei erfolgreicher Suche: 19/7
3c) Präordnung mit Klammern: Stack ( Queues ( List ( Hashtable ) Set ) Table (Tree) ); mittlere Suchzeit: 18/7 hab ich nicht so... Das ist glaube ich kein Binärbaum mehr... Meine Lösung in Präordnung mit klammern ist Set ( Liste (Hashtable Queue) Table (Stack Tree)) mittlere Suchzeit 17/7

Übung 10, Aufgabe 1: Also ich hätte jetzt gedacht, dass es sich beim Baum in 1a um einen B+-Baum handelt (weil er alle Kriterien erfüllt), bei 1b jedoch nicht, weil es Knoten mit weniger als m Schlüsseln gibt und die Wege von der Wurzel zu den Blättern nicht alle die gleiche Länge haben. Ist das richtig? Und noch ne andere Frage: Welche Ordnung hat der Baum in 1b? 3? Wenn nein – warum? 1b hat die Ordnung 2. Steht in der Aufgabe. Der Weg zu den Blättern ist nicht immer gleich. Deshalb kein B+-Baum. Alle Knoten haben mindestens 2 und höchstens 4 schlüssel. Alles OK. Verstehe die Frage nicht ganz

Übung 10, Aufgabe 2: Hmm – die übermittel ich jetzt mein Ergebnis hierzu. Also nach den drei Aktionen sieht mein Baum so aus:

• 4 30 45
• 1 2 3
• 21 24 28
• 30 40 44
• 49 50 59 sieht gut aus...
  

Ist das richtig?

Übung 10, Aufgabe 3: Wieso hat der Baum die Ordnung 2??? Ich raffe das nicht. Der läuft doch auf 3 „Ebenen“…

B+-Bäume
B+-Baum der Ordnung m mit m > 1 ist ein Mehrfach-Verzweigungsbaum mit Suchbaum-Eigenschaft.
Es gilt weiterhin
1. Wurzel des Baumes enthält zwischen 1 und 2m Schl¨ussel
2. interne Knoten außer die Wurzel enthalten zwischen m und 2m Schlüssel
3. Alle Wege von der Wurzel zu einem Blatt haben die gleiche Länge

Die Ordnung hat mit den Ebenen nix zu tun. Nur mit den Schlüsseln in den Knoten.

Hoffe das stimmt alles so

Erstmal vielen Dank für Eure Antworten. Da ich heute noch bei nem Umzug helfen musste werde ich mir erst morgen die Sachen nochmal genauer angucken. Dann gehts ja auch in den finalen Lern-Endspurt ;-).

Ein paar Punkte konnte ich mir aber schon angucken. Anbei meine Rückfragen ;-).

Quoted from "hyperion"

Nein, bei 1b wird die 1 gelöscht und der sieht dann ca so aus 6 4 2 7 5 10 3 11 9 13 8 12 14. Nach 1c sollte er wieder so wie in 1a aussehen.

Ja - logisch. Das meinte ich auch...

Quoted from "hyperion"

Ich komme da auf folgenden Code
a 01010
b 11
c 0111
d 0100
e 10
f 01011
g 00
h 0110

Mit einer Länge von 2,62.

Hmm... wie ist denn da Dein Ansatz? Ich bin so vorgegangen, dass ich immer die geringsten Wahrscheinlichkeiten zusammengefasst habe, also a und f, dann d dazu, dann h dazu usw. Und dann hat sich daraus halt der Baum gebildet. Hab ich da was falsch gemacht?

Quoted from "Armin1906"

Queues ( List ( Hashtable ) Set ) Table (Tree) ); mittlere Suchzeit: 18/7 hab ich nicht so... Das ist glaube ich kein Binärbaum mehr... Meine Lösung in Präordnung mit klammern ist Set ( Liste (Hashtable Queue) Table (Stack Tree)) mittlere Suchzeit 17/7

Hmm - verdammt. Hab voll hin und her überlegt aber darauf irgendwie nicht gekommen...

Quoted from "Armin1906"

Die Ordnung hat mit den Ebenen nix zu tun. Nur mit den Schlüsseln in den Knoten.

Dann muss ich nochmal kurz nachfragen, wie sich die Ordnung eines Baumes bestimmt. Irgendwie hab ich da wohl was falsch verstanden...

So - für heute reichts!

LG Timo

Quoted from "timo96"

Quoted from "hyperion"

Ich komme da auf folgenden Code
a 01010
b 11
c 0111
d 0100
e 10
f 01011
g 00
h 0110

Mit einer Länge von 2,62.

Hmm... wie ist denn da Dein Ansatz? Ich bin so vorgegangen, dass ich immer die geringsten Wahrscheinlichkeiten zusammengefasst habe, also a und f, dann d dazu, dann h dazu usw. Und dann hat sich daraus halt der Baum gebildet. Hab ich da was falsch gemacht?

Der Ansatz ist korrekt. Hast Du denn auch die richtigen Zahlen abgelesen? Ich habe folgende Verbindungen im Baum:
a f
(a-f) d
c h
(a-f-d) (c-h)
b e
(a-f-d-c-h) g
(a-f-d-c-h-g) (b-e)

Und komme dann eben auf meinen Code mit 2,62 Länge.

Quoted from "hyperion"

Der Ansatz ist korrekt. Hast Du denn auch die richtigen Zahlen abgelesen? Ich habe folgende Verbindungen im Baum:
a f
(a-f) d
c h
(a-f-d) (c-h)
b e
(a-f-d-c-h) g
(a-f-d-c-h-g) (b-e)

Und komme dann eben auf meinen Code mit 2,62 Länge.

Hmm - aber so korrekt kann das bei mir nicht sein. Ich habe nämlich immer einfach das Symbol mit der nächstgeringsten Wahrscheinlichkeit dazugenommen, also

a f
(a-f) d
(a-f-d) h
(a-f-d-h) c
(a-f-d-h-c) e
usw.

Wenn ich das bei dir richtig sehe und interpretiere hast Du nach (a-f) d = 0,11 zuerst c und h = 0,17 zusammengefasst. Wieso? Weil (c-h) = 0,17 < (a-f-c-h) = 0,18?

Quoted from "timo96"

Wenn ich das bei dir richtig sehe und interpretiere hast Du nach (a-f) d = 0,11 zuerst c und h = 0,17 zusammengefasst. Wieso? Weil (c-h) = 0,17 < (a-f-c-h) = 0,18?

Ja, Du nimmst immer die beiden kleinsten Werte zusammen. Im Endeffekt gibt es dann die kleinste Summe.

EDIT:
So wie Du es aufgezählt hattest, klang der Ansatz korrekt

Ich komme auch auf 2.62
Es geht nicht darum eine Symbolwahrscheinlichkeit nach der anderen hinzuzufügen, sondern jeweils die beiden kleinsten.
Nach (a-f-d)=0.11 sind die beiden kleinsten h=0.07 und c=0.10. Also müssen diese zuerst zusammengefasst werden.
Hoffe, ich konnte damit noch zur Klärung beitragen


*zu spät*

Jep - verstanden. Vielen Dank Euch beiden! Wenn ihr mir jetzt auch noch bei der Sortierung und den anderen Punkten auf die Sprünge helfen könntet wäre das super ;-).

Und ich schicke noch mal zwei kurze Fragen hinterher, weil ich gerade das Skript durcharbeite: Wie errechnet sich das Mittel bei nicht erfolgreicher Suche beim Hashing (Skript S. 72 und 75). Wo kommen die Zahlen her, die da addiert werden. Das raff ich irgendwie nicht...

Du addierst für jede Kombination die Zugriffe bis du eindeutig sagen kannst das du es nicht findest.
Das heißt Wenn schon was drin steht, sucht du mind. noch eins weiter, wen nichts drinsteht dann 0 mal. Also stehen die 0en für die leeren Plätze.
Bei den Verknüpften Hashtabellen (S. 72) kommt die 3 zum Beispiel dadurch zu stande, das an der 14. Position 3 Einträge sind, die verglichen werden müssen.

Das ganze teilst du dann um das Mittel zu bekommen durch die Tabellenplätze (also Gesamt anzahl der Plätze).

Wenn du double Hashing hast, dann musst du alle möglichen Kombinationen der beiden Funktionen auflisten und die Zugriffe bestimmen, die dann benötigt werden, um den Misserfolg eindeutig feststellen zu können.

Hey,
bin im Skript über das Kapitel Rot - Schwarz Bäume gestolpert und wollte mal wissen ob wir die in einer Übung oder so jemals behandelt hatte, da es mir komplett unbekannt vorkommt.
Und welchem Wert ist der Übungsklausur zu zumessen??

Rot-Schwarz- Bäume und AVL Bäume kommen nicht dran!