Предговор¶

Ефикасност алгоритама је једна од тема која није довољно позната међу ученицима и наставницима основних и средњих школа. Неупућеност у ову тему посебно погађа ученике који се такмиче у програмирању. Наиме, на такмичењима из информатиике за ученике основних школа у Србији има и задатака у којима треба водити рачуна о ефикасности. Да би освојили све поене предвиђене за такав задатак, такмичари треба не само да напишу програм који даје тачан резултат на сваком тест примеру, него је потребно да се ти тачни одговори добију пре него што истекне време предвиђено за извршавање програма. Неефикасна, а тачна решења могу донети око половине укупног броја поена за такав задатак, а понекад и мање.

У последњих пар година се усталила пракса да се на окружним такмичењима основаца може појавити један задатак за који се очекује ефикасно решење. На државним такмичењима и млађи ученици (пети и шести разред) могу очекивати бар један овакав задатак, а старији и више. Слична пракса је усвојена и у другим земљама, а на међународним такмичењима је значај ефикасности решења још већи. Награђивање ефикасних решења на такмичењима је сасвим оправдано и у складу је са значајем ефикасности програма у пракси. Мноштво је примера да неки програм постане једва употребљив (или сасвим неупотребљив) када треба да обради више података, а само зато што се није водило рачуна о ефикасности.

Малецки увод у ефикасност је написан са намером да помогне у основном разумевању идеја и појмова у вези са налажењем ефикасних решења такмичарских задатака. Намењен је пре свега ученицима основних школа у Србији који се такмиче или намеравају да се такмиче из информатиике, као и њиховим менторима. Курс може бити користан и занимљив и средњошколцима (нарочито ако су такмичари - почетници) и њиховим наставницима, а препоручујемо га и свима које интересује програмирање, а нису се до сада бавили ефикасношћу алгоритама. Теорија (иначе врло високог нивоа) је овде сведена на минимум и користи се неформално и интуитивно, да би била приступачнија ширем кругу читалаца и циљној популацији. Амбициозније читаоце свакако подстичемо да наставе изучавање ове теме уз неки курс или уџбеник вишег нивоа.

Претпоставља се ниво знања програмирања који је потребан бар за општински ниво такмичења у основним школама.

Иако је C++ најпопуларнији такмичарски језик код нас (што није без разлога), сви примери су ипак дати на језику Пајтон. То је учињено пре свега из жеље да се генерално повећа интересовање за програмирање у Србији, а у оквиру тога и за такмичарско прогрмамирање, и да се подрже и охрабре ученици који уче Пајтон на редовној настави. Осим тога, верујемо да ће сви који разумеју C++ много лакше разумети програме на Пајтону, него обрнуто.

Уколико будете желели да експериментишете са програмима који су овде дати, што свакако поздрављамо, саветујемо да само мале примере испробавате директно у браузеру. За извршавање на великим тестовима и све остало (мерење времена, цртање графика), саветујемо да ако већ нисте - инсталирате Пајтон, копирате дате програме на ваш рачунар и извршавате их у вашем окружењу ван веб браузера.

У оквиру овог скраћеног курса можете видети како да измерите време рада вашег програма, како да процените колико времена ће се ваш програм извршавати за велике улазне податке, шта је сложеност алгоритма, како да одредите сложеност неког вашег алгоритма (ако није сувише компликован) и томе слично.

Желимо вам пријатно и успешно програмирање!

Садржај¶