matheraum.de
Raum für Mathematik
Offene Informations- und Nachhilfegemeinschaft

Für Schüler, Studenten, Lehrer, Mathematik-Interessierte.
Hallo Gast!einloggen | registrieren ]
Startseite · Forum · Wissen · Kurse · Mitglieder · Team · Impressum
Forenbaum
^ Forenbaum
Status Mathe
  Status Schulmathe
    Status Primarstufe
    Status Mathe Klassen 5-7
    Status Mathe Klassen 8-10
    Status Oberstufenmathe
    Status Mathe-Wettbewerbe
    Status Sonstiges
  Status Hochschulmathe
    Status Uni-Analysis
    Status Uni-Lin. Algebra
    Status Algebra+Zahlentheo.
    Status Diskrete Mathematik
    Status Fachdidaktik
    Status Finanz+Versicherung
    Status Logik+Mengenlehre
    Status Numerik
    Status Uni-Stochastik
    Status Topologie+Geometrie
    Status Uni-Sonstiges
  Status Mathe-Vorkurse
    Status Organisatorisches
    Status Schule
    Status Universität
  Status Mathe-Software
    Status Derive
    Status DynaGeo
    Status FunkyPlot
    Status GeoGebra
    Status LaTeX
    Status Maple
    Status MathCad
    Status Mathematica
    Status Matlab
    Status Maxima
    Status MuPad
    Status Taschenrechner

Gezeigt werden alle Foren bis zur Tiefe 2

Navigation
 Startseite...
 Neuerdings beta neu
 Forum...
 vorwissen...
 vorkurse...
 Werkzeuge...
 Nachhilfevermittlung beta...
 Online-Spiele beta
 Suchen
 Verein...
 Impressum
Das Projekt
Server und Internetanbindung werden durch Spenden finanziert.
Organisiert wird das Projekt von unserem Koordinatorenteam.
Hunderte Mitglieder helfen ehrenamtlich in unseren moderierten Foren.
Anbieter der Seite ist der gemeinnützige Verein "Vorhilfe.de e.V.".
Partnerseiten
Dt. Schulen im Ausland: Mathe-Seiten:Weitere Fächer:

Open Source FunktionenplotterFunkyPlot: Kostenloser und quelloffener Funktionenplotter für Linux und andere Betriebssysteme
StartseiteMatheForenKrypto,Kodierungstheorie,Computeralgebradiskrete Mathematik
Foren für weitere Schulfächer findest Du auf www.vorhilfe.de z.B. Informatik • Physik • Technik • Biologie • Chemie
Forum "Krypto,Kodierungstheorie,Computeralgebra" - diskrete Mathematik
diskrete Mathematik < Krypt.+Kod.+Compalg. < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
Ansicht: [ geschachtelt ] | ^ Forum "Krypto,Kodierungstheorie,Computeralgebra"  | ^^ Alle Foren  | ^ Forenbaum  | Materialien

diskrete Mathematik: Frage (beantwortet)
Status: (Frage) beantwortet Status 
Datum: 17:02 Sa 17.01.2004
Autor: phymastudi

Hi Ihr!

Wieder zwei für mich bedingt verständliche Aufgaben brechen mir meine Geduld.
Vileeicht darf ich eure wieder beasten?
wär super.
1. Ein linearer (n,k)-Code C heiße t-perfekt: [mm] \gdw [/mm] : es gibt für [mm] y\in [/mm] V  n genau ein [mm] c\in [/mm] C: d(y,c)<= t.
a) Warum kann es keinen 1-pe3rfekten linearen (3,2)-Code geben?
b) Welche notwendige Bedingung müssen n und k erfüllen, damit ein linearer (n,k)-Code eine Chance auf 1 Perfektheit besitzt? (Hinweis: Eine der folgenden Bedingungen für [mm] n\in \IN [/mm] ist richtig: n=2  r oder
n=2  r-1 mit [mm] r\in \IN [/mm]  oder n Primzahl)
c) Beweise oder widerlege: n=23 und k= 12 erfüllen die notwendige Bedingung für die Existenz eines 3-perfekten Codes.


2. Zur Eulerschen Phi-Funktion: [mm] \IN [/mm] geht zu [mm] \IN [/mm] , phi(n):=|[1 kleiner gleich k kleiner gleich n | ggt(k,n)=1]|:
a) Gesucht sind vier verschiedene [mm] n\in \IN [/mm]  mit phi(n)=4
b) Gesucht sind Primzahlen p und q mit pq=14803 und phi(pq)=14560

Ich hoffe ihr könnt mir irgendwie wieder weiterhelfen.
Vielen Dank!!!!
Euer Björn

        
Bezug
diskrete Mathematik: zu 2)
Status: (Antwort) fertig Status 
Datum: 18:32 Sa 17.01.2004
Autor: Stefan

Hallo Björn,

zu 1. muss ich erst was in dem Beutelspacher-Buch nachlesen.

Zu 2., das ist elementare Zahlentheorie, kann ich jetzt schon was sagen:

a) Einfach mal ausprobieren! Es geht zum Beispiel für [mm]n=5[/mm], [mm]n=8[/mm], [mm]n=10[/mm] und [mm]n=12[/mm].

Oder verstehst du die Definition von [mm]\phi(n)[/mm] nicht? Dann frage bitte nach.

b) Für eine Primzahl [mm]p[/mm] gilt:

[mm]\phi(p)=p-1[/mm]. (Warum? Überlege dir das bitte! Oder frage nach.)

Daher müssen die beiden folgenden Gleichungen erfüllt sein:

(I) [mm] p\cdot q = 14803[/mm]
(II) [mm](p-1)\cdot (q-1) = 14560[/mm]

Multipliziere (II) aus:

[mm]p\cdot q - p - q + 1 = 14560[/mm]

Zieht man die beiden Gleichungen voneinander ab und löst nach [mm]p[/mm] auf, so erhält man:

[mm]p=244-q[/mm].

Setze dies nun in (I) ein. Dann erhältst du zwei Lösungen für [mm]p[/mm] (und damit auch zwei Lösungen für [mm]q[/mm]). Die beiden Lösungen sind aber sozusagen symmetrisch, so dass du für das Problem eine Lösung erhältst.

Welche?

Melde dich mal mit einem Lösungsvorschlag...

Alles Gute
Stefan

Bezug
        
Bezug
diskrete Mathematik: zu 1a): Verständnisfragen
Status: (Antwort) fertig Status 
Datum: 00:14 So 18.01.2004
Autor: Stefan

Hallo Björn,

leider kenne ich hier die Definitionen nicht. Ich wollte sie im Beutelspacher nachlesen, aber sie stehen dort nicht. Benutzt ihr mittlerweile ein anderes Buch als Grundlage? Wenn ja, welches?

Vielleicht kannst du uns ja mal alle Dinge hier definieren. Dann bin ich mir sicher, dass Marc und ich (und vielleicht auch andere) die Aufgabe locker hinkriegen. (Jedenfalls dann, wenn sich der Schwierigkeitsgrad dieser Aufgabe im Bereich eurer bisherigen Aufgaben bewegt.) Hier meine Fragen:

1) Was ist ein (n,k)-Code? (falls es das alleine gibt)
2) Was ist ein linearer (n,k)-Code?
3) Was ist V?
4) Was ist d(y,c)? Ist dies eine Metrik? Wie ist sie definiert?

Sobald wir alle Definitionen haben, werden wir die Lösung hoffentlich (ich bin so vermessen zu sagen: mit Sicherheit) hinkriegen.

Aber hellsehen, was diese Begriffe bedeuten, kann ich leider nicht. ;-)

Alles Gute
Stefan

Bezug
                
Bezug
diskrete Mathematik: zu a): Verständnisfragen
Status: (Mitteilung) Reaktion unnötig Status 
Datum: 14:46 So 18.01.2004
Autor: phymastudi

Hi Stefan!

Klar! Sorry!
Also.
1. Jeder k-dimensionaler Untervektorraum von V  [mm] n={(a1,...,an)|ai\in {0,1}} [/mm] heisst linearer (n,k)-Code.

2. Ein (n,k)-Code ist ein Code mit Codewortlänge n und Dimension k. Beispiel. (3,1)-Code ist: {(o,o,o),(1,1,1)}. Dieser Code ist sogar ein Linearcode.

3. V ist ein Vektorraum

4. d ist der Hammingabstnad zweier Codewörter.
Seien x=(x1,...,xn) und y=(y1,...,yn) Codewörter eines beliebigen Codes. Dann heisst d(x,y):= [mm] |{i\in 71,...,n0
Bemerkung.
Das wired vermutlivch irgendwie mit einer Generatormatrix lösbar sein.

Vielen Dank für eure Mühen.

Bezug
                        
Bezug
diskrete Mathematik: zu a): Verständnisfragen
Status: (Mitteilung) Reaktion unnötig Status 
Datum: 16:10 So 18.01.2004
Autor: Stefan

Hallo Björn!

Weitere Verständnisfragen:

1) Ist es richtig, dass [mm]V[/mm] einfach der [mm]\IZ_2^n[/mm] ist, mit der üblichen Addition und skalaren Multiplikation?

2) Zu dieser Definition vonr dir:

> 1. Ein linearer (n,k)-Code C heiße [mm] t-perfekt:\gdw [/mm] : es gibt für [mm] y\in [/mm] V  n
> genau [mm] einc\in [/mm] C: d(y,c)<= t.

habe ich eine Frage: Muss es für jedes [mm]y \in V[/mm] ein von [mm]y[/mm] unabhängiges [mm]c \in C[/mm] mit [mm]d(y,c) \le t[/mm] geben oder darf [mm]c[/mm] von [mm]y[/mm] abhängen?

3) Was ist in diesem Fall eine Generatormatrix? Schreibe uns mal ein komplettes Beispiel dazu hier ins Forum.

Mir ist die ganze Struktur noch nicht so klar (dir, Marc?), von daher kann ich mich mit der Aufgabe auch noch nicht so richtig beschäftigen. Wir brauchen erst einmal alle Infos um das Drumherum. Du solltest es so erklären, dass  jemand, der nie in der Vorlesung war, versteht, worum es geht. Versuche bitte erst einmal die Fragen 1)-3) zu beantworten.

Es wäre nett, wenn du unsere mathematische Eingabehilfe korrekt benutzen würdest, dann kann man deine Texte auch besser lesen.

Wir helfen dir dann weiter, sobald alle Fragen geklärt sind.

Alles Gute
Stefan

Bezug
                                
Bezug
diskrete Mathematik: zu a): Verständnisfragen
Status: (Mitteilung) Reaktion unnötig Status 
Datum: 18:17 So 18.01.2004
Autor: Marc

Hallo zusammen,

> 1) Ist es richtig, dass [mm]V[/mm] einfach der [mm]\IZ_2^n[/mm] ist, mit der
> üblichen Addition und skalaren Multiplikation?

Ich vermute (auch), ja.

> 2) Zu dieser Definition vonr dir:
>
> > 1. Ein linearer (n,k)-Code C heiße [mm] t-perfekt:\gdw [/mm] : es
> gibt für [mm] y\in [/mm] V  n
> > genau [mm] einc\in [/mm] C: d(y,c)<= t.
>
> habe ich eine Frage: Muss es für jedes [mm]y \in V[/mm] ein von [mm]y[/mm]
> unabhängiges [mm]c \in C[/mm] mit [mm]d(y,c) \le t[/mm] geben oder darf [mm]c[/mm] von
> [mm]y[/mm] abhängen?

Das kann im Hinblick auf die 1. Frage doch nicht so schwierig herzuleiten sein (als Ansporn für mich gedacht), denn V hat doch nur 8 Vektoren:
{000, 001, 010, 011, 100, 101, 110, 111}

Und diese 2-dim Untervektorräume:
{000, 001, 010, 011}
{000, 001, 100, 110}
{000, 010, 100, 110}
{000, 001, 100, 110}

{000, 111, 001, 110}
{000, 111, 010, 101}
{000, 111, 100, 011}

{000, 110, 011, 101}

(Gibt es mehr?)

Davon rechne ich gleich mal die Hammingabstände aus...

> 3) Was ist in diesem Fall eine Generatormatrix? Schreibe
> uns mal ein komplettes Beispiel dazu hier ins Forum.

Keine Ahnung.

Bis gleich,
Marc.

Bezug
                                        
Bezug
diskrete Mathematik: zu a): Verständnisfragen
Status: (Mitteilung) Reaktion unnötig Status 
Datum: 18:44 So 18.01.2004
Autor: Marc

Hallo zusammen,

aus dem Bauch heraus würde ich sagen, dass das c für jedes y einzeln zu finden sein muß und dass dabei noch wichtig ist, dass es nur genau ein c gibt.
Denn V enthält ja Wörter, die möglich sind, C nur solche, die tatsächlich gültig sind. Ein 1-perfekter Code würde dann für jedes mögliche Wort aus V, das nur einen (Übertragungs-) Fehler enthält, eindeutig auf das gültige Wort c schließen lassen, also zur Fehlererkennung wäre auch noch eine Korrektur möglich.
Ein 2-perfekter Code erlaubt sogar zwei Fehler, da diese erkannt und sogar verbessert werden können.

Das ist aber sehr vage von mir vermutet/geraten.

Ich bleibe dran,
Marc.

Bezug
                                        
Bezug
diskrete Mathematik: zu a): Verständnisfragen
Status: (Mitteilung) Reaktion unnötig Status 
Datum: 18:59 So 18.01.2004
Autor: Marc

Hallo zusammen,

>  V={000, 001, 010, 011, 100, 101, 110, 111}
>  
> Und diese 2-dim Untervektorräume:
>  {000, 001, 010, 011}
>  {000, 001, 100, 110}
>  {000, 010, 100, 110}
>  {000, 001, 100, 110}
>  
> {000, 111, 001, 110}
>  {000, 111, 010, 101}
>  {000, 111, 100, 011}

Alle diese Unterräume kommen für C nicht in Frage, da sie Vektoren enthalten, die nur genau eine 1 haben; für diesen Vektor gilt dann
d(000,001)=d(000,010)=d(000,100)=1
Da aber sowieso gilt
d(000,000)=0
gibt es bei all diesen Vektorräumen für 000 kein eindeutig bestimmtes c mit d(000,c)<=1.
  

> {000, 110, 011, 101}

000: d(000,000)=0, d(000,110)=2, d(000,011)=2, d(000,101)=2 (c eindeutig bestimmt)
001: d(001,000)=1, d(001,110)=3, d(001,011)=1 (c nicht eindeutig bestimmt)

Also gibt es keinen (3,2)-Code, der 1-perfekt ist.

Bin mal gespannt, welche Empörungsstürme jetzt auf mich niedergehen...

Marc.


Bezug
                                                
Bezug
diskrete Mathematik: zu a): Verständnisfragen
Status: (Mitteilung) Reaktion unnötig Status 
Datum: 20:40 So 18.01.2004
Autor: Stefan

Lieber Marc,

aha, so langsam kapiere selbst ich den Witz hier.

Kling logisch, ja. ;-)

Liebe Grüße
Stefan

Bezug
        
Bezug
diskrete Mathematik: Antwort
Status: (Antwort) fertig Status 
Datum: 21:54 So 18.01.2004
Autor: Stefan

Hallo zusammen,

ich habe 1b) und 1c) gelöst.

Hallo Björn, schaue doch nachher einfach noch mal ins Forum. :-)

Bin gerade noch am Telefonieren...

Bis nachher!
Alles Gute
Stefan

Bezug
        
Bezug
diskrete Mathematik: Zu 1 b)/c)
Status: (Antwort) fertig Status 
Datum: 23:30 So 18.01.2004
Autor: Stefan

Hallo Björn,

jetzt habe ich dank Marc die Aufgabenstellung endlich verstanden. Damit war, wie bereits vermutet, das größte Problem aus dem Weg geräumt, der Rest war dann mehr oder weniger eine kombinatorische Fingerübung.

zu b) Wieviel Elemente haben [mm]V[/mm] und [mm]C[/mm] ?

[mm]V[/mm] hat [mm]2^n[/mm] und [mm]C[/mm] hat [mm]2^k[/mm] Elemente. Die Elemente aus [mm]V[/mm] lassen sich jetzt aber auf eineindeutige Weise den Elementen aus [mm]C[/mm] zuordnen. Jedes [mm]x \in V[/mm] orden wir demjenigen (nach Voraussetzung eindeutig bestimmten!) [mm]c(x)[/mm] aus [mm]C[/mm] zu, so dass [mm]d(x,c(x))\le 1[/mm] gilt. Damit haben wir eine Partition der Menge [mm]V[/mm] gefunden.

[mm]V[/mm] lässt sich als disjunkte Vereinigung darstellen:

[mm]V = M(c_1) \cup \ldots \cup M(c_{2^k})[/mm],

wobei [mm]x \in M(c_i)[/mm] genau dann gilt, wenn [mm]d(x,c_i) \le 1[/mm] gilt.

Jedes [mm]M(c_i)[/mm] ist jedoch gleichmächtig. Denn in [mm]M(c_i)[/mm] liegen neben [mm]c_i[/mm] selbst (also dem Element aus [mm]V[/mm], das zu [mm]c_i[/mm] den Abstand 0 hat) alle Elemente aus [mm]V[/mm], die zu [mm]c_i[/mm] den Abstand 1 haben. Aber klar ist: Diese erreicht man genau dadurch, dass man genau eine Komponente von [mm]c_i[/mm] verändert. Da [mm]c_i[/mm] genau [mm]n[/mm] Komponenten hat, gilt:

[mm]|M(c_i)| = 1 + n[/mm] für alle [mm]i=1,\ldots, 2^k[/mm].

Es muss also notwendigerweise die Beziehung

[mm]|C| \cdot |M(c_i)| = |V|[/mm],

also:

[mm]2^k \cdot (1+n) = 2^n[/mm]

gelten, also

[mm]n = 2^{n-k} - 1[/mm].

(Insbesondere muss [mm]n[/mm] notwendigerweise ungerade sein.)

Rückblick auf a):

Es kann keinen 1-perfekten (3,2)-Code geben, da

[mm]3 \ne 1 = 2^{3-2}-1[/mm]

gilt.

Nun zu c):

Die Argumentation geht wie in b):

[mm]V[/mm] lässt sich als disjunkte Vereinigung darstellen:

[mm]V = M(c_1) \cup \ldots \cup M(c_{2^k})[/mm],

wobei [mm]x \in M(c_i)[/mm] genau dann gilt, wenn [mm]d(x,c_i) \le 3[/mm] gilt.

Jedes [mm]M(c_i)[/mm] ist jedoch gleichmächtig. Denn in [mm]M(c_i)[/mm] liegen neben [mm]c_i[/mm] selbst (also dem Element aus [mm]V[/mm], das zu [mm]c_i[/mm] den Abstand 0 hat) alle Elemente aus [mm]V[/mm], die zu [mm]c_i[/mm] den Abstand 1, 2 oder 3 haben. Aber klar ist: Diese erreicht man genau dadurch, dass man genau eine Komponente von [mm]c_i[/mm], genau zwei Komponenten und genau drei Komponenten verändert. Dafür gibt es genau [mm]n[/mm], [mm]{n \choose 2}[/mm] und [mm]{n \choose 3}[/mm] Möglichkeiten. Es folgt also in diesem Fall (systematisch aufgeschrieben, damit du das System erkennst):

[mm]|M(c_i)| = {n \choose 0} + {n \choose 1} + {n \choose 2} + {n \choose 3} = 1 + n + {n \choose 2} + {n \choose 3}[/mm]

für alle [mm]i=1,\ldots, 2^k[/mm].

Es muss also notwendigerweise die Beziehung

[mm]|C| \cdot |M(c_i)| = |V|[/mm],

also:

[mm]2^k \cdot (1+n+ {n \choose 2} + {n \choose 3}) = 2^n[/mm]

gelten,

also:

[mm]1+n+ {n \choose 2} + {n \choose 3} = 2^{n-k}[/mm].

Diese notwendige Bedingung  ist für [mm]n=23[/mm] und [mm]k=12[/mm] erfüllt, denn

[mm]1 + 23 + {23 \choose 2} + {23 \choose 3} = 2048 = 2^{11} = 2^{23-12}[/mm].

Gute Nacht!
Stefan

Bezug
                
Bezug
diskrete Mathematik: Zu 1 b)/c)
Status: (Mitteilung) Reaktion unnötig Status 
Datum: 20:27 Mo 19.01.2004
Autor: phymastudi

Hallo Stefan, Hallo MArc!

Erneut erstmal vielen Dank für eure Hilfe. Wenn man erstmal die Lösung vor Augen hat sieht alles so logich aus.
Manchmal denke ich, ich bin einfach zu blöd, aber dann habe ich auch wieder Sternstunden, bei denen ich schwere Aufgaben ganz allein lösen kann.
Ich habe mittlerweile ein ziemlich schlechtes Gewissen, weil ich nur mit Fragen auftrete und mich doch auch gern mal produktiv einbringen möchte. Doch ich bin in meiner Mathematik, iwe ihr ja merkt, selbst noch sehr unsicher und Fragen zu anderen Klassenstufen sind immer schon beantwortet, ehe man sich beteiligen kann.
Daher hoffe ich nicht, dass ihr mir allzu böse seid.

Gruß Björn

Bezug
                        
Bezug
diskrete Mathematik: Zu 1 b)/c)
Status: (Mitteilung) Reaktion unnötig Status 
Datum: 20:37 Mo 19.01.2004
Autor: Stefan

Hallo Björn,

wir freuen uns über jede Unterstützung. :-) Das ist auch der Sinn einer Gemeinschaft, dass jeder hilft.

Dennoch ist dies keine Pflicht, und sauer sind wir ganz sicher nicht. Man kann sich auch auf andere Weise im Forum einbringen: auf das Forum hinweisen, Aufgaben mit Lösungen in unsere Datenbank einfügen, Korrektur lesen etc. Es gibt viele Möglichkeiten. Sollte etwas Interessantes für dich dabei sein, wo du dich einbringen möchtest, würden wir uns darüber sehr freuen. :-)

Viele Grüße
Stefan

Bezug
Ansicht: [ geschachtelt ] | ^ Forum "Krypto,Kodierungstheorie,Computeralgebra"  | ^^ Alle Foren  | ^ Forenbaum  | Materialien


^ Seitenanfang ^
www.matheraum.de
[ Startseite | Forum | Wissen | Kurse | Mitglieder | Team | Impressum ]