Barcodes (Kombinatorik) |
23.09.2011, 14:42 | Gast11022013 | Auf diesen Beitrag antworten » | ||||
Barcodes (Kombinatorik) 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? |
||||||
23.09.2011, 15:26 | 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? |
||||||
23.09.2011, 15:56 | 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. 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. |
||||||
23.09.2011, 15:57 | 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. |
||||||
23.09.2011, 16:01 | Gast11022013 | Auf diesen Beitrag antworten » | ||||
Ist meine Poker-Aufgabe denn wenigstens einigermaßen korrekt? Die stammt auch von der Seite. Bilder beim Poker (Kombinatorik) |
||||||
23.09.2011, 16:05 | 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. |
||||||
Anzeige | ||||||
|
||||||
23.09.2011, 16:06 | 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. |
||||||
23.09.2011, 16:11 | 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... |
||||||
23.09.2011, 16:25 | 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...? |
||||||
23.09.2011, 16:39 | René Gruber | Auf diesen Beitrag antworten » | ||||
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). |
||||||
23.09.2011, 16:43 | 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? |
||||||
23.09.2011, 16:49 | René Gruber | Auf diesen Beitrag antworten » | ||||
Der Beschreibung
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. |
||||||
23.09.2011, 17:04 | 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... |
||||||
23.09.2011, 17:07 | 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!!! |
||||||
23.09.2011, 18:10 | 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. |
||||||
23.09.2011, 21:00 | René Gruber | Auf diesen Beitrag antworten » | ||||
Ist korrekt. Obwohl es bei IV. transparenter aussieht, wenn man es als schreibt. Insgesamt also . P.S.: Schon eine Idee zu 2.) ? |
||||||
23.09.2011, 21:24 | 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. |
||||||
23.09.2011, 21:29 | René Gruber | Auf diesen Beitrag antworten » | ||||
Na den Barcode von hinten nach vorn lesen. |
||||||
23.09.2011, 21:41 | 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. |
||||||
23.09.2011, 23:16 | 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?). |
||||||
23.09.2011, 23:19 | 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. |
||||||
23.09.2011, 23:22 | René Gruber | Auf diesen Beitrag antworten » | ||||
Doch, ist schon richtig. |
||||||
23.09.2011, 23:23 | 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. |
||||||
23.09.2011, 23:31 | 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
Diese unsymmetrischen Codes lassen sich jeweils zu Paaren zusammenfassen, jeweils mit ihrem Spiegelbild, hier ist das
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. |
||||||
23.09.2011, 23:31 | 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. |
||||||
23.09.2011, 23:36 | René Gruber | Auf diesen Beitrag antworten » | ||||
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 ? |
||||||
23.09.2011, 23:36 | Gast11022013 | Auf diesen Beitrag antworten » | ||||
Ah, ich hab schon! s ist 32. Die Lösung ist also 272. Ich danke Dir sehr! |
||||||
23.09.2011, 23:40 | 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! |
||||||
23.09.2011, 23:41 | René Gruber | Auf diesen Beitrag antworten » | ||||
Ja genau. 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. |
||||||
23.09.2011, 23:46 | 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? |
||||||
23.09.2011, 23:52 | René Gruber | Auf diesen Beitrag antworten » | ||||
Ja, gut möglich. |
||||||
07.01.2012, 20:08 | 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. |
|
Verwandte Themen
Die Beliebtesten » |
|
Die Größten » |
|
Die Neuesten » |
|