Sie sind nicht angemeldet.

Hazel

Praktikant

  • »Hazel« ist männlich
  • »Hazel« ist der Autor dieses Themas

Beiträge: 21

Registrierungsdatum: 10.01.2006

1

02.02.2007, 17:22

Klausur Diskrete Strukturen

Die Ergebnisse der Wiederholungsklausur hängen vor Raum G015 aus. Werde Montag nachsehen fahren... teu teu teu! =)
Think positive. Think big.

Torrero

Senior Schreiberling

  • »Torrero« ist männlich

Beiträge: 854

Registrierungsdatum: 16.10.2003

Wohnort: Laatzen

Beruf: Angewandte Informatik

2

17.01.2008, 23:21

Kann mir evtl. jemand erklären, wie die Erzeugermatrix in Standardform aufgestellt wird, ich gucke mir das im Skript an und verstehe da im Moment irgendwie nur Bahnhof. Evtl. an einem konkreten Beispiel, z.B. an dem aus dem Skript.

http://www.iag.uni-hannover.de/~behrens/…trukturen10.pdf (auf der 2ten Seite)

Torrero

Senior Schreiberling

  • »Torrero« ist männlich

Beiträge: 854

Registrierungsdatum: 16.10.2003

Wohnort: Laatzen

Beruf: Angewandte Informatik

3

26.01.2008, 21:58

Ich schäme mich zwar etwas diese Frage zu stellen, aber ich machs mal trotzdem

wie funktioniert modulo bei negativen zahlen ?

also wenn es -2 mod 5 ist, ist das ergebnis 3, wenn der taschenrechner nicht lügt
aber wie funktioniert das ganze, wenn man z.B. -5 mod 2 rechnen soll ?

DrChaotica

Senior Schreiberling

  • »DrChaotica« ist männlich

Beiträge: 714

Registrierungsdatum: 22.01.2005

Wohnort: SHG

Beruf: SW-Entwickler

4

26.01.2008, 23:47

(a modulo b) ist meine ich durch mod(a,b) = a - floor(a/b) * b definiert (Floor rundet auf die nächstkleinere ganze Zahl ab), also z.B.

... mod(-4,3)=2, mod(-3,3)=0, mod(-2,3)=1, mod(-1,3)=2, mod(0,3)=0, mod(1,3)=1, mod(2,3)=2, mod(3,3)=0, mod(4,3)=1...
Hast also immer diese kreisförmige Struktur (...,0, 1, 2, ..., b, 0, 1, 2, ..., b, ...) für a mod b, das setzt sich in die negativen Zahlen genauso fort.

Theoretische Hintergründe gibts im nächsten Post, oder z.B. hier: http://www.iti.fh-flensburg.de/lang/algo…en/zahlenth.htm

Dieser Beitrag wurde bereits 1 mal editiert, zuletzt von »DrChaotica« (27.01.2008, 11:50)


thz.

Praktikant

Beiträge: 31

Registrierungsdatum: 05.10.2007

5

27.01.2008, 11:30

a = b mod c, falls es eine ganze Zahl k gibt, mit a - b = k * c.

Für deine Beispiele ergibt sich also:
-2 - 3 = (-1) * 5, also -2 = 3 mod 5
-5 - 1 = (-3) * 2, also -5 = 1 mod 2
Never, ever reuse a paper abstract for a presentation, except if the abstract is “We show P = NP” or “We show P != NP”. If your abstract is one of the above two, double-check whether your proof is correct.
-- User’s Guide to the Beamer Class

sommla

Junior Schreiberling

  • »sommla« ist männlich

Beiträge: 169

Registrierungsdatum: 27.10.2005

6

27.01.2008, 18:29

Kann mir evtl. jemand erklären, wie die Erzeugermatrix in Standardform aufgestellt wird, ich gucke mir das im Skript an und verstehe da im Moment irgendwie nur Bahnhof. Evtl. an einem konkreten Beispiel, z.B. an dem aus dem Skript.

http://www.iag.uni-hannover.de/~behrens/…trukturen10.pdf (auf der 2ten Seite)



Hey!

Das würde mich auch sehr interessieren... irgendwie erklärt das Skript nicht wirklich, wie das funktionieren mag ?(



lg
lars
Lieber ein Haus im Grünen als 'nen Grünen im Haus.

Torrero

Senior Schreiberling

  • »Torrero« ist männlich

Beiträge: 854

Registrierungsdatum: 16.10.2003

Wohnort: Laatzen

Beruf: Angewandte Informatik

7

27.01.2008, 19:46

Ich war beim Übungsleiter, und er hat es mir in 5 Minuten verständlich erklärt. Ist einfacher, als es auf den ersten Blick aussieht. Aber hier irgendwie doch schwer zu beschreiben.

Ganz einfach ist es, wenn man die Kontrollmatrix H hat, dann musst du diese nur transponieren und einfach die entsprechende Einheitsmatrix dranhängen.

Die andere Methode versuche ich jetzt auch mal :
Du hast z.B. 3 Gleichungen mit 7 Variablen, dann ist die Dimension 4, also hat die Erzeugermatrix 4 Zeilen und 7 Spalten,
dann kannst du als erstes die 4x4 Einheitsmatrix hinschreiben, denn die Erzeugermatrix ist G=(E|P)

Und die anderen 3 Elemente jeder Zeile rauszukriegen, nimmst du dir Zeile für Zeile die Einheitsmatrix her, und setzst diese in die Gleichungen ein, und dann musst zu gucken, welche übrigen Variablen der Gleichungen 0 oder 1 werden müssen, um die Gleichung zu erfüllen.

Dann nochmal was zur Gleichungsberechnung in Z_N :

Es gibt die 2 Gleichungen aus der Übung in Z_7 :

(1) x + 2y = 4
(2) 4x + 3y = 4

Dann stelle ich die erste zuerst nach x um
(1) x = 4 - 2y / dann muss man die -2y ja noch nach Z_7 "transferieren" also (-2+7)y=5y
==> x = 4 + 5y

Dann setzt man das in (2) ein

(2) 4(4+5y) + 3y = 4
ausmultipliziert gibt das 16 + 20y + 3y = 4
der nächste Schritt in der Lösung ist, dass das dann in Z_7 = 2+2y ist
kommt man darauf, indem man die 16 und die 23y jeweils mod 7 nimmt ?
16 mod 7 = 2 und 23 mod 7 = 2, also 2+2y = 2 ?

Dieser Beitrag wurde bereits 2 mal editiert, zuletzt von »Torrero« (27.01.2008, 20:42)


sommla

Junior Schreiberling

  • »sommla« ist männlich

Beiträge: 169

Registrierungsdatum: 27.10.2005

8

28.01.2008, 13:33

Ha, cool... danke für den Tipp. Das macht Sinn.

Zu Deiner Frage: Ja, Du hast Recht. 16 + 23y wird durch mod 7 zu 2 + 2y.
Hab ich auch erst eine Zeit lang drüber nachgedacht..
Lieber ein Haus im Grünen als 'nen Grünen im Haus.

Torrero

Senior Schreiberling

  • »Torrero« ist männlich

Beiträge: 854

Registrierungsdatum: 16.10.2003

Wohnort: Laatzen

Beruf: Angewandte Informatik

9

28.01.2008, 18:39

Ich dachte schon, dass ich das mit den Gleichungen kapiert habe, aber ein Schritt kann ich da noch nicht so nachvollziehen :

da ist am Ende der Berechnung :

2 y = 2 und wird dann umgeformt zu y = 4 * 2 = 8 = 1 (das ganze immer noch in z_7)

wie kommt die 4 bei y = 4*2 zustande ?

thz.

Praktikant

Beiträge: 31

Registrierungsdatum: 05.10.2007

10

28.01.2008, 19:27

2*y = 2 => 8 * y = 8 => y = 1
Never, ever reuse a paper abstract for a presentation, except if the abstract is “We show P = NP” or “We show P != NP”. If your abstract is one of the above two, double-check whether your proof is correct.
-- User’s Guide to the Beamer Class

  • »Schokoholic« ist männlich

Beiträge: 2 516

Registrierungsdatum: 04.10.2006

Wohnort: Hannover

Beruf: Haarspaltung

11

28.01.2008, 21:23

Genau. Die 4 die dich da stört ist nämlich das multiplikative Inverse von 2 (im Ring der Restklassen modulo 7).
Also 4 * 2 = 8 = 1 (mod 7)

Normalerweise würdest du die Gleichung ja auflösen indem du mit 1/2 multiplizierst. Das bringt aber nur was, weil 1/2 das multiplikative Inverse von 2 ist.
Also 2 * 1/2 = 2/2 = 1.