Matroids Matheplanet Forum Index
Moderiert von Bilbo
Informatik » Theoretische Informatik » Behauptung der terminierenden Art
Druckversion
Druckversion
Antworten
Antworten
Autor
Kein bestimmter Bereich Behauptung der terminierenden Art
Goswin
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 18.09.2008
Mitteilungen: 1443
Aus: Chile, Ulm
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Themenstart: 2019-09-22


Wenn für einen deterministischen Algorithmus eine Funktion existiert, die (1)_von der Zustandsmenge des Algorithmus in die natürlichen Zahlen geht und (2)_bezüglich der Schrittzahl des Algorithmus streng monoton fällt, dann muss dieser Algorithmus für jede Eingabe nach endlich vielen Schritten terminieren.

Ich habe nun gerade einen Algorithmus mit (ziemlich abstraktem) Terminierungsbeweis untersucht und "zu meiner Freude" festgestellt, dass für diesen Algorithmus so eine Funktion existiert, die ich nun kenne.

Meine Frage ist, ob diese "meine Freude" nicht ziemlich voraussehbar und deshalb etwas übertrieben war; in anderen Worten, ob es nicht für *jeden* deterministischen Algorithmus, der bewiesenermaßen terminiert, so eine Funktion geben *muss* (wobei nicht gesagt wird, dass sie leicht zu finden ist).

Ist diese letzte (für mich recht plausible) Umkehrung der obigen Aussage selbstverständlich, oder bedarf sie eines Beweises?


-----------------
/Kyristo meu kimgei kom nhi cumgen ta Gendmogen.



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
ligning
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 07.12.2014
Mitteilungen: 3081
Aus: Berlin
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.1, eingetragen 2019-09-22


Ja, so eine Funktion existiert trivialerweise: Die Anzahl der vom aktuellen Zustand aus noch auszuführenden Schritte, bis ein Endzustand erreicht wird.


-----------------
⊗ ⊗ ⊗



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Goswin
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 18.09.2008
Mitteilungen: 1443
Aus: Chile, Ulm
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.2, vom Themenstarter, eingetragen 2019-09-22


2019-09-22 19:28 - ligning in Beitrag No. 1 schreibt:
Ja, so eine Funktion existiert trivialerweise: Die Anzahl der vom aktuellen Zustand aus noch auszuführenden Schritte, bis ein Endzustand erreicht wird.

... womit diese Funktion in der Tat nicht immer leicht zu finden wäre. 😛 Verschärfen wir doch etwas die Behauptung, indem wir verlangen, dass diese Funktion Schritt für Schritt "deutlich" schneller zu berechnen ist als die Ausführung des Algorithmus selber.

Kennt ihr ein Beispiel von terminierendem Algorithmus, für welchen keine solche schnell berechenbare Funktion bekannt ist?



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Yggdrasil
Senior Letzter Besuch: im letzten Quartal
Dabei seit: 01.07.2004
Mitteilungen: 856
Aus: Berlin
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.3, eingetragen 2019-09-22


2019-09-22 20:28 - Goswin in Beitrag No. 2 schreibt:
Kennt ihr ein Beispiel von terminierendem Algorithmus, für welchen keine solche schnell berechenbare Funktion bekannt ist?

Die Anzahl der vom aktuellen Zustand aus noch auszuführenden Schritte, bis ein Endzustand erreicht wird. 😁



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Goswin
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 18.09.2008
Mitteilungen: 1443
Aus: Chile, Ulm
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.4, vom Themenstarter, eingetragen 2019-09-23


2019-09-22 23:03 - Yggdrasil in Beitrag No. 3 schreibt:
2019-09-22 20:28 - Goswin in Beitrag No. 2 schreibt:
Kennt ihr ein Beispiel von terminierendem Algorithmus, für welchen keine solche schnell berechenbare Funktion bekannt ist?

Die Anzahl der vom aktuellen Zustand aus noch auszuführenden Schritte, bis ein Endzustand erreicht wird. 😁

Verstehe ich nicht. Das ist eine berechenbare *Funktion* für einen vorgegebenen terminierenden Algorithmus, wieso ist das ein Beispiel für einen Algorithmus?



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
DerEinfaeltige
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 11.02.2015
Mitteilungen: 2237
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.5, eingetragen 2019-09-23


Die lineare Suche in einer Liste sollte ein Gegenbeispiel sein. Denn um die gewünschte Funktion anzugeben, wird man um ein Zählen/Indizieren aller Einträge nicht herumkommen. Letzteres kann nicht effizienter sein als die Suche selbst.

Ich fabuliere mal etwas stärker: Kann man vom Zustand nicht auf die Problemgröße schließen, wird solch eine Funktion im Allgemeinen nicht existieren.


-----------------
Why waste time learning when ignorance is instantaneous?
- Bill Watterson -



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Goswin
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 18.09.2008
Mitteilungen: 1443
Aus: Chile, Ulm
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.6, vom Themenstarter, eingetragen 2019-09-23


2019-09-23 09:14 - DerEinfaeltige in Beitrag No. 5 schreibt:
Kann man vom Zustand nicht auf die Problemgröße schließen, wird solch eine Funktion im Allgemeinen nicht existieren.

Aber der Zustand enthält doch unter anderem die Eingabedaten, so dass man *immer* die Problemgröße ermitteln kann.

2019-09-23 09:14 - DerEinfaeltige in Beitrag No. 5 schreibt:
Die lineare Suche in einer Liste sollte ein Gegenbeispiel sein.

Beim Start wäre der Funktionswert die Listenlänge, und in jedem Suchschritt wird er um 1 verkleinert. Die Funktion soll in jedem Schritt schneller als der gesamte Algorithmus sein, nicht in der Summe über alle Schritte.



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
DerEinfaeltige
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 11.02.2015
Mitteilungen: 2237
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.7, eingetragen 2019-09-24


2019-09-23 21:25 - Goswin in Beitrag No. 6 schreibt:

Aber der Zustand enthält doch unter anderem die Eingabedaten, so dass man *immer* die Problemgröße ermitteln kann.


Die Eingabedaten der linearen Suche sind nur der Zeiger auf das erste Element.
Will man die Listenlänge wissen, muss man über die komplette Liste iterieren. Das dauert mindestens so lange wie die lineare Suche selbst.
Wenn deine Funktion die Listenlänge benötigt, kann sie daher nicht effizienter sein.


-----------------
Why waste time learning when ignorance is instantaneous?
- Bill Watterson -



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Zwerg_Allwissend
Aktiv Letzter Besuch: im letzten Quartal
Dabei seit: 02.12.2013
Mitteilungen: 216
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.8, eingetragen 2019-10-10


2019-09-22 19:20 - Goswin im Themenstart schreibt:
Wenn für einen deterministischen Algorithmus eine Funktion existiert, die (1)_von der Zustandsmenge des Algorithmus in die natürlichen Zahlen geht und (2)_bezüglich der Schrittzahl des Algorithmus streng monoton fällt, dann muss dieser Algorithmus für jede Eingabe nach endlich vielen Schritten terminieren.

Was ist die "Zustandsmenge eines Algorithmus"? Es reicht, wenn die Funktion die Eingabeparameter nach |N abbildet. Bei einem rekursiv definierten Algorithmus muß das Bild der Parameter des rekursiven Aufrufs kleiner werden, bei Schleifen entsprechend.

2019-09-22 19:20 - Goswin im Themenstart schreibt:
... ob es nicht für *jeden* deterministischen Algorithmus, der bewiesenermaßen terminiert, so eine Funktion geben *muss* (wobei nicht gesagt wird, dass sie leicht zu finden ist).

Versuche mal Deine Behauptung auf die Ackermann-Funktion anzuwenden:

function ack(x : ℕ, y : ℕ) : ℕ <=
if x = 0
  then y + 1
  else if y = 0
         then ack(x - 1, 1)
         else ack(x - 1, ack(x, y - 1))
       end_if
end_if

Weiteres Beispiel:



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Goswin hat die Antworten auf ihre/seine Frage gesehen.
Neues Thema [Neues Thema] Antworten [Antworten]    Druckversion [Druckversion]

 


Wechsel in ein anderes Forum:
 Suchen    
 
All logos and trademarks in this site are property of their respective owner. The comments are property of their posters, all the rest © 2001-2020 by Matroids Matheplanet
This web site was originally made with PHP-Nuke, a former web portal system written in PHP that seems no longer to be maintained nor supported. PHP-Nuke is Free Software released under the GNU/GPL license.
Ich distanziere mich von rechtswidrigen oder anstößigen Inhalten, die sich trotz aufmerksamer Prüfung hinter hier verwendeten Links verbergen mögen.
Lesen Sie die Nutzungsbedingungen, die Distanzierung, die Datenschutzerklärung und das Impressum.
[Seitenanfang]