252-0057-00L  Theoretische Informatik

SemesterHerbstsemester 2017
DozierendeJ. Hromkovic
Periodizitätjährlich wiederkehrende Veranstaltung
LehrspracheDeutsch
KommentarHinweis: 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

NummerTitelUmfangDozierende
252-0057-00 VTheoretische Informatik4 Std.
Di08:15-10:00HG G 5 »
Fr08:15-10:00HG G 5 »
10.11.08:15-10:00HG E 1.2 »
08:15-10:00HG E 3 »
08:15-10:00HG E 7 »
15.12.08:15-10:00HG E 1.2 »
08:15-10:00HG E 3 »
08:15-10:00HG E 7 »
J. Hromkovic
252-0057-00 UTheoretische Informatik2 Std.
Di13:15-15:00CAB G 59 »
13:15-15:00HG E 21 »
13:15-15:00ML J 37.1 »
13:15-15:00NO C 44 »
Mi15:15-17:00ETZ E 7 »
15:15-17:00ETZ E 9 »
15:15-17:00ETZ G 91 »
15:15-17:00HG D 3.3 »
15:15-17:00HG G 26.3 »
Do16:15-18:00HG E 33.1 »
16:15-18:00HG E 33.5 »
16:15-18:00HG F 26.3 »
J. Hromkovic

Katalogdaten

KurzbeschreibungKonzepte 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?
LernzielVermittlung der grundlegenden Konzepte der Informatik in ihrer geschichtlichen Entwicklung
InhaltDie 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
SkriptDie Vorlesung ist detailliert durch das Lehrbuch "Theoretische Informatik" bedeckt.
LiteraturBasisliteratur:
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 / BesonderesWährend des Semesters werden zwei freiwillige Probeklausuren gestellt.

Leistungskontrolle

Information zur Leistungskontrolle (gültig bis die Lerneinheit neu gelesen wird)
Leistungskontrolle als Semesterkurs
ECTS Kreditpunkte7 KP
PrüfendeJ. Hromkovic
FormSessionsprüfung
PrüfungsspracheDeutsch
RepetitionDie Leistungskontrolle wird nur in der Session nach der Lerneinheit angeboten. Die Repetition ist nur nach erneuter Belegung möglich.
Prüfungsmodusschriftlich 180 Minuten
Zusatzinformation zum PrüfungsmodusEs 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 schriftlichKeine.
Diese Angaben können noch zu Semesterbeginn aktualisiert werden; verbindlich sind die Angaben auf dem Prüfungsplan.

Lernmaterialien

 
HauptlinkInformation
LiteraturJuraj 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.

Angeboten in

StudiengangBereichTyp
Computational Biology and Bioinformatics MasterMethoden der InformatikWInformation
Informatik BachelorGrundlagenfächerOInformation
Informatik LehrdiplomTeil 1OInformation
Mathematik BachelorKernfächer aus Bereichen der angewandten Mathematik ...WInformation