in1010 vår2024

(a) Løsningsforslag: Invarianter er betingelser i et program som alltid er sanne. De er en type påstand som forblir uendret før og etter utførelsen av visse operasjoner i et program. For eksempel, i en klasse som representerer en stabel, kan en invariant være at antallet elementer i stabelen aldri er negativt.

(b) Løsningsforslag: Invarianter brukes ofte i programmering for å hjelpe med å sikre at et program fungerer som forventet. De er spesielt nyttige i objektorientert programmering, hvor de kan brukes til å definere og bevare tilstanden til et objekt. Invarianter kan også brukes i løkker (kjent som løkkeinvarianter). En løkkeinvariant er en betingelse som er sann før en løkke begynner og forblir sann etter hver iterasjon av løkken. Løkkeinvarianter benyttes blant annet innen algoritmeanalyse for å bevise korrektheten av en algoritme (mer om algoritmer og algoritmeanalyse i IN2010).

(c) Løsningsforslag: Vi bruker invarianter for å hjelpe med å sikre at et program fungerer som forventet, og for å forhindre at det går inn i en ugyldig tilstand. Ved å definere invarianter, kan vi lage programmer som er mer robuste, lettere å forstå og enklere å feilsøke. De gir også en form for dokumentasjon, da de uttrykker viktige egenskaper ved programmet som skal være sanne til enhver tid. Dette kan være svært nyttig når man prøver å forstå eller endre eksisterende kode.

(d) Løsningsforslag: En mulig invariant for en lenkeliste kan være at “hvert element i listen peker på det neste elementet, og det siste elementet peker på null”. Dette er en grunnleggende egenskap ved lenkelister som forblir konstant uavhengig av operasjonene som utføres på listen (som innsetting, sletting, o.s.v.). Hvis denne invarianten brytes (for eksempel hvis et element peker på feil element), indikerer det vanligvis en feil i koden.

(e) Løsningsforslag: En løkkeinvariant for en for-løkke er en betingelse som er sann før og etter hver iterasjon av løkken. For eksempel, i en for-løkke som itererer over et array, kan en mulig invariant være at "for hver iterasjon, i, er elementene i arrayet sortert fra og med indeks 0 og til og med indeks i". Denne betingelsen er sann før løkken starter (da ingen elementer er behandlet), og den forblir sann etter hver iterasjon.

(a) Før et element er satt inn i lenkelista er lista tom. Både forste og siste er derfor lik null. Når et element settes inn, opprettes en ny Node med et dataelement av typen BaerekraftigArbeidsplass. Etter at noden er satt inn, holder forste og siste på referansen til denne noden. For den første noden i lista er forrige og neste lik null.

(b) Når du henter et element fra lista uten å fjerne det, forblir tilstanden til lista uendret. Det vil si at alle nodene er på samme plass i lista, og alle pekerne (forste, siste, forrige, neste) peker fortsatt på det samme.

1. Arrayopprettelse: Programmet starter med å opprette to arrayer, arr1 og arr2, begge av typen PlantebasertMelk[] og med en lengde på 5. På dette tidspunktet er begge arrayene tomme, det vil si at alle elementene er null.

2. Fylling av arr1: Programmet oppretter nye PlantebasertMelk-objekter og setter referansene til dem inn i arr1. Etter for-løkken er arr1 fylt med referanser til PlantebasertMelk-objekter, mens arr2 fortsatt er tomt (alle elementene er null).

3. Flytting av objekter fra arr1 til arr2: Programmet flytter en og en referanse til et PlantebasertMelk-objekt fra arr1 til arr2, og den tilsvarende posisjonen i arr1 settes til null. Etter for-løkken er arr1 tomt (alle elementene er null), og arr2 inneholder referansene til PlantebasertMelk-objektene.

Invarianten tilsier at sum før hver iterasjon skal inneholde summen av alle tallene fra og med tall[0] til og med tall[i-1]. Invarianten holder derfor ikke.

Programmet må endres til følgende:

public class SumArray {
    public static void main(String[] args) {
        int[] tall = {1, 2, 3, 4, 5};

        // Endring: sum initialiseres til 0 i stedet for 1 (vi endrer førbetingelsen)
        int sum = 0;

        for (int i = 0; i < tall.length; i++) {
            sum += tall[i];
        }

        System.out.println("Summen av elementene i arrayet er: " + sum);
    }
}

Invarianten holder ikke. Den implementerte lista er ei liste med elementer sortert i synkende rekkefølge, fra start til slutt, etter prioritet. Invarianten du fikk oppgitt holder derimot for ei liste med elementer sortert i stigende rekkefølge, fra start til slutt, etter prioritet.

Her er koden med de implementerte endringene, slik at lenkeliste-invarianten holder:

class Node {
    String data;
    int prioritet;
    Node neste;

    Node(String data, int prioritet) {
        this.data = data;
        this.prioritet = prioritet;
    }
}

class Lenkeliste {
    Node hode;

    void settInn(String data, int prioritet) {
        Node nyNode = new Node(data, prioritet);

        // Endring: byttet ut > med < for at invarianten skal holde
        if (this.hode == null || nyNode.prioritet < this.hode.prioritet) {
            nyNode.neste = this.hode;
            this.hode = nyNode;
        } else {
            Node gjeldende = this.hode;

            // Endring: byttet ut >= med <= for at invarianten skal holde
            while (gjeldende.neste != null && gjeldende.neste.prioritet <= nyNode.prioritet) {
                gjeldende = gjeldende.neste;
            }

            nyNode.neste = gjeldende.neste;
            gjeldende.neste = nyNode;
        }
    }
}

(a) Løsningsforslag invariant og betingelser:

Løkkeinvariant:
Før hver iterasjon ved indeks 'i' i løkken, er subarrayen 'A[0] til A[i]' sortert i ikke-avtagende rekkefølge.

Førbetingelser:
Input 'A' er et array av String-objekter. Det behøver ikke å være sortert, siden formålet med metoden er å sjekke om det er sortert eller ikke.

Etterbetingelser:
Hvis array 'A' er sortert i stigende rekkefølge, vil metoden returnere 'true'.
Hvis array 'A' ikke er sortert i stigende rekkefølge, vil metoden returnere 'false'.

(b) Løsningsforslag rekursiv løsning:

public class Sorteringssjekk {
    public static boolean erSortert(String[] A) {
        return erSortertRekursiv(A, 0);
    }

    private static boolean erSortertRekursiv(String[] A, int indeks) {
        if (indeks >= A.length - 1) {
            return true;
        }
        if (A[indeks].compareTo(A[indeks + 1]) > 0) {
            return false;
        }
        return erSortertRekursiv(A, indeks + 1);
    }
}

For hver observatør som har blitt varslet til nå (én observatør varsles per iterasjon), er observatørens tilstand konsistent med tilstanden til subjektet (subjektet varsler observatørene om endringer). Med andre ord, hver observatør som har blitt varslet har mottatt og behandlet oppdateringen fra subjektet.

Invarianten til Singleton-mønsteret i den gitte koden er at det bare vil være én instans av Singleton-klassen gjennom hele kjøretiden til et program. Denne instansen er enten satt til null (før den er opprettet) eller til Singleton-instansen (etter at den er opprettet).