Heute am 25. Jänner 2013 war zum ersten Mal eine schriftliche Prüfung vom Drmota. Wir wurden mit folgenden Beispielen überrascht:
1. Vereinfachen Sie folgende Summen zu einer geschlossenen Form: ,
2. Eine Permutation der Zahlen heißt 3-sortiert, wenn , , und . Bestimmen Sie die Anzahl solcher Permutationen. Geben Sie auch die Asymptotik mit der Stirling'schen Formel an!
3. Finden Sie einen Quicksort-ähnlichen Algorithmus der aus einer Permutation der Zahlen die M kleinsten Zahlen auswählt. Sei die erwartete Anzahl der Operationen (Ausgaben und Vergleiche) unter dem Random-Permutation-Model. Zeigen Sie, dass folgende Rekursion erfüllt: , mit den Anfangswerten und für . Lösen Sie diese Rekursion für !
4. Ein kubenfreies Polynom ist ein Polynom, dass keine echten Teiler der Form hat (mit ). Zeigen Sie folgende Eigenschaften: Jedes normierte Polynom lässt sich eindeutig in der Form mit kubenfrei darstellen. Die erzeugende Funktion der normierten kubenfreien Polynome ist . Bestimmen sie die Anzahl der normierten kubenfreien Polynome vom Grad n.
Hatte heute das Vergnügen! Soweit ichs noch im Kopf hab, die Angabe:
Bsp 1: siehe Bsp 1 ein Post weiter oben (zwei Summen)
Bsp 2: siehe Bsp 2 ein Post weiter oben (3-sorteirt)
Bsp 3: Eine Komposition einer natürlichen Zahl , ist die Zerlegung von in eine Summe von natürichen Zahlen. Es bezeichne die Anzahl aller möglichen Kompositionen von , wobei die Reihenfolge berücksichtigt wird, und Wiederholungen erlaubt sind. Zeigen Sie für die wkerzeugende Funktion die Gleichung
Berechnen Sie damit . (mein Ergebniss war hier glaub ich ) Bezeichne die Anzahl an Summanden einer (zufällig) gewählten Komposition $n$. Begründen Sie die Gleichung (ich hoffe die stimmt so circa)
und berechnen Sie den Erwartungswert von . (mein Ergebniss war hier )
Bsp 4: TRIES Kann mich hier nicht mehr genau an die Angabe erinnern, da ich mich selbst nicht lang mit den Bsp auseinandergesetzt habe bei der Prüfung. Irgendwas sollte man, "analog zur Vorlesung" berechnen, glaube die erwartete Linkspfadlänge, oder irgendsowas.
b) Zeige (z.B. mittels vollständiger Induktion nach n) dass für 0 ≤ m ≤ n:
(Hoffe dass das so stimmt)
Bsp 2: 3-sortierte Permutation (genau dasselbe wie bei den anderen beiden Prüfungen)
Bsp 3: Wie bei der 2. Prüfung: Man sollte bei den TRIES die erwartete Linkspfadlänge bestimmen (d.h. Länge des Pfades wenn man von der Wurzel aus immer den linken Zweig nimmt)
Prüfung vom 2.2.2016, Sehr viele Sachen haben sich wiederholt, ich kopiere diese einfach aus den vorherigen Postings.
Bsp 1: a) Vereinfache folgende Summe:
b) Zeige (z.B. mittels vollständiger Induktion nach n) dass für 0 ≤ m ≤ n:
(Hoffe dass das so stimmt)
Bsp 2a) war neu, man musste das asymptotische Verhalten von
für d = 0,1,2 bestimmen. Bsp 2b) waren die dreisortierten Permutationen, allerdings war dieses Mal nur die Anzahl der zweisortieren Permutationen zu bestimmen.
Bsp 3 war das Suchen der M kleinsten Zahlen mit einem Quicksort-artigen Algorithmus, dieses Mal allerdings mit den Daten in einem binären Suchbaum, und man musste die Daten mit x <= M, wobei M gegeben war finden. Der Rest gleich wie aus dem bereits erwähnten Beispiel.
4. Ein kubenfreies Polynom ist ein Polynom, dass keine echten Teiler der Form hat (mit ). Zeigen Sie folgende Eigenschaften: Jedes normierte Polynom lässt sich eindeutig in der Form mit kubenfrei darstellen. Die erzeugende Funktion der normierten kubenfreien Polynome ist . Bestimmen sie die Anzahl der normierten kubenfreien Polynome vom Grad n.
LG Felix
Mi 03-02-2016 09:42:23
maddin
Registriert: 10/2010 Beiträge: 24
Re: Schriftliche Prüfung Drmota
04.03.2016:
1. 2 Summen von oben 2. 3-sortiert 3. Komposition Natürlicher Zahlen. Soweit ich mich erinnere, war die Formel:
4. Linkspfadlänge von TRIES. Gemeint ist aber, dass man die Pfade zu allen Daten hernimmt, davon aber nur die Linkskanten mitzählt.
Easy Points!
So 06-03-2016 12:19:45
Haeger
Registriert: 11/2008 Beiträge: 22+3
Re: Schriftliche Prüfung Drmota
Zitat:
4. Linkspfadlänge von TRIES. Gemeint ist aber, dass man die Pfade zu allen Daten hernimmt, davon aber nur die Linkskanten mitzählt.
Hat jemand einen Ansatz für das Beispiel?
Do 21-04-2016 12:34:57
ajdani
Registriert: 10/2010 Beiträge: 25+26
Re: Schriftliche Prüfung Drmota
Prüfung vom 25.11.2016: 1) a)
1) b)
2) Komposition einer natürlichen Zahl
3) war das Suchen der M kleinsten Zahlen mit einem Quicksort-artigen Algorithmus, dieses Mal allerdings mit den Daten in einem binären Suchbaum, und man musste die Daten mit x <= M, wobei M gegeben war finden. Der Rest gleich wie aus dem bereits erwähnten Beispiel.
4) wie die kubenfreien Polynome, nur in diesem Fall alles für nullstellenfreie Polynome (also a), b) und c))
Sa 26-11-2016 12:14:29
Belko
Registriert: 10/2012 Beiträge: 25+14
Studium: anderes Studium
Re: Schriftliche Prüfung Drmota
1) a) Beweis einer Identität für die harmonische Zahlen b) Damit dann eine Gleichung für die Zeta beweisen
2) die 2 sortierten Permutation
3) Couponsammelproblem a) WS für p_{n}{k}, dass beim k-ten Ziehen, das 1. Bildchen doppelt vorkommt. b) Erwartungswert berechnen für wann das 1. doppelte Bildchen gezogen wird.
Ich hatte heute die Ehre. Die Beispiele waren: 1) Mittels Induktion eine Identität für die verallgemeinerten Harmonischen Summen zu zeigen und daraus eine Formel für die Zeta-Funktion zu berechnen. 2) 2-sortierte Permutationen 3) Coupon-Collector-Problem: Wahrscheinlichkeit, dass man nach genau k Zügen das erste mal ein Sticker doppelt hat bestimmen und daraus das Geburtsparadoxon lösen. Es war sehr viel Anleitung inkludiert und daher waren die Resultate auch relativ einfach zu bestimmen. 4) Linkspfadlänge bei Tries
Ich hatte am 2. Oktober 2020 Prüfung. Diesmal kam wieder: 1) a) 1) b) 2) a) Die oben schon erwähnen Summen S_d, für die man für d=0,1,2 die Asymptomatik angeben muss. 2) b) Das Permutationenbeispiel war diesmal leicht anders: Die Anzahl von Permutationen auf {1, ..., 2n} angeben mit der Eigenschaft, dass a_1 < a_2, a_3 < a_4, ect. 3) war das Suchen der M kleinsten Zahlen mit einem Quicksort-artigen Algorithmus, dieses Mal allerdings mit den Daten in einem binären Suchbaum, und man musste die Daten mit x <= M, wobei M gegeben war finden. Der Rest gleich wie aus dem bereits erwähnten Beispiel.
Prüfung vom 26.01.2022: 1) die beiden Summen aus dem vorigen Beitrag
2) Komposition natürlicher Zahlen
3) Quicksortartiger Algorithmus für das Auffinden der kleinsten M Elemente in einem binären Suchbaum
4) Nullstellenfreie Polynome über F_q: a) Jedes normierte Polynom f über F_q lässt sich eindeutig darstellen als f = g h, wobei g über F_q in Linearfaktoren zerfällt und h normiert und nullstellenfrei ist b) Sei N(x) die erzeugende Funktion der nullstellenfreien, normierten Polynome. Zeige
und begründe insbesondere, dass I_1 = q.
c) Bestimme explizit oder asymptotisch die Anzahl a_n^{(0)} der normierten nullstellenfreien Polynome vom Grad n.
Mitglieder in diesem Forum: 0 Mitglieder und 0 Gäste
Du darfst neue Themen in diesem Forum erstellen. Du darfst Antworten zu Themen in diesem Forum erstellen. Du darfst deine Beiträge in diesem Forum nicht ändern. Du darfst deine Beiträge in diesem Forum nicht löschen. Du darfst keine Dateianhänge in diesem Forum erstellen.