View Full Version : [Frage] Hauptuni Prüfungstermin
ghost dog
17-05-2004, 15:23
hello!
gibts bereits einen prüfunstermin termin?
vielen dank!
michi
hello!
gibts bereits einen prüfunstermin termin?
vielen dank!
michi
hi michi !
laut piswi gibt es noch keinen termin. werde dir bescheid sagen wenn es wieder einen gibt !
lg
max
ghost dog
21-05-2004, 12:36
hat prof. shikuta in der VO mal einen termin genannt?
Prof. Schikuta hat einmal etwas vom 29.06. erzählt. Und es soll im Jahr immer sechs Prüfungstermine geben.
sentencedX
01-06-2004, 22:20
wo bekommt man eigentlich das scriptum?
Die Prüfung ist am 1.7. um 10 Uhr in NIG.
wo bekommt man eigentlich das scriptum?
Scriptum ist ausschließlich in der Sekrätariat zu kaufen. kosten ~6 €.
LaTiNo___
19-06-2004, 01:15
Ich hab den Prof. Shikuta auch für die PO-s gefragt... er hat gesagt, dass es gibt, aber ich kann die leider nicht im Internet finden .... weiss jemand vielleicht den Link wo die PO-s sind?!!
Vergesst nicht euch im Piswi anzumelden!
Der Schikuta ist bei Terminen ziemlich streng! Man muss sich bis zum 24.06.2004 angemeldet haben!
Ich hab den Prof. Shikuta auch für die PO-s gefragt... er hat gesagt, dass es gibt, aber ich kann die leider nicht im Internet finden .... weiss jemand vielleicht den Link wo die PO-s sind?!!
bin mir nicht sicher ob es nichts aktuelleres gibt, aber mehr hatte ich nicht gefunden..
Falls ihr was habt bitte posten! :)
Hat Prof. Schikuta in der VO etwas wichtiges erwähnt bezüglich der Prüfung? war leider nur in der ersten Vorlesung anwesend :D
LaTiNo___
24-06-2004, 15:17
Hier können die PO-s finden
http://leonardo.pri.univie.ac.at/~schiki/teach/materials/AD1/prfg/
Hier können die PO-s finden
http://leonardo.pri.univie.ac.at/~schiki/teach/materials/AD1/prfg/
Danke! :thumb:
hat schon wer Ausarbeitungen dazu? :)
hallo,
war in der letzten Vo-Einheit anwesend. Schikuta hat gemeint es kommen nur die folien, die er auch gemacht hat. Da ich nicht immer anwesend war, weiss ich leider nicht, welche Folien er ausgelassen hat.
Weiss das jemand?
Danke
hab ne Frage zu den 2-3-4-Bäumen:
250304_2a: Fügen Sie die Werte 5,8,3,4,6,7,1,2,9,11,10 in dieser Reihenfolge in einen ursprünglich leeren 2-3-4-Baum ein.
hab da 2 Lösungsvarianten (beim einen splitte ich gleich, beim anderen später) und weiß nicht welche davon passt.. kann sich das mal wer angucken bitte? :)
Lösungsvariante 1 (http://stud3.tuwien.ac.at/~e9525517/algodat/algo_250304_2a_1.png)
Lösungsvariante 2 (http://stud3.tuwien.ac.at/~e9525517/algodat/algo_250304_2a_2.png)
(gelb: Zwischenschritte, rote Pfeilmarkierungen: Unterschiede)
oder lieg ich ganz falsch? :shinner:
thx in advance,
alpi 8)
edit: oder sind beide in Ordnung? ;)
edit2: wenn wer Lust hat sich am Wochenende gemeinsam an die Ausarbeitung der Prüfungen zu machen -> mail an alpi (at) gmx.at
hallo,
war in der letzten Vo-Einheit anwesend. Schikuta hat gemeint es kommen nur die folien, die er auch gemacht hat. Da ich nicht immer anwesend war, weiss ich leider nicht, welche Folien er ausgelassen hat.
Weiss das jemand?
Danke
welche Folien hat er denn in der letzten VO gemacht? ist er ganz durchgekommen mit dem Stoff (also inkl. Graphen und Optimierungsalgorithmen)?
welche Folien hat er denn in der letzten VO gemacht? ist er ganz durchgekommen mit dem Stoff (also inkl. Graphen und Optimierungsalgorithmen)?
wir sind bis folie 444 (die wolf-kohl-ziege-bauer gschichte) gekommen => kapitel 6.6 und der rest kommt nimma zur prüfung (für alle termine!) :thumb:
eine frage hätt' ich auch noch: hat irgendwer ein bespiel mit einem b-baum der ordnung 1 gelöst (das, was im vader nicht funktioniert) - ich steh da irgendwie auf der leitung! :confused:
danke schon mal
jeannie
Die letzte Folie, die der Schikuta gemacht hat, war die Traversierung. Ab Kapitel 6.6 kommt also nichts mehr zum Test.
@Stoff: danke für die Info ;)
@2-3-4 - Baum: Kann es sein das es zu den 2-3-4 Bäumen mehrere richtige Lösungen geben kann? theoretisch wäre ja auch 359(Wurzel), 12, 4, 678, 1011 eine richtige Lösung, oder? :confused:
ein Applet dazu gibts auf http://www.cs.unm.edu/~rlpm/499/ttft.html
@VADer: hab den erst gestern zufällig während dem Elfmeterkrimi zwischen Schweden und Holland gefunden! :D also hier der Link für die dies nicht kennen/haben: http://www.pri.univie.ac.at/~schiki/unterlagen/vader/vader.zip
@B+ - Baum der Ordnung 1: guck ich mir mal heute oder morgen abend an.. mal schaun ob ich was check :)
@Heap: was ist mit informelle Ableitung zu den Aufwänden in O-Notation gemeint? (010703 A5d bzw. 250304 5c)
@Tries: hat wer einen Pseudocode eines Algorithmus zur Suche aller gespeicherten Strings im Trie, die mit einem gegebenen Teilstring (Präfix) beginnen? (010703 A4 bzw. 250304 4)
cya,
alpi 8)
@Stoff: danke für die Info ;)
@Heap: was ist mit informelle Ableitung zu den Aufwänden in O-Notation gemeint? (010703 A5d bzw. 250304 5c)
cya,
alpi 8)
zugriff auf minmum O(1) weil minimum in der wurzel gespeichert ist
einfügen: O(log n) weil in der blattebene eingefügt wird und bis dorthin log n schritte erforderlich sind + wiederherstellen der heap-bedingung auch maximal log n mal stattfindet -> 2*log n => O(log n)
löschen: O(log n) weil suchen des zu löschenden elements max log n schritte und wiederherstellen der heap-bed. auch ... s.o.
soweit meine "informelle" lösung (ich hoff der schikuta sieht' such so)
hat sich schon jemand damit beschäftigt, welche vorteile ein de la Briandais Trie gegenüber einems Patricia Trie hat :confused:
o.k. mit ein bissi nachlesen und nachdenken bin ich selber draufgekommen: wenn ich richtig liege braucht der 2. bei k buchstaben in jedem knoten eine k+1 tabelle (egal wieviele dann tatsächlich drin sind) während der 1. nur tatsächlich vorkommende buchstaben speichert, also weniger speicherplatz; kann erweitert werden -> dynamisch
jetzt hätt ich noch eine frage, zu der ich wirklich nix im skriptum gefunden habe: geben sie für jeden der sortierverfahren (bubble, quick, bucket) eine situation in der praxis an, in der es sinnvoll ist, gerade ihn einzusetzen.
[aufgabe 3d vom 1.7.03]
... jetzt mal abgesehen davon, dass es die aufgebenstellung verlangt ...
jetzt hätt ich noch eine frage, zu der ich wirklich nix im skriptum gefunden habe: geben sie für jeden der sortierverfahren (bubble, quick, bucket) eine situation in der praxis an, in der es sinnvoll ist, gerade ihn einzusetzen.
[aufgabe 3d vom 1.7.03]
... jetzt mal abgesehen davon, dass es die aufgebenstellung verlangt ...
echt gute Frage :D
Quicksort: schwer zu sagen, wird zwar zB bei der Sortierfunktion in Java afaik verwendet, aber ein besseres Beispiel aus der Praxis muss doch zu finden sein.. :)
BucketSort: ist zB gut geeignet um eine Adressliste aus dem Adressbuch nach Postleitzahlen zu ordnen
Bubblesort: Anwendung innerhalb effizienterer Sortieralgorithmen wie QuickSort oder MergeSort. Jene Algorithmen, die die zu sortierenden Daten rekursiv unterteilen, sind beim Sortieren kleiner Reihen ineffizient. Bubblesort wird dann eingesetzt, wenn die unterteilte Datenmenge eine gewisse Grenze unterschritten hat. Quelle (http://www.net-lexikon.de/BubbleSort.html)
oder Bubblesort folgt einem so einleuchtenden Mechanismus, daß der Algorithmus oft aus Zeitmangel (oder Ungeduld) gewählt wird :D Quelle (http://www.cs.fhm.edu/~schieder/programmieren-1-ws95-96/sortieralgorithmen.html)
cya,
alpi 8)
B+ - Baum der Ordnung 1:
edit: ich glaub ich hab gleich am Anfang einen Fehler.. also alles nochmal.. brb :D
B+ - Baum der Ordnung 1:
hmm echt mühsam mit der Ordnung 1(!)..
hab zwar einen Lösungsvorschlag, bin mir aber nicht sicher obs passt; vorallem beim letzten Schritt (kann man Grenzen einfach ändern? - würde einiges vereinfachen :D)
Teil1 (http://stud3.tuwien.ac.at/~e9525517/algodat/bplus2_1.png) Teil2 (http://stud3.tuwien.ac.at/~e9525517/algodat/bplus2_2.png) Teil3 (http://stud3.tuwien.ac.at/~e9525517/algodat/bplus2_3.png)
Bitte um Feedback..
cya,
alpi 8)
hmmm, einmal tust du beim splitten vom knoten ins neue linke blatt einen wert rein und ins rechte blatt 2 werte rein (3-5-8 -> 3 5-8), und dann wieder beim nächsten split gerade umgekehrt (5-6-8 -> 5-6 8). Prinzipiell ist ja nichts einzuwenden dagegen, nur dass halt der algorithmus von einem programm ja immer gleich vorgehen sollte... denk ich mal so (zb bei split linker knoten immer 2 werte, rechter knoten einen wert).
Sollte man nun drauf achten oder nicht?
und der letzte schritt von dir scheint falsch zu sein:
du musst 8-9-10 splitten -> 9er kommt rauf
dann entsteht einen knoten weiter oben 8-9-10 -> muss wieder gesplitet werden -> 9er kommt in die wurzel rauf -> wurzel=7-9
ups, und noch eine frage:
muss man bei der prüfung auch so viele einzelschritte angeben... da wird man ja kaum fertig mit dem schreiben
hmmm, einmal tust du beim splitten vom knoten ins neue linke blatt einen wert rein und ins rechte blatt 2 werte rein (3-5-8 -> 3 5-8), und dann wieder beim nächsten split gerade umgekehrt (5-6-8 -> 5-6 8). Prinzipiell ist ja nichts einzuwenden dagegen, nur dass halt der algorithmus von einem programm ja immer gleich vorgehen sollte... denk ich mal so (zb bei split linker knoten immer 2 werte, rechter knoten einen wert).
Sollte man nun drauf achten oder nicht?
keine Ahnung, kann aber nicht schaden, stimmt...
und der letzte schritt von dir scheint falsch zu sein:
du musst 8-9-10 splitten -> 9er kommt rauf
dann entsteht einen knoten weiter oben 8-9-10 -> muss wieder gesplitet werden -> 9er kommt in die wurzel rauf -> wurzel=7-9
hmm, muß ich mir später mal genauer anschauen.. ganz klar es mir noch nicht :confused:
ups, und noch eine frage:
muss man bei der prüfung auch so viele einzelschritte angeben... da wird man ja kaum fertig mit dem schreiben
ich hoffe nicht! :D
kann jemand einen Lösungsvorschlag zu den rekursiven Programmen posten? (Rekurrenzgleichung, asymptotisches Laufzeitverhalten und zyklomatische Komplexität) ;)
cya,
alpi 8)
B+ - Baum der Ordnung 1:
hmm echt mühsam mit der Ordnung 1(!)..
hab zwar einen Lösungsvorschlag, bin mir aber nicht sicher obs passt; vorallem beim letzten Schritt (kann man Grenzen einfach ändern? - würde einiges vereinfachen :D)
Teil1 (http://stud3.tuwien.ac.at/~e9525517/algodat/bplus2_1.png) Teil2 (http://stud3.tuwien.ac.at/~e9525517/algodat/bplus2_2.png) Teil3 (http://stud3.tuwien.ac.at/~e9525517/algodat/bplus2_3.png)
Bitte um Feedback..
cya,
alpi 8)
zum teil 2: einfügen von 1 (2. baum): sollte in dem knoten 1|5 nicht eher 3|5 stehen?
zum teil 2: einfügen von 1 (2. baum): sollte in dem knoten 1|5 nicht eher 3|5 stehen?
yeap.. wenn ich nachher noch 2 einfüge passts ja erst wieder nicht :)
cya,
alpi 8)
ich fang jetzt zum lernen an...
hab die prüfung beim schikuta schon mal gemacht...
ist das skriptum brauchbar?
wer war von euch in der vorlesung? bzw. sind noch immer alle kapitel aus den folien im stoffgebiet?
ups, und noch eine frage:
muss man bei der prüfung auch so viele einzelschritte angeben... da wird man ja kaum fertig mit dem schreiben
naja fertig wird man schon; kannst auch ab und zu was auslassen
also wegen der zeit braucht man sich nicht viele sorgen machen, aber es ist eine der wenigen prüfungen wo man sie auch wirklich fast komplett ausnutzt
übrigens; falls jemand noch nicht geschaut hat:
da gibts auch recht gute zusammenfassungen:
http://mitaub.sourceforge.net/tst/html/modules.php?name=Downloads&d_op=viewdownload&cid=35&min=0&orderby=titleA&show=10
sind Unterlagen eigentlich erlaubt?
sind Unterlagen eigentlich erlaubt?
nein leider ohne Unterlagen :)
@Skriptum: naja, hab mir mehr erwartet.. so kommt man sicher auch mit der URL http://www.pri.univie.ac.at/~schiki/unterlagen/GAlgoDat/ , gemeinsam mit anderer Lektüre aus..
cya,
alpi 8)
Wulfgang
29-06-2004, 23:05
Angabe vom 25.03.04:
1/a)
Rekurrenzgleichung:
T(n) = T1 + T2 + T3 + T(n/4) + T(n/4) + T4
T(n) = T1 + T2 + T3 + 2*T(n/4) + T4
T(n) = 2+T(n/4) + 1 => O(log n)
Laufzeitverhalten:
T(n) = 2*T(n/4)+1
a=2, b=4, C=0 eingesetzt in die Gleichung aus Folie 93 ergib sich:
Fall 1 c<logb a => T(n) = Ot(n^logb a)
1/d)
Es gibt 2 möglich Pfade für das Programm:
Graph hat 6 Knoten und 6 Kanten: 6-6+2 = 2
und es gibt nur 1 Bedingung: 1+1 = 2
=> Magische Zahl = 2 und 2<5 => leichtes Programm
Hoffe meine Lösungen stimmten, bitte um Rückmeldung
Graphen sind nicht mehr Prüfungsstoff?
Graphen sind nicht mehr Prüfungsstoff?
doch bis 6.6 (also bis einschließlich Folie 445)
Wie würdet ihr das beantworten?
c. [0.4] Erläutern Sie, warum die algorithmische Lücke beim Sortieren basierend auf Elementvergleichen geschlossen ist.
Bzw. wie würdet ihr die algorithmische Lücke selbst mit euren Worten beschreiben?
b. [0.4] Definieren Sie die Begriffe Ω(n) und Θ(n) bei der Laufzeitabschätzung eines Programms?
Wulfgang
30-06-2004, 11:38
Wie würdet ihr das beantworten?
c. [0.4] Erläutern Sie, warum die algorithmische Lücke beim Sortieren basierend auf Elementvergleichen geschlossen ist.
Bzw. wie würdet ihr die algorithmische Lücke selbst mit euren Worten beschreiben?
Die Lücke ist geschlossen, da das Problem das man beim händischen Sortieren hat gleich dem implementierten Problem entspricht. D.h. wenn ich die Folge mit der Hand sortiere kommte ich auf die gleiche Laufzeit, als wenn ich die Folge mit einem Algorithmus sortiere => Ω(P) = O(A)
b. [0.4] Definieren Sie die Begriffe Ω(n) und Θ(n) bei der Laufzeitabschätzung eines Programms?
es gibt 2 Konstanten c0 und n0 so dass gilt: Ω(g(n)) = f(n) >= c0*g(n) für alle n > n0. Gibt eine untere Schranke für das Laufzeitverhalten an.
O(g(n)) = f(n) <= c0*g(n) für alle n > n0, gibt eine obere Schranke für das Laufzeitverhalten der Funktion.
O(n) = Ω(n) => Θ(n) beschreibt das Laufzeitverhalten exakt.
[/QUOTE]
Angabe vom 25.03.04:
1/a)
Rekurrenzgleichung:
T(n) = T1 + T2 + T3 + T(n/4) + T(n/4) + T4
T(n) = T1 + T2 + T3 + 2*T(n/4) + T4
T(n) = 2+T(n/4) + 1 => O(log n)
bei der 3. Zeile hab ich T(n)=2*T(n/4)+1 => T(n)=4*n= O(n) :confused:
Laufzeitverhalten:
T(n) = 2*T(n/4)+1
a=2, b=4, C=0 eingesetzt in die Gleichung aus Folie 93 ergib sich:
Fall 1 c<logb a => T(n) = Ot(n^logb a)
das hab ich auch: Fall1, da 0<0,5 => T(n)=-O(n^(log4 2))=-O(1/n^2)
1/d)
Es gibt 2 möglich Pfade für das Programm:
Graph hat 6 Knoten und 6 Kanten: 6-6+2 = 2
und es gibt nur 1 Bedingung: 1+1 = 2
=> Magische Zahl = 2 und 2<5 => leichtes Programm
Hoffe meine Lösungen stimmten, bitte um Rückmeldung
beim Programmgraph hatte sich bei mir ein Fehler eingeschlichen, komm jetzt aber auch auf eine magische Zahl (2)
cya,
alpi 8)
Wulfgang
30-06-2004, 13:09
bei der 3. Zeile hab ich T(n)=2*T(n/4)+1 => T(n)=4*n= O(n) :confused:
statt + gehört bei mir auch *, 1. wie kommst du auf 4n, ist ein wenig viel für einen rekursiven Algorithmus der nicht einmal n-mal durchlaufen wird. Ich hab den Algo in java implementiert, der Algo wird auf keinen Fall n-mal durchlaufen.
Auf O(log n) komme ich, da man konstate Faktoren wie 2 weglassen soll.
statt + gehört bei mir auch *, 1. wie kommst du auf 4n, ist ein wenig viel für einen rekursiven Algorithmus der nicht einmal n-mal durchlaufen wird. Ich hab den Algo in java implementiert, der Algo wird auf keinen Fall n-mal durchlaufen.
Auf O(log n) komme ich, da man konstate Faktoren wie 2 weglassen soll.
thx, ist mir nun etwas klarer ;)
eine Frage zu den Programmgraphen: was sind die mag. Zahlen bei 010703 A1 und 010703 B3? (3?)
thx enstweilen...
hätte noch eine Frage:
c. [0.5] Beschreiben Sie die Eigenschaften eines 2-3-4 Baumes.
bzw. was zeichnet den 2-3-4 Baum aus?
finde das in den Folien nicht...
thx enstweilen...
hätte noch eine Frage:
c. [0.5] Beschreiben Sie die Eigenschaften eines 2-3-4 Baumes.
bzw. was zeichnet den 2-3-4 Baum aus?
finde das in den Folien nicht...
she. Folien 230 + 239 ;)
andere Formulierung: Suchbäume, deren Knoten aus 2, 3 und 4 "Kinder-Knoten" bestehen und deren Blätter alle auf einer Ebene liegen.
VT:2-3-4 Bäume sind immer optimal balanciert -> effiziente Suche
NT:hoher Aufwand für Löschen und Einfügen
typische Verwendung: Hintergrundspeicherverwaltung
hmm, bräuchte kurz mal eure hilfe
wie zeichnet man so einen programmgraphen?
B+ - Baum der Ordnung 1:
hmm echt mühsam mit der Ordnung 1(!)..
hab zwar einen Lösungsvorschlag, bin mir aber nicht sicher obs passt; vorallem beim letzten Schritt (kann man Grenzen einfach ändern? - würde einiges vereinfachen :D)
Teil1 (http://stud3.tuwien.ac.at/~e9525517/algodat/bplus2_1.png) Teil2 (http://stud3.tuwien.ac.at/~e9525517/algodat/bplus2_2.png) Teil3 (http://stud3.tuwien.ac.at/~e9525517/algodat/bplus2_3.png)
Bitte um Feedback..
cya,
alpi 8)
Sollte nicht immer der Mittelwert bei jedem Überlauf rauf wandern? Daran hältst du dich da nämlich eigentlich nicht...
Hab da folgenden Artikel im Internet gefunden:
Kommt es hingegen im betreffenden Knoten zu einem „Überlauf“, d.h. er würde mehr als 2n Einträge enthalten, so fügt man den neuen Schlüssel erst einmal „virtuell“ ein, d.h. man erweitert den Knoten um einen neuen Eintrag, und fügt dann den neuen Schlüssel ein, wobei man die Größe der Schlüssel berücksichtigen muss. Anschließend bestimmt man den Eintrag in der Mitte des virtuellen Knotens. Der Knoten wird gespalten, wobei die Schlüssel, die links vom mittleren Schlüssel liegen in einen neuen linken Knoten eingetragen werden; die Einträge, die rechts vom „Mittelwert“ liegen, werden in einen neuen rechten Knoten eingetragen; aus einem Knoten wurden somit zwei, die beide wieder alle Eigenschaften eines B-Baums erfüllen und mit n Einträgen gefüllt sind. Der vorgenannte mittlere Eintrag wird in den Vaterknoten (der Knoten, der sich eine Ebene über dem virtuellen Knoten befindet) verschoben. Sollte dieser eine Ebene höher gelegene Knoten nun aber ebenfalls voll sein, so wird auch er nach der genannten Regel geteilt. Dieses Verfahren wird nun unter Umständen solange durchgeführt bis man an der Wurzel angelangt ist.
Sollte nicht immer der Mittelwert bei jedem Überlauf rauf wandern? Daran hältst du dich da nämlich eigentlich nicht...
Hab da folgenden Artikel im Internet gefunden:
Kommt es hingegen im betreffenden Knoten zu einem „Überlauf“, d.h. er würde mehr als 2n Einträge enthalten, so fügt man den neuen Schlüssel erst einmal „virtuell“ ein, d.h. man erweitert den Knoten um einen neuen Eintrag, und fügt dann den neuen Schlüssel ein, wobei man die Größe der Schlüssel berücksichtigen muss. Anschließend bestimmt man den Eintrag in der Mitte des virtuellen Knotens. Der Knoten wird gespalten, wobei die Schlüssel, die links vom mittleren Schlüssel liegen in einen neuen linken Knoten eingetragen werden; die Einträge, die rechts vom „Mittelwert“ liegen, werden in einen neuen rechten Knoten eingetragen; aus einem Knoten wurden somit zwei, die beide wieder alle Eigenschaften eines B-Baums erfüllen und mit n Einträgen gefüllt sind. Der vorgenannte mittlere Eintrag wird in den Vaterknoten (der Knoten, der sich eine Ebene über dem virtuellen Knoten befindet) verschoben. Sollte dieser eine Ebene höher gelegene Knoten nun aber ebenfalls voll sein, so wird auch er nach der genannten Regel geteilt. Dieses Verfahren wird nun unter Umständen solange durchgeführt bis man an der Wurzel angelangt ist.
sorry die Dateien sind nicht mehr ganz up2date, aber du hast Recht.. ich hoffe es kommt wirklich ein B+-Baum der Ordnung 1.. würd mich echt freuen :D
cya,
alpi 8)
P.S.: wenn man sich strikt an ein System hält, dann ist das ganze keine Kunst mehr.
meine Lsg (hoffe sie stimmt):
5/8
3/- 7/- 9/10
1/2 3/4 6/- 7/- 8/- 9/- 10/11
Viel Glück bei der Prüfung auf alle Fälle, wird schon schief gehn...
Hab die ganze Nacht durchgelern und noch nix gepennt :)
Jaja, weil man auch immer zu spät zum Lernen anfangen muss...
wünsch auch allen viel Glück... wird schon schiefgehen :shinner:
cya,
alpi 8)
vBulletin® v3.7.1, Copyright ©2000-2009, Jelsoft Enterprises Ltd.