Program takmičenja za srednjoškolska takmičenja iz informatike 04.12.2017

Program takmičenja

Godišnji ciklus takmičenja iz informatike učenika srednjih škola Republike Srbije (u daljem tekstu “ciklus takmičenja”) koncipiran je tako da se težina zadataka povećava sa porastom nivoa takmičenja. Na težinu zadatka utiče složenost ideje, količina znanja i nivo programerskog umeća koji su potrebni da bi se zadatak rešio.

Tehnike, algoritmi i strukture podataka (u daljem tekstu “znanja”) potrebni za određene nivoe takmičenja su navedeni u sledećoj listi; crvenom bojom označena su znanja koja mogu doći samo za A kategoriju na datom nivou. Svaki nivo takmičenja podrazumeva i sva znanja potrebna za sve prethodne nivoe, bez obzira na kategoriju takmičara (npr. na Državnom takmičenju za B kategoriju može doći zadatak sa Quick sort-om, što je znanje koje je na Okružnom takmičenju potrebno za A, ali ne i za B kategoriju).

Kvalifikacije, kao specifični online nivo takmičenja, mogu zahtevati znanja sa svih onsite nivoa takmičenja (okružno, državno, SIO). Za ovaj nivo se garantuje da će za bar jedan zadatak (a uglavnom za više) biti dovoljna znanja za okružno takmičenje B kategorije.

Na Srpskoj informatičkoj olimpijadi (SIO) nema podele na kategorije i program ovog nivoa je koncipiran tako da je u skladu sa programom Međunarodne informatičke olimpijade (IOI) čija se poslednja verzija može pronaći na http://ioi2017.org/files/ioi-syllabus-2017.pdf.

Okružno takmičenje

  • Jednostavne strukture podataka (korišćenje i implementacija)
    • Nizovi i matrice
    • Stringovi
    • Povezane liste
    • Stek i red (stack & queue)
  • Osnovni matematički postupci
    • Brojevni sistemi
    • Operacije nad bitovima (and, or, xor, not, shift)
    • Efikasno računanje eksponenta (binarno stepenovanje)
  • Osnovni algoritmi teorije brojeva
    • Provera da li je broj prost i faktorizacija broja u složenosti O(sqrt(n))
    • Eratostenovo sito
    • Euklidov algoritam (NZD, NZS)
  • Rekurzija i backtrack
    • Generisanje i prebrojavanje kombinatornih objekata (permutacija, kombinacija, varijacija, podskupova, ...)
    • Optimizacija pretrage odsecanjem (branch and bound)
  • Algoritmi sortiranja
    • Selection sort, insertion sort, bubble sort
    • Counting sort
    • Quick sort
  • Osnovi analitičke geometrije
    • Predstavljanje osnovnih geometrijskih objekta u koordinatnoj ravni (tačke, duži, prave, kružnice)
    • Jednostavni postupci nad geometrijskim objektima (nalaženje preseka duži/prava, euklidska rastojanja, Pitagorina teorema)
  • Pohlepni (gramzivi) algoritmi (greedy algorithms)
  • Binarna pretraga
    • Efikasna pretraga sortiranog niza i varijante tog problema
    • Binarna pretraga po vrednosti rešenja

Državno takmičenje

  • Princip “podeli pa vladaj (divide & conquer)”
    • Merge sort
    • Brzo nalaženje k-tog elementa u nizu (quickselect)
  • Dinamičko programiranje
    • Poznavanje principa matematičke indukcije i pojma rekurentne jednačine
    • Poznavanje tehnika u rešavanju klasičnih optimizacionih problema, poput:
      • Problem ranca (Knapsack problem)
      • Najduži rastući podniz (LIS)
      • Najduži zajednički podniz (LCS)
    • Dinamičko programiranje nad stablom
    • Dinamičko programiranje sa bitmaskama
  • Jednostavni grafovski algoritmi
    • Predstavljanje grafova preko matrica i listi susedstva
    • Pretraživanje u dubinu i širinu (DFS i BFS), i primene (povezane komponente, nalaženje ciklusa, najkraći put u netežinskom grafu…)
    • Pojam i osobine stabla (kao specijalne klase grafova)
    • Topološko sortiranje
  • Geometrijski algoritmi
    • Korišćenje vektorskog i skalarnog proizvoda (provera paralelnosti, ortogonalnosti, kolinearnosti, “levog/desnog skretanja” (vector orientation), …)
    • Računanje površine prostog poligona
    • Provera pripadnosti tačke poligonu
  • Strukture podataka
    • Predstavljanje binarnog stabla pretrage
    • Heap
  • Napredne kombinatorne tehnike
    • Princip uključenja-isključenja
    • Osnove kombinatorne teorije igara (pobedničke/gubitničke pozicije)

Srpska informatička olimpijada

  • Napredni grafovski algoritmi
    • Najkraći putevi
      • Dijkstrin algoritam, sa i bez heap-a (Dijkstra)
      • Belman-Fordov algoritam (Bellman-Ford)
      • Flojd-Varšalov algoritam (Floyd-Warshall)
    • Minimalna razapinjuća stabla (MCST/MST) - Primov i Kruskalov algoritam
    • Dvostruka povezanost (biconnectivity), artikulacioni čvorovi i mostovi
    • Jako povezane komponente (strongly connected components)
    • Uparivanje (matching) u bipartitnom grafu - algoritam složenosti O(VE)
    • Detekcija/nalaženje Ojlerovog ciklusa u grafu
  • Napredne strukture podataka
    • Balansirana binarna stabla pretrage (zadaci neće biti dizajnirani tako da zavise od konkretnih implementacija poput red-black tree, splay tree, treap…)
    • Disjunktni skupovi (Union-Find)
    • Statička balansirana binarna stabla tj. segmentna stabla (Segment tree/Tournament tree) i kumulativne tabele (Binary Indexed Tree/Fenwick tree)
      • 2D/3D segmentna stabla/kumulativne tabele
      • Lazy propagation tehnika za segmentna stabla
      • Implicitno predstavljanje segmentnih stabala
      • Persistent segment trees
    • Nalaženje najstarijeg zajedničkog pretka (LCA) u stablu, u složenosti O(log n)
    • Struktura TRIE
  • Nalaženje konveksnog omotača poligona - Graham scan



Dodatak 1 - Preporučena predznanja

Zbog specifičnosti takmičenja iz informatike, da bi se gore pomenuta “znanja” mogla u potpunosti savladati, idealno je da takmičar poseduje sledeća “predznanja”:

  • Algoritamsko razmišljanje

    • Razumevanje pojma “algoritam”
    • Razlikovanje efikasnih i neefikasnih rešenja (vreme, memorija, …)
    • Osnovno znanje o složenosti algoritama i intuitivno razumevanje “veliko O” notacije (O(n), O(n log n), …)
    • Sposobnost analize rešenja - provera tačnosti i složenosti, smišljanje (kontra)primera, …
  • Matematičko predznanje

    • Matematička logika (razumevanje postavke problema, sposobnost apstrakcije, logički iskazi)
    • Kombinatorika (kombinatorna prebrajanja, binomni koeficijenti, …)
    • Osnovna teorija brojeva (deljivost, prosti brojevi, najveći zajednički delilac, …)
    • Osnovna analitička geometrija (vektori, jednačine prave, kruga, …)
    • Elementarne matematičke funkcije (koren, apsolutna vrednost, gornji i donji ceo deo, logaritam…)
  • Programski jezik i kompajler
    • Poznavanje sintakse i tipova podataka
    • Poznavanje razvojnog okruženja
    • Sposobnost debug-ovanja (koristeći ugrađeni debugger, štampanjem među-rezultata,...)
    • Poznavanje dodatnih mogućnosti i biblioteka programskog jezika
    • Rad sa interfejsima i modulima (potrebno za SIO)
    • Osnovno poznavanje odgovarajućeg kompajlera i razlike na Windows-u i Linux-u (32bit vs 64bit, new line format, %lld vs %I64d,...)

Dodatak 2 - Znanja koja se ne zahtevaju

Neka od opisanih znanja iz programa (npr. divide & conquer, matematički postupci, geometrijski algoritmi…) u opštem slučaju mogu obuhvatati previše oblasti od kojih neke NISU deo programa ciklusa takmičenja kao ni deo programa IOI-a (iako neke od njih mogu biti potrebne za druga međunarodna takmičenja i korisno ih je znati). Garantuje se da nijedan zadatak u ciklusu takmičenja neće zahtevati znanja data u sledećoj listi:

  • Linearna algebra i analiza
    • Algoritam Gausove eliminacije
    • Furijeove transformacije
    • Linearno programiranje u 3 i više dimenzija
    • Modularno deljenje, računanje multiplikativnih inverza
    • Trigonometrijske funkcije
  • Geometrija
    • 3D geometrija
    • Voronoi dijagrami
    • Delaunay triangulacija
  • Strukture podataka
    • Kompleksne varijante heap-a poput Fibonacci heaps
    • Korišćenje i implementacija heš tabela
  • Grafovi
    • Protok u grafu (flow)
    • Težinsko uparivanje (weighted matching)
    • Heavy-light decompositon
  • Stringovi
    • KMP algoritam
    • Suffix array/tree
    • Aho-Corasick
  • Razno
    • Napredna teorija kombinatornih igara (npr. Sprague-Grundy teorija)
    • Tehnike bazirane na preciznosti floating-point tipa podataka