0 Daumen
1,4k Aufrufe

Gegeben eine Menge U und eine Menge S, die Teilmengen von U enthält. Eine Überdeckung ist die kleinste Teilmenge C von S, deren Vereinigung U ergibt. Für die TeilmengenS1 = (1; 3; 5), S2 = (2; 4), S3 = (1; 4) und S4 = (2; 5) wäre beispielsweise (S1; S2) eine Überdeckung von U = (1; 2; 3; 4; 5).

Finden Sie ein Gegenbeispiel für den folgenden Algorithmus zum Finden einer Überdeckung:
Wähle immer die Teilmenge mit der größten Anzahl an noch nicht überdeckten
Elementen aus, solange bis alle Elemente aus U abgedeckt sind.



Ich habe mehrere Aufgaben dieser Art, weiß aber nicht wirklich wie ich es angehen soll. Wenn mir das jemand an dem Beispiel erklären könnte, würde mir das bestimmt weiterhelfen.

Avatar von

Vom Duplikat:

Titel: Algorithmus - Mengenüberdeckung

Stichworte: algorithmus,informatik

Gegeben eine Menge U und eine Menge S, die Teilmengen von U enthält. Eine Überdeckung ist die kleinste Teilmenge C von S, deren Vereinigung U ergibt. Für die TeilmengenS1 = (1; 3; 5), S2 = (2; 4), S3 = (1; 4) und S4 = (2; 5) wäre beispielsweise (S1; S2) eine Überdeckung von U = (1; 2; 3; 4; 5).

Finden Sie ein Gegenbeispiel für den folgenden Algorithmus zum Finden einer Überdeckung:
Wähle immer die Teilmenge mit der größten Anzahl an noch nicht überdeckten
Elementen aus, solange bis alle Elemente aus U abgedeckt sind.


Ich habe mehrere Aufgaben dieser Art, weiß aber nicht wirklich wie ich es angehen soll. Wenn mir das jemand an dem Beispiel erklären könnte, würde mir das bestimmt weiterhelfen.

1 Antwort

+1 Daumen
Wähle immer die Teilmenge mit der größten Anzahl an noch nicht überdeckten Elementen aus.

U = {1, 2, 3, 4, 5, 6}, S = {{1, 2, 3, 4}, {1, 2, 5}, {3, 4, 6}}

wie ich es angehen soll.

Probieren. Wenn's fehlschlägt, dann überlege, woran es gescheitert ist.

Avatar von 107 k 🚀

Ein anderes Problem?

Stell deine Frage

Willkommen bei der Mathelounge! Stell deine Frage einfach und kostenlos

x
Made by a lovely community