Boockmeyer, ArneArne Boockmeyer ist Softwareentwickler und Master-Student am Hasso-Plattner-Institut in Potsdam. Er befasst sich mit der Didaktik des Faches Informatik, ist als Dozent zum Thema Programmierung mit Java tätig und als Tutor für Competitive Programming am Lehrstuhl für Algorithm Engineering aktiv. Er begeistert regelmäßig Schüler für die Informatik und freut sich immer, wenn er seine Faszination für das Fach weitergeben kann.Fischbeck, PhilippPhilipp Fischbeck kennt typische Hürden beim Lernen aus seiner Arbeit mit Jugendlichen in der Schülerakademie des Hasso-Plattner-Instituts und mit Studierenden als Tutor. Die Interessenschwerpunkte des PhD-Studenten sind Algorithmik und Graphentheorie. Er ist immer wieder begeistert, wenn sich schwierige Themen und Techniken nach etwas Einarbeitungszeit meistern lassen. Wer sich vom Spaß am Problemlösen und Rätseln anstecken lassen möchte, ist bei ihm richtig.Neubert, StefanStefan Neubert hat zahlreiche Informatik-Workshops und -Camps für Schüler entwickelt und durchgeführt. Er unterstützt seit Jahren die Bachelor-Lehrveranstaltung "Theoretische Informatik" als Tutor und arbeitet mit Leidenschaft dafür, komplexe Themen verständlich zu machen. Der PhD-Student am Hasso-Plattner-Institut schätzt sein Fach auch dafür, dass es Kreativität und Teamfähigkeit erfordert, obwohl das vielleicht oft nicht vermutet wird. Schüler wie Leser schätzen seine verständliche Sprache und anschaulichen Beispiele - vor allem dann, wenn es anspruchsvoller wird.

Ideal zum Selbststudium

Geleitwort ... 15


Intro ... 17


1. Algorithmen ... 26


Knobelei zum Einstieg: Wo ist der Ausgang des Labyrinths? ... 27

Was ist ein Algorithmus? ... 28

Wie wird ein Algorithmus notiert? ... 30

Schleifen ... 33

Verzweigungen ... 34

Logische Aussagen ... 37

Funktionen ... 41

Zusammenfassung und Einordnung ... 42

Aufgaben ... 43

Lösungen ... 44



2. Zahlen und Kodierungen ... 48


Knobelei zum Einstieg: Gib mir 31! ... 49

Zahlensysteme und Einheiten ... 50

Kodierungen ... 54

Zusammenfassung und Einordnung ... 60

Aufgaben ... 61

Lösungen ... 62



3. Datenstrukturen ... 64


Knobelei zum Einstieg: Speicherung gleicher Daten ... 65

Geordnete Daten ... 65

Ungeordnete Daten ... 72

Datenzuordnungen ... 74

Zusammenfassung und Einordnung ... 75

Aufgaben ... 76

Lösungen ... 77



4. Einfache Sortieralgorithmen ... 80


Knobelei zum Einstieg: Bücher sortieren ... 81

Selection Sort ... 82

Insertion Sort ... 87

Bubble Sort ... 89

Ordnungen ... 92

Zusammenfassung und Einordnung ... 93

Aufgaben ... 95

Lösungen ... 96



5. Komplexität ... 100


Knobelei zum Einstieg: Schokolade aufteilen ... 101

Verschiedene Wege führen zum Ziel ... 102

Eingabegröße ... 103

Messen der Laufzeit ... 104

Berechnen der Laufzeit ... 104

Die Landau-Notation ... 107

Typische Laufzeiten ... 110

Zusammenfassung und Einordnung ... 112

Aufgaben ... 114

Lösungen ... 115



6. Effizientere Sortieralgorithmen ... 118


Knobelei zum Einstieg: Sortieren im Team ... 119

Merge Sort ... 119

Quick Sort ... 124

Rekursion und Divide and Conquer ... 127

Noch schneller sortieren ... 130

Zusammenfassung und Einordnung ... 132

Aufgaben ... 134

Lösungen ... 135



7. Suchen ... 140


Knobelei zum Einstieg: Finden und Sortieren ... 141

Lineare Suche ... 141

Binäre Suche ... 144

Suchbäume ... 147

Zusammenfassung und Einordnung ... 154

Aufgaben ... 155

Lösungen ... 156



8. Backtracking und Dynamische Programmierung ... 160


Knobelei zum Einstieg: Das Kistenproblem ... 161

Die perfekte Kiste ... 161

Branch and Bound ... 163

Dynamische Programmierung ... 164

Zusammenfassung und Einordnung ... 166

Aufgaben ... 167

Lösungen ... 168



9. Graphen ... 172


Knobelei zum Einstieg: Morgendliches Anziehen ... 173

Verknüpfte Daten ... 174

Varianten von Graphen ... 175

Suchen und Bewegen in Graphen ... 178

Eigenschaften von Graphen ... 183

Zusammenfassung und Einordnung ... 186

Aufgaben ... 187

Lösungen ... 189



10. Formale Sprachen ... 192


Knobelei zum Einstieg: Sätze erzeugen ... 193

Grammatiken ... 194

Automaten ... 198

Sprachen und Mengenoperationen ... 202

Reguläre Ausdrücke ... 205

Zusammenfassung und Einordnung ... 207

Aufgaben ... 208

Lösungen ... 209



11. Objektorientierung ... 214


Knobelei zum Einstieg: Das Vereinsfest ... 215

Objekte und Klassen ... 216

Objektorientierte Programmierung ... 217

Vererbung ... 218

Abstrakte Klassen ... 219

Sichtbarkeiten ... 221

Zusammenfassung und Einordnung ... 223

Aufgaben ... 224

Lösungen ... 225



12. Datenbanken ... 232


Knobelei zum Einstieg: Max' Lieblingsfilme ... 233

Strukturierte Datenspeicherung ... 235

Operationen auf Datenbanken ... 240

Empfohlene Strukturierung von Daten ... 247

Zusammenfassung und Einordnung ... 251

Aufgaben ... 253

Lösungen ... 255



13. Computer ... 260


Knobelei zum Einstieg: Addieren auf Hardware-Ebene ... 261

Logische Schaltungen ... 262

Hardware-Komponenten und ihr Zusammenspiel ... 265

Betriebssysteme ... 268

Betriebssystemunabhängigkeit ... 272

Virtuelle Computer ... 274

Zusammenfassung und Einordnung ... 275

Aufgaben ... 276

Lösungen ... 277



14. Netzwerke ... 280


Knobelei zum Einstieg: Die Post des Kanzleramts ... 281

Eine mögliche Lösung für die Poststelle ... 282

Netzwerke ... 283

Internetstruktur ... 286

Einheitliche Kommunikation ... 290

Zusammenfassung und Einordnung ... 293

Aufgaben ... 294

Lösungen ... 295



15. Verschlüsselung ... 298


Knobelei zum Einstieg: Fdhvdu ... 299

Warum verschlüsseln? ... 300

Symmetrische Verschlüsselung ... 300

Asymmetrische Verschlüsselung ... 302

Hybridverfahren ... 304

Verschlüsselungen knacken ... 304

Zusammenfassung und Einordnung ... 307

Aufgaben ... 308

Lösungen ... 309



16. Softwareentwicklung ... 310


Algorithmus vs. Software ... 311

Die Werkzeuge eines Softwareentwicklers ... 313

Große Probleme lösen ... 315

Zusammenfassung und Einordnung ... 318



17. Teamarbeit ... 320


Knobelei zum Einstieg: Konflikte ... 321

Warum Teams? ... 322

Softwareentwicklung im Team ... 322

Kommunikation in Teams ... 323

Aufgabenverwaltung und Kommunikationswerkzeuge ... 325

Versionsverwaltung ... 325

Zusammenfassung und Einordnung ... 330

Aufgaben ... 332

Lösungen ... 333



18. Fehler ... 334


Knobelei zum Einstieg: Auf Fehlersuche ... 335

Warum ist Software fehlerhaft? ... 336

Bugs ... 337

Verschiedene Fehlerarten ... 337

Techniken zur Fehlervermeidung ... 343

Zusammenfassung und Einordnung ... 346

Aufgaben ... 347

Lösungen ... 348



19. Hands-on: Programmieren mit Java ... 350


Die Programmiersprache Java ... 351

Hallo Leser ... 352

Variablen ... 354

Klassen, Objekte und Methoden ... 355

Datentypen ... 359

Kontrollstrukturen ... 366

Fehlersuche ... 369

Eine kleine Werkzeugkiste ... 371

Aufgaben ... 372

Lösungen ... 374



20. Ethik in der Informatik ... 378


Recht und Ordnung ... 379

Informatik in der Wirtschaft ... 381

Der Wert persönlicher Daten ... 384

Gemeingüter und Open Source ... 385

Verantwortung für Technologie ... 388

IT-Gerechtigkeit ... 392

Der technisierte Mensch ... 393

Zusammenfassung und Einordnung ... 394



21. Extro ... 396


Wie wird man Informatiker? ... 397

Ressourcen ... 402

Wie geht es weiter? ... 403



Index ... 405