, um zu prüfen, ob Sie einen Vollzugriff auf diese Publikation haben.
Sammelband Kein Zugriff
Komplexität von Algorithmen
Mathematik für Anwendungen Band 4
Autor:innen/Herausgeber:innen:
| |
Verlag:
2020
Zusammenfassung
Dieses Lehrbuch, entstanden aus einer Anfängervorlesung aus dem Informatik-Studiengang an der Leibniz Universität Hannover, bietet einen ersten Einstieg in den Bereich der Komplexitätstheorie. Der Leser wird mit den wichtigsten Begriffen und Resultaten aus diesem Bereich vertraut gemacht: Komplexitätsklassen, vollständige („schwierigste“) Probleme in einer Komplexitätsklasse – detailliert am Begriff der NP-Vollständigkeit und an vielen Beispielen ausgeführt – sowie Approximationsalgorithmen als Lösungsmöglichkeit für viele NP-vollständige Probleme. Außerdem enthält das Buch eine große Anzahl an Übungsaufgaben (mit vielen Lösungen) wie auch abschließend die Möglichkeit, sein erarbeitetes Wissen in zwei exemplarischen Klausuren zu prüfen.
Schlagworte
Publikation durchsuchen
Bibliographische Angaben
Auflage
2/2020
Copyrightjahr
2020
ISBN-Print
978-3-96543-137-9
ISBN-Online
978-3-96543-142-3
Verlag
Lehmanns Media, Berlin
Sprache
Deutsch
Seiten
212
Produkttyp
Sammelband
Inhaltsverzeichnis
KapitelSeiten
Titelei/Inhaltsverzeichnis Kein Zugriff Seiten 1 - 6
Welche Probleme wollen wir lösen? Kein Zugriff
Eine Universalmaschine Kein Zugriff
Viele Bänder bringen nicht viel mehr als zwei Kein Zugriff
Nichtdeterminismus Kein Zugriff
Beziehungen zwischen den Komplexitätsklassen Kein Zugriff
Die Hierarchiesätze Kein Zugriff
Sind Turingmaschinen ein realistisches Modell? Kein Zugriff
Polynomialzeit – die Klasse P Kein Zugriff
NP – the class of dashed hopes and idle dreams Kein Zugriff
Die größte Frage der Informatik: Das P-NP-Problem Kein Zugriff
Reduzierbarkeit – aus Problem A wird Problem B Kein Zugriff
Vollständigkeit – das (vorerst) letzte Wort Kein Zugriff
Der Satz von Cook und Levin – der Anfang ist gemacht Kein Zugriff
Graphenprobleme Kein Zugriff
Numerische Probleme Kein Zugriff
Mahaney's Theorem Kein Zugriff
Rezepte Kein Zugriff
Optimierungsprobleme – bis wohin geht's? Kein Zugriff
Approximationsalgorithmen Kein Zugriff
Das Problem des Handlungsreisenden MinTSP Kein Zugriff
