$$ \newcommand{\floor}[1]{\left\lfloor{#1}\right\rfloor} \newcommand{\ceil}[1]{\left\lceil{#1}\right\rceil} \newcommand{\mod}{\,\mathrm{mod}\,} \renewcommand{\div}{\,\mathrm{div}\,} \newcommand{\metar}{\,\mathrm{m}} \newcommand{\cm}{\,\mathrm{cm}} \newcommand{\dm}{\,\mathrm{dm}} \newcommand{\litar}{\,\mathrm{l}} \newcommand{\km}{\,\mathrm{km}} \newcommand{\s}{\,\mathrm{s}} \newcommand{\h}{\,\mathrm{h}} \newcommand{\minut}{\,\mathrm{min}} \newcommand{\kmh}{\,\mathrm{\frac{km}{h}}} \newcommand{\ms}{\,\mathrm{\frac{m}{s}}} \newcommand{\mmin}{\,\mathrm{\frac{m}{min}}} \newcommand{\smin}{\,\mathrm{\frac{s}{min}}} $$
Uvod u algoritme / Matematički algoritmi 1

Matematički algoritmi 1

  • Dozvoljeno polaganje
  • Osnovni
  • Nema
  • Nikola Milosavljević
  • 4/17/2013

Programiranje i matematika su dve nerazdvojne oblasti. Matematiku koristimo stalno, od formiranja ideje, preko samog dizajna agoritma i, na kraju, do analize njegove složenosti. U takmičarskom programiranju nisu sve obasti matematike ravnomerno zastupljene ali ipak tu svoje mesto nalaze kombinatorika, teorija grafova, teorija brojeva, analitička geometrija, algebra, numerička matematika itd. Zato je bitno poznavati teoriju ovih oblasti (bar na osnovnom nivou) a još bitnije je poznavati lepe ideje i “cake” koje svaka od oblasti sadrži na pretek.

 

Iako je svaki algoritam na neki način “matematički”, pod pojmom Matematički algoritmi ovde podrazumevamo algoritme koji su direktna posledica teorije odgovarajuće matematičke obasti i koji se uglavnom primenjuju na nama poznatim objektima”: brojevima, nizovima, funkcijama… Kako ovakvih algoritama ima puno, biće obrađivani u više koraka tj. lekcija. Ova lekcija predstavlja samo prvi korak i bavi se teorijom brojeva.

 

Algoritmi teorije brojeva su veoma bitni – jedna od najvećih praktičnih uloga im je u kriptografiji (npr. RSA). Ovde će biti analizirani osnovni koncepti teorije brojeva kao što su deljivost, prosti brojevi i jedinstvena faktorizacija. Naučićete šta su to brojevni sistemi i kako isti broj može imati različite zapise. Upoznaćete se sa Eratostenovim sitom, Euklidovim algoritmom i sa idejama koje omogućavaju da čak i sa brojevima reda veličine 1.000.000.000.000.000.000 radimo dovoljno efikasno.