¶ Algorithmierung und Programmierung
¶ Spielerische Einführung
https://compute-it.toxicode.fr/?progression=python
https://silentteacher.toxicode.fr/hour_of_code.html?theme=basic_python
Für die Klausur zugelassen:
¶ Algorithmen
Definition: Algorithmus
Ein Algorithmus ist eine Verarbeitungsvorschrift, die aus einer endlichen Folge von eindeutig ausführbaren Anweisungen besteht, mit der man eine Vielzahl gleichartiger Aufgaben lösen kann.
Ein Algorithmus gibt an, wie Eingabegrößen schrittweise in Ausgabegrößen umgewandelt werden.
¶ Eigenschaften von Algorithmen
| Eigenschaften | Beschreibung |
|---|---|
| Finitheit | Endliche Beschreibung des Algorithmus (endliche Anzahl von Codezeilen) |
| Terminiertheit | Ausführung endet für alle Eingaben in endlicher Zeit |
| Deterministisch | Es gibt zu jedem Zeitpunkt der Ausführung nur eine Möglichkeit der Fortsetzung. |
| Determiniertheit | Gleiche Startbedingungen führen zum gleichen Ergebnis. Ein deterministischer Algorithmus ist determiniert, aber nicht umgekehrt. |
| Ausführbarkeit | jede Anweisung muss für den Prozessor (den Ausführenden) verständlich und umsetzbar sein; jeder Algorithmus ist demzufolge nur ein Algorithmus bezüglich eines Prozessors |
| Allgemeingültigkeit | das Verfahren löst eine Klasse von Problemen (nicht nur ein singuläres) |
Aufgabe 1:
Entscheiden Sie begründet, ob es für folgenden Probleme Algorithmen gibt, die alle Eigenschaften erfüllen.
- Suchen eines Wortes im Lexikon
- Addition von gemeinen Brüchen
- Regal aufbauen
- Instrument nach Noten spielen
- Aufschreiben aller geraden natürlichen Zahlen
- Schießen eines Tores beim Handball
Aufgabe 2:
Welche Eigenschaften erfüllen folgende Algorithmen nicht?
- SelectionSort
- QuickSort mit zufällig gewählten Pivot-Element
¶ Programmierparadigmen
Es existieren unterschiedliche Ansätze, Software zu entwickeln und Probleme zu lösen. Dabei werden verschiedene Programmierparadigmen unterschieden.
Ein Paradigma (Plural Paradigmen) ist eine grundsätzliche Denkweise.
Übersetzt aus dem griechischen bedeutet es „Beispiel, Vorbild, Muster“ auch „Weltsicht“ oder „Weltanschauung“.
Quelle: https://de.wikipedia.org/wiki/Paradigma
¶ Übersicht Programmierparadigmen
In der imperativen Programmierung beschreibt man WIE ein Ergebnis Schritt für Schritt erreicht wird, während man in der deklarativen Programmierung angibt, WAS das Ergebnis sein soll, ohne den genauen Ablauf festzulegen.
Folgende Tabelle vergleicht die Paradigmen (funktional und deklarativ werden wir später besprechen > nicht klausurrelevant)
| Merkmal | Prozedurorientiert | Objektorientiert | Funktional | Deklarativ |
|---|---|---|---|---|
| Grundidee | Programm besteht aus Prozeduren (Funktionen), die Daten verarbeiten | Programm besteht aus Objekten, die Daten und Verhalten kapseln | Berechnungen werden als Auswertung von Funktionen beschrieben | Beschreibt was erreicht werden soll, nicht wie |
| Zentrale Konzepte | Prozeduren, Kontrollstrukturen (Bedingung und Schleifen), Variablen | Klassen, Objekte, Vererbung, Polymorphie | Funktionen höherer Ordnung, Rekursion, Immutabilität | Regeln, Beziehungen, Ausdrücke |
| Daten und Zustand | Daten und Code getrennt | Daten und Code in Objekten vereint | Unveränderliche Daten (Immutable State) | Zustand meist implizit oder vom System verwaltet |
| Vorteile | Einfacher Aufbau, gute Kontrolle des Ablaufs | Wiederverwendbarkeit, Wartbarkeit, Modularität | Kürzerer, mathematisch klarer Code, einfache Nebenwirkungsfreiheit | Weniger Code, Fokus auf Logik statt Implementierung |
| Nachteile | Schwer wartbar bei großen Projekten | Komplexität durch Objektstrukturen | Hohe Lernkurve, weniger verbreitet | Eingeschränkte Kontrolle, ineffizient bei komplexen Abläufen |
| Typische Anwendung | Systemnahe Programmierung, einfache Skripte | Große Softwaresysteme, Simulationen | Datenanalyse, KI, wissenschaftliche Berechnungen | Datenbanken, Konfiguration, logische Systeme |
Python unterstützt das prozedur-, objektorientierte und funktionales Paradigma.
¶ Paradigma 1: Prozedurale Programmierung
Programme werden in Prozeduren (auch Funktionen oder Methoden genannt) unterteilt werden. Der Fokus liegt auf einer schrittweisen Abarbeitung von Anweisungen. Grundstrukturen
- Sequenz
- Bedingung
- Schleife
Methoden und Funktionen in Python
def ein_algorithmus(parameter1, parameter2, ...):
# mache etwas
# hex
# hex
return ergebnis # ohne return ist Rückgabewert None
# Aufruf
ein_alorithmus(argument1, argument2)
Beispiel
def summe(a, b):
return a + b
# Aufruf
summe(5, 3)
Ohne Rückgabewert: Methode. Methoden haben Seiteneffekt wie Ausgabe (print), Speichern, Änderung von Werten.
Mit Rückgabewert: Funktion. "Als pure Funktion bezeichnet man eine Funktion, deren Rückgabewert ausschließlich von ihren Argumenten abhängt und die keine Nebenwirkungen entfaltet, vergleichbar einer Abbildung in der Mathematik." Quelle
¶ Grafische Programmierung
Entwicklungsumgebung: https://strivemath.org/ide
Dokumentation von p5js. Alles JavaScript (JS). Lässt sich aber einfach nach Python übertragen.
Tolle Tutorials beim @Coding Train
Aufgabe 1:
Implementieren Sie einen Ball, der von der oberen Seite des Canvas nach unten fällt.Erweitern Sie das Programm:
a) Bälle die das Feld unten verlassen, erscheinen wieder oben.
b) 3 Bälle an unterschiedlichen zufälligen Positionen.
c) Bälle in unterschiedlichen Farben.
d) Bälle fallen mit unterschiedlichen Geschwindigkeiten.
e) Neben Bällen auch Quadrate, Dreiecke, usw.
f) Bälle ändern beim Anklicken die Farbe.
Probleme bei der Umsetzung
Die Implementierung eines Balls war verhältnismäßig einfach. Aber das Hinzufügen neues Bälle führte zu vielfältigen Problemen. Für jeden Ball mussten alle Eigenschaften (Variablen für x-Position, y-Position, Geschwindigkeit, Farbe) kopiert und umbenannt werden. Zudem musste der Code für das Verhalten des Balls (Bewegung und Wiedererscheinen nach dem Verlassen des Feldes) kopiert und angepasst werden.
Mit dem prozeduralem Paradigma scheinen wir hier an unseren Grenzen zu stoßen.
¶ Merkmale guten Codes
Es gibt viele Merkmale guten Codes wie zum Beispiel
- Lesbarkeit
- Verständlichkeit
- Wartbarkeit
- Wiederverwendbarkeit
- Effizienz
- gute Testabdeckung
- usw.
Ständige Wiederholungen im Code, wie sie in der letzten Aufgabe aufgetreten sind, gehören sicher nicht dazu. Zukünftig wollen wir folgendes Prinzip für guten Code einhalten.
DRY = “Don’t Repeat Yourself”
Zentrales Prinzip in der Softwareentwicklung, nachdem jede Information, Logik oder Struktur nur einmal im Code existieren sollte. Wird dieselbe Logik an mehreren Stellen wiederholt, erhöht das die Wahrscheinlichkeit von Fehlern, erschwert die Wartung und macht Änderungen aufwendiger, weil man sie an vielen Stellen gleichzeitig durchführen müsste.
¶ Paradigma 2: Objektorientierte Programmierung
Zur Verbesserung der Code-Qualität kann das objektorientierte Paradigma (kurz OOP) angewendet werden.
OOP beginnt immer mit der Modellierung der Software.
¶ Modellierung des Balls und der Grafik
| Ball |
|---|
| + x:int + y:int + dy:int |
| # Konstruktur + __init__(): Ball + draw(): None + move(): None |
Die Grafik kann auch als Klasse dargestellt werden (auch wenn hier ohne class implementiert, wird von strive eine Klasse erstellt).
| Grafik |
|---|
| + baelle:list[Ball] |
| # Konstruktur + __init__(): Grafik + setup(): None + draw(): None |
¶ Implementierung auf Grundlage des Modells
# Beispiel ObjektOrientierung: Fallende Bälle
# Repräsentiert einen fallenden Ball
class Ball:
# Konstruktor
def __init__(self):
# Anlegen der Attribute
self.x = random(0, windowWidth)
self.y = windowHeight
# Bewegungsgeschwindigkeit (d = delta, y = y-Achse)
self.dy = random(1,20)
self.color = (random(0,255),random(0,255),random(0,255))
# Ball zeichnet sich auf die Zeichenfläche
def draw(self):
fill(self.color)
circle(self.x, self.y, 50)
# Bewegung (Berechnung und Speicherung der neuen Position)
def move(self):
# Fallen
self.y = self.y - self.dy
# Wenn Außerhalb Spielfeld
if self.y < 0:
self.y = windowHeight
self.x = random(0.1,windowWidth)
# Liste aller Bälle
baelle = []
def setup():
global baelle
createCanvas(windowWidth,windowHeight)
# Anlegen der Bälle
for i in range(300):
# Ball() ruft den Konstruktor __init__() auf
baelle.append(Ball())
def draw():
background("black")
# Jeder Ball wird gezeichnet und bewegt sich
for ball in baelle:
ball.draw()
ball.move()
¶ Aufgabe Sonnensystem
Aufgabe
Unten finden Sie eine stark vereinfachte Implementierung unseres Sonnensystems.
a) Erstellen Sie ein UML Klassendiagramm für die Klasse Planet.
b) Erweitern Sie die Grafik um alle Planenten des Sonnensystems (mögliche Quelle: https://www.geo.de/geolino/forschung-und-technik/4917-rtkl-weltraum-unser-sonnensystem).
c) Erweitern Sie die Klasse Planet um das Attribut Name (String), sodass dieser beim Anlegen des Planten mit angegeben werden kann (Beispiel: Planet("Erde", 12756, 150, 365, (0,255,0)))
d) Zeichnen Sie den Namen des Planeten in die Grafik (text(string, x, y))
class Planet:
"""
Klasse repräsentiert einen Planeten, der um die Sonnen kreist.
"""
def __init__(self, diameter, distance, umlaufzeit, color = (255, 255, 255)):
# Durchmesser in Kilometer
self.diameter = diameter
# Sonnenabstand in mio. Kilometer
self.distance = distance
# Farbe in (R, G, B) (Datentyp = Tuple)
self.color = color
# in Erdtagen
self.umlaufzeit = umlaufzeit
# Position in Grad
self.__position = random(0,360)
def draw(self):
# Skalierung, da Abstände sonst zu groß
distance_scaled = self.distance / 3
# Berechnung der Position
pos_x = windowWidth/2 + cos(self.__position) * distance_scaled
pos_y = windowHeight/2 + sin(self.__position) * distance_scaled
# Zeichnen
fill(self.color)
circle(pos_x, pos_y, self.diameter / 800)
def move(self):
self.__position = (self.__position + 365 / self.umlaufzeit) % 360
# Liste aller Planeten
planeten = []
def setup():
createCanvas(windowWidth,windowHeight)
# Anlegen der Planeten
# TODO: alle fehlenden Planeten des Sonnensystems hinzufügen
erde = Planet(12756, 150, 365, (0,255,0))
planeten.append(erde)
def draw():
background("black")
# Sonne im Zentrum ()
fill("yellow")
circle(windowWidth/2, windowHeight/2, 50)
# Für alle Planeten
for planet in planeten:
planet.draw()
planet.move()
Lösung
Erweiterte Lösung
https://strivemath.org/ide/c1f12894-5a22-4917-9a07-7767cc3817e8?panelSize=50&consoleSize=20&fontSize=16&autoscale=false&autorun=true
¶ Klickgame
Hausaufgabe: Klickgame
Modelliert und implementiert ein Klickgame. Im Spiel sollen Kreise mit unterschiedlichen Durchmessern und Farben an verschiedenen zufälligen Position angezeigt werden. Ein Klick auf einen Kreis erhöht die Punktzahl des Spielers. Nach einem Klick auf einen Kreis soll dieser an einer neuen Position erscheinen.
Lösung mit Vererbung und Quadraten
https://strivemath.org/ide/62a90da8-60f3-4e9e-ac90-6045a95653e6?panelSize=50&consoleSize=20&fontSize=16&autoscale=false&autorun=true
¶ Pong
Hausaufgabe: Pong
...
¶ Sortieralgorithmen
Für das Sortierproblem existieren verschiedene Algorithmen.
Informieren Sie sich zur Funktionsweise folgende Sortieralgorithmen. Erklären Sie dem Kurs die Funktionsweise Ihres Algorithmus am Beispiel der Liste [5, 7, 1, 6, 4, 9, 8]
- Bubblesort
- Insertionsort
- Selectionsort
- Quicksort
Optischer Vergleich
https://www.youtube.com/watch?v=kPRA0W1kECg