www.vorhilfe.de
Vorhilfe

Kostenlose Kommunikationsplattform für gegenseitige Hilfestellungen.
Hallo Gast!einloggen | registrieren ]
Startseite · Forum · Wissen · Kurse · Mitglieder · Team · Impressum
Forenbaum
^ Forenbaum
Status Vorhilfe
  Status Geisteswiss.
    Status Erdkunde
    Status Geschichte
    Status Jura
    Status Musik/Kunst
    Status Pädagogik
    Status Philosophie
    Status Politik/Wirtschaft
    Status Psychologie
    Status Religion
    Status Sozialwissenschaften
  Status Informatik
    Status Schule
    Status Hochschule
    Status Info-Training
    Status Wettbewerbe
    Status Praxis
    Status Internes IR
  Status Ingenieurwiss.
    Status Bauingenieurwesen
    Status Elektrotechnik
    Status Maschinenbau
    Status Materialwissenschaft
    Status Regelungstechnik
    Status Signaltheorie
    Status Sonstiges
    Status Technik
  Status Mathe
    Status Schulmathe
    Status Hochschulmathe
    Status Mathe-Vorkurse
    Status Mathe-Software
  Status Naturwiss.
    Status Astronomie
    Status Biologie
    Status Chemie
    Status Geowissenschaften
    Status Medizin
    Status Physik
    Status Sport
  Status Sonstiges / Diverses
  Status Sprachen
    Status Deutsch
    Status Englisch
    Status Französisch
    Status Griechisch
    Status Latein
    Status Russisch
    Status Spanisch
    Status Vorkurse
    Status Sonstiges (Sprachen)
  Status Neuerdings
  Status Internes VH
    Status Café VH
    Status Verbesserungen
    Status Benutzerbetreuung
    Status Plenum
    Status Datenbank-Forum
    Status Test-Forum
    Status Fragwürdige Inhalte
    Status VH e.V.

Gezeigt werden alle Foren bis zur Tiefe 2

Navigation
 Startseite...
 Neuerdings beta neu
 Forum...
 vorwissen...
 vorkurse...
 Werkzeuge...
 Nachhilfevermittlung beta...
 Online-Spiele beta
 Suchen
 Verein...
 Impressum
Das Projekt
Server und Internetanbindung werden durch Spenden finanziert.
Organisiert wird das Projekt von unserem Koordinatorenteam.
Hunderte Mitglieder helfen ehrenamtlich in unseren moderierten Foren.
Anbieter der Seite ist der gemeinnützige Verein "Vorhilfe.de e.V.".
Partnerseiten
Dt. Schulen im Ausland: Mathe-Seiten:

Open Source FunktionenplotterFunkyPlot: Kostenloser und quelloffener Funktionenplotter für Linux und andere Betriebssysteme
Forum "Algorithmen und Datenstrukturen" - Das Coin-Weighing-Problem
Das Coin-Weighing-Problem < Algor.+Datenstr. < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
Ansicht: [ geschachtelt ] | ^ Forum "Algorithmen und Datenstrukturen"  | ^^ Alle Foren  | ^ Forenbaum  | Materialien

Das Coin-Weighing-Problem: Frage
Status: (Frage) beantwortet Status 
Datum: 19:59 Di 03.05.2005
Autor: Aly

Hallo zusammen!

Könnte jemand einen Ansatz zur Lösung des folgenden Problems geben?

Gegeben seien N Münzen und eine elektronische Waage.
Es ist nicht bekannt wieviele dieser Münzen unecht sind.
Man weiss aber, dass echte Münzen das Gewicht "A" haben und verfälschte Münzen das Gewicht "B", mit B<A.
Gefragt ist, ob es einen Algorithmus gibt, der ab ein bestimmtes N  im "worst case" weniger als N Wiegeoperationen braucht, um die echten Münzen zu erkennen (Und somit auch die verfälschten), wobei man pro Wiegeoperation eine beliebige Anzahl(<= N) von Münzen nehmen kann.


--------------------------------------------------------------------
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt

        
Bezug
Das Coin-Weighing-Problem: Antwort
Status: (Antwort) fertig Status 
Datum: 23:51 Di 03.05.2005
Autor: Karl_Pech

Hi Aly,

[willkommenvh]

Das Coin-Weighting Problem ist offensichtlich berühmt.
Ich habe []hier etwas dazu gefunden, weiß aber nicht, ob es dir gänzlich weiterhilft.

Grüße
Karl



Bezug
        
Bezug
Das Coin-Weighing-Problem: Lösungsvorschlag
Status: (Mitteilung) Reaktion unnötig Status 
Datum: 18:39 Do 12.05.2005
Autor: michagm1

Hallo,
weißt Du zu Beginn des Lösungsweges wie viele München Du hast? Wenn ja, dann geht folgendes Verfahren

Man z.B. so vorgehen:Nimm die erste Hälte der Münzen und rechne wie folgt:
x=n/2 * Gewicht der Münzen
dann berechne
y =n/2 * Gewicht "A"

wenn x != y dann halbierst du die Menge und prüfst die neue Menge usw.

Dann prüfst du die zweite Hälfte ähnlich

Dieses Verfahren hat einen speziellen Namen. Der fällt mir im Moment nur nicht ein.

Viel Spaß beim probieren.
Gruß
Michae> Hallo zusammen!

>  
> Könnte jemand einen Ansatz zur Lösung des folgenden
> Problems geben?
>  
> Gegeben seien N Münzen und eine elektronische Waage.
>  Es ist nicht bekannt wieviele dieser Münzen unecht sind.
>  Man weiss aber, dass echte Münzen das Gewicht "A" haben
> und verfälschte Münzen das Gewicht "B", mit B<A.
> Gefragt ist, ob es einen Algorithmus gibt, der ab ein
> bestimmtes N  im "worst case" weniger als N
> Wiegeoperationen braucht, um die echten Münzen zu erkennen
> (Und somit auch die verfälschten), wobei man pro
> Wiegeoperation eine beliebige Anzahl(<= N) von Münzen
> nehmen kann.
>  
>
> --------------------------------------------------------------------
>  Ich habe diese Frage in keinem Forum auf anderen
> Internetseiten gestellt


Bezug
                
Bezug
Das Coin-Weighing-Problem: Mitteilung
Status: (Mitteilung) Reaktion unnötig Status 
Datum: 22:26 Do 12.05.2005
Autor: Karl_Pech

Hallo Michael,

[willkommenvh]

> Dieses Verfahren hat einen speziellen Namen. Der fällt mir
> im Moment nur nicht ein.

Nennt sich das nicht "Divide And Conquer"-Verfahren?


Grüße
Karl



Bezug
                
Bezug
Das Coin-Weighing-Problem: Idee
Status: (Mitteilung) Reaktion unnötig Status 
Datum: 23:53 Fr 13.05.2005
Autor: Aly

Hallo :),

Danke für eure Antworten.
Also was die Halbierungsmethode betrifft ist nichts einzuwenden, ausser dass sie nicht garantiert, dass ab einer bestimmten Anzahl von Münzen im Worst-Case mit geringer als N wiegeoperationen auszukommen ist, weil es kann so passieren, dass in jeder gewählten Menge x!=y gilt.

Idee:
Das Problem kann schön vereinfacht dargestellt werden ohne seine Schärfe zu verlieren.
Nämlich man kann o.B.d.A annehmen, dass verfälschte Münzen das Gewicht 0 haben, wogegen die echten das Gewicht 1 bekommen.
Nun reduziert sich das Problem auf die Anzahl der Wiegevorgänge die nötig sind, um diese "Zeichenkette" von Nullen und Einssen zu bestimmen.

Es ist auch nützlich sich Gedanken darüber zu machen, was es bedeuten würde, wenn es tatsächlich einen Algorithmus gibt, die die gewünschte Eigenschaft hat. z.B würde das dann meiner Meinung nach bedeuten, dass man über beliebige Zeichenketten (ab einer bestimmten Länge) nicht alles wissen muss, um diese zu bestimmen.

Grüsse,
Ali

Bezug
        
Bezug
Das Coin-Weighing-Problem: Überlegungen
Status: (Mitteilung) Reaktion unnötig Status 
Datum: 18:22 Fr 20.05.2005
Autor: Zyllyn

mit der elektronischen Waage sehe ich keine Lösung die worst case weniger als N Wiegeversuche braucht ... Dafür garantiert die Teilungsmethode, dass du maximal N Wiegeversuche brauchst.

Der worse case tritt ein, wenn Du gleiche Anzahl echte und unechte Münzen hast. Je größer die Differenz zwischen zwischen den Anzahlen von echten und unechten Münzen, desto weniger Wiegeversuche. --> also indirekt eine Aussage über N :)

NB: wenn du eine Balkenwaage nimmst, und vorraussetzt, das Du mindestens eine echte und mindesten eine unechte Münze hast, wieder ein Teilungsverfahren ansetzt, dann brauchst du auch im worst case nur N-1 Wiegeversuche (allerdings sollte N eine Zweipotenz sein :) )

Bezug
        
Bezug
Das Coin-Weighing-Problem: Antwortversuch
Status: (Antwort) fertig Status 
Datum: 14:51 Fr 03.06.2005
Autor: Becci

In N Versuchen ist das Problem trivial (wiege jede einzelne der N Münzen), aber ich glaube, in N-1 Wiegeversuchen ist es i.A. nicht möglich, das Gewicht jeder einzelnen Münze festzustellen (also ob es A oder B ist).

Begründung:

Wir können über das Gewicht einer bestimmten Münze nur dann etwas aussagen, wenn wir sie schon einmal
- entweder allein
- oder aber NUR mit anderen Münzen desselben Gewichts zusammen gewogen haben.

D.h., dass wir genau das für jede Münze einmal tun müssen, um am Ende über alle "Bescheid zu wissen".

Es bringt uns aber nichts, einzelne Münzen zu wiegen, denn: Dann haben wir N-1 Münzen übrig, deren Gewicht wir nicht kennen, und dürfen nur noch N-2mal wiegen => Dasselbe Problem immer noch.

Also muss ein Algorithmus, der das Problem in N-1 Versuchen löst, dabei  mindestens einmal eine Menge M von [mm] |M| \geq 2 [/mm] Münzen gleichen Gewichts wiegen.

Gibt es einen Algorithmus, der garantiert auf solch eine Menge M stößt und dennoch nur N-1 mal wiegen muss?

Denken wir uns mal den worst-case, d.h. es haben [mm] \bruch{N}{2}[/mm] Gewicht A und der Rest hat Gewicht B (für N ungerade nehme die untere Gaußklammer, d.h. es gibt 1 weniger echte Münzen als falsche).

Wann immer der Algorithmus aus den N Münzen einige (einzelne Münzen bringen ihm ja nix, s.o.) auswählt, um sie zu wiegen, habe er nun "Pech", d.h. für diese Menge von Münzen gilt wieder dass die Hälfte echt ist und die Hälfte unecht.

Dann wird der Alg., egal welche Münzen er genommen hat, immer noch nichts über das Gewicht einer beliebigen Einzelmünze wissen.
Dieses Spielchen kann man jetzt fortführen und sieht, dass unter den worst-case-Voraussetzungen der Alg. jede Münze tatsächlich einzeln berachten muss: Solange eine zweite dabei ist, ist ja nach der Annahme, dass wir "Pech" haben, eine davon schwerer und eine leichter und niemand weiß welche jetzt welche ist...

Damit braucht er auch mindestens N Wiegevorgänge.

(Die erwartete Anzahl Wiegevorgänge für die schon vorgeschlagene Divide-and-Conquer-Methode ist zwar wohl <N, weil der worst case höchst unwahrscheinlich ist. Aber garantieren kann man eben (meiner Meinung nach) nichts besseres als N.)

Hoffe du kannst was damit anfangen

Gruß

Becci

Bezug
                
Bezug
Das Coin-Weighing-Problem: Genaue Untersuchung
Status: (Mitteilung) Reaktion unnötig Status 
Datum: 20:49 Mo 06.06.2005
Autor: Aly

Hallo Becci,

Danke für deine ausführliche Vorführung .
Dein Beweis ist schön. Aber er enthält nur eine Schwachstelle oder zumindest scheint eine Schwachstelle zu enthalten.

Sei superA ein Algorithmus der das Coinweighingproblem positiv löst.

Deine Überlegungen stimmen sicher, wenn man annimmt dass der Algorithmus zur Lösung des Problems vorbestimmt und vordefiniert sein soll, aber es wäre denkbar, dass der Algorithmus sein Verhalten entscheidend verändert je nachdem was das Ergebnis
des Wiegens ist... z.B Wenn der Algorithmus merkt, dass die Hälfte der Münzen echt sind, kann er zu einer bestimmten Aufteilung der Menge aller Münzen in Teilmengen zugreifen, die die Eigenschaft hat, dass mindestens eine dieser Teilmengen weniger echte als verfälschte Münzen hat.
Es wäre sogar denkbar dass man durch eine geeignete Aufteilung mehrere solcher mengen erhält oder dass es ebenfalls durch geeignete Aufteilung einen deutlichen unterschied zwischen der Anzahl echter und verfälschter Münzen in einer Teilmenge entsteht. Wenn man das erreicht dann hat man gewiss weniger als n-Wiegeoperationen durchzuführen.

Es ist hier zu erwähnen dass man theoretisch mithilfe der Entropie der Informationstheorie beweisen kann, dass man nicht mit besser als n/log(n) Wiegeoperationen rechnen kann. Aber man weiss noch nicht, ob man diese untere Schranke tatsächlich erreichen kann.

Also ich denke dass deine Überlegungen reichen nicht, um die Existenz von superA zu verneinen sondern sie reichen um die Existenz aller vorbestimmten Algorithmen die das Problem positiv lösen zu verneinen.

D.h. wir wissen dass wenn es einen solchen Algorithmus gibt dann muss er klug sein.

Was meinst du dazu? und andere auch?  

Gruß

Bezug
                        
Bezug
Das Coin-Weighing-Problem: SuperA?
Status: (Mitteilung) Reaktion unnötig Status 
Datum: 12:35 Mi 15.06.2005
Autor: Becci

>> Sei superA ein Algorithmus der das Coinweighingproblem positiv löst.
>> Deine Überlegungen stimmen sicher, wenn man annimmt dass der Algorithmus zur Lösung des Problems vorbestimmt
>> und vordefiniert sein soll, aber es wäre denkbar, dass der Algorithmus sein Verhalten entscheidend verändert je nachdem was das Ergebnis
>> des Wiegens ist... z.B Wenn der Algorithmus merkt, dass die Hälfte der Münzen echt sind, kann er zu einer bestimmten Aufteilung der Menge aller
>> Münzen in Teilmengen zugreifen, die die Eigenschaft hat, dass mindestens eine dieser Teilmengen weniger echte als verfälschte Münzen hat.

Nun, ich denke eigentlich nicht dass das so ist.
Man könnte es meinen, ja. Aber als ich mir das überlegt habe, bin ich zu folgendem Ergebnis gekommen:

Also sei jetzt der Algorithmus abhängig vom Ergebnis des Wiegens, d.h.
er hat jetzt eine Menge A von Münzen gewogen und weiß: Aha, die Hälfte ist falsch.
(oder für ungerade Anzahl halt untere/obere Gaußklammer)

Er weiß nur leider NICHT: Welche Münzen sind die falschen und welche die richtigen?

Du sagst jetzt, er kann sich die Menge A so in Teilmengen aufteilen, dass er über die Teilmengen weiß:
Eine hat weniger echte als falsche Münzen.

Wie denn? Sagen wir mal, er macht aus A n Teilmengen.
Er kann die Elemente der Teilmengen nur zufällig aus A wählen, weil er keinen Schimmer hat, welche Münze in A wieviel wiegt.

Also holt er meinetwegen zuerst mal m Münzen in die Teilmenge M.
Egal was jetzt m ist, er kann Pech haben (worst case) und hat ausgerechnet wieder (untere Gaußklammer von) m/2 falsche Münzen.
Wenn er das Pech hatte, und das nehmen wir ja an (immer noch worst case),
dann hat er bei der Einteilung der nächsten Menge wieder exakt dasselbe Problem (weil A immer noch gleichverteilt) und so weiter für alle n Teilmengen die er bildet.

D.h., wenn A sicherstellen will, dass irgendwo ein Ungleichgewicht in einer Teilmenge herrscht, dann muss er eine Teilmenge ungerader Kardinalität nehmen -
und auch da ist das Ungleichgewicht  wieder nur genau EINE Münze (im worst case), so dass wir eh nur wieder den in meinem Lösungsvorschlag behandelten Fall haben.

Oder?

Gruß

Becci

Bezug
                        
Bezug
Das Coin-Weighing-Problem: Mitteilung
Status: (Mitteilung) Reaktion unnötig Status 
Datum: 12:45 Mi 15.06.2005
Autor: Zyllyn

ich kann becci nur Zustimmen. Unabhängig davon interessiert mich der Beweis der untere Schranke [mm] \bruch{n}{log(n)}[/mm]
vielleicht versteckt sich ja im Beweis die Idee für unser Wiegeproblem

Zyllyn

Bezug
        
Bezug
Das Coin-Weighing-Problem: Mitteilung
Status: (Mitteilung) Reaktion unnötig Status 
Datum: 13:33 Mi 20.07.2005
Autor: Aly

Hallo Becci,

Ich habe einen Algorithmus gefunden der in allen Fällen mit weniger als n-Wiegeoperationen auskommt.
Es stimmt nicht, dass die Wiegeoperationen uns bei der Bestimmung der einzelnen Münzen überhaupt
nicht helfen. Versuche es mit dem Fall über den du schnell geflogen bist. nämlich den Fall wo die Anzahl der Münzen ungerade ist. Da kann man ein Loch verursachen und es mit grösser werdenden n vergrössen. Ich werde meinen Algorithmus momentan nicht veröffentlichen. ich versuche ihn zu verbessern.
Aber danke für deine Denkanstösse, sie haben mich dazu geführt diesen Algorithmus zu finden.

Grüsse Aly.

Bezug
                
Bezug
Das Coin-Weighing-Problem: Test
Status: (Mitteilung) Reaktion unnötig Status 
Datum: 06:55 So 24.07.2005
Autor: Aly

Hallo Alle,

test

Grüsse Aly.

Bezug
Ansicht: [ geschachtelt ] | ^ Forum "Algorithmen und Datenstrukturen"  | ^^ Alle Foren  | ^ Forenbaum  | Materialien


^ Seitenanfang ^
www.vorhilfe.de