Die Mathe-Redaktion - 19.10.2019 17:21 - Registrieren/Login
Auswahl
ListenpunktHome
ListenpunktAktuell und Interessant ai
ListenpunktArtikelübersicht/-suche
ListenpunktAlle Links / Mathe-Links
ListenpunktFach- & Sachbücher
ListenpunktMitglieder / Karte / Top 15
ListenpunktRegistrieren/Login
ListenpunktArbeitsgruppen
Listenpunkt? im neuen Schwätz
ListenpunktWerde Mathe-Millionär!
ListenpunktFormeleditor fedgeo
Schwarzes Brett
Aktion im Forum
Suche
Stichwortsuche in Artikeln und Links von Matheplanet
Suchen im Forum
Suchtipps

Bücher
Englische Bücher
Software
Suchbegriffe:
Mathematik bei amazon
Naturwissenschaft & Technik
In Partnerschaft mit Amazon.de
Kontakt
Mail an Matroid
[Keine Übungsaufgaben!]
Impressum

Bitte beachten Sie unsere Nutzungsbedingungen, die Distanzierung, unsere Datenschutzerklärung und
die Forumregeln.

Sie können Mitglied werden. Mitglieder können den Matheplanet-Newsletter bestellen, der etwa alle 2 Monate erscheint.

Der Newsletter Okt. 2017

Für Mitglieder
Mathematisch für Anfänger
Wer ist Online
Aktuell sind 371 Gäste und 19 Mitglieder online.

Sie können Mitglied werden:
Klick hier.

Über Matheplanet
 
Zum letzten Themenfilter: Themenfilter:
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: 1323
Aus: Chile, Ulm
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Themenstart: 2019-09-22 19:20


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.



  Profil  Quote  Link auf diesen Beitrag Link
ligning
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 07.12.2014
Mitteilungen: 2761
Aus: Berlin
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.1, eingetragen 2019-09-22 19:28


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


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



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


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. razz 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?



  Profil  Quote  Link auf diesen Beitrag Link
Yggdrasil
Senior Letzter Besuch: im letzten Monat
Dabei seit: 01.07.2004
Mitteilungen: 846
Aus: Berlin
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.3, eingetragen 2019-09-22 23:03


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. biggrin



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


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. biggrin

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



  Profil  Quote  Link auf diesen Beitrag Link
DerEinfaeltige
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 11.02.2015
Mitteilungen: 2139
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.5, eingetragen 2019-09-23 09:14


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 -



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


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.



  Profil  Quote  Link auf diesen Beitrag Link
Folgende Antworten hat der Fragesteller vermutlich noch nicht gesehen.
DerEinfaeltige
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 11.02.2015
Mitteilungen: 2139
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.7, eingetragen 2019-09-24 20:12


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 -



  Profil  Quote  Link auf diesen Beitrag Link
Zwerg_Allwissend
Aktiv Letzter Besuch: im letzten Monat
Dabei seit: 02.12.2013
Mitteilungen: 198
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.8, eingetragen 2019-10-10 21:37


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: de.wikipedia.org/wiki/Sudanfunktion



  Profil  Quote  Link auf diesen Beitrag Link
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-2019 by Matroids Matheplanet
This web site was made with PHP-Nuke, a web portal system written in PHP. 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]