I efteråret 2022 har jeg fulgt og bestået kursus i Algoritmer og datastrukturer ved AU. Hvad har jeg lært?
Algoritmer er et forskningsfelt inden for datalogien, hvor man optimerer for tids- og pladsforbrug. En effektiv algoritme er mere besparende end en hurtig computer.
Nogle af de effektive algoritmer kører rekursivt dvs. kalder sig selv med et nyt argument. Rekursive algoritmer benytter en kalde-stak, hvor det sidste, som er lagt på stakken, også afvikles først (LIFO=last in, first out). Kommandoer som står før det rekursive kald, afvikles mens kaldestakken fyldes. Kommandoer som står efter det rekursive kald, afvikles mens kaldestakken tømmes.
Alternativt til en stak, bruges nogle gange en kø, hvor de sidste som er lagt i køen også afvikles sidst (FIFO = first in, first out). Køen kan udvides til en prioritets-kø, hver elementerne hele tiden skal sorteres efter værdi, så elementet med mindst værdi (minPQ) ligger først i køen.
De fleste event-drevne systemer som f.eks. Micro:bit og MakeCode Arcade bruger en prioritetskø til at afvikle funktioner. Når systemet registrerer en ny event, bliver den tilføjet bagest i køen, og tidligere tilføjede funktioner skal være færdige, før en ny kan afvikles. Der er undtagelser: Forever-funktionen får altid laveste prioritet og den indbyggede Pause-funktion sætter afviklingen af en funktion på pause og lægger den i en stak til pausen er slut. Dette program kan demonstrere det.
Der er mange sorterings-algoritmer, som hver har deres fordele og ulemper (fx selection sort, insertion sort, mergesort, quicksort, heapsort).
Der er mange søge-algoritmer (fx binær søgning, binære søgetræer). Binære søgetræer skal helst være balancerede (samme dybde til alle blade dvs. fra top til bund), hvilket kan opnås med rød-sorte binære søgetræer.
Grafer er samlinger af knuder forbundet af kanter. Om to knuder er forbundet, kan afgøres efter dybde-først-søgning. Korteste vej (sti) mellem to knuder kan kortlægges i en vægtet orienteret graf med Dijkstras algoritme eller i en uorienteret graf med bredde-først søgning (korteste antal kanter).
Den model af et biologisk neuralt netværk, som jeg har skrevet i JavaScript, kunne gemmes som en rettet vægtet graf, dvs. knuden er cellens soma, og linket (kanten) til en anden nervecelle er aksonet, som kan sende signal i een retning (deraf rettet graf). Aksonet kan være vægtet med en værdi, som repræsenterer synapsens følsomhed.
En rettet vægtet graf er ofte gemt i en datastruktur, hvor knuderne gemt i et array (adjacency list), hvor hvert element i arrayet indeholder en hægtet liste (linked list) af naboknuder, som knuden har en kant hen til jvf. kantens retning. Naboknuderne er gemt som objekter med værdier fx type, vægt m.v., og med en pointer til næste naboknude. Dvs. for index 2, kan man iterere over knude 2’s naboknuder ved at følge pointeren ned gennem den hægtede liste.
Et virkelig spændende kursus, og et helt nyt felt, som har åbnet sig på klem for mig, men nok ikke noget jeg kommer til at forfølge i større grad.