Benutzer:Kwschneider/Softwareentwicklung/Grundlagen/Datenstrukturen und einfache Algorithmen

4. Datenstrukturen und einfache Algorithmen

Arrays/Listen, Tupel, Dictionaries

Listen (in Python auch Arrays genannt), Tupel und Dictionaries sind grundlegende Datenstrukturen, die du immer wieder brauchst. Eine Liste ist wie ein Behälter, in dem du verschiedene Werte speichern kannst – zum Beispiel Zahlen oder Wörter – und du kannst sie später einfach verändern, Elemente hinzufügen oder entfernen. Ein Tupel funktioniert ähnlich, aber die Werte darin kannst du nach dem Erstellen nicht mehr verändern: Es ist quasi eine „feste“ Liste. Dictionaries (Wörterbücher) sind besonders praktisch, wenn du Daten als Paare speichern willst, zum Beispiel Namen und dazugehörige Telefonnummern. Jedes Element besteht aus einem Schlüssel und einem Wert – so kannst du blitzschnell nachschauen, was zu welchem Schlüssel gehört. Wenn du mit diesen Daten arbeitest, brauchst du manchmal einfache Algorithmen, also Schritt-für-Schritt-Anleitungen, um Probleme zu lösen. Ein Beispiel ist die lineare Suche: Du gehst eine Liste von vorne bis hinten durch, um herauszufinden, ob ein bestimmter Wert darin vorkommt. Zum Sortieren von Listen gibt es viele Möglichkeiten – eine davon ist der sogenannte Bubble Sort. Dabei werden die Elemente immer wieder paarweise verglichen und getauscht, wenn sie in der falschen Reihenfolge stehen, bis die ganze Liste sortiert ist. Diese Techniken sind die Basis für viele Aufgaben – und in Python kannst du sie mit ein paar Zeilen Code ausprobieren!

Suchen und Sortieren (lineare Suche, Bubble Sort)

Suchen und Sortieren sind grundlegende Techniken, die dir im Programmieren immer wieder begegnen – gerade auch in Python. Die lineare Suche nutzt du, wenn du herausfinden willst, ob ein bestimmter Wert in einer Liste steckt. Das funktioniert ganz einfach: Du gehst die Liste von vorne bis hinten durch und vergleichst jedes Element mit dem Wert, den du suchst. Passt es? Super, dann bist du fertig! Wenn nicht, schaust du einfach weiter, bis du am Ende angekommen bist.

In Python sieht das zum Beispiel so aus:

 
gesucht = 42 
liste = [17, 23, 42, 5, 8] 
gefunden = False

for zahl in liste:
    if zahl == gesucht:
        gefunden = True
        break

if gefunden:
    print("Die Zahl wurde gefunden!")
else:
    print("Die Zahl ist nicht in der Liste.")

Beim Sortieren gibt es verschiedene Algorithmen. Ein ganz einfacher ist der Bubble Sort. Dabei vergleichst du immer benachbarte Werte in der Liste und vertauschst sie, wenn sie in der falschen Reihenfolge stehen. Das machst du so lange, bis keine Werte mehr vertauscht werden müssen – dann ist die Liste sortiert.

Hier ein Beispiel in Python:

 
liste = [4, 2, 7, 1, 9] 
n = len(liste)

for i in range(n):
    for j in range(0, n - i - 1):
        if liste[j] > liste[j + 1]:
            liste[j], liste[j + 1] = liste[j + 1], liste[j]

print(liste) # Ausgabe: [1, 2, 4, 7, 9]

Solche Algorithmen helfen dir, Daten zu durchsuchen oder zu ordnen – egal, ob es um Zahlen, Wörter oder andere Werte geht. Gerade in Python kannst du viele dieser Dinge mit wenigen Zeilen Code ausprobieren und bekommst so schnell ein Gefühl dafür, wie Programme im Hintergrund arbeiten.

Grundlagen der Rekursion

Rekursion bedeutet, dass sich eine Funktion in ihrem eigenen Körper selbst aufruft. Das klingt vielleicht erst mal kompliziert, ist aber eigentlich ein elegantes Werkzeug, um Probleme zu lösen, die sich in kleinere Teilprobleme zerlegen lassen. Ein klassisches Beispiel ist die Berechnung der Fakultät einer Zahl. Schauen wir uns das mal in Python an:

 
def fakultaet(n): 
    if n == 0: 
        return 1 
    else: 
        return n * fakultaet(n - 1)

print(fakultaet(5)) # Ausgabe: 120

Hier ruft sich die Funktion fakultaet immer wieder selbst auf, bis die Bedingung n == 0 erfüllt ist. Das nennt man auch die Abbruchbedingung – sie verhindert, dass die Funktion endlos weiterläuft. Rekursive Funktionen können viele Aufgaben lösen, zum Beispiel das Durchlaufen von Verzeichnissen, das Berechnen von Zahlenfolgen oder das Lösen von Rätseln wie dem berühmten Türme-von-Hanoi-Problem. Wichtig ist bei der Rekursion immer, dass es eine klare Abbruchbedingung gibt, damit das Programm nicht in einer Endlosschleife festhängt. In Python sind rekursive Lösungen oft sehr kompakt und anschaulich, aber bei sehr tiefen Rekursionen kann der Speicher knapp werden. Deshalb sollte man Rekursion immer mit Bedacht wählen und überlegen, ob auch eine Schleife zum Ziel führt.

Komplexität (Big-O-Notation – optional, je nach Niveau)

Wenn du Programme schreibst, möchtest du oft wissen, wie schnell oder wie viel Speicher sie brauchen – besonders, wenn sie mit grossen Datenmengen arbeiten. Dafür gibt es die sogenannte „Big-O-Notation“. Sie hilft, grob einzuschätzen, wie sich die Laufzeit oder der Speicherverbrauch eines Programms verhält, wenn die Eingabe immer grösser wird. Stell dir vor, du hast eine Liste von 100 Zahlen und möchtest jede Zahl einmal anschauen. In Python machst du das mit einer Schleife:

 
for zahl in liste: 
    print(zahl)

Hier läuft das Programm 100-mal – bei 1.000 Zahlen läuft es 1.000-mal. Wir sagen dann: Das hat eine Komplexität von O(n). Das „n“ steht für die Anzahl der Elemente. Je mehr Elemente, desto länger dauert’s. Bei rekursiven Funktionen wie der Fakultät von oben ist die Komplexität O(n), weil für jede Zahl bis 0 ein eigener Funktionsaufruf gemacht wird. Es gibt aber auch schnellere und langsamere Algorithmen, zum Beispiel:

• O(1): Dauert immer gleich lang, egal wie gross die Eingabe ist (z.B. Zugriff auf ein einzelnes Element in einer Liste: liste[0]).
• O(n): Die Laufzeit wächst linear mit der Eingabemenge (z.B. durch eine Liste laufen).
• O(n²): Für jede Zahl wird noch einmal die ganze Liste durchlaufen, wie bei einer verschachtelten Schleife (Doppelschleife).
• O(log n): Eine Suche, die immer die Hälfte ausschliesst (z.B. binäre Suche), ist viel schneller als das Durchgehen aller Elemente.

In der Praxis hilft dir das, bessere und schnellere Programme zu schreiben. Du musst die Big-O-Notation nicht auswendig können, aber wenn du ein grundlegendes Verständnis davon hast, erkennst du, warum manche Lösungen bei kleinen Datenmengen gut und bei grossen langsam werden. In Python kannst du oft mit eingebauten Funktionen und cleveren Datenstrukturen schon viel erreichen.

Quiz

Was beschreibt die Big-O-Notation hauptsächlich? (!Die Lesbarkeit des Codes) (!Die Anzahl der Variablen im Programm) (!Das Speicherformat einer Datei) (Die Laufzeit oder den Ressourcenverbrauch eines Algorithmus in Abhängigkeit von der Eingabemenge)

Welche Laufzeit hat ein Algorithmus mit O[n²]? (!Die Laufzeit bleibt immer gleich, egal wie viele Elemente) (!Die Laufzeit wächst exponentiell bei mehr Elementen) (Für jedes Element wird die komplette Liste erneut durchlaufen) (!Die Laufzeit halbiert sich bei doppelter Eingabegröße)

Was ist der Hauptvorteil von Versionsverwaltungssystemen wie Git? (!Sie machen den Code schneller) (Änderungen am Code können nachverfolgt und ältere Versionen wiederhergestellt werden) (!Sie übersetzen den Code in Maschinensprache) (!Sie formatieren automatisch den Quelltext)

Wie dokumentierst du in Python längere Erklärungen zu Funktionen am besten? (!Mit einfachen Anführungszeichen) (Mit Docstrings, die durch dreifache Anführungszeichen gekennzeichnet sind) (!Mit eckigen Klammern) (!Mit dem Zeichen %)

Was beschreibt ein typischer Workflow bei der Arbeit mit Git in einem Team? (!Jeder arbeitet im selben Branch und überschreibt Änderungen anderer) (!Änderungen werden per E-Mail verschickt) (Änderungen werden in einem eigenen Branch vorgenommen und später mit dem Hauptzweig zusammengeführt) (!Alle machen ihre Änderungen direkt im Hauptzweig, ohne Absprachen)