MATHEMATISCHES INSTITUT DER UNIVERSITÄT MÜNCHEN Dr. W. Spann, G. Kleen WS 2022/2023

Programmieren II für Studierende der Mathematik

Aufgabe 6

Die Diedergruppe D_{5} der Ordnung 10 ist die Gruppe der ebenen Isometrien eines regelmäßigen Fünfecks bzgl. Hintereinanderausführung der Abbildungen. Sie wird durch die Drehung um 72^{∘} um den Mittelpunkt (Bez. a) und die Spiegelung an einer Symmetrieachse des Fünfecks (Bez. b) erzeugt. e bezeichne die identische Isometrie und stellt das neutrale Element der Gruppe dar. Wegen a^{5} = b^{2} = e und ba = a^{4}b ergibt sich für die Elemente von D_{5} = {d_{0}, …, d_{9}} mit d_{i} = a^{i} und d_{i+5} = a^{i}b (i = 0, …, 4) die nicht kommutative Gruppenverknüpfung

d_{i} ∘ d_{j} = \{ \begin{matrix}d_{r(i+j)} & 0 ≤ i ≤ & 4, & 0 ≤ j ≤ & 4 \\ d_{5+r(i+j)} & 0 ≤ i ≤ & 4, & 5 ≤ j ≤ & 9 \\ d_{5+r(i−j)} & 5 ≤ i ≤ & 9, & 0 ≤ j ≤ & 4 \\ d_{r(i−j)} & 5 ≤ i ≤ & 9, & 5 ≤ j ≤ & 9 \end{matrix}

mit r(k) ∈ {0, …, 4} und r(k) ≡ k mod 5. Zusammen mit einer geeigneten Permutation π von 0, 1, …, 9 , die

d_{i} ∘ d_{π(j)} ≠ d_{j} ∘ d_{π(i)} (i, j = 0, …, 9, i ≠ j)

erfüllt, werden endliche Dezimalziffernfolgen z_{1}z_{2} … z_{K} betrachtet, die

d_{π(z_{1})} ∘ d_{π^{2}(z_{2})} ∘ ⋯ ∘ d_{π^{K−1}(z_{K−1})} ∘ d_{z_{K}} = e

erfüllen. z_{K} dient dabei als Prüfziffer, mit der sich einzelne Ziffernfehler und einzelne Vertauschungen aufeinanderfolgender Ziffern (mit Ausnahme evtl. der beiden letzten) erkennen lassen.

Die Deutsche Bundesbank setzte dieses Verfahren (mit K = 11) für die aus 11 Zeichen bestehenden Kennungen auf ihren 1991 − 2001 ausgegebenen DM-Banknoten^{1} ein. Die Großbuchstaben A, D, G, K, L, N, S, U, Y, Z werden jeweils durch die Ziffern 0, 1, …, 9 ersetzt und als Permutation wird

\begin{matrix}i & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 \\ π(i) & 1 & 5 & 7 & 6 & 2 & 8 & 3 & 0 & 9 & 4 \end{matrix}

verwendet.

Benutzen Sie für die Zuordnung der eingelesenen Zeichen zu Ziffern möglichst einen assoziativen

Vektor (map<char,int>).

Bestimmen Sie die Prüfziffer (11. Zeichen) mit einem Programm durch Berechnung von d := d_{π(z_{1})} ∘ ⋯ ∘ d_{π^{10}(z_{10})} und Lösen der Gleichung d ∘ d_{z_{11}} = e. Auszugeben sind die eingelesenen Zeichenketten und die Zeichenketten mit Prüfziffer. Für die Eingabe sollen Klein– und Großbuchstaben zulässig sein, in der Ausgabe sollen nur Großbuchstaben erscheinen.

Rechnen Sie folgende Beispiele:

(a) dd3205068a  (b) dn5129171y  (c) DL3565627D  (d) da1530819L.

Bearbeitungszeitraum: bis Donnerstag, 21.12.2022, 16^{00}

1Abbildungen dieser vierten Banknotenserie ( ”BBK III“) mit Seriennummern finden Sie unter http://de.wikipedia.org/wiki/Bargeld der Deutschen Mark