Dynamische Programmierung und Greedy - Grundlagen

[@95Coaster]

Unfassbar, dass dieses Video nur 300 Aufrufe hat. Mir hat es gerade sehr beim Lernen geholfen, vielen Dank, super erklärt!

[@carsteneinwort]

Dem stimme ich zu!

[@totoman999]

Gesegnet seid ihr, Freunde! Das hat mir wirklich weitergeholfen!

[@tarekdawalibi1776]

Sehr gut Erklärt (y) Danke sehr!

[@katharinah5105]

was ist ein NP-hartes Problem?

[@jusa7603]

Ein NP-Hartes Problem, oder NP-Schweres Problem bezeichnet eine Eigenschaft eines algorithmischen Problems. Eine wichtige Problemklasse ist die Komplexitätsklasse NP, die Klasse aller Entscheidungsprobleme, für die eine gefundene Lösung effizient überprüft werden kann. Dabei steht NP für nichtdeterministische Polynomialzeit. Ein NP-schweres Problem ist dabei mindestens so „schwer“ wie alle Probleme in NP. Das bedeutet, dass ein Algorithmus, der ein NP-schweres Problem löst, mithilfe einer Reduktion benutzt werden kann, um alle Probleme in NP zu lösen.

[@ZeonLP]

@@jusa7603 "Ein NP-schweres Problem ist mindestens so 'schwer' wie alle Probleme in NP" Würde das nicht bedeuten, dass alle NP-schweren Probleme gleich "schwer" sind? Wenn wir zwei Probleme p1, p2 in NP wählen, dann gilt p1 >= p2 und p2 >= p1 (wenn >= "mindestens so schwer" bedeutet). Daraus kann ja nur p1 "=" p2 folgen.

[@j.franciscox3318]

Well I guess it's dynamic programming and greedy algorithms.