Ausdrücke, Sorten, Konstruktor < Sonstiges < Hochschule < Informatik < Vorhilfe
|
| Status: |
(Frage) überfällig  | | Datum: | 14:22 Mi 26.03.2008 | | Autor: | Pein |
| Aufgabe |
In dieser Aufgabe geht es darum, die Datenstruktur "Binärbaum" als Abstrakten Datentyp darzustellen.
Die Menge der Sorten ist gegeben durch
B = Menge der Wahrheitswerte
K = Menge der SChlüsselwerte-Paare
T = Menge der Bäume
Die Operationen mit zugehöriger Signatur sind
create : [mm] \to [/mm] T
root : T [mm] \to [/mm] K
tree : T [mm] \times [/mm] K [mm] \times [/mm] T [mm] \to [/mm] T
left: T [mm] \to [/mm] T
right: T [mm] \to [/mm] T
empty: T [mm] \to [/mm] B
Kreuzen Sie alle syntaktisch zulässigen Ausdrücke an mit k, [mm] k_1, k_2 \in [/mm] K
1) root(tree(create(),k,create() ))
2) [mm] tree(left(tree(create(),k_1,create())),k_2,create())
[/mm]
3) empty(left(tree(create(),x,create() ))))
4) empty(root(create() ))
|
Hallo
Ich brauche mal hilfe bei dieser Multiple-Choice Aufgabe und würde gerne wissen, was ihr als richtig anseht
1) ist meiner Meinung nach richtig
2) auch richtig
3) nicht richtig, weil was ist denn x?
4) nicht richtig, weil empty(root(create() ) ) <-> empty(root(T) ) <-> empty(K) nicht definiert (so darf man es vermutlich nicht aufschreiben, aber so habe ich überlegt)
Würde mich sehr über Hilfe hier freuen. Da dies wohl eine einfache Aufgabe ist, schreibe ich die schwierige in einem weiteren Frageartikel
Danke euch schon mal!!!
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
|
|
| |
|
| Status: |
(Frage) beantwortet  | | Datum: | 14:36 Mi 26.03.2008 | | Autor: | Pein |
| Aufgabe | In dieser Aufgabe geht es darum, die Datenstruktur "Binärbaum" als Abstrakten Datentyp darzustellen.
Die Menge der Sorten ist gegeben durch
B = Menge der Wahrheitswerte
K = Menge der SChlüsselwerte-Paare
T = Menge der Bäume
Die Operationen mit zugehöriger Signatur sind
create : $ [mm] \to [/mm] $ T
root : T $ [mm] \to [/mm] $ K
tree : T $ [mm] \times [/mm] $ K $ [mm] \times [/mm] $ T $ [mm] \to [/mm] $ T
left: T $ [mm] \to [/mm] $ T
right: T $ [mm] \to [/mm] $ T
empty: T $ [mm] \to [/mm] $ B
Klassifizieren Sie die Operationen in Konstruktor und Nichtkonstruktormenge, und geben Sie einen vollständigen Satz von Axiomen an.
Definition aus der Vorlesung: Konstruktormenge = mininale Menge von Operationen, mit denen man alle Elemente (=Instanzen) des Abstrakten Datentyps konstruieren kann. |
Noch mal hallo.
Leider muss ich sagen, die Operationen kann ich schon nicht ganz nachvollziehen
create, legt einen neuen Baum an
root sagt einem, wie viele Schlüssel-Wert-Paare es in all unseren erzeugten Bäumen gibt
Jetzt weiß ich leider nicht, was Schlüsselwertpaare sind
[mm] tree:T\times [/mm] K [mm] \times [/mm] T -> T
Was sagt einem das? Nimmt man den gesuchten Wert und zwei Bäume A und B und tree sagt einem dann, ob sich der gesuchte Wert im Baum A oder im Baum B befindet? "Menge der Bäume" würde meine Vermutung als falsch ansehen
left, right? Was macht man da? Guckt man da im Baum links und im Baum rechts?
empty: Sagt einem, ob der Baum leer ist.
Nach der Definition der Konstruktormenge verstehe ich, worum es geht. Für die Konstruktormenge ist gesucht, mit welchen Operationen ich andere darstellen kann.
Z. B. dachte ich da: right(right)= left
Das ist bestimmt falsch, aber ich kann auch kein Beispiel geben, was ich meine
Vielleicht in etwa so
Wenn es noch create2: -> T geben würde
Dann wäre create z. B. in der Konstruktormenge und create2 in der Nichtkonstruktormenge, weil wir ja create2 schon durch create "darstellen" können.
Auch wenn meine Überlegungen alles Müll sind, helft mir hier bitte weiter :(
|
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 16:07 Do 27.03.2008 | | Autor: | dk-netz |
Hallo,
> Noch mal hallo.
>
> Leider muss ich sagen, die Operationen kann ich schon nicht
> ganz nachvollziehen
>
> create, legt einen neuen Baum an
richtig
>
> root sagt einem, wie viele Schlüssel-Wert-Paare es in all
> unseren erzeugten Bäumen gibt
> Jetzt weiß ich leider nicht, was Schlüsselwertpaare sind
da bin ich mir im Moment auch nicht sicher!
>
> [mm]tree:T\times[/mm] K [mm]\times[/mm] T -> T
> Was sagt einem das? Nimmt man den gesuchten Wert und zwei
> Bäume A und B und tree sagt einem dann, ob sich der
> gesuchte Wert im Baum A oder im Baum B befindet? "Menge der
> Bäume" würde meine Vermutung als falsch ansehen
>
> left, right? Was macht man da? Guckt man da im Baum links
> und im Baum rechts?
Das bedeuted eigentlich folgendes: Man nimmt einen linken Teilbaum (also einen normalen Baum), also das erste T, dann nimmt für gewöhnlich eine Bezeichnung für den neuen Wurzelknoten (und ich würde hier auch sagen, dass das K auch etwas derartiges bedeuted) und das 2. K ist der rechte Teilbaum. Es wird also ein neuer Baum gebaut, dessen Knoten K heißt und als linken Teilbaum das erste Argument hat und als linken den zweiten!
>
> empty: Sagt einem, ob der Baum leer ist.
richtig [mm] \Rightarrow [/mm] nimmt einen Baum und liefert einen Wahrheitswert
>
>
> Nach der Definition der Konstruktormenge verstehe ich,
> worum es geht. Für die Konstruktormenge ist gesucht, mit
> welchen Operationen ich andere darstellen kann.
>
Ich würde einfach sagen, dass das alle Operationen sind, die einen Baum erstellen, und zwar einen neuen.
Gruß
Daniel
|
|
|
| |
|
| Status: |
(Frage) überfällig | | Datum: | 16:34 Do 27.03.2008 | | Autor: | Pein |
| Aufgabe 1 | In dieser Aufgabe geht es darum, die Datenstruktur "Binärbaum" als Abstrakten Datentyp darzustellen.
Die Menge der Sorten ist gegeben durch
B = Menge der Wahrheitswerte
K = Menge der SChlüsselwerte-Paare
T = Menge der Bäume
Die Operationen mit zugehöriger Signatur sind
create : $ [mm] \to [/mm] $ T
root : T $ [mm] \to [/mm] $ K
tree : T $ [mm] \times [/mm] $ K $ [mm] \times [/mm] $ T $ [mm] \to [/mm] $ T
left: T $ [mm] \to [/mm] $ T
right: T $ [mm] \to [/mm] $ T
empty: T $ [mm] \to [/mm] $ B
Klassifizieren Sie die Operationen in Konstruktor und Nichtkonstruktormenge, und geben Sie einen vollständigen Satz von Axiomen an.
Definition aus der Vorlesung: Konstruktormenge = mininale Menge von Operationen, mit denen man alle Elemente (=Instanzen) des Abstrakten Datentyps konstruieren kann. |
Hallo
> > Leider muss ich sagen, die Operationen kann ich schon nicht
> > ganz nachvollziehen
> >
> > create, legt einen neuen Baum an
> richtig
> >
> > root sagt einem, wie viele Schlüssel-Wert-Paare es in all
> > unseren erzeugten Bäumen gibt
> > Jetzt weiß ich leider nicht, was Schlüsselwertpaare
> sind
> da bin ich mir im Moment auch nicht sicher!
> >
> > [mm]tree:T\times[/mm] K [mm]\times[/mm] T -> T
> > Was sagt einem das? Nimmt man den gesuchten Wert und
> zwei
> > Bäume A und B und tree sagt einem dann, ob sich der
> > gesuchte Wert im Baum A oder im Baum B befindet? "Menge der
> > Bäume" würde meine Vermutung als falsch ansehen
> >
> > left, right? Was macht man da? Guckt man da im Baum links
> > und im Baum rechts?
> Das bedeuted eigentlich folgendes: Man nimmt einen linken
> Teilbaum (also einen normalen Baum), also das erste T, dann
> nimmt für gewöhnlich eine Bezeichnung für den neuen
> Wurzelknoten (und ich würde hier auch sagen, dass das K
> auch etwas derartiges bedeuted) und das 2. K ist der rechte
> Teilbaum. Es wird also ein neuer Baum gebaut, dessen Knoten
> K heißt und als linken Teilbaum das erste Argument hat und
> als linken den zweiten!
> >
> > empty: Sagt einem, ob der Baum leer ist.
> richtig [mm]\Rightarrow[/mm] nimmt einen Baum und liefert einen
> Wahrheitswert
Ok, danke, damit komme ich schon mal im Ansatz weiter.
> >
> > Nach der Definition der Konstruktormenge verstehe ich,
> > worum es geht. Für die Konstruktormenge ist gesucht, mit
> > welchen Operationen ich andere darstellen kann.
> >
> Ich würde einfach sagen, dass das alle Operationen sind,
> die einen Baum erstellen, und zwar einen neuen.
Warum denn dann Operation in Mehrzahl? Zunächst dachte ich, es handelt sich nur um create. Also kommt tree noch mit dazu und das war es dann, oder?
Möchte hier nur sicher gehen, dass ich das richtig verstanden habe
Und was mache ich bei dieser Teilaufgabe?
| Aufgabe 2 |
und geben Sie einen vollständigen Satz von Axiomen an.
|
Grüße, Pein
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 18:21 So 27.04.2008 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
| |
|
| Status: |
(Frage) überfällig | | Datum: | 14:47 Mi 26.03.2008 | | Autor: | Pein |
| Aufgabe | In dieser Aufgabe geht es darum, die Datenstruktur "Binärbaum" als Abstrakten Datentyp darzustellen.
Die Menge der Sorten ist gegeben durch
B = Menge der Wahrheitswerte
K = Menge der SChlüsselwerte-Paare
T = Menge der Bäume
Die Operationen mit zugehöriger Signatur sind
create : $ [mm] \to [/mm] $ T
root : T $ [mm] \to [/mm] $ K
tree : T $ [mm] \times [/mm] $ K $ [mm] \times [/mm] $ T $ [mm] \to [/mm] $ T
left: T $ [mm] \to [/mm] $ T
right: T $ [mm] \to [/mm] $ T
empty: T $ [mm] \to [/mm] $ B
Definieren Sie unter Verwendung obiger Operationen die neue Operation leaves: T [mm] \to \mathbb{N}, [/mm] welche die Anzahl der Blätter des Baumes T zurückgibt.
|
und ein drittes Hallo 
Was ein Blatt eines Baumes ist, weiß ich. Was ein Baum ist, weiß ich auch. Nur wie zähle ich hier die Anzahl der Blätter?
Nehmen wir an, ich habe einen Binär-Baum mit 7 Knoten, 6 Kanten.
Da würde es vier Blätter geben. Weiterhin haben wir doch das Niveau 2 (unser Dozent hat es immer durcheinander gebracht, daher gibts wohl unterschiedliche Definitionen?), d. h. wir haben quasi "drei Ebenen" => [mm] 2^3 [/mm] - 1 = 7 = # Knoten im Binärbaum. Und [mm] 2^{3-1} [/mm] = 2 Blätter. Ich nehme an, das ist eine Formel, die wir in der Vorlesung hatten (oder sie ist unsinn ;) Meine vielen Zeichnungen deuten auf so eine Formel hin).
Jetzt habe ich mir folgendes überlegt:
a) Man durchwandert den Baum und zählt somit alle Blätter: ganz rechter Pfad, ganz rechter Pfad und vor der letzten Verzweigung biegen wir links ab, etc.
Ziemlich kompliziert, deswegen habe ich ja nach Formeln gesucht
b) wir Zählen die Anzahl der Knoten, die es z. B. im rechten Pfad gibt und würden dann mit der Formel [mm] 2^{AnzahlDerLevel - 1} [/mm] die Blätter berechnen.
Dann ist mir aufgefallen, dass das hier alles Müll ist, weil es ja nicht um Binärbäume geht
Ich komme auc leider mit den Operationen hier gar nicht klar.
Ich weiß nur, dass ich nach einem Ausdruck suche
leaves(bla(blabla, laber), bla2) = [mm] \IN
[/mm]
aber das kann auch irgendwie nicht sein, da wir ja nach einer Operation suchen,
Und die Operationen sind doch nur von der Form
leaves: T [mm] \to \IN
[/mm]
Ganz ehrlich, wäre nur gefragt gewesen nach einer Operation, die die Anzahl der Blätter des Baumes T zurückgibt, hätte ich leaves: T [mm] \to \IN [/mm] für de Antwort gehalten.
Grüße von Pein
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 16:20 Sa 26.04.2008 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 16:20 Sa 26.04.2008 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
