Informatik zum Jahresanfang – SELFHTML-Forum Forum als Ergänzung zum SELFHTML-Wiki und zur Dokumentation SELFHTML https://forum.selfhtml.org/self Informatik zum Jahresanfang Wed, 02 Jan 19 13:14:11 Z https://forum.selfhtml.org/self/2019/jan/2/informatik-zum-jahresanfang/1739779#m1739779 https://forum.selfhtml.org/self/2019/jan/2/informatik-zum-jahresanfang/1739779#m1739779 <p>Das Bild zeigt einen endlichen Automaten, der sich bei der Eingabe einer Ziffernfolge nur dann im Endzustand (dargestellt durch doppelte Linie) befindet, wenn die dadurch eingegebene Zahl durch 2 teilbar ist. (Führende Nullen sollen erlaubt sein.)</p> <p><a href="/images/e1c2c44c-9fbb-44ea-bffc-c2a26744ba2b.jpeg" rel="noopener noreferrer"><img src="/images/e1c2c44c-9fbb-44ea-bffc-c2a26744ba2b.jpeg?size=medium" alt="" loading="lazy"></a></p> <ol> <li>Formal beschrieben ist dieser durch ein Quintupel (<em>S</em>, <em>s</em>₁, <em>Σ</em>, <em>δ</em>, <em>F</em>) mit:<br> <em>S</em> – Menge der Zustände, in dem Fall <em>S</em> = {<em>s</em>₁, <em>s</em>₂}<br> <em>s</em>₁ ∈ <em>S</em> – Startzustand<br> <em>Σ</em> – Menge der Eingabesymbole (Eingabealphabet), in dem Fall <em>Σ</em> = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}<br> <em>δ</em>: <em>S</em> × <em>Σ</em> → <em>S</em> – Zustandsübergangsfunktion, in dem Fall $$\delta(s_i, \sigma) = \begin{cases} s_2, & \text{wenn }\sigma ∈ {0, 2, 4, 6, 8}<br> s_1, & \text{wenn }\sigma ∈ {1, 3, 5, 7, 9} \end{cases}; i ∈ {1, 2}$$<br> <em>F</em> ⊆ <em>S</em> – Menge der Endzustände, in dem Fall <em>F</em> = {<em>s</em>₂}</li> </ol> <p>Die Aufgabe ist, einen endlichen Automaten zu bauen, der sich nur dann in einem Endzustand befindet, wenn die eingegebene Zahl durch 4 teilbar ist. Grafische Darstellung genügt. (Wie oben: führende Nullen sind erlaubt.)</p> <p>LLAP </p> <div class="signature">-- <br> <em>„Wer durch Wissen und Erfahrung der Klügere ist, der sollte nicht nachgeben. Und nicht aufgeben.“</em> —Kurt Weidemann </div> Informatik zum Jahresanfang Wed, 02 Jan 19 13:33:00 Z https://forum.selfhtml.org/self/2019/jan/2/informatik-zum-jahresanfang/1739786#m1739786 https://forum.selfhtml.org/self/2019/jan/2/informatik-zum-jahresanfang/1739786#m1739786 <p>Hallo Gunnar Bittersmann,</p> <blockquote> <p>[Bild gelöscht]</p> </blockquote> <p>Der Startzustand wird durch einen zum Zustand zeigenden Pfeil symbolisiert.</p> <p>Bis demnächst<br> Matthias</p> <div class="signature">-- <br> Pantoffeltierchen haben keine Hobbys. </div> Informatik zum Jahresanfang Thu, 03 Jan 19 00:43:47 Z https://forum.selfhtml.org/self/2019/jan/2/informatik-zum-jahresanfang/1739844#m1739844 https://forum.selfhtml.org/self/2019/jan/2/informatik-zum-jahresanfang/1739844#m1739844 <p>@@Gunnar Bittersmann</p> <blockquote> <p>Das Bild zeigt einen endlichen Automaten, der sich bei der Eingabe einer Ziffernfolge nur dann im Endzustand (dargestellt durch doppelte Linie) befindet, wenn die dadurch eingegebene Zahl durch 2 teilbar ist. (Führende Nullen sollen erlaubt sein.)</p> <p><a href="/images/e1c2c44c-9fbb-44ea-bffc-c2a26744ba2b.jpeg" rel="noopener noreferrer"><img src="/images/e1c2c44c-9fbb-44ea-bffc-c2a26744ba2b.jpeg?size=medium" alt="" loading="lazy"></a></p> </blockquote> <p>Erklärung, wie das zu verstehen ist; am Beispiel von 9876:</p> <p>Der Automat ist anfangs im Zustand <em>s</em>₁; das ist kein Endzustand.</p> <p>Durch Eingabe einer 9 bleibt der Automat im Zustand <em>s</em>₁. Kein Endzustand; 9 ist nicht durch 2 teilbar.</p> <p>Durch Eingabe einer 8 geht der Automat in den Zustand <em>s</em>₂. Das ist ein Endzustand; 98 ist durch 2 teilbar.</p> <p>Durch Eingabe einer 7 geht der Automat wieder in den Zustand <em>s</em>₁. (Das kann er tun. Endzustand heißt, dass der Automat am Ende in dem Zustand sein kann; nicht aber, das er den Zustand nicht wieder verlassen kann, wenn er sich zwischendurch darin befindet.) <em>s</em>₁ ist kein Endzustand; 987 nicht durch 2 teilbar.</p> <p>Durch Eingabe einer 6 geht der Automat wieder in den Zustand <em>s</em>₂. Endzustand; 9876 ist durch 2 teilbar.</p> <p>LLAP </p> <div class="signature">-- <br> <em>„Wer durch Wissen und Erfahrung der Klügere ist, der sollte nicht nachgeben. Und nicht aufgeben.“</em> —Kurt Weidemann </div> Informatik zum Jahresanfang – Zusatzaufgabe Thu, 03 Jan 19 19:53:51 Z https://forum.selfhtml.org/self/2019/jan/2/informatik-zum-jahresanfang/1739942#m1739942 https://forum.selfhtml.org/self/2019/jan/2/informatik-zum-jahresanfang/1739942#m1739942 <p>@@Gunnar Bittersmann</p> <p>Inzwischen trudelten einige richtige und fast richtige Lösungen per DM bei mir ein. Mal abwarten, vielleicht machen ja noch ein paar mehr Leute mit?</p> <p>Wo ihr schon dabei seid, könnt ihr auch gleich weitermachen:</p> <blockquote> <p>… wenn die dadurch eingegebene Zahl durch 2 teilbar ist.<br> … wenn die eingegebene Zahl durch 4 teilbar ist.</p> </blockquote> <p>Was kann denn jetzt wohl kommen?</p> <p>Die Zusatzaufgabe ist, einen endlichen Automaten zu bauen, der sich nur dann in einem Endzustand befindet, wenn die eingegebene Zahl durch 8 teilbar ist.</p> <p>LLAP </p> <div class="signature">-- <br> <em>„Wer durch Wissen und Erfahrung der Klügere ist, der sollte nicht nachgeben. Und nicht aufgeben.“</em> —Kurt Weidemann </div> Informatik zum Jahresanfang Fri, 04 Jan 19 17:06:27 Z https://forum.selfhtml.org/self/2019/jan/2/informatik-zum-jahresanfang/1740019#m1740019 https://forum.selfhtml.org/self/2019/jan/2/informatik-zum-jahresanfang/1740019#m1740019 <p>@@Gunnar Bittersmann</p> <blockquote> <p>Die Aufgabe ist, eine endlichen Automaten zu bauen, der sich nur dann in einem Endzustand befindet, wenn die eingegebene Zahl durch 4 teilbar ist.</p> </blockquote> <p>Da versucht doch tatsächlich jemand, mich auszutricksen! </p> <p>Naja, der Trick besteht darin, eine Lücke schamlos auszunutzen, die ich in der Aufgabenstellung gelassen hatte und hiermit für diese und alle weiteren Aufgaben schließe: Gesucht ist der minifizierte<sup class="footnote-ref"><a href="#fn1" id="fnref1">[1]</a></sup> Automat, d.h. jener mit der geringsten Anzahl von Zuständen.</p> <p>LLAP </p> <div class="signature">-- <br> <em>„Wer durch Wissen und Erfahrung der Klügere ist, der sollte nicht nachgeben. Und nicht aufgeben.“</em> —Kurt Weidemann </div> <hr class="footnotes-sep"> <section class="footnotes"> <ol class="footnotes-list"> <li id="fn1" class="footnote-item"><p>Ich erinnere mich, dass es in der Vorlesung Theoretische Informatik einen Begriff gab, aber nicht mehr genau, welcher. Vielleicht war’s ja wirklich „minifiziert“? Oder „minimal“? <a href="#fnref1" class="footnote-backref">↩︎</a></p> </li> </ol> </section> Informatik zum Jahresanfang – Auflösung für 4 Sat, 05 Jan 19 21:44:03 Z https://forum.selfhtml.org/self/2019/jan/2/informatik-zum-jahresanfang/1740062#m1740062 https://forum.selfhtml.org/self/2019/jan/2/informatik-zum-jahresanfang/1740062#m1740062 <p>@@Gunnar Bittersmann</p> <blockquote> <p>Die Aufgabe ist, eine endlichen Automaten zu bauen, der sich nur dann in einem Endzustand befindet, wenn die eingegebene Zahl durch 4 teilbar ist.</p> </blockquote> <p>Während man sich bei der Teilbarkeit durch 2 nur die letzte Stelle ansehen muss, sind es bei der Teilbarkeit durch 4 die letzten beiden. Ist die vorletzte gerade (oder nicht vorhanden), dann muss die letzte 0, 4 oder 8 sein, damit die Zahl durch 4 teilbar ist. Ist die vorletzte Stelle ungerade, dann muss dafür die letzte 2 oder 6 sein.</p> <p>Ein regulärer Ausdruck, der eine durch 4 teilbare Zahl angibt, sieht also so aus: [048]|[0-9]*([02468][048]|[13579][26])<sup class="footnote-ref"><a href="#fn1" id="fnref1">[1]</a></sup></p> <ol> <li>Reguläre Ausdrücke<sup class="footnote-ref"><a href="#fn2" id="fnref2">[2]</a></sup> und endliche Automaten sind äquivalent; sie erkennen beide dieselbe Klasse von Sprachen: die regulären Sprachen (Typ 3 in der <a href="https://de.wikipedia.org/wiki/Chomsky-Hierarchie" rel="nofollow noopener noreferrer">Chomsky-Hierarchie</a>).</li> </ol> <p>Der endliche Automat muss 3 Zustände haben</p> <ul> <li>letzte gelesene Ziffer ungerade;</li> <li>letzte gelesene Ziffer gerade, Zahl nicht durch 4 teilbar</li> <li>letzte gelesene Ziffer gerade, Zahl durch 4 teilbar (Endzustand)</li> </ul> <p>und sieht so aus:</p> <p><img src="/images/79ef026e-ee97-47ad-91bb-678ecefeb27a.jpg" alt="" loading="lazy"></p> <p>Diagramm von <a href="/users/6547" class="mention registered-user" rel="noopener noreferrer">@Rolf B</a>. Meins sah genauso aus, außer dass ich faul war und „ung.“ statt „1, 3, 5, 7, 9“ geschrieben hatte. Da kann ich mir sparen, das nochmal aufzuzeichnen und wieder Gefahr zu laufen, den Startpfeil zu vergessen.</p> <p>Den Gipfel der Faulheit erreichte <a href="/users/2" class="mention registered-user" rel="noopener noreferrer">@Matthias Apsel</a>, der auch die geraden Zahlen in zwei benannte Klassen {0, 4, 8} und {2, 6} einteilte und dann jeden Pfeil mit nur jeweils einem Buchstaben beschriftete.</p> <p>Aber Leute: Wenn es drei Zustände gibt, wobei jeder mit jedem anderen und mit sich selbst verbunden ist, dann sollten die in der Darstellung ein gleichseitiges Dreieck bilden. Wie sieht denn das sonst aus?</p> <p>Es sei denn, man macht’s wie <a href="/users/27" class="mention registered-user" rel="noopener noreferrer">@dedlfix</a> und sagt: „Das Ergebnis ist ein Gesicht.“</p> <p><a href="/images/3cf73283-19bd-4b2c-b621-07fd8f592ebb.png" rel="noopener noreferrer"><img src="/images/3cf73283-19bd-4b2c-b621-07fd8f592ebb.png?size=medium" alt="" loading="lazy"></a></p> <p>LLAP </p> <div class="signature">-- <br> <em>„Wer durch Wissen und Erfahrung der Klügere ist, der sollte nicht nachgeben. Und nicht aufgeben.“</em> —Kurt Weidemann </div> <hr class="footnotes-sep"> <section class="footnotes"> <ol class="footnotes-list"> <li id="fn1" class="footnote-item"><p>Die Klammern dienen hier nur zur Klammerung, nicht zum Merken von Matches. In Implementationen in Programmiersprachen wäre <code>(?:</code> zu schreiben. <a href="#fnref1" class="footnote-backref">↩︎</a></p> </li> <li id="fn2" class="footnote-item"><p>„Regulär“ wie in <a href="https://forum.selfhtml.org/self/2008/nov/6/alt-zu-allen-img-tags-hinzufuegen-falls-nicht-vorhanden/1305266#m1305266" rel="noopener noreferrer">regulär</a>. <a href="#fnref2" class="footnote-backref">↩︎</a></p> </li> </ol> </section> Informatik zum Jahresanfang – noch mehr Teiler Sun, 06 Jan 19 12:38:36 Z https://forum.selfhtml.org/self/2019/jan/2/informatik-zum-jahresanfang/1740076#m1740076 https://forum.selfhtml.org/self/2019/jan/2/informatik-zum-jahresanfang/1740076#m1740076 <p>@@Gunnar Bittersmann</p> <blockquote> <p>Das Bild zeigt einen endlichen Automaten, der sich bei der Eingabe einer Ziffernfolge nur dann im Endzustand (dargestellt durch doppelte Linie) befindet, wenn die dadurch eingegebene Zahl durch 2 teilbar ist. (Führende Nullen sollen erlaubt sein.)</p> <p><a href="/images/e1c2c44c-9fbb-44ea-bffc-c2a26744ba2b.jpeg" rel="noopener noreferrer"><img src="/images/e1c2c44c-9fbb-44ea-bffc-c2a26744ba2b.jpeg?size=medium" alt="" loading="lazy"></a></p> </blockquote> <p>Durch geringfügige Modifikation wird daraus ein Automat, der durch 5 teilbare Zahlen erkennt:</p> <p><img src="/images/a7a22ca8-c042-4896-81a2-428dbad0dcc9.png" alt="" loading="lazy"></p> <p>Und einer, der durch 10 teilbare Zahlen erkennt:</p> <p><img src="/images/a7e9ac91-6943-48b1-8bd1-471c1a109030.png" alt="" loading="lazy"></p> <p>Und wenn man einen 2er und einen 10er hinternander setzt, erhält man einen Automaten, der durch 20 teilbare Zahlen erkennt. Hier in der dedlfixschen Gesichtsform:</p> <p><img src="/images/3472cb2a-6460-4f1c-9d7e-9736b622baf4.png" alt="" loading="lazy"></p> <p></p> <p>So, was haben wir denn jetzt? Teilbarkeit durch 2, 4, 5, … Moment, was ist mit der 3?</p> <p>Hier die Aufgabe für alle, die mit der 8 fertig sind oder mit der 8 <em>fertig</em> sind: </p> <p>Baue einen endlichen Automaten, der sich nur dann in einem Endzustand befindet, wenn die eingegebene Zahl durch 3 teilbar ist.</p> <p>Und wenn man den hat, hat man auch durch geringfügige Modifikation den für 6. Und den für 15.</p> <p>LLAP </p> <div class="signature">-- <br> <em>„Wer durch Wissen und Erfahrung der Klügere ist, der sollte nicht nachgeben. Und nicht aufgeben.“</em> —Kurt Weidemann </div> Informatik zum Jahresanfang – noch eine Variation Wed, 09 Jan 19 14:23:04 Z https://forum.selfhtml.org/self/2019/jan/2/informatik-zum-jahresanfang/1740308#m1740308 https://forum.selfhtml.org/self/2019/jan/2/informatik-zum-jahresanfang/1740308#m1740308 <p>@@Gunnar Bittersmann</p> <blockquote> <p>Das Bild zeigt einen endlichen Automaten, der sich bei der Eingabe einer Ziffernfolge nur dann im Endzustand (dargestellt durch doppelte Linie) befindet, wenn die dadurch eingegebene Zahl durch 2 teilbar ist. (Führende Nullen sollen erlaubt sein.)</p> <p><a href="/images/e1c2c44c-9fbb-44ea-bffc-c2a26744ba2b.jpeg" rel="noopener noreferrer"><img src="/images/e1c2c44c-9fbb-44ea-bffc-c2a26744ba2b.jpeg?size=medium" alt="" loading="lazy"></a></p> </blockquote> <p>Ich mach mal den Columbo: Eine Frage hätte ich da noch. Wie müsste man den Automaten verändern, wenn führende Nullen nicht erlaubt sind?</p> <p>LLAP </p> <div class="signature">-- <br> <em>„Wer durch Wissen und Erfahrung der Klügere ist, der sollte nicht nachgeben. Und nicht aufgeben.“</em> —Kurt Weidemann </div> Informatik zum Jahresanfang Sun, 13 Jan 19 08:07:26 Z https://forum.selfhtml.org/self/2019/jan/2/informatik-zum-jahresanfang/1740610#m1740610 https://forum.selfhtml.org/self/2019/jan/2/informatik-zum-jahresanfang/1740610#m1740610 <p>@@Gunnar Bittersmann</p> <p>Ich möchte mich bei allen Beteiligten für diesen Thread bedanken. Ich hatte anfangs keine Vorstellung, wo dieser hinführen würde.</p> <p>Ich hab einiges gelernt:</p> <ul> <li> <p>dass man nicht nur die (Teilbarkeits-)Regeln im Kopf haben, sondern <em lang="en">beyond</em> <em>tellerrand</em> denken sollte; dann kann auch vorher Unmöglich-Geglaubtes möglich werden</p> </li> <li> <p>dass es für alles Werkzeuge gibt, manchmal auch richtig gute (wie <a href="https://flaci.com/home/" rel="nofollow noopener noreferrer">FLACI</a>)</p> </li> <li> <p>dass man zum Generieren von SVG-Elementen per JavaScript den Namensraum braucht</p> </li> <li> <p>wie man in GeoGebra Körper modelliert (Kugel, Zylinder, Torus)</p> </li> <li> <p>dass man mit endlichen Automaten auch Kunst machen kann:</p> <p><a href="/self/2019/jan/2/informatik-zum-jahresanfang/1740062#m1740062" rel="noopener noreferrer"><img src="/images/3cf73283-19bd-4b2c-b621-07fd8f592ebb.png?size=medium" alt="Gesicht von dedlfix" title="Gesicht von dedlfix" loading="lazy"></a> <a href="/self/2019/jan/2/informatik-zum-jahresanfang/1740122#m1740122" rel="noopener noreferrer"><img src="/images/773f6cbb-5c25-4aeb-9d3a-06735c4706a3.jpeg?size=medium" alt="keltisches Ornament von Gunnar Bittersmann" title="keltisches Ornament von Gunnar Bittersmann" loading="lazy"></a> <a href="/self/2019/jan/2/informatik-zum-jahresanfang/1740223#m1740223" rel="noopener noreferrer"><img src="/images/e96ecaa2-e0a4-4378-a09b-76bce3a4bafe.png" alt="3D-Adventskranz von Gunnar Bittersmann" title="3D-Adventskranz von Gunnar Bittersmann" loading="lazy"></a> <a href="/self/2019/jan/2/informatik-zum-jahresanfang/1740221#m1740221" rel="noopener noreferrer"><img src="/images/dd2e18d9-42b1-4467-9e00-6d74f818e0c8.jpg?size=medium" alt="Herz von Orlok" title="Herz von Orlok" loading="lazy"></a> <a href="/self/2019/jan/2/informatik-zum-jahresanfang/1740519#m1740519" rel="noopener noreferrer"><img src="/images/ceffeec0-e031-4c91-bae7-9b5f61fa80d0.png" alt="Sektglas von Matthias Apsel" title="Sektglas von Matthias Apsel" loading="lazy"></a> <a href="/self/2019/jan/2/informatik-zum-jahresanfang/1740518#m1740518" rel="noopener noreferrer"><img src="/images/6c1df75f-e3fa-4a1b-a753-072045cc464d.png" alt="Orion von Gunnar Bittersmann" title="Orion von Gunnar Bittersmann" loading="lazy"></a></p> </li> </ul> <p>LLAP </p> <div class="signature">-- <br> <em>„Wer durch Wissen und Erfahrung der Klügere ist, der sollte nicht nachgeben. Und nicht aufgeben.“</em> —Kurt Weidemann </div> Informatik zum Jahresanfang Wed, 16 Jan 19 20:49:21 Z https://forum.selfhtml.org/self/2019/jan/2/informatik-zum-jahresanfang/1740833#m1740833 https://forum.selfhtml.org/self/2019/jan/2/informatik-zum-jahresanfang/1740833#m1740833 <p>@@Gunnar Bittersmann</p> <p>Hier noch mal alle Automaten aus dem Thread gesammelt. Die Bilder verlinken auf die entsprechenden Postings.</p> <p>Teilbarkeit durch:</p> <p><a href="https://forum.selfhtml.org/self/2019/jan/2/informatik-zum-jahresanfang/1739779#m1739779" rel="noopener noreferrer"><img src="/images/e1c2c44c-9fbb-44ea-bffc-c2a26744ba2b.jpeg?size=medium" alt="Automat für Teilbarkeit durch 2" loading="lazy"></a> ◀︎ 2           <a href="https://forum.selfhtml.org/self/2019/jan/2/informatik-zum-jahresanfang/1740262#m1740262" rel="noopener noreferrer"><img src="/images/5f87c392-0401-47fe-9f42-609aa84c1af2.png" alt="Automat für Teilbarkeit durch 3" loading="lazy"></a> ◀︎ 3           <a href="https://forum.selfhtml.org/self/2019/jan/2/informatik-zum-jahresanfang/1740062#m1740062" rel="noopener noreferrer"><img src="https://forum.selfhtml.org/images/79ef026e-ee97-47ad-91bb-678ecefeb27a.jpg" alt="Automat für Teilbarkeit durch 4" loading="lazy"></a> ◀︎ 4</p> <p><a href="https://forum.selfhtml.org/self/2019/jan/2/informatik-zum-jahresanfang/1740076#m1740076" rel="noopener noreferrer"><img src="https://forum.selfhtml.org/images/a7a22ca8-c042-4896-81a2-428dbad0dcc9.png" alt="Automat für Teilbarkeit durch 5" loading="lazy"></a> ◀︎ 5           <a href="https://forum.selfhtml.org/self/2019/jan/2/informatik-zum-jahresanfang/1740262#m1740262" rel="noopener noreferrer"><img src="/images/18786f01-1513-40b2-aa6d-eca1db494ec3.png" alt="Automat für Teilbarkeit durch 6" loading="lazy"></a> ◀︎ 6           <a href="https://forum.selfhtml.org/self/2019/jan/2/informatik-zum-jahresanfang/1740221#m1740221" rel="noopener noreferrer"><img src="https://forum.selfhtml.org/images/dd2e18d9-42b1-4467-9e00-6d74f818e0c8.jpg?size=medium" alt="Automat für Teilbarkeit durch 7" loading="lazy"></a> ◀︎ 7</p> <p><a href="https://forum.selfhtml.org/self/2019/jan/2/informatik-zum-jahresanfang/1740122#m1740122" rel="noopener noreferrer"><img src="/images/d05edabd-754a-4b86-b660-b5b9ab050c48.png?size=medium" alt="Automat für Teilbarkeit durch 8" loading="lazy"></a> ◀︎ 8           <a href="https://forum.selfhtml.org/self/2019/jan/2/informatik-zum-jahresanfang/1740263#m1740263" rel="noopener noreferrer"><img src="https://forum.selfhtml.org/images/5bf0613a-7a6a-46c3-b000-40819b672f0b.png" alt="Automat für Teilbarkeit durch 9" loading="lazy"></a> ◀︎ 9           <a href="https://forum.selfhtml.org/self/2019/jan/2/informatik-zum-jahresanfang/1740076#m1740076" rel="noopener noreferrer"><img src="https://forum.selfhtml.org/images/a7e9ac91-6943-48b1-8bd1-471c1a109030.png" alt="Automat für Teilbarkeit durch 10" loading="lazy"></a> ◀︎ 10</p> <p><a href="https://forum.selfhtml.org/self/2019/jan/2/informatik-zum-jahresanfang/1740121#m1740121" rel="noopener noreferrer"><img src="https://forum.selfhtml.org/images/9ae38d08-fdc5-4786-ad75-eb862f508ce3.png?size=medium" alt="Automat für Teilbarkeit durch 13" loading="lazy"></a> ◀︎ 13           <a href="https://forum.selfhtml.org/self/2019/jan/2/informatik-zum-jahresanfang/1740262#m1740262" rel="noopener noreferrer"><img src="/images/c201c6d0-be5b-42a1-bb2b-537abccd60ed.png" alt="Automat für Teilbarkeit durch 15" loading="lazy"></a> ◀︎ 15           <a href="https://forum.selfhtml.org/self/2019/jan/2/informatik-zum-jahresanfang/1740076#m1740076" rel="noopener noreferrer"><img src="https://forum.selfhtml.org/images/3472cb2a-6460-4f1c-9d7e-9736b622baf4.png" alt="Automat für Teilbarkeit durch 20" loading="lazy"></a> ◀︎ 20</p> <p><a href="https://forum.selfhtml.org/self/2019/jan/2/informatik-zum-jahresanfang/1740220#m1740220" rel="noopener noreferrer"><img src="https://forum.selfhtml.org/images/c2ece82f-109f-46db-87a5-c98206ea9b0f.png" alt="Automat für Teilbarkeit durch 1000000" loading="lazy"></a> ◀︎ 1000000           <a href="https://forum.selfhtml.org/self/2019/jan/2/informatik-zum-jahresanfang/1740293#m1740293" rel="noopener noreferrer">$$\left( {s_{-0}, s_0, \ldots, s_{n-1}}, s_{-0}, {0, \ldots, 9}, \delta(s_u, d) = s_{(10u + d) \bmod n}, {s_0} \right)$$</a> ◀︎ <em>n</em></p> <hr> <p>ohne führende 0:</p> <p><a href="https://forum.selfhtml.org/self/2019/jan/2/informatik-zum-jahresanfang/1740519#m1740519" rel="noopener noreferrer"><img src="https://forum.selfhtml.org/images/ceffeec0-e031-4c91-bae7-9b5f61fa80d0.png" alt="Automat für Teilbarkeit durch 2" loading="lazy"></a> ◀︎ 2           <a href="https://forum.selfhtml.org/self/2019/jan/2/informatik-zum-jahresanfang/1740836#m1740836" rel="noopener noreferrer">$$\delta(s_u, d) = \begin{cases} s_{v = (10u + d) \bmod n} <br> s_{\mathrm{zero}} <br> s_{\mathrm{trap}} \end{cases}$$</a> ◀︎ <em>n</em>           <a href="https://forum.selfhtml.org/self/2019/jan/2/informatik-zum-jahresanfang/1740518#m1740518" rel="noopener noreferrer"><img src="https://forum.selfhtml.org/images/6c1df75f-e3fa-4a1b-a753-072045cc464d.png" alt="Automat für Dezimalzahl" loading="lazy"></a> ◀︎ Dezimalzahl</p> <p>LLAP </p> <div class="signature">-- <br> <em>„Wer durch Wissen und Erfahrung der Klügere ist, der sollte nicht nachgeben. Und nicht aufgeben.“</em> —Kurt Weidemann </div> Informatik zum Jahresanfang Wed, 02 Jan 19 13:40:34 Z https://forum.selfhtml.org/self/2019/jan/2/informatik-zum-jahresanfang/1739790#m1739790 https://forum.selfhtml.org/self/2019/jan/2/informatik-zum-jahresanfang/1739790#m1739790 <p>@@Matthias Apsel</p> <blockquote> <p>Der Startzustand wird durch einen zum Zustand zeigenden Pfeil symbolisiert.</p> </blockquote> <p>Grmpf, natürlich. Den hatte ich vergessen. Jetzt ergänzt.</p> <p>LLAP </p> <div class="signature">-- <br> <em>„Wer durch Wissen und Erfahrung der Klügere ist, der sollte nicht nachgeben. Und nicht aufgeben.“</em> —Kurt Weidemann </div> Informatik zum Jahresanfang – Zusatzaufgabe Fri, 04 Jan 19 12:52:11 Z https://forum.selfhtml.org/self/2019/jan/2/informatik-zum-jahresanfang/1740002#m1740002 https://forum.selfhtml.org/self/2019/jan/2/informatik-zum-jahresanfang/1740002#m1740002 <p>Hallo Gunnar Bittersmann,</p> <blockquote> <p>Die Zusatzaufgabe ist, eine endlichen Automaten zu bauen, der sich nur dann in einem Endzustand befindet, wenn die eingegebene Zahl durch 8 teilbar ist.</p> </blockquote> <p>Falls es auch eine Dezimalzahl sein soll, bin ich auf die Lösung gespannt.</p> <p>Bis demnächst<br> Matthias</p> <div class="signature">-- <br> Pantoffeltierchen haben keine Hobbys. </div> Informatik zum Jahresanfang – Auflösung der Zusatzaufgabe für 8 Mon, 07 Jan 19 07:17:33 Z https://forum.selfhtml.org/self/2019/jan/2/informatik-zum-jahresanfang/1740122#m1740122 https://forum.selfhtml.org/self/2019/jan/2/informatik-zum-jahresanfang/1740122#m1740122 <p>@@Gunnar Bittersmann</p> <blockquote> <blockquote> <p>… wenn die dadurch eingegebene Zahl durch 2 teilbar ist.<br> … wenn die eingegebene Zahl durch 4 teilbar ist.</p> </blockquote> <p>Was kann denn jetzt wohl kommen?</p> <p>Die Zusatzaufgabe ist, eine endlichen Automaten zu bauen, der sich nur dann in einem Endzustand befindet, wenn die eingegebene Zahl durch 8 teilbar ist.</p> </blockquote> <p>Bei Teilbarkeit durch 2 muss man sich die letzte Stelle ansehen, bei Teilbarkeit durch 4 die letzten beiden, bei Teilbarkeit durch 8 die letzten drei.</p> <p>Ein regulärer Ausdruck, der durch 8 teilbare Zahlen erkennt:<br> [048]?[08]|[26]4|[159]6|[37]2 | [0-9]* ( [02468] ([048][08]|[26]4|[159]6|[37]2) | [13579] ([048]4|[26][08]|[159]2|[37]6) )</p> <p>(Ich hab zur besseren Übersichtlichkeit Leerzeichen gesetzt. Die sind natürlich hier keine Symbole.)</p> <p>Endlicher Automat: ein <a href="https://de.wikipedia.org/wiki/Pentagramm#Pentakel" rel="nofollow noopener noreferrer">Pentakel</a>.</p> <p><a href="/images/d05edabd-754a-4b86-b660-b5b9ab050c48.png" rel="noopener noreferrer"><img src="/images/d05edabd-754a-4b86-b660-b5b9ab050c48.png?size=medium" alt="" loading="lazy"></a></p> <p>Darstellung analog zur dedlfixschen Gesichtsform beim 4er: ein keltisches Ornament?</p> <p><a href="/images/773f6cbb-5c25-4aeb-9d3a-06735c4706a3.jpeg" rel="noopener noreferrer"><img src="/images/773f6cbb-5c25-4aeb-9d3a-06735c4706a3.jpeg?size=medium" alt="" loading="lazy"></a></p> <p>(Fehlende Beschriftung gewollt, aber ich hab mal wieder keinen Startpfeil gemalt und der Übergang vom Endzustand zu sich selbst fehlt. Aber das würde nur die Symmetrie stören. )</p> <p>LLAP </p> <div class="signature">-- <br> <em>„Wer durch Wissen und Erfahrung der Klügere ist, der sollte nicht nachgeben. Und nicht aufgeben.“</em> —Kurt Weidemann </div> Informatik zum Jahresanfang – Zusatzaufgabe Fri, 04 Jan 19 14:00:39 Z https://forum.selfhtml.org/self/2019/jan/2/informatik-zum-jahresanfang/1740008#m1740008 https://forum.selfhtml.org/self/2019/jan/2/informatik-zum-jahresanfang/1740008#m1740008 <p>@@Matthias Apsel</p> <blockquote> <p>… wenn die eingegebene Zahl durch 8 teilbar ist.</p> <p>Falls es auch eine Dezimalzahl sein soll, bin ich auf die Lösung gespannt.</p> </blockquote> <p>Ein Dezimaltrennzeichen gehört nicht zum Eingabe-Alphabet.</p> <p>Macht nicht der Begriff „Teilbarkeit“ sowieso nur Sinn für ganze Zahlen?</p> <p>Ich bin eher gespannt, wie’s dann mit 16, 32, … weitergeht. Aber schön der Reihe nach …</p> <p>LLAP </p> <div class="signature">-- <br> <em>„Wer durch Wissen und Erfahrung der Klügere ist, der sollte nicht nachgeben. Und nicht aufgeben.“</em> —Kurt Weidemann </div> Informatik zum Jahresanfang – Zusatzaufgabe Fri, 04 Jan 19 15:22:41 Z https://forum.selfhtml.org/self/2019/jan/2/informatik-zum-jahresanfang/1740013#m1740013 https://forum.selfhtml.org/self/2019/jan/2/informatik-zum-jahresanfang/1740013#m1740013 <p>Hallo Gunnar Bittersmann,</p> <blockquote> <blockquote> <p>Falls es auch eine Dezimalzahl sein soll, bin ich auf die Lösung gespannt.</p> </blockquote> </blockquote> <p>Gemeint ist Zahl im Dezimalsystem.</p> <blockquote> <p>Ich bin eher gespannt, wie’s dann mit 16, 32, … weitergeht. Aber schön der Reihe nach …</p> </blockquote> <p>Ich betrachte mich als an 8 gescheitert.</p> <p>Bis demnächst<br> Matthias</p> <div class="signature">-- <br> Pantoffeltierchen haben keine Hobbys. </div> Informatik zum Jahresanfang – Zusatzaufgabe Fri, 04 Jan 19 16:55:26 Z https://forum.selfhtml.org/self/2019/jan/2/informatik-zum-jahresanfang/1740018#m1740018 https://forum.selfhtml.org/self/2019/jan/2/informatik-zum-jahresanfang/1740018#m1740018 <p>@@Matthias Apsel</p> <blockquote> <p>Gemeint ist Zahl im Dezimalsystem.</p> </blockquote> <p>Ach so. Nun ja, das Eingabe-Alphabet legt nahe, dass ich das auch meine. </p> <p>Hexadezimalsystem wäre ja auch zu einfach. </p> <p></p> <blockquote> <p>Ich betrachte mich als an 8 gescheitert.</p> </blockquote> <p>Hm, ich hätte jetzt gedacht, der Gedankenschritt von der 2 zur 4 wäre größer als der von der 4 zur 8. </p> <p>LLAP </p> <div class="signature">-- <br> <em>„Wer durch Wissen und Erfahrung der Klügere ist, der sollte nicht nachgeben. Und nicht aufgeben.“</em> —Kurt Weidemann </div> Informatik zum Jahresanfang – Zusatzaufgabe Fri, 04 Jan 19 17:13:27 Z https://forum.selfhtml.org/self/2019/jan/2/informatik-zum-jahresanfang/1740020#m1740020 https://forum.selfhtml.org/self/2019/jan/2/informatik-zum-jahresanfang/1740020#m1740020 <p>@@Gunnar Bittersmann</p> <p>Zum Reim fehlt eine Zeile hier:</p> <blockquote> <p>Hm, ich hätte jetzt gedacht,<br> der Gedankenschritt von der 2 zur 4<br> wäre größer als der von der 4 zur 8. </p> </blockquote> <p>LLAP </p> <div class="signature">-- <br> <em>„Wer durch Wissen und Erfahrung der Klügere ist, der sollte nicht nachgeben. Und nicht aufgeben.“</em> —Kurt Weidemann </div> Informatik zum Jahresanfang Fri, 04 Jan 19 17:17:24 Z https://forum.selfhtml.org/self/2019/jan/2/informatik-zum-jahresanfang/1740021#m1740021 https://forum.selfhtml.org/self/2019/jan/2/informatik-zum-jahresanfang/1740021#m1740021 <p>Hallo Gunnar Bittersmann,</p> <blockquote> <p>Naja, der Trick besteht darin, eine Lücke schamlos auszunutzen, die ich in der Aufgabenstellung gelassen hatte und hiermit für diese und alle weiten Aufgaben schließe: Gesucht ist der minifizierte[^mini] Automat, d.h. jener mit der geringsten Anzahl von Zuständen.</p> <p>[^mini]: Ich erinnere mich, dass es in der Vorlesung Theoretische Informatik einen Begriff gab, aber nicht mehr genau, welcher. Vielleicht war’s ja wirklich „minifiziert“? Oder „minimal“?</p> </blockquote> <p>Ich verwende Minimalautomat.</p> <p>Allerdings müsstest du auch beweisen, dass sich der Automat nicht um weitere Zustände erleichtern lässt.</p> <p>Ich würde deshalb von einem Automaten mit möglichst geringer Anzahl von Zuständen sprechen.</p> <p>Bis demnächst<br> Matthias</p> <div class="signature">-- <br> Pantoffeltierchen haben keine Hobbys. </div> Informatik zum Jahresanfang – Auflösung für 4 Sun, 06 Jan 19 09:30:57 Z https://forum.selfhtml.org/self/2019/jan/2/informatik-zum-jahresanfang/1740066#m1740066 https://forum.selfhtml.org/self/2019/jan/2/informatik-zum-jahresanfang/1740066#m1740066 <p>Hallo Gunnar Bittersmann,</p> <blockquote> <p>Ein regulärer Ausdruck, der eine durch 4 teilbare Zahl angibt, sieht also so aus:<br> [048]|[0-9]*([02468][048]|[13579][26])</p> </blockquote> <p><code>[02468][048] | [13579][26]</code> kann man sich ohne Hilfsmittel gut beim Spazierengehen überlegen.</p> <p><code>[0-9]*</code> ist trivial, <code>[048]</code> kommt dann ins Spiel, wenn man die Sonderfälle beachten möchte und den Automaten damit auf drei Zustände reduziert.</p> <blockquote> <p>Den Gipfel der Faulheit erreichte <a href="/users/2" class="mention registered-user" rel="noopener noreferrer">@Matthias Apsel</a>, der auch die geraden Zahlen in zwei benannte Klassen {0, 4, 8} und {2, 6} einteilte und dann jeden Pfeil mit nur jeweils einem Buchstaben beschriftete.</p> </blockquote> <p>Aber dafür hatte ich sprechende Zustandsnamen.</p> <blockquote> <p>die Zustände heißen</p> <ul> <li><strong>R0</strong> für "Einerziffer hat bei Division durch 4 den Rest 0"</li> <li><strong>R2</strong> für "Einerziffer hat bei Division durch 4 den Rest 2"</li> <li><strong>U</strong> für "Einerziffer ist ungerade"</li> </ul> <p>das Eingabealphabet</p> <ul> <li>n ∈ N = {0; 4; 8}</li> <li>z ∈ Z = {2; 6}</li> <li>u ∈ U = {1; 3; 5; 7; 9}</li> </ul> <p><a href="/images/7a765706-c384-4739-8913-dbf821617c3a.png" rel="noopener noreferrer"><img src="/images/7a765706-c384-4739-8913-dbf821617c3a.png?size=medium" alt="endlicher Automat" loading="lazy"></a><br> (Grafik erstellt mit <a href="https://flaci.com/" rel="nofollow noopener noreferrer">FLACI</a>)</p> </blockquote> <p>Bis demnächst<br> Matthias</p> <div class="signature">-- <br> Pantoffeltierchen haben keine Hobbys. </div> Informatik zum Jahresanfang – Auflösung für 4 Sun, 06 Jan 19 10:24:05 Z https://forum.selfhtml.org/self/2019/jan/2/informatik-zum-jahresanfang/1740069#m1740069 https://forum.selfhtml.org/self/2019/jan/2/informatik-zum-jahresanfang/1740069#m1740069 <p>@@Gunnar Bittersmann</p> <p>BTW, <img src="/images/34fed28e-f2e9-4f35-a028-b11ab67db602.png" alt="Auflösung" loading="lazy"> ist auch so ein Kandidat, <a href="https://forum.selfhtml.org/self/2018/dec/27/typografie-zum-jahresende/1739687#m1739687" rel="noopener noreferrer">wo keine fl-Ligatur gesetzt werden sollte</a>.</p> <p>LLAP </p> <div class="signature">-- <br> <em>„Wer durch Wissen und Erfahrung der Klügere ist, der sollte nicht nachgeben. Und nicht aufgeben.“</em> —Kurt Weidemann </div> Informatik zum Jahresanfang – Auflösung für 4 Sun, 06 Jan 19 10:10:27 Z https://forum.selfhtml.org/self/2019/jan/2/informatik-zum-jahresanfang/1740067#m1740067 https://forum.selfhtml.org/self/2019/jan/2/informatik-zum-jahresanfang/1740067#m1740067 <p>@@Matthias Apsel</p> <blockquote> <blockquote> <p>Ein regulärer Ausdruck, der eine durch 4 teilbare Zahl angibt, sieht also so aus:<br> [048]|[0-9]*([02468][048]|[13579][26])</p> </blockquote> <p><code>[048]</code> kommt dann ins Spiel, wenn man die Sonderfälle beachten möchte</p> </blockquote> <p>?? Nee, [048] da vornedran ist für die einstelligen 0, 4 und 8.</p> <p>Man kann da ja nicht [0-9]*([02468]<strong>?</strong>[048]|[13579][26]) schreiben, denn das würde ja alle [0-9]*[048] matchen.</p> <blockquote> <p>… und den Automaten damit auf drei Zustände reduziert.</p> </blockquote> <p>?? Der reguläre Ausdruck hat mit den Zuständen eines entsprechenden endlichen Automaten zunächst einmal wenig zu tun.</p> <p></p> <blockquote> <blockquote> <p>(Grafik erstellt mit <a href="https://flaci.com/" rel="nofollow noopener noreferrer">FLACI</a>)</p> </blockquote> </blockquote> <p>Ein ziemlich geiles Tool.</p> <p>Hat mir gute Dienste geleistet zu prüfen, ob <a href="/users/6317" class="mention registered-user" rel="noopener noreferrer">@Orlok</a>⁠s oder mein Automat für die Teilbarkeit durch 8 richtig war. Ihr ahnt es: Orloks war’s. </p> <p>LLAP </p> <div class="signature">-- <br> <em>„Wer durch Wissen und Erfahrung der Klügere ist, der sollte nicht nachgeben. Und nicht aufgeben.“</em> —Kurt Weidemann </div> Informatik zum Jahresanfang – Auflösung für 4 Sun, 06 Jan 19 10:17:54 Z https://forum.selfhtml.org/self/2019/jan/2/informatik-zum-jahresanfang/1740068#m1740068 https://forum.selfhtml.org/self/2019/jan/2/informatik-zum-jahresanfang/1740068#m1740068 <p>Hallo Gunnar Bittersmann,</p> <blockquote> <p>?? Nee, [048] da vornedran ist für die einstelligen 0, 4 und 8.</p> </blockquote> <p>Schon klar.</p> <blockquote> <blockquote> <p>… und den Automaten damit auf drei Zustände reduziert.</p> </blockquote> <p>?? Der reguläre Ausdruck hat mit den Zuständen eines entsprechenden endlichen Automaten zunächst einmal wenig zu tun.</p> </blockquote> <p>Meine erster Automat hatte noch 5 Zustände.</p> <p>Bis demnächst<br> Matthias</p> <div class="signature">-- <br> Pantoffeltierchen haben keine Hobbys. </div> Informatik zum Jahresanfang – Auflösung für 4 Sun, 06 Jan 19 16:56:30 Z https://forum.selfhtml.org/self/2019/jan/2/informatik-zum-jahresanfang/1740095#m1740095 https://forum.selfhtml.org/self/2019/jan/2/informatik-zum-jahresanfang/1740095#m1740095 <p>Hallo Matthias,</p> <p>meiner auch. Bis mir die Redundanzen ins Auge fielen…</p> <p><em>Rolf</em></p> <div class="signature">-- <br> sumpsi - posui - clusi </div> Informatik zum Jahresanfang – noch mehr Teiler Sun, 06 Jan 19 16:58:03 Z https://forum.selfhtml.org/self/2019/jan/2/informatik-zum-jahresanfang/1740097#m1740097 https://forum.selfhtml.org/self/2019/jan/2/informatik-zum-jahresanfang/1740097#m1740097 <p>Hallo Gunnar,</p> <p>der für 7 ist auch immer noch offen</p> <p><em>Rolf</em></p> <div class="signature">-- <br> sumpsi - posui - clusi </div> Informatik zum Jahresanfang – noch mehr Teiler - Spoiler Sun, 06 Jan 19 23:56:14 Z https://forum.selfhtml.org/self/2019/jan/2/informatik-zum-jahresanfang/1740121#m1740121 https://forum.selfhtml.org/self/2019/jan/2/informatik-zum-jahresanfang/1740121#m1740121 <p>Tach!</p> <blockquote> <p>So, was haben wir denn jetzt? Teilbarkeit durch 2, 4, 5, … Moment, was ist mit der 3?</p> <p>Hier die Aufgabe für alle, die mit der 8 fertig sind oder mit der 8 <em>fertig</em> sind: </p> <p>Baue einen endlichen Automaten, der sich nur dann in einem Endzustand befindet, wenn die eingegebene Zahl durch 3 teilbar ist.</p> <p>Und wenn man den hat, hat man auch durch geringfügige Modifikation den für 6. Und den für 15.</p> </blockquote> <p>Vermutlich lassen sich alle diese Automaten nach demselben sehr einfachen Prinzip erstellen. Bei allen Zahlen, die ich probiert haben, gibt es eine Regel, wieviele Knoten es mindestens geben muss. Diese erstellt man und trägt für alle Vielfachen des Teilers bis zum 10-fachen die Verbindungen zum Endzustand ein. Der Rest ist stupide Fleißarbeit beim Ausfüllen der Lücken in der Übergangstabelle. Diese Regeln herauszufinden, überlasse ich vorerst dem geneigten Leser.</p> <p>So sieht übrigens der 13er Automat aus, und die Automaten werden mit größeren Primzahlen auch nicht mehr kleiner:</p> <p><a href="/images/9ae38d08-fdc5-4786-ad75-eb862f508ce3.png" rel="noopener noreferrer"><img src="/images/9ae38d08-fdc5-4786-ad75-eb862f508ce3.png?size=medium" alt="" loading="lazy"></a></p> <p>dedlfix.</p> Informatik zum Jahresanfang – noch mehr Teiler Tue, 08 Jan 19 11:27:48 Z https://forum.selfhtml.org/self/2019/jan/2/informatik-zum-jahresanfang/1740220#m1740220 https://forum.selfhtml.org/self/2019/jan/2/informatik-zum-jahresanfang/1740220#m1740220 <p>@@Gunnar Bittersmann</p> <blockquote> <p>Und wenn man einen 2er und einen 10er hinternander setzt, erhält man einen Automaten, der durch 20 teilbare Zahlen erkennt.</p> </blockquote> <p>Und wenn man zwei 10er hinternander setzt, erhält man einen Automaten, der durch 100 teilbare Zahlen erkennt. Das Diagramm ersparen wir uns. Wir sind zu höheren Zielen berufen.</p> <p>Wer wird Millionär?</p> <p><img src="/images/c2ece82f-109f-46db-87a5-c98206ea9b0f.png" alt="" loading="lazy"></p> <p>Die erste Million ist die schwerste.</p> <p>Das schwerste hieran war wohl, den Startpfeil richtig zu setzen. (Und nicht etwa einen zusätzlichen Startzustand vorzusehen.)</p> <p>LLAP </p> <p>PS: höhere Ziele ≠ hehere Ziele, höhö.</p> <div class="signature">-- <br> <em>„Wer durch Wissen und Erfahrung der Klügere ist, der sollte nicht nachgeben. Und nicht aufgeben.“</em> —Kurt Weidemann </div> Informatik zum Jahresanfang – Auflösung für 3, 6 und 15 Tue, 08 Jan 19 23:25:16 Z https://forum.selfhtml.org/self/2019/jan/2/informatik-zum-jahresanfang/1740262#m1740262 https://forum.selfhtml.org/self/2019/jan/2/informatik-zum-jahresanfang/1740262#m1740262 <p>@@Gunnar Bittersmann</p> <blockquote> <blockquote> <p>Das Bild zeigt einen endlichen Automaten, der sich bei der Eingabe einer Ziffernfolge nur dann im Endzustand (dargestellt durch doppelte Linie) befindet, wenn die dadurch eingegebene Zahl durch 2 teilbar ist. (Führende Nullen sollen erlaubt sein.)</p> <p><a href="/images/e1c2c44c-9fbb-44ea-bffc-c2a26744ba2b.jpeg" rel="noopener noreferrer"><img src="/images/e1c2c44c-9fbb-44ea-bffc-c2a26744ba2b.jpeg?size=medium" alt="" loading="lazy"></a></p> </blockquote> <p>Baue einen endlichen Automaten, der sich nur dann in einem Endzustand befindet, wenn die eingegebene Zahl durch 3 teilbar ist.</p> </blockquote> <p>Man könnte geneigt sein zu denken: Teilbarkeit durch 2 – 2 Zustände, Teilbarkeit durch 3 – 3 Zustände, und kommt auf diesen Automaten:</p> <p><img src="/images/ed210a9e-a35d-470b-a2ad-ca4bf630e18e.png" alt="" loading="lazy"></p> <p>Na, nicht so ganz. Das leere Wort (keine Eingabe) repräsentiert keine Zahl, die irgendwie teilbar wäre. Der Anfangszustand darf nicht Endzustand sein.</p> <p>Ich will hier niemanden scharf ankucken; bei der ersten Aufgabe (dem 4er) war auch nicht nur einer zunächst in dasselbe offene Messer gerannt.</p> <p>Beim 4er (wie auch beim 2er im Bild oben) war der Trick, den Pfeil einfach auf einen anderen passenden Zustand zu setzen. Das funktioniert hier aber nicht, weil keiner passt. Wir müssen <em>s</em>₀ in <em>s</em>₀ und <em>s</em>ₑ aufdröseln, die ansonsten identisch „verdrahtet“ sind – nur dass einer Endzustand ist und der andere nicht.</p> <p><img src="/images/5f87c392-0401-47fe-9f42-609aa84c1af2.png" alt="" loading="lazy"></p> <blockquote> <p>Und wenn man den hat, hat man auch durch geringfügige Modifikation den für 6. Und den für 15.</p> </blockquote> <p>Teilbarkeit durch 6 heißt Teilbarkeit durch 2 und durch 3. Hier muss man nun nicht Zustände aufdrösen, sondern Übergange, d.h. die Pfeile. Zum Endzustand <em>s</em>ₑ führen nur gerade Zahlen als letzte Ziffer (innerer Ring); die ungeraden führen zu einem Zustand, der im Kreis der Teilbarkeit durch 3 eine äquivalente Stelle wie <em>s</em>ₑ einnimmt – und einen solchen haben wir schon: das ist ja gerade <em>s</em>₀! (äußerer Ring)</p> <p><img src="/images/18786f01-1513-40b2-aa6d-eca1db494ec3.png" alt="" loading="lazy"></p> <p>Teilbarkeit durch 15 heißt Teilbarkeit durch 3 und durch 5. Zum Endzustand <em>s</em>ₑ führen nur 0 und 5 als letzte Ziffer (innerer Ring); die anderen führen zu <em>s</em>₀ (äußerer Ring):</p> <p><img src="/images/c201c6d0-be5b-42a1-bb2b-537abccd60ed.png" alt="" loading="lazy"></p> <p>LLAP </p> <div class="signature">-- <br> <em>„Wer durch Wissen und Erfahrung der Klügere ist, der sollte nicht nachgeben. Und nicht aufgeben.“</em> —Kurt Weidemann </div> Informatik zum Jahresanfang – noch mehr Teiler Sun, 06 Jan 19 17:08:56 Z https://forum.selfhtml.org/self/2019/jan/2/informatik-zum-jahresanfang/1740098#m1740098 https://forum.selfhtml.org/self/2019/jan/2/informatik-zum-jahresanfang/1740098#m1740098 <p>Hallo Rolf B,</p> <blockquote> <p>der für 7 ist auch immer noch offen</p> </blockquote> <p>Wenn man vergisst, dass es Teilbarkeitsregeln gibt, kann man alle diese Automaten nach demselben Muster bauen.</p> <p>Bis demnächst<br> Matthias</p> <div class="signature">-- <br> Pantoffeltierchen haben keine Hobbys. </div> Informatik zum Jahresanfang – noch mehr Teiler Sun, 06 Jan 19 17:23:06 Z https://forum.selfhtml.org/self/2019/jan/2/informatik-zum-jahresanfang/1740099#m1740099 https://forum.selfhtml.org/self/2019/jan/2/informatik-zum-jahresanfang/1740099#m1740099 <p>@@Matthias Apsel</p> <blockquote> <blockquote> <p>der für 7 ist auch immer noch offen</p> </blockquote> </blockquote> <p>Die wollte ich mir für zum Schluss aufheben.</p> <blockquote> <p>Wenn man vergisst, dass es Teilbarkeitsregeln gibt, kann man alle diese Automaten nach demselben Muster bauen.</p> </blockquote> <p>Kann man? Ich würde sagen: nein.</p> <p>Also gut, dann eröffnen wir auch diese Runde: … Automat, der durch 7 teilbare Zahlen erkennt. Oder beweise, dass es keinen solchen gibt. In anderen Worten: zeige, dass die Sprache der durch 7 teilbaren Zahlen regulär ist bzw. dass sie das nicht ist.</p> <p>LLAP </p> <div class="signature">-- <br> <em>„Wer durch Wissen und Erfahrung der Klügere ist, der sollte nicht nachgeben. Und nicht aufgeben.“</em> —Kurt Weidemann </div> Informatik zum Jahresanfang – noch mehr Teiler Sun, 06 Jan 19 17:32:40 Z https://forum.selfhtml.org/self/2019/jan/2/informatik-zum-jahresanfang/1740100#m1740100 https://forum.selfhtml.org/self/2019/jan/2/informatik-zum-jahresanfang/1740100#m1740100 <p>Hallo Gunnar Bittersmann,</p> <blockquote> <p>Kann man? Ich würde sagen: nein.</p> </blockquote> <p>Wahrscheinlich war ich zu vorschnell.</p> <p>Bis demnächst<br> Matthias</p> <div class="signature">-- <br> Pantoffeltierchen haben keine Hobbys. </div> Informatik zum Jahresanfang – Auflösung für 7 Tue, 08 Jan 19 11:46:23 Z https://forum.selfhtml.org/self/2019/jan/2/informatik-zum-jahresanfang/1740221#m1740221 https://forum.selfhtml.org/self/2019/jan/2/informatik-zum-jahresanfang/1740221#m1740221 <p>@@Gunnar Bittersmann</p> <blockquote> <blockquote> <p>Wenn man vergisst, dass es Teilbarkeitsregeln gibt</p> </blockquote> </blockquote> <p>Guter Tip.</p> <blockquote> <blockquote> <p>kann man alle diese Automaten nach demselben Muster bauen.</p> </blockquote> </blockquote> <p>Ich hatte mich an den Teilbarkeitsregeln orientiert und von hinten nach vorne gedacht, inbesondere bei den Teilbarkeiten durch 2<em>ⁿ</em>: Was muss die letzte Stelle sein, was die vorletzte, …?</p> <p>Wenn man aber von vorne nach hinten denkt …</p> <blockquote> <p>Kann man? Ich würde sagen: nein.</p> </blockquote> <p>Ich wurde eines besseren belehrt.</p> <blockquote> <p>Automat, der durch 7 teilbare Zahlen erkennt.</p> </blockquote> <p>Es trudelten einige Lösungen ein. <a href="/users/6317" class="mention registered-user" rel="noopener noreferrer">@Orlok</a> hat besonders viel Liebe reingesteckt:</p> <p><a href="/images/dd2e18d9-42b1-4467-9e00-6d74f818e0c8.jpg" rel="noopener noreferrer"><img src="/images/dd2e18d9-42b1-4467-9e00-6d74f818e0c8.jpg?size=medium" alt="FSM" title="FSM" loading="lazy"></a></p> <p>LLAP </p> <div class="signature">-- <br> <em>„Wer durch Wissen und Erfahrung der Klügere ist, der sollte nicht nachgeben. Und nicht aufgeben.“</em> —Kurt Weidemann </div> Informatik zum Jahresanfang – noch mehr Teiler - Spoiler Mon, 07 Jan 19 12:56:58 Z https://forum.selfhtml.org/self/2019/jan/2/informatik-zum-jahresanfang/1740142#m1740142 https://forum.selfhtml.org/self/2019/jan/2/informatik-zum-jahresanfang/1740142#m1740142 <p>@@dedlfix</p> <blockquote> <p>Vermutlich lassen sich alle diese Automaten nach demselben sehr einfachen Prinzip erstellen.</p> </blockquote> <p>Ich bin vielleicht der letzte, der’s verstanden hat; aber ich glaube, jetzt hab auch ich es. Um nicht ganz so dumm dazustehen, konter ich mit der nächsten (letzten?) Aufgabe:</p> <p>Baue einen endlichen Automaten, der eine durch <em>n</em> teilbare Zahl erkennt. Für den allgemeinen Fall soll die Einschränkung fallengelassen werden, dass es der Minimalautomat sein muss.</p> <p>Mit einem Diagramm wird das bei beliebigem <em>n</em> wohl nichts, gesucht ist die formale Darstellung als Quintupel (<em>S</em>, <em>s</em>₁, <em>Σ</em>, <em>δ</em>, <em>F</em>) (siehe <a href="https://forum.selfhtml.org/self/2019/jan/2/informatik-zum-jahresanfang/1739779#m1739779" rel="noopener noreferrer">Ursprungsposting</a>). Das Alphabet <em>Σ</em> ist klar, wie gehabt Ziffern 0 bis 9. Wie sieht die Zustandsmenge <em>S</em> aus? (Größe – Namen sind Schall und Rauch.) Und wie die Übergangsfunktion <em>δ</em>?</p> <p>LLAP </p> <p>PS: Abgesehen davon stehen immer noch die Minimalautomaten für 3, 6 und 15 im Raum. Auf die kommt man vermutlich einfacher durch Überlegungen auf direktem Weg als vom allgemeinen Fall auszugehen und dann die Zustandsmenge zu reduzieren.</p> <div class="signature">-- <br> <em>„Wer durch Wissen und Erfahrung der Klügere ist, der sollte nicht nachgeben. Und nicht aufgeben.“</em> —Kurt Weidemann </div> Informatik zum Jahresanfang – Auflösung der Zusatzaufgabe für 8 Mon, 07 Jan 19 08:18:09 Z https://forum.selfhtml.org/self/2019/jan/2/informatik-zum-jahresanfang/1740125#m1740125 https://forum.selfhtml.org/self/2019/jan/2/informatik-zum-jahresanfang/1740125#m1740125 <p>Tach!</p> <blockquote> <p>Darstellung analog zur dedlfixschen Gesichtsform beim 4er: ein keltisches Ornament?</p> <p><a href="/images/773f6cbb-5c25-4aeb-9d3a-06735c4706a3.jpeg" rel="noopener noreferrer"><img src="/images/773f6cbb-5c25-4aeb-9d3a-06735c4706a3.jpeg?size=medium" alt="" loading="lazy"></a></p> <p>(Fehlende Beschriftung gewollt, aber ich hab mal wieder keinen Startpfeil gemalt und der Übergang vom Endzustand zu sich selbst fehlt. Aber das würde nur die Symmetrie stören. )</p> </blockquote> <p>Denk mal dreidimensional. Der Bogen zeigt in Richtung Z-Achse, dann kannst du das Ding drehen, daran aufhängen, und 4 Kerzen in die Zustände stecken. So erhält man einen schönen Adventskranz für informatisch Interessierte.</p> <p>dedlfix.</p> Informatik zum Jahresanfang – Auflösung der Zusatzaufgabe für 8 Tue, 08 Jan 19 12:39:11 Z https://forum.selfhtml.org/self/2019/jan/2/informatik-zum-jahresanfang/1740223#m1740223 https://forum.selfhtml.org/self/2019/jan/2/informatik-zum-jahresanfang/1740223#m1740223 <p>@@dedlfix</p> <blockquote> <blockquote> <p>Darstellung analog zur dedlfixschen Gesichtsform beim 4er: ein keltisches Ornament?</p> <p><a href="/images/773f6cbb-5c25-4aeb-9d3a-06735c4706a3.jpeg" rel="noopener noreferrer"><img src="/images/773f6cbb-5c25-4aeb-9d3a-06735c4706a3.jpeg?size=medium" alt="" loading="lazy"></a></p> <p>(Fehlende Beschriftung gewollt, aber ich hab mal wieder keinen Startpfeil gemalt und der Übergang vom Endzustand zu sich selbst fehlt. Aber das würde nur die Symmetrie stören. )</p> </blockquote> <p>Denk mal dreidimensional. Der Bogen zeigt in Richtung Z-Achse, dann kannst du das Ding drehen, daran aufhängen, und 4 Kerzen in die Zustände stecken. So erhält man einen schönen Adventskranz für informatisch Interessierte.</p> </blockquote> <p><img src="/images/e96ecaa2-e0a4-4378-a09b-76bce3a4bafe.png" alt="" loading="lazy"></p> <p>(<a href="https://www.geogebra.org/3d/xusvmw99" rel="nofollow noopener noreferrer">3D-Modell</a>)</p> <p>Soll in die Mitte auch eine Kerze?</p> <p>Und wenn das 5. Lichtlein brennt, haste Weihnachten verpennt?</p> <p>LLAP </p> <div class="signature">-- <br> <em>„Wer durch Wissen und Erfahrung der Klügere ist, der sollte nicht nachgeben. Und nicht aufgeben.“</em> —Kurt Weidemann </div> Informatik zum Jahresanfang – noch mehr Teiler - Spoiler Mon, 07 Jan 19 13:22:09 Z https://forum.selfhtml.org/self/2019/jan/2/informatik-zum-jahresanfang/1740143#m1740143 https://forum.selfhtml.org/self/2019/jan/2/informatik-zum-jahresanfang/1740143#m1740143 <p>Hallo Gunnar Bittersmann,</p> <blockquote> <p>Baue einen endlichen Automaten, der eine durch <em>n</em> teilbare Zahl erkennt. Für den allgemeinen Fall soll die Einschränkung fallengelassen werden, dass es der Minimalautomat sein muss.</p> </blockquote> <p>Diese Aufgabe ist nicht lösbar.</p> <p>Du kannst höchstens für ein konkretes <em>n</em> einen Automaten bauen, nicht aber einen Automaten, der Teilbarkeit durch beliebige <em>n</em> erkennt.</p> <p>Bis demnächst<br> Matthias</p> <div class="signature">-- <br> Pantoffeltierchen haben keine Hobbys. </div> Informatik zum Jahresanfang – noch mehr Teiler - Spoiler Mon, 07 Jan 19 13:28:38 Z https://forum.selfhtml.org/self/2019/jan/2/informatik-zum-jahresanfang/1740144#m1740144 https://forum.selfhtml.org/self/2019/jan/2/informatik-zum-jahresanfang/1740144#m1740144 <p>Tach!</p> <blockquote> <p>PS: Abgesehen davon stehen immer noch die Minimalautomaten für 3, 6 und 15 im Raum. Auf die kommt man vermutlich einfacher durch Überlegungen auf direktem Weg als vom allgemeinen Fall auszugehen und dann die Zustandsmenge zu reduzieren.</p> </blockquote> <p>Meinst du, die lassen sich mit weniger als 4 Zuständen realisieren?</p> <p>dedlfix.</p> Informatik zum Jahresanfang – noch mehr Teiler - Spoiler Tue, 08 Jan 19 15:13:07 Z https://forum.selfhtml.org/self/2019/jan/2/informatik-zum-jahresanfang/1740230#m1740230 https://forum.selfhtml.org/self/2019/jan/2/informatik-zum-jahresanfang/1740230#m1740230 <p>Hallo Gunnar,</p> <blockquote> <p>Ich bin vielleicht der letzte, der’s verstanden hat; aber ich glaube, jetzt hab auch ich es.</p> </blockquote> <p>Nein, bist Du nicht, ich glaube, ich war's. Aber dafür versuche ich jetzt mal, es aufzuschreiben, am Beispiel der 7.</p> <p>Man braucht für einen solchen Automaten einen Startzustand sowie einen Zustand R0 bis Rn für jeden möglichen Divisionsrest. Die Werte der Übergangsfunktion des Startzustandes sind identisch mit denen des Endzustandes. Er existiert nur, damit das leere Wort nicht als "teilbar durch N" akzeptiert wird. Endzustand ist logischerweise R0.</p> <p>Man muss nun herausfinden, wie sich k und 10k mod 7 verhalten:</p> <p>Wenn $$k \equiv n \pmod 7$$, dann ist $$10k = 7k+3k \equiv 0 + 3n \pmod 7$$. Mit $$p = (3n \bmod 7)$$ erhält man also den Status Rp, der bei Antreffen der Ziffer 0 auf den Rn folgen muss. Die übrigen ergeben sich fortlaufend automatisch: Zum Beispiel ist p=5 für n=4, damit hat der Zustand R4 die Übergänge</p> <pre><code class="block">0,7 -> R5 1,8 -> R6 2,9 -> R0 3 -> R1 4 -> R2 5 -> R3 6 -> R4 </code></pre> <p>Oder - aus FLACI kopiert, diese Deltafunktion:</p> <pre><code class="block"> δ 0 1 2 3 4 5 6 7 8 9 R0 R0 R1 R2 R3 R4 R5 R6 R0 R1 R2 R1 R3 R4 R5 R6 R0 R1 R2 R3 R4 R5 R2 R6 R0 R1 R2 R3 R4 R5 R6 R0 R1 R3 R2 R3 R4 R5 R6 R0 R1 R2 R3 R4 R4 R5 R6 R0 R1 R2 R3 R4 R5 R6 R0 R5 R1 R2 R3 R4 R5 R6 R0 R1 R2 R3 R6 R4 R5 R6 R0 R1 R2 R3 R4 R5 R6 </code></pre> <p>Ob das bei zweistelligen Teilern genauso funktioniert? Wenn $$k \equiv n \pmod{37}$$, was ist dann mit 10k?</p> <p>$$10k = 37k - 27k \equiv 0 - 27n \pmod{37}$$, d.h. für $$p=(-27n) \bmod 37$$ erhält man zum Status n den Folgestatus p bei Antreffen der Ziffer 0. Dabei ist der Rest so zu bestimmen, dass er nicht negativ ist, d.h. es muss beispielsweise $$-27 : 37 = -1$$ mit Rest 10 gelten.</p> <p>Auf den Zustand R1 müsste bei Antreffen der Ziffer 0 also der Zustand $$-27\cdot 1 \bmod{37}= 10$$ folgen, demzufolge bei Antreffen der 4 der Zustand R14. Und auf R14 der Zustand $$-27\cdot 14 \bmod{37}=29$$ für Ziffer 0, demzufolge R0 für Ziffer 8. Kurzer Blick auf den Taschenrechner: $$148=4\cdot 37$$ - scheint zu passen.</p> <p>Ich bin total perplex, das hatte ich für unmöglich gehalten.</p> <p><em>Rolf</em></p> <div class="signature">-- <br> sumpsi - posui - clusi </div> Informatik zum Jahresanfang – Auflösung für n Wed, 09 Jan 19 10:04:48 Z https://forum.selfhtml.org/self/2019/jan/2/informatik-zum-jahresanfang/1740293#m1740293 https://forum.selfhtml.org/self/2019/jan/2/informatik-zum-jahresanfang/1740293#m1740293 <p>@@Gunnar Bittersmann</p> <blockquote> <p>Baue einen endlichen Automaten, der eine durch <em>n</em> teilbare Zahl erkennt. Für den allgemeinen Fall soll die Einschränkung fallengelassen werden, dass es der Minimalautomat sein muss.</p> <p>Mit einem Diagramm wird das bei beliebigem <em>n</em> wohl nichts, gesucht ist die formale Darstellung als Quintupel (<em>S</em>, <em>s</em>₁, <em>Σ</em>, <em>δ</em>, <em>F</em>) (siehe <a href="https://forum.selfhtml.org/self/2019/jan/2/informatik-zum-jahresanfang/1739779#m1739779" rel="noopener noreferrer">Ursprungsposting</a>). Das Alphabet <em>Σ</em> ist klar, wie gehabt Ziffern 0 bis 9. Wie sieht die Zustandsmenge <em>S</em> aus? (Größe – Namen sind Schall und Rauch.) Und wie die Übergangsfunktion <em>δ</em>?</p> </blockquote> <p>Ich glaube, alle Zutaten wurden bereits im Thread zusammengetragen. Ab in den Topf damit, umgerührt – fertig ist die Suppe – äh der Automat.</p> <p>Eine Zahl lässt bei der Division durch <em>n</em> den Rest <em>r</em>, wobei 0 ≤ <em>r</em> < <em>n</em>. Es gibt also <em>n</em> <strong>Restklassen</strong> 0, 1, …, <em>n</em> − 1. Diese bilden wir beim Automaten durch <em>n</em> Zustände $$s_0, s_1, \ldots, s_{n-1}$$ ab. Der Automat soll sich im Zustand <em>sᵤ</em> befinden, wenn die bis dahin gelesene Zahl bei der Division durch <em>n</em> den Rest <em>u</em> lässt. Der Zustand <em>s</em>₀ steht für die Restklasse 0, d.h. wenn der Automat im Zustand <em>s</em>₀ ist, dann ist die eingelesene Zahl durch <em>n</em> teilbar. <em>s</em>₀ ist also der einzige Endzustand.</p> <p>Außerdem brauchen wir – wie wir am <a href="https://forum.selfhtml.org/self/2019/jan/2/informatik-zum-jahresanfang/1740262#m1740262" rel="noopener noreferrer">Beispiel mit der 3</a> gesehen haben (und am Beispiel mit der 9 nicht gesehen haben  ) – einen zusätzlichen Startzustand. Diesen bezeichne ich hinterlistigerweise mit <em>s</em>₋₀. Der ist genauso „verdrahtet“ wie <em>s</em>₀, d.h. für alle Eingaben <em>d</em> sind die Folgezustände für <em>s</em>₀ und <em>s</em>₋₀ jeweils gleich: <em>δ</em>(<em>s</em>₀, <em>d</em>) = <em>δ</em>(<em>s</em>₋₀, <em>d</em>).</p> <p>Wie sieht nun die Übergangsfunktion <em>δ</em> aus? Der Automat sei nach Einlesen der Eingabefolge $$d_{-k}, d_{-k+1}, \ldots, d_{-1}, d_0$$ (mit <em>dᵢ</em> ∈ <em>Σ</em> = {0, 1, …, 9}) – also der Zahl $$z_0 = d_{-k}d_{-k+1}…d_{-1}d_0$$ – im Zustand <em>sᵤ</em>. Das heißt <em>z</em>₀ ≡ <em>u</em> mod <em>n</em> oder, um noch eine weitere Schreibweise zu bemühen: <em>z</em>₀ mod <em>n</em> = <em>u</em>. (mod ist hier ein Operator; entspricht genau dem <code>%</code>-Operator in JavaScript.)</p> <p>Durch Einlesen der nächsten Ziffer <em>d</em>₁ entsteht die neue Zahl $$z_1 = d_{-k}d_{-k+1}…d_{-1}d_0d_1 = 10 z_0 + d_1$$. Für diese gilt:</p> <p><em><em><em>z</em>₁ = 10</em>z</em>₀ + <em>d</em>₁ ≡ 10<em>u</em> + <em>d</em>₁ ≡ v mod <em>n</em>** (mit 0 ≤ <em>v</em> < <em>n</em>)</p> <p>Das ist das ganze Geheimnis, deshalb spendiere ich hierfür Fettschrift und eine eigene Zeile. Anders gesagt: <em><em><em>v</em> = (10</em>u</em> + <em>d</em>₁) mod <em>n</em>** ist die Restklasse der neuen Zahl <em>z</em>₁; <em>sᵥ</em> ist der Folgezustand.</p> <p>Und weil die Rechnung für 0 und −0 dieselbe ist, hatte ich den Startzustand so benannt.</p> <p>Der Folgezustand <em>sᵥ</em> hängt also nur vom vorigen Zustand <em>sᵤ</em> und der Eingabe <em>d</em>₁ ab; die vorherigen Eingaben $$d_{-k}, d_{-k+1}, \ldots, d_{-1}, d_0$$ muss man dazu nicht kennen. Das ist genau der Grund, warum die Erkennung der Teilbarkeit durch <em>n</em> mit einem endlichen Automaten möglich ist; ein endlicher Automat hat ja kein „Gedächtnis“ für die Vergangenheit.</p> <ol> <li> <p>Ein Automat mit Gedächtnis wäre bspw. ein nichtdeterministischer Kellerautomat, welcher eine kontextfreie Sprache (Typ 2 in der <a href="https://de.wikipedia.org/wiki/Chomsky-Hierarchie" rel="nofollow noopener noreferrer">Chomsky-Hierarchie</a>) erkennt.</p> <p>Äquivalent dazu: Ein Ausdruck mit „Gedächtnis“ (<em lang="en">look-around assertions</em>) ist nicht regulär – auch wenn er fälschlicherweise „regulärer Ausdruck“ genannt wird.</p> </li> </ol> <p>Damit haben wir unsere Übergangsfunktion <em>δ</em>(<em>sᵤ</em>, <em>d</em>) = <em>sᵥ</em> mit <em>v</em> = (10<em>u</em> + <em>d</em>) mod <em>n</em>; und damit haben wir unseren Automaten:</p> <p>$$\left( S, s_{-0}, \Sigma, \delta, F \right) = \left( {s_{-0}, s_0, s_1, \ldots, s_{n-1}}, ;; s_{-0}, ;; {0, 1, \ldots, 9}, ;; \delta(s_u, d) = s_v \text{ mit } v = (10u + d) \bmod n, ;; {s_0} \right)$$</p> <p>LLAP </p> <p>Nachtrag: Der Automat ist nicht notwendigerweise minimal, d.h. es können evtl. Zustände zusammengefasst werden. Es steht die Vermutung im Raum, dass der Automat für <em>n</em> prim minimal ist und für <em>n</em> zusammengesetzt nicht.</p> <p>Nachtrag 2: dedlfix hatte schon <a href="https://forum.selfhtml.org/self/2019/jan/2/informatik-zum-jahresanfang/1740224#m1740224" rel="noopener noreferrer">einen Automaten vorgestellt</a>, der für einige <em>n</em> mit weniger als <em>n</em> + 1 Zuständen auskommt, aber auch nicht notwendigerweise minimal ist. Lässt sich jener auch so einfach formal beschreiben?</p> <div class="signature">-- <br> <em>„Wer durch Wissen und Erfahrung der Klügere ist, der sollte nicht nachgeben. Und nicht aufgeben.“</em> —Kurt Weidemann </div> Informatik zum Jahresanfang – noch mehr Teiler - Spoiler Mon, 07 Jan 19 13:31:04 Z https://forum.selfhtml.org/self/2019/jan/2/informatik-zum-jahresanfang/1740145#m1740145 https://forum.selfhtml.org/self/2019/jan/2/informatik-zum-jahresanfang/1740145#m1740145 <p>@@Matthias Apsel</p> <blockquote> <blockquote> <p>Baue einen endlichen Automaten, der eine durch <em>n</em> teilbare Zahl erkennt. Für den allgemeinen Fall soll die Einschränkung fallengelassen werden, dass es der Minimalautomat sein muss.</p> </blockquote> <p>Diese Aufgabe ist nicht lösbar.</p> <p>Du kannst höchstens für ein konkretes <em>n</em> einen Automaten bauen</p> </blockquote> <p>So ist die Aufgabe zu verstehen. So sollte die Aufgabe lösbar sein.</p> <blockquote> <p>nicht aber einen Automaten, der Teilbarkeit durch beliebige <em>n</em> erkennt.</p> </blockquote> <p>Wie hieß das im Matheunterricht immer: für beliebiges, aber festes <em>n</em>.</p> <p>LLAP </p> <div class="signature">-- <br> <em>„Wer durch Wissen und Erfahrung der Klügere ist, der sollte nicht nachgeben. Und nicht aufgeben.“</em> —Kurt Weidemann </div> Informatik zum Jahresanfang – noch mehr Teiler - Spoiler Mon, 07 Jan 19 13:32:04 Z https://forum.selfhtml.org/self/2019/jan/2/informatik-zum-jahresanfang/1740146#m1740146 https://forum.selfhtml.org/self/2019/jan/2/informatik-zum-jahresanfang/1740146#m1740146 <p>@@dedlfix</p> <blockquote> <p>Meinst du, die lassen sich mit weniger als 4 Zuständen realisieren?</p> </blockquote> <p>Nein.</p> <p>Meinst du, man bräuchte mehr?</p> <p>LLAP </p> <div class="signature">-- <br> <em>„Wer durch Wissen und Erfahrung der Klügere ist, der sollte nicht nachgeben. Und nicht aufgeben.“</em> —Kurt Weidemann </div> Informatik zum Jahresanfang – noch mehr Teiler - Spoiler Mon, 07 Jan 19 17:30:36 Z https://forum.selfhtml.org/self/2019/jan/2/informatik-zum-jahresanfang/1740173#m1740173 https://forum.selfhtml.org/self/2019/jan/2/informatik-zum-jahresanfang/1740173#m1740173 <p>Hallo Gunnar Bittersmann,</p> <blockquote> <blockquote> <p>Diese Aufgabe ist nicht lösbar.</p> <p>Du kannst höchstens für ein konkretes <em>n</em> einen Automaten bauen</p> </blockquote> <p>So ist die Aufgabe zu verstehen. So sollte die Aufgabe lösbar sein.</p> </blockquote> <p>Also sind es <em>n</em> Aufgaben. Jede einzelne ist lösbar. Wenn man sich von den Teilbarkeitsregeln löst (wie ich gestern schon schrieb [und bei <em>n</em> < 10 noch ein bisschen aufpassen muss], also war ich doch nicht zu vorschnell).</p> <blockquote> <blockquote> <p>nicht aber einen Automaten, der Teilbarkeit durch beliebige <em>n</em> erkennt.</p> </blockquote> <p>Wie hieß das im Matheunterricht immer: für beliebiges, aber festes <em>n</em>.</p> </blockquote> <p>Genau das geht aber nicht.</p> <p>Bis demnächst<br> Matthias</p> <div class="signature">-- <br> Pantoffeltierchen haben keine Hobbys. </div> Informatik zum Jahresanfang – noch mehr Teiler - Spoiler Mon, 07 Jan 19 13:40:17 Z https://forum.selfhtml.org/self/2019/jan/2/informatik-zum-jahresanfang/1740147#m1740147 https://forum.selfhtml.org/self/2019/jan/2/informatik-zum-jahresanfang/1740147#m1740147 <p>Tach!</p> <blockquote> <blockquote> <p>Meinst du, die lassen sich mit weniger als 4 Zuständen realisieren?</p> </blockquote> <p>Nein.</p> <p>Meinst du, man bräuchte mehr?</p> </blockquote> <p>Nein, ich denke, nach dem Prinzip, das ich (bisher nur) dir per PM in Ausführlichkeit beschrieben habe, sollte sich immer der jeweilige Minimalautomat bauen lassen. Deswegen betrachte ich die "Erstelle für Teiler x"-Aufgaben nur noch als Fleißaufgabe, weil es damit keine Herausforderung mehr ist.</p> <p>dedlfix.</p> Informatik zum Jahresanfang – noch mehr Teiler - Spoiler Mon, 07 Jan 19 15:22:25 Z https://forum.selfhtml.org/self/2019/jan/2/informatik-zum-jahresanfang/1740159#m1740159 https://forum.selfhtml.org/self/2019/jan/2/informatik-zum-jahresanfang/1740159#m1740159 <p>Hi,</p> <blockquote> <blockquote> <p>Meinst du, die lassen sich mit weniger als 4 Zuständen realisieren?</p> </blockquote> </blockquote> <p>für 3 komme ich auf 3 Zustände:</p> <pre><code class="block"> | | v #################### # # -- 0,3,6,9 - # x mod 3 = 0 # | # # <----------- #################### / ^ \ ^ / / \ \ 1,4,7 / 2,5,8 \ / 2,5,8 \ 1,4,7 / / \ \ v / v \ --------------- --------------- - 0,3,6,9 --| |-- 2,5,8 --->| |-- 0,3,6,9 - | | x mod 3 = 1 | | x mod 3 = 2 | | ----------->| |<-- 1,4,7 ---| |<----------- --------------- --------------- </code></pre> <p>Kann grad nix hochladen,daher ASCII art. ## für den Endzustand.</p> <p>cu,<br> Andreas a/k/a MudGuard</p> Informatik zum Jahresanfang – noch mehr Teiler - Spoiler Mon, 07 Jan 19 15:28:23 Z https://forum.selfhtml.org/self/2019/jan/2/informatik-zum-jahresanfang/1740161#m1740161 https://forum.selfhtml.org/self/2019/jan/2/informatik-zum-jahresanfang/1740161#m1740161 <p>Tach!</p> <blockquote> <blockquote> <blockquote> <p>Meinst du, die lassen sich mit weniger als 4 Zuständen realisieren?</p> </blockquote> </blockquote> <p>für 3 komme ich auf 3 Zustände:</p> </blockquote> <p>Wie ist denn die Zahl im Startzustand definiert? Ist sie null oder bereits 0?</p> <p>dedlfix.</p> Informatik zum Jahresanfang – noch mehr Teiler - Spoiler Mon, 07 Jan 19 15:29:26 Z https://forum.selfhtml.org/self/2019/jan/2/informatik-zum-jahresanfang/1740162#m1740162 https://forum.selfhtml.org/self/2019/jan/2/informatik-zum-jahresanfang/1740162#m1740162 <p>Hi,</p> <blockquote> <p>Wie ist denn die Zahl im Startzustand definiert? Ist sie null oder bereits 0?</p> </blockquote> <p>ja </p> <p>cu,<br> Andreas a/k/a MudGuard</p> Informatik zum Jahresanfang – noch mehr Teiler - Spoiler Mon, 07 Jan 19 22:33:43 Z https://forum.selfhtml.org/self/2019/jan/2/informatik-zum-jahresanfang/1740184#m1740184 https://forum.selfhtml.org/self/2019/jan/2/informatik-zum-jahresanfang/1740184#m1740184 <p>@@Matthias Apsel</p> <blockquote> <p>… also war ich doch nicht zu vorschnell).</p> <blockquote> <p>… für beliebiges, aber festes <em>n</em>.</p> </blockquote> <p>Genau das geht aber nicht.</p> </blockquote> <p>Ich hatte in Anspruch genommen, vorschnell zu sein und zu sagen, dass es für 7 nicht ginge.</p> <p>Du darfst gern in Anspruch nehmen, vorschnell zu sein und zu sagen, dass es für <em>n</em> nicht ginge. </p> <p>LLAP </p> <div class="signature">-- <br> <em>„Wer durch Wissen und Erfahrung der Klügere ist, der sollte nicht nachgeben. Und nicht aufgeben.“</em> —Kurt Weidemann </div> Informatik zum Jahresanfang – noch mehr Teiler - Spoiler Tue, 08 Jan 19 06:05:56 Z https://forum.selfhtml.org/self/2019/jan/2/informatik-zum-jahresanfang/1740191#m1740191 https://forum.selfhtml.org/self/2019/jan/2/informatik-zum-jahresanfang/1740191#m1740191 <p>Hallo Gunnar Bittersmann,</p> <blockquote> <p>Du darfst gern in Anspruch nehmen, vorschnell zu sein und zu sagen, dass es für <em>n</em> nicht ginge. </p> </blockquote> <p>Das widerspricht dem Prinzip des endlichen Automaten, der <em>endlich</em> heißt wegen der endlich vielen Zustände. Und bei beliebigem <em>n</em> musst du auch beliebig viele Zustände vorhalten.</p> <p>Bis demnächst<br> Matthias</p> <div class="signature">-- <br> Pantoffeltierchen haben keine Hobbys. </div> Informatik zum Jahresanfang – noch mehr Teiler - Spoiler Tue, 08 Jan 19 06:57:23 Z https://forum.selfhtml.org/self/2019/jan/2/informatik-zum-jahresanfang/1740193#m1740193 https://forum.selfhtml.org/self/2019/jan/2/informatik-zum-jahresanfang/1740193#m1740193 <p>@@Matthias Apsel</p> <blockquote> <p>Das widerspricht dem Prinzip des endlichen Automaten, der <em>endlich</em> heißt wegen der endlich vielen Zustände. Und bei beliebigem <em>n</em> musst du auch beliebig viele Zustände vorhalten.</p> </blockquote> <p>Ich glaube, wir haben eine unterschiedliche Vorstellung davon, was „beliebig“ bedeutet. Du darfst auch gerne „konkret“ dazu sagen (nur dass du halt nicht weißt, welchen konkreten Zahlenwert das <em>n</em> hat).</p> <p>„Beliebig, aber fest“ heißt: Wähle ein beliebiges <em>n</em>. Erstelle für dieses dann feste (konkrete) <em>n</em> den Automaten, der die Teilbarkeit durch dieses <em>n</em> erkennt.</p> <p>Dieser Automat braucht nicht beliebig viele Zustände, sondern eine bestimmte Anzahl in Abhängigkeit von <em>n</em>. (Hättest du ein anderes <em>n</em> gewählt, bräuchte der Automat eine andere Anzahl von Zuständen.)</p> <p>LLAP </p> <div class="signature">-- <br> <em>„Wer durch Wissen und Erfahrung der Klügere ist, der sollte nicht nachgeben. Und nicht aufgeben.“</em> —Kurt Weidemann </div> Informatik zum Jahresanfang – noch mehr Teiler Tue, 08 Jan 19 12:47:52 Z https://forum.selfhtml.org/self/2019/jan/2/informatik-zum-jahresanfang/1740224#m1740224 https://forum.selfhtml.org/self/2019/jan/2/informatik-zum-jahresanfang/1740224#m1740224 <p>Tach!</p> <blockquote> <blockquote> <p>Und wenn man einen 2er und einen 10er hinternander setzt, erhält man einen Automaten, der durch 20 teilbare Zahlen erkennt.</p> </blockquote> <p>Und wenn man zwei 10er hinternander setzt, erhält man einen Automaten, der durch 100 teilbare Zahlen erkennt. Das Diagramm ersparen wir uns. Wir sind zu höheren Zielen berufen.</p> </blockquote> <p>Auch der ensteht, wenn ich nach "meinem" Prinzip vorgehe, mit 9 plus 2 Zuständen. Allerdings konnte der Flaci den auf drei Zustände minimieren. Die Frage wäre also, warum das passieren kann. Hängt es mit dem Dezimalsystem zusammen?</p> <p>Hier mal die komplette Beschreibung <a href="https://forum.selfhtml.org/self/2019/jan/2/informatik-zum-jahresanfang/1740121#m1740121" rel="noopener noreferrer">"meines" Prinzips</a>:</p> <p>Für das Prinzip braucht man keine mathematischen Teilungsregeln zu kennen. Der erste Schritt ist, alle Zahlen von 0 bis exklusive 10 × (n + 1) aufzuschreiben, am besten in 10er-Gruppen. Also beim 3er Automaten bis 39, beim 6er bis 69, etc. Dann markiert man sich alle Vielfachen. Man sieht nun, welche 10er nach der 0 nicht markiert sind. Für diese erstellt man Zustände und nummeriert sie von 1 an aufwärts. Den Startzustand benennt man mit 0 und fügt dann noch einen finiten Zustand benannt mit E hinzu. Man braucht für Primzahlen n Zustände plus den E, bei Nicht-Primzahlen sind es weniger, weil Vielfache von ihnen durch 10 teilbar sind. Nun zeichnet man für alle Vielfachen (inklusive 0) bis zum 10-Fachen die Wege zum E ein. Dazu kommen noch die Wege, die von E auf sich selbst zeigen. Das ist auf alle Fälle die 0 und - bei allen n, die kleiner als 10 sind - alle Endziffern von Vielfachen bis zum nächsten Zehner. Also, beim 3er Automaten sind es 0, 3, 6 und 9 wegen 30, 33, 36 und 39, beim 6er sind es die 0 und 6 wegen 60 und 66. Anschließend wechselt man zur Übergangstabelle. Die Zustände sollten von 0 bis E untereinander stehen. Flaci sortiert sie aber nicht natürlich, weswegen Zustände >= 10 nicht richtig platziert sind. Jedenfalls hat man in der ersten Zeile den Zustand 0 (oder Startzustand) und da ist bereits bei Eingabe der Ziffer 0 (obere Reihe) ein E eingetragen. Dann fügt man nur noch aufsteigend mit 1 nach dem E beginnend alle Zustände ein. Wenn keiner mehr übrig ist, geht es mit 0 beginnend weiter. Es sei denn, es steht bereits ein E in dem Feld, dann geht es im darauf folgenden mit 1 weiter. Ist die Zeile voll, setzt man in der nächsten (numerisch aufsteigend) fort bis inklusive E-Zeile. Fertig ist der Automat.</p> <p>dedlfix.</p> Informatik zum Jahresanfang – noch mehr Teiler Wed, 09 Jan 19 13:27:40 Z https://forum.selfhtml.org/self/2019/jan/2/informatik-zum-jahresanfang/1740301#m1740301 https://forum.selfhtml.org/self/2019/jan/2/informatik-zum-jahresanfang/1740301#m1740301 <p>@@Gunnar Bittersmann</p> <blockquote> <p><img src="/images/c2ece82f-109f-46db-87a5-c98206ea9b0f.png" alt="" loading="lazy"></p> </blockquote> <p>Der minimale Automat für die Teilbarkeit durch 10<em>ⁿ</em> lässt sich auch einfach formal beschreiben:</p> <p>$$\begin{align} \text{Menge der Zustände:} \quad S &= {s_0, s_1, \ldots, s_n} <br> \text{Menge der Endzustände:} \quad F &= {s_n} <br> \text{Eingabealphabet:} \quad \Sigma &= {0, 1, 2, \ldots, 9} <br> \end{align}$$</p> <p><strong>[Ergänzung]</strong> Der Index des Zustands gibt die Anzahl der zuletzt in Folge gelesenen Nullen an.</p> <p>$$\text{Übergangsfunktion:} \quad \delta(s_i, d) = \begin{cases} s_{i+1} & \text{ für } d = 0 \text{ und } i < n <br> s_n & \text{ für } d = 0 \text{ und } i = n <br> s_0 & \text{ für } d \ne 0 <br> \end{cases}$$</p> <blockquote> <p>Das schwerste hieran war wohl, den Startpfeil richtig zu setzen.</p> </blockquote> <p>$$\text{Startzustand:} \quad s_{n-1}$$</p> <p>LLAP </p> <div class="signature">-- <br> <em>„Wer durch Wissen und Erfahrung der Klügere ist, der sollte nicht nachgeben. Und nicht aufgeben.“</em> —Kurt Weidemann </div> Informatik zum Jahresanfang – Auflösung der Zusatzaufgabe für 8 Tue, 08 Jan 19 12:51:04 Z https://forum.selfhtml.org/self/2019/jan/2/informatik-zum-jahresanfang/1740225#m1740225 https://forum.selfhtml.org/self/2019/jan/2/informatik-zum-jahresanfang/1740225#m1740225 <p>Tach!</p> <blockquote> <blockquote> <blockquote> <p>Darstellung analog zur dedlfixschen Gesichtsform beim 4er: ein keltisches Ornament?</p> <p><a href="/images/773f6cbb-5c25-4aeb-9d3a-06735c4706a3.jpeg" rel="noopener noreferrer"><img src="/images/773f6cbb-5c25-4aeb-9d3a-06735c4706a3.jpeg?size=medium" alt="" loading="lazy"></a></p> <p>(Fehlende Beschriftung gewollt, aber ich hab mal wieder keinen Startpfeil gemalt und der Übergang vom Endzustand zu sich selbst fehlt. Aber das würde nur die Symmetrie stören. )</p> </blockquote> <p>Denk mal dreidimensional. Der Bogen zeigt in Richtung Z-Achse, dann kannst du das Ding drehen, daran aufhängen, und 4 Kerzen in die Zustände stecken. So erhält man einen schönen Adventskranz für informatisch Interessierte.</p> </blockquote> <p><img src="/images/e96ecaa2-e0a4-4378-a09b-76bce3a4bafe.png" alt="" loading="lazy"></p> <p>(<a href="https://www.geogebra.org/3d/xusvmw99" rel="nofollow noopener noreferrer">3D-Modell</a>)</p> <p>Soll in die Mitte auch eine Kerze?</p> </blockquote> <p>Kaputt. Da fehlen die Selbst-Übergänge an allen Zuständen. Und wenn du nun den vom mittleren hinzufügen möchtest, hast du wieder das Symmetrie-Problem.</p> <p>dedlfix.</p> Informatik zum Jahresanfang – noch mehr Teiler Tue, 08 Jan 19 13:06:00 Z https://forum.selfhtml.org/self/2019/jan/2/informatik-zum-jahresanfang/1740227#m1740227 https://forum.selfhtml.org/self/2019/jan/2/informatik-zum-jahresanfang/1740227#m1740227 <p>@@dedlfix</p> <blockquote> <blockquote> <p>Und wenn man zwei 10er hinternander setzt, erhält man einen Automaten, der durch 100 teilbare Zahlen erkennt.</p> </blockquote> <p>Auch der ensteht, wenn ich nach "meinem" Prinzip vorgehe, mit 9 plus 2 Zuständen. Allerdings konnte der Flaci den auf drei Zustände minimieren.</p> </blockquote> <p>Bei der Million sind’s sieben Zustände. Allgemein: bei 10<em>ⁿ</em> sind’s <em>n</em> + 1. Bei 100 also 3.</p> <p>LLAP </p> <div class="signature">-- <br> <em>„Wer durch Wissen und Erfahrung der Klügere ist, der sollte nicht nachgeben. Und nicht aufgeben.“</em> —Kurt Weidemann </div> Informatik zum Jahresanfang – noch mehr Teiler Tue, 08 Jan 19 15:33:32 Z https://forum.selfhtml.org/self/2019/jan/2/informatik-zum-jahresanfang/1740231#m1740231 https://forum.selfhtml.org/self/2019/jan/2/informatik-zum-jahresanfang/1740231#m1740231 <p>Hallo dedlfix,</p> <p>uff, das habe ich jetzt auf Anhieb nicht verstanden. Meine Herleitung mit Modulo-Rechnung gefällt mir spontan besser :)</p> <p>Und der Argumentation hier:</p> <blockquote> <p>Man braucht für Primzahlen n Zustände plus den E, bei Nicht-Primzahlen sind es weniger, weil Vielfache von ihnen durch 10 teilbar sind.</p> </blockquote> <p>vertraue ich erstmal nicht. Es scheint mir eher so, dass bei Nichtprimzahlen sich die Werte der Übergangsfunktion bei unterschiedlichen Resten wiederholen (gerade mal mit der 6 durchgezogen, nach "meinem" Prinzip waren es Knoten R0 bis R5 (auf den separaten Startknoten hatte ich verzichtet), nach Optimierung hatte er die Knoten R1+R4 und R2+R5 zusammengefasst. R0 und R3 blieben separat, das hat er ordentlich herausbekommen.</p> <p><em>Rolf</em></p> <div class="signature">-- <br> sumpsi - posui - clusi </div> Informatik zum Jahresanfang – Auflösung der Zusatzaufgabe für 8 Tue, 08 Jan 19 13:00:51 Z https://forum.selfhtml.org/self/2019/jan/2/informatik-zum-jahresanfang/1740226#m1740226 https://forum.selfhtml.org/self/2019/jan/2/informatik-zum-jahresanfang/1740226#m1740226 <p>@@dedlfix</p> <blockquote> <blockquote> <p><img src="/images/e96ecaa2-e0a4-4378-a09b-76bce3a4bafe.png" alt="" loading="lazy"></p> </blockquote> <p>Kaputt. Da fehlen die Selbst-Übergänge an allen Zuständen.</p> </blockquote> <p>Nix kaputt. Die sind innerhalb der roten Kugeln. </p> <p>LLAP </p> <div class="signature">-- <br> <em>„Wer durch Wissen und Erfahrung der Klügere ist, der sollte nicht nachgeben. Und nicht aufgeben.“</em> —Kurt Weidemann </div> Informatik zum Jahresanfang – noch mehr Teiler - Spoiler Tue, 08 Jan 19 16:09:54 Z https://forum.selfhtml.org/self/2019/jan/2/informatik-zum-jahresanfang/1740234#m1740234 https://forum.selfhtml.org/self/2019/jan/2/informatik-zum-jahresanfang/1740234#m1740234 <p>Hallo Rolf B,</p> <blockquote> <p>Ich bin total perplex, das hatte ich für unmöglich gehalten.</p> </blockquote> <p>Ja das passt. Um die Restklassen modulo <em>n</em> zu bestimmen, kannst du so vorgehen: Multipliziere die erste Ziffer mit 10 mod <em>n</em> addiere die zweite. Bilde die Restklasse und fahre fort.</p> <p>Für <em>n</em> > 10 ist 10 mod <em>n</em> = 10, deshalb hatte es letzte Woche mit dem 7er Automaten nicht funktioniert (Stichwort: vorschnell)</p> <p>Btw. k ≡ n(mod37) schreibt man k ≡ n(37)</p> <p>Beispiel bestimme den Rest, den 12345 bei Division durch 119 lässt.</p> <pre><code class="block">1 × 10 + 2 = 12 ≡ 12(119) 12 × 10 + 3 = 123 ≡ 4(119) 4 * 10 + 4 = 44 ≡ 44(119) 44 * 10 + 5 = 445 ≡ 88(119) </code></pre> <p>Bis demnächst<br> Matthias</p> <div class="signature">-- <br> Pantoffeltierchen haben keine Hobbys. </div> Informatik zum Jahresanfang – noch mehr Teiler Tue, 08 Jan 19 15:58:45 Z https://forum.selfhtml.org/self/2019/jan/2/informatik-zum-jahresanfang/1740233#m1740233 https://forum.selfhtml.org/self/2019/jan/2/informatik-zum-jahresanfang/1740233#m1740233 <p>Tach!</p> <blockquote> <p>uff, das habe ich jetzt auf Anhieb nicht verstanden. Meine Herleitung mit Modulo-Rechnung gefällt mir spontan besser :)</p> </blockquote> <p>Das hat auch erstmal nicht viel mit Verstehen im wissenschaftlichen Sinne zu tun, sondern war mehr eine Anleitung zum Erstellen der Zustände und dem Ausfüllen der Übergangstabelle im Flaci. Ich habe diese Regelmäßigkeit nicht gefunden, weil ich mathematisch an die Sache rangegangen bin, sondern weil ich Regelmäßigkeiten einerseits optisch in der Exceltabelle für die teilbaren Zahlen (hier am Beispiel der 6)</p> <p><a href="/images/bdb08574-5f9f-4ada-ac45-154598c3f809.png" rel="noopener noreferrer"><img src="/images/bdb08574-5f9f-4ada-ac45-154598c3f809.png?size=medium" alt="" loading="lazy"></a></p> <p>als auch beim Erstellen der Übergangstabelle gesehen habe.</p> <blockquote> <p>Und der Argumentation hier:</p> <blockquote> <p>Man braucht für Primzahlen n Zustände plus den E, bei Nicht-Primzahlen sind es weniger, weil Vielfache von ihnen durch 10 teilbar sind.</p> </blockquote> <p>vertraue ich erstmal nicht. Es scheint mir eher so, dass bei Nichtprimzahlen sich die Werte der Übergangsfunktion bei unterschiedlichen Resten wiederholen</p> </blockquote> <p>Die Positionen der teilbaren Zahlen wiederholen sich (bei der 6) ab Spalte D.</p> <blockquote> <p>(gerade mal mit der 6 durchgezogen, nach "meinem" Prinzip waren es Knoten R0 bis R5 (auf den separaten Startknoten hatte ich verzichtet), nach Optimierung hatte er die Knoten R1+R4 und R2+R5 zusammengefasst. R0 und R3 blieben separat, das hat er ordentlich herausbekommen.</p> </blockquote> <p>Dass die Optimierung am Ende auf dasselbe Ergebnis kommt, wie es unterschiedliche Spaltenmuster gibt, kann kein Zufall sein. Ich habe jedenfalls gesehen, dass die Wiederholung an der ersten Teilbarkeit durch 10 beginnt (jedenfalls bei den von mir untersuchten Zahlen).</p> <p>dedlfix.</p> Informatik zum Jahresanfang – noch mehr Teiler - Spoiler Tue, 08 Jan 19 16:56:13 Z https://forum.selfhtml.org/self/2019/jan/2/informatik-zum-jahresanfang/1740236#m1740236 https://forum.selfhtml.org/self/2019/jan/2/informatik-zum-jahresanfang/1740236#m1740236 <p>Hallo Matthias,</p> <blockquote> <p>Btw. k ≡ n(mod37) schreibt man k ≡ n(37)</p> </blockquote> <p>Ich nicht. Mit Restklassenrechnung bin ich nie wirklich warm geworden, aber wenn ich was drüber gelesen habe, dann immer mit $$a \equiv b \pmod c$$. Unser MathJax hier übrigens auch: Da schrieb ich <code>$$a \equiv b \pmod c$$</code>. Seit wann verwendet wer deine Notation?</p> <p>Aber dein Verfahren ist dem Augenschein nach anders als meins. Da muss ich mir erstmal überlegen, weshalb das Ergebnis äquivalent ist. Das wird jetzt wieder dauern.</p> <p><em>Rolf</em></p> <div class="signature">-- <br> sumpsi - posui - clusi </div> Informatik zum Jahresanfang – noch mehr Teiler - Spoiler Tue, 08 Jan 19 18:34:53 Z https://forum.selfhtml.org/self/2019/jan/2/informatik-zum-jahresanfang/1740250#m1740250 https://forum.selfhtml.org/self/2019/jan/2/informatik-zum-jahresanfang/1740250#m1740250 <p>Hallo Matthias Apsel,</p> <p>Übrigens, weil 10 ≡ 1(3) und 10 ≡ 1(9) gilt, lauten die Teilbarkeitsregeln für 3 und 9 wie sie eben lauten (Quersumme).</p> <p>Bis demnächst<br> Matthias</p> <div class="signature">-- <br> Pantoffeltierchen haben keine Hobbys. </div> Informatik zum Jahresanfang – noch mehr Teiler - Spoiler Tue, 08 Jan 19 17:18:04 Z https://forum.selfhtml.org/self/2019/jan/2/informatik-zum-jahresanfang/1740239#m1740239 https://forum.selfhtml.org/self/2019/jan/2/informatik-zum-jahresanfang/1740239#m1740239 <p>Hallo Rolf B,</p> <blockquote> <p>Ich nicht. Mit Restklassenrechnung bin ich nie wirklich warm geworden, aber wenn ich was drüber gelesen habe, dann immer mit $$a \equiv b \pmod c$$. Unser MathJax hier übrigens auch: Da schrieb ich <code>$$a \equiv b \pmod c$$</code>. Seit wann verwendet wer deine Notation?</p> </blockquote> <p>keine Ahnung, vielleicht ist meine Notation doch nicht korrekt.</p> <blockquote> <p>Aber dein Verfahren ist dem Augenschein nach anders als meins. Da muss ich mir erstmal überlegen, weshalb das Ergebnis äquivalent ist. Das wird jetzt wieder dauern.</p> </blockquote> <p>Na so anders ist es doch nicht. Für die 7:</p> <p>Ermittle den Rest, den 98765 bei Division durch 7 lässt: 10 ≡ 3(7), also muss immer mit 3 multipliziert werden</p> <pre><code class="block">9 ≡ 2(7) 2 × 3 + 8 = 14 ≡ 0(7) 0 × 3 + 7 = 7 ≡ 0(7) 0 × 3 + 6 = 6 ≡ 6(7) 6 x 3 + 5 = 23 ≡ 2(7) </code></pre> <p>Bis demnächst<br> Matthias</p> <div class="signature">-- <br> Pantoffeltierchen haben keine Hobbys. </div> Informatik zum Jahresanfang – noch mehr Teiler - Spoiler Tue, 08 Jan 19 17:20:36 Z https://forum.selfhtml.org/self/2019/jan/2/informatik-zum-jahresanfang/1740240#m1740240 https://forum.selfhtml.org/self/2019/jan/2/informatik-zum-jahresanfang/1740240#m1740240 <p>Hallo Matthias Apsel,</p> <blockquote> <p>keine Ahnung, vielleicht ist meine Notation doch nicht korrekt.</p> </blockquote> <p>Puh. <a href="https://de.wikipedia.org/wiki/Kongruenz_(Zahlentheorie)#Schreibweise" rel="nofollow noopener noreferrer">https://de.wikipedia.org/wiki/Kongruenz_(Zahlentheorie)#Schreibweise</a></p> <p>Bis demnächst<br> Matthias</p> <div class="signature">-- <br> Pantoffeltierchen haben keine Hobbys. </div> Informatik zum Jahresanfang – Auflösung für 9 Tue, 08 Jan 19 23:27:38 Z https://forum.selfhtml.org/self/2019/jan/2/informatik-zum-jahresanfang/1740263#m1740263 https://forum.selfhtml.org/self/2019/jan/2/informatik-zum-jahresanfang/1740263#m1740263 <p>@@Gunnar Bittersmann</p> <blockquote> <p><img src="/images/5f87c392-0401-47fe-9f42-609aa84c1af2.png" alt="" loading="lazy"></p> <blockquote> <p>Und wenn man den hat …</p> </blockquote> </blockquote> <p>Analog zum 3er gibt’s auch bei der Teilbarkeit durch 9 einen Ring, in dem man mit 1 in den jeweils nächsten Zustand in eine Richtung (in meinem Diagramm in Uhrzeigerrichtung) kommt und mit 9 − 1 = 8 in die andere. Mit 0 und 9 verbleibt man im jeweiligen Zustand; mit den anderen Ziffern nimmt man Abkürzungen über die Diagonalen:</p> <p><img src="/images/5bf0613a-7a6a-46c3-b000-40819b672f0b.png" alt="" loading="lazy"></p> <p>(Die nahe am Zustand stehenden Symbole geben die Richtung an, wie man aus dem Zustand rauskommt; die Pfeile und doppelten Linien hab ich gespart.)</p> <p>‚Aber Gunnar‘, werdet ihr sagen, ‚Anfangs- und Endzustand müssen doch aufgedröselt sein!‘</p> <p><em>„Marty, du musst vierdimensional denken!“</em> Hier reicht eine weniger, wie dedlfix sagte: „Denk mal dreidimensional.“</p> <p>Hab ich gemacht und in 3D gezeichnet: Anfangs- und Endzustand befinden sich in der Projektion genau hintereinander und damit überlappen sich auch ihre Verbindungen zu den anderen Zuständen und deren identischen Beschriftungen! (Die Ausrede konnte ich nicht an andere verschenken, die brauchte ich für mich selber.)</p> <p>Das Neuneck mit Diagonalen hatte ich eigentlich für die Teilbarkeit durch 16 angedacht. Es liegt die Vermutung nahe, dass ein Automat dafür 9 Zustände braucht. Allgemein: 2<em>ⁿ</em>⁻¹ + 1 Zustände für die Teilbarkeit durch 2<em>ⁿ</em>.</p> <p>Da ich faul bin, hatte ich nach einer Grafik eines Neunecks mit Diagonalen gesucht, aber nur eine in einer Auflösung unter 200 × 200 Pixel gefunden. Also selber machen. Da ich faul bin: machen lassen – von einem Script. Und dabei <a href="https://twitter.com/g16n/status/1082278010089365504" rel="nofollow noopener noreferrer">wieder was gelernt</a>: <code class="language-js bad"><span class="token function">createElement</span><span class="token punctuation">(</span><span class="token string">'path'</span><span class="token punctuation">)</span></code> geht nicht; es muss <code class="language-js good"><span class="token function">createElementNS</span><span class="token punctuation">(</span><span class="token string">'http://www.w3.org/2000/svg'</span><span class="token punctuation">,</span> <span class="token string">'path'</span><span class="token punctuation">)</span></code> mit Angabe des SVG-Namensraums sein.</p> <p>(<a href="https://bittersmann.de/test/nonagon/nonagon.svg" rel="nofollow noopener noreferrer">Neuneck als SVG</a> und <a href="https://bittersmann.de/test/nonagon/nonagon.html" rel="nofollow noopener noreferrer">als in HTML eingebettetes SVG</a>)</p> <p>LLAP </p> <div class="signature">-- <br> <em>„Wer durch Wissen und Erfahrung der Klügere ist, der sollte nicht nachgeben. Und nicht aufgeben.“</em> —Kurt Weidemann </div> Informatik zum Jahresanfang – Auflösung für 9 Tue, 08 Jan 19 23:53:28 Z https://forum.selfhtml.org/self/2019/jan/2/informatik-zum-jahresanfang/1740264#m1740264 https://forum.selfhtml.org/self/2019/jan/2/informatik-zum-jahresanfang/1740264#m1740264 <p>Tach!</p> <blockquote> <p>‚Aber Gunnar‘, werdet ihr sagen, ‚Anfangs- und Endzustand müssen doch aufgedröselt sein!‘</p> <p><em>„Marty, du musst vierdimensional denken!“</em> Hier reicht eine weniger, wie dedlfix sagte: „Denk mal dreidimensional.“</p> <p>Hab ich gemacht und in 3D gezeichnet: Anfangs- und Endzustand befinden sich in der Projektion genau hintereinander und damit überlappen sich auch ihre Verbindungen zu den anderen Zuständen und deren identischen Beschriftungen! (Die Ausrede konnte ich nicht an andere verschenken, die brauchte ich für mich selber.)</p> </blockquote> <p>Geht nicht. Wenn es mehrere Ebenen gibt, kann man die nicht durch zeichnerische Projektion eliminieren. An dieser Stelle gibt es keine künstlerische Freiheit. Oder kannst du diesen Automaten bauen, ohne Speicher für einen weiteren Zustand zu verwenden?</p> <p>dedlfix.</p> Informatik zum Jahresanfang – Auflösung für 9 Wed, 09 Jan 19 12:18:03 Z https://forum.selfhtml.org/self/2019/jan/2/informatik-zum-jahresanfang/1740299#m1740299 https://forum.selfhtml.org/self/2019/jan/2/informatik-zum-jahresanfang/1740299#m1740299 <p>@@Gunnar Bittersmann</p> <blockquote> <p>Das Neuneck mit Diagonalen hatte ich eigentlich für die Teilbarkeit durch 16 angedacht.</p> </blockquote> <p>Was auch ’ne faule Ausrede ist.</p> <blockquote> <p>Da ich faul bin: machen lassen – von einem Script.</p> </blockquote> <p>Eben. Einfach in selbigem bei <code class="language-js"><span class="token keyword">const</span> n <span class="token operator">=</span> <span class="token number">9</span><span class="token punctuation">;</span></code> (ich bin ja nicht ganz doof ) die <code class="language-js"><span class="token number">9</span></code> durch <code class="language-js"><span class="token number">10</span></code> ersetzt und schon generiert es ein Dekagon mit all seinen Diagonalen.</p> <p>LLAP </p> <div class="signature">-- <br> <em>„Wer durch Wissen und Erfahrung der Klügere ist, der sollte nicht nachgeben. Und nicht aufgeben.“</em> —Kurt Weidemann </div> Informatik zum Jahresanfang – Auflösung für 9 Wed, 09 Jan 19 00:31:45 Z https://forum.selfhtml.org/self/2019/jan/2/informatik-zum-jahresanfang/1740265#m1740265 https://forum.selfhtml.org/self/2019/jan/2/informatik-zum-jahresanfang/1740265#m1740265 <p>@@dedlfix</p> <blockquote> <blockquote> <p>Hab ich gemacht und in 3D gezeichnet: Anfangs- und Endzustand befinden sich in der Projektion genau hintereinander und damit überlappen sich auch ihre Verbindungen zu den anderen Zuständen und deren identischen Beschriftungen! (Die Ausrede konnte ich nicht an andere verschenken, die brauchte ich für mich selber.)</p> </blockquote> <p>Geht nicht.</p> </blockquote> <p>Oh, schade.</p> <blockquote> <p>Wenn es mehrere Ebenen gibt, kann man die nicht durch zeichnerische Projektion eliminieren.</p> </blockquote> <p>Moment, wieso geht nicht?</p> <p>Einen Schritt zur Seite und es sieht so aus:</p> <p><img src="/images/2bf81ffe-f34d-4b01-9473-312eb26336ac.png" alt="" loading="lazy"></p> <p>LLAP </p> <div class="signature">-- <br> <em>„Wer durch Wissen und Erfahrung der Klügere ist, der sollte nicht nachgeben. Und nicht aufgeben.“</em> —Kurt Weidemann </div> Informatik zum Jahresanfang – Auflösung für n Wed, 09 Jan 19 10:51:10 Z https://forum.selfhtml.org/self/2019/jan/2/informatik-zum-jahresanfang/1740296#m1740296 https://forum.selfhtml.org/self/2019/jan/2/informatik-zum-jahresanfang/1740296#m1740296 <p>@@Gunnar Bittersmann</p> <blockquote> <p>Nachtrag: Der Automat ist nicht notwendigerweise minimal, d.h. es können evtl. Zustände zusammengefasst werden. Es steht die Vermutung im Raum, dass der Automat für <em>n</em> prim minimal ist und für <em>n</em> zusammengesetzt nicht.</p> </blockquote> <p>Ich hätte nicht so vorschnell einen Nachtrag schreiben sollen. Das ist natürlich Unsinn, wie wir am Beispiel mit der 9 (nicht ) gesehen haben. Obwohl 9 nicht prim ist, lässt sich der Automat nicht auf weniger als 9 + 1 Zustände reduzieren.</p> <p>Ich werfe mal eine andere Vermutung in den Raum: Der Automat lässt sich genau dann auf weniger als <em>n</em> + 1 Zustände reduzieren, wenn <em>n</em> durch 2 oder 5 teilbar ist. (Was die Teiler der 10, der Basis unseres Zahlensystems, sind.)</p> <p>LLAP </p> <div class="signature">-- <br> <em>„Wer durch Wissen und Erfahrung der Klügere ist, der sollte nicht nachgeben. Und nicht aufgeben.“</em> —Kurt Weidemann </div> Informatik zum Jahresanfang – Auflösung für n Sat, 19 Jan 19 12:39:06 Z https://forum.selfhtml.org/self/2019/jan/2/informatik-zum-jahresanfang/1740975#m1740975 https://forum.selfhtml.org/self/2019/jan/2/informatik-zum-jahresanfang/1740975#m1740975 <p>@@Gunnar Bittersmann</p> <blockquote> <p>… und damit haben wir unseren Automaten:</p> <p>$$\left( S, s_{-0}, \Sigma, \delta, F \right) = \left( {s_{-0}, s_0, s_1, \ldots, s_{n-1}}, ;; s_{-0}, ;; {0, 1, \ldots, 9}, ;; \delta(s_u, d) = s_v \text{ mit } v = (10u + d) \bmod n, ;; {s_0} \right)$$</p> </blockquote> <p>FWIW, ich hab das Ding mal in JavaScript implementiert. Na, nicht genau den Automaten, der die Teilbarkeit durch einen (den) Endzustand anzeigt, sondern einen, der bei jeder Eingabe „teilbar“ (W wie wahr) bzw. „nicht teilbar“ (F fie falsch) ausgibt – wie irgendwo in den Untiefen dieses Threads schon mal erwähnt. Da die Ausgabe zu einer Eingabe erfolgt, muss man dann nicht zwischen den Zuständen <em>s</em>₋₀ und <em>s</em>₀ unterscheiden und der Automat kommt mit <em>n</em> Zuständen aus.</p> <p>$$\begin{align} \text{Zustandsmenge:} &\ S = {s_0, s_1, \ldots, s_{n-1}} <br> \text{Startzustand:} &\ s_0 <br> \text{Eingabealphabet:} &\ \Sigma = {0, 1, \ldots, 9} <br> \text{Ausgabealphabet:} &\ \Gamma = {\mathrm W, \mathrm F} <br> \text{Übergangsfunktion:} &\ \delta(s_u, d) = s_v \text{ mit } v = (10u + d) \bmod n <br> \text{Ausgabefunktion:} &\ \omega(s_u, d) = \begin{cases} \mathrm W,& \text{wenn } \delta(s_u, d) = s_0, \text{ d.h. wenn } v = (10u + d) \bmod n = 0 <br> \mathrm F,& \text{sonst} \end{cases} \end{align}$$</p> <pre><code class="block language-javascript"><span class="token keyword">class</span> <span class="token class-name">DivisibilityFSA</span> <span class="token punctuation">{</span> n<span class="token punctuation">;</span> currentState <span class="token operator">=</span> <span class="token number">0</span><span class="token punctuation">;</span> inputAlphabet <span class="token operator">=</span> <span class="token punctuation">[</span><span class="token number">0</span><span class="token punctuation">,</span><span class="token number">1</span><span class="token punctuation">,</span><span class="token number">2</span><span class="token punctuation">,</span><span class="token number">3</span><span class="token punctuation">,</span><span class="token number">4</span><span class="token punctuation">,</span><span class="token number">5</span><span class="token punctuation">,</span><span class="token number">6</span><span class="token punctuation">,</span><span class="token number">7</span><span class="token punctuation">,</span><span class="token number">8</span><span class="token punctuation">,</span><span class="token number">9</span><span class="token punctuation">]</span><span class="token punctuation">;</span> <span class="token function">constructor</span><span class="token punctuation">(</span><span class="token parameter">n</span><span class="token punctuation">)</span> <span class="token punctuation">{</span> <span class="token keyword">this</span><span class="token punctuation">.</span>n <span class="token operator">=</span> n<span class="token punctuation">;</span> <span class="token punctuation">}</span> <span class="token function-variable function">transition</span> <span class="token operator">=</span> <span class="token parameter">input</span> <span class="token operator">=></span> <span class="token keyword">this</span><span class="token punctuation">.</span>inputAlphabet<span class="token punctuation">.</span><span class="token function">includes</span><span class="token punctuation">(</span>input<span class="token punctuation">)</span> <span class="token operator">?</span> <span class="token operator">!</span><span class="token punctuation">(</span><span class="token keyword">this</span><span class="token punctuation">.</span>currentState <span class="token operator">=</span> <span class="token punctuation">(</span><span class="token number">10</span> <span class="token operator">*</span> <span class="token keyword">this</span><span class="token punctuation">.</span>currentState <span class="token operator">+</span> input<span class="token punctuation">)</span> <span class="token operator">%</span> <span class="token keyword">this</span><span class="token punctuation">.</span>n<span class="token punctuation">)</span> <span class="token operator">:</span> <span class="token keyword">undefined</span><span class="token punctuation">;</span> <span class="token punctuation">}</span> </code></pre> <p>In der Kürze liegt die Würze: Eine Zuweisung liefert einen Wert (nämlich den zugewiesenen).<br> Wenn also für den Index des Folgezustands, d.h. die Restklasse <code class="language-js"><span class="token punctuation">(</span><span class="token number">10</span> <span class="token operator">*</span> <span class="token keyword">this</span><span class="token punctuation">.</span>currentState <span class="token operator">+</span> input<span class="token punctuation">)</span> <span class="token operator">%</span> <span class="token keyword">this</span><span class="token punctuation">.</span>n</code> die <em lang="en">falsy</em> 0 rauskommt, wird durch die Negation <code class="language-js"><span class="token boolean">true</span></code> zurückgegeben (d.h. „teilbar“).<br> Kommt ein anderer, ein <em lang="en">truthy</em> Wert von 1 bis <em>n</em> − 1 raus, dann <code class="language-js"><span class="token boolean">false</span></code> („nicht teilbar“).</p> <p>Und das nur, wenn die Eingabe aus dem Eingabealphabet ist, ansonsten kommt <code class="language-js"><span class="token keyword">undefined</span></code> zurück. Oder wäre <code class="language-js"><span class="token keyword">null</span></code> passender?</p> <p>7er Automat (❤️):</p> <pre><code class="block language-javascript"><span class="token keyword">const</span> fsa <span class="token operator">=</span> <span class="token keyword">new</span> <span class="token class-name">DivisibilityFSA</span><span class="token punctuation">(</span><span class="token number">7</span><span class="token punctuation">)</span><span class="token punctuation">;</span> console<span class="token punctuation">.</span><span class="token function">log</span><span class="token punctuation">(</span> fsa<span class="token punctuation">.</span><span class="token function">transition</span><span class="token punctuation">(</span><span class="token number">9</span><span class="token punctuation">)</span> <span class="token punctuation">)</span><span class="token punctuation">;</span> <span class="token comment">// false – 9 ist nicht durch 7 teilbar</span> console<span class="token punctuation">.</span><span class="token function">log</span><span class="token punctuation">(</span> fsa<span class="token punctuation">.</span><span class="token function">transition</span><span class="token punctuation">(</span><span class="token number">8</span><span class="token punctuation">)</span> <span class="token punctuation">)</span><span class="token punctuation">;</span> <span class="token comment">// true – 98 ist durch 7 teilbar</span> console<span class="token punctuation">.</span><span class="token function">log</span><span class="token punctuation">(</span> fsa<span class="token punctuation">.</span><span class="token function">transition</span><span class="token punctuation">(</span><span class="token number">7</span><span class="token punctuation">)</span> <span class="token punctuation">)</span><span class="token punctuation">;</span> <span class="token comment">// true – 987 ist durch 7 teilbar</span> console<span class="token punctuation">.</span><span class="token function">log</span><span class="token punctuation">(</span> fsa<span class="token punctuation">.</span><span class="token function">transition</span><span class="token punctuation">(</span><span class="token number">6</span><span class="token punctuation">)</span> <span class="token punctuation">)</span><span class="token punctuation">;</span> <span class="token comment">// false – 9876 ist nicht durch 7 teilbar</span> </code></pre> <p>Mit <code class="language-js"><span class="token keyword">new</span> <span class="token class-name">DivisibilityFSA</span><span class="token punctuation">(</span><span class="token number">13</span><span class="token punctuation">)</span></code> schlägt’s dreizehn. <a href="https://codepen.io/gunnarbittersmann/pen/VqoamX?editors=0011" rel="noopener noreferrer">Zum Rumspielen</a></p> <p>Ich dachte, man könnte <code class="language-js">currentState</code> und <code class="language-js">inputAlphabet</code> durch vorangestelltes <code>#</code> privat machen, aber da spielt CodePen nicht mit?</p> <p>LLAP </p> <div class="signature">-- <br> <em>„Wer durch Wissen und Erfahrung der Klügere ist, der sollte nicht nachgeben. Und nicht aufgeben.“</em> —Kurt Weidemann </div> Informatik zum Jahresanfang – Auflösung für n Tue, 22 Jan 19 14:08:07 Z https://forum.selfhtml.org/self/2019/jan/2/informatik-zum-jahresanfang/1741305#m1741305 https://forum.selfhtml.org/self/2019/jan/2/informatik-zum-jahresanfang/1741305#m1741305 <p>@@Gunnar Bittersmann</p> <blockquote> <p>Ich werfe mal eine andere Vermutung in den Raum: Der Automat lässt sich genau dann auf weniger als <em>n</em> + 1 Zustände reduzieren, wenn <em>n</em> durch 2 oder 5 teilbar ist. (Was die Teiler der 10, der Basis unseres Zahlensystems, sind.)</p> </blockquote> <p>So sieht’s wohl aus.</p> <p>Die Übergangstabelle mal am Beispiel für unseren Lieblingsautomaten, den ❤️ 7er:</p> <p>Die Zeile für <em>s</em>₀ ist eine Kopie der Zeile für <em>s</em>₋₀ wegen δ(<em>s</em>₋₀, d) = δ(<em>s</em>₀, d)</p> <p>| δ | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |---| | <strong><em>s</em>₀</strong> | <em>s</em>₀ | <em>s</em>₁ | <em>s</em>₂ | <em>s</em>₃ | <em>s</em>₄ | <em>s</em>₅ | <em>s</em>₆ | <em>s</em>₀ | <em>s</em>₁ | <em>s</em>₂</p> <p>und muss im Weiteren nicht betrachtet werden.</p> <p>| δ | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |---| | <strong><em>s</em>₋₀</strong> | <em>s</em>₀ | <em>s</em>₁ | <em>s</em>₂ | <em>s</em>₃ | <em>s</em>₄ | <em>s</em>₅ | <em>s</em>₆ | <em>s</em>₀ | <em>s</em>₁ | <em>s</em>₂ | <strong><em>s</em>₁</strong> | <em>s</em>₃ | <em>s</em>₄ | <em>s</em>₅ | <em>s</em>₆ | <em>s</em>₀ | <em>s</em>₁ | <em>s</em>₂ | <em>s</em>₃ | <em>s</em>₄ | <em>s</em>₅ | <strong><em>s</em>₂</strong> | <em>s</em>₆ | <em>s</em>₀ | <em>s</em>₁ | <em>s</em>₂ | <em>s</em>₃ | <em>s</em>₄ | <em>s</em>₅ | <em>s</em>₆ | <em>s</em>₀ | <em>s</em>₁ | <strong><em>s</em>₃</strong> | <em>s</em>₂ | <em>s</em>₃ | <em>s</em>₄ | <em>s</em>₅ | <em>s</em>₆ | <em>s</em>₀ | <em>s</em>₁ | <em>s</em>₂ | <em>s</em>₃ | <em>s</em>₄ | <strong><em>s</em>₄</strong> | <em>s</em>₅ | <em>s</em>₆ | <em>s</em>₀ | <em>s</em>₁ | <em>s</em>₂ | <em>s</em>₃ | <em>s</em>₄ | <em>s</em>₅ | <em>s</em>₆ | <em>s</em>₀ | <strong><em>s</em>₅</strong> | <em>s</em>₁ | <em>s</em>₂ | <em>s</em>₃ | <em>s</em>₄ | <em>s</em>₅ | <em>s</em>₆ | <em>s</em>₀ | <em>s</em>₁ | <em>s</em>₂ | <em>s</em>₃ | <strong><em>s</em>₆</strong> | <em>s</em>₄ | <em>s</em>₅ | <em>s</em>₆ | <em>s</em>₀ | <em>s</em>₁ | <em>s</em>₂ | <em>s</em>₃ | <em>s</em>₄ | <em>s</em>₅ | <em>s</em>₆</p> <p>Von δ(<em>s</em>₋₀, 0) ausgehend werden die Felder fortlaufend mit <em>s</em>₀ bis <em>s</em>₆ gefüllt, dann geht’s wieder bei <em>s</em>₀ los u.s.w. u.s.f.</p> <p></p> <p>Das gilt auch allgemein für alle <em>n</em>. In einer Zeile sieht’s so aus:</p> <p>Sei <em>v</em> der Index des Folgezustands für den Zustand <em>sᵤ</em> und die Eingabe <em>d</em>: <em>v</em> = (10<em>u</em> + <em>d</em>) mod <em>n</em>.</p> <p>Dann gilt für den Index <em>w</em> des Folgezustands für <em>sᵤ</em> und die Eingabe <em>d</em> + 1 (wobei <em>d</em> ≠ 9):<br> <em>w</em> = (10<em>u</em> + <em>d</em> + 1) mod <em>n</em> = ((10<em>u</em> + <em>d</em>) mod n + 1) mod <em>n</em> = (<em>v</em> + 1) mod <em>n</em>.</p> <p><em>w</em> ist also der Nachfolger von <em>v</em> modulo <em>n</em>, d.h. $$w = \begin{cases} v + 1, & \text{wenn } v + 1 < n <br> 0, & \text{sonst} \end{cases}$$</p> <p>Am Zeilenende sieht’s so aus:</p> <p>Sei <em>v</em> wieder der Index des Folgezustands für den Zustand <em>sᵤ</em> und die Eingabe 9: <em>v</em> = (10<em>u</em> + 9) mod <em>n</em>.</p> <p>Dann gilt für den Index <em>w</em> des Folgezustands für <em>sᵤ</em>₊₁ und die Eingabe 0 (wobei <em>u</em> ≠ <em>n</em> − 1):<br> <em>w</em> = (10(<em>u</em> + 1) + 0) mod <em>n</em> = (10<em>u</em> + 10) mod <em>n</em> = (10<em>u</em> + 9 + 1) mod <em>n</em> = (<em>v</em> + 1) mod <em>n</em>.</p> <p>Auch hier ist <em>w</em> ist der Nachfolger von <em>v</em> modulo <em>n</em>.</p> <p>Das heißt: die Tabellenfelder (<em>n</em> Zeilen à 10 Spalten) werden fortlaufend mit <em>s</em>₀ bis $$s_{n-1}$$ gefüllt, dann geht’s wieder bei <em>s</em>₀ los u.s.w. u.s.f. Insgesamt sind es 10 Wiederholungen der Folge <em>s</em>₀, <em>s</em>₁, …, $$s_{n-1}$$.</p> <p>Wenn nun die Anzahl der Zeilen und die Anzahl der Spalten (also <em>n</em> und 10) teilerfremd sind, kommt in jeder Spalte jeder Index von 0 bis <em>n</em> − 1 genau einmal vor. Es gibt also keine identischen Zeilen, d.h. es können keine Zustände zusammengefasst werden.</p> <p></p> <p>Anders hingegen, wenn die Anzahl der Zeilen und die Anzahl der Spalten nicht teilerfremd sind, d.h. wenn <em>n</em> durch 2 oder durch 5 teilbar ist. Bspw. beim 6er:</p> <p>| δ | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |---| | <strong><em>s</em>₋₀</strong> | <em>s</em>₀ | <em>s</em>₁ | <em>s</em>₂ | <em>s</em>₃ | <em>s</em>₄ | <em>s</em>₅ | <em>s</em>₀ | <em>s</em>₁ | <em>s</em>₂ | <em>s</em>₃ | <strong><em>s</em>₁</strong> | <em>s</em>₄ | <em>s</em>₅ | <em>s</em>₀ | <em>s</em>₁ | <em>s</em>₂ | <em>s</em>₃ | <em>s</em>₄ | <em>s</em>₅ | <em>s</em>₀ | <em>s</em>₁ | <strong><em>s</em>₂</strong> | <em>s</em>₂ | <em>s</em>₃ | <em>s</em>₄ | <em>s</em>₅ | <em>s</em>₀ | <em>s</em>₁ | <em>s</em>₂ | <em>s</em>₃ | <em>s</em>₄ | <em>s</em>₅ | <strong><em>s</em>₃</strong> | <em>s</em>₀ | <em>s</em>₁ | <em>s</em>₂ | <em>s</em>₃ | <em>s</em>₄ | <em>s</em>₅ | <em>s</em>₀ | <em>s</em>₁ | <em>s</em>₂ | <em>s</em>₃ | <strong><em>s</em>₄</strong> | <em>s</em>₄ | <em>s</em>₅ | <em>s</em>₀ | <em>s</em>₁ | <em>s</em>₂ | <em>s</em>₃ | <em>s</em>₄ | <em>s</em>₅ | <em>s</em>₀ | <em>s</em>₁ | <strong><em>s</em>₅</strong> | <em>s</em>₂ | <em>s</em>₃ | <em>s</em>₄ | <em>s</em>₅ | <em>s</em>₀ | <em>s</em>₁ | <em>s</em>₂ | <em>s</em>₃ | <em>s</em>₄ | <em>s</em>₅</p> <p>Die Zeilen für <em>s</em>₋₀ und <em>s</em>₃ sind identisch, ebenso für <em>s</em>₁ und <em>s</em>₄ sowie für <em>s</em>₂ und <em>s</em>₅. Diese Zustände können jeweils zusammengefasst werden – heraus kommt der bekannte Automat mit 4 Zuständen (inclusive <em>s</em>₀):</p> <p><a href="https://forum.selfhtml.org/self/2019/jan/2/informatik-zum-jahresanfang/1740262#m1740262" rel="noopener noreferrer"><img src="/images/18786f01-1513-40b2-aa6d-eca1db494ec3.png" alt="Automat für Teilbarkeit durch 6" loading="lazy"></a></p> <p></p> <p>Auch das gilt allgemein. Wenn <em>n</em> durch 2 teilbar ist, gilt für <em>u</em> < <em>n</em>/2:</p> <p>$$\delta(s_{u + n/2}, d) = \left(10 \left( u + \tfrac{n}{2} \right) + d \right) \bmod n = \left(10u + 5n + d \right) \bmod n = \left(10u + d \right) \bmod n = \delta(s_u, d)$$</p> <p>Analog für durch 5 teilbare <em>n</em> und <em>u</em> < ⅘<em>n</em>:</p> <p>$$\delta(s_{u + n/5}, d) = \left(10 \left( u + \tfrac{n}{5} \right) + d \right) \bmod n = \left(10u + 2n + d \right) \bmod n = \left(10u + d \right) \bmod n = \delta(s_u, d)$$</p> <p>Damit ist gezeigt, dass der Automat genau dann nicht minimal ist, wenn <em>n</em> durch 2 oder 5 teilbar ist.</p> <p>LLAP </p> <div class="signature">-- <br> <em>„Wer durch Wissen und Erfahrung der Klügere ist, der sollte nicht nachgeben. Und nicht aufgeben.“</em> —Kurt Weidemann </div> Informatik zum Jahresanfang – noch eine Variation Wed, 09 Jan 19 14:42:22 Z https://forum.selfhtml.org/self/2019/jan/2/informatik-zum-jahresanfang/1740310#m1740310 https://forum.selfhtml.org/self/2019/jan/2/informatik-zum-jahresanfang/1740310#m1740310 <p>Tach!</p> <blockquote> <blockquote> <p><a href="/images/e1c2c44c-9fbb-44ea-bffc-c2a26744ba2b.jpeg" rel="noopener noreferrer"><img src="/images/e1c2c44c-9fbb-44ea-bffc-c2a26744ba2b.jpeg?size=medium" alt="" loading="lazy"></a></p> </blockquote> <p>Ich mach mal den Columbo: Eine Frage hätte ich da noch. Wie müsste man den Automaten verändern, wenn führende Nullen nicht erlaubt sind?</p> </blockquote> <p>Erstellst du S0 als Start und leitest alle 0-Eingaben auf einen Fehler-Zustand und dort alles auf sich selbst. Die restlichen Übergänge von S0 gehen zu S1.</p> <p>dedlfix.</p> Informatik zum Jahresanfang – noch eine Variation Wed, 09 Jan 19 16:44:15 Z https://forum.selfhtml.org/self/2019/jan/2/informatik-zum-jahresanfang/1740317#m1740317 https://forum.selfhtml.org/self/2019/jan/2/informatik-zum-jahresanfang/1740317#m1740317 <p>Hallo Gunnar,</p> <p>Örks. 5 Zustände?</p> <p><em>Rolf</em></p> <div class="signature">-- <br> sumpsi - posui - clusi </div> Informatik zum Jahresanfang – noch eine Variation Fri, 11 Jan 19 20:02:40 Z https://forum.selfhtml.org/self/2019/jan/2/informatik-zum-jahresanfang/1740519#m1740519 https://forum.selfhtml.org/self/2019/jan/2/informatik-zum-jahresanfang/1740519#m1740519 <p>@@Gunnar Bittersmann</p> <blockquote> <blockquote> <p><a href="/images/e1c2c44c-9fbb-44ea-bffc-c2a26744ba2b.jpeg" rel="noopener noreferrer"><img src="/images/e1c2c44c-9fbb-44ea-bffc-c2a26744ba2b.jpeg?size=medium" alt="" loading="lazy"></a></p> </blockquote> <p>Ich mach mal den Columbo: Eine Frage hätte ich da noch. Wie müsste man den Automaten verändern, wenn führende Nullen nicht erlaubt sind?</p> </blockquote> <p>Wie „ein Sektglas. Passend zum Jahresanfang.“ —<a href="/users/2" class="mention registered-user" rel="noopener noreferrer">@Matthias Apsel</a></p> <p><img src="/images/ceffeec0-e031-4c91-bae7-9b5f61fa80d0.png" alt="endlicher Automat" loading="lazy"></p> <p>LLAP </p> <div class="signature">-- <br> <em>„Wer durch Wissen und Erfahrung der Klügere ist, der sollte nicht nachgeben. Und nicht aufgeben.“</em> —Kurt Weidemann </div> Informatik zum Jahresanfang – noch eine Variation Wed, 09 Jan 19 14:47:41 Z https://forum.selfhtml.org/self/2019/jan/2/informatik-zum-jahresanfang/1740311#m1740311 https://forum.selfhtml.org/self/2019/jan/2/informatik-zum-jahresanfang/1740311#m1740311 <p>@@dedlfix</p> <blockquote> <blockquote> <p>Wie müsste man den Automaten verändern, wenn führende Nullen nicht erlaubt sind?</p> </blockquote> <p>Erstellst du S0 als Start und leitest alle 0-Eingaben auf einen Fehler-Zustand</p> </blockquote> <p>Alle 0-Eingaben? Nein! Eine unbeugsame hört nicht auf, dieser Regel Widerstand zu leisten.</p> <p>LLAP </p> <div class="signature">-- <br> <em>„Wer durch Wissen und Erfahrung der Klügere ist, der sollte nicht nachgeben. Und nicht aufgeben.“</em> —Kurt Weidemann </div> Informatik zum Jahresanfang – noch eine Variation Wed, 09 Jan 19 14:56:13 Z https://forum.selfhtml.org/self/2019/jan/2/informatik-zum-jahresanfang/1740312#m1740312 https://forum.selfhtml.org/self/2019/jan/2/informatik-zum-jahresanfang/1740312#m1740312 <p>Tach!</p> <blockquote> <blockquote> <blockquote> <p>Wie müsste man den Automaten verändern, wenn führende Nullen nicht erlaubt sind?</p> </blockquote> <p>Erstellst du S0 als Start und leitest alle 0-Eingaben auf einen Fehler-Zustand</p> </blockquote> <p>Alle 0-Eingaben? Nein! Eine unbeugsame hört nicht auf, dieser Regel Widerstand zu leisten.</p> </blockquote> <p>Da S0 nur für die erste Ziffer zuständig ist, sind nicht alle 0-Eingaben betroffen, sondern nur Eingaben, die mit 0 anfangen (und beliebig weitergehen).</p> <p>dedlfix.</p> Informatik zum Jahresanfang – noch eine Variation Wed, 09 Jan 19 14:59:41 Z https://forum.selfhtml.org/self/2019/jan/2/informatik-zum-jahresanfang/1740313#m1740313 https://forum.selfhtml.org/self/2019/jan/2/informatik-zum-jahresanfang/1740313#m1740313 <p>@@dedlfix</p> <blockquote> <p>Da S0 nur für die erste Ziffer zuständig ist, sind nicht alle 0-Eingaben betroffen, sondern nur Eingaben, die mit 0 anfangen (und beliebig weitergehen).</p> </blockquote> <p>Schon klar. Es ist aber nicht richtig, die alle auf einen Fehler-Zustand zu leiten.</p> <p>LLAP </p> <div class="signature">-- <br> <em>„Wer durch Wissen und Erfahrung der Klügere ist, der sollte nicht nachgeben. Und nicht aufgeben.“</em> —Kurt Weidemann </div> Informatik zum Jahresanfang – noch eine Variation Wed, 09 Jan 19 15:01:35 Z https://forum.selfhtml.org/self/2019/jan/2/informatik-zum-jahresanfang/1740314#m1740314 https://forum.selfhtml.org/self/2019/jan/2/informatik-zum-jahresanfang/1740314#m1740314 <p>Tach!</p> <blockquote> <blockquote> <p>Da S0 nur für die erste Ziffer zuständig ist, sind nicht alle 0-Eingaben betroffen, sondern nur Eingaben, die mit 0 anfangen (und beliebig weitergehen).</p> </blockquote> <p>Schon klar. Es ist aber nicht richtig, die alle auf einen Fehler-Zustand zu leiten.</p> </blockquote> <p>Wenn "wenn führende Nullen nicht erlaubt sind", dann ist die gesamte Eingabe falsch, wenn sie mit einer führenden 0 beginnt. Wenn führenden Nullen lediglich ignoriert werden sollen, muss die Aufgabenstellung anders lauten.</p> <p>dedlfix.</p> Informatik zum Jahresanfang – noch eine Variation Wed, 09 Jan 19 15:11:58 Z https://forum.selfhtml.org/self/2019/jan/2/informatik-zum-jahresanfang/1740315#m1740315 https://forum.selfhtml.org/self/2019/jan/2/informatik-zum-jahresanfang/1740315#m1740315 <p>@@dedlfix</p> <blockquote> <p>Wenn "wenn führende Nullen nicht erlaubt sind", dann ist die gesamte Eingabe falsch, wenn sie mit einer führenden 0 beginnt.</p> </blockquote> <p>Eben nicht.</p> <p>LLAP </p> <div class="signature">-- <br> <em>„Wer durch Wissen und Erfahrung der Klügere ist, der sollte nicht nachgeben. Und nicht aufgeben.“</em> —Kurt Weidemann </div> Informatik zum Jahresanfang – noch eine Variation Wed, 09 Jan 19 16:33:26 Z https://forum.selfhtml.org/self/2019/jan/2/informatik-zum-jahresanfang/1740316#m1740316 https://forum.selfhtml.org/self/2019/jan/2/informatik-zum-jahresanfang/1740316#m1740316 <p>Hallo dedlfix,</p> <p>Worte wie "007" oder "00" wären sicherlich falsch und dürfen nicht auf den Endezustand laufen.</p> <p>Aber was ist mit... <a href="https://jsfiddle.net/d2jm53as/" rel="noopener noreferrer">[SPOILER]</a> </p> <p><em>Rolf</em></p> <div class="signature">-- <br> sumpsi - posui - clusi </div> Informatik zum Jahresanfang – noch eine Variation Wed, 09 Jan 19 18:18:09 Z https://forum.selfhtml.org/self/2019/jan/2/informatik-zum-jahresanfang/1740321#m1740321 https://forum.selfhtml.org/self/2019/jan/2/informatik-zum-jahresanfang/1740321#m1740321 <p>Hallo dedlfix,</p> <blockquote> <blockquote> <blockquote> <p>Da S0 nur für die erste Ziffer zuständig ist, sind nicht alle 0-Eingaben betroffen, sondern nur Eingaben, die mit 0 anfangen (<strong>und beliebig weitergehen</strong>).</p> </blockquote> </blockquote> </blockquote> <p>Hervorhebung von mir.</p> <blockquote> <p>Wenn "wenn führende Nullen nicht erlaubt sind", dann ist die gesamte Eingabe falsch, wenn sie mit einer führenden 0 beginnt. Wenn führenden Nullen lediglich ignoriert werden sollen, muss die Aufgabenstellung anders lauten.</p> </blockquote> <p>Nicht alle Zahlen die mit einer Null beginnen, sind ungültig.</p> <p>Bis demnächst<br> Matthias</p> <div class="signature">-- <br> Pantoffeltierchen haben keine Hobbys. </div> Informatik zum Jahresanfang – noch eine Variation Wed, 09 Jan 19 17:46:28 Z https://forum.selfhtml.org/self/2019/jan/2/informatik-zum-jahresanfang/1740319#m1740319 https://forum.selfhtml.org/self/2019/jan/2/informatik-zum-jahresanfang/1740319#m1740319 <p>@@Rolf B</p> <blockquote> <p>Aber was ist mit...</p> </blockquote> <p>Spielt noch jemand mit? Kann euch dieses Bild zum Weiterspielen motivieren? </p> <p><img src="https://upload.wikimedia.org/wikipedia/commons/thumb/a/a4/13-02-27-spielbank-wiesbaden-by-RalfR-093.jpg/640px-13-02-27-spielbank-wiesbaden-by-RalfR-093.jpg" alt="Roulette" loading="lazy"></p> <p>Foto: Ralf Roletschek / <a href="http://roletschek.at/" rel="nofollow noopener noreferrer">roletschek.at</a>, <a href="https://creativecommons.org/licenses/by-sa/3.0/deed.en" rel="nofollow noopener noreferrer">CC-BY-SA 3.0</a></p> <p>LLAP </p> <div class="signature">-- <br> <em>„Wer durch Wissen und Erfahrung der Klügere ist, der sollte nicht nachgeben. Und nicht aufgeben.“</em> —Kurt Weidemann </div> Informatik zum Jahresanfang – noch eine Variation Wed, 09 Jan 19 17:35:59 Z https://forum.selfhtml.org/self/2019/jan/2/informatik-zum-jahresanfang/1740318#m1740318 https://forum.selfhtml.org/self/2019/jan/2/informatik-zum-jahresanfang/1740318#m1740318 <p>@@Rolf B</p> <blockquote> <p>Örks. 5 Zustände?</p> </blockquote> <p>Örks. Wenigstens einer versteht mich. </p> <p>LLAP </p> <div class="signature">-- <br> <em>„Wer durch Wissen und Erfahrung der Klügere ist, der sollte nicht nachgeben. Und nicht aufgeben.“</em> —Kurt Weidemann </div> Informatik zum Jahresanfang – noch eine Variation Wed, 09 Jan 19 18:23:20 Z https://forum.selfhtml.org/self/2019/jan/2/informatik-zum-jahresanfang/1740322#m1740322 https://forum.selfhtml.org/self/2019/jan/2/informatik-zum-jahresanfang/1740322#m1740322 <p>Hallo Gunnar Bittersmann,</p> <blockquote> <p>Örks. Wenigstens einer versteht mich. </p> </blockquote> <p>Erstelle einen Automaten über dem Alphabet <code>{0; 1; 2; 3; 4; 5; 6; 7; 8; 9; -; ,}</code>, der erkennt, ob die eingegebene Zahl eine gültige Zahl ist. Gültig im Sinne von: Darf so im Heft eines Schülers stehen.</p> <p>Bis demnächst<br> Matthias</p> <div class="signature">-- <br> Pantoffeltierchen haben keine Hobbys. </div> Informatik zum Jahresanfang – noch eine Variation Wed, 09 Jan 19 18:46:10 Z https://forum.selfhtml.org/self/2019/jan/2/informatik-zum-jahresanfang/1740325#m1740325 https://forum.selfhtml.org/self/2019/jan/2/informatik-zum-jahresanfang/1740325#m1740325 <p>Tach!</p> <blockquote> <p>Nicht alle Zahlen die mit einer Null beginnen, sind ungültig.</p> </blockquote> <p>Zahlen, die mit 0 beginnen sind Zahlen mit führenden Nullen und die sind nicht erlaubt. "Nicht erlaubt" ist was anderes als "sind zu ignorieren". Erlaubten Zahlen mit nicht erlaubten führende Nullen gibt es nicht, wenn die Eingabe mit 0 anfängt. Wir sind hier in der Informatik, da sind diese Zeichen vorhanden und haben keine Sonderstellung wie beim Rechnen in der Mathematik. Die Aufgabe ist in der Formulierung und mit dem Zusatz nicht lösbar. Es sei denn, ich interpretiere sie anders als nach dem Wortlaut, das wäre dann aber das Fach Deutsch. Und dann ist das Ergebnis nicht mehr deterministisch.</p> <p>dedlfix.</p> Informatik zum Jahresanfang – noch eine Variation Wed, 09 Jan 19 18:50:18 Z https://forum.selfhtml.org/self/2019/jan/2/informatik-zum-jahresanfang/1740326#m1740326 https://forum.selfhtml.org/self/2019/jan/2/informatik-zum-jahresanfang/1740326#m1740326 <p>Tach!</p> <blockquote> <p>Erstelle einen Automaten über dem Alphabet <code>{0; 1; 2; 3; 4; 5; 6; 7; 8; 9; -; ,}</code>, der erkennt, ob die eingegebene Zahl eine gültige Zahl ist. Gültig im Sinne von: Darf so im Heft eines Schülers stehen.</p> </blockquote> <p>Fehler: zu viele Unbekannte in der Aufgabenstellung. Gemäß welcher Vorschrift ist denn begrenzt, was ein Schüler in Hefte in seinem Besitz schreiben darf?</p> <p>dedlfix.</p> Informatik zum Jahresanfang – noch eine Variation Wed, 09 Jan 19 18:52:18 Z https://forum.selfhtml.org/self/2019/jan/2/informatik-zum-jahresanfang/1740328#m1740328 https://forum.selfhtml.org/self/2019/jan/2/informatik-zum-jahresanfang/1740328#m1740328 <p>Hallo dedlfix,</p> <blockquote> <blockquote> <p>Nicht alle Zahlen die mit einer Null beginnen, sind ungültig.</p> </blockquote> <p>Zahlen, die mit 0 beginnen sind Zahlen mit führenden Nullen und die sind nicht erlaubt.</p> </blockquote> <p>Und was ist mit <code>0</code>? Diese Zahl ist durch 2 teilbar. <code>00</code> hingegen ist gar keine Zahl, <code>007</code> auch nicht.</p> <p>Bis demnächst<br> Matthias</p> <div class="signature">-- <br> Pantoffeltierchen haben keine Hobbys. </div> Informatik zum Jahresanfang – noch eine Variation Wed, 09 Jan 19 19:16:36 Z https://forum.selfhtml.org/self/2019/jan/2/informatik-zum-jahresanfang/1740334#m1740334 https://forum.selfhtml.org/self/2019/jan/2/informatik-zum-jahresanfang/1740334#m1740334 <p>Hallo dedlfix,</p> <blockquote> <blockquote> <p>Erstelle einen Automaten über dem Alphabet <code>{0; 1; 2; 3; 4; 5; 6; 7; 8; 9; -; ,}</code>, der erkennt, ob die eingegebene Zahl eine gültige Zahl ist. Gültig im Sinne von: Darf so im Heft eines Schülers stehen.</p> </blockquote> <p>Fehler: zu viele Unbekannte in der Aufgabenstellung. Gemäß welcher Vorschrift ist denn begrenzt, was ein Schüler in Hefte in seinem Besitz schreiben darf?</p> </blockquote> <p>Das ist nicht begrenzt. Aber wenn ich es exakt beschreiben möchte, ist es schon fast keine Aufgabe mehr.</p> <p>Bis demnächst<br> Matthias</p> <div class="signature">-- <br> Pantoffeltierchen haben keine Hobbys. </div> Informatik zum Jahresanfang – noch eine Variation Wed, 09 Jan 19 18:59:41 Z https://forum.selfhtml.org/self/2019/jan/2/informatik-zum-jahresanfang/1740331#m1740331 https://forum.selfhtml.org/self/2019/jan/2/informatik-zum-jahresanfang/1740331#m1740331 <p>Tach!</p> <blockquote> <blockquote> <blockquote> <p>Nicht alle Zahlen die mit einer Null beginnen, sind ungültig.</p> </blockquote> <p>Zahlen, die mit 0 beginnen sind Zahlen mit führenden Nullen und die sind nicht erlaubt.</p> </blockquote> <p>Und was ist mit <code>0</code>? Diese Zahl ist durch 2 teilbar. <code>00</code> hingegen ist gar keine Zahl, <code>007</code> auch nicht.</p> </blockquote> <p>Wenn 0 gestattet sein soll, 00 oder noch mehr Nullen aber nicht, ist der Automat nicht erstellbar, weil man (unter anderem) mit 0 und 10 gültigerweise auf den Endzustand kommt, aber dann mit weiteren Nullen nicht unterschiedlich abbiegen kann.</p> <p>dedlfix.</p> Informatik zum Jahresanfang – noch eine Variation Wed, 09 Jan 19 19:06:36 Z https://forum.selfhtml.org/self/2019/jan/2/informatik-zum-jahresanfang/1740332#m1740332 https://forum.selfhtml.org/self/2019/jan/2/informatik-zum-jahresanfang/1740332#m1740332 <p>Hallo dedlfix,</p> <blockquote> <p>Wenn 0 gestattet sein soll, 00 oder noch mehr Nullen aber nicht, ist der Automat nicht erstellbar, weil man (unter anderem) mit 0 und 10 gültigerweise auf den Endzustand kommt, aber dann mit weiteren Nullen nicht unterschiedlich abbiegen kann.</p> </blockquote> <p>Endliche Automaten dürfen auch mehrere Endzustände haben.</p> <p>Bis demnächst<br> Matthias</p> <div class="signature">-- <br> Pantoffeltierchen haben keine Hobbys. </div> Informatik zum Jahresanfang – noch eine Variation Thu, 10 Jan 19 07:09:34 Z https://forum.selfhtml.org/self/2019/jan/2/informatik-zum-jahresanfang/1740355#m1740355 https://forum.selfhtml.org/self/2019/jan/2/informatik-zum-jahresanfang/1740355#m1740355 <p>@@Matthias Apsel</p> <blockquote> <p>Endliche Automaten dürfen auch mehrere Endzustände haben.</p> </blockquote> <p>Wie schon im <a href="https://forum.selfhtml.org/self/2019/jan/2/informatik-zum-jahresanfang/1739779#m1739779" rel="noopener noreferrer">Eröffnungsspiel</a> gesagt:</p> <p><em>F</em> ⊆ <em>S</em> – Menge der Endzustände, in dem Fall <em>F</em> = {<em>s</em>₂}</p> <p>Es dürfen sogar alle Zustände Endzustände sein.</p> <p>Man könnte einen Automaten auch so definieren, dass er beim Übergang von einem Zustand zum nächsten eine Ausgabe tätigt (in dem Fall „teilbar durch <em>n</em>“ bzw. „nicht teilbar durch <em>n</em>“) und alle Zustände Endzustände sind. Dann hätte man auch das <a href="https://forum.selfhtml.org/self/2019/jan/2/informatik-zum-jahresanfang/1740262#m1740262" rel="noopener noreferrer">Problem des offenen Messers</a> nicht und der Automat käme mit <em>n</em> Zuständen aus.</p> <p>LLAP </p> <div class="signature">-- <br> <em>„Wer durch Wissen und Erfahrung der Klügere ist, der sollte nicht nachgeben. Und nicht aufgeben.“</em> —Kurt Weidemann </div> Informatik zum Jahresanfang – noch eine Variation Fri, 11 Jan 19 19:48:18 Z https://forum.selfhtml.org/self/2019/jan/2/informatik-zum-jahresanfang/1740518#m1740518 https://forum.selfhtml.org/self/2019/jan/2/informatik-zum-jahresanfang/1740518#m1740518 <p>Hallo Matthias Apsel,</p> <blockquote> <p>Das ist nicht begrenzt. Aber wenn ich es exakt beschreiben möchte, ist es schon fast keine Aufgabe mehr.</p> </blockquote> <p>Das Thema scheint ausgelutscht zu sein. Ich führe deshalb mal aus, wie eine Zahl aufgebaut ist.</p> <ul> <li>sie beginnt mit einem Minuszeichen oder einer Ziffer</li> <li>das Minuszeichen darf nur am Anfang vorkommen</li> <li>sie hat höchstens ein Komma</li> <li>sie darf nicht mit dem Komma enden</li> <li>falls sie mit einer Null beginnt, folgt nichts oder ein Komma</li> <li>Gunnar hat in seiner an die Jahreszeit angepasste Lösung noch mit Nullen endende Nachkommaanteile verboten</li> </ul> <p><img src="/images/6c1df75f-e3fa-4a1b-a753-072045cc464d.png" alt="" loading="lazy"></p> <p>Die Pfeile ins Nirwana führen in den Nebel.</p> <p>Und ob eine Zahl gültig ist, wird meiner Meinung nach von allen Interpretern auf diese Weise geprüft. Wobei die Kriterien sich durchaus unterscheiden können. In manchen <a href="https://de.wikipedia.org/wiki/Computeralgebrasystem" rel="nofollow noopener noreferrer">CAS</a> beispielsweise ist <code>2.</code> eine gültige Zahl und im Unterschied zu <code>2</code> ein Näherungswert und das Programm anweist, mit Näherungswerten zu rechnen.</p> <pre><code class="block">solve(x^2=2.,x) // x=1,414213562373095 or x=-1,414213562373095 solve(x^2=2,x) // x=√2 or x=-√2 </code></pre> <p>Bis demnächst<br> Matthias</p> <div class="signature">-- <br> Pantoffeltierchen haben keine Hobbys. </div> Informatik zum Jahresanfang – noch eine Variation Thu, 10 Jan 19 09:32:05 Z https://forum.selfhtml.org/self/2019/jan/2/informatik-zum-jahresanfang/1740369#m1740369 https://forum.selfhtml.org/self/2019/jan/2/informatik-zum-jahresanfang/1740369#m1740369 <p>Tach!</p> <blockquote> <blockquote> <p>Endliche Automaten dürfen auch mehrere Endzustände haben.</p> </blockquote> <p>Wie schon im <a href="https://forum.selfhtml.org/self/2019/jan/2/informatik-zum-jahresanfang/1739779#m1739779" rel="noopener noreferrer">Eröffnungsspiel</a> gesagt:</p> <p><em>F</em> ⊆ <em>S</em> – Menge der Endzustände, in dem Fall <em>F</em> = {<em>s</em>₂}</p> </blockquote> <p>Kann ich nicht interpretieren, dazu fehlen mir die Grundlagen.</p> <blockquote> <p>Es dürfen sogar alle Zustände Endzustände sein.</p> </blockquote> <p>Dass es mehrere Endzustände geben kann, wusste ich nicht. Grundsätzlich sehe ich das auch nicht als Problem an. Vor allem dann, wenn die Endzustände unterschiedliche Bedeutung haben und die Verarbeitung eben mit unterschiedlichen Ergebnissen enden kann. Mir widerstrebt es aber, das für diese Aufgabenstellung als gültigen Weg anzusehen. Die Aussage zur Teilbarkeit ist ein Datum, das sollte mit einem Zustand abgebildet werden.</p> <p>dedlfix.</p> Informatik zum Jahresanfang – noch eine Variation Thu, 10 Jan 19 10:18:59 Z https://forum.selfhtml.org/self/2019/jan/2/informatik-zum-jahresanfang/1740373#m1740373 https://forum.selfhtml.org/self/2019/jan/2/informatik-zum-jahresanfang/1740373#m1740373 <p>Hallo dedlfix,</p> <blockquote> <p>das sollte mit einem Zustand abgebildet werden.</p> </blockquote> <p>In trivialen Automaten mag das gelingen.</p> <p>Wenn's komplizierter wird, dann ist es eben so. Manchmal führen eben mehrere Wege zu verschiedenen Aspekten des gleichen Ziels.</p> <p><em>Rolf</em></p> <div class="signature">-- <br> sumpsi - posui - clusi </div> Informatik zum Jahresanfang – noch eine Variation Thu, 10 Jan 19 10:33:22 Z https://forum.selfhtml.org/self/2019/jan/2/informatik-zum-jahresanfang/1740374#m1740374 https://forum.selfhtml.org/self/2019/jan/2/informatik-zum-jahresanfang/1740374#m1740374 <p>@@dedlfix</p> <blockquote> <blockquote> <p><em>F</em> ⊆ <em>S</em> – Menge der Endzustände, in dem Fall <em>F</em> = {<em>s</em>₂}</p> </blockquote> <p>Kann ich nicht interpretieren</p> </blockquote> <p>„Menge“: ein Sack, wo auch <em>mehrere</em> Geschenke reinpassen. </p> <p>„der Endzustände“: Genitiv <em>Plural</em></p> <blockquote> <p>dazu fehlen mir die Grundlagen.</p> </blockquote> <p>„Deutsch als Fremdsprache“ in der VHS um die Ecke? SCNR.</p> <blockquote> <p>Mir widerstrebt es aber, das für diese Aufgabenstellung als gültigen Weg anzusehen. Die Aussage zur Teilbarkeit ist ein Datum, das sollte mit einem Zustand abgebildet werden.</p> </blockquote> <p><a href="https://forum.selfhtml.org/self/2019/jan/2/informatik-zum-jahresanfang/1739779#m1739779" rel="noopener noreferrer">Aufgabenstellung</a>: „Die Aufgabe ist, einen endlichen Automaten zu bauen, der sich nur dann in <em>einem</em> Endzustand befindet, wenn die eingegebene Zahl durch 4 [bzw. <em>n</em>] teilbar ist.“</p> <p>„In einem Endzustand“ hieß von Anfang an: in einem von mehreren möglichen; ansonsten hätte da ja „im Endzustand“ gestanden.</p> <p>LLAP </p> <div class="signature">-- <br> <em>„Wer durch Wissen und Erfahrung der Klügere ist, der sollte nicht nachgeben. Und nicht aufgeben.“</em> —Kurt Weidemann </div> Informatik zum Jahresanfang – noch eine Variation Fri, 11 Jan 19 19:21:46 Z https://forum.selfhtml.org/self/2019/jan/2/informatik-zum-jahresanfang/1740514#m1740514 https://forum.selfhtml.org/self/2019/jan/2/informatik-zum-jahresanfang/1740514#m1740514 <p>Hallo dedlfix,</p> <blockquote> <p>Dass es mehrere Endzustände geben kann, wusste ich nicht. Grundsätzlich sehe ich das auch nicht als Problem an. Vor allem dann, wenn die Endzustände unterschiedliche Bedeutung haben und die Verarbeitung eben mit unterschiedlichen Ergebnissen enden kann.</p> </blockquote> <p>Eine Zahl kann eben aus unterschiedlichen Gründen durch eine andere teilbar sein. Und da ist die Null eben an vielen Stellen eine Diva.</p> <blockquote> <p>Mir widerstrebt es aber, das für diese Aufgabenstellung als gültigen Weg anzusehen. Die Aussage zur Teilbarkeit ist ein Datum, das sollte mit einem Zustand abgebildet werden.</p> </blockquote> <p>Die Zustände sind nach außen hin nicht zu sehen. Der Automat befindet sich im Falle der Teilbarkeit am Ende der Eingabe in einem akzeptierenden Zustand. Welcher das ist und wie der Weg dahin war, ist für das Datum Teilbarkeit irrelevant.</p> <p>Bis demnächst<br> Matthias</p> <div class="signature">-- <br> Pantoffeltierchen haben keine Hobbys. </div> Informatik zum Jahresanfang – noch eine Variation Fri, 11 Jan 19 19:16:07 Z https://forum.selfhtml.org/self/2019/jan/2/informatik-zum-jahresanfang/1740512#m1740512 https://forum.selfhtml.org/self/2019/jan/2/informatik-zum-jahresanfang/1740512#m1740512 <p>Hallo Gunnar Bittersmann,</p> <blockquote> <blockquote> <blockquote> <p><em>F</em> ⊆ <em>S</em> – Menge der Endzustände, in dem Fall <em>F</em> = {<em>s</em>₂}</p> </blockquote> <p>Kann ich nicht interpretieren</p> </blockquote> <p>„Menge“: ein Sack, wo auch <em>mehrere</em> Geschenke reinpassen. </p> <p>„der Endzustände“: Genitiv <em>Plural</em></p> <blockquote> <p>dazu fehlen mir die Grundlagen.</p> </blockquote> <p>„Deutsch als Fremdsprache“ in der VHS um die Ecke? SCNR.</p> </blockquote> <p>Ach, Gunnar …</p> <p>Bis demnächst<br> Matthias</p> <div class="signature">-- <br> Pantoffeltierchen haben keine Hobbys. </div> Informatik zum Jahresanfang – noch eine Variation Fri, 11 Jan 19 20:41:14 Z https://forum.selfhtml.org/self/2019/jan/2/informatik-zum-jahresanfang/1740524#m1740524 https://forum.selfhtml.org/self/2019/jan/2/informatik-zum-jahresanfang/1740524#m1740524 <p>@@Matthias Apsel</p> <blockquote> <p><img src="/images/6c1df75f-e3fa-4a1b-a753-072045cc464d.png" alt="" loading="lazy"></p> </blockquote> <p>Hier sieht man auch schön, wann sich ein Automat nicht reduzieren lässt:</p> <p>Vom Zustand <em>α</em> links oben (nennen wir ihn „Beteigeuze“) kommt man mit <code>,</code> zum Zustand <em>δ</em> rechts im Gürtel (nennen wir ihn „Mintaka“) und mit <code>−</code> sowie mit <code>0</code> bis <code>9</code> in den Nebel (aus dem es kein Entkommen mehr gibt).</p> <p>Vom Zustand <em>β</em> rechts unten (nennen wir ihn „Rigel“) ebenso; es gilt also <em>δ</em>(<em>α</em>, <em>σ</em>) = <em>δ</em>(<em>β</em>, <em>σ</em>) für alle Symbole <em>σ</em> ∈ <em>Σ</em>.</p> <p>Dennoch kann man die Zustände <em>α</em> und <em>β</em> nicht zu einem zusammenfassen, weil <em>α</em> ein Endzustand ist, <em>β</em> aber nicht.</p> <p>LLAP </p> <p>PS: Ein roter Riese soll ein Endzustand sein? – Da lachen ja die Hühner, äh die Sterngucker.</p> <div class="signature">-- <br> <em>„Wer durch Wissen und Erfahrung der Klügere ist, der sollte nicht nachgeben. Und nicht aufgeben.“</em> —Kurt Weidemann </div> Informatik zum Jahresanfang – noch eine Variation Fri, 11 Jan 19 21:08:00 Z https://forum.selfhtml.org/self/2019/jan/2/informatik-zum-jahresanfang/1740526#m1740526 https://forum.selfhtml.org/self/2019/jan/2/informatik-zum-jahresanfang/1740526#m1740526 <p>@@Matthias Apsel</p> <p>Ich hab da mal etwas am Fernrohr rumgedreht und das Bild scharfgestellt.</p> <p><img src="/images/6c1df75f-e3fa-4a1b-a753-072045cc464d.png?size=medium" alt="" loading="lazy"> <img src="/images/6c1df75f-e3fa-4a1b-a753-072045cc464d.png" alt="" loading="lazy"></p> <p>Links das serverseitig auf 400 × 600 Pixel herruntergerechnete Bild <Bild-ID>.png?size=medium. Dateigröße: 31.0 kB.<br> Rechts das Originalbild <Bild-ID>.png mit 600 × 900 Pixel, im Browser herunterskaliert. Dateigröße: 31.8 kB.</p> <p>Manchmal macht die Generierung des „medium“-Bildes einfach keinen Sinn. Minimale Einsparung an Dateigröße bei deutlicher Verschlechterung der Qualität.</p> <p>Lohnt es sich, da etwas Gehirnschmalz reinzustecken, wann man auf das serverseitige Runterrechnen verzichtet und besser gleich das Originalbild ausliefert? <a href="/users/1" class="mention registered-user" rel="noopener noreferrer">@Christian Kruse</a></p> <p>LLAP </p> <div class="signature">-- <br> <em>„Wer durch Wissen und Erfahrung der Klügere ist, der sollte nicht nachgeben. Und nicht aufgeben.“</em> —Kurt Weidemann </div> Informatik zum Jahresanfang – noch eine Variation Thu, 17 Jan 19 07:38:39 Z https://forum.selfhtml.org/self/2019/jan/2/informatik-zum-jahresanfang/1740836#m1740836 https://forum.selfhtml.org/self/2019/jan/2/informatik-zum-jahresanfang/1740836#m1740836 <p>@@Gunnar Bittersmann</p> <blockquote> <blockquote> <p>Ich mach mal den Columbo: Eine Frage hätte ich da noch. Wie müsste man den Automaten verändern, wenn führende Nullen nicht erlaubt sind?</p> </blockquote> <p>Wie „ein Sektglas. Passend zum Jahresanfang.“ —<a href="/users/2" class="mention registered-user" rel="noopener noreferrer">@Matthias Apsel</a></p> <p><img src="/images/ceffeec0-e031-4c91-bae7-9b5f61fa80d0.png" alt="endlicher Automat" loading="lazy"></p> </blockquote> <p>Das lässt sich auch verallgemeinern: Wir brauchen in dem <a href="https://forum.selfhtml.org/self/2019/jan/2/informatik-zum-jahresanfang/1740293#m1740293" rel="noopener noreferrer">allgemeinen Automaten für <em>n</em></a> zwei zusätzliche Zustände; ich nenne sie mal $$s_{\mathrm{zero}}$$ und $$s_{\mathrm{trap}}$$ (entsprechen <em>ZO</em> und <em>ZF</em> im Fuß von Matthias’ Sektglas), wobei $$s_{\mathrm{zero}}$$ ein weiterer Endzustand ist. Dann ist also</p> <p>$$\begin{align} S &= {s_{-0}, s_{\mathrm{zero}}, s_{\mathrm{trap}}, s_0, s_1, \ldots, s_n} <br> F &= {s_{\mathrm{zero}}, s_0} \end{align}$$</p> <p>(wobei der Startzustand $$s_{-0}$$ dem <em>ZS</em> in Matthias’ Sektglas entspricht).</p> <p>In der Übergangsfunktion müssen wir den Pfeil für die 0 von $$s_{-0}$$ zu $$s_{\mathrm{zero}}$$ umbiegen (<em>ZS</em> → <em>ZO</em>) und die Ausgänge von $$s_{\mathrm{zero}}$$ und $$s_{\mathrm{trap}}$$ zu $$s_{\mathrm{trap}}$$ (→ <em>ZF</em>) hinzufügen:</p> <p>$$\delta(s_u, d) = \begin{cases} s_v \text{ mit } v = (10u + d) \bmod n & \text{ für } u = 0, \ldots, 9\text{ sowie für } u = -0 \text{ und } d = 1, \ldots, 9 <br> s_{\mathrm{zero}} & \text{ für } u = -0 \text{ und } d = 0 <br> s_{\mathrm{trap}} & \text{ für } s_u \in {s_{\mathrm{zero}}, s_{\mathrm{trap}}} \end{cases}$$</p> <p>LLAP </p> <div class="signature">-- <br> <em>„Wer durch Wissen und Erfahrung der Klügere ist, der sollte nicht nachgeben. Und nicht aufgeben.“</em> —Kurt Weidemann </div> Informatik zum Jahresanfang – noch eine Variation Fri, 11 Jan 19 20:50:58 Z https://forum.selfhtml.org/self/2019/jan/2/informatik-zum-jahresanfang/1740525#m1740525 https://forum.selfhtml.org/self/2019/jan/2/informatik-zum-jahresanfang/1740525#m1740525 <p>Hallo Gunnar Bittersmann,</p> <blockquote> <p>Hier sieht man auch schön, wann sich ein Automat nicht reduzieren lässt:</p> <p>es gilt also <em>δ</em>(<em>α</em>, <em>σ</em>) = <em>δ</em>(<em>β</em>, <em>σ</em>) für alle Symbole <em>σ</em> ∈ <em>Σ</em>.</p> <p>Dennoch kann man die Zustände <em>α</em> und <em>β</em> nicht zu einem zusammenfassen, weil <em>α</em> ein Endzustand ist, <em>β</em> aber nicht.</p> </blockquote> <p>Der Automat könnte sich aber trotzdem reduzieren lassen. Schließlich hat er noch andere Zustände.</p> <p>Bis demnächst<br> Matthias</p> <div class="signature">-- <br> Pantoffeltierchen haben keine Hobbys. </div> Informatik zum Jahresanfang – noch eine Variation Fri, 11 Jan 19 22:40:41 Z https://forum.selfhtml.org/self/2019/jan/2/informatik-zum-jahresanfang/1740534#m1740534 https://forum.selfhtml.org/self/2019/jan/2/informatik-zum-jahresanfang/1740534#m1740534 <p>Hallo Matthias,</p> <p>warte ein paar Milliarden Jahre, dann reduziert er sich von ganz allein auf ein Black Hole.</p> <p><em>Rolf</em></p> <div class="signature">-- <br> sumpsi - posui - clusi </div> Informatik zum Jahresanfang – noch eine Variation Mon, 14 Jan 19 05:16:25 Z https://forum.selfhtml.org/self/2019/jan/2/informatik-zum-jahresanfang/1740675#m1740675 https://forum.selfhtml.org/self/2019/jan/2/informatik-zum-jahresanfang/1740675#m1740675 <p>@@Matthias Apsel</p> <blockquote> <blockquote> <p>Hier sieht man auch schön, wann sich ein Automat nicht reduzieren lässt:</p> </blockquote> <p>Der Automat könnte sich aber trotzdem reduzieren lassen. Schließlich hat er noch andere Zustände.</p> </blockquote> <p>Ja, die wären auch jeweils paarweise zu prüfen.</p> <p>Und wo ich das schon in einer DM erläutert hatte, stelle ich’s auch hier rein.</p> <p></p> <p>Schauen wir uns diesen 2er Automaten an:</p> <p><img src="/images/4388d1a7-e455-4e21-ab8b-771c2fbe31db.png" alt="" loading="lazy"></p> <p>Von <em>S</em>₁ gelangt man mit 1, 3, 5, 7, 9 zu <em>S</em>₂ und mit 0, 2, 4, 6, 8 zu <em>E</em>.<br> Von <em>S</em>₂ gelangt man mit 1, 3, 5, 7, 9 zu <em>S</em>₂ und mit 0, 2, 4, 6, 8 zu <em>E</em>.</p> <p>Beides sind keine Endzustände, deshalb kann man <em>S</em>₁ und <em>S</em>₂ zusammenfassen:</p> <p><img src="/images/6a3abe18-218f-43fb-a8bc-a47b8283bf3b.png" alt="" loading="lazy"></p> <p>Das o.g. Kriterium allein reicht aber nicht.</p> <p><img src="/images/7b6cbf6f-742b-46e2-85fe-8a7a47acbd05.png" alt="" loading="lazy"></p> <p>Von <em>S</em>₁ gelangt man mit 1, 3, 5, 7, 9 zu <strong><em>S</em>₂</strong> und mit 0, 2, 4, 6, 8 zu <em>E</em>.<br> Von <em>S</em>₂ gelangt man mit 1, 3, 5, 7, 9 zu <strong><em>S</em>₁</strong> und mit 0, 2, 4, 6, 8 zu <em>E</em>.</p> <p>Trotzdem kann man auch diesen Automaten genauso reduzieren.</p> <p>Da müsste ich nochmal drüber nachdenken oder nachlesen (vielleicht hab ich sogar noch meine Unterlagen aus Theoretischer Informatik von der Uni irgendwo im Schrank), wie man das auch noch mit reinbekommt.</p> <p>Schauen wir uns nochmal den 3er Automaten an:</p> <p><img src="/images/5f87c392-0401-47fe-9f42-609aa84c1af2.png" alt="" loading="lazy"></p> <p>Von <em>s</em>₀ mit 1, 4, 7 zu <em>s</em>₁, mit 2, 5, 8 zu <em>s</em>₂ und mit 0, 3, 6, 9 zu <em>s</em>ₑ.<br> Von <em>s</em>ₑ mit 1, 4, 7 zu <em>s</em>₁, mit 2, 5, 8 zu <em>s</em>₂ und mit 0, 3, 6, 9 zu <em>s</em>ₑ.</p> <p>Stimmt auch überein. Wenn man nun <em>s</em>₀ und <em>s</em>ₑ zusammenfassen würde:</p> <p><img src="/images/ed210a9e-a35d-470b-a2ad-ca4bf630e18e.png" alt="" loading="lazy"></p> <p>Das hatten wir doch schon! </p> <p><em>s</em>₀ und <em>s</em>ₑ darf man nicht zusammenfassen, da der eine ein Endzustand ist, der andere aber nicht.</p> <p>LLAP </p> <div class="signature">-- <br> <em>„Wer durch Wissen und Erfahrung der Klügere ist, der sollte nicht nachgeben. Und nicht aufgeben.“</em> —Kurt Weidemann </div> Informatik zum Jahresanfang – noch eine Variation Mon, 14 Jan 19 08:21:12 Z https://forum.selfhtml.org/self/2019/jan/2/informatik-zum-jahresanfang/1740681#m1740681 https://forum.selfhtml.org/self/2019/jan/2/informatik-zum-jahresanfang/1740681#m1740681 <p>@@Matthias Apsel</p> <blockquote> <p>Hallo Gunnar Bittersmann,</p> <blockquote> <p>Hier sieht man auch schön, wann sich ein Automat nicht reduzieren lässt:</p> <p>es gilt also <em>δ</em>(<em>α</em>, <em>σ</em>) = <em>δ</em>(<em>β</em>, <em>σ</em>) für alle Symbole <em>σ</em> ∈ <em>Σ</em>.</p> <p>Dennoch kann man die Zustände <em>α</em> und <em>β</em> nicht zu einem zusammenfassen, weil <em>α</em> ein Endzustand ist, <em>β</em> aber nicht.</p> </blockquote> <p>Der Automat könnte sich aber trotzdem reduzieren lassen. Schließlich hat er noch andere Zustände.</p> </blockquote> <p>Zum Beispiel <em>γ</em> rechts oben (nennen wir ihn „Bellatrix“) und den Kopf <em>λ</em> (nennen wir ihn „Heka“): Von beiden geht’s mit <code>0</code> zu <em>λ</em> und mit <code>1</code> bis <code>9</code> zu <em>γ</em> sowie mit <code>−</code> und <code>,</code> in den Nebel. Keine Reduktion, obwohl <em>δ</em>(<em>γ</em>, <em>σ</em>) = <em>δ</em>(<em>λ</em>, <em>σ</em>) für alle Symbole <em>σ</em> ∈ <em>Σ</em>, weil <em>γ</em> ein Endzustand ist, <em>λ</em> aber nicht.</p> <p><img src="/images/6c1df75f-e3fa-4a1b-a753-072045cc464d.png" alt="" loading="lazy"></p> <p>Anders siehts aus, wenn man bei Dezimalbrüchen Nullen am Ende zulässt. (Was ja in der Physik durchaus Sinn macht: 9876,50 ist was anderes als 9876,5 – nämlich eine genauere Messung/Berechnung aus genaueren Messwerten.)</p> <p>Dann ist <em>λ</em> auch ein Endzustand; <em>γ</em> und <em>λ</em> können zusammengefasst werden. Dazu werden die zu <em>γ</em> führenden Pfeile (von <em>γ</em> selbst und vom rechten Gürtelzustand <em>δ</em>) mit <code>0–9</code> beschriftet; <em>λ</em> und alle Pfeile von und zu diesem werden entfernt.</p> <p>LLAP </p> <div class="signature">-- <br> <em>„Wer durch Wissen und Erfahrung der Klügere ist, der sollte nicht nachgeben. Und nicht aufgeben.“</em> —Kurt Weidemann </div> Informatik zum Jahresanfang – noch eine Variation Fri, 11 Jan 19 21:39:41 Z https://forum.selfhtml.org/self/2019/jan/2/informatik-zum-jahresanfang/1740528#m1740528 https://forum.selfhtml.org/self/2019/jan/2/informatik-zum-jahresanfang/1740528#m1740528 <p>Hallo Gunnar,</p> <blockquote> <p>Lohnt es sich, da etwas Gehirnschmalz reinzustecken, wann man auf das serverseitige Runterrechnen verzichtet und besser gleich das Originalbild ausliefert? <a href="/users/1" class="mention registered-user" rel="noopener noreferrer">@Christian Kruse</a></p> </blockquote> <p>Vor V5 eh nicht. Und danach… warum nicht. Behalts im Kopf </p> <p>LG,<br> CK</p> <div class="signature">-- <br> <a href="https://wwwtech.de/about" rel="noopener noreferrer">https://wwwtech.de/about</a> </div> Informatik zum Jahresanfang – Auflösung für n Sun, 20 Jan 19 19:17:59 Z https://forum.selfhtml.org/self/2019/jan/2/informatik-zum-jahresanfang/1741096#m1741096 https://forum.selfhtml.org/self/2019/jan/2/informatik-zum-jahresanfang/1741096#m1741096 <p>Hallo</p> <blockquote> <p>Ich dachte, man könnte <code class="language-js">currentState</code> und <code class="language-js">inputAlphabet</code> durch vorangestelltes <code>#</code> privat machen, aber da spielt CodePen nicht mit?</p> </blockquote> <p>Das ist auch keine <a href="https://tc39.github.io/ecma262/#sec-class-definitions" rel="nofollow noopener noreferrer">Standardsyntax</a>. Zumindest noch nicht. Genauso wie die Zuweisungen im Körper deine Klasse. Dabei handelt es sich bislang nur um <a href="https://github.com/tc39/proposals" rel="noopener noreferrer">Proposals</a>, die jederzeit gekippt werden können.</p> <pre><code class="block language-javascript"><span class="token keyword">class</span> <span class="token class-name">DivisibilityFSA</span> <span class="token punctuation">{</span> <span class="token function">constructor</span><span class="token punctuation">(</span><span class="token parameter">n</span><span class="token punctuation">)</span> <span class="token punctuation">{</span> <span class="token keyword">this</span><span class="token punctuation">.</span>currentState <span class="token operator">=</span> <span class="token number">0</span><span class="token punctuation">;</span> <span class="token keyword">this</span><span class="token punctuation">.</span>inputAlphabet <span class="token operator">=</span> <span class="token punctuation">[</span><span class="token number">0</span><span class="token punctuation">,</span> <span class="token number">1</span><span class="token punctuation">,</span> <span class="token number">2</span><span class="token punctuation">,</span> <span class="token number">3</span><span class="token punctuation">,</span> <span class="token number">4</span><span class="token punctuation">,</span> <span class="token number">5</span><span class="token punctuation">,</span> <span class="token number">6</span><span class="token punctuation">,</span> <span class="token number">7</span><span class="token punctuation">,</span> <span class="token number">8</span><span class="token punctuation">,</span> <span class="token number">9</span><span class="token punctuation">]</span><span class="token punctuation">;</span> <span class="token keyword">this</span><span class="token punctuation">.</span>n <span class="token operator">=</span> n<span class="token punctuation">;</span> <span class="token punctuation">}</span> <span class="token function">transition</span><span class="token punctuation">(</span><span class="token parameter">input</span><span class="token punctuation">)</span> <span class="token punctuation">{</span> <span class="token keyword">if</span> <span class="token punctuation">(</span><span class="token keyword">this</span><span class="token punctuation">.</span>inputAlphabet<span class="token punctuation">.</span><span class="token function">includes</span><span class="token punctuation">(</span>input<span class="token punctuation">)</span><span class="token punctuation">)</span> <span class="token punctuation">{</span> <span class="token keyword">return</span> <span class="token operator">!</span><span class="token punctuation">(</span><span class="token keyword">this</span><span class="token punctuation">.</span>currentState <span class="token operator">=</span> <span class="token punctuation">(</span><span class="token number">10</span> <span class="token operator">*</span> <span class="token keyword">this</span><span class="token punctuation">.</span>currentState <span class="token operator">+</span> input<span class="token punctuation">)</span> <span class="token operator">%</span> <span class="token keyword">this</span><span class="token punctuation">.</span>n<span class="token punctuation">)</span><span class="token punctuation">;</span> <span class="token punctuation">}</span> <span class="token punctuation">}</span> <span class="token punctuation">}</span> </code></pre> <p>Eine standardkonforme Implementierung deines Automaten, die nicht erst transpiliert werden muss, könnte so aussehen wie in dem Beispiel oben.</p> Informatik zum Jahresanfang – Auflösung für n Mon, 21 Jan 19 10:25:08 Z https://forum.selfhtml.org/self/2019/jan/2/informatik-zum-jahresanfang/1741151#m1741151 https://forum.selfhtml.org/self/2019/jan/2/informatik-zum-jahresanfang/1741151#m1741151 <p>@@Doktor Seltsam</p> <blockquote> <p>Das ist auch keine <a href="https://tc39.github.io/ecma262/#sec-class-definitions" rel="nofollow noopener noreferrer">Standardsyntax</a>. Zumindest noch nicht. Genauso wie die Zuweisungen im Körper deine Klasse. Dabei handelt es sich bislang nur um <a href="https://github.com/tc39/proposals" rel="noopener noreferrer">Proposals</a>, die jederzeit gekippt werden können.</p> </blockquote> <p>Ah! Ich hätte mal den <a href="https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Classes#Field_declarations" rel="nofollow noopener noreferrer">Text im roten Kasten</a> lesen sollen. Hätte ja was Wichtiges drinstehen können.</p> <blockquote> <pre><code class="block language-javascript"> <span class="token function">transition</span><span class="token punctuation">(</span><span class="token parameter">input</span><span class="token punctuation">)</span> <span class="token punctuation">{</span> <span class="token keyword">if</span> <span class="token punctuation">(</span><span class="token keyword">this</span><span class="token punctuation">.</span>inputAlphabet<span class="token punctuation">.</span><span class="token function">includes</span><span class="token punctuation">(</span>input<span class="token punctuation">)</span><span class="token punctuation">)</span> <span class="token punctuation">{</span> <span class="token keyword">return</span> <span class="token operator">!</span><span class="token punctuation">(</span><span class="token keyword">this</span><span class="token punctuation">.</span>currentState <span class="token operator">=</span> <span class="token punctuation">(</span><span class="token number">10</span> <span class="token operator">*</span> <span class="token keyword">this</span><span class="token punctuation">.</span>currentState <span class="token operator">+</span> input<span class="token punctuation">)</span> <span class="token operator">%</span> <span class="token keyword">this</span><span class="token punctuation">.</span>n<span class="token punctuation">)</span><span class="token punctuation">;</span> <span class="token punctuation">}</span> <span class="token punctuation">}</span> </code></pre> </blockquote> <p>Ohne Pfeilfunktion ist das wohl auch leichter lesbar; und den ternären Operator muss man dann auch nicht bemühen.</p> <p>Dann kann man das auch noch aufdröseln, um deutlich zu machen, dass tatsächlich der Wert der Zuweisung negiert werden soll und dass es sich nicht um einen Schreibfehler handelt (da soll wirklich <code>=</code> stehen, nicht <code>==</code> oder <code>===</code>):</p> <pre><code class="block language-javascript"> <span class="token function">transition</span><span class="token punctuation">(</span><span class="token parameter">input</span><span class="token punctuation">)</span> <span class="token punctuation">{</span> <span class="token keyword">if</span> <span class="token punctuation">(</span><span class="token keyword">this</span><span class="token punctuation">.</span>inputAlphabet<span class="token punctuation">.</span><span class="token function">includes</span><span class="token punctuation">(</span>input<span class="token punctuation">)</span><span class="token punctuation">)</span> <span class="token punctuation">{</span> <span class="token keyword">this</span><span class="token punctuation">.</span>currentState <span class="token operator">=</span> <span class="token punctuation">(</span><span class="token number">10</span> <span class="token operator">*</span> <span class="token keyword">this</span><span class="token punctuation">.</span>currentState <span class="token operator">+</span> input<span class="token punctuation">)</span> <span class="token operator">%</span> <span class="token keyword">this</span><span class="token punctuation">.</span>n<span class="token punctuation">;</span> <span class="token keyword">return</span> <span class="token operator">!</span><span class="token keyword">this</span><span class="token punctuation">.</span>currentState<span class="token punctuation">;</span> <span class="token punctuation">}</span> <span class="token punctuation">}</span> </code></pre> <p>LLAP </p> <div class="signature">-- <br> <em>„Wer durch Wissen und Erfahrung der Klügere ist, der sollte nicht nachgeben. Und nicht aufgeben.“</em> —Kurt Weidemann </div> Informatik zum Jahresanfang – Auflösung für n Tue, 22 Jan 19 15:55:48 Z https://forum.selfhtml.org/self/2019/jan/2/informatik-zum-jahresanfang/1741315#m1741315 https://forum.selfhtml.org/self/2019/jan/2/informatik-zum-jahresanfang/1741315#m1741315 <p>Hallo Gunnar Bittersmann,</p> <p>Das passt zusammen mit der Periodizität von Stammbrüchen.</p> <p>Bis demnächst<br> Matthias</p> <div class="signature">-- <br> Pantoffeltierchen haben keine Hobbys. </div> Informatik zum Jahresanfang – Auflösung für n Tue, 22 Jan 19 18:26:40 Z https://forum.selfhtml.org/self/2019/jan/2/informatik-zum-jahresanfang/1741327#m1741327 https://forum.selfhtml.org/self/2019/jan/2/informatik-zum-jahresanfang/1741327#m1741327 <p>Hallo Matthias Apsel,</p> <blockquote> <p>Das passt zusammen mit der Periodizität von Stammbrüchen.</p> </blockquote> <p>vollständig gekürzte Brüche, deren Primfaktorzerlegung des Nenners …</p> <ul> <li>nur Faktoren 2 oder 5 enthält, haben eine endliche</li> <li>nur Faktoren außer 2 und 5 enthält, haben eine sofortperiodische</li> <li>beide Sorten von Primfaktoren enthält, haben eine spätperiodische</li> </ul> <p>… Dezimalbruchentwicklung.</p> <p>Die Länge der Dezimalbruchentwicklung im ersten Fall und die Länge der Vorperiode im dritten Fall ist gleich dem Maximum der Anzahl der Faktoren 2 und 5.</p> <p>Die Periodenlänge in den Fällen zwei und drei ist gleich der kleinsten Zahl n, für die gilt 10ⁿ ≡ 1(Nenner).</p> <p>Bis demnächst<br> Matthias</p> <div class="signature">-- <br> Pantoffeltierchen haben keine Hobbys. </div>