miteinander,
hat vielleicht schon jemand etws zu dem Thema Komplexität & Berechenbarkeit für den Klausurzettel, dass er gerne mit uns teilen würde:D
was meint ihr ist hier wichtig, oder vernachlässigt ihr es komplett
:D würd ich gern, trau mich nicht...
sorry- die letzten seiten waren einfach nicht mein ding.
wie gesagt, hat jemand zusammenfassende notizen für den spicker?
Comments
Moritz
Contributions on this page: 1
View profileSascha,
meinst Du den letzten Teil der KE4?
NP |Es gibt Probleme für die kein Algorithmus zur Lösung des
Problems bekannt ist. |Nicht jede Heuristik hat polynomielle Laufzeit.
Das Simplex-Verfahren hat bei manchen Eingaben eine exponentielle
Laufzeit. |Bei einem Problem aus NP muss stets eine potentielle Lösung
in polynomieller Zeit validiert werden können, ob sie tatsächlich eine
Lösung des Problems darstellt. |Für das Bin-Packing Problem gibt es
keinen Algorithmus, der eine optimale Lösung in polynomieller Zeit
errechnet, da das Bin-Packing Problem in NP liegt.
Wenn da aber eine Aufgabe drankommt, bei welcher man das richtig verstanden haben muss, sehe ich alt aus ;)
LG,
Mo