Durch 5 teilbare Binärzahlen
Christian Puritscher
kann man einen endlichen Automaten kreieren, der alle durch 5 teilbare
Binärzahlen, die mit 1 beginnen, erkennt?
Oder wie sehen die Regeln für durch 5 teilbare Binärzahlen eigentlich auf?
Ich habe alle durch 5 teilbaren Binärzahlen bis 100 aufgeschrieben, kann
aber keine Regel unmittelbar erkennen!
Vielen Dank für Eure Hilfe,
Puri
Christian Puritscher
Andreas Ferber
> kann man einen endlichen Automaten kreieren, der alle durch 5 teilbare
> Binärzahlen, die mit 1 beginnen, erkennt?
Ja, man kann, da es sich ganz offenbar um ein berechenbares Problem
handelt. Die 1 am Anfang ist aber abhängig davon, mit wievielen Bits
man arbeitet, wenn man immer nur soviele nimmt, wie für die
Darstellung der jeweiligen Zahl benötigt wird, dann fängt jede
Binärzahl (ausser 0 ;-) mit einer 1 an.
> Oder wie sehen die Regeln für durch 5 teilbare Binärzahlen eigentlich auf?
> Ich habe alle durch 5 teilbaren Binärzahlen bis 100 aufgeschrieben, kann
> aber keine Regel unmittelbar erkennen!
Dafür gibt es keine einfache Regel.
Bis denn dann
--
When a float occurs on the same page as the start of a supertabular
you can expect unexpected results.
-- Documentation of supertabular.sty
Florian Wessels
<pu...@gmx.de> wrote:
>kann man einen endlichen Automaten kreieren, der alle durch 5 teilbare
>Binärzahlen, die mit 1 beginnen, erkennt?
Was heisst "mit einer 1 beginnen"?
Von `rechts' oder von `links'?
Wenn das `Beginnen' auf der `linken' Seite
stattfindet, und du die Binaerzahl von `links nach rechts'
liest, kannst du jeweils in einen Zustand huepfen,
der den Rest bis dahin repraesentiert;
Also etwa fuer 10100:
1 -> rest 1 (bis jetzt)
10 -> rest 1*2 + 0 = 2
^ ^
| | gerade gelesen.
| von vorher.
101 -> rest 2*2 + 1 = 5 = 0 (mod 5)
1010 -> rest 2*0 = 0
10100 -> rest 0.
Hmm... klar, was ich meine?
Das steht wohl allgemein beschrieben in
van Leeuven, Handbook of theoretical computer science Vol B,
S. 36
Gruesse, Florian
----
Florian Wessels
wes...@math.uni-muenster.de
PGP-Schluessel erhaeltlich unter http://www.muenster.de/~fwessels
Florian Wessels
(Andreas Ferber) wrote:
>* Christian Puritscher <pu...@gmx.de> schrieb:
>> kann man einen endlichen Automaten kreieren, der alle durch 5 teilbare
>> Binärzahlen, die mit 1 beginnen, erkennt?
>
>Ja, man kann, da es sich ganz offenbar um ein berechenbares Problem
>handelt.
Das ist aber eine komische Begruendung, oder?
Immerhin gibt es ziemlich viele berechenbare Probleme, die
endliche Automaten nicht hinbekommen.
z.B. zwei Zahlen multiplizieren :-)
Martin Kretzschmar
>> Oder wie sehen die Regeln für durch 5 teilbare Binärzahlen eigentlich auf?
>> Ich habe alle durch 5 teilbaren Binärzahlen bis 100 aufgeschrieben, kann
>> aber keine Regel unmittelbar erkennen!
> Dafür gibt es keine einfache Regel.
Vielleicht gibt es doch eine (ich habe Sie weder bewiesen, noch ausprobiert,
vielleicht klappt sie aber:
Wandle die Zahl ins 4er-System um (je 2 bits zusammenfassen)
Bilde die alternierende Quersumme
Zahl ist durch 5 Teilbar, wenn diese alt. Quersumme durch 5 teilbar ist.
Na, erkannt? Ich hoffe, dieses Verfahren funktioniert wie die Teilbarkeits-
regel für 11 im Dezimalsystem.
Wie gesagt, kein Beweis, kein Beispiel, keine Gewähr
Martin
Cornell Binder
>
>> Oder wie sehen die Regeln für durch 5 teilbare Binärzahlen eigentlich auf?
>> Ich habe alle durch 5 teilbaren Binärzahlen bis 100 aufgeschrieben, kann
>> aber keine Regel unmittelbar erkennen!
>
> Dafür gibt es keine einfache Regel.
Man braucht man einen Automaten mit 5 Zuständen, da
wir mit Modulo 5 arbeiten.
Als Eingabe kommt die Binärzahl von höchstwertigsten
Bit an, und enden schließlich mit 2^0.
Wir arbeiten nun mit der Wert X, den wir durch jedes
neue eingelesen Bit neu berechnen. Da wir ganz
scharf auf die 5 sind, machen wir auch jedes mal
gleich ein Modulo 5 und merken uns so, welchen
Rest unser X gerade hat.
Der Startzustand ist 0. (unser x ebenfalls)
Lesen wir nun eine 1 ein, muessen wir unser x mit
2 multiplizieren (Linksshift) und dann noch 1 addieren.
Für den neuen Zustand muessen wir nun noch ein
modulo 5 ausführen, und wir landen in 1.
Kommt eine 0 wird x mit zwei multpliziert
(Linskshift) und wir bleiben in 0.
Die Übergänge zwischen den Zuständen lassen sich nun
sehr einfach ermitteln.
(Zustand, Eingabe)
0,0 -> 0
0,1 -> 1
1,0 -> 2
1,1 -> 3
2,0 -> 4
2,1 -> 0
3,0 -> 1
3,1 -> 2
4,0 -> 3
4,1 -> 4
Endzustand ist 0. Stehen wir also am Ende wieder im
Zustand 0, ist die Binärzahl durch 5 teilbar.
CoBi - Lang leben archiviert Aufgaben :)
--
+- Joker.dex.de --
| Witze am laufenden Band. Jetzt auch per WAP.
|
+- http://joker.dex.de/ ------------- ein Service von http://www.dex.de/ --
Florian Wessels
<mk79...@irz618.inf.tu-dresden.de> wrote:
>Andreas Ferber <afe...@techfak.uni-bielefeld.de> wrote:
>>> Oder wie sehen die Regeln für durch 5 teilbare Binärzahlen eigentlich auf?
>>> Ich habe alle durch 5 teilbaren Binärzahlen bis 100 aufgeschrieben, kann
>>> aber keine Regel unmittelbar erkennen!
>
>> Dafür gibt es keine einfache Regel.
>
>Vielleicht gibt es doch eine (ich habe Sie weder bewiesen, noch ausprobiert,
>vielleicht klappt sie aber:
>
>Wandle die Zahl ins 4er-System um (je 2 bits zusammenfassen)
>
>Bilde die alternierende Quersumme
>
>Zahl ist durch 5 Teilbar, wenn diese alt. Quersumme durch 5 teilbar ist.
>
>Na, erkannt? Ich hoffe, dieses Verfahren funktioniert wie die Teilbarkeits-
>regel für 11 im Dezimalsystem.
>
>Wie gesagt, kein Beweis, kein Beispiel, keine Gewähr
Das klappt immer.
Ist n = a_0*b^0 + a_1*b^1 + ... + a_n*b^n, wobei b>1, a_i aus
{0..b-1}, dann ist
n mod b+1
= (a_0*b^0 + a_1*b^1 + ... + a_n*b^n) mod b+1
= a_0*b^0 (mod b+1) + ... + a_n*b^n (mod b+1)
= a_0*(b mod b+1)^0 + ... + a_n*(b mod b+1)^n
= a_0*(-1)^0 + ... + a_n*(-1)^n.
d.h. eine Zahl ist modulo b+1 zu ihrer alternierenden b-adischen
Quersumme kongruent.
Ich denke allerdings, dass der Automat komplizierter wird,
als der, der mit den jeweils entstehenden Resten arbeitet.
Christian Puritscher
Also meiner bescheidenen Meinung nach war diese Aufgabe schon etwas zu
aufwendig für eine Klausur, wenn mir die Lösung auch einleuchtet und logisch
erscheint.
"Cornell Binder" <co...@dafhs.org> schrieb im Newsbeitrag
news:8caisa$632i8$1...@fu-berlin.de...
> Andreas Ferber schriebste:
> >
> >> Oder wie sehen die Regeln für durch 5 teilbare Binärzahlen eigentlich
auf?
> >> Ich habe alle durch 5 teilbaren Binärzahlen bis 100 aufgeschrieben,
kann
> >> aber keine Regel unmittelbar erkennen!
> >
> > Dafür gibt es keine einfache Regel.
>
Christopher Wolf
Christian Puritscher wrote:
>
> Danke für Eure Mühe, und für Deine Lösung.
> Also meiner bescheidenen Meinung nach war diese Aufgabe schon etwas zu
> aufwendig für eine Klausur, wenn mir die Lösung auch einleuchtet und logisch
> erscheint.
So eine Aufgabe _war_ Klausuraufgabe: Uni Ulm, Vordiplom Theoretische
Informatik, SS 1999. Lag aber wohl daran, daß wir die Aufgabe für 3
statt für 5 schon auf einem Übungsblatt gemacht hatten ;-)
Gruß,
Christopher
Cornell Binder
> Hallo,
>
> So eine Aufgabe _war_ Klausuraufgabe: Uni Ulm, Vordiplom Theoretische
> Informatik, SS 1999. Lag aber wohl daran, daß wir die Aufgabe für 3
> statt für 5 schon auf einem Übungsblatt gemacht hatten ;-)
dito für die 3.
Aus dem Stand ist es aber dann doch wohl etwas
zu schwer für eine Klausur, das man doch etwas
Zeit benötigt.
CoBi
--
+- WatchCat --
| überwacht täglich Deine Bookmarks und mailt Dich bei Veränderungen an
|
+- http://www.watchcat.de/ ---------- ein Service von http://www.dex.de/ --
Jochen Messner
>
> Christopher Wolf schriebste:
> > Hallo,
> >
> > So eine Aufgabe _war_ Klausuraufgabe: Uni Ulm, Vordiplom Theoretische
> > Informatik, SS 1999. Lag aber wohl daran, daß wir die Aufgabe für 3
> > statt für 5 schon auf einem Übungsblatt gemacht hatten ;-)
>
> dito für die 3.
>
> Aus dem Stand ist es aber dann doch wohl etwas
> zu schwer für eine Klausur, das man doch etwas
> Zeit benötigt.
>
>
Vielleicht. Aber was spricht dagegen in der Pruefung zu testen, ob
jemand gut in den Uebungen mitgearbeitet hat? Kennt man die 3er-Aufgabe
(und hat die Idee verstanden) so ist die 5-er Aufgabe leicht.
Gruss,
Jochen
Andreas Koch
Florian Wessels schrieb:
> Das ist aber eine komische Begruendung, oder?
>
> Immerhin gibt es ziemlich viele berechenbare Probleme, die
> endliche Automaten nicht hinbekommen.
> z.B. zwei Zahlen multiplizieren :-)
Ähm, ist "zwei Zahlen multiplizieren" nicht
Primitiv rekursiv? Und damit äquivalent
zu Loop?
z=0
Loop y do loop x do z=z+1
Und loop sollte doch durch alles andere
emulierbar sein.
Andreas
Christopher Wolf
Andreas Koch wrote:
>
> Ähm, ist "zwei Zahlen multiplizieren" nicht
> Primitiv rekursiv? Und damit äquivalent
> zu Loop?
Doch.
> z=0
> Loop y do loop x do z=z+1
>
> Und loop sollte doch durch alles andere
> emulierbar sein.
Nicht ganz: Endliche Automaten sind reguläre Ausdrücke / Sprachen.
Loop ist eine ganz andere Baustelle.
Gruß,
Christopher
Andreas Koch
Christopher Wolf schrieb:
>
> Hallo,
>
> Andreas Koch wrote:
> >
> > Ähm, ist "zwei Zahlen multiplizieren" nicht
> > Primitiv rekursiv? Und damit äquivalent
> > zu Loop?
>
> Doch.
>
> Nicht ganz: Endliche Automaten sind reguläre Ausdrücke / Sprachen.
> Loop ist eine ganz andere Baustelle.
Hm, stimmt irgendwie. Falsch rum gedacht. Aufwachen ... ;)