heute ist der Geburtstag von
Pierre-Simon Laplace (28.03.1749 - 05.03.1827)



Antwort erstellen 
Benutzername:
Betreff:
Nachrichtentext:
Gib deine Nachricht hier ein. Sie darf nicht mehr als 60000 Zeichen enthalten. 

Smilies
:D :) :( :o :shock: :? 8) :lol: :x :P :oops: :cry: :evil: :twisted: :roll: :wink: :!: :?: :idea: :arrow: :| :mrgreen:
Schriftgröße:
Tipp: Formatierungen können schnell auf den markierten Text angewandt werden.  Schriftfarbe
Optionen:
BBCode ist eingeschaltet
[img] ist eingeschaltet
[flash] ist ausgeschaltet
[url] ist eingeschaltet
Smilies sind eingeschaltet
BBCode ausschalten
Smilies ausschalten
URLs nicht automatisch verlinken
Bestätigungscode
Bestätigungscode
Bestätigungscode:
Gib den Code genau so ein, wie du ihn siehst; Groß- und Kleinschreibung wird nicht unterschieden.
   

Die letzten Beiträge des Themas - schriftliche Prüfungen 
Autor Nachricht

Mit Zitat antworten Beitrag Verfasst: Sa 29-04-2017 16:30:56
Re: schriftliche Prüfungen
schriftliche Prüfung Panholzer am 28.4.17:

1. (a) M_0 := (1 & 0 \\ 0 & 1)); M_1 := (8 & 3 \\ 3 & 0) und M_n := (8 & 3 \\ 3 & 0)^n, also die n-te Potenz dieser der Matrix M_1. Gesucht war eine Rekursionsformel für a_n, wobei a_n folgendem Eintrag in M_n entspricht: M_n = (a_n & b_n \\ c_n & d_n).
(b) Rekursionsgleichung aus Teil (a) lösen.

2. (a) Topological-Sort erklären und auf einen gegebenen Graphen anwenden.
(b) ang. "User" übergibt einen Graphen mit Zyklus, wie kann man Topological-Sort ändern - ohne Laufzeit zu verschlechtern - sodass Fehlermeldung zurückgegeben wird.

3. d-näre Heaps
(a) einen 3-nären Heap als Baum darstellen (Array stand in der Angabe, A=(20, 15, ... ))
(b) Wie würde PARENT und CHILD für d-nären Heap aussehen
(c) Wie kann man die Höhe des d-nären Heaps in Abhängigkeit von n und d angeben
(d) Implementierung von EXTRACT-MAX für d-nären Heap angeben

4. Multiplikation von Polynomen
(a) Für Cauchyprodukt die Laufzeit in Theta-Notation angeben
(b) + (c) hier waren jeweils Implementierungen gegeben deren Laufzeitverhalten man analysieren sollte. Im Teil (c) musste man auch angeben wie man die einzelnen Polynomen addieren muss um das ursprüngliche zu erhalten. (die Angabe dazu war sehr lange - eine ganze A4-Seite - das hat abgeschreckt, war aber nicht so schlimm)

In Summe gab es 40 Punkte zu erreichen - für jedes Bsp. 10.

Mit Zitat antworten Beitrag Verfasst: Fr 06-05-2016 01:56:01
Re: schriftliche Prüfungen
Prüfung vom 28.04.

1) Einen Divide-and-Conquer Algorithmus entwerfen um das maximale Element eines unimodal sortierten Arrays zu finden. Dabei heißt ein Array unimodal, wenn man es in einen aufsteigenden Teil und einen absteigenden Teil splitten kann. (Also a_1<a_2<...<a_m und a_m>a_m+1 > ... a_n)

2) Die Laufzeitanalyse für den WorstCase eines Divide and Conquer Algorithmus der die Anzahl an Inversionen eines Arrays zählt.

3) Beispiel 52 aus der Übung:
Eine alternative Moglichkeit, um einen gerichteten azyklischen Graphen G zu sortieren, ist wie
folgt: Der Algorithmus sucht einen Knoten mit Hingrad 0 in G, gibt ihn aus und entfernt ihn
aus dem Graphen. Der so veränderte Graph heiße G′. Dann wird der Algorithmus rekursiv auf
G′ angewendet. Schreiben Sie eine Pseudocode-Implementierung dieser Idee, deren Laufzeit
O(|V | + |E|) beträgt.

4) Mastertheorem mit Substitution anwenden

Mit Zitat antworten Beitrag Verfasst: Sa 06-02-2016 11:35:52
Re: schriftliche Prüfungen
Hab jetzt auch noch die schriftliche Prüfung beim Gittenberger gemacht. Leider keine Zeit gehabt, die Angabe abzuschreiben, aber sowit ich mich erinnern kann sind 4 Fragen zu je 8 Punkten gekommen:

1) Man soll einen Pseudocode schreiben, der als Input ein Polynom p und einen Auswertungspunkt x empfängt und die Auswertung p(x) mittels
a) Horner Schema
b) gewöhnlichem Einsetzen zurückgibt
Außerdem musste man den Aufwand der beiden Pseudocodes vergleichen

2) Gegeben war eine homogene, lineare Rekursion mit nichtkonstanten Koeffizienten 1.Ordnung und man sollte die allgemeine Lösung mittels Variation der Konstanten angeben. Soweit ich mich erinnern kann war die Rekursion gegeben durch:
(n+1)a_n = n*a_n-1 + (n+1)

3) Man musste anhand eines gegebenen, 9-knotigen, gewichteten Graphens miithilfe des Dijkstra Algorithmus' die kürzesten Wege von einem Ausgangsknoten zu allen anderen Knoten bestimmen (Für den Dijkstra Alg war kein Pseudocode in der Angabe gegeben, man musste also wirklich verstehen, wie er funzt).
Ferner musste man noch die notwendigen Voraussetzungen angeben, die ein Graph erfüllen muss, sodass Dijkstra einen korrekten Output liefert (Gewichtsfunktion muss nichtnegativen Wertebereich besitzen, es dürfen keine Zyklen negativen Gewichtes existieren) und beweisen, warum der Algorithmus korrekt ist.

4) a) Was ist ein Heap?
b) Gegeben war ein Pseudocode, der eine Liste empfängt und mittels Max-Heap-Insert und Heap-Increase-Key einen Max Heap zurückgibt. Zu zeigen war, dass das worst Case Laufzeitverhalten für diesen Algorithmus nlog(n) ist (was darauf hinausgelaufen ist, die worst-case Laufzeit von Heap-Increase-Key zu bestimmen)
c) Man sollte beweisen oder wiederlegen, dass Build-Max-Heap und der angegebene Pseudocode angewandt auf die gleiche Liste den selben Max-Heap erzeugen. (Gegenbesipiel war A=[1 2 3 4])

Beim Beispiel 4 waren außerdem für alle vorkommenden Codes Pseudocodes angegeben.

Mit Zitat antworten Beitrag Verfasst: Di 26-01-2016 15:37:44
Re: schriftliche Prüfungen
Ich weiß, das passt jz nicht ganz zum Thema, aber da noch keine Übungstests hier online sind, fang ich einfach mal mit meinen an:

1.Übungstest:
1) Aufwand von Rekursionen mittels Mastertheorem bestimmen
2) Eine homogene Rekursion lösen mit spezieller Inhomogenität
3) Zeigen, dass eine Folge O(n) is
4) Schubfachprinzip
5) Aufwand eiiner Rekursion mittels Rekusionsbaum Vermutung aufstellen und über Substiutionsmethode beweisen.

Alles in allem nicht allzu schwer, die Fokina verbessert auch wirklich sehr nett. Hab aber leider keine konkreten Angaben mehr. Der zweite UE Test war deutlich schwerer:

1) DFS bzw. BFS anhand eines gegebenen Graphen durchführen + DFS Wald bzw. BFS Baum aufzeichnen (war ganz einfach)

2) Ein Verkaufsautomat verfügt über unbegrenzt viele Münzen mit Nennwerten c0 < c1 < .... < ck-1 wobei c0=1 (z.B.: In der Eurozone: 1,2,5,10,20,100,200,500). Entwickeln Sie ein dynamisches Programmfür den Verkaufsautomaten, das berechnet, wie der Automat das Restgeld v ausgeben soll, indem die Anzahl der Münzen minimal ist.
Bestimmen Sie weiters das asymptotische Verhalten der Laufzeit Ihres Algorithmus.

3) Geg.: UngerichteterGraph G = (V,E) mit Gewichtsfunktion w: E -> R+; Sei T minimaler Spannbaum, S ein Baum kürzester Pfade, w'(e) := w(e) +1
a) z.z.: T ist minimaler Spannbaum für G mit zugehöriger Gewichtsfunktion w'
b) z.z.: S ist kein Baum kürzester Pfade für (G,w')

Die andere Gruppe hat noch gehabt:
Dynamische Programmierung bzw. Flussnetzwerke und maximale Flüsse

Viel Glück,
Tobini!

Mit Zitat antworten Beitrag Verfasst: Di 19-01-2016 23:49:03
Re: schriftliche Prüfungen
Hallo!

Ich würd gern die schriftliche Prüfung am 2.2. beim Prof Gittenberger machen. Da ich selbst die VO bei Prof. Ludwig gehört hab' , wärs kuhl, wenn mir jemand das Stoffgebiet sagen kann, bzw ob es irgendwo Unterlagen gibt, an die ich mich halten könnt beim Lernen!

Thx :)

Mit Zitat antworten Beitrag Verfasst: Sa 09-05-2015 15:33:32
Re: schriftliche Prüfungen
Hallo, da es sehr wenige Angaben zum Üben gibt und ich auch nur 2 auftreiben konnte werde ich diese mal zur Verfügung stellen (siehe Bilder im Anhang).

Dies sind zwei Angaben von Prof. Panholzer von Jänner 2015 und März 2015 (also recht aktuell).

Ich selbst habe die schriftliche Prüfung am 30.4.2015 gemacht und mir ca. gemerkt woraus die Angabe bestand:

1.a) Mittels Master Theorem eine Rekursion lösen und Laufzeit angeben (Anleitung im Hinweis)
1.b) Mittels Substitutionsmethode die Laufzeit von einem Algorithmus angeben
2.a) Programm RANDOM-SEARCH, mittels Anleitung am Zettel programmieren (Pseudocode)
2.b) und c) jeweils Erwartungswerte für das Ergebnis des Codes berechnen (konnte ich nicht da es in meinem Skriptum nicht vorkam)
3.a)DIJKSTRA - Algorithmus an einem Graphen durchführen und eine Tabelle mit den einzelnen Iterationsschritten ausfüllen (um zu beweisen wirklich den Algorithmus angewendet zu haben)
3.b) einen Graphen mit negativem Kantengewicht aber ohne neg. Kreis finden bei dem DIJKSTRA ein falsches Ergebnis liefern würde/liefert
4.a) Lineares Programm mittels Simplex lösen (war sogar in Standardform gegeben)
4.b) Duales Programm hinschreiben und optimale Lösung angeben

Wie ihr seht ist es sinnvoll sich vor allem Laufzeitberechnungen, Simplex und Graphenalgorithmen anzusehen. Wenn man einfache Pseudocodes schreiben kann schadet dies auch nicht.

Jede Aufgabe war bei meiner Prüfung 10 Punkte wert daher war es insgesamt möglich 40 Punkte zu erreichen. Zeit war aber lediglich 100 Minuten.

Da die mündliche Prüfung 20 Punkte abwirft darf man ab 10 Punkten zur mündlichen antreten welche bei Prof. Panholzer ebenfalls schriftlich abgehalten wird (Sammeltermin, Datum steht auf der Angabe der schriftlichen Prüfung).

Man kann also insgesamt 60 Punkte erreichen und in Summe braucht man 30 Punkte um die Prüfung positiv abzuschließen, wenn man die nicht erreicht erhält man glaube(!) ich ein negatives Zeugnis und muss nochmal bei der schriftlichen starten.

Mit Zitat antworten Beitrag Verfasst: Fr 01-03-2013 15:43:31
schriftliche Prüfungen
zu der am 1.3 ist gekommen:

simplex beispiel (inkl L_aux ausrechenen)
greedy ( Wartezeit von Kunden, Beweis das opt Teilstruk, beweisen welche Greedywahl,...)
Graham Methode ( erklären was es macht, konkrete Beispiel ausrechen)
und dann noch einen Algo überlegen, der zählt wieviele Kanten man in einen ungerichteten Graphen entfernen kann, sodass immer noch zusammenhänged

bei der Prüfung im Jänner ist gekommen (was ich so gehört hab)
Simplex
Kruskal/Prim
FFT überlegen durch 3-Teilung des Polynoms
Erwartungswert ausrechen (ähnlich sammelcouponbsp)


Gehe zu:  
cron
Powered by phpBB © phpBB Group.  |  Designed by STSoftware for PTF  |  © Czechnology 2007 - 2024  |  Deutsche Übersetzung durch phpBB.de