Komplexität von Algorithmen

In dieser Vorlesung beschäftigen wir uns mit der Frage, welche Berechnungsprobleme effizient algorithmisch lösbar sind. Dazu werden wir die Komplexitätsmaße Laufzeit und Speicherbedarf formal einführen und untersuchen. Eine zentrale Rolle werden dabei die Komplexitätsklassen P und NP sowie sog. NP-vollständige Probleme spielen. Dies sind Probleme, für die weder ein effizienter Algorithmus bekannt ist noch bewiesen wurde, dass keiner existieren kann. NP-vollständige Probleme kommen in vielen Bereichen der Informatik (VLSI-Design, Netzwerk-Optimierung, Operations-Research, etc.) vor. Erstaunlicherweise zeigt sich, dass alle diese Probleme äquivalent sind in dem Sinne, dass sie alle effizient lösbar sind, wenn man nur für eines von ihnen einen effizienten Algorithmus entdeckt. * Raum- und Zeitkomplexität * Beziehungen zwischen den Komplexitätsklassen * Die Hierarchiesätze * Die Klasse P * Die Klasse NP * NP-Vollständigkeit * Der Satz von Cook * Weitere NP-vollständige Probleme * Approximierbarkeit * Das Problem des Handlungsreisenden * Das Partitionierungsproblem. Literatur1. John E. Hopcroft, Rajeev Motwani, Jeffrey D. Ullman, Einführung in die Automatentheorie, Formale Sprachen und Komplexitätstheorie, Pearson Studium, 2002. 2. Michael Sipser, Introduction to the Theory of Computation, PWS Publishing Company, 1997. 3. Christos Papadimitriou, Computational Complexity, Addison-Wesley, 1994. 4. G. Ausiello et al., Complexity and Approximation: Combinatorial Optimization Problems and Their Approximability Properties, Springer, 1999. 5. D. Harel, Algorithmics – The Spirit of Computing, Addison-Wesley, 3. Auflage, 2004. Bemerkung Hilfreich, aber nicht notwendig sind Kenntnisse über Turing Maschinen ( wie z.B. in Grundlagen der Theoretischen Informatik gelernt). Erfahrungsgemäß führt dies zu Anfangsschwierigkeiten im TI-Studium. Aus diesem Grund bieten wir in der ersten Übungswoche eine Einführung zu diesem Thema. 1. John E. Hopcroft, Rajeev Motwani, Jeffrey D. Ullman, Einführung in die Automatentheorie, Formale Sprachen und Komplexitätstheorie, Pearson Studium, 2002. 2. Michael Sipser, Introduction to the Theory of Computation, PWS Publishing Company, 1997. 3. Christos Papadimitriou, Computational Complexity, Addison-Wesley, 1994. 4. G. Ausiello et al., Complexity and Approximation: Combinatorial Optimization Problems and Their Approximability Properties, Springer, 1999. 5. D. Harel, Algorithmics – The Spirit of Computing, Addison-Wesley, 3. Auflage, 2004. Bemerkung Hilfreich, aber nicht notwendig sind Kenntnisse über Turing Maschinen ( wie z.B. in Grundlagen der Theoretischen Informatik gelernt). Erfahrungsgemäß führt dies zu Anfangsschwierigkeiten im TI-Studium. Aus diesem Grund bieten wir in der ersten Übungswoche eine Einführung zu diesem Thema. keine öffentliche Person Hilfreich, aber nicht notwendig sind Kenntnisse über Turing Maschinen ( wie z.B. in Grundlagen der Theoretischen Informatik gelernt). Erfahrungsgemäß führt dies zu Anfangsschwierigkeiten im TI-Studium. Aus diesem Grund bieten wir in der ersten Übungswoche eine Einführung zu diesem Thema. Universität Hannover SoSe 2015 Informatik, Bachelor of Science Dr. Meier Arne