• Skript bzw. vor allem Aufgabensammlung

• Vortrag, den ich einmal zu neuronalen Netzen gehalten habe: neuronale-netze.pdf

• Vorlage: minischach-vorlage.py
• Lösung: minischach.py

• Vorlage: vorlage-minischach-per-minimax.py
• Lösung: musterloesung-minischach-per-minimax.py

Video zum Minimax-Algorithmus: https://www.youtube.com/watch?v=l-hh51ncgDI

Suchbaum auf Wikipedia, der die $\alpha$-$\beta$-Suche gut erklärt (auch drumherum lesen! Dahinter ist auch der Algorithmus in Pseudocode, den man kopieren mag):

https://de.wikipedia.org/wiki/Alpha-Beta-Suche#Der_Algorithmus

Fragen:

• Wie viele Stellungen werden bei Minimax bewertet? Bei Minimiax mit alpha-beta-pruning?
• Kann man dies noch verbessern, indem man zuerst erfolgversprechendere Züge berechnet?
• Wer gewinnt stets beim 3×3-Schach? Wer beim 3×4-Schach? Wer beim 4×4-Schach etc.
• Bei grösseren Spielfeldern braucht das Berechnen des komplessen Spielbaums sehr lange. Finde gute Bewertungsfunktionen, die in gewisser Suchtiefe abbrechen.
• Programmiere ein anderes (kleines) Spiel, etwa Tic-Tac-Toe oder ein kleines 4-gewinnt oder Nim oder …

• Vorlage: Zeichnen und als svg-Datei speichern: svg-zeichenfenster-demo.py

(Aus der Vorlage kannst du auch lernen, wie man mit einem Python-Programm etwas in eine Datei schreibt.)

Aufgaben:

• Verwende das obige Programm, um eine svg-Datei zu erstellen, in der das Haus des Nikolaus gespeichert ist.
• Simuliere selbst eine Turtle/Schildkroete:
  • erstelle Funktionen vorwaerts, rueckwaerts, links, rechts, stifthoch, stiftrunter, setze_farbe, setze_dicke etc., mit denen du auf das svg zeichnest. (Du musst die Position und die Blickrichtung der Schildkroete speichern, und zusätzlich …; eventuell Trigonometrie erklären.)
  • Mögliche Lösung: schildkroete-direkt.py
  • Als Vorbereitung zu den nachfolgenden Aufgaben (versuche, die Programme selbst zu verstehen; vielleicht besser, die Ideen mündlich zu erklären):
    • schueler-direkt.py
    • schueler-mit-dictionary.py
    • schueler-objektorientiert.py
  • Fusioniere deine Schildkrötdaten in ein Dictionary.
  • Fusioniere deine Funktionen in ein Objekt Schildkroete (dazu Diverses zu objektorientiertem Programmieren erklären).

listenvisualisierung.py

Wiederhole, bis sortiert:

• Wähle zwei zufällige Indizes (= Positionen in der Liste).
• Wenn die beiden zugehörigen Einträge in der falschen Reihenfolge stehen, vertausche sie.

(Sortieren durch Aufsteigen (man denkt an Blasen = bubbles, die in einer Flüssigkeit aufsteigen, siehe Animation). Kurzbeschreibung: Man vergleicht nacheinander jedes Element der Liste mit seinem Nachfolger und vertauscht die beiden Elemente, wenn sie in der falschen Reihenfolge stehen. Dies wiederholt man so lange, bis die gesamte Liste sortiert ist.)

Sei $n$ die Länge der zu sortierenden Liste.

Wiederhole $n$ Mal (oder so lange, bis keine Vertauschung mehr stattgefunden hat:

• Gehe alle Listenpositionen von Position $0$ bis Position $n-1$ durch:
  • Wenn das Element an der aktuell betrachteten Listenposition echt grösser ist als das nachfolgende Listenelement, vertausche die beiden Elemente.

(Sortieren durch Auswählen. Kurzbeschreibung: Man wählt nacheiander das jeweils kleinste Element aus den noch nicht ausgewählten Elementen.)

Sei $n$ die Länge der zu sortierenden Liste.

Suche das kleinste Element der Liste und tausche es an Position 0.

Suche ab Position 1 das kleinste Element der Liste und tausche es an Position 1.

Suche ab Position 2 das kleinste Element der Liste und tausche es an Position 2.

…

Suche ab Position $n-2$ das kleinste Element der Liste und tausche es an Position $n-2$.

(Unnötig:) Suche ab Position $n-1$ das kleinste Element der Liste und tausche es an Position $n-1$.

(Sortieren durch Einfügen. Kurzbeschreibung: Man fügt nacheinander alle Elemente an der richtigen Position im bisher sortierten Teil ein.)

Man stelle sich vor, dass die zu sortierende Liste aus (Spiel-)Karten besteht, die verdeckt in einer Reihe liegen.

Man deckt die erste Karte auf. Dann ist die Liste der aufgedeckten Karten offensichtlich sortiert.

Man deckt dann die nächste Karte auf. Man lässt sie durch Vertauschungen so lange jeweils eine Position nach vorne rücken, bis sie an der richtigen Position liegt, so dass die Liste der aufgedeckten Karten sortiert ist.

Man wiederholt den vorherigen Schritt so lange, bis keine Karte mehr verdeckt daliegt.

original (RGB): bemalt:

Graustufen: Graustufen, invertiert:

SW-Version: SW-Version, invertiert:

Negativ: RGB-Farbrotation:

gespiegelt: rotiertes Bild:

Verpixelt/unscharf: Laplace-Kantendetektion:

Wärmeleitungsgleichung (mit konstanten Randwerten; gif-Datei):

• Verpixeln: rgb-verpixelt.py
• Verpixeln mit 'numpy' (numerical python, erlaubt Vektorrechnung): rgb-verpixelt-mit-numpy.py

Programmiere (aufbauend auf den bisherigen Programmen; eventuell ist es eine gute Idee, alles einmal selbst einzutippen, damit man merkt, welcher Befehl was tut; als Vorlage dürfen natürlich die bisher erstellten Programme verwendet werden):

• Versickerung von Wasser in porösem Gestein:
  • Erzeuge auf dem Spielfeld eine Felsstruktur: Mit einer gewissen Wahrscheinlichkeit wird ein Feld zu Fels (grau) oder zu Luft (schwarz).
  • In der obersten Schicht befindet sich Wasser (blau). Dieses versickert und füllt alle erreichbaren Luftfelder aus.
  • 
• Wachstum einer Koralle:
  • Am Anfang sind alle Felder schwarz.
  • Wiederhole, solange möglich:
    • Ein Partikel (weiss) startet in der linken oberen Bildschirmecke und wandert zufällig in Richtung der rechten unteren Bildschirmecke.
    • Die Wanderung endet, wenn das Partikel die rechte oder untere Bildschirmseite oder ein weisses Feld berührt.
    • Das Feld, an dem die Reise des Partikels endet, wird weiss markiert.
    • 

siehe Abschnitt https://fginfo.ksbg.ch/dokuwiki/doku.php?id=lehrkraefte:snr:informatik:ff25#fuer_fortgeschrittene2 unten

In VS Code das Terminal öffnen und dort pip install pygame eingeben.

• Pygame kennenlernen, erste Zeichnungen: pygame-kennenlernen-vorlage.py
• Vorlage: Chaos game: chaos-game-vorlage.py
• Vorlage zur Spielprogrammierung: Pong Solo: pong-solo-vorlage.py

• Arte, Mathewelten: Spiel des Lebens https://www.arte.tv/de/videos/097454-008-A/mathewelten/
• Vorlage: Game of Life: game-of-life-vorlage.py

• Vorlage: waerme-vorlage.py

Die neue Temperatur $T_{\text{neu}}(x,y)$ an einer Position $(x, y)$ berechnet sich in jedem Zeitschritt wie folgt aus den alten Temperaturen; dabei ist $\gamma$ eine Konstante (siehe Vorlage), die für numerische Stabilität sorgt:

$$T_{\text{neu}}(x,y)=T_{\text{alt}}(x,y) + \gamma \cdot \Big(\big(T_{\text{alt}}(x-1,y)-2T_{\text{alt}}(x,y)+T_{\text{alt}}(x+1,y)\big) + \big(T_{\text{alt}}(x,y-1)-2T_{\text{alt}}(x,y)+T_{\text{alt}}(x,y+1)\big)\Big)$$

(Dies ist die Diskretisierung der Wärmeleitungsgleichung $\frac{\partial u}{\partial t} = \Delta u$.)

• einfachste Version: chaos-game-variante-1.py
• Punkte als Listen mit zwei Einträgen, $x$-Koordinate in nullter Komponente, $y$-Koordinate in erster Komponente: chaos-game-variante-2.py
• Liste von Punkten: chaos-game-variante-3.py
• mit numpy, verwendet Addition von Punkten/Vektoren: chaos-game-variante-4.py
• schnellere Version, Bildschirm-Update nach jeweils 1000 Malvorgängen: chaos-game-variante-5.py

• Vorlage (nach ersten eigenständigen Versuchen) graphen-zeichnen-vorlage.py
• Musterlösung graphen-zeichnen-musterloesung.py

• Den Graphen einer Funktion in zwei Variablen zeichnen, etwa $f(x,y)=\sin(x)\cdot \sin(y)$

• Den Graphen einer Funktion in zwei Variablen drehen (z. B. Film erzeugen, etwa in gif-Datei).
  • Hierfür ist vermutlich Raytracing eine gute Idee, siehe etwa https://omaraflak.medium.com/ray-tracing-from-scratch-in-python-41670e6a96f9

• Dateinamenserweiterungen anzeigen
• Python und Visual Studio Code per Microsoft App Store
• Verzeichnis anlegen
• Jedes Programm neue Datei

• (auch mathematisch interessant) https://omaraflak.medium.com/ray-tracing-from-scratch-in-python-41670e6a96f9
• Python image library (etwa Farbbild zu Schwarz-Weiss-Bild konvertieren, oder Rot- und Grün-Werte tauschen, oder “Negativ” erzeugen, oder Kantenfilter, oder Komprimieren (etwa Farbwerte auf 10px x 10px-Quadraten konstant): https://pypi.org/project/pillow/
• Strategiespiel programmieren (etwa 4×4-Schach, Reversi(?), Minimax-Algorithmus (mit $\alpha$-$\beta$-pruning)): https://www.youtube.com/watch?v=l-hh51ncgDI
• Sortieren (klassisches Informatik-Problem):
  • Sortiere eine Liste (natürlicher Zahlen).
  • Erlaubt sind nur: Element an gegebenem Index ansehen bzw. ihm einen neuen Wert zuweisen.
  • Hilfsvariablen zum Speichern von Zahlen sind erlaubt.
  • Varianten
    • Variante 1: Nur eine Liste darf verwendet werden.
    • Variante 2: Zwei Listen dürfen verwendet werden.
  • Denke dir verschiedene Algorithmen aus. Welcher ist am schnellsten? Welcher braucht wenig Speicherplatz? Solche Fragen sind relevant, wenn man wirklich grosse Listen sortiert mit einigen Millionen Einträgen (und haben auch Auswirkungen auf den Carbon footprint; insbesondere, wenn ein Unternehmen so etwas für viele Millionen Kunden erledigt).
• Rekursion!

a = [[1,1], [1,1]]
print(a)
print(a[0][0])
a[0][0] = 42
print(a)
 
b = 2 * [2 * [1]]
print(b)
print(b[0][0])
b[0][0] = 42
print(b)