|
Strukturbaum
Keine Einordnung ins Vorlesungsverzeichnis vorhanden.
Veranstaltung ist aus dem Semester
SS 2013
, Aktuelles Semester: SoSe 2026
|
- Funktionen:
Zur Zeit kein Belegungszeitraum aktiv.
|
|
Theoretische Informatik Übungen
Sprache: Deutsch
Belegpflicht
|
|
Nr.:
4565
Praktikum
SS 2013
2 SWS
Jedes Semester
|
|
Master-Studiengang:
|
Masterstudiengang Informatik
|
|
|
| |
|
Studiengang
|
Informatik, Abschluss 90,
(
2.
Semester )
- ECTS-Punkte : 3
- Kategorie : Wahlfach
|
|
Zugeordnete Lehrpersonen:
|
Ertel
verantwortlich
,
Drotleff
|
| |
|
|
|
|
Zur Zeit kein Belegungszeitraum aktiv.
|
|
|
Termin:
|
Donnerstag
16:00
-
17:30
wöchentl
|
Durchf. Lehrperson:
Ertel
|
Raum :
K 003
Gebäude K
|
| |
| |
| Inhalt: |
* Berechenbarkeit
- Turingmaschinen
- Loop-Berechenbarkeit
- While-Berechenbarkeit
* Entscheidbarkeit
- Halteproblem
- Postsches Korrespondenzproblem
- Satz von Rice
* Komplexitätstheorie
- Komplexitätsklassen
- NP-Vollständigkeit
Übungen zu Theorie und Praxis aller Teilgebiete vertiefen das
Verständnis der behandelten Themen. |
| |
| Literatur: |
D. Hoffmann: Theoretische Informatik, Hanser Verlag, 2009
M. Garey and D. Johnson: Computers and Intractability, Freeman, 1979 |
| |
| Lernziele: |
Der Student soll verstehen, daß es Funktionen gibt, die ein Computer prinzipiell nicht berechnen kann. Er wird u.a. am Beispiel des Halteproblems ein für die Praxis wichtiges Beispiel für eine nicht entscheidbare Funktion kennenlernen.
Wichtig ist auch das Verständnis der klassischen Unterteilung der Sprachen, bzw. Berechnungsprobleme in die Komplexitätsklassen. Begriffe
wie P, NP, Entscheidbarkeit und rekursive Aufzählbarkeit werden eingeführt. |
| |
| Voraussetzungen: |
Theoretische Informatik |
| |
| Leistungsnachweis: |
PA, unbenotet |
| |
|
|
| Module: |
Theoretische Informatik (IN) |
LSF Online-Hilfe
