Informasjonsteknologi 2 Høst 2023

Vi tester løsningene med to lister: [3, 7, 5] (ingen like tall) og [5, 5, 3]. I den siste listen er 5 størst to ganger, så det riktige svaret er 3.

Løsning 1 finner det største tallet, fjerner det fra listen og finner deretter det største av tallene som er igjen. Det blir riktig så lenge alle forekomstene av det største tallet fjernes. Fjernes bare én forekomst (som liste.remove(x) i Python), blir resultatet det samme som i løsning 3.

Løsning 2 har en sjekk for like tall (tall NOT EQUAL TO størst) inne i løkken. Den starter likevel med de to første tallene uten å sjekke om de er like. For [5, 5, 3] blir både størst og nestStørst 5 før løkken starter, og tallet 3 endrer ikke dette. Løsningen feiler hver gang listen begynner med to like tall og det ikke kommer et større tall senere.

Løsning 3 mangler sjekken for like tall. Når samme største tall kommer en gang til, er det større enn nestStørst, og det blir satt som nest størst.

Løsning 4 sorterer listen synkende. Da ligger alle forekomstene av det største tallet først. Det første tallet som er ulikt tallet foran seg, er det nest største. For [5, 5, 3] er rekkefølgen etter sortering 5, 5, 3, og løkken skriver ut 3.

De to riktige løsningene er derfor 1 og 4.

Hvordan de virker. Løsning 1 bruker to vanlige gjennomganger av listen og finner det største tallet hver gang. Løsning 4 overlater mesteparten av arbeidet til en sorteringsalgoritme og trenger bare å se på tallene øverst i den sorterte listen.

Effektivitet. Løsning 1 går gjennom listen to ganger. I tillegg må den finne og fjerne forekomstene av det største tallet. Tidsbruken vokser proporsjonalt med antall tall $n$ (lineær tid). Å sortere en liste tar mer tid, typisk proporsjonalt med $n\cdot \log n$ med en god sorteringsalgoritme. Løsning 4 blir derfor tregere enn løsning 1 for store lister. For lister med noen hundre eller tusen tall merkes ikke forskjellen.

Lesbarhet og hvor lett de er å implementere. Løsning 4 er kortest. De fleste språk har en innebygd sorteringsfunksjon, så løsningen kan skrives med få linjer. Løsning 1 er også enkel, men lengre. Den krever at vi vet hvordan listefunksjonen for å fjerne elementer virker, siden remove i mange språk fjerner bare den første forekomsten.

Sideeffekter. Begge løsningene endrer listen: løsning 1 fjerner elementer, og løsning 4 endrer rekkefølgen. Trenger programmet den opprinnelige listen senere, må begge jobbe på en kopi.

Spesialtilfeller. Hvis alle tallene i listen er like, finnes det ikke noe nest største tall:

• Løsning 1 ender med en tom liste og viser «negativt uendelig tall». Det må håndteres særskilt.
• Løsning 4 finner ikke to ulike naboer og viser ingenting.

I løsning 4 finnes det heller ikke noe «neste tall» når løkken kommer til det siste tallet. Løkken må derfor stoppe på det nest siste tallet, ellers gir programmet en feil (indeks utenfor listen).

Konklusjon. Løsning 4 er enklest å skrive og lese og passer godt for små og mellomstore lister. Løsning 1 er mer effektiv for store datamengder. Den beste løsningen for store lister er én gjennomgang som ligner løsning 2, men som også tar hensyn til like tall helt fra starten.

Pseudokoden går gjennom listen én gang og sammenligner hvert element med naboen til høyre:

Etter én gjennomgang er listen [5, 2, 6, 8, 12]. Det største tallet som ikke står på riktig plass, «bobler» mot høyre, men listen er ikke ferdig sortert, siden 5 og 2 står i feil rekkefølge.

Algoritmen sier at gjennomgangen skal gjentas til en hel gjennomgang skjer uten ombyttinger. Vi trenger derfor

1. en ytre løkke som gjentar gjennomgangen
2. en variabel byttet som husker om det har skjedd en ombytting i denne runden
3. en funksjon byttPlass() som vet hvilke elementer den skal bytte

FUNCTION byttPlass(a, i)
    SET temp TO a[i]
    SET a[i] TO a[i+1]
    SET a[i+1] TO temp
ENDFUNCTION

REPEAT
    SET byttet TO FALSE
    SET i TO 0
    FOR hver i LESSER THAN n - 1
        IF a[i] GREATER THAN a[i+1]
            CALL byttPlass(a, i)
            SET byttet TO TRUE
        ENDIF
    ENDFOR
UNTIL byttet EQUAL TO FALSE

DISPLAY a

Forklaring av endringene:

• Ytre løkke. Den opprinnelige for-løkken er én gjennomgang. Den er lagt inne i en REPEAT … UNTIL-løkke. Vi må alltid gjennom listen minst én gang for å vite om den er sortert, og derfor passer REPEAT … UNTIL, som sjekker betingelsen til slutt. En WHILE byttet EQUAL TO TRUE-løkke virker også hvis byttet settes til TRUE før løkken.
• Flagget byttet. Det settes til FALSE ved starten av hver gjennomgang og til TRUE hver gang to elementer bytter plass. Er det fortsatt FALSE etter en hel gjennomgang, er listen sortert, og løkken stopper.
• Funksjonen byttPlass(a, i). Funksjonen må vite hvilken liste og hvilken plass den skal jobbe med. Derfor får den a og i som parametere. Vi trenger en hjelpevariabel temp. Uten den ville vi overskrevet a[i] før verdien var flyttet til a[i+1].

For listen i a) blir gjennomgangene:

Etter tredje gjennomgang har det ikke skjedd noen ombytting, så programmet stopper og viser den sorterte listen.

Mulig forbedring: Etter hver gjennomgang står det største av de usorterte tallene på riktig plass bakerst. Den indre løkken kan derfor stoppe ett element tidligere for hver gjennomgang. Det er ikke nødvendig for at algoritmen skal virke.

Åpen bank og nye betalingstjenester (PSD2). Tidligere var det bare banken som hadde tilgang til kundens kontoer og transaksjoner. Betalingstjenestedirektivet PSD2 (2018) krever at bankene, når kunden samtykker, åpner for at andre aktører kan hente ut kontoinformasjon og sette i gang betalinger via standardiserte grensesnitt (API-er).

Dette har gitt nye typer tjenester:

• Kontoinformasjonstjenester samler kontoer fra flere banker i én app, lager budsjett og gir råd om privatøkonomien basert på transaksjonene.
• Betalingsinitieringstjenester lar en nettbutikk eller en app betale direkte fra kundens konto uten kort.

Endringen skyldes informasjonsteknologi. Smarttelefoner, skytjenester, API-er og dataanalyse gjør det mulig for små teknologiselskaper (fintech) å bygge tjenester «på toppen av» bankenes data og infrastruktur. Konkurransen øker, og kundene har fått raskere og mer brukervennlige tjenester, jf. rapporten fra Datatilsynet.

Andre mulige endringer: forsikring priset etter sensordata fra bil, hjem eller aktivitetsarmbånd, kredittvurdering med kunstig intelligens, og mobilbetaling (Vipps).

Dilemmaet. Når nye aktører får tilgang til transaksjonene våre, får kunden bedre og billigere tjenester, men mister samtidig oversikt og kontroll over hvem som vet hva om privatøkonomien. Begge sider har gode argumenter.

For å dele dataene:

• Kunden får bedre oversikt over egen økonomi, persontilpassede råd og kan lettere sammenligne og bytte tilbydere.
• Økt konkurranse gir lavere priser og nye tjenester.
• Tilgangen krever samtykke, og PSD2 og GDPR stiller krav til sikker identifisering, formålsbegrensning og innsyn. Kunden bestemmer i prinsippet selv.

Mot å dele dataene:

• Transaksjonene røper svært mye: hvor vi er, hva vi handler, helse (apotek, lege), religion, fagforening og vaner. Ved sammenstilling kan selskapene trekke slutninger som kunden aldri har samtykket til å dele.
• Informasjon som før lå hos noen få banker, spres til mange små aktører. Hver av dem kan bli en vei inn for kriminelle, og ved en datalekkasje er skaden stor.
• Samtykket er ofte lite reelt. Mange godtar vilkårene uten å lese dem. Gratis tjenester kan være betalt med data, og det kan bli «bli sporet eller betal»: den som ikke vil dele, får dårligere eller dyrere tilbud.
• Profilering kan føre til forskjellsbehandling, for eksempel at noen får dårligere lånevilkår basert på handlemønster.

Konklusjon. Åpen bank gir reelle fordeler, og det er ikke ønskelig å stanse utviklingen. Personvernet må likevel ivaretas av aktørene, ikke bare av kunden. Tjenestene bør bare hente de dataene de trenger (dataminimering), være åpne om bruken, gjøre det enkelt å trekke tilbake samtykket og tilby alternativer uten deling. Da kan kunden velge fritt, og tilliten som finanssektoren er avhengig av, blir bevart.

Oversikt. Modellen er et UML-klassediagram med seks klasser. Hver boks har tre felt: klassenavnet, egenskapene (attributter med datatype) og metodene (med parametertyper).

Arv. SpillObjekt er superklassen. Navnet er skrevet i kursiv, som betyr at klassen er abstrakt. Det skal ikke lages objekter av selve SpillObjekt, bare av subklassene. Pilene med hul trekant peker fra Menneske, Spøkelse, Hindring og Sau til SpillObjekt. Det betyr at de fire klassene arver fra superklassen. Alle spillobjektene får dermed egenskapene xPosisjon og yPosisjon og metodene plassering(int, int) og flytt(int, int). Felles kode skrives én gang, og brettet kan behandle alle objektene likt.

Komposisjon. Linjen mellom SpillObjekt og Spillebrett har en fylt rombe ved Spillebrett og teksten «inneholder». Det er komposisjon: spillebrettet består av spillobjekter. Objektene lever bare så lenge brettet finnes. Spillebrett har egenskapene høyde, bredde og objekter (en liste med SpillObjekt). Metodene leggTilObjekt og fjernObjekt legger til nye objekter (ny sau, nytt spøkelse og ny hindring etter poeng) og fjerner objekter (sau som blir hentet).

Subklassene:

• Menneske har fart, poeng og bærerSau. Metodene er beveg(int, retning) for styring med piltastene, reduserFart og økPoeng, bærSau(Sau) når mennesket henter en sau, og sjekkKollisjon() som finner ut om mennesket treffer en hindring, en sau, et spøkelse eller kanten.
• Spøkelse har endreRetning(), som brukes når spøkelset treffer kanten av brettet eller en frisone.
• Hindring har ingen egne egenskaper. Den står stille.
• Sau har blirBåret og metodene blirLøftet() og fjernSau().

Polymorfi. plassering(int, int) står i superklassen og igjen i alle subklassene. Det betyr at subklassene overstyrer metoden. Reglene for startplassering er ulike: mennesket i venstre frisone, sauene tilfeldig i høyre frisone, og spøkelser og hindringer tilfeldig utenfor frisonene.

Svakheter som kan rettes i b). Spøkelse mangler egenskaper for fart og retning (for eksempel dx og dy), selv om spøkelset beveger seg med konstant fart på skrå. sjekkKollisjon() kunne ligget i SpillObjekt, siden kollisjonstesten er den samme for alle objekter. Sau har både blirBåret og Menneske.bærerSau, så den samme informasjonen lagres to steder. Modellen har heller ingen klasse eller metode som styrer selve spillet (spill-løkke, tastetrykk, poengvisning og avslutning).