TU Wien:Diskrete Mathematik für Informatik VO (Drmota)/Prüfung 03.02.2015

1.a. Sei $(a_{n})$ die durch $A(x)$ generierte Folge. Geben sie die $B(x),C(x)$ an, wobei $b_{n}=\sum _{k=0}^{n}a_{k}$ und $c_{n}=na_{n}$.

1.b. Geben Sie $D(z)$ für die Rekursion $d_{n}=1+\sum _{k=0}^{n}d_{k}(n-k)$ an.

2. Geben sie die die Möbiusfunktion $\mu (0,1)$ für folgende Halbordnung an: $R=\{(0,a),(0,b),(a,c),(b,d),(a,d),(b,c),(c,1),(d,1)\}$ Geben Sie $\mu (0,1)$ für $R\backslash \{(a,d),(b,c)\}$ an.

3. Berechnen Sie den maximalen Flow mittels augmenting Paths. Ändert sich der maximale Flow wenn man Kante X löscht?

Graph (aus dem Gedächtnis): $V=\{s,a,b,c,d,t\}$, $E=\{(s,a,3),(s,b,2),(a,c,1),(a,b,2),(b,d,5),(d,t,3),(d,c,1),(c,t,4),(d,t,3)\}$.

4.a. Welche Polynome sind irreduzibel in $\mathbb {Z} _{3}$?

$x^{3}+x+1$

$x^{2}+2x+1$

4.b. Lösen Sie folgendes Gleichungssystem:

$y^{3}\equiv 1\mod 3$

$12y\equiv 9\mod 15$

Hinweis: bringen Sie das System zuerst in die Form $a_{i}y\equiv b_{i}\mod m_{i}$.

Hinweis

Auf der Angabe waren die Halbordnung und der Graph für den max. Flow natürlich aufgezeichnet.