UE-Test

[skytale]

Hat vielleicht irgendwer eine Ahnung wie die UE-Tests in AlgoDat aussehen? Kommen da solche Beispiele wie bei den VO-Prüfungen (alte Angaben auf der HP) oder sieht es bei der UE anders aus?

[Swida]

ich schätz mal dass solche bsps wie bei den ersten beiden übungszellteln kommen werden...

weis jemand bis zu welcher seite im buch der stoff durchgenommen wurde??

[tocvolxa]

alte prüfungsunterlagen gibts auf der algodat-hp:
http://www.ads.tuwien.ac.at/teaching/LVA/AlgoDat1/altePruef/
.

[phlow]

ich denke aber eher das sind die VO Prüfungen (Abschlussprüfung) und nicht die Übungstests, oder!?

[-z0nk-]

muss man sich zu den tests anmelden ?

mfg, -z0nk-

[moose]

ich glaub nicht dass ich mich zu den tests anmelden muss, ich bin ja sowieso zur uebung angemeldet... wenn ich keinen test mach kann ich doch die uebung nicht abschliessen...

[nix_is]

tutor hat heute gemeint die beispiele sind in etwa so wie in der übung (von der länge her) und es werden so 3-4 kommen..
ob man skriptum verwenden darf weiß ich nicht...

[starlet]

es dürfen keinerlei Unterlagen verwendet werden...
so steht es auf der Seite von Algodat

[tocvolxa]

Original geschrieben von Phlow
ich denke aber eher das sind die VO Prüfungen (Abschlussprüfung) und nicht die Übungstests, oder!?

hast recht. ich hab mich vom namen der files in die irre führen lassen.
(dachte immer das "klausur" nur für übungstests verwendet wird).

[dj_m.o.h.t.]

Auf der Homepage von AlgoDat steht übrigens, welche Matrikelnummern wann und wo zu den Übungstests sein müssen.

WICHTIG: Unterlagen keine erlaubt!

[phlow]

offizielles Statement zum Übungstest, siehe: http://frost.feig.at/informatik-forum/showthread.php?s=&threadid=963

[Jimmy]

also wenn ich mal stichwortartig die Stoffgebiete notieren kann:
<Blockquote>
°Insertion Sort
°Selection Sort
°Merge Sort <k> *kotz* </k>
°Quick-Sort
°Heap-Sort
°Bubble-Sort
°Theta, Omega, O -> <k>"Zeigen oder widerlegen Sie -Beispiele"</k>
°f(n) = O(g(n) <=> g(n) =O(f(n)) - so Beispiele in die Richtung ! also WAHR - FALSCH Kreuzel Fragen (kommt laut Repet. vom 12-04)
°Laufzeit von Pseudocodes mit rekursivem Aufruf (siehe alte Prüfungen) *pfui*
°Laufzeit der Sortieralgorithmen;->Best Case, Worst Case, Avg....
°binäre Suche
°lineare Suche
°f(n) und g(n) gegeben - wir müssen ANKREUZEN ob f(n) in O(n) m, Theta(n) , und/oder Omega(n) gibt. (sowas soll bei denen auch beliebt sein - laut AlgoRep.) es können auch mehrere Lösungen geben, also das f(n) liegt in allen 3 Mengen
</blockquote>
weiters ist nur noch zu wissen, in welcher Übungsgruppegruppe man eingeteilt ist... -> Gruppennummer

fällt jemand noch was ein ? Hab ich was vergessen...?:confused:

greetz,
jim

[Kenny]

in den alten vo-prüfungen is ja oft auch notwendig, dass man die codes der verschiedenen algorithmen mehr oder weniger auswendig kann... à la geben sie einen pseudocode von blabla-sort an der das und das macht...

aber zu den ue-tests is doch ein bissi viel verlangt jeden algo auswendig pseudo-codieren zu können, da sollten die codes doch angegeben sein, wie auf den übunszetteln oder ? *hoff* ;)


-------------------
ciao, Markus
www.MWorx.at - new Pics online: "ZOOMania" & "EMERGENZA"

[Lukas]

also ich glaub nicht dass man algorithmen auswendig können muss. aber du solltest halt wissen was der algortithmus macht und so fragen wie zb. ist xy stabil beantworten können, da geben sie keinen pseudocode an (hat er gestern im repetitorium gesagt).

[eXe]

welche von den algorithmen aus dem skript sind jetz alle stabil? :)

[Jimmy]

Original geschrieben von eXe
welche von den algorithmen aus dem skript sind jetz alle stabil?

<font color="red">Nur Insertion Sort und Bubble Sort sind sicher stabil</font>.. bei Merge Sort ist es abhängig in welcher Version der Pseudocode steht. Angeblich soll es sowohl stabil als auch instabil sein..
Der Rest ist <font color=#00ff00"><b>instabil</font></b>

[tocvolxa]

selection sort müsste doch auch stabil zu machen sein?
(oder is es sogar? - ich hab das skriptum jetzt grad nicht da)
(bucket-sort und fachverteilung imho ebenfalls stb.)

[Jimmy]

Selection Sort - da gabs im alten Skriptum angeblich 2 Versionen vom Algorithmus... die version die <b>wir</b> im NEUEN haben ist instabil..
weil ja zum Bsp.
2(a),2(b),1 sortiert wird in 1,2(b),2(a) -> er vertauscht ja das erste Element mit dem letzten A[minpos] ---> instabil !
im alten Skriptum gabs ne <k>optimierte</k> Version vom Selection Sort die stabil war - laut Tutorium zumindest.
also wenn gefragt ist , ob Sel.S stabil oder instabil ist, einfach angeben ,dass dies vom Sortieralgorithmus abhängt,da es beides seien kann..

gute n8, jim

[Lukas]

selection sort ist immer instabil, im repetitorium hat er gesagt dass es zwei varianten von merge sort gibt, nicht von selection sort.

von merge sort haben wir ja in unserem skriptum auch zwei varianten, ich weiss aber nicht welche davon stabil ist.

[Jimmy]

ja genau stimmt- Upps .... na wie konnte ich sowas vergessen !! ..
Naja .. thx 2 Lukas 4 the clarification !! ich glaub ich sollt mich um die Zeit lieber schlafen legen als Postings zu machen ! :D

[tocvolxa]

@Jimmy: stimmt selection sort is instabil. hab das vertauschen vergessen.
(Allerdings sobald man eine verketterte Liste statt array verwendet kann man statt vertauschen nur einfügen - dann würde das prinzip von selection sort erhalten bleibe und stabil wärs auch. also möglich müssts schon sein)


@Lukas: der 2. Merge Sort (Seite 35) is der instabile.
weil die rechte hälfte in umgekehrter reihenfolge gespeichert wird
und dann immmre das linke element falls gleich übernommen wird
(einfach mit vier gleichen zahlen ausprobieren)

[Kenny]

bsp:

f(n) = theta wurzel ( f( n²) ) ?



und wegen den rekursiven, wie schauts mit sowas aus :

NONAME (p,q)

aufruf von noname(1,n):

falls p<q
l = floor (p+q/2;
noname (p,1)
noname (l+1, q);
for i=p....q {
print i;}


wie bestimmt ma die laufzeit von rekusriven algorithmen, zb diesem hier ?

[Shade]

wenn wir schon bei laufzeiten sind:
müssen wir die auch herleiten können,oder reicht es wenn wir die auswendig können?

[SinusDiabolicus]

also laut skriptum ist ein sortierverfahren stabil...
...wenn es so implementiert werden kann, das die Reihenfolge...
also würd ich sagen merge sort ist stabil.

[Neo]

Original geschrieben von Shade
wenn wir schon bei laufzeiten sind:
müssen wir die auch herleiten können,oder reicht es wenn wir die auswendig können?

Denke mal, dass auch das Teil des Tests sein kann, denn in den Übungsbsp. waren auch solche vorhanden.

[Shade]

hmm,das stimmt.aber ich hab hauptsächlich deshalb gefragt ,weil die herleitung von der laufzeit für rekursive algorythmen recht schwer ist.
wurde beim repititorium nicht gesagt ob man das können muss?