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