infostudium.de

von **aRo** » 17.02.08 16:56

Hi!

Ich dachte ich eröffne mal einfach einen DS Fragen-Sammelthread, wo doch die Klausur nächsten Freitag droht.

Also, ich hätte da nämlich schon mal zwei:

1. Wie berechnet man das zu x(quer) inverse Element in (Z/nZ)^* mittels dem erweiterten euklidischen Algorithmus? Ein Beispiel wäre super!

2. Mir ist auch noch nicht ganz klar, wie das mit der endlichen Ordnung eines Elements einer Gruppe funktioniert. Hier wär ein Beispiel auch Gold wert.

Vielen Dank!

von fw » 17.02.08 17:36

aRo hat geschrieben:1. Wie berechnet man das zu x(quer) inverse Element in (Z/nZ)^* mittels dem erweiterten euklidischen Algorithmus? Ein Beispiel wäre super!

Ja, genau, das geht mit dem euklidischen Algorithmus. Erstmal ist wichtig zu wissen, dass ein Element in $\mathbb{Z}/n\mathbb{Z}$ genau dann invertierbar ist wenn es relativ prim zu $n$ ist, d.h. es darf keine gemeinsamen Teiler mit $n$ haben. Die wichtige Idee beim euklidischen Algorithmus ist nämlich die Tatsache, dass es für zwei Elemente $a,b \in \mathbb{Z}$ immer eine Linearkombination des ggT gibt, d.h. es existieren $s,t \in \mathbb{Z}$ mit $s \cdot a + t \cdot b = ggT(a,b)$ . Wenn a und b teilerfremd sind existiert also eine Darstellung der 1. Okay, was bringt das?

Beispiel:
$R = \mathbb{Z}/6\mathbb{Z}$ und $a = 5$ . Es gilt $ggT(a,n) = ggT(5,6) = 1$ , also ist 5 in diesem Ring invertierbar. Nach dem was ich oben gesagt habe gibt es also $s,t$ mit $1 = 5 \cdot s + 6 \cdot t$ , d.h. also es gibt ein $s$ mit $5 \cdot s \equiv 1\ (mod 6)$ , also ist dieses $s$ genau das Inverse von 5 in $\mathbb{Z}/6\mathbb{Z}$ . Wie bekommt man das nun?

Division mit Rest liefert hier direkt nach dem ersten Schritt:
$6 = 1 \cdot 5 + 1 \Leftrightarrow 1 = \underbrace{(-1)}_{= s} \cdot 5 + \underbrace{1}_{= t} \cdot 6 \Rightarrow 1 \equiv (-1) \cdot 5\ (mod 6)$

D.h. (-1) ist also das Inverse von 5. (-1) ist in diesem Ring das selbe wie 5, also ist das Inverse von 5 gleich 5 (man sagt dann auch "5 ist selbstinvers"). Probe: $5 \cdot 5 = 25 \equiv 1\ (mod 6)$ , stimmt, also $\overline{5}^{-1} = \overline{5}$

Kleiner Tipp: Bei solchen Aufgaben wird oft verlangt beide Faktoren der Linearkombination anzugeben (das $s$ und das $t$ ). Normalerweise (bei größeren Zahlen) ist man auch nicht schon nach einem Schritt fertig.. Schau mal bei Wikipedia, die Seite dazu ist ganz gut erklärt.

aRo hat geschrieben:2. Mir ist auch noch nicht ganz klar, wie das mit der endlichen Ordnung eines Elements einer Gruppe funktioniert. Hier wär ein Beispiel auch Gold wert.

Was genau ist dir daran nicht klar? In diesem Thread wurde das relativ ausführlich erklärt..

Gruss
Flo

von **aRo** » 17.02.08 19:34

Hi Flo!

Vielen Dank für deine super Antwort. Ich würde sagen, ich stelle meine zweite Frage erstmal zurück. Vielleicht komm ich ja selbst drauf, wenn ich bei den entsprechenden Übungsaufgaben angekommen bin.

Nun will ich erstmal das hier verstehen (und danach gibts leider auch noch Fragen zu den Übungsaufgaben in Aufgabe 2 Blatt 7).

gibt es also s,t mit $1 = 5 \cdot s + 6 \cdot t$ , d.h. also es gibt ein s mit $5 \cdot s \equiv 1\ (mod 6)$ , also ist dieses s genau das Inverse von 5 in $\mathbb{Z}/6\mathbb{Z}$

Ab hier fängt es an etwas unklarer für mich zu werden. Die erste Folgerung leuchtet mir ja noch irgendwie ein, denn es muss ja ein s existieren, so dass 5s-1 durch 6 teilbar ist, womit wir unser ganzzahliges t errechnet hätten. Die zweite Folgerung hingegen ist mir nicht klar.
Das neutrale Element beim Rechnen im Restklassenring ist $\bar{1}$ nicht wahr (zumindest für die Multiplikation)?

Also suchst du hier nach einem s, dass mit 5 multipliziert wird und das Ergebnis nach Division durch 6 den Rest 1 lässt, weil das das neutrale Element ist?

Ich muss allgemein gestehen, dass ich mit der modularen Arithmetik noch so meine Schwierigkeiten habe.

von fw » 17.02.08 20:33

aRo hat geschrieben:
fw hat geschrieben:gibt es also s,t mit $1 = 5 \cdot s + 6 \cdot t$ , d.h. also es gibt ein s mit $5 \cdot s \equiv 1\ (mod 6)$ , also ist dieses s genau das Inverse von 5 in $\mathbb{Z}/6\mathbb{Z}$

Die zweite Folgerung (..) ist mir nicht klar.
(..)
Also suchst du hier nach einem s, dass mit 5 multipliziert wird und das Ergebnis nach Division durch 6 den Rest 1 lässt, weil das das neutrale Element ist?

Ja, ganz genau richtig. Sieht nicht so aus als hättest du Schwierigkeiten mit der Folgerung :-) Oder was ist unklar? Warum 5 die gesuchte Eigenschaft erfüllt, d.h. warum 5*5=1 ist in diesem Ring? Oder warum s jetzt genau das Inverse ist?

von **aRo** » 17.02.08 21:24

hmm....weißt du, irgendwie versteh ichs, aber ich kanns nicht richtig greifen

Vielleicht hilft es doch nochmal, wenn du

Oder warum s jetzt genau das Inverse ist?

nochmal erklärst.

Danke Dir!

von fw » 17.02.08 21:38

Okay, also.. Ein Element $a$ einer (multiplikativ geschrieben) Gruppe (mit neutralem Element 1) heißt Inverses Element von $b$ wenn gilt: $a \cdot b = 1$ .

Wenn ich dich richtig verstanden habe, ist dir klar, dass in meinem Beispiel $5 \cdot s \equiv 1\ (mod 6)$ gilt, oder?

Zwei Elemente in dem Ring in meinem Beispiel sind genau dann gleich wenn sie bei Division durch 6 den gleichen Rest ergeben. D.h. z.B. $... = -7 = -1 = 5 = 11 = 17 = 23 = ...$ usw. Mach dir auch klar, dass die Elemente in diesem Ring eigentlich MENGEN sind! Nämlich die Restklassen bzgl. Division durch 6! z.B. $\overline{5} = \{ ..., -7, -1, 5, 11, ... \}$ , d.h. z.B. $\overline{5} = \overline{-7}$ , weil das die gleichen Mengen sind, nur jeweils in anderer Notation (andere Repräsentanten dieser Restklasse)

Okay, du suchst also jetzt ein Element $a$ so dass $5 \cdot a = 1$ in diesem Ring. "gleich" bedeutet in diesem Ring aber nur "gleich bis auf Vielfache von 6", d.h. "gleicher Rest bei Division durch 6" oder "kongruent modulo 6", etc.

Man könnte auch sagen $5 \cdot s = 1$ ist (in diesem Ring) das selbe wie $5 \cdot s \equiv 1\ (mod 6)$ ist das selbe wie $\overline{5} \cdot \overline{s} = \overline{1}$

Hoffe das hilft dir irgendwie... Rechne einfach mal ein paar Aufgaben, das hilft vermutlich mehr als jede kompliziert aussehende Erklärung (die wirst du aber dann im Nachhinein besser verstehen!)

von **aRo** » 17.02.08 22:16

hey!

okay, alles soweit klar.
Nur das hier anscheinend doch nicht so ganz:

Wenn ich dich richtig verstanden habe, ist dir klar, dass in meinem Beispiel $5 \cdot s \equiv 1\ (mod 6)$ gilt, oder?

Ich habe mir mal ein neues Beispiel überlegt:

$R=\mathbb Z /_{7 \mathbb Z}$ = Menge aller Restklassen mod 7.

außerdem wähle ich a=3.
$ggT(3,7) = 1 \Rightarrow \exists \bar{a'} \text{ mit } \bar{a}\cdot\bar{a'}=\bar{1}$

Nach dem euklidischen Algorithmus gibt es s und t mit
$ggT(3,7)=1=s\cdot 3 + t \cdot 7$

So, dann habe ich das hier bei Dir abgeschrieben
$3 \cdot s \equiv 1\ (mod 7)$
ein deutliches Indiz dafür, dass ich nicht genau weiß, was das heißt. Nochmal: Ich suche also ein s, so dass 3*s / 6 den Rest 1 lässt, korrekt?

Allgemein könnte ich sagen, dass $y \equiv x (mod n)$ alle Zahlen sind, die bei der Division durch n den Rest x lassen?

Okay, da gilt $1= 1 \cdot 7 + (-2) \cdot 3$
Ist s also -2 und t=1.

Damit ist unser Inverses -2

Probe:
$\bar{-2} \cdot \bar{3} = \bar{-6} = \bar{1}$
denn -6 mod 7 = 1

Wenn es dann an die großen Zahlen geht:
1. Ich vergewisser mich ob es überhaupt ein Inverses gibt.
2. Ich bestimmte mit Hilfe des erweiterten euklidischen Algorithmus die Zahlen s und t.
s ist mein Inverses und ich bin fertig...

von fw » 17.02.08 22:21

Ja, sieht alles richtig aus.

Falls du Probleme mit der Schreibweise $a \equiv b\ (mod n)$ hast, das bedeutet nichts anderes, als dass $a$ und $b$ bei Division durch $n$ den gleichen Rest lassen (oder anders formuliert: Die Differenz $a-b$ ist ein Vielfaches von $n$ . z.B. ist $10 \equiv 4\ (mod 6)$ , da $\overline{4} = \overline{10}$ bzw. da 10 und 4 bei Division durch 6 den selben Rest lassen (nämlich 4) bzw. da die Differenz $10 - 4 = 6$ ein Vielfaches von 6 ist)

von **aRo** » 18.02.08 11:17

okay, danke, ich denke ich habe es verstanden!

Betrachten wir die symmetrische Gruppe. Da es sich um eine Gruppe handelt, muss das Assoziativgesetz gelten und es muss ein neutrales und ein inverses Element geben:

- neutrale ist die Permutation, die alle Elemente invariant lässt, zB (1)(2)(3)...
- Inverse dreht praktisch die Ziffernreihenfolge im Zykel um.

Nun fehlt nur noch das AG. Und das check ich nicht so ganz, wie das funktionieren soll...ich komme mir da wohl immer mit dem Kommutativgesetz ins Gehege, das ja bekanntlich nicht gilt.
Vielleicht auch hier ein Beispiel?

Bei den Abbildungen ist das neutrale Element die Identitätsabbildung. Als Inverses würde ich die Umkehrfunktion vermuten, die allerdings nur existiert, wenn die Abbildungen immer injektiv sind, korrekt?
Das hier das AG im Allgemeinen gilt, hat er Hiß uns versucht klar zu machen...naja ich glaube ihm das jetzt einfach mal

von **LonliLokli** » 18.02.08 19:29

1. Wie wichtig sind in der Vorlesung vorgestellte Algorithmen (außer EA und EEA, die auf jeden Fall klausurrelevant sind)?

2. Wie wichtig ist das Prinzip der Inklusion/Exklusion (ich habe so eine Aufgabe so gut wie in jeder Klausur vom Lahrstuhl gesehen)? Aber so richtig geübt haben wir das nicht.

von **Chrizzo** » 18.02.08 19:53

Ich ergänze zu Lonis Frage noch das Schubfachprinzip und ersuche eine etwas genauere Erläuterung wie man damit Aufg. angeht =)

von **LonliLokli** » 18.02.08 20:09

Wer noch den Link nicht kennen sollte. Da sind Klausuren, die vom Lehrstuhl D mal gestellt wurden.
http://www.math.rwth-aachen.de/homes/Klausuren/Diskrete_Strukturen/

von **Martin** » 18.02.08 20:13

LonliLokli hat geschrieben:Wer noch den Link nicht kennen sollte. Da sind Klausuren, die vom Lehrstuhl D mal gestellt wurden.
http://www.math.rwth-aachen.de/homes/Klausuren/Diskrete_Strukturen/

Dabei sollte man aufpassen, dass sich die Vorlesung "Diskrete Strukturen", die damals für den Diplomstudiengang gelesen wurde, inhaltlich sehr von dem unterscheiden dürfte, was im Bachelorstudiengang gelehrt wird.

von **LonliLokli** » 18.02.08 20:54

mister_nu hat geschrieben:Dabei sollte man aufpassen, dass sich die Vorlesung "Diskrete Strukturen", die damals für den Diplomstudiengang gelesen wurde, inhaltlich sehr von dem unterscheiden dürfte, was im Bachelorstudiengang gelehrt wird.

Da würde man spätestens bei Durchsehen von Klausuren feststellen. :roll:

von **Chrizzo** » 18.02.08 21:37

könnte mir mal wer die Rechenwege zu den beiden Aufgabe erläutern?

1.
Wieviele Passwörter mit 5 Zeichen, unter denen mindestens eine Ziffer und
mindestens ein Satzzeichen vorkommt, sind möglich?

2.
Wieviele Passw¨orter mit höchstens 5 Zeichen, in denen mindestens ein
Groß- und ein Kleinbuchstabe, sowie mindestens eine Ziffer und ein Satzzeiche vorkommen, sind möglich?

Wer die Aufgabe net findet oder nicht zur Hand hat, 26 Groß-, sowie Kleinbuchstaben, 10 Ziffern, 10 Satzzeichen

infostudium.de

Forum zum Informatikstudium an der RWTH Aachen

[Diskrete] Fragen Sammelthread

Fragen Sammelthread

Re: Fragen Sammelthread