|
| Code: | 189000 |
| Modul: | Theoretische Informatik |
| Module title: | Theoretical Computer Science |
| Version: | 2.01 (12/2013) |
| letzte Änderung: |
02.12.2021 |
| Modulverantwortliche/r: |
Prof. Dr. rer. nat. Wagenknecht, Christian
c.wagenknecht@hszg.de |
|
angeboten in den 4 Studiengängen:
| Informatik (B.Sc.) gültig ab Matrikel 2015 |
Informatik (B.Sc.) gültig ab Matrikel 2018 |
Informatik (B.Sc.) gültig ab Matrikel 2020 |
Informatik (B.Sc.) gültig ab Matrikel 2024 |
|
| Modul läuft im: | SoSe (Sommersemester)
|
| Niveaustufe: | Bachelor/Diplom |
| Dauer des Moduls: | 1 Semester |
| Status: | Pflichtmodul |
| Lehrort: | Görlitz |
| Lehrsprache: | Deutsch |
| Workload* in |
SWS ** |
Semester |
| Zeit- std. | ECTS-
Pkte |
1 |
2 |
3 |
4 |
5 |
6 |
|
V |
S |
P |
W |
V |
S |
P |
W |
V |
S |
P |
W |
V |
S |
P |
W |
V |
S |
P |
W |
V |
S |
P |
W |
| 300 | 10 | 8.0 |
|
4 |
4 |
0 |
0 |
|
|
|
|
| * | Gesamtarbeitsaufwand pro Modul
(1 ECTS-Punkt entspricht einem studentischen Arbeitsaufwand von 30 Zeitstunden) |
| ** | eine Semesterwochenstunde (SWS) entspricht 45 Minuten pro Woche |
| Selbststudienzeit in h |
Angabe gesamt |
davon |
| 210 |
180
Vor- und Nachbereitung LV |
30
Vorbereitung Prüfung |
0
Sonstiges |
|
Lehr- und Lernformen: |
- Vorlesung, Übung und Computerarbeit mit der Lern- und Arbeitsumgebung FLACI (ggf. AtoCC);
- Web-unterstütztes, teilweise projektorientiertes Lernen, Konkretisierung und Versprachlichung abstrakter Inhalte als didaktisches Konzept zur Steigerung der Aktivität des Lerners bei der Aneignung und Anwendung.
- Konstruktivistischer, entwickelnder und handlungsorientierter Ansatz
- Verbindung von Theorie (formale Sprachen, abstrakte Automaten) und Praxis (Compilerbau, moderne Mensch-Maschine-Schnittstellen, Eingabeverifikation)
|
| Hinweise: |
- FLACI (und der Vorgänger AtoCC) sind Ergebnis fach- und mediendidaktischer Forschung des Modulverantwortlichen (im Team). Den Studierenden steht eine Lern- und Arbeitsumgebung orts- und zeitunabhängig zur Verfügung, die keine Wartungsanforderungen stellt. Sie bietet Experimentiermöglichkeiten bei der Lösung von Aufgabenstellungen mit Praxisrelevanz, Dokumentationsformen zur Präsentation individueller Lösungen zur kritischen Diskussion und Ansätze kollaborativen Lernens
Das Testat wird bei gegebenem Lernfortschritt begleitend zu den Computerübungen erteilt. Die erforderlichen Kenntnisse werden entsprechenden Aufgabenlösungen nachgewiesen.
|
| Prüfung(en) |
| Prüfungsvorleistung | Prüfungsvorleistung als Teilnahme/Testat (VT) |
|
| Prüfung | mündliche Prüfungsleistung (PM) |
20 min |
100.0% |
|
| Lerninhalt: |
- Grundbegriffe, wie Zeichen, Alphabet, Wort, Wortmenge, Sprache, Formale Grammatik, Formale Sprache, Syntax, Semantik, Ableitung,
- Chomsky-Hierarchie und zugehörige Automatenklassen, Leistungsfähigkeit der Akzeptormodelle: Endliche Automaten, reguläre Ausdrücke, Minimalautomat, Kellerautomaten, Turingmaschine, Determinismus und Nichtdeterminismus, Entscheidbarkeit des Wortproblems,
- Abstrakte Automaten mit Ausgabe: Moore- und Mealy-Maschinen,
- Pumping-Lemma für kontextfreie und reguläre Sprachen,
- LL(1)- und LR(1)-Sprachen, Syntaxanalyse kontextfreier Sprachen, Methode des rekursiven Abstiegs, Tabellensteuerung, bootstrapping, automatisierte Parsergenerierung für LALR(1)-Sprachen, Scanner- und Parsergenerierung mit VCC (AtoCC, FLACI),
- Zwei kleine Compiler-Projekte: Zeichenroboter, Notensprache.
|
| Lernergebnisse/Kompetenzen: |
| Fachkompetenzen: | Nach erfolgreicher Teilnahme an diesem Modul sind die Studierenden in der Lage
- formale Methoden anzuwenden,
- Definitionen für formale Sprachen mit formalen Grammatiken und abstrakten Automaten zu entwickeln,
- Syntaxanalysen für vorgegebene Wörter durchzuführen,
- Klassifizierungen für Sprachen zu verstehen,
- die jeweilige Leistungsfähigkeit eines Analysemodells zu bewerten,
- Transformationen zu verstehen, anzuwenden und zugehörige Prozesse zu bewerten,
- den Prozess automatisierter Compilerentwicklung zu analysieren und Compiler für Fachsprachen werkzeugunterstützt zu entwickeln.
|
| Fachübergreifende Kompetenzen: | Die Studierenden sind nach erfolgreichem Studium dieses Moluls in der Lage, abstrakte Mentaltechniken (begriffliches Arbeiten, Konkretisieren, Generalisieren, Deskriptionen), wie sie in vielen Bereichen der Informatik und darüber hinaus zunehmend benötigt werden, auf Standardinhalte der theoretischen Informatik anzuwenden. Die Studierenden entwickeln individuelle Konzepte für Transformationsprozesse und tragen damit zur Entwicklung ihrer Modellbildungskompetenz bei. |
|
| Notwendige Voraussetzungen für die Teilnahme: |
- Gute mathematische (Abitur)Kenntnisse, insbesondere aus der Mengenlehre und Analysis;
- Grundlegende Programmierkompetenz;
- Grundkompetenz in der Anwendung von formaler Methoden und Denktechniken
|
| Empfohlene Voraussetzungen für die Teilnahme: | Modul "Programmierparadigmen und Grundkonzepte der Informatik" |
|
| Literatur: |
- Online-Lehrmaterialien (inkl. Vorlesungsskript, interaktive Komponenten, Übungsaufgaben, interaktive Simulationen u. Literatur): https://web1.hszg.de/cwagenknecht-lehre/TI/TI-FSuA/
- Wagenknecht, Chr.; Hielscher, Michael: Formale Sprachen, abstrakte Automaten und Compiler.- Lehr- und Arbeitsbuch für Grundstudium und Fortbildung; Wiesbaden: Springer, 2. Aufl., 2014, 245 S.
- Lernumgebungen: AtoCC (http://www.atocc.de) und FLACI (https://flaci.com/home/)
|
