Python Listen, Schleifen und Funktionen

Listen

• Listen sind Datenstrukturen, die mehrere Werte speichern können.
• In Programmiersprachen wie Python können Listen unterschiedliche Datentypen enthalten und sind flexibel in der Größe.
• Listen werden verwendet, um zusammengehörige Werte zu speichern (z.B. Zahlen, Namen, Objekte).
• Schleifen wie for-Schleifen dienen dazu, alle Elemente einer Liste zu durchlaufen und Operationen auf jedes Element anzuwenden.

Unterprogramme

• Unterprogramme (Funktionen oder Methoden) sind Codeblöcke, die eine bestimmte Aufgabe ausführen.
• Unterprogramme helfen, ein Programm in kleinere, verständlichere Teile zu gliedern und die Wiederverwendbarkeit von Code zu fördern.
• Unterprogramme 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.

Funktionen

• Funktionen sind eine spezielle Art von Unterprogrammen, die einen Rückgabewert an das Hauptprogramm zurückgeben.
• Funktionen sind dann sinnvoll, 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.
• Der Rückgabewert einer Funktion kann im Hauptprogramm verwendet werden, um weiter Berechnungen anzustellen oder in Bedingungen zu integrieren.
• Die Konzepte von Unterprogrammen und Funktionen sind entscheidend für strukturiertes und effizientes Programmieren.

Stapel (Stack)

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

Schlange (Queue)

• Eine Schlange ist eine Datenstruktur, die das FIFO-Prinzip (First In, First Out) verwendet.
• Das erste hinzugefügte Element wird auch als erstes entfernt.
• Schlangen können z.B. für Warteschlangen bei der Paketübertragung verwendet werden.
• Daten werden mit "enque" hinzugefügt und mit "deque" entfernt.

Lineare Suche

• Ein Suchalgorithmus, der jedes Element durchsucht, bis das richtige gefunden wurde.
• Kann bei ungeordneten Daten und kleinen Datenstrukturen verwendet werden.
• Der Worst-Case ist O(n).

Binäre Suche

• Ein Suchalgorithmus, der in der Mitte beginnt und prüft, ob das Element größer oder kleiner ist als die Mitte.
• Anschließend wird die entsprechende Hälfte erneut halbiert um zu schauen, bis das Element gefunden ist.
• Funktioniert nur bei geordneten Daten.
• Der Worst-Case ist O(log n).

Binärer Suchbaum

• Eine Datenstruktur, die aus Knoten besteht.
• Jeder Knoten hat maximal zwei Kinder und hat höchstens zwei Kinder, das kleinere Element links, das grössere rechts.
• Ermöglicht schnelle Suche mit einem Average-Case von O(log n).

Bubble Sort

• Vergleicht das erste Element mit seinem Nachbarn, und tauscht sie, wenn sie in der falschen Reihenfolge sind.
• Die erste Runde endet mit dem grössten Element an letzter Stelle.
• Ist nicht sehr effizient, Worst-Case von O(n^2).

Selection Sort

• Sucht das kleinste Element in der Liste und tauscht es mit dem ersten Element.
• Wiederholt diesen Vorgang für den Rest der Liste.
• Im Allgemeinen schneller als Bubble Sort, aber ebenfalls mit einem Worst-Case von O(n^2).

Effizienz und O-Notation

• Effizienz bedeutet, dass ein Programm weniger Zeit und Ressourcen benötigt.
• Die O-Notation wird verwendet, um die Effizienz von Algorithmen zu messen.
• O(1): Die Laufzeit bleibt statisch, ändert sich nicht.
• O(log n): Die Laufzeit wächst langsamer, da die Zeit pro Schritt halbiert wird.
• O(n): Die Laufzeit wächst linear proportional zur Eingabegröße.
• O(n^2): Die Laufzeit wächst quadratisch.
• O(2^n): Die Laufzeit wächst exponentiell.
• O(n!): Die Laufzeit wächst faktoriell.

P-, NP-Probleme

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