Not logged in. · Lost password · Register

ri31hoky
Member since May 2011
452 posts
Subject: ADT Klausuraufgabe 13.Juli.2008
Moin,

hat die Aufgabe jemand gemacht und kann mir sagen wie intensiv ich mir ADTs noch anschauen muss :D

Meine Lösungen

a)

create und add (Primärkonstruktoren)
remove und removeAll (Hilfskonstruktoren)

b)

T: (Typ) M
x: (Typ) T
y: (Typ) T


A1: contains (x, create) =    0
A2: contains (x, add(y,T)) = 1 + contains (x, T)    wenn x = y
                                       = contains(x, T)           sonst

c)

A3: remove (x, create) = create
A4: remove (x, add(y,T)) = T       wenn  x = y
                                      = remove(x,T) sonst

d)

A5: removeAll (x, T) =            T      wenn contains(x, T) = 0
A6: removeAll (x, add(y,T)) = remove (x, add(y,T)) wenn contains (x, T) = 1
                                          = removeAll(x, remove(x, add(y,T)))  sonst




Edit: Achja und bei Aufgabe 3 wird eine Ausgabe erwartet...die korrekte Antwort wäre wohl der code compilt nicht, weil die Sichtbarkeit von void i(); eingeschränkt wird..

Edit2: Außerdem soll man in der Klausur den Spannbaum mit Hilfe vom Dijkstra Algorithmus angeben o.O? Wie geht man da vor?
Also kürzester Weg mit Dijkstra, und minimale Spannbäume mit Kruskal und Prim sind mir klar, mit Dijkstra hab ich das aber noch nicht gesehen.
This post was edited 2 times, last on 2011-07-29, 16:56 by ri31hoky.
Der Ich
93,333% Dipl.-Exzentriker
Avatar
Member since Oct 2006
3642 posts
Dijkstra erzeugt einen Spannbaum aber nicht zwingend den minimalsten. Du musst halt alle Pfade vom Startknoten zu den anderen Knoten einzeichnen
* 01.10.2006, + 28.11.2011, † 31.01.2013
ri31hoky
Member since May 2011
452 posts
K danke, da hätte man draufkommen können
Der Ich
93,333% Dipl.-Exzentriker
Avatar
Member since Oct 2006
3642 posts
die removeAll-Axiome sind übrigens Grütze
* 01.10.2006, + 28.11.2011, † 31.01.2013
ri31hoky
Member since May 2011
452 posts
A5: removeAll (x, T) =            T      wenn contains(x, T) = 0
A6: removeAll (x, add(y,T)) = remove (x, add(y,T)) wenn contains (x, T) = 1
                                          = removeAll(x, remove(x, add(y,T)))  sonst

Ja ich dachte mir, dass da was nicht stimmt, weiß aber nach wie vor nicht genau was

removeAll(x, remove(x, T))

So ähnlich muss es doch gehen, ich rufe rekursiv die Methode removeAll auf, nur dass die betrachtete Liste jetzt ein x weniger enthält weil das gelöscht wurde.
Das mache ich so lange bis contains 0 ist.
Also vllt so?


A5: removeAll (x, T) =  T  wenn contains(x, T) = 0
                                   removeAll(x, remove(x, T))   sonst
This post was edited on 2011-07-29, 17:53 by ri31hoky.
knix
Avatar
Member since Oct 2009
242 posts
Vorschlag für die removeAll Axiome:

removeAll(x,create()) = create()
removeAll(x,add(y,M)) = removeAll(x,M)         falls x == y
                        add(y,removeAll(x,M))  sonst
just the BEST theorem: ec(G) = tᵤ(G) ∏(deg(v) - 1)!
Der Ich
93,333% Dipl.-Exzentriker
Avatar
Member since Oct 2006
3642 posts
so ist es
* 01.10.2006, + 28.11.2011, † 31.01.2013
ri31hoky
Member since May 2011
452 posts
Hm achso, dann "verliere" ich die Elemente dadurch, dass ich sie einfach überspringe wenn ich sie nicht remove, wenn ich das richtig sehe.

Danke auf jedenfall, bis zur nächsten ADT Aufgabe :D
ri31hoky
Member since May 2011
452 posts
So nächster Versuch: Klausuraufgabe vom 19.03.2007 Seite 6

a)

-  1
-  bin (create, 6, bin (create, 4, create))
-  4


b) height

A8: height (create) = -1
A9: height (bin (t1, x, t2)) = 1 + max (height(t1), height(t2))

c)

    public static int height (BT tree) {
        if (tree == null) {
            return -1;
        }
        else {
            return 1 + max(height(tree.left), height(tree.right));
        }
    }


d) diameter

A10: diameter (create) = -1
A11: diameter (bin (t1, x, t2)) = max (height(t1) + height(t2) + 1, max (diameter(t1), diameter(t2))


e) Zentrale Eigenschaft eines Suchbaumes

Es herrscht eine Ordnungsrelation, so dass für jeden Knoten gilt, dass das linke Kind kleiner (wenn vorhanden) und das rechte Kind größer als der Vaterknoten ist. (Oder andersrum)


f)

A12: isST (create) = true
A13: isST (bin (t1, x, t2)) = false wenn value(t1) >= x oder value(t2) <= x
                                       = isST(t1) && isST(t2) sonst (keine Ahnung wie das sonst gehen soll :D)


g)

An das Minimum von Baum B2 wird B1 als linkes Kind hinzugefügt


Diameter war hart, über Fehlerkorrekturen freue ich mich wie immer :)

Edit: Bin ich eigentlich der einzige der AuD lernt und dazu Fragen im Forum hat? :D so still hier
This post was edited on 2011-07-31, 14:56 by ri31hoky.
MalteM
Member since May 2011
1470 posts
Quote by ri31hoky:
Edit: Bin ich eigentlich der einzige der AuD lernt und dazu Fragen im Forum hat? :D so still hier
Zumindest ich bin im Moment eher mit KonzMod beschaeftigt...
wishes
Member since May 2011
395 posts
Quote by MalteM:
Quote by ri31hoky:
Edit: Bin ich eigentlich der einzige der AuD lernt und dazu Fragen im Forum hat? :D so still hier
Zumindest ich bin im Moment eher mit KonzMod beschaeftigt...

ebenfalls. Hab immer noch nicht alle folien durch :/
xlemmingx
Member since Jul 2011
35 posts
In reply to post #9
Quote by ri31hoky on 2011-07-31, 14:43:
A9: height (bin (t1, x, t2)) = 1 + max (height(t1), height(t2))
[...]
A11: diameter (bin (t1, x, t2)) = max (height(t1) + height(t2) + 1, max (diameter(t1), diameter(t2))

Passen die so? Braucht nicht auch ein rekursiv definiertes Axiom irgendwie eine Abbruchbedingung oder so?
ri31hoky
Member since May 2011
452 posts
Also meines Erachtens sind das hier die Abbruchbedingungen:

A8: height (create) = -1
A10: diameter (create) = -1


Zur Korrektheit hat sich bisher noch niemand geäußert
ellewoods
Member since Nov 2011
45 posts
In reply to post #9
Quote by ri31hoky on 2011-07-31, 14:43:
d) diameter

A10: diameter (create) = -1
A11: diameter (bin (t1, x, t2)) = max (height(t1) + height(t2) + 1, max (diameter(t1), diameter(t2))


f)

A12: isST (create) = true
A13: isST (bin (t1, x, t2)) = false wenn value(t1) >= x oder value(t2) <= x
                                       = isST(t1) && isST(t2) sonst (keine Ahnung wie das sonst gehen soll :D)


Solte es bei der d) in A11 nicht height(t1) + height(t2) + 2 heißen??

bei f) für A13 hab ich: isST(Bin(t1,x,t1)) = true falls x>maximunm(t1) && x>maximum(t2)
                                                          false sonst
Ist das auch möglich?
Close Smaller – Larger + Reply to this post:
Verification code: VeriCode Please enter the word from the image into the text field below. (Type the letters only, lower case is okay.)
Smileys: :-) ;-) :-D :-p :blush: :cool: :rolleyes: :huh: :-/ <_< :-( :'( :#: :scared: 8-( :nuts: :-O
Special characters:
Go to forum
Datenschutz | Kontakt
Powered by the Unclassified NewsBoard software, 20150713-dev, © 2003-2011 by Yves Goergen