Zusammenfassung (Diskrete)

Aus Infostudium Wiki

Inhaltsverzeichnis

1 Zählen
2 Gruppentheorie
3 Siebformel
4 Möbiusinversion
5 Graphentheorie
6 Euklidische Ringe
7 RSA
8 Endliche Körper
9 Codes

Zählen

	geordnet	ungeordnet
zur.	$\| S (n, k) \| = n k$
o. zur.

Gruppentheorie

$G$ , $H$ endliche Gruppen, Homomorphismus dann gilt

, und .

$G$ operiert auf $M$ mit falls , und .

Bahn:

$| F i x M (g) | = | F i x M (h g) |$

$G$ operiert auf $G$ durch Linksmultiplikation und Konjugation.

$G$ operiere auf $M$ , Anzahl der Bahnen sei $n$ , . // In dem Cup muss noch ein Punkt hinein

Färbungen: $M$ Menge, Symmetriegruppe, $A$ Farben, Färbungen. Bestimme Zykeltypen der Konjugationsklassen und Anzahl der Elemente (meist durch $W$ bestimmen). Anzahl der Färbungen:

Achtung: Einerzykel mitzählen!

Siebformel

Sei $M$ Menge, $N = {1,..., n}$ , , , .

oder

, Funktionen. Äquivalent sind:

und

Äquivalente Formulierung:

und

, . Äquivalent sind:

und

Möbiusinversion

Eine partiell geordnete Menge ist eine Menge $M$ mit einer reflexiven ( ), antisymmetrischen ( ) und transitiven ( ) Relation . Aus der Relation kann eine Totalordnung konstruiert werden.

Inzidenzalgebra von :

Parser-Fehler (PNG-Konvertierung fehlgeschlagen; korrekte Installation von LaTeX und dvipng überprüfen (oder dvips + gs + convert)): \iota_\underline{\triangleleft}

ist die charakteristische Funktion von  :

Parser-Fehler (PNG-Konvertierung fehlgeschlagen; korrekte Installation von LaTeX und dvipng überprüfen (oder dvips + gs + convert)): \iota_\underline{\triangleleft}(x,y) = 1

für ,  $0$  sonst Parser-Fehler (PNG-Konvertierung fehlgeschlagen; korrekte Installation von LaTeX und dvipng überprüfen (oder dvips + gs + convert)): \mu_\underline{\triangleleft} = (\iota_\underline{\triangleleft})^{-1}
(inverse Matrix).

Klassische Möbiusfunktion der Zahlentheorie: mit

$(μ(1) = 1)$

Klassische Möbiusinversion: . Äquivalent sind:

und

Graphentheorie

$μ(G) = | E | - | V | + κ = m - n + κ$

$G = (V, E, f)$ Wald $μ(G) = 0$

Eine endliche Folge mit , heißt Kantenzug, falls $f (e i) = {v i - 1, v i}$ für alle .

$K$ heißt offen
$K$ heißt geschlossen $v 0 = v n$
$K$ heißt Weg
$K$ heißt Kreis

und $v 0 = v n$

mit $A v, w = | f - 1 ({{v, w}}) |$ (Anzahl Kanten zwischen $v$ und $w$ ) Adjazenzmatrix von $G$ .

Euklidische Ringe

( )

zu lang und eh klar: (  )
 $G$  zyklisch :

teilerfremd

$(a 1),(a 2)$ teilerfremd $g g T (a 1, a 2) = 1$

$I 1,..., I k$ paarweise teilerfremd, dann:

und

$p$ Primzahl, :

für $p > 2$

für $p = 2$ ,

,

Invertieren in $(R / (f)) *$ : $[a] - 1 = [x]$ falls $x a + y f = 1$ also Euklid mit $f$ und $a$ ausführen und nach $1$ auflösen.

Kongruenzsystem lösen: , dann nach $1$ auflösen und nur den Teil mit nehmen, dieser ist und für .

RSA

$p, q$ Prim. Öffentlich: und $v$ mit $g g T (v,(p - 1)(q - 1)) = 1$ . Privat: $e$ mit .

für

Endliche Körper

für

ist -Automorphismus

Zech-Logarithmus: $α$ primitiv ( $< α > = K *$ )

$α i + α j = α i (1 + α j - i) = α i α l (j - i) = α i + l (j - i)$

Teilkörper von $d | f$

irreduzibel normiert von Grad $f$

$f (X)$ zerfällt in pw. versch. norm. irred. Polynome $g g T (f (X), f'(X)) = 1$

$P n$ ist die Menge der norm. irred. Polynome von Grad $n$

Codes

$C$ Code der Länge $N$ : ,

Informationsrate:

Hamming-Abstand:

Gewicht: $w (x) = d (x,0)$ ,

Minimalabstand:

Dreiecksungleichung:

MDD: $f$ mit

$e$ Fehler bei der Übertragung:

(fehlerhafte Übertragung wird erkannt)

Lineare Codes

Erzeugermatrix zu $C$ : Zeilen erzeugen $C$

, $N$ Länge, $k$ Dimension von $C$

Prüfmatrix: , denn

$d (C) = 1 + R a n g (H)$

Syndrom

Syndrom von $x$ :

für

ist ein MDD mit $s$ Syndrom von $a$ und $a s$ minimaler Vertreter, also .

Hamming Codes

$q$ Primzahlpotenz,

, , $k = N - r$ , der Code wird auch mit $H N (q)$ bezeichnet.

Prüfmatrix: Zeilen sind die Erzeuger der 1-dimensionalen Teilräume von

$d (H N (q)) = 3$ , perfekter Code mit $e = 1$

Perfekte Codes

$C$ perfekt falls eine eine Zahl $e$ existiert, so dass für alle genau ein existiert mit .

Perfekte Codes:

Hammingcode $e = 1$ .

Wiederholungscode ${(0,...,0),(1,...,1)}$ über mit $N$ ungerade

Golay Code $G 23$ , $N = 23$ , $k = 12$ , $d (G 23) = 7$ $e = 3$

Ist $C$ ein perfekter binärer Code, so gilt:

$e = 1$ Hamming-Code

$e > 1$ Wiederholungscode oder Golay Code $G 23$

Erweiterter Code

Für lineare binäre Codes gilt: gerade, also für $d (C)$ ungerade ist .

Zyklische Codes

, pw. versch. norm. irred. Polynome.

$2 t$ Ideale aus Produkten von $f i$ in

Erzeugerpolynom $g (X)$ ist ein Produkt aus $f i$ s für einen zyklischen Code der Länge $N$ : $g N - k X k + g N - k - 1 X k - 1 + ... + g 0$ . Dann ist die Erzeugermatrix

Prüfpolynom

Codieren: . Betrachte $u$ als Koeffizienten für ein Polynom. Führe Polynomdivision von durch mit Rest $r$ , dann ist das Codewort zu $u$ .

$α$ ist eine primitive $N$ -te Einheitswurzel falls $α$ eine Nullstelle von $X N - 1$ ist und

Designierter Minimalabstand:

Wenn $g | X N - 1$ , $α$ primitive $N$ -te Einheitswurzel und $r$ aufeinanderfolgende Potenzen $α b,α b + 1,...,α b + r - 1$ Nullstellen von $X N - 1$ existieren

Decodieren: , $r (X)$ Polynom zum empfangenen Wort, $α$ primitive Einheitswurzel mit erster Nullstelle der Folge $α$ .

Bestimme und , sodass mit Hilfe von Koeffizientenvergleich für $Z$ bis $Z 2 t$ . Fehler an Stelle $i$ $σ(α - i) = 0$ . Korrektur: Addiere zum Koeffizienten von $i$ : .