zurück zur Liste

Algorithmen

Huffman-Code

Der Huffman-Code wird zur verlustfreien Datenkompression eingesetzt und erzeugt einen Binärcode.

Verfahren
Gegeben sind die Wahrscheinlichkeiten der Quellsymbole (z.B. Wörter in einem Text).
Der Huffman-Algorithmus baut einen binären Codebaum rekursiv auf, indem er jeweils die zwei Symbole mit den kleinsten Wahrscheinlichkeiten zu einem Teilbaum zusammenfasst. Dieser Teilbaum geht dann als ein neues Symbol mit der Summe der Wahrscheinlichkeiten der zusammengefassten Symbole in den weiteren Verlauf des Algorithmus ein.

Beispiel
Wir erzeugen einen optimalen Kode mit dem Huffman Algorithmus für die Verteilung (p1, ... , p6) = ( 8/25, 2/25, 1/25, 5/25, 5/25, 4/25).

p1 = 01
p2 = 0001
p3 = 0000
p4 = 10
p5 = 11
p6 = 001

RSA - Rivest, Shamir und Adleman

Zum verschlüsselten Versenden von Daten werden ein Private Key und ein Public Key erzeugt.

Verfahren
  1. Finde zwei Primzahlen p und q
  2. n = p*q
  3. Φ(n) = (p-1)*(q-1)
  4. Finde Primzahl e, die mit Φ(n) keine gemainsamen Teiler hat.
  5. Finde d mit (d*e) mod Φ(n) = 1
  6. Private Key (d, n), Public Key (e, n)

Beispiel
  1. p = 5, q = 7
  2. n = 35
  3. Φ(n)= 24
  4. e = 11
  5. d = 11, da 11*11 = 121 und 121 mod 24 = 1
  6. Private Key (11, 35), Public Key (11, 35) ⇒ zufällig gleich

Knuth-Morris-Pratt - Verschiebefunktion

Um ein Wort in einem Text in O(n+m) zu finden wird der KMP-Algorithmus verwendet.

Verfahren
Beispiel: Wort:
Text:
abcaab
abcabababcaabab

1. Verschiebefunktion aufstellen
abcaab
a bcaab
ab caab
abc aab
abca ab
abcaa b
⇒ 0
⇒ 1
⇒ 1
⇒ 1
⇒ 2
⇒ 2

Es werden alle Prefixe p des Wortes durchgegangen. Die Verschiebefunktion ist die Länge des längsten Prefixes von p, was gleichzeitig auch Suffix von p ist, + 1. Nur die Verschiebefunktion des ersten Prefixes ε ist 0.

Wort
Stelle
Verschiebefunktion f
abcaab
123456
011122

2. Wort im Text suchen
a b c a b a b a b c a a b a b
a
-
b
-
c
-
a
-
a
X
b
f(5) = 2
a b
-
c
X
a a b
f(3) = 1
a
-
b
-
c
X
a a b
f(3) = 1
a
-
b
-
c
-
a
-
a
-
b
-

Wort gefunden
Wort stimmt an n-ter Stelle von Wort mit m-ter Stelle von Text nicht mehr überein.
→ Weiter an (m+1)-ter Stelle in Text mit f(n)-ter Stelle in Wort.

Ackermann Funktion

Sie wiederlegt Hilberts Vermutung, dass jede berechnenbare Funktion, primitiv rekursiv ist.

ack 0 x = x + 1
ack x 0 = ack (x-1) x
ack x y = ack(x-1) (ack x (y-1))

Links

Implementierung vom KMP-Algorithmus von Augustin