Show pageOld revisionsBacklinksBack to top This page is read only. You can view the source, but not change it. Ask your administrator if you think this is wrong. ~~NOTOC~~ * https://wettbewerb.informatik-biber.ch/ * https://www.informatik-biber.ch/documents/tutorials/schueleranleitung.pdf Schweizer Mathematik- und Informatik-Olympiaden starten bald (1. September) * Mathematik: https://mathematical.olympiad.ch/de/mitmachen * Informatik: https://soi.ch/ * Alle Olympiaden: https://science.olympiad.ch/wissenschafts-olympiade ====== Freifach Programmieren 2025 ====== * {{ :lehrkraefte:snr:informatik:freifach-2025:freifach-programmieren.pdf | Skript bzw. vor allem Aufgabensammlung, im Entstehen}} * Vortrag, den ich einmal zu neuronalen Netzen gehalten habe: {{ :lehrkraefte:snr:informatik:freifach-2025:neuronale-netze.pdf |}} ===== Geometrische bzw. graphentheoretische Algorithmen ===== <!-- * Vorlage: {{ :lehrkraefte:snr:informatik:freifach-2025:graphen-vorlage.py |}}--> {{ :lehrkraefte:snr:informatik:freifach-2025:vorlage-minimaler-spannbaum-prim.py | Vorlage Algorithmus von Prim, minimaler Spannbaum}} ===== Strategiespielprogrammierung (Minimax, Alpha-Beta-Suche) ===== * Vorlage: {{ :lehrkraefte:snr:informatik:freifach-2025:minischach-vorlage.py |}} * Lösung: {{ :lehrkraefte:snr:informatik:freifach-2025:minischach.py |}} * Vorlage: {{ :lehrkraefte:snr:informatik:freifach-2025:vorlage-minischach-per-minimax.py |}} * Lösung: {{ :lehrkraefte:snr:informatik:freifach-2025: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 3x3-Schach? Wer beim 3x4-Schach? Wer beim 4x4-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 ... ====== Turtle-Graphik selbst schreiben: Zuerst naiv, dann objektorientiert ====== * Vorlage: Zeichnen und als svg-Datei speichern: {{ :lehrkraefte:snr:informatik:freifach-2025: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: {{ :lehrkraefte:snr:informatik:freifach-2025:schildkroete-direkt.py |}} * Als Vorbereitung zu den nachfolgenden Aufgaben (versuche, die Programme selbst zu verstehen; vielleicht besser, die Ideen mündlich zu erklären): * {{ :lehrkraefte:snr:informatik:freifach-2025:schueler-direkt.py |}} * {{ :lehrkraefte:snr:informatik:freifach-2025:schueler-mit-dictionary.py |}} * {{ :lehrkraefte:snr:informatik:freifach-2025:schueler-objektorientiert.py |}} * Fusioniere deine Schildkrötdaten in ein Dictionary. * Fusioniere deine Funktionen in ein Objekt ''Schildkroete'' (dazu Diverses zu objektorientiertem Programmieren erklären). <!-- Musterlösungen: * {{ :lehrkraefte:snr:informatik:freifach-2025:schildkroete-mit-dictionary.py |}} * {{ :lehrkraefte:snr:informatik:freifach-2025:schildkroete-objektorientiert.py |}} --> ====== Sortieren ====== ===== Hilfsdatei zur Visualisierung der Listen ===== {{ :lehrkraefte:snr:informatik:freifach-2025:listenvisualisierung.py |}} ===== Nicht so cleveres Sortierverfahren ===== 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. <hidden Animation> {{ :lehrkraefte:snr:informatik:freifach-2025:random-swap.gif?200 |}} </hidden> ===== Bubble Sort ===== (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. <hidden Animation> {{ :lehrkraefte:snr:informatik:freifach-2025:bubble.gif?400 |}} </hidden> ===== Selection Sort ===== (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$. <hidden Animation> {{ :lehrkraefte:snr:informatik:freifach-2025:selection.gif?nolink&400 |}} </hidden> ===== Insertion Sort ===== (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. <hidden Animation> {{ :lehrkraefte:snr:informatik:freifach-2025:insertion.gif?nolink&400 |}} </hidden> ====== Bilder manipulieren (Bildverarbeitung) ====== original (RGB): {{:lehrkraefte:snr:informatik:freifach-2025:archimedes.jpg?nolink&200|}} bemalt: {{:lehrkraefte:snr:informatik:freifach-2025:archimedes_bemalt.jpg?nolink&200|}} Graustufen: {{:lehrkraefte:snr:informatik:freifach-2025:archimedes_grau.jpg?nolink&200|}} Graustufen, invertiert: {{:lehrkraefte:snr:informatik:freifach-2025:archimedes_grau-invertiert.jpg?nolink&200|}} SW-Version: {{:lehrkraefte:snr:informatik:freifach-2025:archimedes_sw.jpg?nolink&200|}} SW-Version, invertiert: {{:lehrkraefte:snr:informatik:freifach-2025:archimedes_sw-invertiert.jpg?nolink&200|}} Negativ: {{:lehrkraefte:snr:informatik:freifach-2025:archimedes_negativ.jpg?nolink&200|}} RGB-Farbrotation: {{:lehrkraefte:snr:informatik:freifach-2025:archimedes_rgb-rotated.jpg?nolink&200|}} gespiegelt: {{:lehrkraefte:snr:informatik:freifach-2025:archimedes_gespiegelt.jpg?nolink&200|}} rotiertes Bild: {{:lehrkraefte:snr:informatik:freifach-2025:archimedes_-rotated.jpg?nolink&200|}} Verpixelt/unscharf: {{:lehrkraefte:snr:informatik:freifach-2025:archimedes_verpixelt.jpg?nolink&200|}} Laplace-Kantendetektion: {{:lehrkraefte:snr:informatik:freifach-2025:archimedes_laplace.jpg?nolink&200|}} Wärmeleitungsgleichung (mit konstanten Randwerten; gif-Datei): {{:lehrkraefte:snr:informatik:freifach-2025:archimedes.gif?nolink&200|}} <!-- {{:lehrkraefte:snr:informatik:freifach-2025:archimedes_zufallskern.jpg?nolink&200|}}--> <!--{{:lehrkraefte:snr:informatik:freifach-2025:archimedes_grau_grau-zu-sw.jpg?nolink&200|}}--> <!-- Kantendetektion vom Graustufenbild: {{:lehrkraefte:snr:informatik:freifach-2025:archimedes_grau_laplace.jpg?nolink&200|}}--> <!-- {{:lehrkraefte:snr:informatik:freifach-2025:archimedes_grau_laplace-nur-horizontal.jpg?nolink&200|}} --> <!-- {{:lehrkraefte:snr:informatik:freifach-2025:archimedes_grau-neu.jpg?nolink&200|}}--> <!-- {{:lehrkraefte:snr:informatik:freifach-2025:archimedes_grau_zufallskern.jpg?nolink&200|}}--> ==== Bildmanipulation, einige Beispielprogramme ==== * Verpixeln: {{ :lehrkraefte:snr:informatik:freifach-2025:rgb-verpixelt.py |}} * Verpixeln mit 'numpy' (numerical python, erlaubt Vektorrechnung): {{ :lehrkraefte:snr:informatik:freifach-2025:rgb-verpixelt-mit-numpy.py |}} ====== Auftrag 03.06.2025: Weitere Simulationen ====== 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. * {{:lehrkraefte:snr:informatik:freifach-2025:versickerung-dokuwiki.gif?nolink&400 |}} * 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. * {{:lehrkraefte:snr:informatik:freifach-2025:koralle.gif?nolink&400|}} ===== Für Fortgeschrittene ===== siehe Abschnitt https://fginfo.ksbg.ch/dokuwiki/doku.php?id=lehrkraefte:snr:informatik:ff25#fuer_fortgeschrittene2 unten ===== Vorlagen für Grafik- und Spielprogrammierung mit Pygame ===== ==== Installation von Pygame ==== In VS Code das Terminal öffnen und dort ''pip install pygame'' eingeben. <!--siehe wohl https://www.pygame.org/wiki/GettingStarted Früher konnte man pygame wohl wie folgt unter Windows installieren (in der Powershell?). Funktioniert das noch? {{:lehrkraefte:snr:informatik:glf22:python:install-pygame.png?400|}} Sonst im Terminal in Visual Studio Code, oder Internet-Suche "install pygame, windows". --> ==== Vorlagen für Aufgaben im Skript ==== * Pygame kennenlernen, erste Zeichnungen: {{ :lehrkraefte:snr:informatik:freifach-2025:pygame-kennenlernen-vorlage.py |}} * Vorlage: Chaos game: {{ :lehrkraefte:snr:informatik:freifach-2025:chaos-game-vorlage.py |}} * Vorlage zur Spielprogrammierung: Pong Solo: {{ :lehrkraefte:snr:informatik:freifach-2025:pong-solo-vorlage.py |}} === Game of Life === * Arte, Mathewelten: Spiel des Lebens https://www.arte.tv/de/videos/097454-008-A/mathewelten/ * Vorlage: Game of Life: {{ :lehrkraefte:snr:informatik:freifach-2025:game-of-life-vorlage.py |game-of-life-vorlage.py}} === Wärmeverteilung in beheiztem Raum mit offenem Fenster (Wärmeleitungsgleichung diskret) === * Vorlage: {{ :lehrkraefte:snr:informatik:freifach-2025:waerme-vorlage.py |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 [[https://de.wikipedia.org/wiki/W%C3%A4rmeleitungsgleichung|Wärmeleitungsgleichung]] $\frac{\partial u}{\partial t} = \Delta u$.) ==== Einige Chaos-Game-Programme in Python ==== * einfachste Version: {{ :lehrkraefte:snr:informatik:freifach-2025:chaos-game-variante-1.py |}} * Punkte als Listen mit zwei Einträgen, $x$-Koordinate in nullter Komponente, $y$-Koordinate in erster Komponente: {{ :lehrkraefte:snr:informatik:freifach-2025:chaos-game-variante-2.py |}} * Liste von Punkten: {{ :lehrkraefte:snr:informatik:freifach-2025:chaos-game-variante-3.py |}} * mit numpy, verwendet Addition von Punkten/Vektoren: {{ :lehrkraefte:snr:informatik:freifach-2025:chaos-game-variante-4.py |}} * schnellere Version, Bildschirm-Update nach jeweils 1000 Malvorgängen: {{ :lehrkraefte:snr:informatik:freifach-2025:chaos-game-variante-5.py |}} ==== Graphen von Funktionen zeichnen ==== {{:lehrkraefte:snr:informatik:freifach-2025:graph-2d.jpg?nolink&200|}} * Vorlage (nach ersten eigenständigen Versuchen) {{ :lehrkraefte:snr:informatik:freifach-2025:graphen-zeichnen-vorlage.py |}} * Musterlösung {{ :lehrkraefte:snr:informatik:freifach-2025:graphen-zeichnen-musterloesung.py |}} === Für Fortgeschrittene === {{:lehrkraefte:snr:informatik:freifach-2025:graph-3d.jpg?nolink&200|}} * Den Graphen einer Funktion in zwei Variablen zeichnen, etwa $f(x,y)=\sin(x)\cdot \sin(y)$ === Herausforderung === * 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 ===== Vorbereitungen ===== * Dateinamenserweiterungen anzeigen * Python und Visual Studio Code per Microsoft App Store * Verzeichnis anlegen * Jedes Programm neue Datei ===== Für Fortgeschrittene ===== * (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 4x4-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! ==== Erkläre die Ausgabe dieses Programms! ==== <code python> 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) </code> lehrkraefte/snr/informatik/ff25.txt Last modified: 2026/02/03 11:51by Olaf Schnürer