Денес, практично е невозможно да се замисли животот на луѓето без компјутерите. Реално, тие стануваат дел од сите сфери на општеството. Но, како овие машини успеваат да решат било каков проблем? Како може, преку вашиот компјутер, толку едноставно и безбедно да се испрати порака до вашите пријатели, кои можеби се наоѓаат на другиот крај на светот? Или, како може вашиот телефон, за само неколку секунди, да го пресмета најбрзиот пат од вашиот дом до одредена локација – иако до неа може да се стигне на повеќе начини и преку повеќе патишта?

Одговорот на овие прашања е едноставен – со користење на алгоритми. Имено, кога инженерите изработуваат софтвер за одредена намена, покрај тоа што истите треба да знаат каков проблем треба софтверот да реши - истите мораат, со детални инструкции, да му предочат на компјутерот како да се реши самиот проблем. Накратко, алгоритам претставува множество од чекори кои овозможуваат решавање на одреден проблем - опишани во доволно детали, за истите да можат да бидат извршени од страна на компјутер.

Во овие предавања, ќе се фокусираме на изучување на сите позначајни алгоритми кои наоѓаат широка примена во денешното општество, како и на повеќе податочни структури кои овозможуваат ефикасно решавање на повеќе проблеми. Дополнително, доколку сте ученик кој сака да учествува во натпреварите по информатика, или студент кој сака полесно да ги разбере тајните на оваа област, овие предавања претставуваат одлична можност за подобрување на вашето знаење и вештини.

Потребни предзнаења

Пред да започнете со изучување на темите кои се дел од овие предавања, потребно е да имате основни познавања од некој програмски јазик. Самите материјали содржат код напишан во програмскиот јазик C++, па тоа е препорачаниот јазик за следење на материјалот презентиран во продолжение. Под основни познавања, се подразбира дека знаете како да пишувате едноставни програми, дека знаете што се услови (if, then, else), циклуси (for, while), низи и функции.

Во продолжение е дадена едноставна програма во C++ која ги содржи сите овие елементи. Доколку ви е целосно јасно што прави истата, слободно можете да продолжите со следење на предавањата во продолжение. Доколку пак, има одредени елементи кои ви се нејасни (на пример, функции), слободно посетете го другиот курс кој содржи материјали за изучување на основите на C++, и вратете се кога истите ќе ги совладате.

#include <iostream>
using namespace std;

int findMax(int array[], int N)
{
     int maximum = array[0];
     
     for(int i=1; i<N; i++)
     {
          if (array[i] > maximum)
          {
               maximum = array[i];
          }
     }
     
     return maximum;
}

int main()
{
     int N;
     cin >> N;
     
     int array[N];
     for (int i=0; i<N; i++)
     {
          cin >> array[i];
     }
     
     cout << findMax(array, N) << endl;
     return 0;
}

Накратко, програмата дадена погоре најпрвин чита низа од N броеви од стандарден влез (тастатура), и потоа го печати најголемиот помеѓу нив. Истата содржи функција findMax(array, N), за наоѓање на најголем елемент во низа. Во продолжение на овој курс, често ќе користиме функции за разделување на нашиот код на повеќе делови кои се едноставни за читање.

Барем јас (лично), при имплементацијата на програми, се обидувам да пишувам имиња на променливи на англиски јазик. Имено, бидејќи наредбите во C++ (како if, else, while, итн) се такви, самиот изворен код делува поприродно.

Сложеност

Очигледно, при разгледување на одреден проблем, можно е да постојат повеќе начини за решавање на истиот. На пример, програмата за пронаоѓање на најголем елемент во низа дадена погоре е само еден начин за решавање на проблемот - друг начин на решавање е доколку го натераме компјутерот најпрвин да ги подреди броевите од најголем до најмал и потоа да го отпечатиме првиот број во новата низа (бидејќи истите ќе бидат подредени почнувајќи од најголемиот, првиот број е оној кој што го бараме).

Или, доколку пребаруваме именик кој содржи телефонски броеви - можеме имињата да ги разгледуваме едно по едно почнувајќи од почеток, или да го искористиме фактот дека имињата во именикот се подредени од A до Ш, и многу побрзо да ја најдеме локацијата на која е запишан одреден број (на пример, доколку знаеме дека бараме телефонски број на “Шуклев Петар”, како и дека Ш e последната буква од азбуката, знаеме дека треба да скокнеме до крајот - каде што се наоѓаат лицата чија прва буква од презимето е “Ш” и да бараме таму).

Во сите предавања за алгоритми кои ќе следат во продолжение, ќе ја дискутираме нивната “временска сложеност”. Истата претставува многу важна мерка за ефикасноста на самите алгоритми, и овозможува лесно да се прават анализи за тоа колку брзо ќе функционира одреден алгоритам при решавање на даден проблем. На пример, за програмата дадена погоре, можеме да кажеме дека истата има сложеност O(N), бидејќи брзината со која истата ќе заврши зависи линеарно од N (поради for циклусот, кој ќе се изврши N пати, т.е. ќе го измине секој број од низата). Ваквите ознаки за временска сложеност O(…) ни овозможуваат да правиме брзи и едноставни споредби помеѓу повеќе алгоритми кои решаваат ист проблем, и да го одбереме најефикасниот помеѓу нив.

Многу е важно, пред да почнете со изучување на самите податочни структури, како и алгоритмите дадени во овие предавања, да знаете што значат ознаките за временска сложеност кои ќе ги користиме. Доколку сеуште не сте запознаени со нив, не грижете се – првото следно предавање од овој курс е токму насечено кон ова. Во спротивно, доколку веќе имате основни познавања од делот за временска сложеност, тогаш слободно можете истото да го прескокнете (на пример, доколку сте ги прочитале предавањата од курсот за C++, каде имаше дискусија за оваа тема).

Структура

На Интернет, постојат повеќе сајтови кои овозможуваат да се запознаете со основите на алгоритмите, како и најкористените податочни структури. Сепак, по наше мислење, материјалите кои ќе ги најдете на овој сајт се од извонреден квалитет, и истите овозможуваат едноставно и брзо изучување на најважните поими од оваа област. Дополнително, предавањата кои се наоѓаат на овој сајт се на македонски јазик, а истите, покрај теорија, содржат слики и анимации, како и практични задачи кои можете да ги решавате во било кој период од денот.

Самиот систем содржи функционалност за автоматско оценување на вашите решенија. По испраќање на решение на одредена задача, таа се тестира од страна на системот и вие добивате повратен одговор за точноста на вашето решение за само неколку секунди. Решавањето на задачите не е задолжително, и не постои временско ограничување во кое треба да се решат задачите или да се прочитаат предавањата. Целта на системот е да им овозможи околина на учениците во која секој од нив ќе може ефективно да учи – на начин на кој самиот ученик смета дека е најдобар за него.

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

Развојна околина

За да можете да извршувате програми на вашиот компјутер, потребно е на истиот да имате инсталирано интегрирана развојна околина за пишување на C++ програми. Моментно, најдоброто бесплатно IDE за пишување на овој тип на програми е Code::Blocks. Оваа алатка стандардно се користи од илјадници корисници - како за пишување на едноставни програми, така и за креирање на сериозни комерцијални проекти.

Преземете го Code::Blocks од следниот линк: codeblocks-16.01mingw-setup.exe.

Инсталирајте го Code::Blocks со едноставно извршување на преземената setup датотека. Доколку користите оперативен систем различен од Microsoft Windows, постои Code::Blocks верзија и за вашиот компјутер. Истата можете да ја пронајдете тука: http://www.codeblocks.org/downloads/26.

Автор

Како што е наведено и во другиот курс за програмскиот јазик C++, една од основните работи кои ги научив како студент е дека е важно да се претставиме пред луѓето пред кои презентираме. На тој начин, другите учесници во дискусијата знаат кого да пофалат (доколку нешто функционира како што треба) или да контактираат, прашаат или обвинат (доколку нешто не функционира како што треба).

Името на авторот на овие предавања е Бојан Костадинов. Јас сум магистер по информатички науки и компјутерско инженерство, програмер, но и поранешен натпреварувач по информатика и автор на системот на кој се спроведуваа официјалните натпревари по информатика за основно и средно образование во последните неколку години.

Натпревари

Доколку сте ученик во основно или средно училиште, а сте заинтересирани за учество на натпревари по информатика, повеќе информации можете да добиете на веб-сајтот на Здружението на Информатичарите на Македонија (http://cs.org.mk). Самите натпревари се спроведуваат преку сајтот http://mendo.mk. Во моментот кога се пишувани овие предавања, ЗИМ е здружението кое ги организира официјалните натпревари по информатика за основно и средно образование.

Натпреварите се одлична можност за унапредување на вашето знаење, вежбање на наученото од овие предавања, како и за запознавање на други ученици кои имаат слични интереси како вашите. Најдобрите натпреварувачи имаат можност да ја претставуваат Македонија на разни балкански и интернационални натпревари по информатика.

Контакт

Доколку имате било какви сугестии за подобрување на материјалите дадени на овој сајт, слободно контактирајте не со испраќање на вашите коментари. Истото можете да го направите преку форумот, или со притискање на копчето “Помош” кое се наоѓа во горниот дел од вашиот екран. Сите ваши коментари и идеи ќе бидат разгледани, и доколку постои можност за нивна имплементација, истото ќе го направиме во најкраток можен рок.

Дозвола за користење: CC BY-NC 2.5 ©