Computation: Berechenbarkeit, reguläre Sprachen
Verfasst von Raimond Reichert
Inhalt
Auch wenn sie unglaublich vielseitig eingesetzt werden können: Computer können nicht alles. Sie scheitern zum Beispiel am Domino-/Fliesen-Problem. Im Falle von Kara schaffen es endliche Automaten nicht zu berechnen, wie viele Kleeblätter Kara mit einem Automaten mit n Zuständen legen kann..
Ziele
Verstehen, was es heisst, etwas berechnen zu können oder es nicht zu können. Was sind Berechnungsmodelle? Was bedeutet Berechenbarkeit? Was können endliche Automaten? Wie erkennen endliche Automaten Muster?
Ablauf
| ⅓ Lektion | Übung |
Affenpuzzle mit 2x2 (einfach) und mit 4x4 Teilen ("fast fertig!"). Ziel ist es, spielerisch ein Gefühl für die kombinatorische Explosion eines nicht-berechenbaren Problems zu erhalten Kombinatorische Explosion: Anzahl möglicher Lösungen des Puzzles und Anzahl möglicher Lösungen des Puzzles mit 4x4 Teilen. |
| ⅓ Lektion | Vortrag | Einführung ins Thema Berechenbarkeit, Berechnungsmodelle (Vortrag bis Folie 14) |
| 1 Lektion | Übung | Aufgaben zur Mustererkennung mit Kara für einen sanften Übergang zu formalen endlichen Automaten und regulären Ausdrücken |
| ⅓ Lektion | Vortrag | Abschluss Thema Berechenbarkeit, Berechnungsmodelle (Vortrag ab Folie 15), Grenzen von Kara aufzeigen |
Literatur
R. Reichert, J. Nievergelt, W. Hartmann (2004): Programmieren mit Kara. Ein spielerischer Zugang zur Informatik. 2. erweiterte Auflage. Kapitel 5–6.
Downloads
![Vorlage Affenpuzzle (Jens Gallenbacher; Orginal für aktuelle Acrobat-Versionen auf <a href='http://www.abenteuer-informatik.de'>www.abenteuer-informatik.de/</a>). - PDF [7 MB]](/views/icons/pdf.gif "Vorlage Affenpuzzle (Jens Gallenbacher; Orginal für aktuelle Acrobat-Versionen auf <a href='http://www.abenteuer-informatik.de'>www.abenteuer-informatik.de/</a>). - PDF [7 MB]"){kind=icon} | Vorlage Affenpuzzle (Jens Gallenbacher; Orginal für aktuelle Acrobat-Versionen auf www.abenteuer-informatik.de/). | PDF [7 MB] |
![Vortrag Berechnungsmodelle</strong> - Powerpoint [3 MB]](/views/icons/ppt.gif "Vortrag Berechnungsmodelle</strong> - Powerpoint [3 MB]"){kind=icon} | Vortrag Berechnungsmodelle | Powerpoint [3 MB] · PDF [501 KB] |
![Kara-Aufgaben zur Mustererkennung - Word [298 KB]](/views/icons/doc.gif "Kara-Aufgaben zur Mustererkennung - Word [298 KB]"){kind=icon} | Kara-Aufgaben zur Mustererkennung | Word [298 KB] · PDF [74 KB] |
![Kara herunterladen und starten - JAR [4 MB]](/views/icons/jar.gif "Kara herunterladen und starten - JAR [4 MB]"){kind=icon} | Kara herunterladen und starten | JAR [4 MB] |
Links
| Berechnungsmodelle | |
| Definition Berechnungsmodell (Model of Computation; Wikipedia) | |
| Zweidimensionale Modelle der Berechenbarkeit (Katrin Moßbrucker) [PDF] | |
| Turing Maschinen | |
| TuringKara: Zweidimensionale Turing-Maschinen | |
| Turing-Maschinen (Wikipedia) | |
| Alan Turing, der Erfinder der Turing Maschinen (Wikipedia) | |
| Grosse Zahlen für grosse Laufzeiten | |
| Definition Googol | |
| Weiterführende Lektüre | |
| David Harel (2001): Das Affenpuzzle: Und weitere bad news aus der Computerwelt. | |