Fundamentals of Computer Science Study Guide

Begriff und Definitionen

Definition der Informatik: Die Informatik ist die Wissenschaft von der systematischen Darstellung, Speicherung, Verarbeitung und Übertragung von Informationen, wobei in der Regel die automatische Verarbeitung mit Computern betrachtet wird.
Kernbereiche: Die Informatik liefert das grundlegende Verständnis für Computer, Apps, das Internet, künstliche Intelligenz (KI), Hacking, Algorithmen, Videospiele, Kryptowährungen und digitale Logik.
Unterscheidung zentraler Begriffe:
- Informationstechnik (IT) / Elektronische Datenverarbeitung (EDV): Bezeichnet die gesamte Computer-Infrastruktur innerhalb einer Organisation. Zum Beispiel umfasst die IT an der KZU alle Computer, Netzwerkgeräte, Webseiten, Anwendungen und das IT-Fachpersonal.
- Information and Communications Technology (ICT): Konzentriert sich auf die Vermittlung der praktischen Anwendung und Nutzung von Computer-Software und -Hardware (z. B. Nutzung von Office-Anwendungen, Grafikbearbeitung, Tastaturschreiben). ICT repräsentiert die praktische Anwendung, während sich die Informatik auf das grundlegende theoretische und technische Verständnis konzentriert.
- Computer Science: Der englische Begriff für Informatik.

Geschichte der Informatik

Menschliche Computer: Ursprünglich beschrieb das Wort „Computer“ menschliche Rechner, die vor der Erfindung elektronischer Rechner komplexe mathematische Berechnungen manuell als Beruf ausführten.

Das EVA(S)-Prinzip

Eingabe-Verarbeitung-Ausgabe-(Speicher): Die Datenverarbeitung in jedem Computer folgt strikt einem dreistufigen Ablauf, der durch einen Speicher unterstützt wird:
1. Eingabe (Input): Empfang externer Rohdaten in das System.
2. Verarbeitung (Processing): Ausführung von Rechenoperationen auf den Daten.
3. Ausgabe (Output): Senden oder Darstellen der Rechenergebnisse.
4. Speicher (Storage): Konsultieren oder Beschreiben des Datenspeichers während der Verarbeitungsschritte.

Grundlegende Hardware-Komponenten

Stromversorgung:
- Versorgt alle internen Komponenten mit elektrischer Energie.
- Verwendet wiederaufladbare Batterien (Akku) in mobilen Geräten und Netzteile in stationären Systemen.
Hauptprozessor (CPU / Central Processing Unit):
- Das zentrale Rechenwerk („Kernstück“) des Computers.
- Koordiniert alle mathematischen und logischen Berechnungen, führt Befehle direkt aus oder steuert andere Hardware-Komponenten.
- Leistungsbestimmende Faktoren:
1. Prozessorkerne: Einzelne Verarbeitungseinheiten, die parallel innerhalb einer einzigen CPU arbeiten. Eine 8-Kern-CPU kann bis zu 8-mal schneller arbeiten als eine Einzelkern-CPU.
2. Taktfrequenz: Gibt die Geschwindigkeit der Befehlsausführung an. Eine CPU mit einer Taktfrequenz von $3\,\text{GHz}$ verarbeitet $3 \times 10^9$ Befehle pro Kern und Sekunde.
Hauptplatine (Motherboard / Mainboard):
- Die primäre physische Leiterplatte, auf der die CPU und sekundäre Komponenten installiert sind.
- Stellt Hochgeschwindigkeitsbusse und physische Verbindungen zwischen CPU, RAM, Speicher und externen Eingabe-/Ausgabegeräten bereit.
Arbeitsspeicher (RAM / Random Access Memory):
- Das temporäre Kurzzeitgedächtnis des Computers.
- Hält aktive Programmanweisungen und unmittelbar benötigte Datensätze bereit.
- Bietet einen gleichmäßigen, extrem schnellen Lese-/Schreibzugriff unabhängig von der Sequenz der Speicherorte.
- Flüchtiger Speicher: Funktioniert nur bei aktiver Stromversorgung; alle Daten gehen sofort verloren, wenn die Stromzufuhr unterbrochen wird.
Permanenter Speicher:
- Das nicht-flüchtige Langzeitgedächtnis des Computers.
- Behält gespeicherte Dateien, Anwendungen und Betriebssystemdaten auch ohne Stromversorgung bei.
- Arbeitet deutlich langsamer als der RAM, bietet jedoch eine riesige Speicherkapazität zu wesentlich geringeren Kosten pro Byte.
- Historisch durch Festplattenlaufwerke (HDD mit rotierenden Magnetplatten) realisiert; moderne Geräte verwenden Solid-State-Drives (SSD).
Mooresches Gesetz (Moore's Law): Beschreibt den historischen Trend des exponentiellen Wachstums der Transistordichte und Rechenkapazität in den letzten Jahrzehnten.

Sekundäre Hardware-Komponenten

Grafikprozessor (GPU / Graphics Processing Unit):
- Hochspezialisierter Prozessor, der für mathematische Operationen optimiert ist, die für das Rendering von Computergrafiken (3D-Simulationen, Spiele) erforderlich sind.
- Die Architektur besteht aus Tausenden kleiner, unabhängiger Prozessorkerne ( $>20000$ ), die gleichzeitig parallel arbeiten.
- Übertrifft CPUs bei massiv parallelen Rechenaufgaben wie dem Training von Modellen der Künstlichen Intelligenz (KI) und dem Mining von Kryptowährungen bei Weitem.
Netzwerkanbindung:
- Ermöglicht Netzwerkkommunikation und die Übertragung/Empfang von Internetdaten.
- Häufig über drahtlose WLAN-/Wi-Fi-Module integriert; hocheffiziente oder sichere Umgebungen (Serverräume) nutzen physische Ethernet-Verkabelungen.
Wechseldatenträger:
- Externe Medien, die spezifische Laufwerke oder Steckplätze erfordern: SD-Karten, optische Disks (CDs, DVDs, Blu-rays).
- Magnetbänder (früher in Tonkassetten verwendet) werden in Unternehmensrechenzentren aufgrund ihrer extremen physischen Langlebigkeit zur Langzeitarchivierung weiterhin eingesetzt.
- Einplatinencomputer wie der Raspberry Pi lassen diese einzelnen strukturellen Komponenten für Bildungszwecke offen sichtbar.

Software-Architektur

Natur und Klassifizierung von Software

Software-Definition: Nicht-physische Befehlssätze, die auf Hardware (z. B. SSD) gespeichert sind und den Hardware-Komponenten Anweisungen für den Betrieb geben.
Primäre Kategorien:
1. Anwendungssoftware (Applikationen / Anwendungsprogramme): Programme zur Ausführung spezifischer Benutzeraufgaben (Webbrowser, E-Mail-Clients, Office-Suites, Videoplayer, Spiele).
2. Betriebssystem (Operating System).

Programmiersprachen vs. natürliche Sprachen

Ungeeignetheit natürlicher Sprache: Gesprochene menschliche Sprachen (z. B. Deutsch, Englisch) sind von Natur aus zweideutig, kontextabhängig und unpräzise.
Demonstration von Zweideutigkeit:
- Befehl in natürlicher Sprache: „Schreibe eine Funktion, die 1 zu jeder Zahl in einer Liste addiert und das Ergebnis ausgibt.“
- Inhärente Zweideutigkeiten:
1. Was definiert „eine Liste“? Handelt es sich um einen übergebenen Eingabeparameter oder um Text in der Benutzeroberfläche?
2. Was bedeutet „jede Zahl“? Sind negative Werte oder Dezimalzahlen enthalten? Was passiert, wenn nicht-numerische Zeichenketten vorkommen?
3. Was definiert „das Ergebnis“? Soll das Ausgabeformat 1 2 3 4 oder [1, 2, 3, 4] sein?
4. Wohin soll die Ausgabe erfolgen? Im Code zurückgegeben, auf der Benutzeroberfläche gedruckt oder auf der Festplatte gespeichert?
Präzision von Programmiersprachen: Höhere Programmiersprachen liefern exakte, eindeutige Ausführungsanweisungen.

  def funktion(numbers):
      return [x + 1 for x in numbers]

Programmiersprachen sind strikt so konzipiert, dass jedes syntaktisch gültige Programm genau eine Interpretation für die Ausführung hat.

Sprachabstraktionsebenen

Höhere Sprachen (High-Level): Sprachen, die auf menschliche Lesbarkeit und Entwicklereffizienz ausgerichtet sind (z. B. Python, Java). Sie abstrahieren von Hardware-Management-Details, was zu etwas langsameren Ausführungsgeschwindigkeiten führt.
Niedere Sprachen (Low-Level): Sprachen, die eng an der physischen Hardwarearchitektur ausgerichtet sind (z. B. C, C++, Rust). Sie bieten geringen Overhead und maximale Ausführungsgeschwindigkeit, erfordern jedoch manuelles Speicher- und Hardwaremanagement.
Beispiel für eine Übersetzungshierarchie (Werte tauschen swap(x, y)):
1. Höhere Funktion: swap(x, y)
2. Algorithmitische Abstraktion:
  text temp = x x = y y = temp
3. Assemblersprache (Assembly):
  assembly mov rax, [rdi] mov rbx, [rsi] mov [rdi], rbx mov [rsi], rax
4. Maschinencode (Hexadezimale Darstellung von Binärcode):
  text 48 8B 07 48 8B 1E 48 89 1F 48 89 07 C3

Betriebssysteme (OS)

Die zentrale Systemsoftware, die für die Hardwaresteuerung und die Anwendungsausführung verantwortlich ist.
Drei Kernfunktionen:
1. Hardware-Brücke / Abstraktionsschicht: Standardisiert Hardware-Schnittstellen (Tastatur, Touchscreen, Netzwerk) über verschiedene Hardware-Konfigurationen hinweg, sodass Software nicht für jede physische Komponente angepasst werden muss.
2. Anwendungsmanager / Schiedsrichter: Verwaltet Multitasking, teilt CPU-/RAM-Ressourcen fair auf, verhindert Gesamtsystemabstürze bei Anwendungsfehlern und setzt Security-Sandboxing zum Schutz privater Daten durch.
3. Benutzeroberfläche (UI): Rendert grafische Benutzeroberflächen (GUI) für die menschliche Interaktion.
Gängige Plattformen:
- Mobil: iOS, Android.
- Desktop/Laptop: Windows, macOS, Linux (z. B. Ubuntu, Debian).
- Webserver: Enterprise-Linux-Distributionen.

Zahlensysteme

Systemklassifizierungen und Notation

Dezimalsystem (Zehnersystem): Basis-10-System unter Verwendung der Ziffern $0, 1, 2, 3, 4, 5, 6, 7, 8, 9$ . Historisch vom Zählen an zehn menschlichen Fingern abgeleitet.
Historische Systeme: Römische Zahlen ( $\text{I, V, X, L, C, D, M}$ ); Das Basis-8-System der indigenen Yuki (Zählen der acht physischen Zwischenräume zwischen den Fingern).
Explizite Indexnotation (Definition 2.1): Verhindert numerische Zweideutigkeiten zwischen verschiedenen Basen:
- $10_2$ stellt die Zahl Zwei im Binärsystem dar.
- $10_{10}$ stellt die Zahl Zehn im Dezimalsystem dar.
- $15_{16}$ stellt die Zahl Einundzwanzig im Hexadezimalsystem dar.

Das Binärsystem (Zweiersystem)

Positionelles Zahlensystem zur Basis 2 unter Verwendung der Ziffern $0$ und $1$ . Spiegelt die binären Zustände des elektrischen Stroms (EIN/AUS) wider.
Stellenwerte steigen als aufsteigende Zweierpotenzen ( $2^0, 2^1, 2^2, 2^3, 2^4, 2^5, \dots$ ): $1, 2, 4, 8, 16, 32, 64, \dots$

Zähläquivalenz zwischen Binär- und Dezimalsystem:

Binär	Dezimal
$0_2$	$0_{10}$
$1_2$	$1_{10}$
$10_2$	$2_{10}$
$11_2$	$3_{10}$
$100_2$	$4_{10}$
$101_2$	$5_{10}$
$110_2$	$6_{10}$
$111_2$	$7_{10}$
$1000_2$	$8_{10}$
$1001_2$	$9_{10}$
$1010_2$	$10_{10}$
$1011_2$	$11_{10}$
$1100_2$	$12_{10}$

Beispiele für die Stellenwertentwicklung:
- Dezimal ( $41026{10}$ ):
 $4 \times 10^4 + 1 \times 10^3 + 0 \times 10^2 + 2 \times 10^1 + 6 \times 10^0 = 40000 + 1000 + 0 + 20 + 6 = 41026{10}$
- Binär ( $1001012$ ):
 $1 \times 2^5 + 0 \times 2^4 + 0 \times 2^3 + 1 \times 2^2 + 0 \times 2^1 + 1 \times 2^0 = 32 + 4 + 1 = 37{10}$

Umrechnungsalgorithmen

Binär zu Dezimal: Summation der Stellenwerte, bei denen die Ziffer $1$ ist.
Dezimal zu Binär (Variante A: Divisionsmethode):
1. Dividiere die Dezimalzahl durch 2.
2. Notiere den ganzzahligen Quotienten und den Rest ( $0$ oder $1$ ).
3. Wiederhole die Division mit dem verbleibenden Quotienten, bis 0 erreicht ist.
4. Lies die Reste von unten nach oben ab, um die Binärzahl zu bilden.
- Beispiel (Umrechnung von $19{10}$ in Binär):
 $\begin{aligned} 19 \div 2 &= 9 \quad \text{Rest } 1 \ 9 \div 2 &= 4 \quad \text{Rest } 1 \ 4 \div 2 &= 2 \quad \text{Rest } 0 \ 2 \div 2 &= 1 \quad \text{Rest } 0 \ 1 \div 2 &= 0 \quad \text{Rest } 1 \end{aligned}$
 Das Ablesen von unten nach oben ergibt $100112$
Dezimal zu Binär (Variante B: Subtraktions- / Potenzmethode):
1. Bestimme die größte Zweierpotenz, die in der Dezimalzahl enthalten ist.
2. Subtrahiere diesen Potenzwert und notiere die binäre Ziffer $1$ .
3. Prüfe jede nachfolgende absteigende Zweierpotenz:
- Passt die Potenz in den verbleibenden Wert: Subtrahiere den Potenzwert und notiere $1$ .
- Übersteigt die Potenz den verbleibenden Wert: Notiere $0$ .
1. Fahre fort bis $2^0 = 1$
- Beispiel (Umrechnung von $19_{10}$ in Binär):
- Potenz $16\,(2^4) \le 19 \rightarrow$ subtrahiere 16 (Rest 3), notiere $1$
- Potenz $8\,(2^3) > 3 \rightarrow$ notiere $0$
- Potenz $4\,(2^2) > 3 \rightarrow$ notiere $0$
- Potenz $2\,(2^1) \le 3 \rightarrow$ subtrahiere 2 (Rest 1), notiere $1$
- Potenz $1\,(2^0) \le 1 \rightarrow$ subtrahiere 1 (Rest 0), notiere $1$
  Das Ergebnis lautet $10011_2$

Binäre Arithmetik

Schriftliche Addition: Funktioniert nach denselben spaltenweisen Übertragsregeln wie die dezimale Addition.
- Beispiel ( $10012 + 11012$ ):
  \begin{array}{rccccc} & 1 & 0 & 0 & 12 & (9{10}) \ + & 1 & 1 & 0 & 12 & (13{10}) \ \text{Überträge:} & 1 & 1 & 0 & 1 & \ \hline = & 1 & 0 & 1 & 1 & 02 & (22{10}) \end{array}
Bitverschiebungen (Bit Shifts):
- Multiplikation von Binärzahlen mit Zweierpotenzen ( $2, 4, 8, \dots$ ) verschiebt die Ziffern nach links und hängt Nullen an:
 $10110012 \times 102 = 10110010_2$
- Ganzzahlige Division durch Zweierpotenzen verschiebt die Ziffern nach rechts:
 $10110012 \div 1002 = 101102 \quad \text{Rest } 12$

Hexadezimalsystem (Sechzehnersystem)

Basis-16-Zahlensystem mit 16 verschiedenen Ziffernsymbolen: $0, 1, 2, 3, 4, 5, 6, 7, 8, 9, \text{A, B, C, D, E, F}$ .
Werte: $\text{A}=10, \text{B}=11, \text{C}=12, \text{D}=13, \text{E}=14, \text{F}=15$
Byte-Ausrichtung: Zwei Hexadezimalziffern repräsentieren genau ein Byte ( $8\,\text{Bits}$ ).

Zuordnungstabelle für die direkte Umrechnung von Hexadezimal in Binär:

Hexadezimal	Binär	Dezimal
$0$	$0000$	$0$
$1$	$0001$	$1$
$2$	$0010$	$2$
$3$	$0011$	$3$
$4$	$0100$	$4$
$5$	$0101$	$5$
$6$	$0110$	$6$
$7$	$0111$	$7$
$8$	$1000$	$8$
$9$	$1001$	$9$
$\text{A}$	$1010$	$10$
$\text{B}$	$1011$	$11$
$\text{C}$	$1100$	$12$
$\text{D}$	$1101$	$13$
$\text{E}$	$1110$	$14$
$\text{F}$	$1111$	$15$

Berechnungen zur Hexadezimalumrechnung:
- Hexadezimal zu Dezimal ( $8\text{D}{16}$ ):
 $8\text{D}{16} = 8 \times 16^1 + \text{D} \times 16^0 = 8 \times 16 + 13 \times 1 = 128 + 13 = 141_{10}$
- Hexadezimal zu Binär durch direkte Substitution ( $14\text{AF}7{16}$ ):
 Ersetze jede Hex-Ziffer durch die entsprechende 4-Bit-Binärfolge:
 $1{16} \rightarrow 00012, \quad 4{16} \rightarrow 01002, \quad \text{A}{16} \rightarrow 10102, \quad \text{F}{16} \rightarrow 11112, \quad 7{16} \rightarrow 01112$ Ergebnis: $0001\,0100\,1010\,1111\,01112$

Logik und digitale Schaltungen

Aussagenlogik

Logische Aussagen nehmen entweder den Wert Wahr ( $1$ ) oder Falsch ( $0$ ) an.
Physische Zuordnung: Logische Wahr-/Falsch-Werte korrelieren direkt mit physischen Schalterzuständen (EIN = $1$ , AUS = $0$ ).

Schaltungen und Wahrheitstabellen

Definition 3.1 (Digitale Schaltung): Eine Schaltungsstruktur mit binären Eingangs- und Ausgangsanschlüssen, die die Werte $0$ oder $1$ akzeptiert, um eine festgelegte logische Operation auszuführen.
Wahrheitstabelle: Tabellarische Auflistung, die die Ausgangswerte für alle möglichen Eingangskombinationen definiert.
Beispiel 3.2 (Lichtschaltung mit zwei Schaltern):
- Zwei Eingangsschalter $A$ und $B$ steuern eine Lampe $L$ . Die Lampe leuchtet, wenn mindestens ein Schalter eingeschaltet ist ( $L = A \text{ OR } B$ ).
- Wahrheitstabelle:
  | A | B | L |
  | :---: | :---: | :---: |
  | 0 | 0 | 0 |
  | 0 | 1 | 1 |
  | 1 | 0 | 1 |
  | 1 | 1 | 1 |

Physische Schalt-Hardware

Regeln für den elektrischen Stromfluss:
- Strom fließt vom positiven ( $+$ ) zum negativen ( $-$ ) Pol.
- Strom benötigt durchgehende leitfähige Materialien (z. B. Kupfer). Eine physische Unterbrechung stoppt den Stromfluss.
Relais:
- Elektromechanischer Schalter, der durch eine elektromagnetische Spule betätigt wird.
- Verwendet einen Steuerstrom ( $c$ ), um einen separaten Hochleistungs-Laststrompfad ( $in$ ) zu öffnen oder zu schließen.

Schaltungsrückkopplung und Speicher

Definition 3.2 (Rückkopplung / Feedback): Das Zurückführen des Ausgangssignals einer Schaltung in einen ihrer Eingangsanschlüsse.
Funktion: Ermöglicht es Schaltungen, den historischen Zustand beizubehalten (Datenspeicherung) und programmierbare Logiksysteme zu konstruieren.
Beispiel Einbruchalarm: Die Kombination eines Bewegungsmelders und einer Sirene über ein OR-Gatter mit Ausgangsrückkopplung garantiert, dass das OR-Gatter nach dem Auslösen dauerhaft den Wert $1$ speichert und die Sirene eingeschaltet bleibt, selbst wenn der Bewegungsmelder wieder auf $0$ zurückfällt.