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

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. 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 rekurzijom, š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).

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 (u trenutku objave ovog programa) može pronaći na https://people.ksp.sk/~misof/ioi-syllabus/ioi-syllabus.pdf.

Kvalifikacije

  • Sve oblasti pokrivene ovim programom
  • Prva dva zadatka u svakom krugu zahtevaće isključivo znanja potrebna za Okružno takmičenje u B kategoriji

Okružno takmičenje - kategorija B

  • Upotreba jednostavnih struktura podataka (podržanih samim jezikom, bibliotekom ili sopstvenom implementacijom, po želji)
    • Niz, matrica
    • String
    • Stek, red
  • Elementarne tehnike popravljanja efikasnosti, kao što su
    • Primena formula radi izbegavanja iteracija (npr. zbir prvih n prirodnih brojeva)
    • Prefiskni i sufiksni zbirovi
    • Inkrementalnost (korišćenje prethodno izračunatih veličina radi efikasnijeg računanja sledećih)
    • Tehnika dva pokazivača
    • Odsecanje u linearnoj pretrazi (izbegavanje pretrage u delu za koji može da se zaključi da ne sadrži rešenja)
  • Zapis celog broja u računaru
    • Brojevni sistemi (npr. binarni i heksadekadni sistem)
    • Operacije nad bitovima (and, or, xor, not, shift)
  • Primene sortiranja
    • Upotreba algoritma iz biblioteke za sortiranje podataka bilo kog tipa po raznim kriterujumima
    • Sortiranje prebrojavanjem (counting sort) i razvrstavanjem (radix sort)
  • Binarna pretraga
    • Efikasna pretraga sortiranog niza i varijante tog problema
    • Pronalaženje poslednjeg elementa koji ne zadovoljava, ili prvog koji zadovoljava uslov u nizu uređenom po zadovoljenosti tog uslova.
  • Pohlepni (gramzivi) algoritmi (greedy algorithms)
  • Osnovni algoritmi teorije brojeva
    • Provera da li je broj prost i faktorizacija broja u složenosti O(sqrt(n))
    • Euklidov algoritam (NZD, NZS)
    • Eratostenovo sito
  • Osnovi analitičke geometrije
    • Predstavljanje osnovnih geometrijskih objekata u koordinatnoj ravni (tačke, duži, prave, kružnice)
    • Jednostavni postupci nad geometrijskim objektima (euklidska rastojanja, Pitagorina teorema)

Okružno takmičenje - kategorija A

Кao za kategoriju B i još:

  • Osnovna upotreba struktura podataka (podržanih samim jezikom, bibliotekom ili sopstvenom implementacijom, po želji)
    • Mapa, skup, prioritetni red (map, (multi)set, priority_queue) (npr. provera pripadnosti elementa skupu)
    • Red sa dva kraja (deque)
    • Povezane liste
  • Binarna pretraga po vrednosti rešenja
  • Rekurzija i bektrek
    • Prebrojavanje i generisanje kombinatornih objekata (permutacija, kombinacija, varijacija, podskupova, ...)
    • Optimizacija pretrage odsecanjem (branch and bound)
  • Efikasno računanje stepena (binarno stepenovanje)

Državno takmičenje - kategorija B

Као за окружно А категорије, и још

  • Dinamičko programiranje (DP)
    • Primena DP u problemima kombinatornog prebrojavanja, npr. broj particija zadatog broja, broj korektnih nizova zagrada i sl.
    • Primena DP u rešavanju klasičnih optimizacionih problema, poput:
      • Problem ranca (Кnapsack problem)
      • Najduži rastući podniz (LIS)
      • Najduži zajednički podniz (LCS)
  • 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, predstavljanje i osobine stabla (kao specijalne klase grafova)
  • Princip “podeli pa vladaj” (divide & conquer) i primene (npr. u algoritmu merge-sort)

Državno takmičenje - kategorija A

Кao za kategoriju B i još:

  • Napredne tehnike dinamičkog programiranja
    • Dinamičko programiranje nad stablom
    • Dinamičko programiranje sa bitmaskama
  • Grafovi
    • Topološko sortiranje
    • Najkraći put između dva čvora primenom Dajkstrinog algoritma, sa i bez hipa
  • Strukture podataka
    • Napredna upotreba bibliotečkih strukutra map, set i priority_queue (npr. traženje najmanjeg elementa, korišćenje proizvoljnih tipova podataka kao ključeva, binarna pretraga elemenata skupa i mape (lower_bound, upper_bound), itd.)
    • Osnovne primene statičkih balansiranih binarnih stabla tj. segmentnih stabla (Segment tree/Tournament tree), kumulativnih tabela (Binary Indexed Tree/Fenwick tree) i Sparse tables-a
    • Disjunktni skupovi (Union-Find)
  • Napredne kombinatorne tehnike
    • Princip uključenja-isključenja
    • Osnove kombinatorne teorije igara (pobedničke/gubitničke pozicije)
  • Geometrijski algoritmi
    • Кorišćenje vektorskog i skalarnog proizvoda, npr. provera paralelnosti, ortogonalnosti, kolinearnosti, “levog/desnog skretanja” (orijentacije trojke tačaka), itd.
    • Računanje površine prostog poligona
    • Nalaženje preseka duži/pravih
    • Provera pripadnosti tačke poligonu

Srpska informatička olimpijada

Sve prethodno i još:

  • Napredni grafovski algoritmi
    • Najkraći putevi
      • Belman-Fordov algoritam
      • Flojd-Varšalov algoritam
    • 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
    • Dekompozicije statičkih stabala
      • Teško-laka dekompozicija (heavy-light decomposition)
      • Centroidna dekompozicija (centroid decomposition)
  • Napredne strukture podataka
    • Napredne varijante segmentnih stabla i kumulativnih tabela
      • 2D/3D segmentna stabla/kumulativne tabele
      • Tehnika lenjog propagiranja za segmentna stabla (lazy propagation)
      • Implicitno predstavljanje segmentnih stabala
      • Perzistentna segmentna stabla (Persistent segment trees)
    • Nalaženje najstarijeg zajedničkog pretka (LCA) u stablu, u složenosti O(log n)
    • Struktura TRIE
    • Balansirana binarna stabla pretrage (zadaci neće biti dizajnirani tako da zavise od konkretnih implementacija poput red-black tree, splay tree, treap…)
  • 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, …)
    • Poznavanje principa matematičke indukcije i pojma rekurentne jednačine
    • 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 osnovne sintakse i semantike programskog jezika C++ (tipova podataka, izraza, naredbi, funkcija, ...)
    • Poznavanje razvojnog okruženja
    • Sposobnost debug-ovanja (koristeći ugrađeni debugger, štampanjem među-rezultata,...)
    • Poznavanje dodatnih mogućnosti i biblioteka programskog jezika C++
    • Rad sa interfejsima i modulima (potrebno za SIO)
    • Osnovno poznavanje odgovarajućeg kompajlera i razlike na Windows-u i Linux-u (32-bitne naspram 64-bitnih promenljivih, karakteri za prelazak u novi red, %lld naspravm %I64d,...)

Dodatak 2 - Znanja koja se ne zahtevaju

Neka od opisanih znanja iz programa (npr. podeli pa vladaj tehnika, grafovski algoritmi, 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
    • Voronoj (Voronoi) dijagrami
    • Delone (Delaunay) triangulacija
  • Strukture podataka
    • Kompleksne varijante hipa poput Fibonačijevog hipa
    • Korišćenje i implementacija heš tabela
  • Grafovi
    • Protok u grafu (flow)
    • Težinsko uparivanje (weighted matching)
  • Stringovi
    • KMP algoritam
    • Suffix array/tree
    • Aho-Corasick
  • Razno
    • Napredna teorija kombinatornih igara (npr. Sprague-Grundy teorija)
    • Tehnike bazirane na preciznosti realnih tipova podataka (floating-point)