TDT4109 Informasjonsteknologi, grunnkurs

Denne siden baserer seg på mine tanker og tolkninger av emnet ITGK. Informasjonen presentert på denne siden baserer seg på forelesninger på NTNU, temasider fra NTNU, samtaler med medstudenter og mange youtube videoer. 

Emnebeskrivelse

Personlig synes jeg at ITGK var det mest interessante og kreative emnet første semester (iallfall etter min mening). Dette faget gir en grundig innføring i programmeringsspråket Python. Hvis du velger fagkoden TDT4109, vil programmering utgjøre 2/3 av faget, mens teori vil utgjøre 1/3.

For å bli dyktig i ITGK må du sette av mange timer til programmering. Python er et utmerket første programmeringsspråk. Det er lett å lese og tar deg gjennom grunnleggende operasjoner som også er nyttige i andre programmeringsspråk.

Teoridelen i ITGK dekker grunnleggende informasjon om datamaskinens oppbygning, litt historie og binære operasjoner.

Mitt beste råd for ITGK er å bruke Google. Det er sannsynligvis noen som har støtt på de samme problemene som deg tidligere, så med noen tastetrykk kan du finne en mulig løsning.

På denne siden har jeg laget noen oppsummeringer av de ulike temaene og delt mine besvarelser på øvingene vi har gjennomført. Det kan forekomme noen feil her og der, så ikke nøl med å dobbeltsjekke informasjonen.

Basics

Et språk forteller hva datamaskinen skal gjøre. Python er programmeringsspråket som brukes i dette emnet. Når vi skriver kode, skrive vi egentlig instrukser til datamaskinen, nesten som en oppskrift den skal følge. 

Innebygde funksjoner

På eksamen har du tilgang til diverse innebygde funksjoner og metoder. Disse trenger du ikke lære deg utenatt, men det er fint å ha sett litt på de før eksamen starter. 

Gå inn på denne linken for å finne ulike funksjoner og metoder. 

Du vil også ha tilgang til denne nettsiden under eksamen, det hadde i alle fall vi i 2022. Denne kan virke litt uoversiktlig, så jeg vil anbefale å orientere seg litt på siden før eksamen. 

Temaer

Variabler, datatyper, operasjoner, input/output
Variabler, datatyper, operasjoner, input/output
Variabler 

Variabler representerer verdier som er lagret i datamaskinens minne. For eksempel kan variabelen “navn” ha verdien “Emilie” og vi skriver:

Datatyper

Verdiene som blir lagret i variablene kan være ulike typer data. I eksempelet over er verdien “Emilie” av type tekst, som vi i Python kaller en streng (eng: string). De ulike typene vi har er:

Alt bak # er kommentarer i python.

Operasjoner

Med disse variablene og verdiene kan man utføre ulike operasjoner, som for eksempel pluss og minus. 

 

Input og output

Mange programmer krever interaksjon med brukeren som benytter seg av programmet, derfor må vi ha en input-funksjon. Input er informasjon som kommer fra en brukes oftest gjennom tastaturet. Programmet gjør noen instrukser på denne inputen, før den kommer ut med en output

Eksempel: 

Betingelser og logiske utrykk (if, else)
Betingelser og logiske uttrykk (if / else)

Når man skriver i Python gir vi egentlig bare konkrete instrukser som datamaskinen skal følge. If-setninger er et eksempel på dette som brukes masse. Slik fungerer den med et eksempel:

 

Vålerenga har spilt en fotballkamp mot Lillestrøm.

Hvis Vålerenga scorer flere mål enn Lillestrøm, vinner Vålerenga.

Eller hvis Lillestrøm scorer flere mål enn Vålerenga, vinner Lillestrøm. 

Ellers er det uavgjort. 

Oversatt til kode blir det:

Løkker/loops (for/while)
Løkker/loops (for/while)

Løkker er datamaskinens måte å utføre gjentatte handlinger i raskt tempo. De brukes når du må gjøre noe flere ganger, for eksempel når du skal håndtere oppgaver som:

  • Et firma må betale lønn til sine ansatte hver måned.
  • Et digitalt eksamenssystem må vise og samle inn svar fra studenter som tar eksamen.
  • Sykehusutstyr må overvåke pasienters hjerterytme sekund for sekund og utløse alarmer ved unormaliteter.

For-løkker er ideelle når du allerede kjenner antallet repetisjoner. For eksempel vet et firma hvor mange ansatte det har og bruker derfor en for-løkke til å beregne og utbetale lønn til hver av dem hver måned. Eksempel er nedenfor. 

While-løkker er derimot nyttige når antall repetisjoner ikke er kjent på forhånd, og løkken skal avsluttes når visse kriterier er oppfylt. For eksempel, når du løser matematiske ligninger numerisk og må nå en bestemt presisjon, bruker du en while-løkke. Du vet ikke på forhånd hvor mange iterasjoner som kreves for å oppnå nøyaktigheten, derfor er while-løkken mer hensiktsmessig i denne situasjonen. Eksempel er nedenfor.

range() - funksjonen

range()-funksjonen brukes ofte i for-løkker når du vil gjøre noe x antall ganger.

for i in range (til og uten) (default start er 0)

for i in range (fra og med, til og uten)

for i in range (fra og med, til og uten, steg)

Eksempel for-løkke
Eksempel while-løkke
Funksjoner
Funksjoner

For å unngå gjentakelse av identisk kode flere steder i et program, kan vi definere denne koden én gang og deretter kalle den ved navn når det trengs. Dette gjør programmet mer organisert og reduserer repetisjonen av kode.

Imidlertid har funksjoner med ingen parametere begrenset anvendelighet. En funksjon uten parametere utfører den samme oppgaven hver gang den blir kalt. Ofte trenger vi å utføre en lignende oppgave, men med varierende verdier. For eksempel må en kvadratrotfunksjon kunne beregne roten av ulike tall - en funksjon som bare kan håndtere roten av 2, har begrenset nytte. 

For funksjoner som skal utføre beregninger og returnere et resultat (og mange funksjoner er designet for dette formålet), bruker vi en "returverdi." Når du skriver en funksjon, bruker du returverdien hvis du ønsker å forlate funksjonen og print-verdien hvis du ønsker å fortsette å utføre handlinger i funksjonen.

Lister, tupler og mer om strenger
Lister og tupler og mer om strenger

Lister er en mye brukt datastruktur for å tilordne én variabel en rekke med verdier. Lister kan blant annet inneholde tall, strenger eller andre lister.

For å opprette en tom liste i Python skriver vi []. Vilkårlig lange lister kan lages ved å skrive [a, b, c, … ], der a, b, og c er elementer i listen.

len()-funksjonen gir oss lengden av lista, altså 3 i dette tilfellet. 
“Mia” har indeks 0, “Aksel” har indeks 1 og “Morten har indeks 2.
Man kan hente ut elementene i en liste dersom man har indeksen til elementet ved f.eks:
print(navn[0])
Dette vil skrive ut Mia, fordi “Mia” har indeks 0.

På samme måte som lister, har også strenger indeks. 

streng: P Y T H O N 
indeks: 0 1 2 3 4 5
len("python") = 6
Dictionaries og sets
Dictionaries og sets

En dictionary er et objekt som lagrer en samling av data, og kan minne mye om en liste. Det som skiller en dictionary fra en liste er at hvert element i en dictionary består av to deler: En nøkkel (key) og en verdi (value). En nøkkel peker til en verdi, og man bruker nøkkelen for å hente ut verdien.

  • key: Nøklene kan være flyttall, heltall strenger eller tupler. Nøklene må være unike.
  • values: Innholdet som nøkkelen peker til. Dette kan være lister, strenger, heltall, osv.

En dictionary er bygget opp på denne måten: 

my_dict = {key: value, key_2: value_2, key_3: value_3}

Ulike operasjoner: 

Et set er nesten akkurat det samme som en liste. Forskjellen mellom et set og en liste er at rekkefølgen på elementene i et set spiller ingen rolle. Et element forekommer kun en gang i et set, mens i en liste kan samme element forekomme flere ganger. Sets har også krøllete parenteser {} istedenfor klamme-parenteser []. 

my_set = {2,4,5,6}
Filer og unntak
Filer og unntak

Teori

Datamaskinens oppbygging

tl;dr:

En datamaskin består av tre hoveddeler: en sentralenhet (CPU), input-enheter og output-enheter. CPU-en, som står for Central Processing Unit, fungerer som datamaskinens sentrale hjerne. Alle programmer kjører på CPU-en, og den består av flere mindre komponenter, inkludert ALU (Arithmetic Logic Unit), CU (Control Unit) og minne.

Central Processor Unit (CPU) (mikroprosessor)

tl;dr: CPU-en er datamaskinens hjerne. Dens hovedoppgave er å kjøre programmer (instrukser).

CPU-en er den utførende enheten i datamaskinen. Den leser instrukser og utfører dem, én etter én. Adressen til neste instruks ligger hos programtelleren. CPU inneholder:

  • ALU
    • Beregninger
    • Mellomlagring
    • Registre (akkumulator, pc)
  • Kontrollenhet (control unit)
    • Kontroll av utførelse
  • Hukommelse (memory)
    • Lagring av resultater
  • Består av millioner av transistorer

CPU-en frakter data og sørger for kommunikasjon mellom enheter.

Arithmetic Logic Unit (ALU)

tl;dr: Utfører de matematiske operasjonene i datamaskinen.

  • En del av prosessoren
  • Består av aritmetisk enhet
    • utføre beregninger
    • Addisjon, Subtraksjon, osv.
    • Inkrement (øke med en), osv.
  • Består av logisk enhet
    • utføre logiske operasjoner: AND, OR, NOT etc.
    • Enkle tester som om tall er negative
  • Utfører matematiske operasjoner og boolsk logikk i prosessoren
  • ALU jobber i Instruction Execute (EX) steget i fetch/execute
  •  
Control Unit (CU)

tl;dr: Enheten som har kontroll på instruksene som utføres og hva som er neste instruks. 

  • Håndterer prosessen av kjøring av instrukser i CPU (dirigenten)
    • Henter inn instrukser fra RAM til registre
    • Dekoder instrukser og data
    • Igangsetter ALU
  • Instruction register
    • Liste over instrukser
  • Program counter (PC)
    • Peker på adressen til neste instruks

 

Fetch/execute / kjøring av programmer

tl;dr: Kjøring av programmer gjøres ved at CPU utfører instruksjoner; fetch, decode og execute.

Instruksjoner utføres i tre faser:

Fetch: Hent instruksjon

Decode: Avgjør hva som skal gjøres 

Execute: Utfør instruksjon

  • Instruction fetch (IF)
  • Instruction decode (ID)
  • Data fetch (DF)
  • Instruction execute (EX)
  • Result return (RR)

Pipelining: de ulike stegne i fetch/execute kjøres i parallell, mer effektiv bruk av CPU slik at flere deler av CPU kan brukes samtidig.

Transistorer

En transistor er en slags bryter i datamaskinen som enten kan være på eller av.

  • Kan enten lede strøm eller ikke (1 og 0)
  • Små, krever lite strøm og er pålitelige
  • Lages som regel av silisium (Engelsk: silicon; derav silicon valley)
  • Integrerte kretser inneholder millioner av disse
Fotolitografi

En metode for å “printe” bindinger og tilkoblinger på et kretskort.

Minne

tl;dr: Datamaskinen har i hovedsak to ulike typer minne; persistent og ikke-persistent. Primærminne (RAM) overlever ikke uten strøm (ikke-persistent), dette er datamaskinens arbeidsminne. Sekundærminne overlever selvom maskinen ikke får strøm (persistent).

Registre

I Control Processor Unit (CPU) finnes små og raskt minne på chip som kalles registre.

  • CPU har registre for
    • Instruksjonsadresse, lagrer adresse i RAM til neste instruks
    • Instruksjon, lagrer nåværende instruks
    • Minne, mellomlagre som ofte kalles register A, B, C osv.
  • små, raske og dyre per byte
Cache
  • RAM er en flaskehals, CPU må ofte vente på RAM
  • Cache er et raskere minne på CPU-chip, mindre enn RAM
  • Gir CPU raskere tilgang på data
  • Første stopp hvor CPU sjekekr for data
  • tregere enn registre, men raskere enn RAM
Random Access Memory (RAM)/primærminne
  • Arbeidsminne
  • Ikke persistent- altså trenger strøm for å huske
  • Kan hente ut data fra alle steder i minne til enhver tid (random)
  • Bruker adresse for å spesifisere hvor i minne man skal lese/skrive
  • Ikke en del av prosessoren (CPU)
  • “Random” betyr at man kan hente ut plasseringer i minne i en vilkårlig rekkefølge (i motsetning til en tradisjonell harddisk som må lete seg frem sekvensielt)
  • tregere enn registre, men billigere per størrelse
Persistent minne/sekundærminne
  • Minne som overlever uten strøm
  • Større kapasitet, men tregere
  • Eksempler: harddisk, SSD, minnepinne, CD/DVD
  • Tregere enn RAM, billigere per størrelse, persistent
Harddisk (HDD)

Består av en magnetisk plate hvor en nål må søke seg frem sekvensielt for å finne riktig minneplassering. Kan sammenlignes til en viss grad med en CD/LP-spiller. Lagrer data ved å “flippe” magnetiske bits.

Solid State Drive (SSD)

Mer moderne type harddisk bestående av flash-minne, uten noen bevegelige deler. Kan også lese data uten å søke seg frem, og er på den måten veldig lik RAM.

Binær representasjon

tl;dr: Binær representasjon er en måte å representere noe med to tilstander (0 og 1). Vi bruker denne metoden fordi det minimaliserer signalproblemer og det er logisk. Alt som skjer i en datamaskin kan spores ned til 0-ere og 1-ere. En verdi av 0 eller 1 kalles en bit. Den vanligste kombinasjonen er 8 bits som kalles en byte. 

Generelt

Binær: "av to tilstander"

Boolsk logikk: and, or, not, xor

Bit: en verdi av 0 eller 1

Byte: 8 bits, kan representere 256 ulike verdier. Minne oppgis antall bytes Kilobytes, megabytes, gigabytes, terabytes

Bokstaver

tl;dr: Hver bokstav blir representert som et spesifikt tall som igjen blir representert binært (0 og 1ere). For eksempel A = 65 = 0100 0001

ASCII:

  • ‘American Code for Information Interchange’.
  • En amerikansk standard for representasjon av bokstaver
  • Et system for å konvertere binærkode til bokstaver og tegn
  • Bestod i utgangspunktet 7 bits, så det var kun mulig å representere 128 forskjellige tegn
  • Ble en gang i tiden utvidet til 8 bits, som ble gitt navnet Extended ASCII, for å kunne representere flere europeiske tegn (i dag heter denne varianten ISO-8859-1)

UNICODE:

  • «to rule them all»
  • Støtte for alle språk
  • 16-bit
  • UTF-8 brukes for å representere bokstaver, tall og tegn internasjonalt over internett i dag. Den har variabel lengde, som vil si at antall bits som brukes varierer fra tegn til tegn
  • UTF-8 lar oss representere en hel rekke mulige språk og tegn på en og samme side, noen skriftspråk, som f.eks. kryllisk, vil kreve flere bits for å representeres (uten å gjøre modifikasjoner eller bruke egne tegnsett)
  • UTF-8 er en binær representasjonsform for tegn i Unicode-tegnsett
Lyd

tl;dr: Man kan konvertere elektroniske signaler (lydbølger) til binær data med en Analog to Digital Converter (ADC). Motsatt kan man gå fra binær lyd-data til elektroniske signaler med en Digital to Analog Converter (DAC).

 

Sampling: (ADC)

  • Samplingsfrekvens
    • Hvor hyppig man leser av verdien av lydsignal per sekund (Hz)
    • Hvor hyppig lydsignaler svinger avgjør tone (høyde)
    • Nyquist regelen sier at man må minst ha dobbel samplingsfrekvens av høyeste lydfrekvens
    • CD-plate: 44.1KHz, 16-bit
  • Bitdybde (dit depth)
    • Avgjør oppløsning på volumnivå på lyden
    • Lav bitdybde: fanger ikke små variasjoner av volumendringer
  • Overgang fra elektrisk lydsignal til binær
    • ADC tar punkt-prøver i et elektrisk signal mange ganger i sekundet og sjekker spenningsnivå, som blir representert av et positivt eller negativt tall
    • Dette tallet sier noe om høyde på volum

Digitalisering av lyd

  • Kvalitet avhenger av samplingsfrekvens og bitdybde
  • Mennesker kan oppfatte 20KHz
  • Kontinuerlig lydkonverteres til et diskret format for å kunne lagres i en datamaskin. Diskretisering av lyd foregår ved at man sampler lydbølgen ved en viss frekvens, og lagrer verdien det har i hvert enkelt punkt.
  • Når lyden skal spilles av igjen så bruker man disse punktene og konverterer det til tilbake til kontinuerlig lyd.
  • Bølgetopper og -bunner i lyd eller andre signaler kan sees på som 1 og 0. 
  • Dette er en utrolig liten bit depth. Ved å øke antall mulige verdier (f.eks. 65,536) så kan vi fange opp større nyanser av forskjellige mulige verdier i bølgesignalene (som ellers ville blitt representert likt)
  • Ved å øke bit depth og hvor ofte man måler verdier, sample size, fra bare bølgetopp og -bunn til f.eks. 44,100 ganger i sekundet, så får man mye tydeligere og “bedre musikk”.

Eksempel på utregning av antall bytes 10 sek CD-kvalitet tar:

  • Tar 44100 sampe per sekund
  • Hvert sample er 16 bits (2bytes)
  • Opptaket er 10 sek
  • 10*44100*2 = 0.882MB
Bilder og video

tl;dr: Digitale bilder består av piksler; punkt av lys i forskjellig farge. Disse punktene har tre verdier som representerer i hvilken grad punktet har fargene rød, grønn, blå (RGB).

En video er en mengde bilder som vises raskt etter hverandre. Et slikt bilde kalles "frame" og hastigheten på videoen måles i "frames per second" (FPS).

 

RGB: Red, green, blue

Komprimering: En måte å spare plass ved å bruke smarte algoritmer til å endre innholdet i multimedia slik at det tar mindre plass

Piksel: Et punkt på dataskjermen eller i et bilde. Hvert punkt (piksel) i et bilde består vanligvis av tre farger (RGB-verdi)

Eksempel med bildelagring

  • 8 x 10 tommer 300 piksler per tomme
  • det er 80 tommer^2, hver trenger 300x300 = 90000 piksler
  • Oppløsning:
    • Dimensjoner som måler antall piksler på en skjerm
    • Måles i antall piksler bredde x antall piksler høyde
    • Typiske oppløsninger
      • SD: 640*480
      • HD: 1920*1080
      • UHD/4K: 3840*2160
    • Tetthet (density):
      • Antall piksler per fysisk areal
      • Måles i Pixel Per Inch (PPI)
      • Store skjermer har ofte lav PPI
      • Dyre smarttelefoner har høy PPI
    • Lagring av ikke-komprimert fargebilde på datamaskin
      • Alle piksler blir lagret som 1ere og 0 ere, med en verdi for rød, grønn og blå
      • Høy verdi på farge representerer lyse farger
      • Verdier per farge for 24 bits-bilde er fra 0 til 255
      • Bruker ofte 24-bit, ettersom det er 1 byte per farge
      • Hvor stor lagringsplass tar et 640x480 bilde? Hver pixel tar 3 bytes
        • 640*480*2=921600 = 0.9MB
      • Antall fargealternativer for hver pixel:
        • 1 bit = 2 alternativ
        • 24 bit : 256*256*256=16.7millioner
      • Filstørrelse er bredde*høyde*fargedybde
    • Gjøre digitale bilder lysere:
      • Legge til samme verdi for RGB for alle piksler
    • Trekke fra verdi for å gjøre det mørkere
    • 0 er min-verdi 255 er maksverdi
Komprimering

tl;dr: Å skulle representere bilder og lyd 100% tro til virkeligheten ville krevd enorme (uendelige) mengder lagring. Komprimering reduserer antall bits vi trenger for å representere data.

 

Datakomprimering:

  • Kode data til å bruke færre bit enn original representasjon
  • Gjøre det raskere å overføre bilder og redusere lagringsplass

Lossless:

Tapsløs (lossless) komprimering bruker smarte teknikker for å gjøre informasjon mer effektivt lagret, uten å endre dataen på en irreversibel måte. Kan 100% gjenskape opprinnelig data. Brukes i PNG og ZIP.

  • Run-length-koding:
    • Reduserer repeterende data
    • Tapsløs
    • Vil redusere antall bytes ved mye repeterende data

Lossy:

“Lossy” komprimering tar utgangspunkt i det som er “godt” nok og gjør noen. Fjerner unødvendig eller mindre viktig informasjon som er vanskelig for mennesker å oppdage. Kan ikke 100% gjenskape original data.

  • Lyd
    • Perceptual coding
    • Koder ulike frekvensbånd med ulik presisjon
    • Utnytter at mennesker oppfatter ulike frekvensbånd med ulik nøyaktighet
  • Bilde (JPEG)
    • Deler opp bilder i blokker av 8x8 piksler
    • Utnytter at mennesker har lav sensitivitet til fargenyanser i motsetning til høy sensitivitet til lysstyrke
  • Video 
    • Fokuserer på endringer i bildet istedenfor representasjon av hvert bilde
    • Brukes lite data på steder i bildet som ikke endres fra bilde til bilde
    • Reduserer data basert på likheter i sekvensen av bilder

Latency: tiden det tar for informasjon å bli laget til den blir levert.

Bandwidth: Hvor mye data som overføres per tidsenhet (bits/sek)

Sikkerhet
McCumbers Cube

Beskriver problemstillinger rundt cybersikkerhet. 

Sikkerhetsmål:

  • Konfidensialitet
  • Integritet
  • Tilgjengelighet

Datatilstander:

  • Storage: data er lagret
  • Processing: data kvernes I en prosess
  • Transmission: data overføres på én eller annen måte

Mottiltak:

  • Policy: retningslinjer som sier noe om hva man skal og ikke skal gjøre
  • Education: kultur, det du gjør når ingen andre ser på
  • Technology: brannmuren, og de andre tekniske løsningene
Sårbarheter

Ulike typer sårbarheter:

  • Tekniske
  • Fysiske
  • Prosedyre-messige
  • Organisatoriske
  • Menneskelige

CVSS: common vulnerability scoring system

Vanlige feil i hardware:

  • Designfeil
  • RAM minnekomponenter er monter for nærme hverandre
  • Stadige endringer påvirker nabokomponenter
  • Rowhammer henter data fra nærliggende minneceller, selv om de var beskyttet
  • Intel pentum flyttalldivisjonsfeil
  • Alle nye chipper har feil, debugging er en kontinuerlig prosess
  • Utnyttelse av hardwarefeil skjer gjerne i rettede angrep

Vanlige feil i software:

  • Feil i operativsystemet eller programkoden
  • Fiks ved oppdatere jevnlig patche
  • Følge med på komponenter du bruker sikre at du bruker siste versjon
  • Buffer overflow
Algoritmer
Kjøretid

Fra raskest til saktest:

O(1)

O(log n)

O(n)

O(n log n)

O(n²)

O(n³)

O(kˆn)

O(n!)

Bubble sort

Bubble sort er en enkel sorteringsalgoritme som fungerer ved å sammenligne hvert element i en liste med det neste elementet og bytte plass på dem hvis de er i feil rekkefølge. Algoritmen gjentar denne prosessen gjentatte ganger til hele listen er sortert i stigende rekkefølge.

Her er en enkel forklaring på bubble sort:

1. Start med en liste med ubestemt rekkefølge av elementer som skal sorteres.

2. Sammenlign det første elementet med det neste elementet i listen. Hvis det første elementet er større enn det neste elementet (altså de er i feil rekkefølge), bytter du plass på dem.

3. Gå videre til det neste paret av elementer og sammenlign dem. Fortsett å sammenligne og bytte plass på elementer til du når slutten av listen.

4. Når du har gått gjennom hele listen en gang, vil det største elementet ha "boblet" opp til slutten av listen (derav navnet "bubble sort").

5. Gjenta prosessen, men denne gangen går du ikke helt til slutten av listen, fordi det største elementet allerede er på riktig plass. Fortsett å gjøre sammenligninger og bytte plass på elementer til du har sortert hele listen.

6. Fortsett å gjenta trinn 4 og 5 til hele listen er sortert i stigende rekkefølge.

Bubble sort er en enkel algoritme, men den kan være ineffektiv for store lister, da den har en tidligere tidskompleksitet på O(n^2), der n er antall elementer i listen. Det finnes mer effektive sorteringsalgoritmer for store datamengder, som for eksempel quicksort og mergesort.

Insertion sort

Insertion sort er en enkel sorteringsalgoritme som fungerer ved å dele listen opp i en sortert og en usortert del. Den tar ett element av gangen fra usortert del og setter det inn på riktig plass i den sorterte delen, til hele listen er sortert.

Her er en kort forklaring på insertion sort:

1. Start med en liste med ubestemt rekkefølge av elementer som skal sorteres.

2. Begynn med å anse det første elementet som den sorterte delen av listen. Resten av elementene betraktes som den usorterte delen.

3. Ta ett element fra den usorterte delen av listen, og sammenlign det med elementene i den sorterte delen.

4. Sett inn det valgte elementet på riktig plass i den sorterte delen, slik at den sorterte delen forblir i riktig rekkefølge.

5. Gjenta trinn 3 og 4 for hvert element i den usorterte delen, til hele listen er sortert i stigende rekkefølge.

Insertion sort har også en tidligere tidskompleksitet på O(n^2) for gjennomsnitts- og verste tilfelle, men den kan være raskere enn bubble sort for små datamengder eller når listen allerede er delvis sortert.

Andre viktige begreper

Hardware: utviklet med elektroniske komponenter og andre materialer.

Software: utviklet ved programmering. Et sett med instrukser som muliggjør en applikasjon på en datamaskin.

ENIAC: første generelle programmerbare elektroniske datamaskin, kunne utføre over 5000 operasjoner per sekund. Brukte vakumrør.

Moores law: antallet transistorer i integrerte kretser dobles hvert andre år. 

Klokka i datamaskinen: synkroniserer alle operasjoner i en datamaskin, måles i MHz, GHz

PandA: logikken er enten sann eller usann. Grunnlaget for digital representasjon.

Kompilering: Konverterer kode skrevet i et høynivå-språk (f.eks. Python) til kode i et lavere nivå (f.eks. Assembly eller maskinkode) slik at dette (enklere) kan leses av datamaskinen.

Assembly: Et paraplybegrep for flere forskjellige lavnivå-programmeringsspråk.

Metadata: Informasjon om informasjon