Vorwort

Inhaltsverzeichnis VI

Abbildungssverzeichnis XII
I Grundlagen
1 Mengen und Einführung in die Logik 5
1.1 Definition von Mengen 5
1.2 Aussagenlogik 9
1.2.1 Alphabet der Aussagenlogik 9
1.2.2 Syntax der Aussagenlogik — aussagenlogische Formeln 9
1.2.3 Semantik aussagenlogischer Formeln 10
1.2.4 Logische Folgerung 14
1.2.5 Kalküle 16
1.2.6 Aussagenlogische Äquivalenzen 18
1.2.7 Normalformen und aussagenlogische Basen 19
1.2.8 Resolutionskalkül 22
1.3 Prädikatenlogik 25
1.3.1 Alphabet der Prädikatenlogik 26
1.3.2 Syntax der Prädikatenlogik — prädikatenlogische Formeln . 26
1.3.3 Semantik der Prädikatenlogik 28
1.4 Beweismethoden 31
1.4.1 Direkter Beweis 32
1.4.2 Indirekter Beweis 33
1.4.3 Beweis durch Widerspruch 33
1.4.4 Ringschluss 34
1.5 Teilmengen 34
1.6 Operationen auf Mengen 36
1.7 Boolesche Algebra 39
1.8 Übungen 43

2 Relationen und Funktionen 47
2.1 Relationen 48
2.1.1 Ordnungen 51
2.1.2 Äquivalenzrelationen 52
2.2 Umkehrrelationen und Komposition von Relationen 55
2.2.1 Umkehrrelationen 55
2.2.2 Komposition von Relationen 56
2.2.3 Reflexiv-transitive Hüllen 57
2.3 Funktionen 57
2.4 Übungen 61

3 Induktion und Rekursion 63
3.1 Peano-Axiome: Definition von N 63
3.2 Vollständige Induktion 64
3.3 Rekursion 67
3.3.1 Fibonacci-Zahlen 70
3.3.2 Ackermannfunktion 72
3.4 Verallgemeinertes Rekursionsschema 75
3.5 Alphabete, Wörter, Sprachen 77
3.6 Übungen 80

II Zahlenmengen 83

4 Die Menge der natürlichen Zahlen 87
4.1 Rechenregeln 87
4.2 Abzählbarkeit 89
4.3 Übungen 91

5 Die Menge der ganzen Zahlen 93
5.1 Definition von Z 93
5.2 Rechenregeln in Z 95
5.3 Abzählbarkeit von Z 96
5.4 Übungen 96

6 Die Menge der rationalen Zahlen 97
6.1 Definition von Q 97
6.2 Rechenregeln in Q 98
6.3 Abzählbarkeit von Q 99
6.4 Übungen 100

7 Die Menge der reellen Zahlen 101

8 Darstellungen natürlicher Zahlen 103
8.1 b-adische Darstellung 103
8.1.1 Stellenwertsysteme 104
8.1.2 Divisionsrestverfahren 105
8.2 Addition 6-adischer Zahlen 107
8.3 Multiplikation 6-adischer Zahlen 108
8.4 Übungen 109

9 Ganze Zahlen. Subtraktion 111
9.1 Vorzeichen-/Betrags-Darstellung 111
9.2 Komplementdarstellungen. Subtraktion 112
9.2.1 Das 6-Komplement 112
9.2.2 Addition in 6-Komplementdarstellung 116
9.3 Übungen 121

10 Gleitpunktzahlen 123
10.1 Festpunktdarstellung 123
10.2 Umwandlung Dezimalbruch in Dualbruch 124
10.3 Gleitpunktdarstellung 125
10.3.1 Normalisierte Darstellung 126
10.3.2 Rechnerinterne Darstellung 127
10.4 Addition und Subtraktion von Gleitpunktzahlen 128
10.5 Übungen 130

III Einführung in die elementare Kombinatorik 133

11 Permutationen 137
11.1 Permutationen ohne Wiederholung 137
11.2 Permutationen mit Wiederholung 140
11.3 Übungen 140

12 Kombinationen 141
12.1 Kombinationen ohne Wiederholung 141
12.2 Kombination mit Wiederholung 142
12.3 Übungen 143
13 Binomialkoeffizienten 145

IV Einführung in die Zahlentheorie 149

14 Teilbarkeit und Primzahlen 153
14.1 Größter gemeinsamer Teiler 155
14.2 Euklidischer Algorithmus 157
14.3 Vollkommene Zahlen 160
14.4 Primzahlen 162
14.5 Offene Fragen 165
14.6 Übungen 166

V Algebraische Strukturen 169

15 Einführung 173

16 Halbgruppen 179
16.1 Unterhalbgruppen 180
16.2 Halbgruppenhomomorphismen 181
16.3 Kongruenzrelationen 184
16.4 Übungen 187

17 Gruppen 189
17.1 Gruppenisomorphismen 190
17.2 Zyklische Gruppen 193
17.3 Untergruppen 194
17.3.1 Permutationsgruppen 195
17.3.2 Der Satz von Lagrange 197
17.3.3 Elementordnungen 200
17.3.4 Der Kleine Satz von Fermat 203
17.4 Übungen 205

18 Ringe und Körper 207
18.1 Ringe 207
18.2 Körper 208
18.2.1 Rechenregeln in Körpern 209
18.2.2 Unterringe, Unterkörper, Ring- und Körperhomomorphismen 210
18.2.3 Körpererweiterungen 211
18.2.4 Nullteiler. Invertierbare und nicht invertierbare Elemente Einheitengruppe 212
18.3 Restklassenringe und Primkörper 214
18.4 Chinesischer Restsatz 217
18.5 Polynomringe und -körper 224
18.5.1 Definitionen und grundlegende Eigenschaften 224
18.5.2 Teilbarkeit und Euklidischer Algorithmus 225
18.5.3 Quotientenringe und Irreduzibilität 228
18.5.4 Anwendungsbeispiel: Kanalcodierung 230
18.5.5 Einsetzungen in Polynome. Nullstellen 231
18.6 Primzahltests 232
18.7 Primitivwurzeln und diskreter Logarithmus 238
18.8 Übungen 242

VI Einführung in die Kryptologie 245

19 Einfache Chiffriersysteme 249
19.1 Verschiebe- und Tauschchiffren 249
19.1.1 Cäsar-Chiffre 249
19.1.2 Tauschchiffren 250
19.2 Kryptoanalyse 252
19.3 Weitere Tauschchiffren. Vigenere-Chiffre 253

20 Perfekte Sicherheit und One time pad-Verfahren 257
20.1 Perfekte Sicherheit 257
20.2 One-Time-Pad 257
20.3 Lineare Schieberegister 258

21 Public key-Systeme 261
21.1 Einwegfunktionen 261
21.2 Das RSA-Verfahren 263
21.3 Der Diffie-Hellman-Schlüsselaustausch 270
21.4 Das ElGamal-Verfahren 271
21.5 Signaturen 273
21.6 Übungen 275

VII Lineare Algebra 277

22 Vektorräume 281
22.1 Grundlegende Definitionen und Eigenschaften 281
22.2 Lineare Unabhängigkeit 285
22.3 Basis und Dimension eines Vektorraums 288
22.4 Lineare Abbildungen 289
22.5 Orthogonalräume 292
22.6 Übungen 294

23 Lineare Gleichungssysteme und Matrizen 297
23.1 Matrizen 297
23.2 Lineare Gleichungssysteme 299
23.3 Determinanten 304
23.4 Inverse Matrizen 309
23.5 Übungen 311

VIII Einführung in die Codierungstheorie 313

24 Einfache Codes 319
24.1 Block-Codes 319
24.1.1 Repititionscode 320
24.1.2 Codes mit Paritätsbit 321
24.1.3 Codes mit Blocksicherung 322
24.2 Linearcodes 322
24.3 Übungen 329

25 Perfekte Codes 331
25.1 Triviale perfekte Codes 332
25.2 Hamming-Codes 333
25.3 Übungen 335

26 Präfixcodes 337

27 Information, Entropie und Sätze von Shannon 343
27.1 Huffman-Code 345
27.2 Information 348
27.3 Entropie 350
27.4 Fundamentalsatz über die Quellencodierung 352
27.5 Fundamentalsatz über die Kanalcodierung 355
27.6 Übungen 364

28 Prüfzeichencodierung 365
28.1 Prüfzeichenverfahren: Definition und allgemeine Eigenschaften . . 365
28.2 Prüfziffercodierung in additiven Restklassen 367
28.2.1 ISBN-Codierung 367
28.2.2 EAN-Codierung 369
28.3 Fehlererkennung mit abelschen Gruppen 370
28.4 Prüfziffercodierung in Diedergruppen 373
28.5 Übungen 376

29 Zyklische Codes 379
29.1 Genratorpolynome und -matrizen 380
29.2 Kontrollpolynome und -matrizen 382
29.3 Übungen 383

Literaturverzeichnis 384

Index 388


Abbildungsverzeichnis
20.1 Zwei lineare Schieberegister 259
20.2 Allgemeiner Aufbau eines Schieberegisters der Länge 4 260
23.1 Elementare Begriffe der Codierungstheorie 316
26.1 Codebaum Tc zu C = {1,00,01,10,010,011,111} 339
26.2 1. Codebaum zu Beispiel 26.2 340
26.3 2. Codebaum zu Beispiel 26.2 341
27.1 Beispiel für eine Huffman-Codierung der Quelle Q aus dem Beispiel 27.2 347
27.2 BMC: binärer gedächtnisloser Kanal 356
27.3 BSC: binärer symmetrischer Kanal 357