Fallstudie - Das Rundreiseproblem / Schwer lösbare Probleme

Worum geht es hier?

Wir werden uns hier intensiver mit einem Rundreiseproblem bei Graphen beschäftigen, das als schwer zu lösen eingestuft wird. Die Schwierigkeit besteht darin, dass bis heute nur Lösungen mit sehr hohem Rechenaufwand gefunden wurden.

Bei der Beschäftigung mit dem Rundreiseproblem werden auch die Konzepte eingeführt, die man benötigt, um das in der Informatik sehr bekannte "P=NP?"-Problem zu verstehen.

Hier lernst du ...

• ... wie man das Euler- und das Hamilton-Problem löst.
• ... welche Komplexität entsprechende Lösungsalgorithmen haben.
• ... was man unter den Klassen P und NP versteht.
• ... wie man ein Problem auf ein anderes Problem (polynomial) reduziert.
• ... was ein NP-vollständiges Problem ist und welche Bedeutung diese Probleme haben.