EventoWeb
Zürcher Hochschule für Angewandte Wissenschaften
Menu
Home
User Menu
Nicht angemeldet
Anmelden
[
Deutsch (Schweiz)
Deutsch (Schweiz)
] [
Englisch
Englisch
]
[
de
de
] [
en
en
]
Nicht angemeldet
Anmelden
EventoWeb
Kontakt zu Service Desk
Online-Dokumentation
Allgemeiner Zugriff
Module suchen
t.BA.IT.THIN.19HS (Theoretische Informatik)
Modul: Theoretische Informatik
Diese Information wurde generiert am: 04.11.2024
Nr.
t.BA.IT.THIN.19HS
Bezeichnung
Theoretische Informatik
Veranstalter
T CAI
Credits
4
Beschreibung
Version: 3.0 gültig ab 01.02.2022
Kurzbeschrieb
Grundbegriffe sowie Konzepte der theoretischen Informatik, Modelle zur Beurteilung der Leistungsfähigkeit aktueller und zukünftiger Computersysteme:
Formale Sprachen, Automatentheorie, Berechenbarkeit und Komplexität
Modulverantwortung
Olaf Stern, strf
Lernziele (Kompetenzen)
Ziel
Kompetenzen
Taxonomiestufen
(1) Sie können die wichtigsten formalen Sprachen/Grammatiken und die entsprechenden Automatentypen erläutern und deren Zusammenhänge darlegen. Sie können Automaten für gegebene Sprachen entwerfen, die diese erkennen bzw. definieren (und umgekehrt).
F, M
K2, K3
(2) Sie können die wichtigen Ansätzen zur Formalisierung der Konzepte der Berechenbarkeit und des Algorithmus veranschaulichen und die Äquivalenz der verschiedenen Ansätze erkennen. Sie können die Konzepte der entscheidbaren und semi-entscheidbaren Probleme darlegen und erklären in welchem Verhältnis diese zueinander stehen.
F, M
K2
(3) Sie können die wichtigsten Komplexitätsklassen - insbesondere P und NP - und einfache Notationen dazu (O- und Omega-Notation) erklären. Sie verstehen die Frage ob P=NP ist und können ihre Bedeutung diskutieren. Sie können die Methode der polynomialen Reduktion an einfachen Beispielen anwenden.
F, M
K2, K3
Modulinhalte
Motivation der theoretischen Informatik:
Formale Berechnungsmodelle
Grundlegende Prinzipien erkennen, unabhängig von Hard- und Software
Grenzen der automatischen Berechnungen
(1) Formale Sprachen / Automatentheorie:
Grundlegende Definitionen der Formalen Sprachen
Reguläre Sprachen, endlicher Automat (DEA, NEA, e-NEA)
Kontextfreie Sprachen, Kellerautomaten
(Rekursive Sprachen), Turingmaschine (TM)
Chomsky-Hierarchie
(2) Berechenbarkeit und Algorithmus-Begriff:
Berechenbare Funktionen Church'sche These
Äquivalenz von TM und Computer
Berechenbarkeit und Programmier-Sprachen: GOTO-, While- und Loop-Programme.
Algorithmus-Begriff
Primitive Rekursion
Nicht-Entscheidbarkeit und Entscheidbarkeit: Diagonalisierungssprache Ld, Satz von Rice, Fleissige Bieber
Semi-entscheidbare Probleme: Halteproblem, Game-of-Life, (Collatz-Zahlen ?)
Reduktion
(3) Komplexitätstheorie
Komplexität von Algorithmen
O-Notation (Omega-Notation)
polynomiale Funktionen und exponentielle Funktionen
Klasse P, Klasse NP
NP-vollständig, NP-schwierig
Polynomialzeit-Reduktion
Lehrmittel/Materialien
- Ausführlicher Foliensatz, Ergänzungsunterlagen, Aufgabenserien mit Musterlösungen
- John E. Hopcroft, Rajeev Motwani, und Jeffrey D. Ullman:
Einführung in die Automatentheorie, Formale Sprachen und Berechenbarkeit
bzw.
Introduction to Automata Theory, Languages, and Computation
, Pearson Studium, Addison-Wesley Verlag, (auch als Taschenbuch und e-Book verfügbar), 2011 / 2013
Ergänzende Literatur
- Hans-Joachim Böckenhauer, Juraj Hromkovic: Formale Sprachen, Springer Verlag, 2013
- Juray Hromkovic: Theoretische Informatik, Teubner Verlag, 3. Auflage, 2007
- Uwe Schöning: Theoretische Informatik - kurz gefasst, Spektrum Akademischer Verlag, 5. Auflage, 2008
Zulassungs-voraussetzungen
keine
Unterrichtssprache
(X) Deutsch ( ) Englisch
Teil des Internationalen Profils
( ) Ja (X) Nein
Modulausprägung
Typ 2a
Details siehe unter:
T_CL_Modulauspraegungen_SM2025
Leistungsnachweise
Bezeichnung
Art
Form
Umfang
Bewertung
Gewichtung
Leistungsnachweise während Studiensemester
Aufgabenserien
schriftlich
ca. 9 Serien
Punkte => Note
20%
Semesterendprüfung
Klausur
schrifltich
90 Min.
Note
80%
Bemerkungen
Rechtsgrundlage
Die Modulbeschreibung ist neben Rahmenprüfungsordnung und Studienordnung Teil der Rechtsgrundlage. Sie ist verbindlich. Eine in der ersten Unterrichtswoche des Semesters schriftlich festgehaltene und kommunizierte Modulvereinbarung kann die Modulbeschreibung präzisieren. Die Modulvereinbarung ersetzt nicht die Modulbeschreibung.
Hinweis
Weitere verfügbare Versionen:
2.0 gültig ab 01.02.2019
Kurs: Theoretische Informatik - Vorlesung
Nr.
t.BA.IT.THIN.19HS.V
Bezeichnung
Theoretische Informatik - Vorlesung
Hinweis
Für das Stichdatum 01.08.2099 ist kein Modulbeschreibungstext im System verfügbar.