rješavanje problemskih zadataka za srednjoškolce
Učenik si srednje škole, a već si odslušao Algoritme 1 i Algoritme 2 te želiš nastaviti proširivati svoja znanja iz programiranja? Leži ti matematika i želiš ju primijeniti u rješavanju složenijih problema? Kompetitivnog si duha i želiš se okušati na informatičkim natjecanjima? Želiš upisati neki od računalskih fakulteta (FER, FOI, PMF)? Ako si potvrdno odgovorio na neka od ovih pitanja, tečaj ALGORITMI 3 je stvoren upravo za tebe!
Iskusni programeri u Hrvatskoj mogu zarađivati i do 18 000 kn, a u Europskoj uniji ih nedostaje preko 400 000. Jedno od najprivlačnijih zanimanja današnjice je upravo biti programer. Da bi se to postiglo, potrebno je steći temeljna znanja o jednostavnim i složenim algoritmima i apstraktnim strukturama podataka te ih primijeniti u rješavanju problema.
Što su to algoritmi?
Algoritam je niz naredbi koji efikasno rješava neki problem. U ovom će tečaju učenici upoznati različite algoritme za optimalno rješavanje problema iz svakodnevnog života poput problema najkraćeg puta između dva mjesta; problema trgovačkog putnika ili pak problema pronalaženja optimalne raspodjele posla među radnicima. Ti se problemi najčešće mogu matematički modelirati i to pomoću teorije grafova, teorije brojeva, kombinatorike i ostalih područja matematike. Učenici će steći vještinu osmišljavanja algoritma koji rješava zadani problem. Međutim, zadani problemi su jako često složeni, pa će biti potrebno kombinacijom postojećih i osmišljavanjem novih algoritama doći do efikasnog rješenja. Učenici će, dakle, ne samo naučiti kako riješiti određeni problem, već ga riješiti na optimalan način tako da se na računalu, što je moguće prije, njihov algoritam izvrši. Na ovom će tečaju polaznici koristiti programski jezik C/C++ koji se pokazao kao idealan za pisanje efikasnih programskih rješenja.
Za koga su namijenjeni Algoritmi 3?
Algoritmi 3 je tečaj namijenjen srednjoškolcima koji su već prošli tečajeve Algoritmi 1 i Algoritmi 2 te žele savladati još složenije algoritme, strukture podataka i programerske tehnike.
Ishodi učenja:
- razumjeti osnovne algoritamske konstrukte
- dizajnirati algoritam i izabrati optimalne tipove i strukture podataka u rješavanju složenih problema
- procijeniti efikasnost algoritama sortiranja i pretraživanja
- koristiti napredne tehnike i metodologiju programiranja u ustroju algoritama
- prezentirati i argumentirati svoje stavove, ideje i rješenja
- razvijati vještinu matematičko-logičkog razmišljanja
- razvijati kreativnost i snalažljivost u rješavanju problema
- povezati matematiku i informatiku s ostalim prirodnim znanostima
- upoznati mogućnosti i granice primjene računala u rješavanju problema
Teme:
- matematički algoritmi: brzo potenciranje, Hornerov algoritam, Euklidov algoritam, Eratostenovo sito, Fibonaccijevi brojevi, uzastopno prebrojavanje, princip uključivanja i isključivanja, faktorijeli, binomni koeficijenti, …
- teorija grafova: najkraći put, najmanje razapinjuće stablo, artikulacijske točke i rastav na jako – povezane komponente, bipartitni grafovi i sparivanje, mreže i najveći tok u mreži, najniži zajednički predak para vrhova u stablu, Eulerova tura, Hamiltonov ciklus, …
- geometrijski algoritmi: konveksna ljuska, algoritmi skeniranja linijom, površina i opseg poligona, testiranje je li točka u unutrašnjosti poligona, pravci i krivulje drugog reda, osnove trigonometrije, …
- strukture podataka: stog, red, prioritetni red, skup, mapa, vezana lista, logaritamska struktura, union-find, turnirsko stablo, trie, …
- metode oblikovanja algoritama: pohlepni algoritmi, backtracking, dinamičko programiranje, podijeli pa vladaj, …
- pretraživanja: binarno, ternarno, BFS, DFS, …
- sortiranja: mergesort, quicksort, topološko sortiranje, …