Wenn A Erfolg bezeichnet ist, dann gilt die Formel: A = X + Y + Z.
X ist Arbeit. Y ist Spiel. Z ist Mund halten.
Albert Einstein


Auf das Thema antworten  [ 10 Beiträge ] 
Schriftliche Prüfung Drmota 
Autor Nachricht

Registriert: 04/2008
Beiträge: 25 + 22
Mit Zitat antworten
Beitrag Schriftliche Prüfung Drmota
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: $S_1 = \sum_{k=1}^n kH_k$, $S_2 = \sum_{k=2}^n \frac{H_k}{k(k-1)}$

2. Eine Permutation $a$ der Zahlen $\{1,2,\dots,3n\}$ heißt 3-sortiert, wenn $a_1 < a_4 < \dots < a_{3n-2}$, $a_2 < a_5 < \dots < a_{3n-1}$, und $a_3 < a_6 < \dots < a_{3n}$. Bestimmen Sie die Anzahl $T_n$ 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 $\{1,2,\dots,n\}$ die M kleinsten Zahlen auswählt. Sei $E_{n,M}$ die erwartete Anzahl der Operationen (Ausgaben und Vergleiche) unter dem Random-Permutation-Model. Zeigen Sie, dass $E_{n,M}$ folgende Rekursion erfüllt:
$$E_{n,M} = 1 + \frac 1 n \frac{M(M+1)}2 + \frac 1 n \sum_{k=1}^{M} E_{n-k,M-k} + \frac 1 n \sum_{k=M+1}^n E_{k-1,M}$$, mit den Anfangswerten $E_{n,0} = E_{0,M} = 0$ und $E_{n,M} = 0$ für $M \geq n$.
Lösen Sie diese Rekursion für $M=1$!

4. Ein kubenfreies Polynom $f \in \mathbb{F}_q$ ist ein Polynom, dass keine echten Teiler der Form $g^3$ hat (mit $\mathrm{grad}\; g > 0$). Zeigen Sie folgende Eigenschaften:
Jedes normierte Polynom lässt sich eindeutig in der Form $f = g^3 h$ mit $h$ kubenfrei darstellen.
Die erzeugende Funktion der normierten kubenfreien Polynome ist $$Q(x) = \frac{1-qx^3}{1-qx} = \prod_{k\geq 1} (1 + x^k + x^{2k})^{I_k}$$.
Bestimmen sie die Anzahl $a^{(3)}_n$ der normierten kubenfreien Polynome vom Grad n.

Gabriel.


Fr 25-01-2013 16:26:47
Diesen Beitrag melden
Profil

Registriert: 10/2007
Beiträge: 29 + 19
Wohnort: Mödling
Mit Zitat antworten
Beitrag Re: Schriftliche Prüfung Drmota
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 $n\geq 0$, ist die Zerlegung von $n$ in eine Summe von natürichen Zahlen. Es bezeichne $c_n$ die Anzahl aller möglichen Kompositionen von $n$, wobei die Reihenfolge berücksichtigt wird, und Wiederholungen erlaubt sind. Zeigen Sie für die wkerzeugende Funktion $C(x)$ die Gleichung
\[
C(x) = \frac{\frac{x}{1-x}}{1 - \frac{x}{1-x} }
\]
Berechnen Sie damit $c_n$. (mein Ergebniss war hier glaub ich $c_n= 2^{n-1}$)
Bezeichne $X_n$ die Anzahl an Summanden einer (zufällig) gewählten Komposition $n$. Begründen Sie die Gleichung (ich hoffe die stimmt so circa)
\[
C(x,u) = \sum c_n \mathbb{E}(u^{X_n}) x^n =  \frac{\frac{x}{1-ux}}{1 - \frac{x}{1-ux}}
\]
und berechnen Sie den Erwartungswert von $X_n$. (mein Ergebniss war hier $\frac{n+1}{2}$)

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.


liebe Grüße


Fr 24-01-2014 19:10:58
Diesen Beitrag melden
Profil Website besuchen

Registriert: 11/2011
Beiträge: 23 + 5
Studium: Master Technische Mathematik
Mit Zitat antworten
Beitrag Re: Schriftliche Prüfung Drmota
Prüfung vom Dr. Mota am 01.07.:

Bsp 1: a) Vereinfache folgende Summe:
$\sum_{k=1}^n \frac{{k}^{2}-k+5}{{k}^{2}(k+1)} $
b) Zeige (z.B. mittels vollständiger Induktion nach n) dass für 0 ≤ m ≤ n:
$\frac{1}{\binom{n}{m}}\sum_{k=1}^m \binom{n-k}{n-m} \frac{1}{k} = H_n - H_{n-m}$
(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)

Bsp 4: dasselbe bsp wie das 4. Bsp der 1. Prüfung


Mi 02-07-2014 22:06:41
Diesen Beitrag melden
Profil

Registriert: 03/2014
Beiträge: 22 + 3
Studium: Master Technische Mathematik
Mit Zitat antworten
Beitrag Re: Schriftliche Prüfung Drmota
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:
$\sum_{k=1}^n \frac{{k}^{2}-k+5}{{k}^{2}(k+1)} $
b) Zeige (z.B. mittels vollständiger Induktion nach n) dass für 0 ≤ m ≤ n:
$\frac{1}{\binom{n}{m}}\sum_{k=1}^m \binom{n-k}{n-m} \frac{1}{k} = H_n - H_{n-m}$
(Hoffe dass das so stimmt)

Bsp 2a) war neu, man musste das asymptotische Verhalten von

falsche LaTeX Formel:$ S_d = 4^{-n} \sum_{j=0}^d (-1)^d \binom{2n+1}{n-j} \binom{d}{j} $

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 $f \in \mathbb{F}_q$ist ein Polynom, dass keine echten Teiler der Form $g^3$ hat (mit $\mathrm{grad}\; g > 0$). Zeigen Sie folgende Eigenschaften:
Jedes normierte Polynom lässt sich eindeutig in der Form $f = g^3 h$ mit $h$kubenfrei darstellen.
Die erzeugende Funktion der normierten kubenfreien Polynome ist $$Q(x) = \frac{1-qx^3}{1-qx} = \prod_{k\geq 1} (1 + x^k + x^{2k})^{I_k}$$.
Bestimmen sie die Anzahl $a^{(3)}_n$ der normierten kubenfreien Polynome vom Grad n.


LG
Felix


Mi 03-02-2016 09:42:23
Diesen Beitrag melden
Profil

Registriert: 10/2010
Beiträge: 24
Mit Zitat antworten
Beitrag 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:
falsche LaTeX Formel:\[C(x,u) = \sum c_n \mathbb{E}(u^{X_n}) x^n = \frac{\frac{ux}{1-x}}{1 - \frac{ux}{1-x}}\]
TeX Font Info: Try loading font information for U+msa on input line 7.
(c:/Programme/texlive/2008/texmf-dist/tex/latex/amsfonts/umsa.fd
File: umsa.fd 2002/01/19 v2.2g AMS font definitions
)
LaTeX Font Info: Try loading font information for U+msb on input line 7.
(c:/Programme/texlive/2008/texmf-dist/tex/latex/amsfonts/umsb.fd
File: umsb.fd 2002/01/19 v2.2g AMS font definitions
)

! Package inputenc Error: Keyboard character used is undefined
(inputenc) in inputencoding `utf8'.

See the inputenc package documentation for explanation.
Type H for immediate help.
...

l.8 ^^[
nd{document}
You need to provide a definition with \DeclareInputText
or \DeclareInputMath before using this key.

)
! Emergency stop.
<*> c:/scio/temp/1313160409/_TeMpTeX_

*** (job aborted, no legal \end found)


Here is how much of TeX's memory you used:
1464 strings out of 493887
16230 string characters out of 1150439
65055 words of memory out of 3000000
4771 multiletter control sequences out of 10000+50000
5339 words of font info for 22 fonts, out of 3000000 for 5000
714 hyphenation exceptions out of 8191
27i,2n,22p,242b,83s stack positions out of 5000i,500n,10000p,200000b,50000s
No pages of output.

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
Diesen Beitrag melden
Profil

Registriert: 11/2008
Beiträge: 22 + 3
Mit Zitat antworten
Beitrag 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
Diesen Beitrag melden
Profil

Registriert: 10/2010
Beiträge: 25 + 26
Mit Zitat antworten
Beitrag Re: Schriftliche Prüfung Drmota
Prüfung vom 25.11.2016:
1) a)
$\sum_{k=1}^n \frac{{k}^{2}-k+5}{{k}^{2}(k+1)} $
1) b)
$\frac{1}{\binom{n}{m}}\sum_{k=1}^m \binom{n-k}{n-m} \frac{1}{k} = H_n - H_{n-m}$
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
Diesen Beitrag melden
Profil
Benutzeravatar

Registriert: 10/2012
Beiträge: 25 + 14
Studium: anderes Studium
Mit Zitat antworten
Beitrag 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.

4) Linkspfadlänge von TRIES.


Fr 02-03-2018 16:24:42
Diesen Beitrag melden
Profil

Registriert: 01/2019
Beiträge: 20
Studium: Bachelor Technische Mathematik
Mit Zitat antworten
Beitrag Re: Schriftliche Prüfung Drmota
Ich hatte heute die Ehre. Die Beispiele waren:
1) Mittels Induktion eine Identität für die verallgemeinerten Harmonischen Summen
falsche LaTeX Formel:$H_n^s = \sum_{k=1}^n k^{-s}$
TeX Font Info: Try loading font information for U+msa on input line 7.
(c:/Programme/texlive/2008/texmf-dist/tex/latex/amsfonts/umsa.fd
File: umsa.fd 2002/01/19 v2.2g AMS font definitions
)
LaTeX Font Info: Try loading font information for U+msb on input line 7.
(c:/Programme/texlive/2008/texmf-dist/tex/latex/amsfonts/umsb.fd
File: umsb.fd 2002/01/19 v2.2g AMS font definitions
)

! Package inputenc Error: Keyboard character used is undefined
(inputenc) in inputencoding `utf8'.

See the inputenc package documentation for explanation.
Type H for immediate help.
...

l.8 ^^[
nd{document}
You need to provide a definition with \DeclareInputText
or \DeclareInputMath before using this key.

)
! Emergency stop.
<*> c:/scio/temp/1133998314/_TeMpTeX_

*** (job aborted, no legal \end found)


Here is how much of TeX's memory you used:
1464 strings out of 493887
16230 string characters out of 1150439
65055 words of memory out of 3000000
4771 multiletter control sequences out of 10000+50000
5339 words of font info for 22 fonts, out of 3000000 for 5000
714 hyphenation exceptions out of 8191
27i,3n,22p,242b,71s stack positions out of 5000i,500n,10000p,200000b,50000s
No pages of output.
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


Fr 06-03-2020 18:34:27
Diesen Beitrag melden
Profil

Registriert: 06/2019
Beiträge: 21
Studium: Master Technische Mathematik
Mit Zitat antworten
Beitrag Re: Schriftliche Prüfung Drmota
Ich hatte am 2. Oktober 2020 Prüfung. Diesmal kam
wieder:
1) a)$\sum_{k=1}^n \frac{{k}^{2}-k+5}{{k}^{2}(k+1)} $
1) b)$\frac{1}{\binom{n}{m}}\sum_{k=1}^m \binom{n-k}{n-m} \frac{1}{k} = H_n - H_{n-m}$
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.

4) kubenfreien Polynome


Mo 05-10-2020 08:44:37
Diesen Beitrag melden
Profil
Beiträge der letzten Zeit anzeigen:  Sortiere nach  
Auf das Thema antworten   [ 10 Beiträge ] 


Wer ist online?

Mitglieder in diesem Forum: 0 Mitglieder und 1 Gast


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.

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