1.2 Algorithmik – Unterrichtsmaterial
Das Geburtstagsparadoxon: Simulation und Rekursion in Python
Dieses Unterrichtsmaterial führt anhand des berühmten Geburtstagsparadoxons in die Programmierung mit Python ein. Die Lernenden berechnen die Wahrscheinlichkeiten zunächst mittels Schleifen und implementieren den Algorithmus anschliessend rekursiv.
Zufall und Wahrscheinlichkeiten simulieren in Python
Anhand praktischer Programmieraufgaben in Python lernen Schülerinnen und Schüler, Zufallszahlen zu generieren und Wahrscheinlichkeiten durch Simulationen zu ermitteln. Dabei werden verschiedene Kontrollstrukturen wie Schleifen und Bedingungen angewendet, um spielerische Szenarien wie Würfelspiele auszuwerten.
Einführung in die Assemblersprache mit dem Little Man Computer
Dieses Unterrichtsmaterial führt in die Assemblersprache ein und zeigt anhand des Little Man Computers (LMC), wie grundlegende Programmierkonzepte, Labels, Verzweigungen, Schleifen und Algorithmen auf Maschinennahmen-Ebene umgesetzt werden. Die Lernenden können praktische Programmieraufgaben direkt im Assembler lösen.
Rekursives Programmieren
Dieses Leitprogramm für das Gymnasium führt umfassend in das Konzept der Rekursion in der Informatik und Mathematik ein. Die Lernenden setzen sich intensiv mit rekursiven Programmierstrukturen auseinander und implementieren entsprechende Algorithmen.
InfoTraffic: Informatikkonzepte im Alltag (Verkehrssteuerung)
Das Material stellt alltagsnahe Module zur Verkehrssteuerung vor, die Konzepte wie Aussagenlogik, Warteschlangentheorie und dynamische Systeme mittels Markov-Ketten behandeln. Es verknüpft theoretische Informatikkonzepte anschaulich mit praktischen Alltagsszenarien.
Lineare und binäre Suche im Vergleich
Dieses Unterrichtsmaterial vergleicht die lineare und die binäre Suche anhand von Python-Codebeispielen und analysiert deren algorithmische Komplexität. Zudem wird ein experimenteller Leistungsvergleich der beiden Suchverfahren über verschiedene Listenlängen hinweg durchgeführt.
Rekursion und Algorithmen in Python
Dieses Unterrichtsmaterial behandelt das Konzept der Rekursion anhand von Beispielen wie der Fakultätsfunktion, der Ackermann-Funktion und verschiedenen rekursiven Code-Snippets. Die Lernenden analysieren das Laufzeitverhalten, führen Rekursionen von Hand durch und implementieren Algorithmen in Python.
Einführung in die Rekursion
Dieses Unterrichtsmaterial führt in das Konzept der Rekursion ein, ausgehend von Top-down- und Bottom-up-Ansätzen zur Problemlösung. Es zeigt auf, wie kleinere Teillösungen zur Bewältigung grösserer Probleme beitragen und beleuchtet typische Anwendungsbereiche.
Entwurf und Anwendung von Backtracking-Algorithmen
Dieses Unterrichtsmaterial für die 11. Klasse führt Lernende über die Modellierung von Suchbäumen und deren Speicherprobleme schrittweise an Backtracking-Algorithmen heran. Die Schülerinnen und Schüler lernen, wie das rekursive Trial-and-Error-Verfahren das speicherintensive Erstellen ganzer Suchbäume umgeht.
Konstruktive Induktion und rekursive Algorithmen an Graphbeispielen
Das Material behandelt die Methode der konstruktiven Induktion zur systematischen Entwicklung rekursiver Algorithmen am Beispiel von Graphalgorithmen. Es wird untersucht, wie naive Implementierungen bei zyklischen Graphen versagen können, und wie man diese durch fundierte Ansätze korrigiert, wobei Bezüge zu Speicherbereinigung und Python hergestellt werden.
Unterrichtssequenz Induktion in der Kombinatorik
Diese Unterrichtssequenz für das Gymnasium erweitert das Lehrmittel 'Algorithmen und Künstliche Intelligenz' um das Thema Induktion im Bereich Kombinatorik. Das Material wurde im Rahmen der Fachdidaktik Informatik erarbeitet und bietet einen theoretischen und methodischen Zugang zu algorithmischen beziehungsweise mathematischen Beweisprinzipien.
Unterrichtssequenz Induktion und Kombinatorik
Eine Unterrichtssequenz für das Gymnasium zur Induktion als Erweiterung des Lehrmittels Algorithmen und Künstliche Intelligenz. Sie behandelt im Kapitel Kombinatorik und Induktion mathematisch-informatische Methoden.
Leitprogramm: Entwurfsmethoden für Algorithmen (Greedy & Teile-und-Herrsche)
Dieses Leitprogramm führt Schülerinnen und Schüler in zwei zentrale Entwurfsmethoden für Algorithmen ein: die Greedy-Methode sowie das Teile-und-Herrsche-Prinzip. Anhand von Beispielen lernen die Lernenden, diese Strategien anzuwenden und eigene algorithmische Lösungen für spezifische Probleme zu entwickeln.
Leitprogramm: Automaten Schritt für Schritt erstellen
Dieses Leitprogramm führt Lernende Schritt für Schritt durch die Analyse und den Entwurf eines Automaten. Die Gedankengänge werden nachvollziehbar erklärt, um eigenständige Problemlösungen zu ermöglichen.
Mentoriert Arbeit: Einführung in randomisierte Algorithmen
Diese mentoriert Arbeit führt Schülerinnen und Schüler in das Themengebiet der randomisierten Algorithmen ein. Anhand von Beispielen wie Quicksort, Gegnerüberlistung und Matrixverifikation wird die Stärke des Zufalls in der Informatik sowie die Anwendung der Wahrscheinlichkeitstheorie erarbeitet.
Leitprogramm zu Bäumen und Backtracking
Dieses Leitprogramm für das letzte Gymnasialjahr führt in die Graphentheorie, Baumstrukturen und den Backtracking-Algorithmus ein. Es baut auf Vorkenntnissen in Wahrscheinlichkeitsrechnung und rekursiver Programmierung auf.
Matchings in Graphen und algorithmische Lösungsstrategien
Dieses Unterrichtsmaterial führt Schülerinnen und Schüler in das Konzept von Matchings in Graphen ein. Es behandelt die Modellierung von Zuteilungsproblemen, Greedy-Algorithmen, Backtracking, verbessernde Pfade sowie die Ungarische Methode.
Corewars - Das Duell der Programme
In diesem Unterrichtsmaterial lernen die Schülerinnen und Schüler in der Programmierumgebung Corewars spielerisch Grundkonzepte von Artificial Life und Rechnerarchitekturen kennen. Sie analysieren bestehende Programme in einer rudimentären Assemblersprache, entwickeln eigene Strategien und lassen diese im Speicher einer virtuellen Maschine gegeneinander antreten.
Schwierige Probleme in der Informatik
Dieses Unterrichtsmaterial führt Schülerinnen und Schüler anhand der Software GraphBench spielerisch und entdeckend an NP-vollständige Probleme, Komplexitätstheorie und algorithmische Lösungsansätze heran. Es umfasst Arbeits- und Begleitdokumente für 3 bis 4 Lektionen am Gymnasium.
QueueTraffic: Grundbegriffe der Warteschlangentheorie
Dieses Unterrichtsmaterial führt anhand einer alltäglichen Situation in die Grundbegriffe der Warteschlangentheorie ein. Es enthält einen Einführungsvortrag, Arbeitsblätter mit Beispielrechnungen sowie Aufgaben inklusive Lösungen.
Schnelle Multiplikation – Verfahren von Karatsuba
Das Unterrichtsmaterial führt in das Karatsuba-Verfahren zur schnellen Multiplikation grosser Zahlen ein. Die Schülerinnen und Schüler lernen die algorithmische Entwurfsstrategie von 'Divide and Conquer' kennen, wenden das Verfahren manuell an und vergleichen experimentell die Effizienz mit der herkömmlichen Schulmethode.
Applet: Kleinstquadrat-Methode
Dieses Unterrichtsmaterial behandelt die Methode der kleinsten Quadrate zur Lösung überbestimmter Gleichungssysteme und zur Fehlerreduktion bei Messwerten. Es enthält neben Theorie und Präsentationsfolien auch praktische Applets, Matlab-Prototypen sowie Übungen zur iterativen Lösungsfindung.
Top-Down-Entwurf für das Spiel NumTrip
In diesem Gruppenauftrag erstellen die Schülerinnen und Schüler auf Papier und anschliessend in einem Markdown-Dokument einen strukturierten Top-down-Entwurf für das Spiel NumTrip, wobei bestehende Funktionen integriert werden.
Softwareentwicklungstechniken: Teile und herrsche sowie Top-down und Bottom-up
Der Text erklärt grundlegende Techniken des Softwareengineerings wie das Prinzip 'Teile und herrsche' zur Reduktion von Komplexität. Zudem werden die Ansätze Top-down und Bottom-up bei der funktionalen Dekomposition von Programmen erläutert.
Unterrichtssequenz zu Induktion und Kombinatorik
Eine Unterrichtssequenz für das Gymnasium zur mathematischen Induktion als Erweiterung des Lehrmittels 'Algorithmen und Künstliche Intelligenz'. Das Material vertieft das Kapitel Kombinatorik und Induktion auf gymnasialem Niveau.
GraphBench
GraphBench ist eine interaktive Lernsoftware zur Veranschaulichung von NP-vollständigen Problemen, Reduktionen und Graphenalgorithmen. Die Java-Anwendung bietet neben grafischen Visualisierungen auch eine integrierte Programmierumgebung für eigene Algorithmen.
Vortrag: Backtracking mit Heuristiken
Dieses Material bietet einen einführenden Vortrag über das Konzept des Backtrackings und den Einsatz von Heuristiken. Es enthält Folien, Texte und Beispielaufgaben wie das n-Damen-Problem oder Labyrinth-Aufgaben zur Veranschaulichung.
Lernziele für eine Informatik-Prüfung zu Algorithmen und Datenstrukturen
Dieses Dokument listet detaillierte Lernziele für eine Informatik-Prüfung auf, die Themen wie Suchen, Sortieren, Laufzeitkomplexität (O-Notation), Rekursion, Graphenalgorithmen und das P-NP-Problem abdecken. Es handelt sich um eine reine Stoff- und Prüfungsübersicht ohne direkte Aufgaben oder Erklärungstexte.