Brodtkorb : DATS 2300202001

Om kurset

Hei alle sammen! Her kommer første virtuelle forelesning i år. Siden det blir hel-digital undervisning legger jeg opp til å ha mye videoer på fokuserte emner, og jeg kommer til å spørre dere om tilbakemelding på hva dere liker best av måten ting presenteres på for å forbedre undervisningen.

I dag kommer det fire forelesnings-videoer: to om kurset og hvorfor algoritmer og datastrukturer er viktig, og to om faget selv. Disse omhandler et eksempel på en algoritme - finn største tall, og hvordan vi kan analysere effektiviteten til denne algoritmen.

Gå gjennom videoene, og start så å jobbe med ukeoppgavene. I neste opplasting kommer videoer hvor jeg går gjennom enkelte utvalgte ukeoppgaver (bla. oppsett av github mm.)

Om undervisning, eksamen, obliger, etc.

Om meg og hvorfor algoritmer og datastrukturer er viktig.

Hva er en algoritme? Finn største tall

I denne videoen går jeg gjennom hva en algoritme er, og et eksempel på en algoritme - hvordan vi finner største tall i et array.

Relevant pensum:

Kapittel 1.1

Hvor effektiv er en algoritme? Tellende operasjoner mm.

I denne videoen går jeg gjennom hvordan vi kan snakke om effektivitet til en algoritme. Dette er en introduksjon til temaet, og vi teller antall operasjoner for en gitt array-størrelse (7 tall), og for et array med n tall. Dette gir da en pekepinn på hvor effektiv en algoritme er.

Relevant pensum:

Kapittel 1.1

Permutasjoner, det harmoniske tallet Hn, og algoritmeanalyse av finn maksimum

Relevant pensum:

Antallet tall som er større enn det største foran
Det harmoniske tallet Hn
Resten av Kapittel 1.1

Hybrid forelesning på tirsdag med noen barnesykdommer med teknikken - som både påvirket kvalitet av opptak og foreleser. Jeg er veldig lei meg for dårlig kvalitet på forelesningen her i første halvdel. Kildekoden vi snakker om er følgende:

int max(int[] a) {
    int max_value = a[0];
    for (int i=1; ilength; ++i) {
        if (a[i] > max_value) {
            max_value = a[i];
        }
    }
    return max_value;
}

og permutasjonene vi snakker om er som følger:

To tall:
[1, 2] [2, 1]

Tre tall:
[1, 2, 3] [1, 3, 2] [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]

Fire tall:
[1, 2, 3, 4] [1, 2, 4, 3] [1, 3, 2, 4] [1, 3, 4, 2] [1, 4, 2, 3] [1, 4, 3, 2]
[2, 1, 3, 4] [2, 1, 4, 3] [2, 3, 1, 4] [2, 3, 4, 1] [2, 4, 1, 3] [2, 4, 3, 1]
[3, 1, 2, 4] [3, 1, 4, 2] [3, 2, 1, 4] [3, 2, 4, 1] [3, 4, 1, 2] [3, 4, 2, 1]
[4, 1, 2, 3] [4, 1, 3, 2] [4, 2, 1, 3] [4, 2, 3, 1] [4, 3, 1, 2] [4, 3, 2, 1]

Det vi forsøker å finne ut av er hva X er i forrige video. Grunnen til at vi vil vite det er for å vite om denne if-setningen er viktig for ytelsen eller ikke. Som vi ser fra bare fire tall, så har vi 24 forskjellig muligheter å skrive de fire tallene i forskjellig rekkefølge, og for 5 tall er det 120! Generelt er det n! (n fakultet) for n tall, og se her hvor stort 52! er... Det er umulig å finne ut av hvor mange ganger vi går inn i if-setningen for et array med så få som 52 tall ved å prøve alle kombinasjoner (permutasjoner), og derfor må vi i steden bruke litt matematikk for å se om dette er en dyr eller billig operasjon. Til slutt i videoen så går vi såvidt igjennom hvordan vi kan bruke find_max(int[] a) til å sortere, og hvordan sortering da blir en kvadratisk algoritme - mens å finne maksimum er en lineær algoritme.

Permutasjoner - opptak hjemmefra

I denne videoen så går vi gjennom permutasjoner av tall, og hvordan vi kommer frem til det harmoniske tallet Hn. I et array med n tall vil antall tall som er større enn alle tall foran være Hn-1 i gjennomsnitt.