Divide and conquer

Wissenschaft Informatik
#1

hallo, vielleicht könnt ihr mir bei folgender aufgabe helfen, habe da keine idee und vor allem keine mit „divide and conquer“…

Im Nachlas seiner mutter findet uhr sohn n briefe und gedichte, die frau galt als dichtergenie, die aber zu lebzeiten nichts veröffentlichte…
ein verlag ist an der veröffentlichung interessiert, allerdings stammen offensichtlich nicht alle der n texte aus derselben feder. man einigt sichd arauf die texte zu veröffentlichen wenn mehr als n/2 texte vond erselben autorin stammen.
ein handschriftenexperte, der immer nur 2 der texte gleichzeitig auf die handschrift überprüfen kann wird mit der aufgabe vertraut. offensichtlich
reichen (n über 2) vergleiche aus, um zu entscheiden ob mehr als n/2 der texte von derselben autorin stammen.
der experte erkennt aber, dass er mit weniger vergleichen auskommt.

es soll nun ein algo angegebenw erden der in O(n log n) vergleichen entscheidet, ob mehr als n/2 der n texte von derselben person stammt.
ein vergleich kann immer nur zwischen 2 texten stattfinden und entweder übereinstimmung attestiert oder das gegenteil. die entscheidung ist immer korrekt.

vielleicht steigt jemand genau durch. bis denn.

#2

Moien

hallo, vielleicht könnt ihr mir bei folgender aufgabe helfen,
habe da keine idee und vor allem keine mit „divide and
conquer“…

Na sich macht man ja keine Hausaufgaben hier … aber eine Kurzfassung der Aufgabenstellung sollte hier schon helfen.

Im Nachlas seiner mutter findet uhr sohn n briefe und
gedichte, die frau galt als dichtergenie, die aber zu
lebzeiten nichts veröffentlichte…
ein verlag ist an der veröffentlichung interessiert,

Einzige Information bis hier: es gibt n Briefe.

allerdings stammen offensichtlich nicht alle der n texte aus
derselben feder. man einigt sichd arauf die texte zu
veröffentlichen wenn mehr als n/2 texte vond erselben autorin
stammen.

Frage: sind 50% von der gleichen Person ?

ein handschriftenexperte, der immer nur 2 der texte
gleichzeitig auf die handschrift überprüfen kann wird mit der
aufgabe vertraut.

Man kann nur Vergleiche zwischen 2 Breifen anstellen.

offensichtlich
reichen (n über 2) vergleiche aus, um zu entscheiden ob mehr
als n/2 der texte von derselben autorin stammen.

Wenn man doof rangeht reichen n^2 Vergleiche aus.

Tipp: den Algo solltest du mal ganz aufschreiben und mit 10 Briefen durchspielen.

es soll nun ein algo angegebenw erden der in O(n log n)
vergleichen entscheidet, ob mehr als n/2 der n texte von
derselben person stammt.

Es ist wurscht ob man Text1 mit Text2 vergleicht oder Text2 mit Text1. Wenn man den n^2 Algo durchspielt macht man aber T1 T2 und T2 T1. Mit dem Punkt kann man die Laufzeit auf n log(n) bringen.

cu

#3

Morsche

Moien

offensichtlich
reichen (n über 2) vergleiche aus, um zu entscheiden ob mehr
als n/2 der texte von derselben autorin stammen.

Wenn man doof rangeht reichen n^2 Vergleiche aus.

Sie schreiben aber (n über 2)

Es ist wurscht ob man Text1 mit Text2 vergleicht oder Text2
mit Text1. Wenn man den n^2 Algo durchspielt macht man aber T1
T2 und T2 T1. Mit dem Punkt kann man die
Laufzeit auf n log(n) bringen.

Ne, aber wenn man noch dazu nimmt, dass man keinen Brief mit sich selbst vergleichen muss kommt man gerade auf die (n über 2) die oben genannt wurden.

Ich weiß keinen Algorithmus, aber ich hab eine Idee und da es eine Hausaufgabe ist, passt das ja :smile:

Mein prinzipieller Ansatz wäre: Wenn du zwei Dokumente verglichen hast, und festgestellt hast, dass sie vom gleichen Autor kommen, brauchst du alle anderen nur noch mit einem der beiden Dokumente vergleichen.

Jens

#4

Hallo Fragewurm,

es soll nun ein algo angegebenw erden der in O(n log n)
vergleichen entscheidet, ob mehr als n/2 der n texte von
derselben person stammt.
ein vergleich kann immer nur zwischen 2 texten stattfinden und
entweder übereinstimmung attestiert oder das gegenteil. die
entscheidung ist immer korrekt.

vielleicht steigt jemand genau durch. bis denn.

Also der erste doofe Ansatz wäre:

Brief #1 mit #2 vergleichen.
Sind #1 und #2 gleich, kommt #2 zu #1 auf den Haufen
Sind #1 und #2 ungleich kommt #2 auf Haufen 2.

Das wäre mit n-1 Vergleichen zu schaffen.

Wenn abs(Haufen1-Haufen2)>RestlicheBriefe ist, kann man aber schon abbrechen.

MfG Peter(TOO)

#5

Na, denn dividieren wir mal …

Erstmal für gerade n.

Teile die n Dokumente in n/2 Paare. Wenn mehr als n/2 Dokumente ‚gleich‘ (i.S. von ‚gleiche Handschrift‘) sind, muß wenigstens ein gleiches Paar dabei sein. Ungleiche Paare werden auf einen Haufen beiseitegelegt, gleiche Paare legst Du getrennt auf die andere Seite.

Im Haufen der ungleichen Paare kann die ursprüngliche Bedingung (mehr als die Hälfte gleich) nicht erfüllt sein. Wenn sie also für die Gesamtheit erfüllt ist, dann auch für die Menge der gefundenen gleichen Paare. Dort müßte mehr als die Hälfte aller Paare vom gleichen Autor stammen. Die Bedingung bleibt erfüllt (bzw. bleibt unerfüllt), wenn Du nur eine Karte von jedem gleichen Paar nimmst.

Damit hast Du maximal noch n/2 Karten, für die Du gleiche Bedingung wie vorher überprüfen mußt. Also hast Du spätesten nach [wieviel?] Schritten nur noch ein Dokument, von dem Du weißt: wenn eine Mehrheit der Dokumente vom gleichen Autor ist, dann gehört dieses dazu. Ob es tatsächlich die Mehrheit ist, kann mit n-1 Vergleichen geprüft werden.

Das der Algorithmus in O(n log(n)) liegt, kannst Du jetzt sicherlich zeigen.

Der Algorithmus liegt übrigens sogar in O(n) [warum?]

Wie Du mit ungeraden n umgehst, kriegst Du sicherlich auch noch 'raus.

Gruß,
Ralf

P.S.: Du darfst auch mal 'ne Rückmeldung geben …