Links
Transcrição
Links
Stricken macht Spaß: ein rekursiver Pulli Georg Bremer 1. Mai 2009 1 Stricken • Zur Vereinfachung wird im Folgenden nur das Flachstricken betrachtet. • Es gibt zwei Arten von Maschen, rechte und linke. • Gestrickt wird mit einer Nadel je Hand. – Links liegt das Strickgut und mit der rechten wird angestrickt. – Wenn die Reihe fertig ist, liegt das Strickgut komplett rechts und die Nadeln werden getauscht. 2 Strickmuster Klassisch werden Strickmuster durch ein Strickdiagramm: | | | | | | | | | | | | | | | | | | | | - - | | | | | | | | | | | | | | | | - - | | | | | | | | | | | | | | | | | | | | und verbal : • Reihe 1: * 2 rechte Maschen, 2 linke Maschen; wiederhole von *; die letzten drei Maschen rechts stricken. • wiederhole Reihe 1. beschrieben. • n × m-Matrix beschreibt die Strickreihen und Maschen 1 • Die Einträgen sind aus {|, -}. • | sind rechte und - linke Maschen. | | Die häufigsten Muster sind glatt rechts und dessen Rückseite glatt links. - - | | | | | | | - - - - - | | | | | | | - - - - Strickdiagramme • Ungerade Zeilen beschreiben die Vorderseite, • gerade die Rückseite des Musters.1 • r bezeichnet glatt rechts, l glatt links. • Aus - | | - | | | | - | | - - dem - | | - | | | | - | | - - Strickdiagramm links wird dann das Muster rechts. | | | | r r r r l l l l r r r r l l l l - - - | | | | r r r r l l l l - - - r r r r l l l l l l l l r r r r - - - | | | | l l l l r r r r - - - l l l l r r r r l l l l r r r r | | | | Knittel • Ein Texturelement, wie es auf dem Muster zu sehen ist, wird definiert als Knittel 2 . • Ein Knittel kann je nach Reihe durch eine rechte oder eine linke Masche erzeugt werden. 1 beim 2 Von Flachstricken, beim Rundstricken sind beide gleich. Knitting Element, in Anlehnung an Pixel. 2 • Es können somit leicht Muster erzeugt werden, indem nur die sichtbaren Knittel betrachtet werden und anschließend durch invertieren jeder zweiten Reihe das Strickdiagramm erzeugt wird. 3 Grammatik Eine Reihe des Strickmusters | | | | | | | | | | - - | | | | | | | | - - | | | | | | | | | | kann durch folgende Produktionsregel beschrieben werden: R ::= | | | R - - | | was der Sprache ∗ L(R) = | | | (- - | |) entspricht. Für einen vollständigen Pullover müsste die Grammatik auf zwei Dimensionen erweitert werden. 4 Algorithmisches Stricken Algorithmisches Stricken Im Folgenden werden zwei Strickmuster durch rekursive Algorithmen beschrieben werden, zum einen ein Schachbrettmuster und zum anderen der Sierpinski-Teppich. 4.1 Schachbrettmuster • Als Muster wird eine (n × n)-Matrix A mit n = 2k an der Stelle ax,y gefüllt. • Die Größe des Schachbrettmusters (je vier Felder) wird durch den Parameter d angegeben. • A wird mit glatt rechten Knitteln (r) initialisiert. • Durch ändern des Parameters d sind beliebige Schachbrettgrößen möglich. 3 Schachbrett(A, n, d, x, y) if n == d then for i = 0 to d/2 − 1 do for j = 0 to d/2 − 1 do ai+d/2+x, j+y ← l ai+x, j+d/2+y ← l else for k = 0 to 3 do i←k/2 j ← k mod 2 Schachbrett(A, n/2, d, x + i ∗ n/2, y + j ∗ n/2) 4.2 Sierpinski-Teppich Ein Quadrat wird in 9 Teile unterteilt und das mittlere entfernt, mit den verbliebenden Quadraten wird genauso fortgefahren. Sierpinski-Teppich, die ersten fünf Iterationen. [de.wikipedia.org] • Matrix A der Dimension n = 3k wird wieder mit glatt rechten Knitteln r initialisiert. • Der Parameter d beschreibt die Rekursionstiefe des Fraktals. 5 Komplexität Kolmogorow-Komplexität Die Kolmogorow-Komplexität eines Wortes ist definiert als die Anzahl der Bits, die zu dessen Beschreibung notwendig ist. 4 Sierpinski(A, n, d, x, y) if d == 1 then for i = d/3 to 2 ∗ d/3 − 1 do for j = d/3 to 2 ∗ d/3 − 1 do ai+x, j+y ← l else for i = n/3 to 2 ∗ n/3 − 1 do for j = n/3 to 2 ∗ n/3 − 1 do ai+x, j+y ← l for k = 0 to 8 do if k 6= 4 then i←k/3 j ← k mod 3 Sierpinski(A,n/3,d − 1,x + i ∗ n/3,y + j ∗ n/3) Strickkomplexität Die Strickkomplexität eines Musters ist die Anzahl der Bits, die zur Beschreibung des dazugehörigen Strickdiagramms benötigt wird. Behauptung Die untere Schranke für die Strickkomplexität eines n × mMusters ist Ω(log n + log m). Behauptung Die vorgestellten rekursiven Muster haben die Komplexität Θ(log n). Beweis • m=n • Algorithmus mit konstanter Anzahl an Anweisungen • Eingaben sind alle nach oben beschränkt durch n 6 Strickmusteralgebra Algebraische Kombination von Mustern • Wir nehmen an, in einem Muster kommen nur drei unterschiedliche Arten von Knitteln vor. • Dadurch können diese mit Elementen aus dem F3 dargestellt werden. • Durch einfache Kombinationen von Knittelmatrizen miteinander durch Operationen des Rings können so neue Muster erzeugt werden. 5 Kombination von Mustern durch Multiplikation: Kombination mit Operationsmatrix: mit der Operationsmatrix 7 ×mod3 +mod3 +mod3 ×mod3 Zusammenfassung Zusammenfassung Durch die informatische Sicht auf die Welt des Strickens werden völlig ungeahnte Möglichkeiten eröffnet, sowohl für Strickkurse für Informatiker als auch für Informatikkurse für strickende Hausfrauen. Literatur [1] Anna Bernasconi , Chiara Bodei , and Linda Pagli Knitting for fun: a recursive sweater. Fun with Algorithms, 4th International Conference, FUN 2007, Castiglioncello, Italy, June 3-5, 2007, Proceedings, pp. 53-65 [2] The Home of Mathematical Knitting http://www.toroidalsnark.net/mathknit.html 6