Modultitel
- Theoretische Informatik für BIG
Modultitel (Englisch)
Lehrveranstaltungen des Moduls
- Theoretische Informatik (WS: 4V + 2Ü)
Modulverantwortliche(r)
Lehrinhalte
Zentrale Gegenstände des Moduls sind Formalisierung von Algorithmen und deren sprachliche Realisierungen als Programme sowie Problemlösungen durch Berechnungsverfahren. Neben formalen Sprachen und ihrer Typisierung nach Leistungsfähigkeit werden Grammatiken und Automaten behandelt. Es folgen Einführungen in die Berechenbarkeitstheorie, die sich mit grundsätzlichen Möglichkeiten und Grenzen der Algorithmisierbarkeit befasst, und in die Komplexitätstheorie, die untersucht, mit welchem Aufwand an Berechnungsressourcen (Rechenzeit, Speicherplatz) algorithmische Aufgaben gelöst werden können. Abschließend werden Grundzüge der Logik im Hinblick auf ihre Rolle in informatischen Aufgabenstellungen vermittelt.
Kompetenzen
Grundsätzliches Verständnis von theoretischen Prinzipien der Informatik und Aneignung formaler Methoden.
Literatur:
- Hopcroft, J.E., Motwani, R., Ullman, J.D.: Einführung in die Automatentheorie, Formale Sprachen und Komplexitätstheorie. Addison-Wesley, 2002 (zur Vertiefung)
- Lewis, H.R., Papadimitriou, C.H.: Elements of the theory of computation. Prentice Hall, 1981 (z. Vertief.)
- Schöning, U.: Theoretische Informatik kurz gefasst. Spektrum Akademischer Verlag, 1995.
- Schöning, U.: Logik für Informatiker. Spektrum Akademischer Verlag, 1995.
Anzahl Einzelleistungen (benotet und unbenotet)
eine unbenotete Einzelleistung
Prüfungsformen
erfolgreiche Bearbeitung der Übungsaufgaben
Voraussetzungen für die Vergabe von Leistungspunkten
regelmäßige Teilnahme an Vorlesung und Übung, erfolgreiche Übungsteilnahme (mind. 60% der erreichbaren Punkte der Übungsaufgaben)
Arbeitsaufwand und Leistungspunkte
Für das Modul gibt es 5 Leistungspunkte. Der Arbeitsaufwand setzt sich zusammen aus
| Teilnahme an der Vorlesung Teilnahme an den Übungen Bearbeiten der Übungszettel: gesamt: 150h = 5 LP |
4 SWS x 16 Wochen 2 SWS x 16 Wochen |
= 60h = 30h = 60h |
Teilnahmevoraussetzungen und Vorkenntnisse
keine
Weitere Bezüge: Auf diesem Modul können Vorlesungen zur Logik und Rekursionstheorie, Logik-Programmierung, zum Übersetzerbau und zur Künstlichen Intelligenz aufbauen.
Modultyp und Verwendbarkeit
Pflichtmodul für den Bachelorstudiengang
- Bioinformatik und Genomforschung
Dauer des Moduls / Angebotsturnus
Wintersemester
jährlich