Informatikmaterialien
von Tino Hempel

	Richard-Wossidlo-Gymnasium Ribnitz-Damgarten Fachbereich Informatik

Semesterplan Leistungskurs 13
Theoretische Informatik

Klasse: Leistungskurs 13	Unterricht: montags, 1./2. Stunde dienstags, 5./6. Stunde donnerstags, 8./9. Stunde (in den ungeraden Wochen)

August 31.07. – 06.08. 07.08. – 14.08. 14.08. – 20.08. 21.08. – 27.08. 28.08. – 03.09.	September 04.09. – 10.09. 11.09. – 17.09. 18.09. – 24.09. 25.09. – 01.10.	Oktober 02.10. – 08.10. 09.10. – 15.10. 16.10. – 22.10. 23.10. – 29.10.	November 30.10. – 05.11. 06.11. – 12.11. 13.11. – 22.11. 20.11. – 26.11. 27.11. – 03.12.	Dezember 04.12. – 10.12. 11.12. – 17.12. 18.12. – 24.12. 25.12. – 31.12.	Januar 01.01. – 07.01. 08.01. – 14.01. 15.01. – 21.01. 22.01. – 28.01.
Februar 29.01. – 04.02. 05.02. – 11.02. 12.02. – 18.02. 19.02. – 25.02. 26.02. – 04.03.	März 05.03. – 11.03. 12.03. – 18.03. 19.03. – 25.03. 26.03. – 01.04.	April 02.04. – 08.04. 09.04. – 15.04. 16.04. – 22.04. 23.04. – 29.04.	Mai 30.04. – 06.05. 07.05. – 13.05. 14.05. – 20.05. 21.05. – 27.05. 28.05. – 03.06.	Juni 04.06. – 10.06. 11.06. – 17.06. 18.06. – 24.06. 25.06. – 01.07.	Juli 02.07. – 08.07. 09.07. – 15.07. 16.07. – 22.07. 23.07. – 29.07.

Es entfallen nebenstehende Einzeltage. Komplette Wochen wurden nicht berücksichtigt.	Mo	Di	Mi	Do	Fr
	30.10. 09.04. 28.05.	03.10. 31.10. 10.04. 01.05. 29.05.	11.04.	17.05.	24.11. 18.05. 25.05.

Januar
Mo 01	Di 02	Mi 03	Do 04	Fr 05

Weihnachtsferien

Januar
Mo 08	Di 09	Mi 10	Do 11	Fr 12

Endliche Automaten und Formale Sprachen

Mo	Thema: Reale Automaten Reale Automaten Benutzen eines Fahrkartenautomaten ( Simulation) Analyse: Begriffe, Bestandteile, Automatengraphen als Darstellungsmöglichkeit weitere Beispiele HA:

Thema: DEA

Wiederholung
Aufbau eines realen Automaten
Deterministischer Endlicher Automat (DEA)
Definition
Beispiele
Simulation in PROLOG und im Simulationsprogramm Automat von G. Röhner

HA: LB S. 140/9 implementieren?

Januar
Mo 15	Di 16	Mi 17	Do 18	Fr 19

Endliche Automaten und Formale Sprachen

Mo	Thema: Akzeptor Akzeptor Definition Beispiele Sprache des Akzeptors Simulation in PROLOG, im Simulationsprogramm Automat von G. Röhner und in AutoEdit HA:


Di	Thema: Akzeptor Übungen zum Akzeptor Definition Beispiele Simulation in PROLOG, im Automatensimulator von C. Burch, in JFLAP und im Simulationsprogramm Automat von G. Röhner HA:

Do	Ausfall wg. Orkan HA:

Januar
Mo 22	Di 23	Mi 24	Do 25	Fr 26

Endliche Automaten und Formale Sprachen

Mo	Thema: Akzeptor Akzeptor Beispiele Simulation in PROLOG, im Automatensimulator von C. Burch, in JFLAP und im Simulationsprogramm Automat von G. Röhner HA:

Thema: Grammatiken

Akzeptor und formale Sprachen
Beispiele
Simulation in PROLOG, im Automatensimulator von C. Burch, in JFLAP und im Simulationsprogramm Automat von G. Röhner
Grammatiken
Definition, Arten
Erzeugen von Sprachen durch Grammatiken – Akzeptor prüft Sprachen

HA:

Januar - Februar
Mo 29	Di 30	Mi 31	Do 01	Fr 02

Grammatik und Sprache

Mo	Thema: Grammatiken und Chomsky-Hierarchie Grammatiken Übungen Erzeugen von Sprachen durch Grammatiken – Akzeptor prüft Sprachen Chomsky-Hierarchie Erläuterungen Grenzen von Akzeptoren HA:


Di	Thema: Chomsky-Hierarchie und Übungen – Grenzen von Akzeptoren Chomsky-Hierarchie Erläuterungen Typ 2 Grammatiken und Grenzen von Akzeptoren Grenzen aufzeigen Problem der Speicherung Kellerautomat Simulationen HA:

Do	Thema: Abiturvorbereitung Aufbau des Abiturs Lösen von Aufgaben unter abiturähnlichen Bedingungen HA:

Februar
Mo 05	Di 06	Mi 07	Do 08	Fr 09

Winterferien

Februar
Mo 12	Di 13	Mi 14	Do 15	Fr 16

Winterferien

Februar
Mo 19	Di 20	Mi 21	Do 22	Fr 23

Kellerautomat

Mo	Thema: Kellerautomat Wiederholung Grenzen des Akzeptors Definiton und Aufbau des Kellerautomaten (deterministisch/nichtdeterministisch) Sprache des Kellerautomaten - Chomsky-Hierarchie Beispiele und Übungen HA:

Thema: Kellerautomat

Test
Beispiele und Übungen
(Lösungen finden sich im Moodle-System)

HA: LB. S. 111/4

Februar - März
Mo 26	Di 27	Mi 28	Do 01	Fr 02

Turingmaschine

Mo	Thema: Grenzen des Kellerautomaten Typ 0/1 Grammatiken und Turingmaschinen Wiederholung Kellerautomat (deterministisch/nichtdeterministisch) Grenzen aufzeigen TM Simulationen mit diversen Programmen Übungen HA:


Di	Thema: Turingmaschinen Übungen HA:

Do	Thema: Abiturvorbereitung Aufbau des Abiturs Lösen von Aufgaben unter abiturähnlichen Bedingungen HA:

März
Mo 05	Di 06	Mi 07	Do 08	Fr 09

Unlösbare Probleme – Erste Leistungsgrenze von Computern

Mo	Thema: Halteproblem Wiederholung: intuitiver Algorithmusbegriff Halteproblem 3A+1-Algorithmus, Halteproblem, seltsame Algorithmen, Leistungsgrenze Präzisierung des Algorithmusbegriffs - Churchsche Hypothese Begriff der TM-Berechenbarkeit, Übungen HA:

Thema: Selbststudium - TM-Berechenbarkeit

Präzisierung des Algorithmusbegriffs - Churchsche Hypothese
Begriff der TM-Berechenbarkeit, Übungen zur TM
Übungen zur TM
LB S. 197/2, 4
LB S. 198/9, 10
LB S. 192/Kapitel 12.5, 12.6 und 12.7 durcharbeiten

HA:

März
Mo 12	Di 13	Mi 14	Do 15	Fr 16

Effiziente Algorithmen – Zweite Leistungsgrenze von Computern

Mo	Thema: Sortieralgorithmen: Ripplesort Grundproblem Sortieren Sortieralgorithmus Ripplesort Struktogramm, OOA, OOD, Implementation der Methode im sonst fertigen Programm HA:


Di	Thema: Laufzeitanalyse – Zeitkomplexität Test Laufzeituntersuchungen HA:

Do	Thema: Abiturvorbereitung Aufbau des Abiturs Lösen von Aufgaben unter abiturähnlichen Bedingungen HA:

März
Mo 19	Di 20	Mi 21	Do 22	Fr 23

Effiziente Algorithmen – Zweite Leistungsgrenze von Computern

Mo	Thema: Laufzeitanalyse – Zeitkomplexität Auswertung der Laufzeituntersuchungen Begriff der Zeitkomplexität und O-Notation HA:

Thema: Bubblesort und Bubblesort II, MergeSort

Sortierverfahren Bubblesort
Implementation, Untersuchungen, Komplexität
Sortierverfahren MergeSort

HA:

Klausur unter abiturähnlichen Bedingungen

März
Mo 26	Di 27	Mi 28	Do 29	Fr 30

Effiziente Algorithmen – Zweite Leistungsgrenze von Computern

Mo	Ausfall wg. Vorabitur Mathematik


Di	Thema: Mergesort, Tanzpaarungsproblem Sortierverfahren MergeSort Auswertung der Laufzeituntersuchungen Zusammenfassung Algorithmen mit polynomialer und exponetieller Laufzeit Grundproblem Zuordnungen Heiratsproblem Tanzpaarungsproblem Berechnung aller Permutationen einer n-elementigen Menge (BlueJ) HA:

Do	Thema: Abiturvorbereitung Aufbau des Abiturs Lösen von Aufgaben unter abiturähnlichen Bedingungen HA:

April
Mo 02	Di 03	Mi 04	Do 05	Fr 06

Ostern

April
Mo 09	Di 10	Mi 11	Do 12	Fr 13

Abiturvorbereitung

Ostern


Di	Ostern

Do	Thema: Abiturvorbereitung Auswertung der Klausur unter abiturähnlichen Bedingungen HA:

April
Mo 16	Di 17	Mi 18	Do 19	Fr 20

Effiziente Algorithmen – Zweite Leistungsgrenze von Computern

Thema: Tanzpaarungsproblem

Wiederholung/Kontrolle Sortierverfahren
Algorithmen mit polynomialer und exponetieller Laufzeit
Fortsetzung Tanzpaarungsproblem
Berechnung aller Permutationen einer n-elementigen Menge (BlueJ)
Feststellung: zu einem Problem kann es Algorithmen geben mit polynomialer und exponetieller Laufzeit

HA:

Thema: TSP und Rucksackproblem, Klasse NP

HA:

April
Mo 23	Di 24	Mi 25	Do 26	Fr 27

Effiziente Algorithmen – Zweite Leistungsgrenze von Computern

Mo	Thema: Zusammenfassung Zusammenfassung Abiturtraining HA:


Di	Thema: Abiturvorbereitung Auswertung der Klausur unter abiturähnlichen Bedingungen HA:

Do	Thema: Abiturvorbereitung Auswertung der Klausur unter abiturähnlichen Bedingungen HA:

April - Mai
Mo 30	Di 01	Mi 02	Do 03	Fr 04

Abiturvorbereitung

Mo	Thema: Abiturvorbereitung Auswertung der Klausur unter abiturähnlichen Bedingungen HA:


Di	Maifeiertag

Mai
Mo 07	Di 08	Mi 09	Do 10	Fr 11

Abiturphase

zur Startseite

Im Web vertreten seit 1994.
Eine Internet-Seite aus dem Angebot von Tino Hempel.
Impressum

Semesterplan Leistungskurs 13Theoretische Informatik

Semesterplan Leistungskurs 13
Theoretische Informatik