"Ausgewaehlte Kapitel der th Informatik 001.ps.gz" - читать интересную книгу автора

Martin-Luther-Universit"at Halle-Wittenberg

Institut f"ur Informatik Prof. Dr. L. Staiger, Dipl.- Math. Ralf Stiebe

Skript zur Vorlesung Ausgew"ahlte Kapitel der Theoretischen

Informatik

Wintersemester 1996, Version vom 16.4.97

Inhaltsverzeichnis 1 Halbgruppen und Monoide 2

1.1 Halbgruppen und Monoide . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 1.2 Eigenschaften von W"ortern . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 1.3 Automaten und Halbgruppen . . . . . . . . . . . . . . . . . . . . . . . . . 8

2 Codes 9

2.1 Pr"afix-Codes und B"aume . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12

3 Sprachentheoretische Eigenschaften von Codes 17

3.1 Der Satz von Sardinas und Petterson . . . . . . . . . . . . . . . . . . . . . 17 3.2 Maximalit"at und Vollst"andigkeit . . . . . . . . . . . . . . . . . . . . . . . . 20 3.3 Decodierverz"ogerung . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24

4 Kryptologie 26

4.1 Klassische Verfahren / Symmetrische Verfahren . . . . . . . . . . . . . . . 26

4.1.1 Monoalphabetische Verfahren . . . . . . . . . . . . . . . . . . . . . 26 4.1.2 Polyalphabetische Verfahren . . . . . . . . . . . . . . . . . . . . . . 28 4.2 Asymmetrische Verfahren / Public Key Kryptographie . . . . . . . . . . . 30

4.2.1 Darstellung des Grundgedanken asymmetrischer Verfahren . . . . . 30 4.2.2 Zahlentheoretische Grundlagen . . . . . . . . . . . . . . . . . . . . 30 4.3 Primzahltests . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33 4.4 RSA - Verfahren . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34 4.5 Elektronische Unterschriften . . . . . . . . . . . . . . . . . . . . . . . . . . 35

5 Kolmogorov Komplexit"at 35

5.1 Anwendungen der Kolmogorov Komplexit"at . . . . . . . . . . . . . . . . . 39

6 Kolmogorov Komplexit"at unendlicher Folgen 40 7 EA auf unendlichen W"ortern 43

7.1 Topologie in X! . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48