Python-Listen und -Unterprogramme

Listen

• Listen sind Datenstrukturen, die mehrere Werte speichern können und in Sprachen wie Python unterschiedliche Datentypen enthalten können.
• Sie sind flexibel in der Größe und nützlich zum Speichern von Wertesammlungen, auf die später zugegriffen werden kann.
• Listen werden verwendet, um mehrere zusammengehörige Werte zu speichern, z.B. Zahlen, Namen oder Objekte.
• Schleifen wie die for-Schleife werden verwendet, um alle Elemente einer Liste zu durchlaufen und Operationen auf jedes Element anzuwenden, wie z. B. Berechnungen oder Ausgaben.

Unterprogramme

• Unterprogramme (Funktionen oder Methoden) sind Codeblöcke, die eine bestimmte Aufgabe ausführen.
• Sie helfen, Programme in kleinere, verständlichere Teile zu gliedern und die Wiederverwendbarkeit von Code zu fördern.
• Unterprogramme strukturieren ein Programm und ermöglichen es, gleiche Aufgaben an mehreren Stellen im Code auszuführen, ohne sie jedes Mal neu schreiben zu müssen.
• Unterprogramme können Eingabewerte (Parameter) erhalten, die sie in ihren Berechnungen oder Prozessen verwenden, wodurch sie flexibel mit verschiedenen Daten arbeiten können.

Funktionen

• Funktionen sind eine spezielle Art von Unterprogrammen, die einen Rückgabewert an das Hauptprogramm zurückgeben.
• Sie sind nützlich, wenn eine Berechnung oder Verarbeitung durchgeführt wird und das Ergebnis an das Hauptprogramm zurückgegeben werden soll.
• Funktionen liefern ein Ergebnis, das durch das Schlüsselwort return zurückgegeben wird und im Hauptprogramm weiterverarbeitet oder gespeichert werden kann.
• Der Rückgabewert einer Funktion kann im Hauptprogramm für weitere Berechnungen verwendet oder in Bedingungen integriert werden.
• Listen und Unterprogramme sind entscheidend für ein strukturiertes und effizientes Programm, da sie Programme übersichtlicher gestalten und den Code modularer halten.

Stapel

• Ein Stapel ist eine Datenstruktur, die das LIFO-Prinzip (Last In, First Out) verwendet.
• Das zuletzt hinzugefügte Element wird zuerst entfernt.
• Stapel eignen sich für Funktionen wie "search history" oder "ctrl z".
• Elemente werden mit "push" hinzugefügt und mit "pop" entfernt.

Schlange

• Eine Schlange ist eine Datenstruktur, die das FIFO-Prinzip (First In, First Out) verwendet.
• Das erste Element wird auch als erstes entfernt.
• Schlangen können z.B. bei Warteschlangen mit Paketversendung verwendet werden, wobei Informationen in der Reihenfolge ihres Eintreffens verarbeitet werden.
• Daten werden mit "enque" hinzugefügt und mit "deque" entfernt.

Lineare Suche

• Die lineare Suche ist ein Suchalgorithmus, der jedes Element durchsucht, bis das richtige gefunden wurde.
• Sie kann bei ungeordneten Daten und kleinen Datenstrukturen verwendet werden.
• Der Worst Case liegt bei O(n).

Binäre Suche

• Die binäre Suche ist ein Suchalgorithmus, der in der Mitte beginnt und prüft, ob das Element größer oder kleiner ist.
• Dann wird die kleinere/größere Hälfte erneut halbiert, um zu prüfen, ob das Element größer oder kleiner als die Mitte ist.
• Binäre Suche kann nur bei geordneten Daten verwendet werden und hat einen Worst Case von O(log n).

Binärer Suchbaum

• Ein binärer Suchbaum ist eine Datenstruktur, die aus Knoten besteht, wobei jeder Knoten höchstens zwei Kinder hat (links kleiner, rechts größer).
• Sie ermöglicht eine schnelle Suche mit einem Average Case von O(log n).

Bubble Sort

• Bubble Sort ist ein Sortieralgorithmus, der das erste Element mit seinem Nachbarn vergleicht und sie vertauscht, wenn sie in der falschen Reihenfolge sind.
• Die erste Runde endet mit dem größten Element an der letzten Stelle.
• Bubble Sort ist nicht sehr effizient und hat einen Worst Case von O(n^2).

Selection Sort

• Selection Sort ist ein Sortieralgorithmus, der das kleinste Element in der Liste sucht und es mit dem ersten Element der Liste vertauscht.
• Es ist schneller als Bubble Sort, hat aber trotzdem einen Worst Case von O(n^2).

Effizienz und O-Notation

• Effizienz bedeutet, ein Programm so zu ändern, dass es weniger Zeit und Ressourcen benötigt.
• In der Informatik wird die Effizienz mit der O-Notation gemessen.
  • O(1): Bleibt statisch, ändert sich nicht.
  • O(log n): Die Laufzeit wird langsamer, da sich die Zeit pro Schritt halbiert.
  • O(n): Wächst proportional zur Eingabegröße (N = 6 => 6).
  • O(n^2): Wächst quadratisch (N = 5 => 25).
  • O(2^n): Wächst exponentiell zur Eingabe (N = 4 => 16).
  • O(n!): Wächst faktoriell (5! => 54321 = 120).

P- versus NP-Probleme

• P = NP Problem: eines der schwierigsten Probleme der Informatik und Mathematik.
• Es wird untersucht, ob jedes Problem, das schnell überprüfbar ist (wie ein Zauberwürfel), auch schnell lösbar ist.
• P = polynomiale Zeit (bezeichnet die Laufzeit eines Algorithmus, die mit einem Polynom der Eingabedatengröße wächst).
• NP = die Menge von Entscheidungsproblemen, deren Lösungen in polynomialer Zeit verifiziert werden können.