Einige effiziente Algorithmen in der Codierungstheorie
| Talking persons: |
| Dr. Ulrich Tamm |
| Abstract: |
| 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. |
| Times: |
| Thursday 30th January 2003, 9.15 am, room 1/208 |
