Hallo, mir ist gerade aufgefallen, dass wir für Aufgabe 2.3 auf Übungsblatt 6 die Größe (k) der Knotenüberdeckung für die das Entscheidungsproblem gelöst werden soll nicht angegeben haben. Die Laufzeit Ihres Brute Force Algorithmus wird aber (vermutlich) wesentlich von k abhängen. Insbesondere ist für manche Werte von k die Antwort trivial (insbesondere k=n, oder k=1).
Wählen Sie hier bitte eine Zahl, die zwischen 1 und n liegt und mit n wächst, beispielsweise k=n/6 (gerundet auf eine ganze Zahl).
Alternativ können Sie in Aufgabe 2 auch einen BruteForce Algorithmus für das Optimierungsproblem *kleinste* Knotenüberdeckung angeben und diesen dann nutzen. Machen Sie aber bitte deutlich, ob Sie hier das Entscheidungs- oder das Optimierungsproblem betrachten, damit wir beim Korrigieren wissen, womit wir es zu tun haben.
Viele Grüße und weiterhin viel Spaß mit dem Übungsblatt,
Marie Schmidt
Haben Sie die Aufgabe schon unter Annahme einer sinnvollen Größe k gelöst? Prima, Sie brauchen nichts zu ändern. Auch sonst