TU Wien:Diskrete Mathematik für Informatik VO (Drmota)/Prüfung 2015-02-03

1 Erzeugende Funktionen

a) A(z) ist bekannt, bestimme die erzeugende Funktionen für $b_{n}$ und $c_{n}$

$b_{n}=\Sigma _{k=0}^{n}a_{k}$

$c_{n}=n*a_{n}$

b) D(z)

$d_{n}=\Sigma _{k=0}^{n}d_{k}\cdot (n-k)$

2 Möbiusfunction

a) Calculate Möbiusfunction

b) Relations (c,b) and (d,a) removed, what is the new $\mu (0,1)$

3 Maximal Flow

a) Maximal Flow with Ford-Fulkerson algorithm

b) Does the maximal flow change if edge $(a,d)$ is capped.

4 Irreducible Polynoms / System of Congruences

Irreducible Polynoms over Z3

$f(x)=x^{2}+x+1$

$g(x)=x^{2}+2x+1$

System of Congruences

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

$12y\equiv 9\mod 15$