← Startseite
đŸ§©

Vorlesung 3

Was ist ein Algorithmus?

Fortgeschrittene Algorithmen und Programmierung
Prof. Dr. Alexandra Mikityuk
HTW Berlin

DrĂŒcken Sie → oder Leertaste zum Starten

Willkommen zurĂŒck!

In den letzten zwei Wochen haben wir Datentypen, Variablen und Eingabe/Ausgabe in C wiederholt.

Heute machen wir den großen Sprung: Wir reden zum ersten Mal ĂŒber Algorithmen — das HerzstĂŒck der Informatik.

🎯 Das Ziel heute:
Verstehen, was ein Algorithmus ist, und die ersten Beispiele anschauen — ganz ohne Mathematik-Dschungel.

Themen der heutigen Vorlesung

Teil 1: Was ist ein Algorithmus?

  • Definition — und warum ein Kochrezept einer ist
  • Die vier Eigenschaften jedes Algorithmus
  • Erstes Beispiel: das Maximum finden

Teil 2: Der Trick von Gauß

  • Die Summe 1 + 2 + 
 + 100
  • Der geniale Trick eines 9-JĂ€hrigen
  • Warum clever denken schneller ist als hart arbeiten

Was ist ein Algorithmus?

Ein Algorithmus ist eine Schritt-fĂŒr-Schritt-Anleitung, um aus einer Eingabe eine Ausgabe zu erzeugen.

Das klingt kompliziert. Ist es aber nicht. Du benutzt Algorithmen jeden Tag — nur nennst du sie anders.

🍳

Kochrezept

Input: Zutaten
Output: Pizza

đŸ› ïž

IKEA-Anleitung

Input: Teile
Output: Regal

đŸ—ș

Wegbeschreibung

Input: Start & Ziel
Output: Route

Woher kommt das Wort "Algorithmus"?

📜

Muhammad ibn Musa
al-Khwarizmi

persischer Mathematiker, ~ 825 n. Chr.
lebte und lehrte in Bagdad

Sein Name → unser Wort

Sein Name "al-Khwarizmi" wurde im Lateinischen zu "Algorismus" — daraus wurde das deutsche "Algorithmus".

Aus seinem Buch "al-jabr" kommt ĂŒbrigens auch das Wort "Algebra".

💡 Fun Fact: Algorithmen gibt es seit ĂŒber 1200 Jahren — der erste war eine Anleitung, lineare Gleichungen zu lösen. Lange bevor es Computer gab.

Algorithmen begegnen dir jeden Tag

Du benutzt sie — meistens, ohne es zu merken.

đŸŽ”

Spotify Shuffle

Welcher Song kommt als nĂ€chstes? Ein Algorithmus mischt — aber nicht ganz zufĂ€llig.

đŸ—ș

Google Maps

Schnellster Weg zur HTW? Ein Algorithmus durchsucht Millionen Straßen in Sekunden.

🎬

Netflix-Empfehlungen

"Das könnte dir gefallen" — ein Algorithmus rĂ€t, was du als nĂ€chstes schauen willst.

đŸ“±

TikTok-Feed

Welches Video du als nĂ€chstes siehst, entscheidet ein Algorithmus — sekundenschnell.

🛒

Aldi-Kasse

Welche Schlange ist die schnellste? Auch das ist ein Algorithmus — den dein Gehirn macht.

đŸ“·

Face-ID

Dein Handy erkennt dein Gesicht in 0,2 Sekunden — dank eines Algorithmus.

Ein Kochrezept ist ein Algorithmus

🍳 Pfannkuchen-Rezept

  1. Mehl, Milch, Eier in SchĂŒssel geben
  2. Mit Schneebesen verrĂŒhren
  3. Pfanne erhitzen
  4. Etwas Teig in Pfanne geben
  5. Nach 2 Min. wenden
  6. Weitere 2 Min. braten
  7. Auf Teller legen

đŸ’» Was das gemeinsam hat

  • Eingabe: Zutaten
  • Schritte: klar, nummeriert
  • Reihenfolge: wichtig (erst rĂŒhren, dann braten!)
  • Ausgabe: Pfannkuchen
  • Endlich: irgendwann fertig
💡 Merke: Jedes gute Rezept ist ein Algorithmus. Und jeder gute Algorithmus liest sich wie ein Rezept.

Die vier Eigenschaften eines Algorithmus

1ïžâƒŁ Endlich

Er hat eine klare Anzahl an Schritten und hört irgendwann auf.

"RĂŒhre 5 Minuten" — nicht "rĂŒhre fĂŒr immer"

2ïžâƒŁ Eindeutig

Jeder Schritt ist klar formuliert. Keine MissverstÀndnisse.

"Gib 200 g Mehl dazu" — nicht "ein bisschen Mehl"

3ïžâƒŁ AusfĂŒhrbar

Der Computer (oder Mensch) kann jeden Schritt wirklich umsetzen.

Nicht: "Teleportiere das Ei"

4ïžâƒŁ Liefert Ergebnis

Am Ende kommt die erwartete Ausgabe heraus.

Pfannkuchen. Nicht Kuchen.

Unser erster Algorithmus: Wechselgeld geben

Du arbeitest an einer Kasse. Ein Kunde kauft etwas fĂŒr 3,17 € und gibt dir einen 5-€-Schein.

5,00 € − 3,17 € = 1,83 € zurĂŒck

Welche MĂŒnzen gibst du dem Kunden? Und zwar so wenige wie möglich (sonst wird seine Geldbörse dick).

2 €
1 €
50 ct
20 ct
10 ct
5 ct
2 ct
1 ct

VerfĂŒgbare MĂŒnzen

MĂŒnzwechsel — Schritt fĂŒr Schritt

Regel: nimm immer die grĂ¶ĂŸte MĂŒnze, die noch in den Restbetrag passt.

Start offen:
1,83 €
Schritt 1
1 €
→ Rest:
0,83 €
Schritt 2
50 ct
→ Rest:
0,33 €
Schritt 3
20 ct
→ Rest:
0,13 €
Schritt 4
10 ct
→ Rest:
0,03 €
Schritt 5
2 ct
→ Rest:
0,01 €
Schritt 6
1 ct
→ Rest:
0,00 € ✓
Ergebnis: 1 € + 50 ct + 20 ct + 10 ct + 2 ct + 1 ct = 6 MĂŒnzen. Fertig.

MĂŒnzwechsel — in C

// Wechselgeld berechnen — Betrag in Cent (z.B. 183 fĂŒr 1,83 €) void wechselgeld(int cent) { int muenzen[] = {200, 100, 50, 20, 10, 5, 2, 1}; for (int i = 0; i < 8; i++) { while (cent >= muenzen[i]) { // passt die MĂŒnze noch? printf("%d Cent\n", muenzen[i]); // dann nimm sie cent -= muenzen[i]; // und ziehe sie ab } } }
💡 Beobachtung: Der Code ist fast wörtlich das, was wir gerade mit den MĂŒnzen gemacht haben. Genau das ist ein Algorithmus.
🔼 Vorgeschmack: Diese Strategie ("nimm immer das GrĂ¶ĂŸte zuerst") heißt Greedy. Wir treffen sie in Vorlesung 13 wieder.

Zweites Beispiel: eine Aufgabe fĂŒr Gauß

Berechne: 1 + 2 + 3 + 4 + ... + 98 + 99 + 100

Das ist die Aufgabe, die ein Lehrer 1787 seiner Klasse gab — um die Kinder 30 Minuten zu beschĂ€ftigen.

👩 Carl Friedrich Gauß, 9 Jahre alt

... war nach wenigen Sekunden fertig. Er hatte einen Trick.

Schauen wir uns erst die naive Lösung an — dann den Trick.

Lösung A — einfach addieren

Der normale Ansatz: alle Zahlen nacheinander zusammenzÀhlen.

// 1 + 2 + 3 + ... + n per Schleife int summe_schleife(int n) { int summe = 0; for (int i = 1; i <= n; i++) { summe += i; } return summe; }
Bei n = 100: Der Computer addiert 100 Mal.
Bei n = 1.000.000: Der Computer addiert 1 Million Mal.
Bei n = 1 Milliarde: ... 1 Milliarde Additionen. Das dauert Sekunden!

Gauß' Trick — Schritt 1: Paare bilden

Schreibe die Zahlen einmal vorwĂ€rts und einmal rĂŒckwĂ€rts, untereinander:

1
2
3
4


97
98
99
100
100
99
98
97


4
3
2
1

Jetzt die Spalten zusammenrechnen ↓

Gauß' Trick — Schritt 2: alle Paare geben 101!

1
+
100
=
101
2
+
99
=
101
3
+
98
=
101






99
+
2
=
101
100
+
1
=
101
Magie: jede Spalte gibt dieselbe Summe — 101. Das ist der ganze Trick!

Gauß' Trick — Schritt 3: multiplizieren

Wir haben 100 Spalten. Jede ergibt 101.

100 × 101 = 10.100

Aber Moment — wir haben jede Zahl zweimal gezĂ€hlt (einmal vorwĂ€rts, einmal rĂŒckwĂ€rts).

Also: durch 2 teilen!

10.100 Ă· 2 = 5.050
✹ Fertig. Drei Rechenoperationen — statt hundert Additionen.

Die Formel von Gauß

FĂŒr n Zahlen (1 bis n) funktioniert derselbe Trick:

  • Es gibt n Spalten.
  • Jede Spalte ergibt n + 1.
  • Das ergibt n · (n + 1).
  • Wir haben doppelt gezĂ€hlt → durch 2.
1 + 2 + 
 + n = n · (n+1) / 2

Probe: n=100 → 100 · 101 / 2 = 5.050 ✓

Gauß-Formel in C

// Summe 1 bis N per Formel long long summe_gauss(long long n) { return n * (n + 1) / 2; }

🐱 Lösung A (Schleife)

Bei n = 1 Milliarde:

~ 3 Sekunden

1 Milliarde Additionen

🚀 Lösung B (Gauß)

Bei n = 1 Milliarde:

< 0,000001 s

3 Rechenoperationen

Die große Erkenntnis

Beide Lösungen laufen auf demselben Computer.
Beide ergeben dasselbe Ergebnis.

Der Unterschied liegt nur im Algorithmus.

Eine schlaue Idee schlÀgt jeden schnellen Prozessor.
Darum lohnt es sich, Algorithmen zu studieren — auch wenn der Computer sehr schnell ist.

Drittes Beispiel: Palindrom?

Ein Palindrom ist ein Wort, das vorwĂ€rts und rĂŒckwĂ€rts gleich gelesen wird.

ANNA

✓ Palindrom

OTTO

✓ Palindrom

HALLO

✗ kein Palindrom

Frage: Wie kann ein Computer das prĂŒfen?

Palindrom-Algorithmus: von außen nach innen

Wir vergleichen erstes mit letztem, zweites mit vorletztem, und so weiter.

Beispiel: ANNA

Schritt 1
A
N
N
A
A = A ✓
Schritt 2
A
N
N
A
N = N ✓ → Palindrom!

Beispiel: HALLO

Schritt 1
H
A
L
L
O
H ≠ O ✗ → kein Palindrom (Abbruch!)
💡 Smart: Sobald ein Paar nicht passt, brechen wir ab. Nicht alle Buchstaben prĂŒfen!

Palindrom — in C

// PrĂŒfe, ob ein Wort ein Palindrom ist (1 = ja, 0 = nein) int ist_palindrom(char wort[], int n) { int links = 0; int rechts = n - 1; while (links < rechts) { if (wort[links] != wort[rechts]) { return 0; // gleich abbrechen! } links++; rechts--; } return 1; // alle Paare passten }
💡 Beobachtung: Zwei Variablen links und rechts wandern aufeinander zu. Sobald ein Paar nicht passt → sofort raus. Schneller geht es nicht.

Wie viele Schritte braucht ein Algorithmus?

Bisher haben wir drei Algorithmen gesehen. ZĂ€hlen wir mal, wie viele Schritte sie brauchen:

AlgorithmusEingabegrĂ¶ĂŸeSchritte ungefĂ€hr
MĂŒnzwechselBetrag in Centhöchstens 8 MĂŒnzsorten × wenige MĂŒnzen
Summe (Schleife)Zahl nn Additionen
Summe (Gauß-Formel)Zahl n3 Operationen (immer!)
PalindromWort mit n Buchstabenhöchstens n/2 Vergleiche
🔼 Vorschau: Manche Algorithmen wachsen mit der Eingabe, andere nicht. Diesen Unterschied mathematisch beschreiben lernen wir in Vorlesung 5 — die Big-O-Notation.

Mini-Übung: Erfinde deinen eigenen Algorithmus

👉 Beispiel: "Ein Glas Wasser holen"

  1. Stehe vom Stuhl auf
  2. Gehe in die KĂŒche
  3. Öffne den Schrank, nimm ein Glas heraus
  4. Halte es unter den Wasserhahn
  5. Drehe den Hahn auf, warte bis das Glas voll ist, drehe zu
  6. Trinke đŸ„€
Jetzt du: schreibe Schritt fĂŒr Schritt einen Algorithmus fĂŒr 

  • đŸŠ· ZĂ€hne putzen
  • 🍕 Pizza online bestellen
  • 📚 Ein bestimmtes Buch in der Bibliothek finden

Tipp: jeder Schritt muss eindeutig sein. "Mach es einfach schön" zÀhlt nicht!

🧠 Quiz 1

Welche dieser Anweisungen ist kein Algorithmus?

A) Rezept fĂŒr Apfelkuchen
B) Schritt-fĂŒr-Schritt-Anleitung zum Schuhe binden
C) „Mach die Wohnung einfach schön"
D) Python-Programm, das Primzahlen berechnet

Tipp: Ein Algorithmus muss eindeutig sein.

🧠 Quiz 2

Du sollst die Summe 1+2+
+1000 berechnen. Welcher Weg ist klĂŒger?

A) 1000 Zahlen einzeln mit dem Taschenrechner addieren
B) Gauß-Formel: 1000 · 1001 / 2 = 500.500
C) Einen schnelleren Taschenrechner kaufen
D) Google fragen

Ein besserer Algorithmus schlÀgt einen besseren Rechner.

Zusammenfassung

  • Ein Algorithmus ist eine klare Schritt-fĂŒr-Schritt-Anleitung von Input zu Output.
  • Er muss endlich, eindeutig, ausfĂŒhrbar sein und ein Ergebnis liefern.
  • Wir haben drei Algorithmen gesehen: MĂŒnzwechsel (Greedy), Summe (Schleife & Gauß), Palindrom.
  • Der Gauß-Trick zeigt: eine clevere Idee kann Milliarden Operationen sparen.
  • Manche Algorithmen haben immer gleich viele Schritte, andere wachsen mit der Eingabe.
📚 NĂ€chste Woche: Unser erster großer Algorithmen-Klassiker — Sortieren. Wir bringen Ordnung ins Chaos mit Bubble-, Selection- und Insertion-Sort.

Wichtig fĂŒr spĂ€ter

  • ✅ Was ein Algorithmus ist, in eigenen Worten erklĂ€ren können
  • ✅ Die vier Eigenschaften: endlich, eindeutig, ausfĂŒhrbar, Ergebnis
  • ✅ Den Gauß-Trick nachvollziehen (Paare mit Summe n+1)
  • ✅ Zu erkennen, dass ein guter Algorithmus Milliarden Operationen sparen kann

Prof. Dr. Alexandra Mikityuk
HTW Berlin

Viel Spaß beim Ausprobieren im Lab!

© 2026 Prof. Dr. Alexandra Mikityuk | HTW Berlin
1 / 28