Алгоритми. Вовед.

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

Ги земам за пример земјите од соседството. Хрватаска е одличен пример за тоа како треба да се едуцираат млади кадри и пример за тоа како државата се грижи за своите таленти, Бугарија редовно е меѓу првите 10 земји во свет, Романија отсекогаш ги имала едни од најдобрите програмери (зборувам во светски рамки). Наскоро планирам да напишам и за тоа кои земји колку имаат постигнато во полето на програмирањето. Во ова што го напишав и што го поставив овде се вклучени и мои размислувања. Некои од податоците се земени од Интернет (wikipedia).

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

Algoritmi.pdf

Транспортни мрежи (Network Flow)

Транспортна мрежа е ориентиран граф, без циклуси во кој на секое ребро (i, j) му е придружен реален број аij>=0 што се нарекува пропусна способност на реброто, и за кој важи

• постои едно и само едно теме s, за кое важи дека нема ребра што влегуваат во тоа теме, кое се нарекува влезно теме или влез на мрежата
• постои едно и само едно теме t за кое важи дека нема ребра кои што излегуваат од тоа теме, кое се нарекува излезно теме или излез од мрежата

Протокот низ секое ребро не е поголем од неговата пропусна способност.
За секое теме освен влезното и излезното важи дека вкупниот проток што влегува во темето е еднаков со вкупниот проток што излегува од темето

Алгоритмот за наоѓање максимален проток од влезот (s) до излезот (t) е следен:

Алгоритмот ја започнува работата со произволен проток, што може да биде и нулти поток (се ставаат сите моментални проводности на нула). Потоа, протокот постојано се зголемува со систематска проверка на сите аугментални патеки од s кон t. Барањето на овие аугментални патеки се прави со помош на доделување ознаки на темињата кои кажуваат во правец на кои ребра и за колку потокот може да биде зголемен. Така, потокот се зголемува за максимално можна вредност и потоа повторно се ажурираат ознаките на темињата. Постапката се повторува се додека има аугментални патеки од s кон t.

Овој алгоритам е познат како алгоритам на Форд-Фалкерсон и доколку потокот секогаш го зголемуваме по најкусата аугментална патека, максималниот поток се добива за помалку од |V|*|E|/2 итерации каде што со V го означуваме бројот на темиња, а со E бројот на ребра во графот.

Имплементацијата во Java е следна:

 static int M;        // M is the number of vertices
 static long c[][] = new long[50][50];
 static long f[][] = new long[50][50];  // the flow
 
 static boolean busy[] = new boolean[50];
 static long ver[] = new long[50];
 static int who[] = new int[50];
 
 static void updateNeighbours(int mom) {
  int i;
  long newver;
  
  for (i=1;i<=M;i++) {
   if (busy[i] == false) {
    newver = Math.min(ver[mom], c[mom][i]-f[mom][i]);
    
    if (newver > ver[i]) {
     ver[i] = newver;
     who[i] = mom;
    }
   }
  }
 }
 
 static boolean findPath() {
  // we set all the vertices as unvisited
  int i;
  int bestv;
  long bestscore;
  long dec;
  
  for (i=1;i<=M;i++) {
   busy[i] = false;
   ver[i] = 0;
  }
  
  busy[1] = true;
  ver[1] = Integer.MAX_VALUE;
  who[1] = 0;
  updateNeighbours(1);
  
  while (busy[M] == false) {
   // we find the best vertex found so far
   bestv = 0;
   bestscore = 0;
   
   for (i=1;i<=M;i++) {
    if (busy[i] == false) {
     if (ver[i] > bestscore) {
      bestscore = ver[i];
      bestv = i;
     }
    }
   }
   
   if (bestv == 0) {
    // this means that a path has not been found
    return false;
   }
   
   busy[bestv] = true;
   updateNeighbours(bestv);
   
  }
  
  dec = ver[M];
  i = M;
  while (i!=1) {
   // we work with the segment from i to who[i]
   f[who[i]][i]+=dec;
   f[i][who[i]]=-f[who[i]][i];
   i=who[i];
  }
  
  return true;
 }
 
 static void networkFlow() {
  while (findPath() == true) {
   
  }
 }

M е бројот на темиња.
c[i][j] е пропусната способност на реброто од i до j.
f[i][j] е моменталната проводност по патот од i до j.

Пред да се повика функцијата networkFlow() треба да се иницијализираат пропусните способности на сите ребра. Доколку нема пат од едно теме i до друго теме j тогаш c[i][j]=0. Доколку графот е насочен, т.е. може да се оди само од i до j тогаш само c[i][j] > 0, а c[j][i] = 0. Доколку може да се оди во двете насоки тогаш c[i][j] == c[j][i] > 0. Треба да се напомене дека при повикувањето на networkFlow(), сите елементи f[i][j] треба да бидат иницијализирани на нула.
busy[], ver[] и who[] се низи кои се потребни за работа на алгоритмот на Дијкстра (правилниот изговор е Диџкстра, но јас го викам Дијкстра :) со кој го наоѓаме патот од изворот до излезното теме.

Овој алгоритам може да се примени и за други проблеми, како што е bipartite matching problem. Проблемот може да се дефинира вака.
Дадени ни се група на машки и група на женски и дадено ни е кој со кој си одговара :)
Да се одреди максималниот број на парови што можат да бидат направени така што да си одговараат машкото и женското од секој пар :)




Како може да го решиме проблемот со помош на тоа што веќе го знаеме за транспортните мрежи? Земаме две темиња кои ќе бидат влезно и излезно теме. Сите темиња од групата машки ги поврзуваме со изворот, а сите темиња од групата женски ги поврзуваме со излезното теме. Ги поврзуваме само оние машки и женски кои си одговараат. Сите врски се со тежина 1, т.е. доколку темињата i и j се поврзани, тогаш c[i][j] = 1.

Објаснувањето зошто треба вака да се реши проблемот го оставам на вас :)

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

Користена литература:
USACO
Introduction to Algorithms - Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein
Algorithms in C - Robert Sedgewick

CodeFu, 2008 Seasonal competition!

Во недела 7 декември, во 12 часот ќе се одржи Codefu натпреварот во програмирање. Сигурно повеќето од вас имаат слушнато за овој натпревар кој иако има традиција само две години издигна стандарди за тоа како треба да се организираат натпревари кај нас, а уште поважно, на индиректен начин создаде нови програмери, како што имам кажано, за мене програмер е човек кој што знае да решава проблеми и да размислува "алгоритамски", без навреда кон сите останати. Исто така на тие малкуте квалитетни програмери им го издигна нивото. На овој натпревар задачите се решаваат во Java. Задaчите се алгоритамски и логички и поделени се на тежини.

Мој совет до сите што знаат да програмираат во Java (не треба којзнае колку да си специјалист во Java) но и до тие што не знаат Java , а знаат Pascal, C или C++, да се пријават. Ништо не можат да изгубат туку само да добијат. Java се учи брзо. Од лично искуство кажувам дека да се совлада само тој дел од Java кој ќе ви овозможи да решавате задачи не е многу тешко. Лани специјално за Codefu натпреварот почнав да учам Java и буквално во една вечер ги научив основите на Java. Следниот ден веќе решавав задачи од Codefu. Уште една добра работа. Кога ќе се регистрирате имате пристап до задачите од претходните години. Има околу 50 задачи од различна тежина кои можете да ги решавате и да проверите дали ви се точни или не. Слободно можете да го тестирате системот.

Натпреварот ќе трае 2 часа и ќе се одвива преку Интернет. 5 задачи за 2 часа... малку звучи застрашувачки :) Наградите се примамливи iPod за победникот и уште еден за некој по случаен озбор од оние што имат над нула поени ;) Еве уште една мотивација да учествувате. Што помасовен натпревар значи поголем квалитет на кој ќе се издигнеме сите ние. Секоја чест на организаторите кои ги овозможуваат овие натпревари.

Учествувајте, нема да зажалите!

Прости броеви

Пак математика :) Овде ставам два алгоритми за генерирање на прости броеви.

Првиот алгоритам генерира табела од која брзо може да се види дали некој број е прост.

int i,j;
int N = 100;

boolean isprime[] = new boolean[N+1];

for (i=2;i<=N;i++) {
  isprime[i]=true;
}

for (i=2;i<=N;i++) {
  if (isprime[i]==true) {
      for (j=2*i;j<=N;j+=i) {
          isprime[j]=false;
      }
  }
}

Вториот алгоритам генерира низа во која се чуваат простите проеви.

int i,j;
int prime[] = new int[1000];
int numofprimes=1;
boolean pom;
prime[0]=2;

for (i=3;i<1000;i++) {
   // we check if i is a prime number
   pom=true;
   for (j=0;j<numofprimes;j++) {
       if (prime[j]<=Math.sqrt((double)i)) {
           if (i%prime[j]==0) {
               pom=false;
               break;
           }
       } else {
           break;
       }   
   }
   if (pom==true) {
       prime[numofprimes]=i;
       numofprimes++;
   }
}

Пресметување на комбинации

In combinatorial mathematics, a combination is an un-ordered collection of distinct elements, usually of a prescribed size and taken from a given set.

Овде ќе зборувам за алгоритам за пресметување на комбинации. Според основната дефиниција може да се направи една функција, но како што може да се забележи е многу неефикасна во смисла на тоа што n! тешко може да се смести во променлива, поради големината. На пример 15! = 1,307,674,368,000. Ова не го собира во long, а да не зборуваме за int. Ова не е единствениот недостаток на овој алгоритам, има премногу пресметки па дури и да го поправиме овој алгоритам. Има уште една работа освен комплексноста за која нема да зборувам овде. Еднаш при решавање на задача, го решив најголемиот дел на задачата, и кога дојде она "најлесното", пресметување на комбинациите го оптимизирав овој алгоритам и цело време ми паѓаше на време, се додека не ми текна на нешто што го знаев од часовите по математика. Потоа направив брз алгоритам, но ми беше криво што порано не сум се сетил на тоа :) Но од грешките се учи, па тоа ми беше една добра лекција, доколку некој алгоритам е точен, но паѓа на време, размисли дали проблемот може да се реши со друг алгоритам.

Решението на нашиот проблем лежи во Паскаловиот триаголник. Колку просто :)



Нема да објаснувам многу за ова, повеќе можете да прочитате на wikipedia.

Еве една инплементација на пресметување на комбинации со помош на Паскалов триаголник.

long N=20;
int i,j;
long comb[][] = new long[N][N];

for (j=0;j<N;j++) {
  comb[0][j]=1;
  comb[j][j]=1;
  for (i=1;i<j;i++) {
       comb[i][j]=comb[i-1][j-1]+comb[i][j-1];
  }
}

Како што се гледа, комплексноста на алгоритмот е O(N), а кога ни се пресметани "претходните" комбинации, пресметувањето на една комбинација е во константно време O(1). За да пресметаме N "последователни" комбинации ни треба O(N). Нема да навлегувам во понатамошни анализи :)

Теорија на веројатност

Една од математичките дисциплини кои често се предмет на проучување од страна на програмерите е Теоријата на веројатност. Една од примените е кај проблемите од типот, колкави ми се шансите да фатам на лото :)

Во математиката, веројатноста да се случи еден настан А се претставува како реален број во опсегот од 0 до 1 и се запишува како P(A). Невозможен настан има веројатност 0, и сигурен настан име веројатност 1.

Спротивно или комплемент на настанот A е настанот [not A] (ова е, настанот A не се случил). Неговата веројатност се означува со P(not A) = 1 - P(A)> На пример, шансата да не ти се падне шестка при фрлање на коцка е 1 - (шансата да ти се падне шест) = 1 - (1/6) = (5/6).



Ако двата настани А и B се случат во исто време додека се врши експериментот, ова се нарекува "joint probability" на A и B.
Ако двата настани А и В се независни, тогаш "joint probability" е:

P(A and B) = P(A) * P(B)

пример: ако две монети се фрлени, шансата да се погоди "глава" и кај двете е (1/2) * (1/2) = (1/4).



Ако се случи настанот А или настанот В, или пак се случат и двата настани истовремено, ова се нарекува унија на настаните А и В.
Ако настаните А и В не можат да се случат истовремено т.е. тие се зависни, тогаш веројатноста да се случи еден од нив е:

P(A or B) = P(A) + P(B)

пример: шансата да ти се погоди 1 или 2 при фрлање на коцка е P(1 or 2) = P(1) + P(2) = (1/6 + (1/6) = (1/3)

Ако настаните А и В не се зависни еден од друг тогаш:

P(A or B) = P(A) + P(B) - P(A and B).

На пример, при извлекувањето на една карта по случајност од еден шпил од карти, шансата да добијам "срце" или карта во боја (J, Q, K) (или една што е и во срце и е карта во боја) е (13/52) + (12/52) - (3/52) = (22/26), затоа што од 52 карти, 13 се во "срце", 12 се карти во боја, и 3 се и двете: овде веројатноста вклучена во "3 што се и двете" се вклучени во секоја од "13 срца" и "12 карти во боја", но треба да бидат избројани само еднаш.



Условна веројатност е веројатноста да се случи некој настан А, при дадена веројатноста на друг настан B. Симболот погоре се чита "веројатност на А, при дадено В". Се дефинира како:

P(A | B) = P(A and B) / P(B)

На пример. Земаме два настани А и В. Две фрлања на коцки А и В.

A: Првата коцка паѓа на 3.
В: Вкупната сума на погодени броеви по фрлањето на втората коцка е 8.

Да претпоставиме дека ги фрламе двете коцки истовремено и ја покриваме втората коцка, па само ја гледаме коцката 1; и забележуваме дека коцката 1 паднала на 3. При дадена половична информација, веројатноста дека збирот на двете коцки ќе даде 8 не е 5/36 (2+6; 3+5, 4+4, 5+4, 6+3 од сите можни збирови на двете коцки кои се 6*6 на број) туку е 1/6, затоа што втората коцка мора да падне точно на 5 за да се постигне бараниот резултат.

Повеќе информации и примери за условна веројатност.

Најмал заеднички содржател

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

int nzd(int a, int b) {
   return ( b != 0 ? nzd(b, a % b) : a );
}

int nzs(int a, int b) {
   return (a*b)/nzd(a,b);
}