Reševanje problemov in računalniško mišljenje
Ta domena preverja miselne postopke reševanja problemov: razčlenjevanje, prepoznavanje vzorcev, abstrakcijo in načrtovanje algoritma ter njihovo preverjanje s testi. Naloge zahtevajo opis postopka in utemeljitev, ne le končnega rezultata.
Postopek
- Razčlenitev: problem razdeli na manjše, obvladljive podprobleme.
- Abstrakcija: odstrani nepomembne podrobnosti in ohrani le tiste, ki vplivajo na rešitev; model je poenostavljena predstavitev.
- Prepoznavanje vzorcev: podobni podproblemi vodijo do splošne rešitve, npr. ponavljajoča se zanka.
- Zapis: psevdokod ali diagram poteka; vsak korak mora biti določen.
Preverjanje
- Testni podatki: tipični, mejni (npr. 0, 1, največja vrednost) in neveljavni.
- Sledenje (trace table): zapiši vrednosti spremenljivk po vsaki iteraciji.
- Razlikuj napako v sintaksi, izvajanju in logiki; slednjo odkrije šele primerjava pričakovanega z dejanskim.
Rešen primer
Poišči par v seznamu [3, 7, 1, 9, 4], katerega vsota je 10. Preprost postopek primerja vse pare: 10 primerjav, čas O(n²). Bolje: za vsak x preveri, ali je 10 − x že v množici. Koraki: 3 → 7 ni v množici, dodaj 3; 7 → 3 je v množici, par (3,7) najden, 2 koraka. Sklep: zamenjava zunanje zanke z iskanjem v množici zmanjša O(n²) na pričakovanih O(n), a zahteva dodatni pomnilnik za množico.
Pasti
- testiranje le s tipičnimi podatki;
- enačenje algoritma s programom;
- prezrti omejitvi časa in pomnilnika;
- iskanje optimalnosti pred pravilnostjo;
- primerjava realnih števil z ==;
- neizvedeno sledenje zaradi »očitnega« rezultata.