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

Graphische Notation

33

Pseudocode

34

1.4 Schleifen

35

1.5 Verzweigungen

37

1.6 Logische Aussagen

39

Logisches NICHT

40

Logisches UND

40

Logisches ODER

41

Klammerung und Vorrangsregeln

41

Besondere Aussagen

42

1.7 Funktionen

43

1.8 Zusammenfassung und Einordnung

44

2 Zahlen und Kodierungen

50

2.1 Gib mir 31!

51

2.2 Zahlensysteme und Einheiten

52

Rechnen im Binärsystem

53

Einheiten

54

2.3 Kodierungen

56

Natürliche Zahlen

56

Ganze Zahlen

57

Kommazahlen

58

Text

59

Bilder

60

2.4 Zusammenfassung und Einordnung

62

3 Datenstrukturen

68

3.1 Speicherung gleicher Daten

69

3.2 Geordnete Daten

69

Repräsentation im Speicher

72

Andere Operationen auf den Datenstrukturen

75

3.3 Ungeordnete Daten

75

3.4 Datenzuordnungen

77

3.5 Zusammenfassung und Einordnung

78

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

5 Komplexität

104

5.1 Schokolade aufteilen

105

5.2 Verschiedene Wege führen zum Ziel

106

5.3 Eingabegröße

107

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

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

131

6.5 Noch schneller sortieren

133

6.6 Zusammenfassung und Einordnung

136

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

Suchen in Suchbäumen

152

Hinzufügen eines Elements

154

Erstellen von Suchbäumen

155

Balancierte Bäume

157

7.5 Zusammenfassung und Einordnung

158

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

9 Graphen

176

9.1 Morgendliches Anziehen

177

9.2 Verknüpfte Daten

178

9.3 Varianten von Graphen

179

Gerichtete Kanten

179

Gewichtete Kanten

180

Beispiele für Graphen

180

9.4 Suchen und Bewegen in Graphen

182

Implementierung

183

Beispiel

184

9.5 Eigenschaften von Graphen

187

Bäume und Zyklenfreiheit

187

Zusammenhang

188

Eulersche Graphen

189

Planarität

189

9.6 Zusammenfassung und Einordnung

190

10 Formale Sprachen

196

10.1 Sätze erzeugen

197

10.2 Grammatiken

198

Reguläre Grammatiken

200

Kontextfreie Grammatiken

200

Höhere Grammatiken

201

10.3 Automaten

202

Endliche Automaten

202

Höhere Automaten

205

10.4 Sprachen und Mengenoperationen

206

10.5 Reguläre Ausdrücke

208

10.6 Zusammenfassung und Einordnung

210

11 Modellierung

216

11.1 Das Vereinsfest

217

11.2 Modellierung und Modelle

217

11.3 Problemmodellierung

219

11.4 Prozessmodellierung

220

Aktivitäten und deren Reihenfolge

220

Start- und Endknoten

220

Verzweigungen

221

Verantwortungsbereiche

222

11.5 Strukturmodellierung

223

Objekte und Klassen

223

Vererbung

224

Abstrakte Klassen

225

Sichtbarkeiten

226

11.6 Zusammenfassung und Einordnung

226

12 Datenbanken

232

12.1 Max’ Lieblingsfilme

233

12.2 Strukturierte Datenspeicherung

235

Grundbegriffe

236

Darstellung

236

Kardinalitäten

237

Schlüssel

239

12.3 Operationen auf Datenbanken

239

Daten abfragen und sortieren

240

Gruppierung von Daten

243

Einträge einfügen

245

Einträge modifizieren

245

Einträge löschen

246

12.4 Empfohlene Strukturierung von Daten

247

Ein Wert pro Zelle

247

Redundanzen vermeiden

249

12.5 Zusammenfassung und Einordnung

251

13 Künstliche Intelligenz

260

13.1 Mensch gegen Maschine

261

13.2 Was ist Intelligenz?

262

Autonomie und Lernfähigkeit

262

Intelligenztests für Maschinen

263

Starke und schwache Intelligenz

264

13.3 Nachgeahmte Intelligenz

265

Entscheidungsbäume

265

Wissens- und logikbasierte Systeme

267

Heuristiken

271

13.4 Maschinelles Lernen

272

Arten des Lernens

272

Künstliche neuronale Netze

274

13.5 Anwendungsfelder

278

Automatische Textverarbeitung

279

Empfehlungssysteme in der Medizin

279

Intelligente Handykameras

281

Selbstfahrende Fahrzeuge

281

13.6 Zusammenfassung und Einordnung

282

14 Computer

288

14.1 Addieren auf Hardware-Ebene

289

14.2 Logische Schaltungen

290

Die Knobelei als Schaltplan

291

Exklusives ODER

292

Algorithmen als logische Schaltungen

293

14.3 Hardware-Komponenten und ihr Zusammenspiel

293

14.4 Betriebssysteme

296

Kernfunktionen von Betriebssystemen

297

Verbreitete Betriebssysteme

299

Betriebssystemnahe Programmierung

300

14.5 Betriebssystemunabhängigkeit

301

Interpreter

301

Bytecode-Sprachen

302

14.6 Virtuelle Computer

302

14.7 Zusammenfassung und Einordnung

303

15 Netzwerke

308

15.1 Die Post des Kanzleramts

309

15.2 Eine mögliche Lösung für die Poststelle

309

15.3 Netzwerke

311

Clients und Server

311

Weitere Netzwerkgeräte

312

15.4 Internetstruktur

314

Services im Internet

316

Daten im Internet versenden

316

Adressauflösung zum Finden der IP-Adresse

317

15.5 Einheitliche Kommunikation

318

Eine HTTP-Anfrage

318

Die Antwort des Webservers

319

Die Anfrage zusätzlicher Ressourcen

320

15.6 Zusammenfassung und Einordnung

321

16 Verschlüsselung

326

16.1 Fdhvdu

327

16.2 Warum verschlüsseln?

328

16.3 Symmetrische Verschlüsselung

328

16.4 Asymmetrische Verschlüsselung

329

16.5 Hybridverfahren

332

16.6 Verschlüsselungen knacken

332

16.7 Zusammenfassung und Einordnung

334

17 Softwareentwicklung

338

17.1 Algorithmus vs. Software

339

17.2 Die Werkzeuge eines Softwareentwicklers

341

17.3 Große Probleme lösen

343

Top-down-Methode

343

Bottom-up-Methode

344

17.4 Zusammenfassung und Einordnung

345

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

352

18.6 Versionsverwaltung

353

Änderungen kleinschrittig speichern

354

Daten mit einem Server synchronisieren

354

Mit anderen Entwicklern zusammenarbeiten

355

Verschiedene Entwicklungszweige verfolgen

356

18.7 Zusammenfassung und Einordnung

358

19 Fehler

362

19.1 Auf Fehlersuche

363

19.2 Warum ist Software fehlerhaft?

364

19.3 Bugs

365

19.4 Verschiedene Fehlerarten

365

Kompilierungsfehler

365

Laufzeitfehler

366

Logische Fehler

367

Designfehler

368

Umgebungsfehler

370

Kommunikationsfehler

370

19.5 Techniken zur Fehlervermeidung

371

Testen

371

A/B Testing

372

Programmierstil

373

Pair Programming

373

Code Review

374

19.6 Zusammenfassung und Einordnung

374

20 Hands-on: Programmieren mit Python

378

20.1 Die Programmiersprache Python

379

20.2 Hallo Leser

380

Ausführung

380

Erklärung des Programmcodes

381

20.3 Variablen

381

20.4 Klassen, Objekte und Methoden

382

Eigenschaften von Objekten

383

Verhalten von Objekten

383

20.5 Datentypen

386

Zahlen

386

Wahrheitswerte

387

Zeichen und Zeichenketten

388

Arrays

389

Queues und Stacks

390

Sets und Maps

392

20.6 Kontrollstrukturen

393

Verzweigungen

393

Schleifen

394

20.7 Fehlersuche

396

20.8 Eine kleine Werkzeugkiste

398

21 Ethik in der Informatik

404

21.1 Recht und Ordnung

405

Software für den Überwachungsstaat

405

Die Hutfarben der Hacker

407

21.2 Informatik in der Wirtschaft

407

Automatisierung statt Arbeitsplatz

407

Netzneutralität

408

21.3 Der Wert persönlicher Daten

409

21.4 Gemeingüter und Open Source

412

Wissen für jedermann

412

Kostenlose und quelloffene Software

413

Probleme der Anarchie

413

21.5 Vertrauen in Informationen

415

21.6 Verantwortung für Technologie

416

Das Leben in der Blase

416

Vermeidbare Fehlfunktionen

417

Unvermeidbare Folgen

418

21.7 IT-Gerechtigkeit

419

21.8 Der technisierte Mensch

420

Abhängigkeit von Technik

420

Arbeitszeit: 24/7

421

21.9 Zusammenfassung und Einordnung

422

22 Extro

424

22.1 Wie wird man Informatiker*in?

425

Inhalte des Informatikstudiums

425

Organisation des Studiums

427

Entscheidung für ein Studium

427

Ausbildung als Alternative zum Studium

429

Ein duales Studium als Mittelweg

429

Das Berufsleben in der Informatik

430

22.2 Ressourcen

430

22.3 Wie geht es weiter?

430