|
Vorlesung, 4 SWS, ECTS-Studium, ECTS-Credits: 8;
Fachgebiet: Theoretische und Praktische Informatik
|
|
Zeit und Ort:
| Do, 10:15 - 11:45 Uhr,
CAP2-R.B[Audimax]
|
| | Mo, 10:15 - 11:45 Uhr,
LMS2-R.Ü2
|
|
Erster Termin:
|
Do, 25.10.2007, 10:15 - 11:45 Uhr
|
|
Abweichender Termin:
|
Di, 22.1.2008, 12-14 statt Mo, 21.1.
|
|
Abweichender Termin:
|
Di, 29.1.2008, 12-14 statt Mo, 28.1.
|
|
Abweichender Termin:
|
Di, 5.2.2008, 12-14 statt Do, 7.2.
|
| Klausurtermin: |
14. Februar 08, während der Vorlesungszeit |
|
Die Vorlesung wendet sich an Diplom-Informatiker und
Diplom-Mathematiker mit Nebenfach Informatik nach dem Vordiplom. Es werden
zentrale Algorithmen der Informatik vorgestellt, zusammen mit einer
Einführung und Diskussion der wichtigsten Entwurfstechniken. Daneben sollen
Ergebnisse über untere Aufwandsschranken behandelt werden.
Themenstichworte sind: - Grundlagen: Komplexitätsmaße, Datenstrukturen und Algorithmen für
Mengen (via Listen und Bäume)
- Graph-Algorithmen, u. a. für minimale Spannbäume. Zusammenhangs- und
Flußprobleme, allgemeines Wegeproblem
- Algebraische Probleme: Matrizenmultiplikation, Polynomauswertung und
-multiplikation, schnelle Fouriertransformation, Optimalitätsfragen
- NP-Vollständigkeit
|
- Levitin, Introduction to the Design and Analysis of Algorithms: International Edition
- Cormen, Leiserson, Rivest, Introduction to Algorithms, MIT Press, Cambridge, Mass 1990
- Aha, Hopcroft, Ullman, The Design and Analysis of Computer Algorithms, Addison-Wesley, Reading, MA, 1974
- A. Brandstädt, Graphen und Algorithmen, B. G. Teubner, 1994
|
|