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\ge 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\le 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 1mod3$

$15x\equiv 12mod21$