Kursplan Tävlingsprogrammering 1

Mål

Efter kursen ska eleven kunna:
grundläggande programmering i C++
enkla problemlösningstekniker så som rekursion, giriga algoritmer, simulering, back-tracking och dynamisk programmering
göra uppskattningar om körtid hos ett program och vid behov utföra nödvändiga optimeringar
lösa de problem som uppkommer i Programmeringsolympiadens kvaltävling


Innehåll

Kursen ska behandla:
Programmering

Syntax för C++.
Standardbiblioteken i C och C++ (libc och STL).
Lätt objektorientering.
Debugging-tekniker.

Problemlösning och matematik

Enkla problemlösningstekniker så som rekursion, giriga algoritmer, simulering, back-tracking och dynamisk programmering.
Analys av tidskomplexitet hos en algoritm.
Lätt grafteori och grafteoretiska algoritmer, spelteori och annan diskret matematik som uppkommer i programmeringsproblem.
Optimeringstekniker så som memoisering, pruning och korrekt val av datastrukturer.
Matematiska bevismetoder.