Informatik

Algoritmer er alle vegne. Der bliver talt om Facebooks algoritmer, hvordan Google optimerer deres søge-algoritmer osv. Ikke mindst sprogmodellernes indtog i vores hverdag, har skabt fornyet fokus på algoritmer. Men hvad er en algoritme og hvad har computere og algoritmer med hinanden at gøre?

Algoritmer

En algoritme kan defineres som en rækkefølge af entydige, ekserkverbare trin, der definerer en afsluttende proces.

Her skal vi lægge mærke til rækkefølge, dvs. en trin-for-trin-beskrivelse; entydige, dvs. de skal ikke kunne misforstås eller udføres på andre måder; ekserkverbare, dvs. at de skal kunne udføres indenfor den ramme, der er givet; og endelig afsluttet proces, hvilket vil sige, at der skal være defineret et endemål eller resultat.

En madopskrift og en strikkeopskrift er eksempler på almene algoritmer. De indeholder en tydeligt afgrænset rækkefølge på de skridt, der skal følges for at nå frem til den færdige ret eller tørklæde.

Eksempler på algoritmer

Lad os udføre et tankeeksperiment med to forskellige algoritmer.

Algoritme 1

Mål: I en bog på 560 sider skal I finde side 475.

Fremgangsmåde: slå op på første side, er det side 475, hvis ikke gå videre til næste side, osv. indtil sidetallet er 475.

Denne algoritme vil kræve 475 handlinger før den korrekte side er fundet. Det er ikke en effektiv algoritme.

Algoritme 2

Mål: I en bog på 560 sider skal I finde side 475.

Fremgangsmåde: Slå op på den midterste side (side 280) og se på sidetallet. Hvis det er lavere end 475, slå op på den midterste side af øvre halvdel (side 420) og se på sidetallet (ellers gør det modsatte). Hvis det er lavere end 475, slå op på den midterste side af den øvre halvdel (side 490) og se på sidetallet (ellers gør det modsatte). Hvis det er højere end 475, slå op på den midterste del af den nedre halvdel, du lige har rykket (side 455) og se på sidetallet (ellers gør det modsatte). Hvis det er lavere end 475, slå op på den midterste del af den øvre halvdel, du lige har rykket (ca. side 472) og se på sidetallet (ellers gør det modsatte). Hvis det er lavere end 475, slå op på den midterste del af den øvre halvdel, du lige har rykket (ca. side 480) og se på sidetallet (ellers gør det modsatte). Hvis det er højere end 475, slå op på den midterste del af den nedre halvdel (side 476) og se på sidetallet (ellers gør det modsatte). Hvis det er højere end 475, slå op på den midterste del af af den nedre halvdel (side 474) og se på sidetallet (ellers gør det modsatte). Hvis det er lavere end 475, slå op på den midterste del af den øvre halvdel (side 475) og se på sidetallet.

Denne algoritme vil finde den korrekte side med kun 9 handlinger. Den er altså betydelig mere effektiv end den forrige algoritme.

Øvelse 1

Udfør algoritmen med en bog på 1550 sider og find side 650. Tæl hvor mange opslag, I skal foretage jer for at finde den rigtige side ved at følge samme principper som ovenfor.

Antal forsøg	Sidetal
1.	1550 (halver sidetal)
2.	775 (gå til midterste halvdel af nedre halvdel…)
3.	388 (gå til midterste halvdel af øvre halvdel…)
4.	582 (gå til midterste halvdel af øvre halvdel
5.	…
6.	…
7.	…
8.	…
9.	…

Sorteringsalgoritmer

En af de mest grundlæggende algoritmetyper, som udføres på en computer er sorteringsalgoritmer. Der er mange forskellige slags, men en af de nemmeste er bubble sort-algoritmen.

Bubble sort

Det er en simpel sorteringsalgoritme, der fungerer ved fx at sammenligne tal i en liste med tallet ved siden af og bytte rundt på dem, hvis de er i forkert rækkefølge. Denne proces gentages indtil alle tallene i listen er i korrekt rækkefølge.

Øvelse 2 Bodygramming Bubble sort

I skal nu opleve en bubble sort-algoritme på egen krop. Inddel klassen i grupper af 8 elever. Hver elev har et nummer fra 0-9. Placer numrene i tilfældig rækkefølge og begynd:

Start fra venstre til højre. Sammenlign placering 1 med placering 2, byt om hvis placering 2 er mindre end placering 1. Sammenlign placering 2 med 3, byt om hvis placering 3 er mindre end placering 2. Gentag processen indtil, I når til placering 8. Nu er placering 8 det højeste tal i listen. Gentag processen fra placering 1 til 7, osv.

Pseudokode Bubble sort

Men denne lange beskrivelse kan skrives lidt nemmere ved at bruge det, vi kalder pseudokode. Pseudokode er en uformel måde at beskrive, hvordan en algoritme fungerer, uden at bruge den nøjagtige syntaks af et specifikt programmeringssprog. Pseudokode bruger almindeligt sprog blandet med simple programmeringsstrukturer for at beskrive trin-for-trin, hvordan en opgave skal udføres.

Her er bubble sort-algoritmen forklaret med pseudokode:

start

   for hver runde i listen:
   
      for hvert par af tal i listen:
      
         hvis det første tal er større end det næste:
            byt deres placering                      

   gentag indtil hele listen er sorteret

slut

Pythonkode Bubble sort

Den samme algoritme i programmeringssproget python ser lidt mere kompliceret ud. Teksten markeret med # er kommentarer, som forklarer hvad de enkelte dele af koden gør.

def bubble_sort(liste):
    n = len(liste)  # Længden af listen
    
    # Gå igennem listen flere gange
    for i in range(n):
        byttet = False  # Holder styr på, om der er blevet byttet i denne runde
        
        # Sammenlign hvert par af tal i listen
        for j in range(0, n - i - 1):
            
            # Hvis det første tal er større end det næste
            if liste[j] > liste[j + 1]:
                # Byt deres placering
                liste[j], liste[j + 1] = liste[j + 1], liste[j]
                byttet = True  # Marker at vi har byttet
                
        # Hvis ingen tal blev byttet, er listen allerede sorteret
        if not byttet:
            break

# Eksempel på brug af koden:
min_liste = [5, 3, 8, 4, 2]
print("Før sortering:", min_liste)
bubble_sort(min_liste)
print("Efter sortering:", min_liste)

Prøv selv koden af i en såkaldt online IDE (Integratet Development Enviroment), så I kan se hvordan den virker

Øvelse 3 Omvendt Bubble sort

Vend Bubble sort-algoritmen om, så den gør det modsatte. Altså sorterer listen, så de laveste tal er sidst.

• Modificer ovenstående pseudokode, så den passer til den nye funktion. Skriv resultatet ind i jeres logbog.
• Forsøg nu at modificere ovenstående pythonkode, så den passer til den nye funktion. I kan skrive og teste den i W3Schools Tryit Editor.

Insertion sort

Insertion Sort er en enkel sorteringsalgoritme, der er en lidt mere effektiv udgave af bubble sort-algoritmen. Den fungerer ved at opbygge den sorterede liste element for element. Den tager hvert element fra den usorterede del og indsætter det på den rette plads i den allerede sorterede del af listen.

Øvelse 4 Bodygramming Insertion sort

• Opsætning: Eleverne står i en uordnet række, og de spiller elementerne i en liste. Én elev er “sortereren”, som går fra venstre mod højre og placerer eleverne på deres rigtige position i en ny “sorteret” del af rækken.
• Fremgangsmåde: “Sortereren” starter med de første to elever og placerer dem i stigende rækkefølge, og derefter går den til næste elev og indsætter dem på den rigtige plads i forhold til de allerede sorterede elever.

Øvelse 5 Pseudokode Insertion sort

Skriv en pseudokode på en Insertion sort-algoritme. Se evt. ovenstående pseudokode for hjælp og inspiration.

Øvelse 6 pythonkode Insertion sort

Prøv at modificere denne pythonkode, så den sorterer i omvendt rækkefølge, altså størst til mindst. Test den af i W3Schools Tryit Editor

def insertion_sort(liste):
    for i in range(1, len(liste)):
        noegle = liste[i]
        j = i - 1
        while j >= 0 and liste[j] > noegle:
            liste[j + 1] = liste[j]
            j -= 1
        liste[j + 1] = noegle

# Eksempel
tal_liste = [9, 3, 5, 1, 8]
insertion_sort(tal_liste)
print("Sorteret liste:", tal_liste)

Øvelse 7 Insertion sort blokprogrammering

Gå ind på linket og prøv at køre sorteringsalgoritmen. Tryk på remix og forsøg at få koden til at sortere i omvendt rækkefølge.

https://scratch.mit.edu/projects/1221379040

Selection sort

Selection Sort er en enkel sorteringsalgoritme, der (i modsætning til Insertion Sort) hele tiden finder det mindste (eller største) element i den usorterede del af listen og flytter det frem til sin rigtige plads.
Algoritmen gentager denne proces for hvert element, indtil hele listen er sorteret.

Øvelse 8 Bodygramming Selection sort

Opsætning: Eleverne står i en uordnet række og repræsenterer elementerne i en liste (fx hver med et kort med et tal). Én elev er “sortereren” og bevæger sig fra venstre mod højre.

Fremgangsmåde: “Sortereren” kigger på hele rækken og finder den elev med det mindste tal. Denne elev bytter plads med eleven længst til venstre i rækken. Nu er den første position sorteret. “Sortereren” springer over den første position og gentager processen for de resterende elever (finder den med det næstmindste tal og flytter eleven op på position nummer to). Fortsæt, indtil alle står i stigende rækkefølge.

Øvelse 9 Pseudokode – Selection Sort

start
    for hver position i listen:
        antag at tallet er det mindste
        gå igennem resten af listen
            hvis et tal er mindre byt det med det aktuelle tal
    gentag indtil alle tal i listen er gennemgået 
        
slut

Øvelse 10 Pythonkode – Selection Sort

Her er en standard-implementation der sorterer i stigende rækkefølge.
Prøv at ændre den, så den sorterer i faldende rækkefølge (størst til mindst).

def selection_sort(liste):
    for i in range(len(liste)):
        mindste_index = i
        for j in range(i + 1, len(liste)):
            if liste[j] < liste[mindste_index]:
                mindste_index = j
        liste[i], liste[mindste_index] = liste[mindste_index], liste[i]

# Eksempel
tal_liste = [9, 3, 5, 1, 8]
selection_sort(tal_liste)
print("Sorteret liste:", tal_liste)

Tip: For at få den til at sortere størst til mindst, skal du ændre betingelsen i if-sætningen, så algoritmen vælger det største element i stedet for det mindste. Test koden i W3Schools Tryit Editor.