Idéer för aktivt lärande
Algoritmisk effektivitet och komplexitet handlar om att förstå att alla lösningar inte är lika bra. I Datalogi 1 introduceras eleverna till hur man mäter prestanda i termer av tid och minne, särskilt när datamängden växer. Genom att använda Ordo-notation (Big O) får de ett vetenskapligt språk för att beskriva och jämföra olika algoritmers skalbarhet.
Aktivitet 01
Eleverna utför en manuell uppgift (t.ex. hitta ett namn i en lista) med 10, 20 och 40 element. De klockar tiden, ritar grafer och diskuterar om tidsåtgången ökar linjärt eller snabbare.
Vad menas med tidskomplexitet?
Aktivitet 02
Eleverna får olika scenarier (t.ex. att städa ett rum vs. att para ihop alla strumpor i en tvättkorg). De diskuterar i par vilken Big O-kategori uppgiften tillhör och motiverar sitt svar för klassen.
Hur påverkar datamängdens storlek algoritmens körtid?
Aktivitet 03
Grafer som visar O(1), O(n), O(n log n) och O(n^2) hängs upp. Eleverna ska matcha olika algoritmer (t.ex. binärsökning, bubble sort) till rätt graf och förklara varför.
Vad innebär O(n) och O(n^2)?
Några anteckningar om att undervisa detta avsnitt
Se upp för dessa missuppfattningar
Att en snabbare dator gör en ineffektiv algoritm bra.
Elever tror ofta att hårdvara löser allt. Genom att visa hur en O(n^2)-algoritm snabbt blir oanvändbar även på en superdator när datamängden är stor, förstår de vikten av algoritmisk design.
Att Big O mäter exakta sekunder.
Många tror att Ordo-notation ger en tid i millisekunder. Genom diskussion klargörs att det handlar om hur tillväxten ser ut i förhållande till indata, inte den faktiska tiden på en specifik maskin.
Metoder som används i denna översikt
Introduktion till algoritmiskt tänkande
Att bryta ner komplexa problem i mindre, hanterbara steg. Eleverna lär sig formulera algoritmer med pseudokod och flödesscheman.
8 methodologies
Sök- och sorteringsalgoritmer
En djupdykning i klassiska algoritmer som linjär sökning, binärsökning, bubble sort och insertion sort. Vi jämför deras tillvägagångssätt.
8 methodologies