Barcodes (Kombinatorik)

Neue Frage »

Gast11022013 Auf diesen Beitrag antworten »
Barcodes (Kombinatorik)
Meine Frage:
Hallo, ich verlinke mal diese Aufgabe:

http://mo.mathematik.uni-stuttgart.de/inhalt/interaufg/interaufg94/

[Ich hoffe, das ist okay, weil dort u.a. ein Bild dargestellt ist, das ich hier nicht darstellen könnte.]


Irgendwie komme ich schon bei a) nicht auf die Lösung.

Meine Ideen:
a) Von was soll man denn hier ausgehen? Von dem Bild, also 3 dünnen Lücken, 1 dicken Lücke, 3 dünnen Streifen und 2 dicken Streifen? Oder einfach nur von 5 Streifen und 4 Lücken?

Ich denke mal Letzteres.

Davon gehe ich jetzt mal aus.

Wenn am Anfang und am Ende jeweils ein Strich stehen soll, so gibt es dafür meines Erachtens schonmal Möglichkeiten.

Jetzt müsste man noch irgendwie herausfinden, auf vielen Möglichkeiten, man die übrigen 3 Striche und 4 Lücken anordnen kann.

Sind das Möglichkeiten?
Gast11022013 Auf diesen Beitrag antworten »
RE: Barcodes (Kombinatorik)
Achso, vielleicht ist es so gemeint, daß man alle Fälle betrachten soll, die es nur überhaupt bei 5 Strichen und 4 Lücken geben kann??

Also:

Striche:

5 dicke - 0 dünne
4 dicke - 1 dünner
3 dicke - 2 dünne
2 dicke - 3 dünne
1 dicker - 4 dünne
0 dicke - 5 dünne

Lücken:

4 dicke - 0 dünne
3 dicke - 1 dünne
2 dicke - 2 dünne
1 dicke - 3 dünne
0 dicke - 4 dünne


Und jetzt jede Variante aus "Strichen" mit jeder aus "Lücken" "kreuzen" und jeweils die Möglichkeiten ausrechnen?
René Gruber Auf diesen Beitrag antworten »

Offenbar ist das ganze ja so gemeint, dass sowohl Striche als auch Lücken eine Breite haben, die ganzzahliges Vielfaches einer gewissen Grundbreite sind. Diese Information fehlt in der Aufgabenstellung ebenso wie die, wieviele "Grundbreiten" für den Code (5 Striche + 4 Lücken) insgesamt zur Verfügung stehen. Soll man das alles der Skizze entnehmen? Nicht mal das steht da, wenn das der Fall sein sollte. Insgesamt eine lausig gestellte Aufgabe - such dir lieber eine andere. unglücklich

Dass die Breite der Striche und Lücken "vollkommen frei" ist, macht wenig Sinn: Denn dann lautet die Antwort bei 1.) einfach , und der Barcode kann beliebig große Ausmaße annehmen - alles irgendwie sehr praxisfern. unglücklich
Gast11022013 Auf diesen Beitrag antworten »

Okay, dann suche ich mir aus den Aufgaben dort mal eine andere, in der Hoffnung, dass sie besser gestellt sind!

Eventuell frage ich wieder hier dann nach, natürlich in einem neuen Thread.
Gast11022013 Auf diesen Beitrag antworten »

Ist meine Poker-Aufgabe denn wenigstens einigermaßen korrekt? Die stammt auch von der Seite.

Bilder beim Poker (Kombinatorik)
René Gruber Auf diesen Beitrag antworten »

Ich hab's mir nochmal durchgelesen: Sieht so aus, als gibt es nur Striche und Lücken der Breiten 1 und 2. Ok, in dem Fall ist es natürlich lösbar.
 
 
Gast11022013 Auf diesen Beitrag antworten »

Wie geht man denn dann an die Aufgabe ran?

Ich sehe nämlich dann immer noch nicht, wie sie lösbar ist. unglücklich
René Gruber Auf diesen Beitrag antworten »

Fangen wir mit 1. an: Jeder der 9 Striche oder Lücken kann Breite 1 oder 2 haben, d.h. jeweils zwei Möglichkeiten, voneinander frei wählbar. Macht Möglichkeiten...
Gast11022013 Auf diesen Beitrag antworten »

Hm, die Lösung stimmt, aber ich verstehe sie nicht.

Am Anfang und Ende soll ein Strich sein, wo ist zum Beispiel das berücksichtigt?
Und die ganzen Anordungen, die man machen kann...?
René Gruber Auf diesen Beitrag antworten »

Zitat:
Original von Dennis2010
Am Anfang und Ende soll ein Strich sein, wo ist zum Beispiel das berücksichtigt?

Es sind 9 Segmente, die die immer gleiche Aufeinanderfolge haben: S L S L S L S L S

Da gibt es nichts extra zu berücksichtigen, das ist schon laut Konstruktion so! Das einzige, was variiert wird, ist die Breite der einzelnen Segmente (jeweils 1 oder 2).
Gast11022013 Auf diesen Beitrag antworten »

Achso!!!

Ich dachte die ganze Zeit, daß zum Beispiel auch zwei Striche hintereinander folgen können!

Wenn es immer SLSLSLSLS ist, dann verstehe ich das. Sorry.


Woher entnimmt man diese Info aus der Aufgabe?
René Gruber Auf diesen Beitrag antworten »

Zitat:
Original von Dennis2010
Woher entnimmt man diese Info aus der Aufgabe?

Der Beschreibung

Zitat:
Ein Zeichen wird dabei durch eine Folge von schmalen oder breiten Strichen und Lücken, die mit einem Strich beginnt und endet, dargestellt.

unter Berücksichtigung des GMV: Zwei schmale Striche direkt nebeneinander sind von einem breiten Strich durch den Scanner nicht unterscheidbar. Und zwei breite Striche (oder ein breiter und ein schmaler) direkt nebeneinander ergeben einen überbreiten, d.h. überhaupt nicht erlaubten Strich. Augenzwinkern
Gast11022013 Auf diesen Beitrag antworten »

Wenn ich den Code mit einem dünnen Strich beginnen lasse, kann danach kein dicker Strich kommen, das verstehe ich.

Wieso soll man nicht aber einen weiteren dünnen Strich nehmen können, man hätte dann halt einen dicken Strich...
René Gruber Auf diesen Beitrag antworten »

Nochmal: Wie soll der dekodierende Scanner einen breiten von zwei aneinandergeklatschten schmalen Streifen unterscheiden? Am Ende soll doch ein klar und eindeutig dekodierter Barcode stehen!!!
Gast11022013 Auf diesen Beitrag antworten »

Zu 3.)

Es sollen die Möglichkeiten mit höchstens 3 breiten Streifen betrachtet werden.
Das bedeutet für mich: In Betracht kommen diejenigen Codes mit 0, 1, 2 und 3 breiten Strichen.

I. 0 breite Striche

Das bedeutet doch für den Strich am Anfang 1 Möglichkeit, für die darauf folgende Lücke 2 Möglichkeiten, dann wieder ein Strich mit 1 Möglichkeit usw.

Sodaß ich hier auf Möglichkeiten komme.


II. 1 breiter Strich

Die Striche nehmen ja die Positionen 1, 3, 5, 7, 9 ein.
Der eine breite Strich, der vorkommen soll, kann also an Stelle 1, 3, 5, 7 oder 9 stehen, das sind schon 5 Möglichkeiten. Dazu kommen wieder Möglichkeiten, also insgesamt 80.

III. 2 breite Striche

IV. 3 breite Striche


Bei III und IV. weiß ich leider nicht weiter.



Edit:

Bei III. und IV. habe ich jeweils Möglichkeiten ermittelt.



Insgesamt sind's dann 416 Möglichkeiten.

Stimmt, sagt der Link. Tanzen
René Gruber Auf diesen Beitrag antworten »

Zitat:
Original von Dennis2010Bei III. und IV. habe ich jeweils Möglichkeiten ermittelt.

Ist korrekt. Obwohl es bei IV. transparenter aussieht, wenn man es als schreibt. Insgesamt also

.


P.S.: Schon eine Idee zu 2.) ? Augenzwinkern
Gast11022013 Auf diesen Beitrag antworten »
RE: Barcodes (Kombinatorik)
Noch habe ich keine rechte Idee zu 2.), weil ich nicht ganz verstehe, was dort mit "Vertauschung der Reihenfolge" gemeint ist.
René Gruber Auf diesen Beitrag antworten »

Na den Barcode von hinten nach vorn lesen.
Gast11022013 Auf diesen Beitrag antworten »

Kannst Du mir vllt. ein Beispiel für zwei Codes geben, die durch Vertauschung ineinander übergehen? Vllt. kann ichs mir dann besser vorstellen.

Edit:

Achso, ich glaube, ich habe das schon verstanden:

Beispiel:

dicker Strich - dünne Lücke - dünner Strich - dicke Lücke - dünner Strich - dünne Lücke - dünner Strich - dünne Lücke - dünner Strich


Dann wird nicht gesondert gezählt:

dünner Strich - dünne Lücke - dünner Strich - dünne Lücke - dünner Strich - dicke Lücke - dünner Strich - dünne Lücke - dicker Strich


Hm, wie ich das jetzt rechnerisch umsetze, weiß ich jedoch noch nicht.
René Gruber Auf diesen Beitrag antworten »

Wichtig ist die Frage, wie viele der 512 Codes aus 1.) symmetrisch sind, d.h. durch die hier diskutierte Vertauschung in sich selbst (!) übergehen. Mit Hilfe dieser Anzahl lässt sich dann auch die in 2.) gesuchte Anzahl bestimmen (wie?).
Gast11022013 Auf diesen Beitrag antworten »

In sich selbst gehen doch diejenigen Codes über, die an den Stellen 1-4 und 6-9 "spiegelverkehrt" angeordnet sind.

Hm, ist glaube ich komisch ausgedrückt.
René Gruber Auf diesen Beitrag antworten »

Doch, ist schon richtig.
Gast11022013 Auf diesen Beitrag antworten »

Jetzt überlege ich gerade, wie man berechnen kann, wieviele das bloß sind.

Wenn man das wüsste, könnte man diese Anzahl vermutlich von 512 subtrahieren und hätte die gesuchte Anzahl.


verwirrt
René Gruber Auf diesen Beitrag antworten »

Nein, das ist es (noch) nicht:

Wir haben symmetrische Codes (den genauen Wert von s musst du noch berechnen), und wir haben die restlichen unsymmetrischen Codes, z.B. den hier

Zitat:
Original von Dennis2010
dicker Strich - dünne Lücke - dünner Strich - dicke Lücke - dünner Strich - dünne Lücke - dünner Strich - dünne Lücke - dünner Strich

Diese unsymmetrischen Codes lassen sich jeweils zu Paaren zusammenfassen, jeweils mit ihrem Spiegelbild, hier ist das

Zitat:
Original von Dennis2010
dünner Strich - dünne Lücke - dünner Strich - dünne Lücke - dünner Strich - dicke Lücke - dünner Strich - dünne Lücke - dicker Strich

Von jedem dieser Paare darfst du für 2.) nur einen Code zählen, d.h. insgesamt dermaßen unterscheidbare Codes.

Bei den symmetrischen Codes ist das anders: Da zählt für 2.) jeder dieser Codes, so dass du summa summarum



Codes als Antwort zu 2.) hast. Bleibt jetzt nur noch die Berechnung von , und die ist auch nicht so schwer.
Gast11022013 Auf diesen Beitrag antworten »

Also zunächst können an 5. Stelle ein dicker oder ein dünner Strich stehen.

Das wäre also schonmal der Faktor 2.


Auf den Rest komme ich nicht.
René Gruber Auf diesen Beitrag antworten »

Zitat:
Original von Dennis2010
Also zunächst können an 5. Stelle ein dicker oder ein dünner Strich stehen.

Das wäre also schonmal der Faktor 2.

Das ist richtig.

Wenn du 1.-4. festlegst, dann stehen 6.-9. aufgrund der Spieglebedingung automatisch fest. Und dieses 1.-4. kannst du aber ebenso frei festlegen, wie bereits 5.

Wie groß ist also ?
Gast11022013 Auf diesen Beitrag antworten »

Ah, ich hab schon!

s ist 32.



Die Lösung ist also 272.



Ich danke Dir sehr!

Gott
Gast11022013 Auf diesen Beitrag antworten »

Ich finde diese Übungsaufgaben echt gut.

Sie sind (für mich) anspruchsvoll und daran lerne ich es besser als an zu einfachen Aufgaben. Und wenn man dann noch so tolle Hilfe hat, kann man daran nur gewinnen!
René Gruber Auf diesen Beitrag antworten »

Ja genau. Freude

Dieses 2.) spielt innerhalb der elementaren Kombinatorik schon auf eine etwas anspruchsvollere Thematik an - Stichwort Burnside-Lemma. Allerdings ist es für diese Aufgabe (noch) nicht nötig, sich da einzuarbeiten. Augenzwinkern
Gast11022013 Auf diesen Beitrag antworten »

Burnside? Vielleicht sage ich da jetzt ganz was Blödes, aber diesen Namen erinnere ich aus einer Algebra-Vorlesung, da ging es allerdings (sofern, ich das recht erinnere) um Gruppenoperationen. Vielleicht hängt das ja damit zusammen?
René Gruber Auf diesen Beitrag antworten »

Ja, gut möglich.
derfrederic Auf diesen Beitrag antworten »

Keiner mehr an den Aufgabenteil 4 interessiert ? Befasse mich gerade auch mit der Aufgabe und stehe da (leicht) auf dem Schlauch...

Gefragt ist wieviel Striche und Lücken man mindestens braucht wenn man alle Ziffern und Zahlen (0...9 , A.....Z), also 26 + 10 = 36 Elemente darstellen will UND Zeichen nicht voneinander unterschieden werden welche durch Vertauschen der Reihenfolge ineinander übergehen...

Muss sagen, dass mich die Fragestellung schonmal ziemlich demotiviert.

Hoffe demnach auf etwas Unterstützung, kleine Tipps oder etwas Denkanstoß und bedanke mich schonmal.
Neue Frage »
Antworten »



Verwandte Themen

Die Beliebtesten »
Die Größten »
Die Neuesten »