diskrete Mathematik...Codes < Sonstiges < Hochschule < Mathe < Vorhilfe
|
Hi, bin ganz neu und hab schon einige Aufgabern, bei denen ich etwas Hilfe benötigen könte.Wär echt nett!!
erstens:
Beweise: Jeder Gruppencode mit Permutationen erkennt ale Einzelfehler
zweitens:
Gesucht ist die Verknüpfungstafel der Diedergruppe D 5
drittens:
Auf einer Seite eines Euro-Geldschein findet man einen Buchstaben, gefolgt von mehreren Ziffern (z.B. X03339149519). Welche Codierungsmethode steckt hinter diesen Zeichen? Was bedeutet der Buchstabe? Welche anderen Buchstaben sind möglich? Ist das obige Beispiel korrekt?
Ganz schön viel auf einmal oder? Aber vielleicht habt ihr ja irgendwelche Ideen???
Lieben Gruß Björn
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 21:13 Mi 10.12.2003 | | Autor: | Stefan |
Hallo Björn,
also, ich kann dir leider nicht helfen, da ich von diskreter Mathematik keine Ahnung habe. Wenn Marc dir auch nicht helfen kann (was ich nicht weiß), dann sieht es schlecht aus.
Die Aufgabe mit der Diedergruppe ist ja eine reine Algebra-Aufgabe. Die könnte ich noch versuchen hinzukriegen.
Hmmmh... existiert ein Skript im Internet, wo man die Sachen nachlesen kann?
Alles Gute
Stefan
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 21:36 Mi 10.12.2003 | | Autor: | Marc |
Hallo phymastudi,
> Hi, bin ganz neu und hab schon einige Aufgabern, bei denen ich
> etwas Hilfe benötigen könte.Wär echt nett!!
also auch von mir: Herzlich Willkommen 
Allerdings kann ich dir auch nicht so richtig weiterhelfen, immerhin habe ich eine Ahnung, worum es geht, wahrscheinlich Kryptografie.
Wenn du Geduld hast, und mir die Begriffe/Definitionen erklärst, finden wir bestimmt auch eine Lösung!
> erstens:
> Beweise: Jeder Gruppencode mit Permutationen erkennt ale
> Einzelfehler
Definition von "Gruppencode", und vielleicht auch "Gruppencode mit Permutationen" und natürlich "Einzehlfehler".
Ein Einzelfehler ist ist wahrscheinlich die Vertauschung zweier benachbarter Ziffern/Zeichen oder eine einzelne, falsch übertragene Ziffer.
> zweitens:
> Gesucht ist die Verknüpfungstafel der Diedergruppe D
> 5
Später mehr dazu.
> drittens:
> Auf einer Seite eines Euro-Geldschein findet man einen
> Buchstaben, gefolgt von mehreren Ziffern (z.B. X03339149519).
> Welche Codierungsmethode steckt hinter diesen Zeichen? Was
> bedeutet der Buchstabe? Welche anderen Buchstaben sind möglich?
> Ist das obige Beispiel korrekt?
Tja, jetzt müßte man sich mit Codierungsmethoden auskennen...
Ich nehme doch mal an, dass der Buchstabe -- wie bei einer ISB-Nummer -- eine Art Checksumme ist. Oder er codiert einfach den Druckort...
Vielleicht sind ja noch mehr Informationen in dieser Zeichenfolge, z.B. Wert, Jahr des Drucks etc.
> Ganz schön viel auf einmal oder? Aber vielleicht habt ihr ja
> irgendwelche Ideen???
In welchen Bereich/Vorlesung gehören denn diese Aufgaben?
Alles Gute,
Marc.
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 23:27 Mi 10.12.2003 | | Autor: | phymastudi |
ja, ist praktisch auf dem Weg hin zur Kryptografie!
Ein Skript gibt es leider nicht.
Wir arbeiten in der Vorlesung mit dem Beutelspacher Buch "Diskrete Mathematik für Einsteiger".
Ich werde erstmal etwas weiterüberlegen und werde euch die nächsten Tage mal mit den Definitionen zuschütten, wenn s euch recht ist.
Die Diedergruppe war auch schon bei uns Bestandteil der algebra, aber leider ist mir das wieder entfallen.
lfg Björn
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 08:22 Do 11.12.2003 | | Autor: | Stefan |
Hallo Björn!
> Wir arbeiten in der Vorlesung mit dem Beutelspacher Buch
> "Diskrete Mathematik für Einsteiger".
Vielen Dank für den Hinweis. Ich werde mir das Buch kaufen und bestelle es gleich. Wollte ich eh mal tun und dies ist eine gute Gelegenheit dazu.
Alles Gute
Stefan
|
|
|
| |
|
Hallo Stefan.
Vorweg erstmal vielen DAnk für deine Mühen.
Leider kann ich beim Öffnen dieser Seite nur unbrauchbare Buchstabefolgen ohne Sinn entnehmen.
Vielleicht liegt das am Dateienformat?
Mal schauen.
Bis demnächst.
LG Björn
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 21:13 Do 11.12.2003 | | Autor: | Marc |
Hallo phymastudi,
hier habe ich die Datei nach pdf konvertiert:
![[a]](/images/paperclip.gif "Dateianhänge") [Dateianhang Nr. None (fehlt/gelöscht)]
Gruß,
Marc.
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 10:49 Sa 13.12.2003 | | Autor: | Stefan |
Hallo Björn,
also, ich habe mir das Buch jetzt gekauft, konnte die Definitionen nachlesen und damit die Aufgabe lösen.
Zunächst einmal die Definitionen:
Definition 1 (Code/Einzelfehler)
(a) Ein Code der Länge [mm]n[/mm] zur Basis [mm]q[/mm] ist irgendeine Menge von Folgen [mm](a_1,a_2,\ldots,a_n)[/mm] der Länge [mm]n[/mm], wobei die [mm]a_i[/mm] ganze Zahlen zwischen [mm]0[/mm] und [mm]q-1[/mm] sind. Man spricht auch von einem Code über dem Alphabet [mm]\{0,1,\ldots,q-1\}[/mm] und den Ziffern [mm]0,1,\ldots,q-1[/mm]. Die Elemente des Codes nennen wir Codewörter. Statt [mm](a_1,a_2,\ldots,a_n)[/mm] schreiben wir auch [mm]a_1 a_2 \cdots a_n[/mm].
(b) Wir sagen, dass ein Code Einzelfehler erkennt, wenn folgendes gilt: Wenn an einem Codewort an einer Stelle der Wert [mm]a_i[/mm] in [mm]a_i' \quad (\ne a_i)[/mm] geändert wird, so ist die entstehende Folge kein Codewort.
Mit anderen Worten bedeutet dies, dass sich je zwei verschiedene Codewörter an mindestens zwei Stellen unterscheiden. Der Empfänger einer Nachricht überprüft, ob diese ein Codewort ist. Er akzeptiert diese Nachricht genau dann, wenn diese ein Codewort ist.
Definition 2 (Gruppencode mit Permutationen)
Es sei [mm]G[/mm] eine multiplikativ geschriebene Gruppe, und [mm]c[/mm] ein beliebiges Element von [mm]G[/mm]. Ferner seien [mm]\pi_1,\pi_2,\ldots,\pi_n[/mm] Permutationen der Menge [mm]G[/mm]. Ein Code der Länge [mm]n[/mm] über der Gruppe [mm]G[/mm] mit Kontrollsymbol [mm]c[/mm] und Permutationen [mm]\pi_1,\pi_2,\ldots,\pi_n[/mm] ist die Menge aller [mm]n[/mm]-Tupel von Gruppenelementen, so dass ihr "permutiertes" Produkt gleich [mm]c[/mm] ist. In Formeln:
[mm]C=\{(g_1,g_2,\ldots,g_n)\, \vert\, g_i \in G,\, \pi_1(g_1)\cdot \pi_2(g_2)\cdot \ldots \cdot \pi_n(g_n)=c\}.[/mm]
Wir sprechen auch von einem Gruppencode mit Permutationen [mm]\pi_1,\pi_2,\ldots,\pi_n[/mm].
Jetzt die zu zeigende Aussage (im Beutelspacher Seite 108, Kapitel 6, Aufgabe 12):
Aufgabe
Zeigen Sie, dass jeder Gruppencode mit Permutationen alle Einzelfehler erkennt.
Lösungsvorschlag
Es sei [mm]C[/mm] ein Gruppencode mit Permutationen, gegeben wie in Definition 2. Wir nehmen an, dass [mm]C[/mm] nicht alle Einzelfehler erkennt. Dann gibt es ein [mm](g_1,g_2,\ldots,g_n) \in C[/mm], ein [mm]i \in \{1,\ldots,n\}[/mm] sowie ein [mm]g_i' \in G[/mm] mit [mm]g_i \ne g_i'[/mm], so dass auch
[mm](g_1,g_2,\ldots, g_{i-1},g_i',g_{i+1},\ldots,g_n) \in C[/mm]
gilt. Nach Voraussetzung haben wir also:
[mm]\pi_1(g_1)\cdot \pi_2(g_2)\cdot \ldots \cdot \pi_{i-1}(g_{i-1}) \cdot \pi_i(g_i) \cdot \pi_{i+1}(g_{i+1}) \cdot \ldots \cdot \pi_n(g_n)=c[/mm]
und
[mm]\pi_1(g_1)\cdot \pi_2(g_2)\cdot \ldots \cdot \pi_{i-1}(g_{i-1}) \cdot \pi_i(g_i') \cdot \pi_{i+1}(g_{i+1}) \cdot \ldots \cdot \pi_n(g_n)=c[/mm],
also auch:
[mm]\pi_1(g_1)\cdot \pi_2(g_2)\cdot \ldots \cdot \pi_{i-1}(g_{i-1}) \cdot \pi_i(g_i) \cdot \pi_{i+1}(g_{i+1}) \cdot \ldots \cdot \pi_n(g_n)=\pi_1(g_1)\cdot \pi_2(g_2)\cdot \ldots \cdot \pi_{i-1}(g_{i-1}) \cdot \pi_i(g_i') \cdot \pi_{i+1}(g_{i+1}) \cdot \ldots \cdot \pi_n(g_n)[/mm].
Wenn wir nun nacheinander auf beiden Seiten der Gleichung von links mit [mm](\pi_1(g_1)\cdot \pi_2(g_2)\cdot \ldots \cdot \pi_{i-1}(g_{i-1}))^{-1}[/mm] und von rechts mit [mm](\pi_{i+1}(g_{i+1}) \cdot \ldots \cdot \pi_n(g_n))^{-1}[/mm] multiplizieren (man beachte, dass es sich in beiden Fällen um Elemente der Gruppe [mm]G[/mm] handelt), dann folgt unmittelbar, dass
[mm]\pi_i(g_i) = \pi_i(g_i')[/mm]
wahr sein muss. Da [mm]\pi_i[/mm] eine Permutation und damit bijektiv ist, folgt daraus
[mm]g_i = g_i'[/mm],
was einen Widerspruch zur Annahme darstellt.
Somit erkennt [mm]C[/mm] alle Einzelfehler und die Aussage ist bewiesen.
Alles verstanden?
Alles Gute
Stefan
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 00:12 Di 16.12.2003 | | Autor: | phymastudi |
Hallo !
Ich muss schon sagen, ich bin baff!!!
Das ist superklasse, was du da hinbekommen hast!!!
RESPEKT!!!
Ich denke ich spreche im Namen aller, wenn ich sage, dass euer Angagement u8nd eure Hilfe einfach super genial sind!!!!!
Vielen, vielen DAnk!!!!
Viele Grüße euer Björn
|
|
|
| |
|
Hallo Stefan, Hallo Marc!
Erstmal wünsch ich euch en super gesundes und erfolgreiches neues jahr.
Ich wende mich wieder mit Problemen an euch!
Und zwar:
Diese Aufgabe benötige ich dringend bis Montag abend gelöst:
Sei C der >Gruppencode der Länge n=3 über der Gruppe (Z 3,+ 3) mit Kontrollsymbol c=0 und den Permutationen Pi1= (012), PI2= (02), PI3.
Beweise oder widerlege:
a) (1,2,2)ist Element von C, wenn gilt (0,1,1) ist kein Element von C
b) (1,2,2) ist Element von C, wenn gilt: (0,1,2) ist Element von C
c) (1,2,2),(0,2,0) ist Element von C, wenn gilt: PI3 ist eindeutig bestimmt!
PLEASE HElP!!
Ihr würdet mir super weiterhelfen..
Vielen Dank im voraus.
Gruß Björn
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 12:34 Mo 05.01.2004 | | Autor: | Stefan |
Hallo Björn,
auch dir ein erfolgreiches und gesundes Neues Jahr!
Zu deinen Aufgaben:
> Sei C der >Gruppencode der Länge n=3 über der Gruppe (Z
> 3,+ 3) mit Kontrollsymbol c=0 und den
> Permutationen Pi1= (012), PI2= (02), PI3.
Also:
[mm]C= \{(g_1,g_2,g_3) \in \IZ_3^3\, : \, \Pi_1(g_1) +_3 \Pi_2(g_2) +_3 \Pi_3(g_3) = 0\},[/mm]
wobei ich mich [mm]+_3[/mm] die Addition in [mm] \IZ_3[/mm] bezeichne.
> Beweise oder widerlege:
> a) (1,2,2)ist Element von C, wenn gilt (0,1,1) ist kein Element
> von C
Das ist natürlich Blödsinn. Für [mm]\Pi_3=(01)[/mm] etwa ist [mm](0,1,1)[/mm]
wegen
[mm]\Pi_1(0)+_3 \Pi_2(1) +_3 \Pi_3(1) = 1 +_3 1 +_3 0 = 2 \ne 0[/mm]
kein Element von [mm]C[/mm] und
[mm](1,2,2)[/mm] wegen
[mm]\Pi_1(1) +_3 \Pi_2(2) +_3 \Pi_3(2) = 2 +_3 0 +_3 2 = 1 \ne 0[/mm]
ebenfalls nicht.
> b) (1,2,2) ist Element von C, wenn gilt: (0,1,2) ist Element
> von C
Das stimmt. Denn wegen
[mm]\Pi_1(1) +_3 \Pi_2(2) = 2 +_3 0 = 2[/mm]
und
[mm]\Pi_1(0) +_3 \Pi_2(1) = 1 +_3 1 = 2[/mm]
sind sowohl [mm](1,2,2)[/mm] als auch [mm](0,1,2)[/mm] genau dann Element von [mm]C[/mm], wenn [mm]\Pi_3(2) = 1[/mm] gilt.
> c) (1,2,2),(0,2,0) ist Element von C, wenn gilt: PI3 ist
> eindeutig bestimmt!
Was ist hier mit "eindeutig bestimmt" gemeint? Wodurch eindeutig bestimmt? Um für jedes einzelne [mm](x,y,z)[/mm] in [mm]\IZ_3^3[/mm] entscheiden zu können, ob [mm](x,y,z) \in C[/mm] gilt oder nicht, ist [mm]\Pi_3[/mm] doch immer eindeutig bestimmt. Kannst du mir das vielleicht erläutern (oder jemand anders)?
Alles Gute
Stefan
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 20:15 Mo 05.01.2004 | | Autor: | phymastudi |
hey vielen vielen Dankj Stefan.
Irre, was du draufhast.
Mega Respekt und nochmals vielen Dank für die Hilfe!!!#Gruß Björn
|
|
|
|
![[]](/images/popup.gif){kind=small}
http://www.math.tu-dresden.de/~meinecke/lehre/isy08.ps
