Können wir quantifizieren, wie nahe ein teilweise korrektes Programm an der Richtigkeit liegt?

Ich weiß, dass es etwas gibt, das als teilweise Korrektheit bezeichnet wird, aber ich habe mich gefragt, ob es eine Möglichkeit gibt, festzustellen, wie nahe ein halbkorrektes Programm an einem vollständig korrekten Programm liegt.

Wenn Sie beispielsweise ein Sortierprogramm hätten, das ein Array fast vollständig sortiert, könnten Sie dann mithilfe der Hoare-Logik bestimmen, wie nahe es daran ist, die richtige Antwort zu erhalten? Eine Möglichkeit, dies zu tun, besteht darin, die Vorbedingung zu einer Reihe von und Anweisungen zu machen und zu sehen, wie viele dieser Anweisungen die schwächste Voraussetzung, die sich aus der Weitergabe der Nachbedingung durch das Programm ergibt, implizieren können.

Diese Methode scheint jedoch sehr grob zu sein. Gibt es eine andere Möglichkeit, so etwas zu tun?

Teilkorrektheit bedeutet nicht, dass nicht alle Aussagen einer Spezifikation von einem Algorithmus erfüllt werden. Schauen Sie sich den Wikipedia-Artikel über Korrektheit an :

Teilweise Korrektheit eines Algorithmus bedeutet, dass er die richtige Antwort zurückgibt, wenn er beendet wird.

Völlige Korrektheit bedeutet, dass zusätzlich garantiert wird, dass der Algorithmus beendet wird.

Ein solcher Abschlussnachweis kann zB durch eine Schleifenvariante erfolgen : Um zu beweisen, dass eine Schleife beendet wird, zeigen wir, dass ein ganzzahliger Ausdruck im Schleifenkörper verringert wird und dass der Ausdruck immer nicht negativ bleibt. Dann kann die Schleife nur eine endliche Anzahl von Malen wiederholt werden. Die B-Methode verwendet solche ganzzahligen Varianten in ihren while-Schleifen. Eine Alternative für einen ganzzahligen Ausdruck wäre eine endliche Menge, bei der in jeder Iteration ein Element entfernt wird.

Beispiel : Ein einfacher Algorithmus zum Initialisieren eines Arrays der Größe n mit 0:

i := 0
while i<n do
  x[i] := 0
  i := i+1
done

Die teilweise Korrektheit kann durch Verwendung einer Schleifeninvariante nachgewiesen werden ("alle Elemente von x in 0..isind 0" 0<=i,, i<=n). Man muss zeigen, dass die Invariante beim Eintritt in die Schleife und nach jeder Iteration erfüllt ist. Nach der Schleife wissen wir, dass die Invariante erfüllt ist und die Schleifenbedingung nicht ( i>=nzusammen mit der Schleifeninvariante impliziert dies wiederum i=n, dass "alle Elemente von x in 0..n0 sind"). Selbst wenn wir die Zeile vergessen i := i+1, könnten wir die teilweise Korrektheit des Algorithmus beweisen, dh das Array wird nach Beendigung mit 0 gefüllt. Das Problem wäre, dass es nicht beendet wird.

Die Kündigung kann durch Auswahl n-ials Variante angezeigt werden . Mit der Invariante i<=nkann bewiesen werden, dass die Variante immer nicht negativ ist und n-iin jeder Iteration verringert wird (durch Erhöhen von i). Somit muss die Schleife enden. Zusammen mit der teilweisen Korrektheit wird die vollständige Korrektheit angezeigt.

In einer Nussschale:

Teilrichtigkeit ist eine Frage der Kündigung, nicht der Richtigkeit der berechneten Daten. Eine Funktion ist in Bezug auf eine Spezifikation teilweise korrekt, wenn alles, was sie berechnet, korrekt ist, wenn sie beendet wird. Diese Idee kann auf die Berechnung unvollständiger (Teil-) Antworten ausgedehnt werden. Was auch immer aus der Antwort berechnet wird, ist korrekt, aber das Programm kann irgendwann in eine nicht terminierende Schleife geraten, möglicherweise ohne die gesamte Antwort berechnet zu haben. Teilantworten sind Annäherungen an vollständige Antworten.

Diese Approximationsstruktur ist eine Teilordnung, die das Grundkonzept von Scotts Semantikdomänen darstellt und tatsächlich zur Beantwortung einer anderen Interpretation der Frage verwendet werden kann. Können wir einen Abstand zwischen einer richtigen und einer nicht ganz richtigen Antwort messen, z. B. wenn ein Element eines Arrays falsch (und nicht unbekannt) ist? Eine Möglichkeit, einen solchen Abstand zu definieren, besteht darin, die Näherungsreihenfolge zu berücksichtigen und die beiden inkompatiblen Antworten (die richtige und die falsche) mit der besten Teilantwort zu verknüpfen, die eine Annäherung an beide ist. Dieses Problem wird unter dem Gesichtspunkt der numerischen Analyse, bei der eine Präzisionsanalyse unerlässlich ist, und einiger anderer Bereiche schnell betrachtet.

Dieser zweite Punkt wird tatsächlich in einer zweiten Antwort auf die Frage untersucht, da mir zunächst nicht klar war, dass die beiden Antworten einen Zusammenhang haben könnten. Aber beide Antworten sind ziemlich lang, und ich fühlte mich nicht klug, sie zusammenzuführen, als ich die Verbindung erkannte.

Eine erste einfache Ansicht der teilweisen Korrektheit

Es gibt keine Möglichkeit, im absoluten Sinne (teilweise) korrekt zu sein . Ein Programm ist korrekt, wenn es einer bestimmten Spezifikation entspricht. Die Spezifikation kann ein anderes Programm oder eine logische Anweisung sein oder was auch immer formalisiert werden kann. Die Spezifikation muss irgendwie Informationen darüber enthalten, wann das Programm beendet wird, möglicherweise immer (was in den meisten Definitionen tatsächlich angenommen wird, so dass nichts Komplexeres gesagt werden muss). Tatsächlich kann die Domain in der Spezifikation auf den Teil beschränkt sein, in dem eine Kündigung erwartet wird, so dass immer eine Kündigung erwartet wird , was die Annahme einer Kündigung in der gesamten Domäne in der üblichen Definition ( Wikipedia und Wikipedia) rechtfertigen kann). Dies setzt wiederum eine implizite Annahme für jede Spezifikation voraus, die so bequem sein kann oder nicht.

Ein Programm ist in Bezug auf eine Spezifikation korrekt, wenn es beendet wird, wann immer die Spezifikation dies vorschreibt, und mit einem Ergebnis, das der Spezifikation entspricht. Es ist teilweise richtig, wenn es manchmal nicht dort endet, wo es in der Spezifikation angegeben ist, aber beim Beenden immer ein korrektes Ergebnis liefert.$P$$S$

Infolgedessen ist ein Programm, das niemals beendet wird, in Bezug auf eine Spezifikation teilweise korrekt .

Ich habe eine leicht erweiterte Definition gewählt, auch weil sie genau dem Begriff der Approximation in Scotts semantischen Domänen entspricht , wie er in der Denotationssemantik verwendet wird. Eine Scott-Domäne enthält eine Teilreihenfolge, die genau der Idee der Teilkorrektheit entspricht (die beiden Verwendungen des Wortes "Teil" sind etwas unabhängig voneinander). Eine Funktion ist und die Approximation einer Funktion ist endet immer dann, wenn endet, und beide ergeben dann das gleiche Ergebnis. So kann ein Ergebnis geben , wenn nicht. Und wir können sagen, dass Bezug auf teilweise richtig ist oder dass$F$$G$$G$$F$$G$$F$$F$$G$$F$approximieren oder .$G$$F\sqsubseteq G$

Diese Ideen sind wichtig, um die Semantik von Funktionen mit Schleife (oder Rekursion) als die Grenze eines unendlichen Satzes von Funktionen ohne Schleife oder Rekursion zu definieren. Siehe zum Beispiel Wikipedia oder eine sehr informelle Präsentation über SE .

Die Standard-Hoare-Logik funktioniert nur zum Nachweis der teilweisen Korrektheit und muss erweitert werden, um die Terminierungseigenschaften und damit die vollständige Korrektheit zu adressieren (siehe Wikipedia ). Es gibt Beispiele für solche spezifischen Erweiterungen.

Der Nachweis der vollständigen Korrektheit bedeutet den Nachweis der teilweisen Korrektheit und Beendigung. Die Hoare-Logik ist für die teilweise Korrektheit durchaus geeignet. Der Nachweis der Beendigung erfordert normalerweise einen Beweis durch Induktion (Wiederholung), was der natürliche Ansatz ist, um Dinge in Scotts Semantik zu beweisen (da die Semantik selbst auf diese Weise induktiv definiert ist). Die Antwort von Danielp zeigt, wie eine solche Induktion einen Beweis in Hoares Logik ergänzen kann.

Wenn Sie die teilweise Korrektheit quantifizieren möchten, können Sie die Teile der Domäne, in denen das Programm beendet wird oder nicht, oder einige Eigenschaften dieser Teile identifizieren, sofern Sie dies dennoch möchten.

Erweiterung auf komplexe Ergebnisse, angewendet auf das Sortierbeispiel.

Tatsächlich kann das Problem etwas komplexer sein, wenn Sie komplexe Antworten wie Datenstrukturen berücksichtigen (was beim Sortieren von Arrays der Fall ist). Die Spezifikation könnte die Berechnung von zwei Antworten (dh eines Paares) erfordern, und für einige Teile der Eingabedomäne könnte ein tatsächliches Programm ein Element des Paares finden, aber nicht enden, während das andere berechnet wird, in anderen Fällen nur das andere Element, oder finden Sie beide, oder finden Sie keine. Dies ist immer noch eine Annäherung im Sinne von Scott, und ein solches Programm ist teilweise korrekt.

Allgemeiner gilt die Idee der Annäherung im Scott-Sinne sowohl für Daten als auch für Programme. Dazu benötigen Sie informell das Konzept einer unbekannten Antwort (noch nicht berechnet, möglicherweise nie bekannt, wenn die Berechnung nicht beendet wird). Es wird normalerweise durch das Symbol . Das Paar nähert sich . Was Sie in einem Programm erhalten, das den 36-Teil liefert und dann nicht beendet wird, kann durch .$\perp$$(\perp,36)$$(25,36)$$(\perp,36)$

Wie kann dies auf ein Programm angewendet werden, das Arrays mit fünf Ganzzahlen sortiert? Angenommen, Sie schreiben ein Programm SORT5, das parallel zu Ihrer Hauptanwendung ausgeführt wird (ich versuche, die Dinge realistisch zu machen) und ein solches Array für die Anwendung sortieren soll. Das Programm SORT5 soll sein Ergebnis in einem von der Anwendung bereitgestellten Array speichern und kann dies für jedes Element separat tun, sobald es weiß, wo es platziert werden soll. Es sucht zuerst nach dem größten und dem kleinsten und speichert sie an beiden Enden. Dann versucht es, eine Rekursion (oder was auch immer) durchzuführen, hat jedoch einen Fehler, der es ohne weitere Ergebnisse in eine Endlosschleife sendet. Die Hauptanwendung erhält noch eine teilweise Antwort. Wenn das zu sortierende Array , lautet die Antwort$[25, 36, 3, 9, 12]$$[3,\perp,\perp,\perp,36]$anstelle von . Was auch immer bereitgestellt wird, ist korrekt und der Rest wird nicht berechnet, sodass Sie nur einen Teil der Antwort haben . Sie haben also eine Annäherung an das gewünschte Ergebnis. Wenn Sie nachweisen können, dass dies immer der Fall ist, ist Ihr fehlerhaftes Programm SORT5, das nicht beendet wird, in Bezug auf die Spezifikation eines Sortierprogramms teilweise noch korrekt.$[3,9,12,25,36]$

Ein teilweise korrektes Programm kann nützlich sein. Es könnte sein, dass Sie nicht wirklich sortieren mussten, sondern nur das größte und kleinste Element. In diesem Fall spielt die Tatsache, dass Ihr Sortierprogramm SORT5 nicht beendet wird und nur teilweise korrekt ist, keine Rolle, und Ihre Anwendung funktioniert und wird hoffentlich mit einer korrekten Antwort beendet.

Aber wer wird Ihren Rogue-Sortieralgorithmus stoppen, der weiterhin Rechenleistung verschwendet? Es gibt Berechnungsstrategien (Lazy Evaluation), bei denen kein Unterprogramm ausgeführt wird, wenn derzeit keine weiteren Informationen zum Ergebnis benötigt werden. Nachdem Sie das größte und kleinste Element erhalten haben, wird das Programm SORT5 angehalten, bis andere Elemente angefordert werden.

In diesem Fall könnte es natürlich eine Möglichkeit geben, die teilweise Korrektheit zu quantifizieren. Ich bin mir jedoch nicht sicher, ob es sehr nützlich wäre.

In diesem Zusammenhang ist es notwendig, die Definition ein wenig zu überarbeiten, was ich etwas informell mache:

Ein Programm P ist in Bezug auf eine Spezifikation S teilweise korrekt, wenn es eine vollständige Antwort gibt, die der Spezifikation vor dem Beenden entspricht, oder einen Teil einer Antwort liefert, die der Spezifikation entspricht, bevor eine nicht terminierende Berechnung durchgeführt wird, die keinen weiteren Teil der Antwort liefert .

Dann ist ein Programm, das niemals beendet wird und keinen Teil des Ergebnisses erzeugt, in Bezug auf eine Spezifikation teilweise korrekt.

Beachten Sie, dass diese Definition ein Programm auslässt, das ständig rechnet und immer neue Teile der Antwort erzeugt. Aber da es keine Infinitesimale erzeugt (ich weiß nicht, dass dies rechnerisch sinnvoll sein könnte), berechnet es tatsächlich eine unendliche Antwort.

Diese Techniken können tatsächlich sehr fruchtbar sein, um die Semantik der Berechnung eines unendlichen Objekts (nur für sehr geduldige Benutzer) zu formalisieren, wie beispielsweise die exakte dezimale (oder binäre) Darstellung des Werts von oder unendliche Listen. Es gibt andere interessante Anwendungen. Aber das ist weit von der ursprünglichen Frage entfernt, und deshalb lasse ich es weg.$\pi$

Die Quantifizierung der Korrektheit von Programmen ist heutzutage im Kontext formaler Methoden ein ziemlich heißes Thema. Anstatt eine Referenzliste zu veröffentlichen, können Sie hier ¹ (Vollversion hier ) beginnen und mit den Referenzen fortfahren. Offenlegung: Dieses Papier ist eine Arbeit von mir.

Eine kurze Zusammenfassung dieser Arbeit: Wir führen einen Spezifikationsformalismus ein, der die lineare zeitliche Logik um eine Reihe von "Qualitätsfunktionen" erweitert. Diese Funktionen werden vom Designer ausgewählt, sodass der Designer die Qualität nach Belieben definieren kann.

Wir zeigen, dass die Modellprüfung für diese Logik in PSPACE erfolgt. Mit den entsprechenden Qualitätsfunktionen können Sie beispielsweise den Abstand eines Arrays von einem sortierten messen.

1. Formalisierung und Argumentation über Qualität von S. Almagor, U. Boker und O. Kupferman (2013)

Im Prinzip ist es möglich, diese Bedingung mit etwas wie der Hoare-Logik auszudrücken, aber es ist nicht klar, ob dies sehr nützlich oder praktisch ist.

Betrachten Sie eine Funktion in Ihrem Programm mit einem Argument. Angenommen, wir haben ein Prädikat , das die Bedingung ausdrückt, dass die richtige Antwort auf die Eingabe , dh wenn die Ausgabe am Eingang ist diese Ausgabe korrekt. Nehmen wir auch an, wir haben ein Prädikat , das ausdrückt, dass die Antworten und nahe beieinander liegen. Definieren Sie das Prädikat durch$f$$P(x,y)$$y$$x$$f$$y$$x$$Q(y,y')$$y$$y'$$R(x,y')$

Dann drückt die gewünschte Bedingung aus, dh dass nahe an der richtigen Antwort auf die Eingabe .$R(x,y')$$y'$$x$

In Ihrem Beispiel könnte die Aussage ausdrücken, dass eine sortierte Version von , und könnte eine Entfernungsmetrik in Listen ausdrücken (z. B. dass von durch erhalten werden kann eine kleine Anzahl von Transpositionen).$P(x,y)$$y$$x$$Q(y,y')$$y'$$y$

Das ist nur das Problem der Spezifikation. Es gibt ein separates Problem der Überprüfung, dh die Überprüfung, ob eine Funktion die Spezifikation erfüllt . Das Überprüfungsproblem kann in der Praxis hässlich und schwierig sein. Wie jmite feststellt, ist es im Allgemeinen unentscheidbar, zu überprüfen, ob eine Implementierung einer Funktion einer bestimmten Spezifikation entspricht. Wie immer bei der Überprüfung haben Sie es also immer mit Unentscheidbarkeit zu tun (z. B. Unvollständigkeit).$f$$R$

Unrichtigkeit

Ich habe eine erste Antwort über teilweise Korrektheit geschrieben, die eine genaue technische Bedeutung hat. Ich dachte besser daran, diese andere Antwort zu trennen, die ich anfangs technisch sehr unterschiedlich fand. Es stellt sich heraus, dass es nicht ganz richtig ist, aber beide Antworten sind lang genug, deshalb dachte ich besser, sie nicht zusammenzuführen

Anscheinend scheint das OP mehr an einer Idee von Programmen interessiert zu sein, die teilweise falsch sind, Antworten zu finden, die in gewisser Hinsicht falsch sind, aber ich denke, hoffentlich nicht zu weit davon entfernt, richtig zu sein.

Es gibt tatsächlich zwei Möglichkeiten, die Nähe zu berücksichtigen, um eine Funktion zu korrigieren:

• ob berechnete Antworten richtige und falsche Teile haben oder

• ob sie manchmal richtig und manchmal falsch sind.

Diese beiden Aspekte können jedoch kombiniert werden. Wenn Sie es schaffen, so etwas wie einen Abstand zwischen Werten im Antwortsatz zu definieren, können Sie versuchen, diesen Abstand auf einen Abstand zwischen Funktionen auszudehnen, der äußerst informell eine Art Integral des Abstands ihres Ergebnisses für jeden Punkt ihrer Domäne ist oder eine andere Funktion der Unrichtigkeit für jeden Punkt der Domäne.

Dann kann das Problem darin bestehen, zu bestimmen, ob der Abstand zwischen der vollständig korrekten und der programmierten Funktion einen festen Schwellenwert nicht überschreitet oder ob der Fehler beim Ergebnis der Anwendung der Funktion für jeden Domänenpunkt einen möglicherweise verwandten Schwellenwert nicht überschreitet zu diesem Domainpunkt.

Diese Techniken können auch nützlich sein, um die Berechnung so korrekt wie möglich durchzuführen, wobei Daten, die in gewissem Sinne zunächst nicht korrekt sind, wie z. B. experimentelle Ergebnisse. Wenn der Grad der Unrichtigkeit bewertet oder angenommen werden kann, kann dies dazu beitragen, die Auswirkungen auf die Berechnung zu verfolgen.

Dies hängt wahrscheinlich stark von der Art der Daten ab, auf denen Sie rechnen.

Ich glaube, es gibt bereits eine solche Theorie für das numerische Rechnen, die oft für technische Arbeiten angewendet wird, aber ich weiß wenig darüber. Grundlegende Aspekte werden häufig in Physikkursen vermittelt.

Viele numerische Berechnungen befassen sich mit reellen Zahlen. Es kann nicht genau (richtig) sein, da der Computer nur Annäherungen an reelle Zahlen verwendet (es gibt ein Konzept des Rechnens mit exakter reeller Arithmetik , aber es ist ein ganz anderes Thema, das theoretisch sehr stark mit der teilweisen Korrektheit zusammenhängt ). Annäherungen bei der numerischen Berechnung verursachen kleine Fehler ( Rundungsfehler)), die sich ausbreiten und manchmal außer Kontrolle geraten können. Daher haben Numeriker Techniken entwickelt, um ihre Programme zu analysieren und zu bewerten, wie nahe die Antwort am richtigen Ergebnis liegt. Sie entwerfen ihre Algorithmen tatsächlich so, dass die Rechenfehler zusätzlich zu den anderen üblichen Kriterien minimiert werden, da die Reihenfolge einiger Operationen einen tiefgreifenden Einfluss auf die Größe des übertragenen Fehlers haben kann.

Diese Techniken sind auch wichtig, weil sie häufig mit physischen Daten umgehen müssen , die selbst nur "nahezu korrekt" sind, dh mit einer gewissen Annäherung angegeben werden. Die Behandlung der Fehler in der Eingabe zusammen mit Rechenfehlern und deren Ausbreitung ist meines Erachtens Gegenstand bedeutender Forschungen auf dem Gebiet der numerischen Analyse . Aber ich bin kein Experte. Einige Programme berechnen sowohl das ungefähre Ergebnis als auch ein Fehlerintervall, in dem die richtige Antwort gefunden wird. Dies setzt sowohl die physikalischen Messfehler als auch die numerischen Berechnungsfehler zusammen.

Während dies in der numerischen Mathematik, die sich mit Realen (einem kontinuierlichen Satz von Werten) befasst, im Wesentlichen unvermeidbar war, gibt es keine ähnliche eingebaute Einschränkung für die symbolische Berechnung , daher kein offensichtlicher Anreiz a priori, ähnliche Techniken zu entwickeln. Darüber hinaus ist es möglicherweise nicht offensichtlich, dies zu tun.

Ein genauer Blick auf Fehlerbehandlungstechniken beim Parsen und bei der Verarbeitung natürlicher Sprache zeigt jedoch, dass sie tatsächlich eine ähnliche konzeptionelle Sichtweise verwenden, selbst in einem rein symbolischen Kontext.

Die Antwort von Shaull scheint darauf hinzudeuten, dass man an solchen Approximationsideen in der Softwareentwicklung interessiert sein könnte , aber ich bin nicht sicher, ob es sich um dieselben Konzepte handelt. Ich habe seine Arbeit nicht gelesen und wenig über die Literatur zu diesem Thema gelesen, und die Antwort gibt keinen Hinweis auf die Techniken, die er in Betracht ziehen könnte.

Dies kann eine ganz andere Idee sein, da sich das Software-Engineering stark mit der Messung des Fehlers der Software befasst, jedoch versehentlich mit einem Fehler. Ich weiß, dass einige statistische Analysen zeigen, dass verschiedene Parameter, die an einem Programm gemessen werden können, statistisch mit der Qualität des Programms, seiner Wartbarkeit und der Wahrscheinlichkeit von Fehlern zusammenhängen.

Die IDs der ungefähren Antworten in der numerischen Analyse (zum Beispiel) sind keine Frage von Fehlern, sondern der Behandlung der Einschränkungen physikalischer Messungen sowie der Einschränkungen des Rechnens (das von Natur aus zählbar ist), wenn es zur Behandlung von Real verwendet wird ( die unzählig sind). Wenn es ein Fehler ist, ist das die Schuld unseres Universums, nicht der Programmierer.

Versuch, die Probleme zu vereinheitlichen: teilweise Korrektheit und Unkorrektheitsmessung

Das Folgende ist rein spekulativ und ein Hinweis auf die Arbeit, die getan werden könnte. Ich würde vermuten, dass zumindest ein Teil davon bereits erledigt wurde (ich habe nicht gründlich gesucht). Aber ich erinnere mich nicht daran, darüber gelesen zu haben und kann keine richtigen Referenzen geben. Die Beschreibung ist nur eine Skizze, und es ist wahrscheinlich, dass ein Großteil davon verfeinert oder präzisiert werden sollte, einschließlich der Auswahl der Definitionen. Ich kann nichts garantieren, was ich mathematisch nicht vollständig ausgearbeitet habe (und selbst dann ... :).

Es gibt eine veröffentlichte Literatur zur Berechnung reeller Zahlen, die auf Definitionen von Näherungen reeller Zahlen basiert, die sie in einer Scott-Domäne organisieren. Das Annähern von Real mit Intervallen ist sicherlich ein Weg, dies zu tun, und das ist ein geeigneter Weg, um eine Theorie der Berechenbarkeit über den Real zu entwickeln. Ich vermute, dass dies bereits geschehen sein muss und eine gute Grundlage für eine Semantiktheorie und für die Analyse von Crunching-Programmen für reelle Zahlen zusammen mit einer Bewertung der Genauigkeit des Ergebnisses wie oben beschrieben bietet. (Ich hatte keine Gelegenheit, einen Spezialisten zu fragen).

Dies kann nun ein Hinweis darauf sein, was mit der symbolischen Berechnung oder mit der Berechnung über die ganzen Zahlen zu tun ist, um eine Vorstellung von einer annähernd korrekten Berechnung zu erhalten, insbesondere bei Vorhandensein komplexer Daten, dh der Verwendung von Datenstrukturen.

Die Grundidee ist dieselbe wie für real. Verwenden Sie ein Approximationskonzept und organisieren Sie Ihre Berechnungsdomäne (die Werte, mit denen Sie berechnen) als Scoot-Domäne. Es muss jedoch so etwas wie ein Gitter sein , bei dem zwei Elemente eine größte Untergrenze (glb oder meet) sowie eine kleinste Obergrenze (lub oder join) haben müssen. Im numerischen Fall entspricht das glb dem kleinsten Intervall, das 2 andere Intervalle enthält, und dem Schnittpunkt zwischen lub und Intervall.

Nehmen Sie unser Sortierbeispiel aus der ersten Antwort und sortieren Sie ein Array mit 5 Zahlen$[25, 36, 3, 9, 12]$Wir könnten alle Teilarrays als Gitter betrachten und haben:

• $lub([3,\perp,\perp,\perp,36], [\perp,9,\perp,\perp,36])=[3,9,\perp,\perp,36]$

• $glb([3,\perp,\perp,\perp,36], [7,9,\perp,\perp,36])=[\perp,\perp,\perp,\perp,36]$

Wenn Sie nun einen Begriff der Entfernung in der Ordnungsstruktur definieren, können Sie die Entfernung zwischen zwei möglichen Antworten als die Summe ihrer Abstände zu ihrem glb (oder einer anderen symmetrischen und monoton ansteigenden Funktion dieser beiden Abstände) definieren.

Wenn die Domäne kein glb hat , können Sie die Entfernungen gemäß jeder der unteren Grenzen (tatsächlich nur die maximalen Elemente der Menge der unteren Grenzen) nehmen und die kleinste solche Entfernung (oder möglicherweise eine andere Funktion der Entfernungen von) berücksichtigen maximale Elemente mit angemessenen Eigenschaften).

Der wichtigste Punkt ist eine nachvollziehbare Definition des Korrektheitsabstands über den von Ihnen manipulierten Daten.

Dann kann dieser Begriff der Entfernung auf die Messung der Entfernungen zwischen Funktionen erweitert werden, was eine Antwort auf die gestellte Frage sein sollte. Ich bin mir nicht sicher, wie viel zusätzlicher mathematischer Aparatus benötigt wird, da möglicherweise eine Form der Integration (im Sinne des Kalküls) erforderlich ist.

Eine flüchtige Suche im Internet zu diesen Themen ergab das folgende Papier: "Auf dem Weg zur Berechnung der Entfernungen zwischen Programmen über Scott Domains ", das bereits 15 Jahre alt ist. Es sollte einen besseren mathematischen Hintergrund bieten. Aber ich habe es gefunden, nachdem ich diese Antwort geschrieben habe.

Dieses Problem kann möglicherweise mit einer anderen Logik angegangen werden, aber ich vermute, dass es viel mehr ein Problem für das Konzept der Approximation innerhalb von Wertebereichen ist. Es gibt andere Möglichkeiten, sie zu erstellen als die oben für Arrays beschriebene. Das Definieren von Annäherungen an Daten kann Teil der Definition eines abstrakten Datentyps oder einer Klasse in der OO-Programmierung sein.

_{Hinweis: Ich habe diesen Zusammenhang mit meiner vorherigen Antwort nicht erwartet. daher die zwei getrennten Antworten.}