TU Wien:Diskrete Mathematik für Informatik VO (Drmota)/Prüfung 2019-06-28

Generating functions

a) $A(x)$ and $B(x)$ are generating functions with coefficients $a_{n}$ and $b_{n}$. Determine $C(x)$ for $c_{n}=\sum _{n\geq 0}\sum _{k=0}^{n}a_{k}b_{n-k}$.

b) Determine $D(x)$ and $d_{n}$ for $d_{n}=\sum _{k=0}^{n}d_{k}-n$

Möbius function

Define $\mu (0,1)$ for this poset:

  1
 / \
|   c
a   |
|   b
 \ /
  0

Define $\mu (0,1)$ for the poset with the additional relation $(a\leq c)$

Dijkstra algorithm

A graph was given (can't remember the exact graph, sorry) and the Dijkstra algorithm had to be performed to get from a specified start node to a specified end node.

Irreducible polynomials + System of congruences

a) Which of these polynomials are irreducible over $\mathbb {Z} _{3}$:

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

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

b) Solve the following system of congruences:

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

$15x\equiv 12\mod 21$