Bisher haben wir uns mit Variablen beschäftigt, die nur einen Wert speichern können:
x = 3 (eine Zahl / “integer”)
name = "Hallo" (einen Text / “string”)
ist_wahr = True (einen Wahrheitswert / “boolean”)
In der Informatik ist es jedoch oft nötig, mit vielen Werten gleichzeitig arbeiten zu können, gerade im Kontext von Big Data. Eine Möglichkeit, in Python mit vielen Werten zu arbeiten, sind Listen.
Liste
Eine Liste ist eine Sammlung von Werten, die in einer Variable gespeichert werden können. Eine Liste kann beliebig viele Werte enthalten und diese Werte können von einem beliebigen Typ wie zum Beispiel “integer”, “string” oder “boolean” sein.
Listen erstellen
Folgendes Beispiel zeigt, wie eine Liste in Python definiert wird. Wir können dabei, wie auch bei anderen Variablentypen, beliebige Namen verwenden. Die Inhalte der Liste werden in eckigen Klammern [] geschrieben und die einzelnen Werte werden durch Kommas , getrennt.
Zugriff auf Listen
Wenn wir auf die einzelnen Werte in der Liste zugreifen möchten, können wir dies mit dem Index tun. Der Index ist eine Zahl, die angibt, an welcher Stelle sich der Wert in der Liste befindet. Der Index beginnt bei 0, das heisst, der erste Wert in der Liste hat den Index 0, der zweite Wert hat den Index 1 und so weiter.
Listen-Werte verändern
Um den Wert an einer bestimmten Stelle in der Liste zu ändern, können wir ebenfalls den Index verwenden. Wir können den Wert an dieser Stelle einfach durch einen neuen Wert ersetzen.
Länge einer Liste
Der Befehl len(liste) gibt die Länge der Liste zurück, also die Anzahl der Werte, die in der Liste gespeichert sind. Dies ist nützlich, wenn wir wissen möchten, wie viele Werte in der Liste enthalten sind.
Listen erfüllen vielfältige Aufgaben in der Informatik. Sie können verwendet werden, um Daten zu speichern, zu sortieren, zu filtern und zu analysieren. In Python gibt es viele eingebaute Funktionen und Methoden, die speziell für Listen entwickelt wurden, um diese Aufgaben zu erleichtern.
Zahlen-Liste summieren
Folgendes Beispiel zeigt auf, wie eine Liste in einer Funktion verwendet werden kann, um eine Summe zu berechnen. Die Funktion berechne_summe nimmt eine Liste von Zahlen als Eingabe und gibt die Summe dieser Zahlen zurück.
Zeit-Tabelle
Notieren Sie die Werte der Variablen i, daten[i] und summe am Anfang und am Ende jedes Durchlaufs der Schleife in einer Tabelle:
Durchlauf
i
daten[i]
summe
1. Durchlauf (Anfang)
___
___
___
1. Durchlauf (Ende)
___
___
___
2. Durchlauf (Anfang)
___
___
___
2. Durchlauf (Ende)
___
___
___
3. Durchlauf (Anfang)
___
___
___
3. Durchlauf (Ende)
___
___
___
4. Durchlauf (Anfang)
___
___
___
4. Durchlauf (Ende)
___
___
___
5. Durchlauf (Anfang)
___
___
___
5. Durchlauf (Ende)
___
___
___
6. Durchlauf (Anfang)
___
___
___
6. Durchlauf (Ende)
___
___
___
💡 Musterlösung anzeigen
Die Liste ist [4, 2, -6, 17, 5, 12].
Durchlauf
i
daten[i]
summe
1. Durchlauf (Anfang)
0
4
0
1. Durchlauf (Ende)
1
2
4
2. Durchlauf (Anfang)
1
2
4
2. Durchlauf (Ende)
2
-6
6
3. Durchlauf (Anfang)
2
-6
6
3. Durchlauf (Ende)
3
17
0
4. Durchlauf (Anfang)
3
17
0
4. Durchlauf (Ende)
4
5
17
5. Durchlauf (Anfang)
4
5
17
5. Durchlauf (Ende)
5
12
22
6. Durchlauf (Anfang)
5
12
22
6. Durchlauf (Ende)
6
Error!
34
Index am Ende der Schleife
Am Ende des Codes in Abschnitt hat die Variable i den Wert 6, obschon die Liste nur 6 Elemente hat. Erklären Sie, weshalb dies so ist. Ist das ein Problem? Warum oder warum nicht?
💡 Musterlösung anzeigen
Die Variable i wird in der Schleife von 0 bis 5 erhöht, um auf die Indizes der Liste zuzugreifen. Nachdem die Schleife den letzten Index (5) erreicht hat, wird i erneut um 1 erhöht, wodurch sie den Wert 6 annimmt. Dies ist kein Problem, da die Schleife bereits alle Elemente der Liste durchlaufen hat und der Wert von i nach der Schleife nicht mehr verwendet wird.
Schleifen ohne Index
Etwas effizienter kann auf jedes Element der Liste mit dem Befehl for zahl in liste zugegriffen werden. Dabei wird die Variable zahl nacheinander auf jedes Element der Liste gesetzt.
Aufgabe
Erstellen Sie eine Funktion vergroessere_um_fuenf(liste), die mithilfe einer Schleife jeden Wert in der Liste mit den Werten [20, -7, 8, 2, 1, 6] um 5 erhöht. Die Anzahl der Wiederholungen der Schleife soll dabei mit len() bestimmt werden. Kontrollieren Sie Ihr Programm mit print(liste).
💡 Musterlösung anzeigen
Aufgabe
Entwickeln Sie eine Funktion berechne_durchschnitt(liste), die für die Liste (z.B. [5, 0, -2, 3, 51, 8, 13, -100, -10, -1]) den Durchschnittswert der Beträge aller Elemente berechnet und mit print() ausgibt.
Der Durchschnitt einer Liste von Zahlen ist die Summe aller Zahlen geteilt durch die Anzahl der Zahlen.
💡 Musterlösung anzeigen
Aufgabe
Erstellen Sie ein Programm, das alle geraden Zahlen in der Liste daten = [5, 7, 8, 6, 3] verdoppelt. Kontrollieren Sie Ihr Programm mit print(daten).
💡 Musterlösung anzeigen
Aufgabe
Das Skalarprodukt wird in vielen Lebensbereichen verwendet, z.B. in der Mathematik, Physik und Informatik. Im Alltag begegnen wir dem Skalarprodukt häufig in der Finanzwelt, z.B. bei der Berechnung des Gesamtpreises von Produkten: %
Produkt
Mengem
Preisp
800 g
2.- / kg
1200 g
2.50 / kg
2300 g
5.- / kg
Schreiben Sie eine Funktion, die das Skalarprodukt zweier Listen berechnet. Das Skalarprodukt ist die Summe der Produkte der jeweils entsprechenden Elemente beider Listen. Beispiel: Für die Listen m = [0.8, 1.2, 2.3] (in kg) und p = [2.0, 2.5, 5.0] (Preis pro kg) berechnet das Skalarprodukt den Gesamtpreis.
Wie berechnen wir den Gesamtpreis? Dies kann mit dem Skalarprodukt gemacht werden: m[0] * p[0] + m[1] * p[1] + ... + m[-1] * p[-1]. Zur Erinnerung: m[-1] gibt uns das letzte (hinterste) Element der Liste m.1
💡 Musterlösung anzeigen
Kleinste Zahl in einer Liste
Mit folgendem Code können wir die kleinste Zahl in einer Liste finden. Wir verwenden eine Schleife, um alle Zahlen in der Liste zu durchlaufen und die kleinste Zahl zu finden. Der Code gibt am Schluss die kleinste Zahl in der Liste aus.
Aufgabe
Verändern Sie den Code aus Abschnitt so, dass die Funktion finde_kleinste_zahl nicht nur die kleinste Zahl in einer Liste von Zahlen ausgibt, sondern auch deren Position (Index) in der Liste.
💡 Musterlösung anzeigen
Aufgabe
Schreiben Sie eine Funktion, welche gleichzeitig den grössten und den kleinsten Wert sowie deren Indizes (Positionen) in einer Liste von Zahlen zurückgibt.
💡 Musterlösung anzeigen
Aufgabe
Schreiben Sie eine Funktion, die zählt, wie oft die Zahl 10 in einer Liste von Zahlen vorkommt. Testen Sie Ihre Funktion mit der Liste [1, 2, 3, 10, 4, 10, 5]. Die Funktion soll die Anzahl der Vorkommen von 10 ausgeben (2 in diesem Fall).
💡 Musterlösung anzeigen
Challenge
Schreiben Sie eine Funktion, die überprüft, ob eine Liste von Zahlen sortiert ist oder nicht. Falls die Liste sortiert ist, soll die Funktion den Wert True zurückgeben, ansonsten den Wert False.
Tipps: %
Gehen Sie jedes Element der Liste mit einer Schleife durch, und überprüfen Sie, dass das Element grösser oder gleich dem vorigen Element ist.
return bricht die Funktion ab und gibt einen Wert an das Hauptprogramm zurück. Sie können also, sobald eine Zahl in falscher Reihenfolge gefunden worden ist, direkt False zurückgeben.
Falls Sie nie ein falsches Element gefunden haben, geben Sie am Ende der Funktion True zurück.
💡 Musterlösung anzeigen
Aufgabe
Eine Supermarkt-Kette bittet Sie, die Rabatte auf ausgewählte Produkte zu berechnen. Sie gibt Ihnen hierzu zwei Listen: die erste Liste enthält die Preise der Produkte ohne Rabatt und die zweite Liste enthält die Rabatte in Prozent.
Das Beispiel bedeutet, dass das erste Produkt nicht 39.95, sondern 30 % weniger als 39.95 kosten sollte, also 70 % von 39.95 = 27.965.
Der rabattierte Preis eines einzelnen Produkts wird folgendermassen berechnet:
Schreiben Sie eine Funktion, die die rabattierten Preise für alle Produkte berechnet und als Liste auf der Konsole ausgibt. Sie müssen die Preise nicht runden.
💡 Musterlösung anzeigen
Aufgabe
Sie hatten zum Mittagessen ein Sandwich sowie einen Energy-Drink. Sie möchten gerne wissen, wie viele Kalorien das gesamte Mittagessen hatte, die Nährwerte sind jedoch nur pro 100 Gramm oder 100 Milliliter (wobei 100 Gramm = 100 Milliliter sind) angegeben. Berechnen Sie die Gesamt-Kalorien, indem Sie folgende zwei Listen erstellen:
l_kcal: Liste der Kalorien pro 100 Gramm (bzw. 100 Milliliter) für das Sandwich und den Energy-Drink.
l_gramm: Liste der Mengen in Gramm, bzw. Milliliter für das Sandwich und den Energy-Drink.
Die Nährwert-Informationen entnehmen Sie dem Bild Abschnitt
💡 Musterlösung anzeigen
Challenge
Schreiben Sie nun eine Funktion, mit der Sie beliebig viele Nährwerte und Mengenangaben mittels Input eingeben. Die Funktion soll folgendes machen:
Mittels input("...") nach einer Kalorienangabe für ein Lebensmittel fragen (pro 100 Gramm).
Mittels input("...") nach der konsumierten Menge für dasselbe Lebensmittel fragen.
Mittels input("...") fragen, ob noch weitere Lebensmittel hinzukommen.
Schritt 1-2 sollen so lange wiederholt werden, bis in Schritt 3 False eingegeben wird.
💡 Musterlösung anzeigen
Algorithmen
Sortier-Algorithmen
Eine der häufigsten Anwendungen in der Informatik ist das Sortieren von Daten. Es gibt viele verschiedene Algorithmen, um Daten zu sortieren, und jeder Algorithmus hat seine eigenen Vor- und Nachteile, insbesondere hinsichtlich der Geschwindigkeit und der benötigten Rechenleistung. Im Folgenden wird der Bubble-Sort-Algorithmus vorgestellt, der eine einfache Methode ist, um Daten zu sortieren. Der Bubble-Sort-Algorithmus funktioniert, indem er die Liste von Werten durchläuft und benachbarte Werte vergleicht. Wenn ein Wert grösser ist als der nächste Wert, werden die beiden Werte vertauscht. Dieser Vorgang wird so lange wiederholt, bis die gesamte Liste sortiert ist. Die ersten zwölf Schritte des Bubble-Sort-Algorithmus sind in Abschnitt dargestellt. Der Algorithmus wird so lange wiederholt, bis die gesamte Liste sortiert ist.
Folgender Code zeigt, wie der Bubble-Sort-Algorithmus in Python implementiert werden kann. Der Algorithmus wird in einer Funktion bubble_sort definiert, die eine Liste von Zahlen als Eingabe erhält und die sortierte Liste zurückgibt. Die Funktion verwendet eine Schleife, um die Liste zu durchlaufen und benachbarte Werte zu vergleichen. Wenn ein Wert grösser ist als der nächste Wert, werden die beiden Werte vertauscht. Dieser Vorgang wird so lange wiederholt, bis die gesamte Liste sortiert ist.
Aufgabe
Schauen Sie sich den Python-Code für Bubble Sort an sowie die folgenden drei Listen:
x = [3, 4, 1, -3, 6]
x = [3, 4, 5, 6, 7] %
x = [7, 6, 5, 4, 3]
Notieren Sie von Hand, wie die Listen nach jedem Durchgang der äusseren Schleife aussehen (für eine Liste von Länge 5 sollten Sie beispielsweise 4 Zwischenresultate notieren). Kontrollieren Sie Ihr Resultat, indem Sie das Programm mit diesen Listen ausführen.
💡 Musterlösung anzeigen
Zeitkomplexität
Um zu verstehen, wie lange ein Algorithmus benötigt, um eine Aufgabe zu lösen, ist es wichtig, die Zeitkomplexität des Algorithmus zu analysieren. Wenn ein Algorithmus beispielsweise mit grösserwerdender Anzahl Zahlen im Quadrat länger dauert, ist dies viel ungünstiger als ein Algorithmus, der so lange dauert, wie die Anzahl der Zahlen. In der Informatik wird die Zeitkomplexität eines Algorithmus oft in Bezug auf die Eingabegrösse angegeben, um zu verstehen, wie sich die Laufzeit des Algorithmus mit zunehmender Eingabegrösse verändert. Im vorliegenden Fall ist die Eingabegrösse die Anzahl der Werte in der Liste, die sortiert werden soll.
Der Bubble-Sort-Algorithmus verwendet zwei verschachtelte Schleifen: die äussere Schleife durchläuft die Liste \(n-\) Mal, und die innere Schleife durchläuft die Liste ebenfalls \(n-1\) Mal, um die benachbarten Werte zu vergleichen und zu vertauschen. Die gesamte Anzahl der Vergleiche, die der Algorithmus durchführt, ist also \((n-1)^2\). Durch Umformung dieser Gleichung erhalten wir: [(n-1)^2=-2n+1] Wir erkennen, dass bei sehr grossen Werten von \(n\) die quadratische Komponente \(\colorbox{yellow}{\ensuremath{n^2}}\) dominiert, während die lineare Komponente \(-2n\) und die Konstante \(1\) im Vergleich vernachlässigbar werden. Daher wird die Zeitkomplexität des Bubble-Sort-Algorithmus als \(O(n^2)\) ausgedrückt (s. Abschnitt).
Big-O-Notation
Die Laufzeit eines Algorithmus wird oft mit der sogenannten Big O-Notation angegeben, die die Wachstumsrate der Laufzeit in Bezug auf die Eingabegrösse beschreibt. Dabei wird die Laufzeit in der Form \(O(f(n))\) (“Big O von f von n”) angegeben, wobei \(f(n)\) eine Funktion ist, die die Anzahl der Schritte beschreibt, die der Algorithmus benötigt, um eine Eingabe der Grösse \(n\) zu verarbeiten.
In der Big-O-Notation werden nur die dominanten Terme berücksichtigt, da sie den Hauptfaktor für das Wachstum der Laufzeit darstellen. Im Fall von Bubble Sort dominiert die quadratische Komponente (\(n^2\)), wenn \(n\) sehr gross wird. Daher wird die Laufzeit des Algorithmus als \(O(n^2)\) ausgedrückt. Entscheidend ist nur der Term, der das Wachstum der Laufzeit dominiert, und in diesem Fall ist es die quadratische Komponente \(n^2\).
Verschiedene typische Laufzeiten von Algorithmen werden in der Big-O-Notation wie folgt ausgedrückt:
\(O(1)\): konstante Laufzeit, unabhängig von der Eingabegrösse
\(O(\log n)\): logarithmische Laufzeit, z.B. bei binärer Suche
\(O(n)\): lineare Laufzeit, z.B. bei einfacher Iteration durch eine Liste
\(O(n \log n)\): lineare-logarithmische Laufzeit, z.B. bei effizienten Sortieralgorithmen wie Mergesort oder Quicksort
\(O(n^2)\): quadratische Laufzeit, z.B. bei einfachen Sortieralgorithmen wie Bubble Sort oder Insertion Sort
\(O(n^3)\): kubische Laufzeit, z.B. bei bestimmten Algorithmen für Matrizenmultiplikation
\(O(2^n)\): exponentielle Laufzeit, z.B. bei bestimmten rekursiven Algorithmen
\(O(n!)\): faktoriale Laufzeit, z.B. bei bestimmten Brute-Force-Algorithmen
Einige dieser Laufzeiten sind in Abschnitt grafisch dargestellt, um die Unterschiede in der Wachstumsrate zu verdeutlichen.
Die Laufzeitkomplexität des Bubble-Sort-Algorithmus kann folgendermassen in der Big-O-Notation ausgedrückt werden:
nicht optimierte Version: Da wir zwei verschachtelte Schleifen haben, die je \(n-1\) Durchläufe machen, beträgt die Anzahl der Vergleiche [(n-1)^2] Das bedeutet: Für eine Liste mit 6 Elementen sind das \(5^2 = 25\) Vergleiche. Die Anzahl der Vergleiche beträgt [(n-1)^2 = - 2n + 1] In der Big O-Notation wird dies als \(O(n^2)\) ausgedrückt, da die quadratische Komponente \(n^2\) dominiert, wenn \(n\) sehr gross wird.
optimierte Version: In der optimierten Version wird die innere Schleife nach jedem Durchlauf der äusseren Schleife um 1 verkleinert, da das grösste Element nach jedem Durchlauf an die richtige Position verschoben wird. Daher werden im ersten Durchlauf \(n-1\) Vergleiche durchgeführt, im zweiten Durchlauf \(n-2\) Vergleiche, und so weiter, bis im letzten Durchlauf nur noch 1 Vergleich durchgeführt wird. Die Anzahl der Vergleiche entspricht daher der Summe der Zahlen von 1 bis \(n-1\). Für eine Liste mit 6 Elementen ergibt das also beispielsweise \(\displaystyle\sum_{m=1}^{5} m = 1 + 2 + 3 + 4 + 5 = 15\) Vergleiche.
Diese Summe der Zahlen von 1 bis \(n-1\) kann mit folgender Formel berechnet werden: [ (n-1) + (n-2) + + 2 + 1 = _{m=1}^{n-1} m = ]
Die Herleitung dieser Formel ist in Abschnitt dargestellt.
Die Formel lässt sich wie folgt umformen, um die quadratische Komponente \(n^2\) hervorzuheben: [ = - n] Auch in der “optimierten” Version dominiert die quadratische Komponente \(n^2\), wenn \(n\) sehr gross wird, sodass die Laufzeit ebenfalls als \(O(n^2)\) ausgedrückt wird.
Wir sehen also, dass die Optimierung die Anzahl der Vergleiche reduziert, aber die grundsätzliche Komplexität des Algorithmus bleibt \(O(n^2)\).
Laufzeit der optimierten Version
Die Summe aller natürlichen Zahlen von 1 bis \(n-1\) lässt sich folgendermassen als Formel ausdrücken:
$$
_{m=1}^{n-1} m & = \ & = \ & = n + n + n + \ & = n \ & = - n \ & O(n^2)
$$
In der ersten Zeile haben wir die Summe der Zahlen von 1 bis \(n-1\) aufgeschrieben, die Summe setzt sich aus \(n-1\) Summanden (Bestandteilen) zusammen. In der zweiten Zeile haben wir die Summanden mit gleichen Farben zu Paaren zusammengefasst, so dass wir nun nur noch halb so viele Paare (\(\frac{n-1}{2}\)) haben. Jedes dieser Paare ist gleich \(n\). Wir haben also am Schluss \(\frac{n-1}{2}\) Paare, die alle gleich \(n\) sind, was zu \(\frac{(n-1)}{2}\cdot n\) führt. In der letzten Zeile haben wir die Formel in eine Form gebracht, die die quadratische Komponente \(n^2\) hervorhebt, um die Laufzeit in der Big-O-Notation zu bestimmen.
Such-Algorithmen
In der Informatik stellt sich häufig die Frage, wie man möglichst schnell herausfinden kann, ob eine bestimmte Zahl in einer Liste enthalten ist. Dies kann beispielsweise bei der Suche nach einem Namen in einem Telefonbuch oder bei der Suche nach einem Produkt in einem Online-Shop der Fall sein. Die Effizienz der Suche hängt stark davon ab, wie die Daten organisiert sind.
Ist die Liste unsortiert, wie zum Beispiel bei x = [5, 3, 8, 20, 2, 10], bleibt uns nichts anderes übrig, als jedes Element der Liste einzeln zu überprüfen. Dies entspricht einer linearen Suche, bei der im ungünstigsten Fall alle Elemente betrachtet werden müssen.
Ist die Liste jedoch bereits sortiert, wie zum Beispiel bei x = [2, 3, 5, 8, 10, 20], können wir effizientere Suchverfahren anwenden. Dies lässt sich mit der Suche nach einem Gegenstand in einem Koffer vergleichen. Wenn der Koffer unordentlich gepackt ist, müssen wir jeden einzelnen Gegenstand herausnehmen, um den gesuchten zu finden. Wenn der Koffer jedoch ordentlich gepackt ist, können wir die Gegenstände viel schneller finden (siehe Abschnitt).
Ein besonders schneller Algorithmus ist die sogenannte binäre Suche, bei der die Liste immer wieder halbiert wird, um das gesuchte Element zu finden.
Das Suchen bezeichnet allgemein den Vorgang, ein bestimmtes Element in einer Datenmenge möglichst effizient zu finden. Im Folgenden lernen wir die binäre Suche als effizienten Such-Algorithmus für sortierte Listen kennen.
Der Algorithmus zur Umsetzung der binären Suche ist in Python wie folgt implementiert:
Bei solchen, etwas komplexeren Codes, kann es nützlich sein, sich die Entwicklung der Variablenwerte im Verlauf der Ausführung des Codes von Hand zu notieren (siehe Abschnitt).
links
mitte
rechts
1. while
2. while
3. while
***
Beispiel
Wir können für folgende Liste [4, 8, 9, 11, 15, 23, 42] die binäre Suche verwenden. Der Code sucht nach der Zahl 9 und gibt den Index der Zahl in der Liste zurück. Wir evaluieren jeweils die Werte der Variablen links, mitte und rechts nach Zeile 9, um den Ablauf des Codes zu verstehen. Die Tabelle Abschnitt zeigt die Werte der Variablen nach jedem Schritt der Schleife.
links
mitte
rechts
1. while
0
3
6
2. while
0
1
2
3. while
2
2
2
Laufzeit der binären Suche
Die binäre Suche hat eine Zeitkomplexität von \(O(\log n)\), was bedeutet, dass die Laufzeit des Algorithmus logarithmisch mit der Anzahl der Werte in der Liste wächst. Dies macht die binäre Suche für grosse Datenmengen sehr effizient, insbesondere im Vergleich zur linearen Suche, die eine Zeitkomplexität von \(O(n)\) hat.
Beweis: Die binäre Suche halbiert die Anzahl der zu durchsuchenden Elemente in jedem Schritt. Wenn die Liste \(n\) Elemente enthält, wird die Anzahl der verbleibenden Elemente nach \(k\) Schritten durch die Formel \(\frac{n}{2^k}\) gegeben. Um das gesuchte Element zu finden, muss die Anzahl der verbleibenden Elemente auf 1 reduziert werden, was bedeutet, dass \(\frac{n}{2^k} = 1\) sein muss. Durch Umstellen dieser Gleichung erhalten wir \(n = 2^k\), was bedeutet, dass \(k = \log_2(n)\) ist. Daher wächst die Anzahl der Schritte logarithmisch mit der Anzahl der Elemente in der Liste, was zu einer Zeitkomplexität von \(O(\log n)\) führt.
Laufzeit der linearen und binären Suche
Wie viele Vergleiche müssen im schlimmsten Fall bei einer linearen Suche durchgeführt werden, um ein Element in einer Liste der Länge \(100\) zu finden? Wie viele Vergleiche müssen im schlimmsten Fall bei einer binären Suche durchgeführt werden, um ein Element in einer Liste der Länge \(1000\) zu finden? Berechnen Sie die Anzahl der Vergleiche für beide Suchverfahren und vergleichen Sie die Ergebnisse.
💡 Musterlösung anzeigen
lineare Suche: Im schlimmsten Fall müssen alle Elemente der Liste überprüft werden, um das gesuchte Element zu finden. Daher beträgt die Anzahl der Vergleiche \(100\) für eine Liste der Länge \(100\) bzw. \(1000\) für eine Liste der Länge \(1000\).
binäre Suche: Die Anzahl der Vergleiche bei einer binären Suche kann mit der Formel \(\log_2(n)\) berechnet werden, wobei \(n\) die Anzahl der Elemente in der Liste ist. Für eine Liste der Länge \(100\) beträgt die Anzahl der Vergleiche \(\log_2(100) \approx 6.64\), was aufgerundet \(7\) Vergleiche ergibt. Für eine Liste der Länge \(1000\) beträgt die Anzahl der Vergleiche \(\log_2(1000) \approx 9.97\), was aufgerundet \(10\) Vergleiche ergibt.
Laufzeitkomplexität eines Codes analysieren
Betrachten Sie folgenden Codes, der eine Liste von Zahlen gegenüber einer anderen Liste von Zahlen überprüft und die Anzahl der gemeinsamen Elemente zählt. Analysieren Sie die Laufzeitkomplexität dieses Codes in Bezug auf die Länge der beiden Listen. Die Länge der ersten Liste wird mit \(n\) und die Länge der zweiten Liste mit \(m\) bezeichnet.
💡 Musterlösung anzeigen
Die Laufzeitkomplexität dieses Codes ist \(O(n \cdot m)\), wobei \(n\) die Länge der ersten Liste (liste1) und \(m\) die Länge der zweiten Liste (liste2) ist. Dies liegt daran, dass der Code zwei verschachtelte Schleifen verwendet: Die äussere Schleife durchläuft jedes Element in liste1 (was \(n\) Schritte erfordert), und für jedes Element in liste1 durchläuft die innere Schleife jedes Element in liste2 (was \(m\) Schritte erfordert). Daher multiplizieren sich die Anzahl der Schritte der beiden Schleifen, was zu einer Gesamtzahl von \(n \cdot m\) Schritten führt.
Aufgabe
Verwenden Sie die folgende Liste: [-20, -17, -13, -13, 2, 5, 7, 7, 9, 10]. Vollziehen Sie den Ablauf des Programms für folgende Werte
-20
6
Zeichnen Sie eine Zeit-Tabelle wie in Abschnitt und überprüfen Sie Ihre Resultate, indem Sie zwischen den Zeilen 9 und 10 print-Befehle verwenden, um die Werte von links, mitte und rechts auszugeben.
Aufgabe
Ändern Sie den Code für die binäre Suche so ab, dass ein while True: gemeinsam mit einer booleschen Variable gefunden sowie dem Befehl break verwendet wird.
💡 Musterlösung anzeigen
Listen verändern
Häufig müssen Listen verändert werden, beispielsweise um Elemente hinzuzufügen oder zu entfernen, oder um diese neu zu ordnen. Python bietet hierfür verschiedene Methoden an. Methoden sind Funktionen, die auf bestimmte Variablen angewandt werden. In \(\ref{sec:classes}\) werden wir lernen, wie Methoden definiert werden können. Hier lernen wir einige vordefinierte Methoden für Listen kennen.
Listen verändern
Listen können in Python dynamisch verändert werden, indem Elemente hinzugefügt oder entfernt werden. Einige der wichtigsten Methoden sind:
liste.append(wert) fügt am Ende der Liste einen neuen Wert hinzu.
liste.insert(index, wert) fügt an der angegebenen Position (index) einen neuen Wert ein. Alle nachfolgenden Elemente werden nach rechts verschoben.
liste.pop(index) entfernt das Element an der angegebenen Position (index) und gibt es zurück. Wird kein Index angegeben, wird das letzte Element entfernt.
Weitere Methoden zum Verändern von Listen sind in der offiziellen Python-Dokumentation aufgelistet.
Elemente hinzufügen und entfernen
Folgender Code zeigt auf, wie Listen in Python verändert werden können. Wir erstellen eine Liste von Zahlen und fügen dann neue Zahlen hinzu, entfernen das letzte Element und das erste Element. Die Ergebnisse werden anschliessend ausgegeben.
Funktionen und Methoden
Funktionen und Methoden sind beides Möglichkeiten, um eine bestimmte Aufgabe auszuführen. Der Hauptunterschied zwischen ihnen besteht darin, dass Funktionen unabhängig von einem Objekt (Variable) definiert werden, während Methoden an ein Objekt (Variable) gebunden sind und auf dieses Objekt angewendet werden.
Ein Beispiel für eine Funktion ist:
Methoden hingegen sind Funktionen, die an ein Objekt gebunden sind und auf dieses Objekt angewendet werden. Sie werden mit einem Punkt (.) aufgerufen, gefolgt vom Methodennamen und den Argumenten in Klammern. Methoden können den Zustand des Objekts verändern oder Informationen über das Objekt zurückgeben.
Ein Beispiel für eine Methode ist die append-Methode einer Liste:
Eine Methode hat als ersten Parameter immer das Objekt, auf dem sie angewendet wird (in diesem Fall meine_liste), obschon dieser Parameter in der Methode nicht explizit (in einer Klammer) übergeben wird. Weitere Parameter können zusätzlich übergeben werden, wie zum Beispiel die Zahl 4 in diesem Fall. Im obigen Beispiel wären die Parameter der append-Methode also meine_liste und 4.
Speziell an Methoden ist, dass sie das Objekt, auf dem sie angewendet werden, verändern können, ohne dass ein Gleichzeichen benötigt wird.
Aufgabe
Fügen Sie der Liste fruechte = ["Apfel", "Banane"] zuerst "Orange" am Ende hinzu, dann "Kiwi" an der zweiten Stelle. Entfernen Sie danach das erste Element der Liste und geben Sie die Liste aus.
💡 Musterlösung anzeigen
Aufgabe
Erstellen Sie eine leere Liste zahlen. Fügen Sie mit einer Schleife die Zahlen 1 bis 5 mit append hinzu. Entfernen Sie dann das Element an der dritten Stelle mit pop und geben Sie die Liste aus.
💡 Musterlösung anzeigen
Aufgabe
Gegeben ist die Liste farben = ["rot", "blau", "grün"]. Fügen Sie "gelb" an der zweiten Stelle ein und entfernen Sie das letzte Element mit .pop(). Geben Sie die veränderte Liste aus.
💡 Musterlösung anzeigen
Aufgabe
Gegeben seien zwei gleich lange Listen A und B.
Schreiben Sie eine Python-Funktion verschmelzen(A, B), welche die beiden Listen zu einer Liste C zusammenfügt. Das Zusammenfügen soll “reissverschlussartig” geschehen: Elemente aus A und B sollen sich in C abwechseln, beginnend mit einem Element aus A. Betrachten Sie dazu die Beispiele. Schliesslich soll die Liste C mit print ausgegeben werden.
💡 Musterlösung anzeigen
Aufgabe
Gegeben sei eine Liste A von ganzen Zahlen.
Schreiben Sie eine Python-Funktion entferne_duplikate(A), welche eine neue Liste B erstellt, welche genau die Elemente von A enthält aber ohne Duplikate (mehr als einmal vorkommende Elemente). Die Liste B soll schliesslich durch einen print-Befehl ausgegeben werden.
Zum Beispiel:
Tipps: %
Erstellen Sie eine leere Liste B, in der die Elemente von A ohne Duplikate gespeichert werden sollen.
Gehen Sie jedes Element von A mit einer Schleife durch.
Für jedes Element von A überprüfen Sie, ob es bereits in der Liste B enthalten ist. Wenn nicht, fügen Sie es am Ende von B hinzu. Dazu benötigen eine innere Schleife, um die Elemente von B zu überprüfen.
Verwenden Sie eine bool’sche Variable (True oder False), um zu verfolgen, ob ein Element bereits in der Liste B vorhanden ist.
💡 Musterlösung anzeigen
Challenge
Probieren Sie weitere Methoden zum Verändern von Listen aus, indem Sie folgende Begriffe verwenden: .extend(...), .remove(...), .sort(), .reverse(). Eine Auflistung aller möglichen Methoden für ein Objekt der Klasse list finden Sie in der offiziellen Python-Dokumentation.
Wörterbücher (dictionaries)
In der Informatik werden Daten oft nicht nur als Listen, sondern auch als sogenannte Dictionaries (Wörterbücher) gespeichert. Ein Dictionary ist eine Sammlung von Schlüssel-Wert-Paaren. Anders als bei Listen werden die Werte nicht durch einen Index, sondern durch einen eindeutigen Schlüssel (key) lokalisiert. Dies ist vielfach praktischer als die Speicherung in Listen, da man direkt mit einem Begriff auf die Werte zugreifen kann, ohne die Position des Werts in der Liste kennen zu müssen.
Dictionary
Ein Dictionary ist eine Datenstruktur, die jedem Schlüssel (key) einen Wert (value) zuordnet. Die Schlüssel müssen eindeutig sein und können z.B. Zahlen oder Zeichenketten sein.
Dictionary für Kontaktdaten
Ein typisches Beispiel für ein Dictionary ist ein Adressbuch, in dem zu jedem Namen die Telefonnummer gespeichert ist:
Dictionary für Produktpreise
Auch in einem Online-Shop werden Produkte oft mit ihren Preisen als Dictionary gespeichert:
Werte hinzufügen und ändern
Sie können einem Dictionary neue Schlüssel-Wert-Paare hinzufügen oder bestehende Werte ändern:
Alle Schlüssel und Werte durchgehen
Mit einer Schleife können Sie alle Einträge eines Dictionaries durchgehen:
Überprüfen, ob ein Schlüssel existiert
Um zu überprüfen, ob ein Schlüssel in einem Dictionary existiert, können Sie den in-Operator verwenden:
Aufgabe
Erstellen Sie ein Dictionary noten, das die Noten von drei Schülern speichert: "Lea" (Note 5.5), "Tim" (Note 4.0), "Sara" (Note 6.0). Geben Sie die Note von "Sara" aus.
💡 Musterlösung anzeigen
Aufgabe
Fügen Sie dem Dictionary noten aus der vorherigen Aufgabe einen neuen Schüler “Alex” mit der Note 5.0 hinzu. Ändern Sie Tims Note auf 4.5 und geben Sie das gesamte Dictionary aus.
💡 Musterlösung anzeigen
Aufgabe
Sie verwalten die Lagerbestände eines kleinen Geschäfts. Erstellen Sie ein Dictionary lager mit den Produkten "Cola" (10 Stück), "Fanta" (5 Stück) und "Wasser" (20 Stück). Schreiben Sie ein Programm, das die Anzahl der Flaschen "Fanta" um 2 reduziert (z.B. durch Verkauf) und das neue Dictionary ausgibt.
💡 Musterlösung anzeigen
Aufgabe
Erstellen Sie ein Dictionary, das für verschiedene Länder die jeweilige Hauptstadt speichert:
Für die Schweiz: "Hier gibt es keine Hauptstadt, nur eine Bundesstadt."
Für Deutschland: "Berlin"
Für Frankreich: "Paris"
Lassen Sie den Benutzer mit input() nach einem Land fragen und geben Sie die entsprechende Hauptstadt aus dem Dictionary mit print aus.
Falls das eingegebene Land nicht im Dictionary existiert, soll ausgegeben werden:
"Land nicht gefunden."
siehe Abschnitt für Hinweise dazu, wie dies umgesetzt werden kann.
💡 Musterlösung anzeigen
Aufgabe
Carlas Englisch ist nicht so gut. Helfen Sie Carla, ein paar Sätze zu übersetzen. Schreiben Sie in einem Dictionary namens deutsch_zu_englisch die Übersetzung der folgenden Wörter in Englisch: “Die”, “Der”, “Das”, “Stuhl”, “Sofa”, “Lampe”, “ist”, “rot”, “grün”, “gelb”, “blau”, “schwarz”, “weiss”.
Implementieren Sie eine Funktion uebersetzen(satz), die eine Liste erstellt, welche die englische Übersetzung jedes Wortes in der Liste satz enthält. Die Liste soll Wort für Wort erstellt und am Schluss mit print ausgegeben werden.
Vorlage:
Tipp: Arbeiten Sie sich schrittweise heran! %
Schreiben Sie nun einen Code, um auf jedes Element (jedes Wort) der Liste satz zuzugreifen, speichern Sie das Wort in einer Variable wort.
Greifen Sie nun auf das entsprechende englische Wort im Dictionary deutsch_zu_englisch zu.
Fügen Sie das englische Wort der neuen Liste hinzu.
💡 Musterlösung anzeigen
Die Werte eines Dictionaries können selber ebenfalls Listen, Dictionaries oder andere Python-Objekte sein, was besonders nützlich ist, wenn mehrere Werte zu einem Schlüssel gespeichert werden sollen.
Aufgabe
Erstellen Sie ein Dictionary likes, das für verschiedene Nutzer die Anzahl der Likes auf einem Social-Media-Post als Liste speichert. Beispiel:
Schreiben Sie einen Code, der für einen eingegebenen Nutzernamen die durchschnittliche Anzahl der Likes berechnet und ausgibt.
💡 Musterlösung anzeigen
Aufgabe
Erstellen Sie ein Dictionary wettervorhersage, das für verschiedene Tage die Wetterdaten als weiteres Dictionary speichert. Beispiel:
Schreiben Sie einen Code, der für einen eingegebenen Tag die Temperatur und ob es regnet ausgibt. Falls es regnet oder unter 15 Grad ist, soll zusätzlich die Meldung “Ich gehe mit dem Bus” ausgegeben werden, ansonsten “Ich gehe per Fahrrad”.
💡 Musterlösung anzeigen
Mengen (sets)
Mengen (en. sets) sind eine weitere wichtige Datenstruktur in der Informatik. Eine Menge ist eine Sammlung von einzigartigen Elementen, die keine bestimmte Reihenfolge haben. In Python werden Mengen mit geschweiften Klammern { und } oder mit dem Befehl set() erstellt.
In Python stehen die Mengenoperationen, welche Ihnen aus dem Mathematikunterricht wohlvertraut sind, zur Verfügung. Wir werden die drei mengentheoretischen Operationen Vereinigung, Schnittmenge und Differenz einführen und mittels 2 illustrieren.
\(\mathbf{A \cup B}\), in Python: \ \(A \cup B := \setcm{x\in M}{(x\in A) \lor (x\in B)}\)\ Die von \(A\) und \(B\). Die Vereinigung von \(A\) und \(B\) enthält genau alle Elemente, die in \(A\)oder\(B\) liegen.
\(\mathbf{A \cap B}\), in Python: A & B\ \(A \cap B := \setcm{x\in M}{(x\in A) \land (x\in B)}\)\ Die von \(A\) und \(B\). Die Schnittmenge von \(A\) und \(B\) enthält genau alle Elemente, die in \(A\)und in \(B\) liegen.
\(\mathbf{A\setminus B}\), in Python: A - B\ \(A\setminus B := \setcm{x\in M}{(x\in A) \land (x\notin B)}\)\ Die von \(A\) und \(B\). Die Differenz von \(A\) und \(B\) enthält genau alle Elemente, die in \(A\) aber nicht in \(B\) liegen.
Falls \(M\) eine endliche Menge ist (nicht unendlich viele Elemente enthält), dann bezeichnet \(\abs{M}\) die Anzahl der Elemente in \(M\). In Python finden wir die Anzahl der Elemente in der Menge \(M\) mit dem Befehl len(M).
Mengen erstellen und Mengenoperationen anwenden
Sets können in Python mit geschweiften Klammern { und } oder mit dem Befehl set() erstellt werden. Folgender Code zeigt die drei Mengenoperationen an einem Beispiel mit Früchten.
Aufgabe
An einer Schule können Schüler mehrere Kurse wählen. Manche Kurse überschneiden sich, andere sind Pflicht.
Finden Sie alle Kurse, die mindestens einer der Schüler belegt.
Finden Sie alle Kurse, die von allen drei Schülern gemeinsam belegt werden.
Bestimmen Sie alle Kurse, die exklusiv nur Schüler A hat.
Ermitteln Sie die Pflichtkurse, die zwar existieren, aber von mindestens einem Schüler nicht gewählt wurden.
Stellen Sie eine Liste aller Wahlkurse zusammen, die alle drei Schüler gemeinsam gewählt haben.
Tipp: Mit dem Befehl set(liste) können Sie eine Liste in eine Menge umwandeln. Mit dem Befehl list(menge) können Sie eine Menge wieder in eine Liste umwandeln. %
💡 Musterlösung anzeigen
Tuple
Tuples sind eine weitere grundlegende Datenstruktur in Python, die Ähnlichkeiten mit Listen aufweisen, sich aber in einem entscheidenden Punkt unterscheiden: ihrer Unveränderlichkeit.
Definition
Ein Tuple in Python ist eine geordnete, unveränderliche Sammlung von Elementen. Tuples sind ähnlich wie Listen, können aber nach ihrer Erstellung nicht mehr verändert werden. Man erstellt sie, indem man Elemente in runde Klammern setzt, getrennt durch Kommas.
Tuples in Python haben die folgenden Eigenschaften:
Unveränderlichkeit (Immutability): Versucht man, ein Element zu ändern, erhält man eine Fehlermeldung. Zum Beispiel würde koordinaten[0] = 5 einen Fehler verursachen.
Geordnetheit: Die Reihenfolge der Elemente bleibt erhalten.
Heterogenität: Ein Tuple kann verschiedene Datentypen enthalten, wie ganze Zahlen, Zeichenketten oder sogar andere Tuples. Zum Beispiel: person = ('Anna', 30, True).
Anwendungsbereiche: Tuples werden oft verwendet, wenn man sicherstellen will, dass Daten nicht versehentlich geändert werden, wie z. B. bei Datenbankkoordinaten, Rückgabewerten von Funktionen oder als Schlüssel in einem Wörterbuch.
Tuples sind besonders nützlich, wenn Sie eine feste Anzahl von Elementen haben, die zusammengehören, wie z. B. die Koordinaten eines Punktes in einem 2D-Raum (x, y). Tuples können auch als Rückgabewerte von Funktionen verwendet werden, um mehrere Werte gleichzeitig zurückzugeben.
Tuples für 2D-Koordinaten
Tuples für Rückgabewerte von Funktionen
Funktion mit mehreren Rückgabewerten
Schreiben Sie eine Funktion min_max(liste), die eine Liste von Zahlen als Eingabe erhält und ein Tuple zurückgibt, das die kleinste und die grösste Zahl in der Liste enthält.
💡 Musterlösung anzeigen
Nützlichkeit von Tuples und Rückgabewerte
Tuples sind besonders nützlich, wenn Sie eine feste Anzahl von Elementen haben, die zusammengehören, wie z. B. die Koordinaten eines Punktes in einem 2D-Raum (x, y). Tuples können auch als Rückgabewerte von Funktionen verwendet werden, um mehrere Werte gleichzeitig zurückzugeben.
Weshalb geben Funktionen mit mehreren Rückgabewerten ein Tuple zurück, anstatt eine Liste zu verwenden? In Python gibt es keine speziellen ``mehrfachen Rückgabewerte’’. Stattdessen fasst die Sprache mehrere Werte automatisch zu einem Tuple zusammen. Ein Tuple eignet sich dafür besonders gut, weil es eine feste Anzahl von Werten mit einer festen Bedeutung beschreibt (z. B. Breite und Höhe oder Quotient und Rest). Listen hingegen stehen eher für veränderbare Sammlungen von Elementen. Dass Tuples unveränderlich sind, ist dabei ein zusätzlicher Vorteil, aber nicht der Hauptgrund für ihre Verwendung.
Weitere Aufgaben
Notenspiegel für mehrere Personen
Sie möchten ein Programm schreiben, das für mehrere Personen in Ihrer Klasse den Notenschnitt berechnet und prüft, ob jede Person ihr Ziel erreicht hat.
Teilaufgabe 1: Schreiben Sie die Funktion .
Der Parameter ist ein Dictionary, in dem jeder Schlüssel ein Name ist und jeder Wert eine Liste von Noten für die jeweilige Person (oder Punkten).
Die Funktion berechnet für jede Person den Durchschnitt und gibt ein Dictionary zurück, in dem die Namen den berechneten Schnitten zugeordnet sind.