Fit fürs Studium - Informatik

Geleitwort ... 17

Intro ... 19

1. Algorithmen ... 28
1.1 ... Wo ist der Ausgang des Labyrinths? ... 29
1.2 ... Was ist ein Algorithmus? ... 30
1.3 ... Wie wird ein Algorithmus notiert? ... 32
1.4 ... Schleifen ... 35
1.5 ... Verzweigungen ... 37
1.6 ... Logische Aussagen ... 39
1.7 ... Funktionen ... 43
1.8 ... Zusammenfassung und Einordnung ... 44
1.9 ... Aufgaben ... 45
1.10 ... Lösungen ... 46

2. Zahlen und Kodierungen ... 50
2.1 ... Gib mir 31! ... 51
2.2 ... Zahlensysteme und Einheiten ... 52
2.3 ... Kodierungen ... 56
2.4 ... Zusammenfassung und Einordnung ... 62
2.5 ... Aufgaben ... 63
2.6 ... Lösungen ... 64

3. Datenstrukturen ... 68
3.1 ... Speicherung gleicher Daten ... 69
3.2 ... Geordnete Daten ... 69
3.3 ... Ungeordnete Daten ... 75
3.4 ... Datenzuordnungen ... 77
3.5 ... Zusammenfassung und Einordnung ... 78
3.6 ... Aufgaben ... 80
3.7 ... Lösungen ... 81

4. Einfache Sortieralgorithmen ... 84
4.1 ... Bücher sortieren ... 85
4.2 ... Selection Sort ... 86
4.3 ... Insertion Sort ... 91
4.4 ... Bubble Sort ... 93
4.5 ... Ordnungen ... 96
4.6 ... Zusammenfassung und Einordnung ... 97
4.7 ... Aufgaben ... 98
4.8 ... Lösungen ... 99

5. Komplexität ... 104
5.1 ... Schokolade aufteilen ... 105
5.2 ... Verschiedene Wege führen zum Ziel ... 106
5.3 ... Eingabegröße ... 106
5.4 ... Messen der Laufzeit ... 108
5.5 ... Berechnen der Laufzeit ... 108
5.6 ... Die Landau-Notation ... 111
5.7 ... Typische Laufzeiten ... 114
5.8 ... Zusammenfassung und Einordnung ... 116
5.9 ... Aufgaben ... 118
5.10 ... Lösungen ... 119

6. Effizientere Sortieralgorithmen ... 122
6.1 ... Sortieren im Team ... 123
6.2 ... Merge Sort ... 123
6.3 ... Quick Sort ... 128
6.4 ... Rekursion und Divide and Conquer ... 130
6.5 ... Noch schneller sortieren ... 133
6.6 ... Zusammenfassung und Einordnung ... 135
6.7 ... Aufgaben ... 137
6.8 ... Lösungen ... 138

7. Suchen ... 144
7.1 ... Finden und Sortieren ... 145
7.2 ... Lineare Suche ... 145
7.3 ... Binäre Suche ... 148
7.4 ... Suchbäume ... 151
7.5 ... Zusammenfassung und Einordnung ... 158
7.6 ... Aufgaben ... 159
7.7 ... Lösungen ... 160

8. Backtracking und dynamische Programmierung ... 164
8.1 ... Das Kistenproblem ... 165
8.2 ... Die perfekte Kiste ... 165
8.3 ... Branch and Bound ... 167
8.4 ... Dynamische Programmierung ... 168
8.5 ... Zusammenfassung und Einordnung ... 170
8.6 ... Aufgaben ... 171
8.7 ... Lösungen ... 172

9. Graphen ... 176
9.1 ... Morgendliches Anziehen ... 177
9.2 ... Verknüpfte Daten ... 178
9.3 ... Varianten von Graphen ... 179
9.4 ... Suchen und Bewegen in Graphen ... 182
9.5 ... Eigenschaften von Graphen ... 187
9.6 ... Zusammenfassung und Einordnung ... 190
9.7 ... Aufgaben ... 191
9.8 ... Lösungen ... 193

10. Formale Sprachen ... 196
10.1 ... Sätze erzeugen ... 197
10.2 ... Grammatiken ... 198
10.3 ... Automaten ... 201
10.4 ... Sprachen und Mengenoperationen ... 205
10.5 ... Reguläre Ausdrücke ... 208
10.6 ... Zusammenfassung und Einordnung ... 210
10.7 ... Aufgaben ... 211
10.8 ... Lösungen ... 212

11. Modellierung ... 216
11.1 ... Das Vereinsfest ... 217
11.2 ... Modellierung und Modelle ... 217
11.3 ... Problemmodellierung ... 219
11.4 ... Prozessmodellierung ... 220
11.5 ... Strukturmodellierung ... 223
11.6 ... Zusammenfassung und Einordnung ... 226
11.7 ... Aufgaben ... 228
11.8 ... Lösungen ... 229

12. Datenbanken ... 232
12.1 ... Max' Lieblingsfilme ... 233
12.2 ... Strukturierte Datenspeicherung ... 235
12.3 ... Operationen auf Datenbanken ... 239
12.4 ... Empfohlene Strukturierung von Daten ... 246
12.5 ... Zusammenfassung und Einordnung ... 250
12.6 ... Aufgaben ... 252
12.7 ... Lösungen ... 255

13. Künstliche Intelligenz ... 260
13.1 ... Mensch gegen Maschine ... 261
13.2 ... Was ist Intelligenz? ... 262
13.3 ... Nachgeahmte Intelligenz ... 265
13.4 ... Maschinelles Lernen ... 272
13.5 ... Anwendungsfelder ... 281
13.6 ... Zusammenfassung und Einordnung ... 285
13.7 ... Aufgaben ... 287
13.8 ... Lösungen ... 288

14. Computer ... 290
14.1 ... Addieren auf der Hardware-Ebene ... 291
14.2 ... Logische Schaltungen ... 292
14.3 ... Hardware-Komponenten und ihr Zusammenspiel ... 295
14.4 ... Betriebssysteme ... 298
14.5 ... Betriebssystemunabhängigkeit ... 303
14.6 ... Virtuelle Computer ... 304
14.7 ... Zusammenfassung und Einordnung ... 305
14.8 ... Aufgaben ... 307
14.9 ... Lösungen ... 308

15. Netzwerke ... 310
15.1 ... Die Post des Kanzleramts ... 311
15.2 ... Eine mögliche Lösung für die Poststelle ... 311
15.3 ... Netzwerke ... 313
15.4 ... Internetstruktur ... 316
15.5 ... Einheitliche Kommunikation ... 320
15.6 ... Zusammenfassung und Einordnung ... 323
15.7 ... Aufgaben ... 324
15.8 ... Lösungen ... 325

16. Verschlüsselung ... 328
16.1 ... Fdhvdu ... 329
16.2 ... Warum verschlüsseln? ... 329
16.3 ... Symmetrische Verschlüsselung ... 330
16.4 ... Asymmetrische Verschlüsselung ... 331
16.5 ... Hybridverfahren ... 333
16.6 ... Verschlüsselungen knacken ... 334
16.7 ... Zusammenfassung und Einordnung ... 336
16.8 ... Aufgaben ... 337
16.9 ... Lösungen ... 338

17. Softwareentwicklung ... 340
17.1 ... Algorithmus vs. Software ... 341
17.2 ... Die Werkzeuge in der Softwareentwicklung ... 343
17.3 ... Große Probleme lösen ... 345
17.4 ... Zusammenfassung und Einordnung ... 347

18. Teamarbeit ... 348
18.1 ... Konflikte ... 349
18.2 ... Warum Teams? ... 350
18.3 ... Softwareentwicklung im Team ... 350
18.4 ... Kommunikation in Teams ... 351
18.5 ... Aufgabenverwaltung und Kommunikationswerkzeuge ... 353
18.6 ... Versionsverwaltung ... 354
18.7 ... Zusammenfassung und Einordnung ... 358
18.8 ... Aufgaben ... 360
18.9 ... Lösungen ... 361

19. Fehler ... 362
19.1 ... Auf Fehlersuche ... 363
19.2 ... Warum ist Software fehlerhaft? ... 364
19.3 ... Bugs ... 365
19.4 ... Verschiedene Fehlerarten ... 365
19.5 ... Techniken zur Fehlervermeidung ... 371
19.6 ... Zusammenfassung und Einordnung ... 374
19.7 ... Aufgaben ... 375
19.8 ... Lösungen ... 376

20. Hands-on: Programmieren mit Python ... 378
20.1 ... Die Programmiersprache Python ... 379
20.2 ... Hallo Leser*in ... 380
20.3 ... Variablen ... 381
20.4 ... Klassen, Objekte und Methoden ... 382
20.5 ... Datentypen ... 386
20.6 ... Kontrollstrukturen ... 393
20.7 ... Fehlersuche ... 397
20.8 ... Eine kleine Werkzeugkiste ... 398
20.9 ... Aufgaben ... 399
20.10 ... Lösungen ... 400

21. Ethik in der Informatik ... 404
21.1 ... Recht und Ordnung ... 405
21.2 ... Informatik in der Wirtschaft ... 408
21.3 ... Der Wert persönlicher Daten ... 410
21.4 ... Gemeingüter und Open Source ... 412
21.5 ... Vertrauen in Informationen ... 415
21.6 ... Verantwortung für Technologie ... 416
21.7 ... IT-Gerechtigkeit ... 420
21.8 ... Die technisierte Gesellschaft ... 421
21.9 ... Zusammenfassung und Einordnung ... 423

22. Extro ... 424
22.1 ... Wie wird man Informatiker*in? ... 424
22.2 ... Ressourcen ... 430
22.3 ... Wie geht es weiter? ... 430

Index ... 433