Was ist eine Invariante?

Question

Das Wort scheint in einer Reihe von Zusammenhängen zu gewöhnen. Das Beste, was ich herausfinden kann, ist, dass sie eine Variable bedeuten, die nicht geändert werden können. Ist das nicht was / Finale Konstanten (darn Sie Java!) Sind für?

Answer 1

Ein invariant ist mehr „konzeptuelle“ als eine Variable. Im Allgemeinen ist es eine Eigenschaft des Programmzustandes, der immer wahr ist. Eine Funktion oder ein Verfahren, das sicherstellt, dass die invariant hält gesagt, um die invariant zu halten.

Zum Beispiel kann ein binärer Suchbaum könnte die invariante hat, dass für jeden Knoten, der Schlüssel des linken Kindes des Knotens ist kleiner als der eigene Schlüssel des Knotens. Eine korrekt geschrieben Einfügefunktion für diesen Baum wird diese invariant halten.

Wie Sie sagen, das ist nicht das, was Sie in einer Variablen speichern können: es ist mehr eine Aussage über das Programm. Durch herauszufinden, welche Art von Invarianten Ihr Programm beibehalten sollte, dann bewerten Sie den Code, um sicherzustellen, dass es hält tatsächlich, diese Invarianten, Sie logische Fehler im Code vermeiden.

Answer 2

Es ist eine Bedingung wissen Sie immer wahr zu sein an einem bestimmten Ort in Ihrer Logik und können überprüfen, wenn das Debuggen um herauszufinden, was schief gegangen ist.

Answer 3

ich in der Regel sehen sie mehr in Form von Algorithmen oder Strukturen.

Zum Beispiel könnten Sie eine Schleifeninvariante haben, die geltend gemacht werden könnten - immer wahr am Anfang oder Ende jeder Iteration. Das heißt, wenn Sie Ihre Schleife eine Sammlung von Objekten von einem Stapel zum anderen verarbeiten sollte, könnte man sagen, dass | stack1 | + | Stack2 |. = C, am oberen oder unteren Ende der Schleife

Wenn die invariant Prüfung nicht bestanden, wäre es etwas schief gelaufen zeigen. In diesem Beispiel könnte es bedeuten, dass Sie vergessen haben, das verarbeitete Element auf das endgültige Stapel zu schieben, etc.

Answer 4

Die Magie von wikipedia: Invariant (Informatik)

  

In der Informatik, ein Prädikat, das,   wenn sie wahr wird, treu bleiben überall ein   spezifische Sequenz von Operationen ist   genannt (ein) invariant dass   Sequenz.

Answer 5

Wie diese Zeile heißt es:

  

In der Informatik, ein Prädikat, das, wenn sie wahr ist, wird während einer bestimmten Folge von Operationen wahr bleiben, heißt (an) invariant zu dieser Sequenz.

Um besser zu verstehen, diese Hoffnung dieses Beispiel in C ++ unterstützt.

ein Szenario vor, wo Sie einige Werte erhalten haben und die Gesamtzahl der sie in einer Variablen als count und fügen Sie sie in einer Variablen als sum genannt genannt bekommen

Die invariant (wieder, es ist mehr wie ein Konzept):

// invariant:
// we have read count grades so far, and
// sum is the sum of the first count grades

Der Code für die oben wäre so etwas wie dies,

int count=0;
double sum=0,x=0;
while (cin >> x) {
++count;
sum+=x;
}

Was der obige Code funktioniert?

1) Liest den Eingang von cin und setzt sie in x

2) Nach einem erfolgreichen Lesen, erhöhen count und sum = sum + x

Wiederholen

3) 1-2, bis Lese Anschläge (d Strg + D)

Schleifeninvariante:

Die Invariante muss wahr sein immer . Also zunächst starten Sie Ihren Code aus mit nur diese

while(cin>>x){
  }

Diese Schleife liest Daten von der Standardeingabe und speichert in x. Schön und gut. Aber die invariant falsch wird, da der erste Teil unserer invariant wurde nicht gefolgt (oder gehalten true).

// we have read count grades so far, and

Wie die invarianten wahr halten?

Einfach! Schrittzahl.

So ++count; täte gut !. Jetzt ist unser Code so etwas wie dieses wird,

while(cin>>x){
 ++count; 
 }

Aber

Auch jetzt unser invariant (ein Konzept, das wahr sein muss) ist falsch, weil jetzt haben wir nicht den zweiten Teil der unser invariant erfüllen.

// sum is the sum of the first count grades

Also, was jetzt zu tun?

In x sum und speichern sie in sum (sum+=x) und das nächste Mal cin>>x wird einen neuen Wert in x lesen.

Jetzt ist unser Code wird so etwas wie dies,

while(cin>>x){
 ++count; 
 sum+=x;
 }

Lassen Sie uns prüfen

Ob Code entspricht unsere invariant

// invariant:
// we have read count grades so far, and
// sum is the sum of the first count grades

code:

while(cin>>x){
 ++count; 
 sum+=x;
 }

Ah !. Nun ist die Schleifeninvariante True immer und Code funktioniert gut.

Das obige Beispiel wurde genommen und modifiziert von Buch Accelerated C ++ von Andrew-Koening und Barbara-E

Answer 6

Etwas, das in einem Block von Code nicht ändern

Answer 7

Im Anschluss an was es ist, Invarianten sehr nützlich sind in sauberen Code zu schreiben, da konzeptionell zu wissen, welche Invarianten sollten vorhanden sein, in Code ermöglicht es Ihnen, leicht zu entscheiden, wie Sie Ihren Code zu organisieren diejenigen zu erreichen Ziel hat. Wie ealier erwähnt, sind sie bei der Fehlersuche auch nützlich, wie zu überprüfen, ob das Wesen oft behauptet ist unveränderlich ist ein guter Weg, wenn zu sehen, was auch immer Manipulation Sie versuchen tatsächlich auszuführen ist zu tun, was Sie wollen es.

Answer 8

Es ist in der Regel eine Menge, die unter bestimmten mathematischen Operationen nicht ändert. Ein Beispiel: ist ein Skalar, die bei Drehungen nicht ändert. Bei der Magnetresonanz-Bildgebung, zum Beispiel, ist es nützlich, eine Gewebeeigenschaft durch eine Rotations invariant zu charakterisieren, weil dann seine Abschätzung der Orientierung des Körpers in dem Scanner nicht optimal ab.

Answer 9

Die ADT invariant Beziehungen der festlegt, unter den Datenfeldern (Instanzvariablen) das muss immer richtig sein vor und nach die Ausführung jeder Instanzmethode.