Wat is een invariant?

Het woord lijkt in een aantal contexten gebruikt te worden. Het beste wat ik kan bedenken is dat ze een variabele bedoelen die niet kan veranderen. Is dat niet waar constanten/finales (verdomme Java!) voor zijn?


Antwoord 1, autoriteit 100%

Een invariant is meer ‘conceptueel’ dan een variabele. Over het algemeen is het een eigenschap van de programmastatus die altijd waar is. Een functie of methode die ervoor zorgt dat de invariant geldt, zou de invariant behouden.

Een binaire zoekboom kan bijvoorbeeld de invariant hebben dat voor elk knooppunt de sleutel van het linkerkind van het knooppunt kleiner is dan de eigen sleutel van het knooppunt. Een correct geschreven invoegfunctie voor deze boom zal die invariant behouden.

Zoals je kunt zien, kun je dat niet in een variabele opslaan: het is meer een statement overhet programma. Door uit te zoeken wat voor soort invarianten uw programma moet onderhouden en vervolgens uw code te herzien om er zeker van te zijn dat deze invarianten ook daadwerkelijk worden onderhouden, kunt u logische fouten in uw code voorkomen.


Antwoord 2, autoriteit 16%

Het is een voorwaarde waarvan u weet dat deze altijd waar is op een bepaalde plaats in uw logica en die u kunt controleren tijdens het debuggen om uit te zoeken wat er mis is gegaan.


Antwoord 3, autoriteit 10%

De magie van wikipedia: Invariant (computerwetenschap)

In de informatica is een predikaat dat,
indien waar, blijft waar gedurende a
specifieke volgorde van bewerkingen, is
genaamd (een) invariant daarvan
volgorde.


Antwoord 4, autoriteit 7%

Ik bekijk ze meestal meer in termen van algoritmen of structuren.

Je zou bijvoorbeeld een lusinvariant kunnen hebben die beweerd kan worden — altijd waar aan het begin of einde van elke iteratie. Dat wil zeggen, als je lus een verzameling objecten van de ene stapel naar de andere zou moeten verwerken, zou je kunnen zeggen dat |stack1|+|stack2|=c, bovenaan of onderaan de lus.

Als de invariante controle mislukt, geeft dit aan dat er iets mis is gegaan. In dit voorbeeld kan het betekenen dat u bent vergeten het verwerkte element op de laatste stapel te duwen, enz.


Antwoord 5, autoriteit 5%

Dit antwoord is voor mijn 5-jarige kind. Beschouw een invariant niet als een constante of vaste numerieke waarde. Maar het kan. Het is echter meer dan dat.

Integendeel, een invariant is zoiets als een vaste relatie tussen verschillende entiteiten. Je leeftijd zal bijvoorbeeld altijd lager zijn dan die van je biologische ouders. Zowel je leeftijd als die van je ouders verandert in de loop van de tijd, maar de relatie die ik hierboven noemde is een invariant.

Een invariant kan ook een numerieke constante zijn. De waarde van piis bijvoorbeeld een onveranderlijke verhouding tussen de omtrek van de cirkel en zijn diameter. Hoe groot of klein de cirkel ook is, die verhouding is altijd pi.


Antwoord 6, autoriteit 5%

Zoals deze regel aangeeft:

In de informatica wordt een predikaat dat, indien waar, waar zal blijven gedurende een specifieke reeks bewerkingen, (een) invariant van die reeks genoemd.

Om deze hoop beter te begrijpen, helpt dit voorbeeld in C++.

Bedenk een scenario waarin je een aantal waarden moet krijgen en het totale aantal ervan moet krijgen in een variabele met de naam counten ze moet toevoegen aan een variabele met de naam sum

De invariant(alweer is het meer een concept):

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

De code voor het bovenstaande zou er ongeveer zo uitzien,

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

Wat doet de bovenstaande code?

1) Leest de invoer van cinen zet ze in x

2) Na één succesvolle lezing verhoogt u counten sum = sum + x

3) Herhaal 1-2 tot het lezen stopt (d.w.z. ctrl+D)

Loop invariant:

De invariant moet True ALWAYSzijn. Dus in eerste instantie begin je je code met alleen dit

while(cin>>x){
  }

Deze lus leest gegevens van standaardinvoer en winkels in x. Goed en wel. Maar de Invariant wordt vals omdat het eerste deel van onze invariant niet werd gevolgd (of waar is gehouden).

// we have read count grades so far, and

Hoe de invariant waar te houden?

Eenvoudig! increment tellen.

Dus ++count;zou goed doen!. Nu wordt onze code zoiets,

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

maar

Zelfs nu onze invariant (een concept dat waar moet zijn) is onjuist omdat we nu niet aan het tweede deel van onze invariant hebben voldaan.

// sum is the sum of the first count grades

Dus wat te doen?

Voeg xnaar sumen bewaar het in sum(sum+=x) EN DE VOLGENDE TIJD
cin>>xLees een nieuwe waarde in x.

Nu wordt onze code zoiets,

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

Laten we

controleren

Of code overeenkomt met onze 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!. Nu is de lus-invariant waar altijd en code werkt prima.

Het bovenstaande voorbeeld was genomen en gewijzigd van het boek versneld C++ door Andrew-Koening en Barbara-E


Antwoord 7, Autoriteit 2%

iets dat niet verandert in een blok van code


Antwoord 8

Volgen vanaf wat het is, zijn invarianten vrij nuttig bij het schrijven van schone code, omdat het conceptueel weten welke invarianten in uw code moeten zijn, kunt u eenvoudig beslissen hoe u uw code kunt organiseren om die code te organiseren Doelstellingen. Zoals vermeld EAALIER, zijn ze ook nuttig bij het debuggen, zoals controle om te zien of de invariant wordt gehandhaafd, vaak een goede manier is om te zien of de manipulatie je probeert uit te voeren, daadwerkelijk is wat je wilt.


Antwoord 9

Het is typisch een hoeveelheid die niet verandert onder bepaalde wiskundige operaties.
Een voorbeeld is een scalaire, die niet verandert onder rotaties. Bij magnetische resonantie-beeldvorming is het bijvoorbeeld handig om een ​​weefselgoed te kenmerken door een rotatie-invariant, omdat dan de schatting idealiter niet afhankelijk is van de oriëntatie van het lichaam in de scanner.


Antwoord 10

Alle antwoorden hier zijn geweldig, maar ik voelde dat ik meer licht kan werpen op de zaak:

Invariant uit een oogpunt van een taal betekent iets dat nooit verandert. Het concept komt echter eigenlijk uit wiskunde, het is een van de populaire prooftechnieken in combinatie met inductie.

Hier is hoe een bewijs gaat, als u een invariant kunt vinden die zich in de eerste toestand bevindt, en dat deze invariant aanhoudt, ongeacht de [Juridische] transformatie die op de staat wordt toegepast, dan kunt u dat bewijzen dat als een bepaalde staat doet Niet deze invariant hebben, dan kan het nooit optreden, ongeacht welke volgorde van transformaties worden toegepast op de initiële toestand.

Nu de vorige manier van denken (opnieuw gecombineerd met inductie) maakt het mogelijk om de logica van computersoftware te prediken. Vooral belangrijk wanneer de uitvoering in lussen gaat, waarin een invariant kan worden gebruikt om te bewijzen dat een bepaalde lus een bepaald resultaat zal opleveren of dat het nooit de staat van een programma op een bepaalde manier zal veranderen.

Wanneer invariant wordt gebruikt om een ​​luslogica te prediken, wordt het lus invariant . Het kan buitenlussen worden gebruikt, maar voor loops is het echt belangrijk, omdat u vaak veel mogelijkheden heeft, of een oneindig aantal mogelijkheden.

Merk op dat ik het woord “Predicaat” de logica van een computersoftware gebruiken en niet bewijzen. En dat komt omdat terwijl in wiskunde invariant kan worden gebruikt als een bewijs, het kan nooit Bewijs dat de computersoftware bij uitvoering zal opleveren wat wordt verwacht, vanwege het feit dat de software bovenop vele abstracties wordt uitgevoerd, die nooit kan worden bewezen dat ze zullen opleveren wat wordt verwacht (denk bijvoorbeeld aan de hardware-abstractie).

Eindelijk, terwijl theoretisch en rigoureus voorspellen softwarelogica is alleen belangrijk voor hoge kritische toepassingen zoals medische en militaire. Invariant kan nog steeds worden gebruikt om de typische programmeur te helpen bij het debuggen. Het kan worden gebruikt om te weten waar het programma op een bepaalde locatie is mislukt omdat het niet in staat is om een ​​bepaalde invariante te handhaven – velen van ons gebruiken het hoe dan ook zonder erover te geven.


Antwoord 11

De ADT-invariante specificeert relaties
Onder de gegevensvelden (exemplaarvariabelen)
Dat moet altijd voor en na
de uitvoering van een willekeurige methode.


Antwoord 12

Class Invariantis een voorwaarde die altijd true moet zijn vóór en na het bellen van de relevante functie

Balanced Tree heeft bijvoorbeeld een Invariantdie isBalancedwordt genoemd. Wanneer u uw boom aanpast via enkele methoden (bijvoorbeeld AddNode, Removenode …) – isBalancedmoet altijd true zijn voor en na het wijzigen van de boom


Antwoord 13

Er is een uitstekend voorbeeld van een invariant en waarom het belangrijk is in het boek Java-concurrency in de praktijk .

Hoewel JAVA-Centric, het voorbeeld een code beschrijft die verantwoordelijk is voor het berekenen van de factoren van een verstrekt geheel getal. De voorbeeldcode pogingen om het meegeleverde laatste getal te cachen, en de factoren die werden berekend om de prestaties te verbeteren. In dit scenario is er een invariant die niet is verantwoord in de voorbeeldcode die de code vatbaar is voor racecondities in een gelijktijdig scenario.

Other episodes