Natjecateljsko programiranje

Nauči vidjeti
širu sliku.

Vještina na kojoj će se polaznike upoznati s primjenom algoritama u rješavanju složenih problema. Cilj vještine je predstaviti polaznicima primjenu već naučenih algoritama na složenije probleme i područja na kojima njihova primjena nije nimalo očita, a ponekad ni intuitivna.

Moj natpro Materijali

01

Uvodno predavanje

Upoznajte se s predavačima natjecateljskog programiranja i strukturom kolegija. Nakon upoznavanja slijedi kratak uvod u C++ i podsjećanje osnovnih algoritama.

Materijali

02

Sortiranje i pretraživanje

Korištenje i način rada funkcija za sortiranje integriranih u programski jezik te binarno pretraživanje rješenja.

Materijali

03

Potpuno pretraživanje i pohlepni algoritmi

Upoznat ćemo te s metodama backtrackinga, pruninga, meet in the middle te pohlepnih rješenja problema.

Materijali

04

Dinamičko programiranje

Naučit ćemo te koncept dinamičkog programiranja, te objasniti ti kako se računa složenost uz istovremeni oprez na količinu korištene memorije.

Materijali

05

Upiti nad intervalima 1

Upoznat ćeš sljedeće algoritme: prefix sum, difference array, sparse table, fenwick, kompresija indexa.

Materijali

06

Upiti nad intervalima 2

Naučit ćeš implementirati segmentno stablo te offline algoritme uz mnoge primjere primjene naučenog.

Materijali

07

Grafovi 1

Upoznat ćeš načine zapisa grafa u memoriju, najkraće puteve, strukturu union find (koja se koristi u algoritmu MST) te detekciju ciklusa.

Materijali

08

Grafovi 2

Naučit ćeš topološki sort, Kosaraju algoritam, 2SAT problem te LCA skakanje.

Materijali

09

Matematika

Upoznat ćemo te s teorijom igara, teorijom brojeva te linearnim sustavima koje rješavamo matricama.

Materijali

10

Stringovi

Naučit ćeš hash algoritme, sufiksne nizove te sve vezano uz njih.

Materijali