www.vorhilfe.de
Vorhilfe

Kostenlose Kommunikationsplattform für gegenseitige Hilfestellungen.
Hallo Gast!einloggen | registrieren ]
Startseite · Forum · Wissen · Kurse · Mitglieder · Team · Impressum
Forenbaum
^ Forenbaum
Status Vorhilfe
  Status Geisteswiss.
    Status Erdkunde
    Status Geschichte
    Status Jura
    Status Musik/Kunst
    Status Pädagogik
    Status Philosophie
    Status Politik/Wirtschaft
    Status Psychologie
    Status Religion
    Status Sozialwissenschaften
  Status Informatik
    Status Schule
    Status Hochschule
    Status Info-Training
    Status Wettbewerbe
    Status Praxis
    Status Internes IR
  Status Ingenieurwiss.
    Status Bauingenieurwesen
    Status Elektrotechnik
    Status Maschinenbau
    Status Materialwissenschaft
    Status Regelungstechnik
    Status Signaltheorie
    Status Sonstiges
    Status Technik
  Status Mathe
    Status Schulmathe
    Status Hochschulmathe
    Status Mathe-Vorkurse
    Status Mathe-Software
  Status Naturwiss.
    Status Astronomie
    Status Biologie
    Status Chemie
    Status Geowissenschaften
    Status Medizin
    Status Physik
    Status Sport
  Status Sonstiges / Diverses
  Status Sprachen
    Status Deutsch
    Status Englisch
    Status Französisch
    Status Griechisch
    Status Latein
    Status Russisch
    Status Spanisch
    Status Vorkurse
    Status Sonstiges (Sprachen)
  Status Neuerdings
  Status Internes VH
    Status Café VH
    Status Verbesserungen
    Status Benutzerbetreuung
    Status Plenum
    Status Datenbank-Forum
    Status Test-Forum
    Status Fragwürdige Inhalte
    Status VH e.V.

Gezeigt werden alle Foren bis zur Tiefe 2

Navigation
 Startseite...
 Neuerdings beta neu
 Forum...
 vorwissen...
 vorkurse...
 Werkzeuge...
 Nachhilfevermittlung beta...
 Online-Spiele beta
 Suchen
 Verein...
 Impressum
Das Projekt
Server und Internetanbindung werden durch Spenden finanziert.
Organisiert wird das Projekt von unserem Koordinatorenteam.
Hunderte Mitglieder helfen ehrenamtlich in unseren moderierten Foren.
Anbieter der Seite ist der gemeinnützige Verein "Vorhilfe.de e.V.".
Partnerseiten
Dt. Schulen im Ausland: Mathe-Seiten:

Open Source FunktionenplotterFunkyPlot: Kostenloser und quelloffener Funktionenplotter für Linux und andere Betriebssysteme
Forum "Sonstiges" - Ausdrücke, Sorten, Konstruktor
Ausdrücke, Sorten, Konstruktor < Sonstiges < Hochschule < Informatik < Vorhilfe
Ansicht: [ geschachtelt ] | ^ Forum "Sonstiges"  | ^^ Alle Foren  | ^ Forenbaum  | Materialien

Ausdrücke, Sorten, Konstruktor: Ausdruck korrekt? Choice-Aufg
Status: (Frage) überfällig Status 
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.

        
Bezug
Ausdrücke, Sorten, Konstruktor: Konstruktor und Nichtkonstruk
Status: (Frage) beantwortet Status 
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 :(


Bezug
                
Bezug
Ausdrücke, Sorten, Konstruktor: Antwort
Status: (Antwort) fertig Status 
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

Bezug
                        
Bezug
Ausdrücke, Sorten, Konstruktor: Nur create und Tree?
Status: (Frage) überfällig Status 
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

Bezug
                                
Bezug
Ausdrücke, Sorten, Konstruktor: Fälligkeit abgelaufen
Status: (Mitteilung) Reaktion unnötig Status 
Datum: 18:21 So 27.04.2008
Autor: matux

$MATUXTEXT(ueberfaellige_frage)
Bezug
        
Bezug
Ausdrücke, Sorten, Konstruktor: Neue Operation
Status: (Frage) überfällig Status 
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




Bezug
                
Bezug
Ausdrücke, Sorten, Konstruktor: Fälligkeit abgelaufen
Status: (Mitteilung) Reaktion unnötig Status 
Datum: 16:20 Sa 26.04.2008
Autor: matux

$MATUXTEXT(ueberfaellige_frage)
Bezug
        
Bezug
Ausdrücke, Sorten, Konstruktor: Fälligkeit abgelaufen
Status: (Mitteilung) Reaktion unnötig Status 
Datum: 16:20 Sa 26.04.2008
Autor: matux

$MATUXTEXT(ueberfaellige_frage)
Bezug
Ansicht: [ geschachtelt ] | ^ Forum "Sonstiges"  | ^^ Alle Foren  | ^ Forenbaum  | Materialien


^ Seitenanfang ^
www.vorhilfe.de