392003 Theoretische Informatik (V) (SoSe 2001)
Contents, comment
-
Um ein gegebenes Problem mit dem Computer lösen zu können, sind zwei Schritte notwendig: (a) das "Erfinden" eines Berechnungsverfahrens und (b) die sprachliche Realisierung als Programm.
Die Vorlesung behandelt die dazu erforderlichen theoretischen Grundlagen, die eine zentrale Stellung innerhalb der theoretischen Informatik haben. In Teil I geht es um formale Sprachen und Grammatiken bis hin zu einer Typisierung von Sprachklassen nach ihrer Leistungsfähigkeit (Chomsky-Hierarchie). Unter dem Gesichtspunkt der Spracherkennung betrachtet der Teil II formale Sprachen und Automaten (deterministische und nichtdeterministische endliche Automaten, Kellerautomaten, Turing-Maschinen und RAM-Maschinen). In Teil III folgen
Einführungen in die Berechenbarkeitstheorie, die sich mit grundsätzlichen Möglichkeiten und Grenzen der Algorithmisierbarkeit befaßt, und in die Komplexitätstheorie, die untersucht, mit welchem Aufwand an Berechnungsressourcen (Rechenzeit, Speicherplatz) algorithmische Aufgaben gelöst werden können. In Teil IV werden Grundzüge der Logik vermittelt. Auf diesen Grundlagen bauen im Hauptstudium Vorlesungen zur Logik und Rekursionstheorie, Logik-Programmierung, zum Übersetzerbau und zur Künstlichen Intelligenz auf.Vorausgesetzt werden neben mathematischem Grundlagenwissen auch Kenntnisse in der Programmierung.
Literatur:
- Schöning, U.: Theoretische Informatik kurz gefaßt. (2. Auflage) Mannheim: BI Wissenschaftsverlag, 1995
- Hopcroft, J.E., Ullman, J.D.: Introduction to automata theory, languages, and computation. Reading, Mass.: Addison-Wesley, 1979; dt.: Einführung in die Automatentheorie, Formale Sprachen und Komplexitätstheorie. Bonn: Addison-Wesley, 1988 (zur Vertiefung)
- Lewis, H.R., Papadimitriou, C.H.: Elements of the theory of computation. Englewood Cliffs, N.J.: Prentice Hall, 1981 (zur Vertiefung)
- Schöning, U.: Logik für Informatiker (4. Aufl.). Mannheim: BI Wissenschaftsverlag, 1989 (in Auszügen)
External comments page
Teaching staff
Dates ( Calendar view )
| Frequency | Weekday | Time | Format / Place | Period | |
|---|---|---|---|---|---|
| weekly | Di | 10-12 | H12 | - | |
| weekly | Do | 10-12 | H13 | - |
Subject assignments
| Degree programme/academic programme | Validity | Variant | Subdivision | Status | Semester | LP | |
|---|---|---|---|---|---|---|---|
| Naturwissenschaftliche Informatik / Diplom | (Enrollment until SoSe 2004) | - | - | Pflicht | 4. | - | GS |
- Registered number: 2
- This is the number of students having stored the course in their timetable. In brackets, you see the number of users registered via guest accounts.
- Address:
- SS2001_392003@ekvv.uni-bielefeld.de
- This address can be used by teaching staff, their secretary's offices as well as the individuals in charge of course data maintenance to send emails to the course participants. IMPORTANT: All sent emails must be activated. Wait for the activation email and follow the instructions given there.
- If the reference number is used for several courses in the course of the semester, use the following alternative address to reach the participants of exactly this: VST_1000569@ekvv.uni-bielefeld.de
- Coverage:
- No students to be reached via email
- Notes:
- Additional notes on the electronic mailing lists
- Last update basic details/teaching staff:
- Friday, December 11, 2015
- Last update times:
- ?
- Last update rooms:
- ?
- Type(s) / SWS (hours per week per semester)
- lecture (V) / 4
- Department
- Faculty of Technology
- Questions or corrections?
- Questions or correction requests for this course?
- Planning support
- Clashing dates for this course
- Links to this course
- If you want to set links to this course page, please use one of the following links. Do not use the link shown in your browser!
- The following link includes the course ID and is always unique:
- https://ekvv.uni-bielefeld.de/kvv_publ/publ/vd?id=1000569
- Send page to mobile
-
Click to open QR code
Scan QR code:
- ID
- 1000569