Komplexität und Berechenbarkeit

View all featured content
saschkai

saschkai

Dr Franke Ghostwriter
miteinander,
hat vielleicht schon jemand etws zu dem Thema Komplexität & Berechenbarkeit für den Klausurzettel, dass er gerne mit uns teilen würde😀
was meint ihr ist hier wichtig, oder vernachlässigt ihr es komplett
😀 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?
 
Nach Datum sortieren Nach Stimmen sortieren
Sascha,

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
 
Positive Stimme 0 Negative Stimme
Antworten
Oben