blatt2

Mathematik für Informatiker I

Prof . Dr. F.-O. Schreyer

Übungsblatt 2

Abgabetermin Montag 11.11.2002 vor der Vorlesung

$\mathbb {Q}$ [x] bezeichne die Menge aller Polynome mit rationalen Koeffizienten.
Sei
p $\left(\vphantom{ x}\right.$ x $\left.\vphantom{ x}\right)$ : = a_dx^d + ... + a₁x + a₀ $\in$ $\mathbb {Q}$ [x]
ein Polynom vom Grad d, welches für große n $\in$ $\mathbb {Z}$ ganzzahlige Werte annimmt, d.h. $\exists$ n₀, sodaß gilt p $\left(\vphantom{ n}\right.$ n $\left.\vphantom{ n}\right)$ $\in$ $\mathbb {Z}$ $\forall$ n $\geq$ n₀.
Zeigen Sie $\exists$ $\alpha_{{0}}^{}$ ,..., $\alpha_{{d}}^{}$ $\in$ $\mathbb {Z}$ , sodaß

p $\displaystyle \left(\vphantom{ x}\right.$ x $\displaystyle \left.\vphantom{ x}\right)$ = $\displaystyle \sum_{{k=0}}^{{d}}$ $\displaystyle \alpha_{{k}}^{}$ $\displaystyle \binom{%% \begin{tabular}[c]{lll}%% $x$\ & $+$\ & $k$%% \end{tabular}}{k}%%$
Dabei sei

$\displaystyle \binom{%% \begin{tabular}[c]{lll}%% $x$\ & $+$\ & $k$%% \end{tabular}}{k}$ : = $\displaystyle \prod_{{j=1}}^{{k}}$ $\displaystyle {\frac{{x+j}}{{j}}}$ $\displaystyle \in$ $\displaystyle \mathbb {Q}$ [x]

Hinweis: Verwenden Sie Induktion nach d und das Differenzenpolynom $\triangle$ p $\in$ $\mathbb {Q}$ [x] definiert für p $\in$ $\mathbb {Q}$ [x] durch

$\displaystyle \triangle$ p $\displaystyle \left(\vphantom{ x}\right.$ x $\displaystyle \left.\vphantom{ x}\right)$ : = p $\displaystyle \left(\vphantom{ x}\right.$ x $\displaystyle \left.\vphantom{ x}\right)$ - p $\displaystyle \left(\vphantom{ x-1}\right.$ x - 1 $\displaystyle \left.\vphantom{ x-1}\right)$
Äquivalenzrelationen:
1. Wir definieren die folgende Äquivalenzrelation auf M : = × durch a, b c, d genau dann, wenn a + d = b + c.
  1. Zeigen Sie, daß dies eine Äquivalenzrelation auf M ist.
  2. Beschreiben Sie die Äquivalenzklassen [ $\left(\vphantom{ 1,1}\right.$ 1, 1 $\left.\vphantom{ 1,1}\right)$ ] und [ $\left(\vphantom{ 3,1}\right.$ 3, 1 $\left.\vphantom{ 3,1}\right)$ ].
  3. Definieren Sie die Addition von Äquivalenzklassen durch
    
    [ $\displaystyle \left(\vphantom{ a,b}\right.$ a, b $\displaystyle \left.\vphantom{ a,b}\right)$ ] + [ $\displaystyle \left(\vphantom{ c,d}\right.$ c, d $\displaystyle \left.\vphantom{ c,d}\right)$ ] : = [ $\displaystyle \left(\vphantom{ a+c,b+d}\right.$ a + c, b + d $\displaystyle \left.\vphantom{ a+c,b+d}\right)$ ]
    Zeigen Sie, daß diese Addition wohldefiniert ist, d.h. unabhängig von den gewählten Repräsentanten der Äquivalenzklassen ist.
  4. Zeigen Sie [ $\left(\vphantom{ a,b}\right.$ a, b $\left.\vphantom{ a,b}\right)$ ] + [ $\left(\vphantom{ 2,2}\right.$ 2, 2 $\left.\vphantom{ 2,2}\right)$ ] = [ $\left(\vphantom{ a,b}\right.$ a, b $\left.\vphantom{ a,b}\right)$ ] und [ $\left(\vphantom{ 2,5}\right.$ 2, 5 $\left.\vphantom{ 2,5}\right)$ ] + [ $\left(\vphantom{ 7,5}\right.$ 7, 5 $\left.\vphantom{ 7,5}\right)$ ] = [ $\left(\vphantom{ 1,2}\right.$ 1, 2 $\left.\vphantom{ 1,2}\right)$ ]
  5. Kennen Sie die Menge der Äquivalenzklassen M/ $\sim$ unter anderem Namen?
2. Betrachte Sie die Menge M : = ²\0, 0, d.h. die Menge aller Punkte der reellen Ebene ohne den 0-Punkt.
  Wir definieren eine Äquivalenzrelation auf M×M durch $\left(\vphantom{ x,y}\right.$ x, y $\left.\vphantom{ x,y}\right)$ $\sim$ $\left(\vphantom{ x^{\prime},y^{\prime}}\right.$ x, y $\left.\vphantom{ x^{\prime},y^{\prime}}\right)$ genau dann, wenn es eine Gerade durch den Nullpunkt $\left(\vphantom{ 0,0}\right.$ 0, 0 $\left.\vphantom{ 0,0}\right)$ $\in$ $\mathbb {R}$ ² gibt, auf der sowohl der Punkt $\left(\vphantom{ x,y}\right.$ x, y $\left.\vphantom{ x,y}\right)$ als auch der Punkt $\left(\vphantom{ x^{\prime},y^{\prime}}\right.$ x, y $\left.\vphantom{ x^{\prime},y^{\prime}}\right)$ liegen.
  1. Zeigen Sie, daß dies tatsächlich eine Äquivalenzrelation ist.
  2. Finden Sie eine geometrische Darstellung der Menge der Äquivalenzklassen M/ $\sim$ indem Sie in jeder Äquivalenzklasse einen geeigneten Repräsentanten wählen.
Sei M eine unendliche Menge. Zeigen Sie:
1. Es gibt keine surjektive Abbildung $\varphi$ : M $\rightarrow$ 2^M.
2. Es gibt keine injektive Abbildung $\psi$ : 2^M $\rightarrow$ M.
Lösen Sie folgende simultane Kongruenzen:

x $\displaystyle \equiv$ 5mod6

x $\displaystyle \equiv$ 8mod15

x $\displaystyle \equiv$ 3mod10
1. Programmieren Sie in Maple eine Funktion ggT, die für zwei ganze Zahlen a, b eine Darstellung
  
  ggT $\displaystyle \left(\vphantom{ a,b}\right.$ a, b $\displaystyle \left.\vphantom{ a,b}\right)$ = u^.a + v^.b
  mit u, v $\in$ $\mathbb {Z}$ berechnet und die Liste [ggT $\left(\vphantom{ a,b}\right.$ a, b $\left.\vphantom{ a,b}\right)$ , u, v] zurückgibt.
  Bem.: Verwenden Sie proc zur Definition einer Prozedur und iquo zur Division mit Rest. Vergleichen Sie an Beispielen ihre Funktion mit der eingebauten Maple-Prozedur igcdex.
2. Scheiben Sie eine Maple-Funktion, die den ggT $\left(\vphantom{ L}\right.$ L $\left.\vphantom{ L}\right)$ für eine Liste von ganzen Zahlen L = [a₁,..., a_k] bestimmt.
(Abgabe bitte als Ausdruck mit einer Beispielrechnung).

janko 2002-10-31

x	$\displaystyle \equiv$ 5mod6
x	$\displaystyle \equiv$ 8mod15
x	$\displaystyle \equiv$ 3mod10