Type and Content |
| Title: |
Algorithmen, Komplexitätstheorie und Formale Sprachen |
| Host: |
Reischuk |
| Classification: |
Diplom-Studiengang Informatik 5. Semester, Pflicht
Bachelor-Studiengang Informatik, mit Ergänzungsfach Bioinformatik/Biomathematik, 5. Semester, Wahlpflicht |
| Conentent: |
- Entwurf und Analyse effizienter Algorithmen,
- Komplexität algorithmischer Probleme,
- Maschinenmodelle,
- Berechenbarkeit,
- Rekursionstheorem,
- Sprachfamilien,
- Hierarchien
|
| Literature: |
- Aho, Hopcroft, Ullman, Design and Analysis of Computer Algorithms, Addison Wesley 1978
- Cormen, Leiserson, Rivest, Introduction to Algorithms, MIT Press 1990
- R. Reischuk, Komplexitätstheorie, Band I: Grundlagen, Teubner 1998
- Hopcroft, Ullman, Introduction to Automata Theory, Languages and Computation, Addison Wesley 1979
- Harrison, Introduction to Formal Language Theory, Addison Wesley 1978
- Kleinberg, Tardos, Algorithm Design, Addison Wesley 2005
|
Lecture |
| Host: |
Reischuk |
| Hours: |
4 SWS, 8 ETCS |
| Dates: |
Mi. + Fr. 8h -10h, Raum R3 |
| Skripte: |
- 1. Skript (Prädikatenlogik, (Primitive) Rekursion, LOOP, WHILE)
- 2. Skript (Turing-Maschine, RAM, Gödelisierung, Halteproblem, Indexmenge, rekursive Mengen)
- 3. Skript (Unentscheidbarkeit des Halteproblems, Diagonalisierung, rekursive Aufzählbarkeit, S-m-n-, Rekursionstheorem, Fixpunktsatz, Satz von Rice, PKP, Beweismethoden rekursiv / rekursiv aufz., Reduktion )
- Skriptabschnitt über kontextfreie Grammatiken
- 5. Skript (Komprimierung von Strings, String-Verarbeitung)
- 6. Skript (Weitere String-Probleme, Erfüllbarkeitsproblem, Resolutionsmethode)
- 7. Skript (noch nicht verfügbar)
- 8. Skript (Online-Algorithmen, kompetitive Rate, Flussprobleme, Matching-Probleme)
1. Quiz (Rekursionstheorie)
|
Exercise |
| Host: |
Reischuk, Hinkelmann |
| Hours: |
2 SWS |
| Dates: |
Diplom: 2 SWS Übungen (2 Gruppen)
Mo. 16h -18h, Raum H4, ITCS Seminarraum Nr. 21, S 3b
Bachelor: 2 SWS Übung (1 Gruppe)
Mo. 16h -18h, Raum Seminarraum 1 (Minsky), ITCS Seminarraum Nr. 21, Notebookarbeitsraum (Neumann) Geb. 64, EG
Gruppe:
- I – Seminarraum TCS
- II – Seminarraum I (Gödel)
- III – Seminarraum VK / V1
|
| Übungsblätter: |
|
