htw saar Piktogramm QR-encoded URL
Zurück zur Hauptseite Version des Moduls auswählen:
Lernziele hervorheben XML-Code


Theoretische Informatik

Modulbezeichnung:
Bezeichnung des Moduls innerhalb des Studiengangs. Sie soll eine präzise und verständliche Überschrift des Modulinhalts darstellen.
Theoretische Informatik
Modulbezeichnung (engl.): Theoretical Informatics
Studiengang:
Studiengang mit Beginn der Gültigkeit der betreffenden ASPO-Anlage/Studienordnung des Studiengangs, in dem dieses Modul zum Studienprogramm gehört (=Start der ersten Erstsemester-Kohorte, die nach dieser Ordnung studiert).
Kommunikationsinformatik, Bachelor, ASPO 01.10.2022
Code: KIB-TI
SAP-Submodul-Nr.:
Die Prüfungsverwaltung mittels SAP-SLCM vergibt für jede Prüfungsart in einem Modul eine SAP-Submodul-Nr (= P-Nummer). Gleiche Module in unterschiedlichen Studiengängen haben bei gleicher Prüfungsart die gleiche SAP-Submodul-Nr..
P222-0044
SWS/Lehrform:
Die Anzahl der Semesterwochenstunden (SWS) wird als Zusammensetzung von Vorlesungsstunden (V), Übungsstunden (U), Praktikumsstunden (P) oder Projektarbeitsstunden (PA) angegeben. Beispielsweise besteht eine Veranstaltung der Form 2V+2U aus 2 Vorlesungsstunden und 2 Übungsstunden pro Woche.
4V (4 Semesterwochenstunden)
ECTS-Punkte:
Die Anzahl der Punkte nach ECTS (Leistungspunkte, Kreditpunkte), die dem Studierenden bei erfolgreicher Ableistung des Moduls gutgeschrieben werden. Die ECTS-Punkte entscheiden über die Gewichtung des Fachs bei der Berechnung der Durchschnittsnote im Abschlusszeugnis. Jedem ECTS-Punkt entsprechen 30 studentische Arbeitsstunden (Anwesenheit, Vor- und Nachbereitung, Prüfungsvorbereitung, ggfs. Zeit zur Bearbeitung eines Projekts), verteilt über die gesamte Zeit des Semesters (26 Wochen).
5
Studiensemester: 4
Pflichtfach: ja
Arbeitssprache:
Deutsch
Prüfungsart:
Klausur, Dauer 90 min.

[letzte Änderung 03.07.2024]
Verwendbarkeit / Zuordnung zum Curriculum:
Alle Studienprogramme, die das Modul enthalten mit Jahresangabe der entsprechenden Studienordnung / ASPO-Anlage.

KIB-TI (P222-0044) Kommunikationsinformatik, Bachelor, ASPO 01.10.2021 , 3. Semester, Pflichtfach
KIB-TI (P222-0044) Kommunikationsinformatik, Bachelor, ASPO 01.10.2022 , 4. Semester, Pflichtfach
PIB-TI (P221-0041) Praktische Informatik, Bachelor, ASPO 01.10.2022 , 3. Semester, Pflichtfach
Arbeitsaufwand:
Der Arbeitsaufwand des Studierenden, der für das erfolgreiche Absolvieren eines Moduls notwendig ist, ergibt sich aus den ECTS-Punkten. Jeder ECTS-Punkt steht in der Regel für 30 Arbeitsstunden. Die Arbeitsstunden umfassen Präsenzzeit (in den Vorlesungswochen), Vor- und Nachbereitung der Vorlesung, ggfs. Abfassung einer Projektarbeit und die Vorbereitung auf die Prüfung.

Die ECTS beziehen sich auf die gesamte formale Semesterdauer (01.04.-30.09. im Sommersemester, 01.10.-31.03. im Wintersemester).
Die Präsenzzeit dieses Moduls umfasst bei 15 Semesterwochen 60 Veranstaltungsstunden (= 45 Zeitstunden). Der Gesamtumfang des Moduls beträgt bei 5 Creditpoints 150 Stunden (30 Std/ECTS). Daher stehen für die Vor- und Nachbereitung der Veranstaltung zusammen mit der Prüfungsvorbereitung 105 Stunden zur Verfügung.
Empfohlene Voraussetzungen (Module):
Keine.
Als Vorkenntnis empfohlen für Module:
Modulverantwortung:
Prof. Dr. Maximilian Altmeyer
Dozent/innen: Prof. Dr. Maximilian Altmeyer

[letzte Änderung 01.10.2022]
Lernziele:
Nach Abschluss der Veranstaltung können Studierende die grundlegenden Begriffe und Konzepte der theoretischen Informatik beschreiben. Sie können Eigenschaften von Automaten und Sprachen diskutieren, mit geeigneten Methoden beweisen (z.B. Pumping-Lemma) und bei praktischen Aufgabenstellungen die geeigneten theoretischen Konzepte (z.B. endlicher Automat, Kellerautomat, Turingmaschine) auswählen und anwenden.


[letzte Änderung 01.07.2024]
Inhalt:
Mathematische Grundlagen
Reguläre Sprachen
Endliche Automaten
Nichtdeterminismus
Reguläre Ausdrücke und Sprachen
Minimalautomat
Pumping-Lemma für reguläre Sprachen
Kontextfreie Sprachen
Kontextfreie Grammatiken
Normalformen
Pumping-Lemma für kontextfreie Sprachen
CYK Algorithmus
Kellerautomaten
Turingmaschinen und Varianten
Entscheidbarkeit
Halteproblem

[letzte Änderung 22.01.2024]
Weitere Lehrmethoden und Medien:
Tafel, Skript, Simulationssoftware

[letzte Änderung 24.10.2016]
Literatur:
HOPCROFT J.E., ULLMANN J.D., MOTWANI R., Einführung in die Automatentheorie, Formale Sprachen und Komplexitätstheorie, Pearson, 2002
SIPSER Michael: Introduction to the theory of computation, Course Technology, 3rd edition, 2012

[letzte Änderung 24.10.2016]
Modul angeboten in Semester:
WS 2024/25, WS 2023/24
[Fri Dec 27 01:46:11 CET 2024, CKEY=kti, BKEY=ki3, CID=KIB-TI, LANGUAGE=de, DATE=27.12.2024]