Allgemeine Informationen
| Veranstaltungsname | Vorlesung + Übung: Informatik III |
| Veranstaltungsnummer | W 1104 |
| Semester | WS 2014/15 |
| Aktuelle Anzahl der Teilnehmenden | 68 |
| Heimat-Einrichtung | Institut für Informatik |
| Veranstaltungstyp | Vorlesung + Übung in der Kategorie Lehre |
| Erster Termin | Dienstag, 21.10.2014 10:00 - 12:00, Ort: (D5-105 IfI - Seminarraum 105 (T1)) |
| Teilnehmende |
Grundstudium Informatik, Wirtschaftsinformatik, Informationstechnik, Mathematik, Wirtschaftsmathematik und Technomathematik It: Ersatz für W 1103 |
| Leistungsnachweis |
Prüfungsvorleistungen: Hausübungen Modulprüfung: Abschlussklausur oder mündliche Prüfung |
| Literatur |
* Hopcroft, J. E., und Ullman, J. D.: Einfuehrung in die Automatentheorie, Formale Sprachen und Komplexitaetstheorie, Addison-Wesley (Deutschland), 1989 * Katrin Erk, Lutz Priese: Theoretische Informatik - Eine umfassende Einfuehrung Springer Verlag, 2000 |
| Medienformen | Beamer-Präsentation, Tafel, Whiteboard |
| SWS | 4 |
| Sonstiges |
Die Studierenden lernen die Grundbegriffe der formalen Sprachen (Grammatiken) und die entsprechenden Automaten kennen. Sie können Parser entwickeln, lernen Grundbegriffe des dynamischen Programmierens (Charts) und können Probleme als entscheidbar/unentscheidbar nachweisen. Ausserdem können sie die Komplexitaet von Problemen bestimmen (P/NP). + Grammatiken der Chomsky Hierarchie (Typ3-Typ 0) + Reguäre Ausdrücke, Satz von Kleene + Endliche Automaten (indet.), epsilon Kanten, Pumping Lemma + Kellerautomaten, Turingmaschinen + Busy Beaver, Halteproblem, Reduktionen, aufzaehlbar/entscheidbar + Random access machines, P/NP |
