Tilman
216 lines
5.6 KiB
PHP
216 lines
5.6 KiB
PHP
<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN" "http://www.w3.org/TR/html4/loose.dtd">
|
|
<html>
|
|
<head>
|
|
<meta http-equiv="content-type" content="text/html; charset=ISO-8859-1">
|
|
<link rel="stylesheet" type="text/css" media="all" href="stylesheet.css">
|
|
<title>Algorithmen</title>
|
|
</head>
|
|
<body>
|
|
<span id="menu"><a href="index.php">zurück zur Liste</a></span>
|
|
|
|
<div id="buttons">
|
|
<form action="edit.php" method="POST">
|
|
<input type="hidden" name="filename" value="<?php echo $_SERVER['SCRIPT_FILENAME']?>">
|
|
<p>
|
|
<input type="submit" value="Seite bearbeiten">
|
|
</p>
|
|
</form>
|
|
</div>
|
|
|
|
<h1>Algorithmen</h1>
|
|
|
|
<h2>Huffman-Code</h2>
|
|
Der Huffman-Code wird zur verlustfreien Datenkompression eingesetzt und erzeugt einen Binärcode.<br><br>
|
|
<b>Verfahren</b><br>
|
|
Gegeben sind die Wahrscheinlichkeiten der Quellsymbole (z.B. Wörter in einem Text). <br>
|
|
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.<br><br>
|
|
<b>Beispiel</b><br>
|
|
Wir erzeugen einen optimalen Kode mit dem Huffman Algorithmus für die Verteilung (p<sub>1</sub>, ... , p<sub>6</sub>) = ( 8/25, 2/25, 1/25, 5/25, 5/25, 4/25).<br><br>
|
|
<table>
|
|
<tr>
|
|
<td><img src="huffman.gif"></td>
|
|
<td>
|
|
p<sub>1</sub> = 01<br>
|
|
p<sub>2</sub> = 0001<br>
|
|
p<sub>3</sub> = 0000<br>
|
|
p<sub>4</sub> = 10<br>
|
|
p<sub>5</sub> = 11<br>
|
|
p<sub>6</sub> = 001
|
|
</td>
|
|
</tr>
|
|
</table>
|
|
|
|
<h2>RSA - Rivest, Shamir und Adleman</h2>
|
|
Zum verschlüsselten Versenden von Daten werden ein <b>Private Key</b> und ein <b>Public Key</b> erzeugt.<br><br>
|
|
<b>Verfahren</b><br>
|
|
<ol>
|
|
<li>Finde zwei <b>Primzahlen p und q</b></li>
|
|
<li><b>n</b> = p*q</li>
|
|
<li><b>Φ(n)</b> = (p-1)*(q-1)</li>
|
|
<li>Finde <b>Primzahl e</b>, die mit Φ(n) keine gemainsamen Teiler hat.</li>
|
|
<li>Finde <b>d</b> mit (d*e) mod Φ(n) = 1</li>
|
|
<li><b>Private Key (d, n), Public Key (e, n)</b></li>
|
|
</ol>
|
|
<br>
|
|
|
|
<b>Beispiel</b><br>
|
|
<ol>
|
|
<li>p = 5, q = 7</li>
|
|
<li>n = 35</li>
|
|
<li>Φ(n)= 24</li>
|
|
<li>e = 11</li>
|
|
<li>d = 11, da 11*11 = 121 und 121 mod 24 = 1</li>
|
|
<li>Private Key (11, 35), Public Key (11, 35) ⇒ zufällig gleich</li>
|
|
</ol>
|
|
|
|
<br>
|
|
<h2>Knuth-Morris-Pratt - Verschiebefunktion</h2>
|
|
Um ein Wort in einem Text in O(n+m) zu finden wird der KMP-Algorithmus verwendet.<br><br>
|
|
|
|
<b>Verfahren</b><br>
|
|
<table>
|
|
<tr>
|
|
<td>Beispiel: </td>
|
|
<td>
|
|
Wort: <br>
|
|
Text:
|
|
</td>
|
|
<td>
|
|
abcaab <br>
|
|
abcabababcaabab
|
|
</td>
|
|
</tr>
|
|
</table>
|
|
<br>
|
|
|
|
<b>1. Verschiebefunktion aufstellen</b><br>
|
|
<table>
|
|
<tr>
|
|
<td>
|
|
abcaab<br>
|
|
a bcaab<br>
|
|
ab caab<br>
|
|
abc aab<br>
|
|
<b>a</b>bc<b>a</b> ab<br>
|
|
<b>a</b>bca<b>a</b> b<br>
|
|
</td>
|
|
<td>
|
|
⇒ 0<br>
|
|
⇒ 1<br>
|
|
⇒ 1<br>
|
|
⇒ 1<br>
|
|
⇒ 2<br>
|
|
⇒ 2<br>
|
|
</td>
|
|
</tr>
|
|
</table>
|
|
<br>
|
|
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.<br><br>
|
|
|
|
<table>
|
|
<tr>
|
|
<td>
|
|
Wort <br>
|
|
Stelle <br>
|
|
Verschiebefunktion f
|
|
</td>
|
|
<td>
|
|
abcaab <br>
|
|
123456 <br>
|
|
011122
|
|
</td>
|
|
</tr>
|
|
</table>
|
|
<br>
|
|
|
|
<b>2. Wort im Text suchen</b><br>
|
|
|
|
<table>
|
|
<tr>
|
|
<td><b>a</b></td>
|
|
<td><b>b</b></td>
|
|
<td><b>c</b></td>
|
|
<td><b>a</b></td>
|
|
<td><b>b</b></td>
|
|
<td><b>a</b></td>
|
|
<td><b>b</b></td>
|
|
<td><b>a</b></td>
|
|
<td><b>b</b></td>
|
|
<td><b>c</b></td>
|
|
<td><b>a</b></td>
|
|
<td><b>a</b></td>
|
|
<td><b>b</b></td>
|
|
<td><b>a</b></td>
|
|
<td><b>b</b></td>
|
|
</tr>
|
|
<tr>
|
|
<td>a<br>-</td>
|
|
<td>b<br>-</td>
|
|
<td>c<br>-</td>
|
|
<td>a<br>-</td>
|
|
<td>a<br>X</td>
|
|
<td>b</td>
|
|
<td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td>
|
|
<td><br>f(5) = 2</td>
|
|
</tr>
|
|
<tr>
|
|
<td></td>
|
|
<td></td>
|
|
<td></td>
|
|
<td><i>a</i></td>
|
|
<td>b<br>-</td>
|
|
<td>c<br>X</td>
|
|
<td>a</td>
|
|
<td>a</td>
|
|
<td>b</td>
|
|
<td></td><td></td><td></td><td></td><td></td><td></td>
|
|
<td><br>f(3) = 1</td>
|
|
</tr>
|
|
<tr>
|
|
<td></td>
|
|
<td></td>
|
|
<td></td>
|
|
<td></td>
|
|
<td></td>
|
|
<td>a<br>-</td>
|
|
<td>b<br>-</td>
|
|
<td>c<br>X</td>
|
|
<td>a</td>
|
|
<td>a</td>
|
|
<td>b</td>
|
|
<td></td><td></td><td></td><td></td>
|
|
<td><br>f(3) = 1</td>
|
|
</tr>
|
|
<tr>
|
|
<td></td>
|
|
<td></td>
|
|
<td></td>
|
|
<td></td>
|
|
<td></td>
|
|
<td></td>
|
|
<td></td>
|
|
<td>a<br>-</td>
|
|
<td>b<br>-</td>
|
|
<td>c<br>-</td>
|
|
<td>a<br>-</td>
|
|
<td>a<br>-</td>
|
|
<td>b<br>-</td>
|
|
<td></td><td></td>
|
|
<td><br>Wort gefunden</td>
|
|
</tr>
|
|
</table>
|
|
|
|
Wort stimmt an n-ter Stelle von Wort mit m-ter Stelle von Text nicht mehr überein.<br>
|
|
→ Weiter an (m+1)-ter Stelle in Text mit f(n)-ter Stelle in Wort.
|
|
|
|
<h2>Ackermann Funktion</h2>
|
|
Sie wiederlegt Hilberts Vermutung, dass jede berechnenbare Funktion, primitiv rekursiv ist.<br><br>
|
|
<code>
|
|
ack 0 x = x + 1<br>
|
|
ack x 0 = ack (x-1) x<br>
|
|
ack x y = ack(x-1) (ack x (y-1))<br>
|
|
</code>
|
|
<h2>Links</h2>
|
|
<a href="http://www.vameo.de/uni/tutorium/kmp.html">Implementierung vom KMP-Algorithmus von Augustin</a>
|
|
</body>
|
|
</html> |