Grundlegende Algorithmen: Lösungshinweise

Kapitel 7

7.1

Seien e und e' zwei neutrale Elemente, dann gilt: e=ee'=e'.

Sei a ein Gruppenelement und b sowie c zwei Inverse zu a, d.h.: ab=e sowie ac=e (wobei e das eindeutige neutrale Element ist).
Wir zeigen zunächst, dass ba=e ist (das Monoid ist nicht notwendig abelsch!). Sei dazu d das Inverse zu ba, d.h. bad=e.
Dann gilt: ba=bae=ba(bad)=b(ab)ad =bead=bad=e.
Betrachte jetzt: b=be=b(ac)=(ba)c=ec=c.

7.2

Beweis durch Induktion.

7.3

Schreibe die Elemente als Potenzen des erzeugenden Elementes und verwende die vorhergehende Aufgabe.

7.4

⇒: Wenn (M',*) eine Untergruppe ist, dann ist M' nach Definition auch abgeschlossen.
⇐: Sei a∈M' und sei M={b₁,...,b_k}. Betrachte a*b₁,...,a*b_k. Da dies auch Elemente von M sind und M eine Gruppe ist, müssen alle Elemente paarweise verschieden sein. Es gibt also ein j&isin[1:k] mit a*b_j=a, d.h. b_j=1 und somit eine neutrales Element in M'. Weiterhin muss es ein i&isin[1:k] mit a*b_i=b_j=1. Also existiert zu a auch ein Inverses in M'. Da a ein beliebiges Element aus M' war, muss es zu jedem Element aus M' ein Inverses geben.

7.5

Sei z das Inverse zu 0*a. Betrachte: 0=0*a+z =(0+0)*a+z =(0*a+0*a)+z =0*a+(0*a+z) =0*a+0 =0*a

7.6

Die Halbringeigenschaften nachrechnen.

7.7

Sei a≠0 und b≠0, dann existieren die Inversen ac=1 und bd=1. Dann folgt aus ab=0, dass abdc=0dc. Mit Aufgabe 7.5 folgt dann: 1=0.

7.8

---

7.9

{e} und G.

7.10

---

7.11

Verwende den Satz aus Aufgabe 7.4.

7.12

⇒: Wenn p∈P, dann ist Z^*p=Z_p\{0} und &phi(p)=p-1. Somit folgt die Behauptung aus einem Satz von Euler.
⇐: Sei d ein Teiler von p, d.h da=p. Nach der rechten Seite gilt d^p-1=1mod p, d.h. d^p-1-1=qp für ein q&isinN. Somit gilt unter Berücksichtigung von p≥2: d(d^p-2-qa)=1. Diese Gleichung über N kann dann und nur dann gelten, wenn d=1.
Aus der Kontraposition der Richtung von links nach rechts kann so erst einmal kein sinnvoller randomisierter Primzahltest abgeleitet werden, da Z_n\{0} im Allgemeinen keine multiplikative Gruppe ist und über die Anzahl der Zeugen nichts ausgesagt werden kann.

7.13

Beweis durch Induktion.

7.14

---

7.15

Fleißaufgabe.
Die Rekursionsgleichung lautet: B(n)=Sum(i=1..n-1) B(i)*B(n-i).
Das Ergebnis lautet: 1/(n)*C(2n-2,n-1), wobei C(.,.) der Binomialkoeffizient ist.

Alternativmöglichkeit: Stelle eine bijektive Beziehung zwischen geordneten erweiterten binären Bäumen und Klammerausdrücken her.

7.16

Es gilt offensichtlich: A(n,m) =1+A(n-1,m)+A(n-1,m-1) sowie A(n,n)=A(n,0)=0. Wir setzen B(n,m):=1+A(n,m). Dann gilt B(n,m) =B(n-1,m)+B(n-1,m-1) sowie B(n,n)=B(n,0)=1. Also ist B(n,m) gleich m aus n. Damit kennen wir auch A.

7.17

---