252-0057-00L Theoretische Informatik
Semester | Herbstsemester 2017 |
Dozierende | J. Hromkovic |
Periodizität | jährlich wiederkehrende Veranstaltung |
Lehrsprache | Deutsch |
Kommentar | Hinweis: Studierende, die das Fach 252-0065-00L Theoretische Informatik (8 KP) bereits abgeschlossen haben, können die LE 252-0057-00L Theoretische Informatik (7 KP) nicht anrechnen lassen. |
Lehrveranstaltungen
Nummer | Titel | Umfang | Dozierende | |||||||||||||||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
252-0057-00 V | Theoretische Informatik | 4 Std. |
| J. Hromkovic | ||||||||||||||||||||||||
252-0057-00 U | Theoretische Informatik | 2 Std. | J. Hromkovic |
Katalogdaten
Kurzbeschreibung | Konzepte zur Beantwortung grundlegender Fragen wie: a) Was ist völlig automatisiert machbar (algorithmisch lösbar) b) Wie kann man die Schwierigkeit von Aufgaben (Problemen) messen? c) Was ist Zufall und wie kann er nützlich sein? d) Was ist Nichtdeterminisus und welche Rolle spielt er in der Informatik? e) Wie kann man unendliche Objekte durch Automaten und Grammatiken endlich darstellen? |
Lernziel | Vermittlung der grundlegenden Konzepte der Informatik in ihrer geschichtlichen Entwicklung |
Inhalt | Die Veranstaltung ist eine Einführung in die Theoretische Informatik, die die grundlegenden Konzepte und Methoden der Informatik in ihrem geschichtlichen Zusammenhang vorstellt. Wir präsentieren Informatik als eine interdisziplinäre Wissenschaft, die auf einer Seite die Grenzen zwischen Möglichem und Unmöglichem und die quantitativen Gesetze der Informationsverarbeitung erforscht und auf der anderen Seite Systeme entwirft, analysiert, verifiziert und implementiert. Die Hauptthemen der Vorlesung sind: - Alphabete, Wörter, Sprachen, Messung der Informationsgehalte von Wörtern, Darstellung von algorithmischen Aufgaben - endliche Automaten, reguläre und kontextfreie Grammatiken - Turingmaschinen und Berechenbarkeit - Komplexitätstheorie und NP-Vollständigkeit - Algorithmenentwurf für schwere Probleme |
Skript | Die Vorlesung ist detailliert durch das Lehrbuch "Theoretische Informatik" bedeckt. |
Literatur | Basisliteratur: 1. J. Hromkovic: Theoretische Informatik. 5. Auflage, Springer Vieweg 2014. 2. J. Hromkovic: Theoretical Computer Science. Springer 2004. Weiterführende Literatur: 3. M. Sipser: Introduction to the Theory of Computation, PWS Publ. Comp.1997 4. J.E. Hopcroft, R. Motwani, J.D. Ullman: Einführung in die Automatentheorie, Formale Sprachen und Komplexitätstheorie. Pearson 2002. 5. I. Wegener: Theoretische Informatik. Teubner Weitere Übungen und Beispiele: 6. A. Asteroth, Ch. Baier: Theoretische Informatik |
Voraussetzungen / Besonderes | Während des Semesters werden zwei freiwillige Probeklausuren gestellt. |
Leistungskontrolle
Information zur Leistungskontrolle (gültig bis die Lerneinheit neu gelesen wird) | |
Leistungskontrolle als Semesterkurs | |
ECTS Kreditpunkte | 7 KP |
Prüfende | J. Hromkovic |
Form | Sessionsprüfung |
Prüfungssprache | Deutsch |
Repetition | Die Leistungskontrolle wird nur in der Session nach der Lerneinheit angeboten. Die Repetition ist nur nach erneuter Belegung möglich. |
Prüfungsmodus | schriftlich 180 Minuten |
Zusatzinformation zum Prüfungsmodus | Es finden zwei freiwillige Zwischenklausuren statt. Um zu den Zwischenklausuren zugelassen zu werden, werden jeweils 50 Prozent der Punkte aus den Übungen benötigt bis zu dem jeweiligen Klausurtermin. Aus den beiden Zwischenklausuren wird eine Durchschnittsnote ermittelt (ggf. Rundung auf nächstbessere Viertelnote). Am Ende des Semesters wählt jeder Teilnehmer eine von zwei Möglichkeiten aus: Entweder Übernahme der Note aus den Zwischenklausuren oder Teilnahme an der Sessionsprüfung. |
Hilfsmittel schriftlich | Keine. |
Diese Angaben können noch zu Semesterbeginn aktualisiert werden; verbindlich sind die Angaben auf dem Prüfungsplan. |
Lernmaterialien
Hauptlink | Information |
Literatur | Juraj Hromkovic: Theoretische Informatik, 5. Auflage, Springer Vieweg 2014. |
Es werden nur die öffentlichen Lernmaterialien aufgeführt. |
Gruppen
Keine Informationen zu Gruppen vorhanden. |
Einschränkungen
Keine zusätzlichen Belegungseinschränkungen vorhanden. |