Veranstaltungsart und -inhalt
|
| Titel |
Einführung in die Informatik IV |
| Dozent |
Prof. Reischuk |
| Einordnung |
Diplom-Studiengang 4. Semester Pflicht
Bachelor-Studiengang 4. Semester Pflicht
|
| Inhalte |
-
Modellierung, Analyse und Lösung algorithmischer Probleme
-
Algorithmische Komplexität: Komplexitätsmaße,
Komplexitätsklassen, NP-Vollständigkeit,
Erfüllbarkeitsprobleme der Logik, diskrete
Optimierungsprobleme
-
Formale Sprachen: Formale Grammatiken, reguläre Sprachen
und Ausdrücke, kontextfreie und kontextsensitive
Sprachen, Chomsky Hierarchie, Pumping Lemma,
Wortprobleme
-
Maschinenmodelle: endliche Automaten, Turing-Maschinen,
Registermaschinen, Determinismus, Nichtdeterminismus,
Reduktion zwischen Problemen, Simulation,
Entscheidbarkeit, Aufzählbarkeit
|
| Buchempfehlungen |
- [HU94] J. Hopcroft, J. Ullman: Einführung in die Automatentheorie, Formale Sprachen und Komplexitätstheorie. Add.Wesley 1994
- [Ha78] M. Harrison: Introduction to Formal Language. Theory. Add.Wesley 1978
- [Sa98] J. Savage: Models of Computation. Add.Wesley 1998
- [Re98] R. Reischuk: Komplexitätstheorie, Band I: Grundlagen, Maschinenmodelle, Zeit- und Platzkomplexität, Nichtdeterminismus.Teubner 1998
- [GJ79] M. Garey, D. Johnson: Computers and Intractability. Freeman, 1979
- [KT05] J. Kleinberg, E. Tardoz: Algorithmen Design. Add. Wesley 2005
|
| Wiki |
Wiki zur Veranstaltung
»Einführung in die Informatik – IV«
|
Vorlesung |
| Dozent |
Prof. Reischuk |
| Umfang |
4 SWS, ECTS-Credits: 9 |
| Termine |
Mi. 8.00h-10.00h, Raum T1/Transistorium und Fr. 8.00h-10.00h, H1
|
Übung |
| Assistent |
Hinkelmann |
| Umfang |
3 SWS |
| Termine |
Gruppe 1: Mo. 14.00h-16.00h + Do. 11.00h-12.00h Seminarraum Informatik 4 (Minsky)
Gruppe 2: Mo. 14.00h-16.00h + Do. 11.00h-12.00h Seminarraum Informatik 2+3 (Cook+Karp)
Gruppe 3: Mo. 14.00h-16.00h ITCS-Seminarraum 2. OG. Zi. 2021 + Fr. 10.00h-11.00h H2
|
