1.3 Theoretische Informatik – Unterrichtsmaterial
Konzept Laufzeitkomplexität
Der Text führt in das theoretische Konzept der Laufzeitkomplexität von Algorithmen ein. Er erklärt die asymptotische Laufzeit, die Skalierbarkeit bei wachsenden Datenmengen und das Worst-Case-Szenario anhand einer verständlichen Schachbrett-Analogie.
Theoretische Informatik: P, NP und Komplexität
Das Unterrichtsmaterial führt in die theoretische Informatik ein, behandelt polynomiale und exponentielle Laufzeiten sowie die Komplexitätsklassen P und NP. Anhand von Beispielen wie der Faktorisierung, dem Erfüllbarkeitsproblem (SAT) und dem Travelling Salesman Problem (TSP) wird das fundamentale P-NP-Problem veranschaulicht.
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.
Zeitmessung von Sortieralgorithmen in Python
Das Unterrichtsmaterial leitet dazu an, klassische Sortieralgorithmen wie Selection Sort, Insertion Sort und Merge Sort in Python zu implementieren und deren Laufzeiten mithilfe der timeit-Bibliothek zu messen und zu vergleichen.
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.
Rechnerarchitektur und Von-Neumann-Rechner
Dieses Unterrichtsmaterial behandelt fundierte Konzepte der Technischen Informatik wie Turingmaschinen, den Aufbau und die Funktionsweise des Von-Neumann-Rechners, logische Schaltungen sowie Assembler-Programmierung mit LMC. Es richtet sich an fortgeschrittene Lerngruppen im Schwerpunktfach oder im Grundlagenfach.
Zustandsmaschinen und endliche Automaten
Dieses Unterrichtsmaterial erklärt das Konzept von Zustandsmaschinen und endlichen Automaten am Beispiel einer Liftsteuerung. Es behandelt Zustände, Ereignisse, State-Event-Tabellen, Zustandsdiagramme sowie die konkrete Implementierung in Python.
Effiziente Sortieralgorithmen: MergeSort und HeapSort
Diese Unterrichtseinheit behandelt effiziente Sortieralgorithmen mit einer Laufzeitkomplexität von O(n log n). Die Schülerinnen und Schüler lernen die Algorithmen MergeSort und HeapSort kennen und wenden Strategien wie Teile-und-Beherrsche sowie Datenstrukturen wie Heaps an.
Esoterisch Programmieren - Brainfuck
Dieses Unterrichtsmaterial führt in die esoterische Programmiersprache Brainfuck ein und behandelt dabei grundlegende Konzepte der theoretischen Informatik und Turing-Vollständigkeit. Die Lernenden analysieren und verwenden Programme, die mit nur acht Befehlen auskommen.
Kara – Programmieren mit endlichen Automaten
Das Lehrmittel führt Schülerinnen und Schüler ohne Vorkenntnisse spielerisch in die Grundlagen des Programmierens und endliche Automaten ein. Mithilfe des programmierbaren Marienkäfers 'Kara' in einer grafischen Umgebung werden elementare algorithmische Abläufe und logische Bedingungen vermittelt.
TuringKara – zweidimensionale Turing-Maschinen
Das Material stellt die Lernumgebung TuringKara zur Verfügung, mit der das Berechnungsmodell der Turing-Maschine anhand eines zweidimensionalen Ansatzes spielerisch und praktisch ausprobiert werden kann. Es bietet eine breite Palette an Aufgaben wie Invertieren von Bitstrings, Addition von Binärzahlen oder die Universelle Turing-Maschine.
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.
Exorciser: Plattform für Aufgaben zur Theoretischen Informatik
Die Seite beschreibt eine Aufgabensammlung namens Exorciser, die gezielt Übungen zu regulären Sprachen, kontextfreien Grammatiken und Markov-Algorithmen bereitstellt. Sie dient Lehrpersonen und Lernenden zur Vertiefung von Konzepten der theoretischen Informatik wie endlichen Automaten und Grammatiken.
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.
Computation: Berechenbarkeit und reguläre Sprachen
Dieses Unterrichtsmaterial behandelt theoretische Grundlagen der Informatik wie Berechenbarkeit, Berechnungsmodelle und endliche Automaten. Es enthält spielerische Einstiege durch Puzzles sowie praktische Aufgaben zur Mustererkennung mit der Programmierumgebung Kara.
Sortieren interaktiv und Laufzeitkomplexität
Dieses Unterrichtsmaterial bietet einen Einblick in fortgeschrittene Sortieralgorithmen und deren Effizienz. Es behandelt konzeptionell die Laufzeitkomplexität und das Wachstumsverhalten von Algorithmen anhand von Beispielen und Analogien.
Tutorial Turingmaschine
Dieses Unterrichtsmaterial leitet die Lernenden dazu an, sich das Konzept der Turingmaschine mithilfe eines externen Tutorials selbstständig zu erarbeiten. Dabei werden auch Übungsaufgaben bearbeitet und Fragen für den anschliessenden Unterrichtsdiskurs festgehalten.
Algorithmisch lösbare und algorithmisch unlösbare Probleme: Aufgaben zur Reduktion
Dieses Unterrichtsmaterial stellt zwei Aufgaben zum Thema Reduktion vor. Es ermöglicht Schülerinnen und Schülern an Gymnasien, sich mit der Lösbarkeit von Problemen auseinanderzusetzen, ohne dafür formale Grundlagen der Berechenbarkeitstheorie vorauszusetzen.
Kara – Programmieren mit endlichen Automaten
Das Material stellt fortgeschrittene Anwendungen des Programmierlernsystems Kara vor, darunter den Labyrinth-Besuch mittels Backtracking, die Simulation von Langtons Ameise und den fleissigen Biber zur Veranschaulichung von Turing-Maschinen.
TuringKara: zweidimensionale Turing-Maschinen
Das Material stellt die Programmierumgebung TuringKara vor, die zweidimensionale Turing-Maschinen spielerisch und visuell erfahrbar macht. Es enthält Hinweise auf Programmieraufgaben, Musterlösungen sowie eine Bedienungsanleitung.
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.