Berechenbarkeit und Komplexität
» This course is given in German.
Vorlesung im Wintersemester 2004/2005
| Art | Termine/Ort | Beginn | Veranstalter |
|---|---|---|---|
| V3 | Di 08:15 - 09:45 Ro Fr 11:45 - 12:30 Ro |
12.10.2004 | Thomas |
| Ü1 | Mi 12:30 - 13:15 Ro | 15.10.2004 | Thomas, Wöhrle |
| ÜT2 | Mo 10:15h-11:45h, 5052 Mo 10:15h - 11:45h, 5054 Mo 12:30h - 14:00h, 5056 Mo 14:15h - 15:45h, 5056 Mi 12:00h - 13:30h, 5054 Mi 13:30h - 15:00h, 5054 Mi 13:45h - 15:15h, 6019 Mi 13:45h - 15:15h, AH VI |
Thomas, Wöhrle |
Inhalt
Ziel dieser Vorlesung ist die Klärung von Grundbegriffen der Informatik wie z.B. "algorithmisches Problem", "Algorithmus", "Berechnung", "Simulation", "Rechenaufwand".
Im Rahmen dieser (mathematisch aufgebauten) Theorie der Berechenbarkeit und Komplexität kann man dann beurteilen, welche algorithmischen Probleme lösbar sind bzw. welche Probleme "praktisch" (effizient) lösbar sind. Die Bedeutung der hier entwickelten Methoden und Resultate liegt darin, dass sie überwiegend unabhängig von heutigen Hardware-Technologien sind. Die methodischen Kenntnisse und Konzepte sind auch bei der Lösung konkreter Aufgaben in der Paxis von Nutzen.
Themenübersicht:- Algorithmische Probleme, Berechnungsmodelle
- Turing-Maschinen und äquivalente Programmiersprachen
- Algorithmische Lösbarkeit von Problemen
- Komplexität von Berechnungen, NP-Vollständigkeit
- Randomisierte und approximative Verfahren, Kryptografie