Einige effiziente Algorithmen in der Codierungstheorie
| Vortragende(r): |
| Dr. Ulrich Tamm |
| Inhalt: |
| Zunächst wird ein Verfahren zur Speicherung binärer Bäume vorgestellt, das durch neuere Algorithmen zur Datenkompression motiviert ist. Die Bäume werden dabei über so genannte Ballot-Folgen als Bitsequenzen eincodiert. Der erhaltene Code hat die Prefix-Eigenschaft (kein Wort ist Anfang eines anderen) und erfüllt die Kraft-Ungleichung mit Gleichheit. Ein zweiter Algorithmus, dessen Analyse überraschenderweise auf ähnlichen mathematischen Methoden beruht, ist die schnelle Invertierung einer Hankel-Matrix (bei Hankel-Matrizen stehen auf den Nebendiagonalen a(ij) für feste Summe i+j immer dieselben Einträge). Matrizen-Inversion, die normalerweise O(n3) viele Schritte benötigt, kann für solche Matrizen in O(n2) Schritten durchgeführt werden. Dies ist ein entscheidender Geschwindigkeitsgewinn für wichtige Decodier-Algorithmen. |
| Zeiten: |
| Donnerstag, der 30.01.2003, 09:15 Uhr, Raum 1/208 |
