codeperfection.blogspot.com

CodeFuEdit

noreply@blogger.com (igormk) — Thu, 11 Mar 2010 20:56:00 +0000

Конечно го поставувам програмчево што го направив за парсирање на problem statements од www.codefu.com.mk. Изработено е уште пред година дена, не го објавив тогаш бидејќи има некои багови, не работи за сите типови на задачи, реков дека кога ќе можам ќе го средам ама некако не ми се навраќа кон стар код :) подобро би направил од ново CodeFu parser. Овој кој го поставувам овде е направен буквално за еден ден, не посветив многу време на тестирање и подобрување со менување на кодот и затоа однапред се извинувам доколку не функционира секогаш најдобро... Сепак врши работа, го користам на сите online codefu натпревари. Се користи едноставно, се копира целиот текст на problem statement заедно со примерите и се внесува. Програмата автоматски генерира почетен template за задачата заедно со код за тестирање. Начинот на кој се справувам со тестирањето во main медотот е "позајмен" од познатата алатка со иста функција но за Topcoder - kawagi.

Dowload CodeFuEdit

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

Верувам дека нема да ви биде тешко да се снајдете со алаткава.

Се надевам ќе ви послужи за codefu натпреварите.

Со среќа :)

Збир на елементи во подматрица

noreply@blogger.com (igormk) — Fri, 05 Feb 2010 00:14:00 +0000

Се мислев како да го именувам денешново пишување. Даден ни е следниот проблем:

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

Ќе го дефинираме поимот подматрица.

Ќе го објаснам графички. На сликата ни е дадена матрица А, и нејзина подматрица B.

Се бара да се напише алгоритам кој на најефикасен начин би го пресметал збирот на елементите во подматрицата B.

Ова е интересен проблем кој бара размислување и анализа. Би го класифицирал во архетипот динамичко програмирање иако може слободно да го вметнеме и во групата на математички проблеми (подоцна ќе објасниме зошто). Со проблемов се сретнав на втор колоквиум по предметот Алгоритми и структури на податоци.

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

Прво треба проблемот добро да се сфати. Треба да се анализира што се бара и да се разгледаат примерите доколку ги има. Доколку уште не е јасно, треба да се проба со свои примери да се сфати и анализира проблемот. На пример во случајот со нашата задача

ред 1: 1 2 3

ред 2: 4 5 6

ред 3: 7 8 9

Ги нумерирам редовите и колоните почнувајќи од еден наместо од нула заради полесна имплементација. Со анализа на кодот ќе биде појасно зошто.

Ние треба да напишеме функција sum(x1, y1, x2, y2) каде што (x1, y1) ни е горниот лев агол на подматрицата, а (x2, y2) ни е долниот десен агол на матрицата. Оваа функција треба да го врати збирот на елементите во овој потправоаголник (подматрица). Во нашиот пример:

sum(1, 1, 3, 3) = 45

sum(1, 1, 2, 3) = 27

sum(1, 1, 1, 3) = 12

sum(2, 1, 3, 3) = 33

sum(2, 1, 2, 1) = 2

...

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

Следна фаза, барање на решение на проблемот.

Најпрост алгоритам е следниот. Ја читаме цела матрица и потоа "со два фора" ги поминуваме сите елементи што се во подматрицата и ги собираме. Многу едноставно. Но се бара најефикасен начин. Претходниов начин би бил брз да речеме за матрица со 1000x1000 елементи, релативно брз затоа што тоа би се извршило за помалку од секунда по повик на функцијата sum(x1, y1, x2, y2). Оставам на вас да размислете зошто не е ефикасно, што би можело да се подобри овде, дали можеби некои пресметки би се вршеле по повеќе пати? На кој начин би можело ова да се оптимизира?

Ефикасноста се подобрува со користење на некои готови резултати.

Прва оптимизација би била ако имаме една акумулациона матрица за колони (аналогно е за редови). Оваа матрица би имала ист број на елементи како и оригиналната матрица. Што е логиката на оваа акумулациона матрица за колони. Елементот со индекс (i, j) означува сума на сите вредности од оригиналната матрица кои што се наоѓаат во ј-тата колона, а кои се наоѓаат во ред со индекс <= i. Потоа во методот sum би имале само еден "for" т.е. би имале линеарна комплесност од една димензија на матрицата! Нема да навлегувам во детали како би се имплементирала функцијата sum во овој случај бидејќи не е тешко да се сфати доколку се размисли малку.

Откако ќе го сфатиме претходниот начин, се прашуваме дали можеме да одиме подалеку, т.е. дали можеме да ја оптимизираме функцијата толку многу што таа ќе работи во време O(C) каде што C е константа со мала вредност? Одговорот на ова прашање е да. Се служиме со сличен принцип како претходниот. Имаме две фази, имплементирање на акумулационата матрица и втора фаза имплементирање на методот sum.

Акумулациона матрица. Оваа матрица има исти димензии како и оригиналната матрица. Индексот (i, j) во матрицата означува дека вредноста поврзана со тој индекс е збир на сите елементи во матрицата кои се наоѓаат во ред со индекс <= i и во колона со индекс <= j.

Во примерот даден претходно, матрицата на акумулација би ги имала следниве вредности

ред 1: 1 3 6

ред 2: 5 12 21

ред 3: 12 27 45

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

Кратките и едноставни формули се добар показател дека користиме динамичко програмирање. Во зависност од тоа дали имаме bottom-to-up или up-to-bottom пристап, динамичкото програмирање можеме да го имплементираме итеративно или со рекурзија и мемоизација. Подетално за овие техники во друга прилика. Динамичкото програмирање овде е покарактеристично кај создавањето на акумулационата матрица, техниката за пресметка во методот sum би го нарекол само "математичка финта" :)

Значи при дадена акумулациона матрица М (да напоменеме дека во случајот x1 <= x2 и y1 <= y2),

sum(x1, y1, x2, y2) = m(x2, y2)-m(x1, y2)-m(x2, y1)+m(x2, y2)

Оваа формула многу добро се објаснува графички. Ако со симболи ги означиме правоаголниците тогаш добиваме дека:

area(E) = area(A)-area(B)-area(C)+area(D)

Акумулационата матрица може да се добие на сличен принцип. Тоа убаво се гледа од кодот, поточно во фукцијата generate(). Во програмата вметнав и една функција за тестирање.

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

Download source file

Проблемот би бил целосно поинаков доколку вредностите во матрицата се менуваат периодично. Во тој случај нема да важи опишаниот алгоритам бидејќи нашите пресметки се засноваа на почетната пресметка, периодичното менување на вредностите во матрицата би предизвикало и менување на акумулационата матрица, а токму постојаноста на акумулационата матрица беше факт врз кој ја градевме функцијата sum(x1, y1, x2, y2). Проблемот кога можеме да имаме промени на вредности и повикувања на функцијата sum се решава на принцип многу поразличен од претходно опишаниот, тој принцип не се вбројува во архетипот динамичко програмирање. Еден од начините за решавање на овој проблем е со користење на бинарни индексни стебла, многу ефикасни и навидум сложени, но сепак едноставни структури доколку се сфати принципот на кој тие функционираат. Овде нема да се задржувам на бинарните индексни стебла, но сигурно во некој од наредните post-ови ќе пишувам опширно.

Tower of Hanoi

noreply@blogger.com (igormk) — Sun, 06 Dec 2009 02:14:00 +0000

Проблемот на Ханојски кули (Tower of Hanoi) е позната математичка игра.

Се состои од три стапчиња, и број на дискови со различна големина кои можат да се стават како прстен на било кое од стапчињата. Играта започнува со тоа што сите дискови се наоѓаат на првото стапче во растечки редослед од горе кон доле (најмалиот диск се наоѓа горе). Целта на играта е да се преместат сите дискови на друго стапче, но да не се прекршуваат правилата:

Во еден потег може да биде поместен само еден диск.

Секој потег се состои од земање на еден диск кој се наоѓа на врв на некое стапче и негово преместување најгоре врз другите дискови на некое друго стапче.

Не може еден диск да се постави врз друг помал диск.

Интересна игра со навистина едноставни правила. Најголем дел од вас ја сретнале загаткава како пример за рекурзија во основните курсеви за програмирање.

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

Рекурзивно многу е кратко решението, иако изгледа комплицирано на прв поглед.


#include<iostream>
using namespace std;

void hanoi(int N, char from, char to, char other) {
 if (N == 0) return;
 // we move N-1 disks from "from" to "other"
 hanoi(N-1, from, other, to);
 // we move the biggest disk from "from" to "to"
 cout<<"I moved "<<N<<" from "<<from<<" "<<to<<"\n";
 // we move N-1 disks from "other" to "to"
 hanoi(N-1, other, to, from);
}

int main() {
 int i,j,k;
 hanoi(4, 'A', 'C', 'B');
 cin>>i;
 return 0;
}

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

Да го проучиме подлабоко проблемот.

Да ги дефинираме параметрите на функцијата и потоа преку опис на параметрите на функцијата да ја дефинираме почетната состојба.

void hanoi(int N, char from, char to, char other);

Првиот аргумент N претставува број на дискови кои сакаме да ги префлиме од дискот кој е обележан како from кон дискот обележан како to. Третиот параметар (иако може да се исфрли) го претставува третиот диск кој индиректно ќе биде искористен при поместувањето.

Значи ако функцијата hanoi ни го решава соодветниот генерален проблем на Ханојските кули, ние со повикување на оваа функција со параметри hanoi(N, 'A', 'C', 'B') го решаваме нашиот конкретен проблем, пренесување на N дискови од дискот обележан како 'A' кон дискот обележан како 'C'.

Сега да ја разгледаме "маѓијата" внатре во функцијата.

Клучната чекор кој го правиме е делењето на еден проблем на потпроблеми од ист тип.

Значи треба некако соодветниот проблем префрлање на N дискови од дискот from кон дискот to да го поедноставиме.

Ако сакаме да префлиме N дискови од дискот from, тогаш знаеме дека тие N дискови се наоѓаат најгоре на стапчето и се наредени по растечки редослед од горе кон доле. Притоа ако најгорниот диск го обележиме со 1, и како одиме надоле давајќи повисоки индекси, дискот обележан како N ќе биде најголем во оваа група од N дискови.

Кога добро ќе се сфати ова идеме на следна фаза.

Префрламе N дискови од A кон C така што прво префламе N-1 дискови од A кон B, потоа дискот кој што ќе остане најгоре на A го префрламе на C, потоа ги префрлуваме (N-1) -те дискови од B кон C.

Да повториме уште еднаш, овојпат наместо A ставаме from, наместо C ставаме to, наместо B ставаме other.

Префрламе N дискови од from кон to така што прво префламе N-1 дискови од from кон other, потоа дискот кој што ќе остане најгоре на from го префрламе на to, потоа ги префрлуваме (N-1) -те дискови од other кон to.

Имаме и почетен услов со кој прекинува рекурзијата, кога бројот на дискови кои треба да се префрлат е нула.

AVL стебла

noreply@blogger.com (igormk) — Mon, 12 Oct 2009 00:19:00 +0000

AVL стебло е балансирано бинарно стебло. За AVL стеблата важи, висините на двете потстебла секој јазол се разликуваат најмногу за 1 па затоа се вели дека е балансирано по висина. Пребарување, додавање на елемент и бришење се со комплексност O(log N) време, ова е просечно време и најлошо време истовремено, кадe N е број на јазли во стеблото пред операцијата. Додавање и бришење на елемент како операции може да вклучат ребалансирање на стеблото со една или повеќе ротации на стеблото.

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


class Node {
Node left;
Node right;
Node parent;
int value;
int height;

Node () {
 left = null;
 right = null;
 parent = null;
 height = 1;
}

Node (int value) {
 left = null;
 right = null;
 this.value = value;
 height = 1;
}

}

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


int getHeight(Node mom) {
if (mom == null) return 0;
return mom.height;
}


int ballanceFactor(Node mom) {
if (mom == null) return 0;
int lh = getHeight(mom.left);
int rh = getHeight(mom.right);
return rh-lh;
}

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

Следува објаснувањето за "најкомплицираниот" дел, ротацијата. На сликата се објаснети четирите случаи (кои воглавно се сведуваат на два симетрични).


Node rightRightCase(Node mom) {
if (mom == null) return null;

Node R = mom.right;
Node T2 = R.left;

if (mom.parent.left == mom) {
 mom.parent.left = R;
} else {
 mom.parent.right = R;
}

R.parent = mom.parent;

R.left = mom;
mom.parent = R;

mom.right = T2;
if (T2 != null) T2.parent = mom;

mom.height = Math.max(getHeight(mom.left), getHeight(mom.right))+1;
R.height = Math.max(getHeight(R.left), getHeight(R.right))+1;

return R;
}

Оваа функција како аргумент прима некој јазел кој е корен на стебло. После ротацијата како резултат функцијата го враќа новиот корен на ова потстебло, т.е. десното дете. Напомена, за да работи оваа функција, јазелот кој се испраќа како аргумент треба да има десно дете (во спротивно нема логика да се прави ваква ротација и стеблото не може да има фактор на балансираност -1 кој пак е основен предуслов за некоја друга функција да го повика овој метод).

R е десното дете, а Т2 е левото дете на јазелот mom. Она што во овој код го правиме е известување до родителот на mom дека дете веќе нема да му биде mom туку R. Потоа ги менуваме местата на mom и R, ротираме на лево. Потстеблото Т2 станува десно потстебло на Т2. Правиме ажурирање на висините на mom и R и како резултат функцијата враќа покажувач кон R, за да знае повикувачот на овој метод кој е јазелот кој си го сменил местото со mom.


Node rightLeftCase(Node mom) {
leftLeftCase(mom.right);
return rightRightCase(mom);
}

Овој случај е двојна ротација. Прво го ротираме на десно стеблото чиј корен е mom.right, па потоа вршиме ротација на лево со референтен јазел во mom.

Напомена: rightRightCase е аналогно со ротација на лево, а leftLeftCase е аналогно со ротација на десно.


Node leftLeftCase(Node mom) {
if (mom == null) return null;
Node L = mom.left;
Node T2 = L.right;

if (mom.parent.left == mom) {
 mom.parent.left = L;
} else {
 mom.parent.right = L;
}

L.parent = mom.parent;

L.right = mom;
mom.parent = L;

mom.left = T2;
if (T2 != null) T2.parent = mom;

mom.height = Math.max(getHeight(mom.left), getHeight(mom.right))+1;
L.height = Math.max(getHeight(L.left), getHeight(L.right))+1;

return L;
}


Node leftRightCase(Node mom) {
rightRightCase(mom.left);
return leftLeftCase(mom);
}

Овие два случаи се симетрични со rightRightCase(Node mom) и rightLeftCase(Node mom) и затоа нема повторно да ги објаснувам.


void ballanceTreeInsertion(Node root, Node mom) {
int a, p;

while (mom != root) {
 p = ballanceFactor(mom);
 if (p == 2) {
  // right subtree outweighs the left subtree
  // If the balance factor of R is +1, a left rotation is needed with P as the root.
  // If the balance factor of R is -1, a double left rotation is needed
 
  a = ballanceFactor(mom.right);
 
  if (a == 1) {
   mom = rightRightCase(mom);
  } else {
   if (a == -1) {
    mom = rightLeftCase(mom);
   }
  }
 
 } else {
  if (p == -2) {
   a = ballanceFactor(mom.left);
  
   if (a == -1) {
    mom = leftLeftCase(mom);
   } else {
    if (a == 1) {
     mom = leftRightCase(mom);
    }
   }
  }
 }

 mom = mom.parent;

 // we update the height of mom
 mom.height = Math.max(getHeight(mom.left), getHeight(mom.right))+1;

}

}

Во мојата имплементација, секое балансирано стебло има единствен корен root. Вистинскиот корен е во левото дете на root. Ова е со цел за да може да се претстави стебло со 0 елементи (root.left ќе биде null во тој случај). Исто така, ваква динамична структура често се менува внатрешно и root.left во различни моменти од времето може да има различни јазли, што е тешко да се претстави доколку не постои некој "поврховен" јазел како коренот со кој единствено се претставува и еднозначно се карактеризира секое стебло.

Оваа функција е клучна за добивање на балансираност на стеблото при додавање на нов елемент. Како аргумент се праќа корен на дрвото и јазелот од кој почнуваме да го балансираме дрвото. Го балансираме јазелот mom и потоа се качуваме нагоре по стеблото се додека не стигнеме до коренот. Алгоритмот за балансирање е следен: во p го сместуваме факторот на балансираност на јазелот кој го обработуваме. ДОколку овој број е 2 или -2, тоа значи дека стеблото во тој јазел е небалансирано (понатаму накратко ќе го употребувам поимот балансираност во јазел, наместо балансираност на стеблото чиј корен е конкретниот јазел). Во зависност од тоа дали десното (левото) дете има фактор на балансираност 1 или -1 се одвива единечна или двојна ротација. Пред да се качиме нагоре по хиерархијата ја ажурираме висината на јазелот кој моментално го обработуваме.


void ballanceTreeDeletion(Node root, Node mom) {
int a, p;

while (mom != root) {
 mom.height = Math.max(getHeight(mom.left), getHeight(mom.right))+1;

 p = ballanceFactor(mom);
 if (p == 2) {
  // right subtree outweighs the left subtree
  // If the balance factor of R is +1, a left rotation is needed with P as the root.
  // If the balance factor of R is -1, a double left rotation is needed
 
  a = ballanceFactor(mom.right);
 
  if ((a == 1)||(a == 0)) {
   mom = rightRightCase(mom);
  } else {
   if (a == -1) {
    mom = rightLeftCase(mom);
   }
  }
 
 } else {
  if (p == -2) {
   a = ballanceFactor(mom.left);
  
   if ((a == -1)||(a == 0)) {
    mom = leftLeftCase(mom);
   } else {
    if (a == 1) {
     mom = leftRightCase(mom);
    }
   }
  }
 }

 mom = mom.parent;

 // we update the height of mom
 mom.height = Math.max(getHeight(mom.left), getHeight(mom.right))+1;

}

}

Оваа функција е скоро идентична на претходната, со таа разлика што овде се применува ротација на лево доколку p = 2 и (а = 1 или а = 0), и ротација на десно доколку p = 2 и (а = -1 или а = 0). Првата функција ќе ја употребуваме за балансирање при додавање на елемент, втората при бришење на елемент. Доколку ве интересира зошто е ваква имплементацијата можете да прочитате повеќе во разни книги кои се занимаваат со тематика од областа на алгоритмите и структурите на податоци.


void addNode(Node root, int value) {
Node mom = root.left;
Node newnode = new Node(value);
Node prev = root;

while (mom != null) {
 if (value <= mom.value) {
  prev = mom;
  mom = mom.left;
 } else {
  prev = mom;
  mom = mom.right;
 }
}

newnode.parent = prev;

if (value <= prev.value) {
 prev.left = newnode;
} else {
 prev.right = newnode;
}

// now we need to balance the tree
mom = newnode;

ballanceTreeInsertion(root, mom);

}

addNode прима како аргумент корен и вредност која што сакаме да се смести во стеблото. Се изминува стеблото надоле додека не се дојде до некој "null елемент" и на негово место се сместува новиот. Овде важи правилото, сите лементи во левото потстебло на даден јазел се помали или еднакви на вредноста на тој јазел, а сите елементи во десното потстебло на јазелот се поголеми од неговата вредност. Откако ќе го внесеме јазелот, го балансираме новиот јазел т.е. ја повикуваме функцијата ballanceTreeInsertion која врши верижно балансирање на стеблото нагоре се до коренот.


void deleteNode(Node root, int value) {
Node mom = root.left;
Node prev = root;
Node T;
boolean found = false;

while (mom != null) {
 if (mom.value == value) {
  found = true;
  break;
 }
 if (value <= mom.value) {
  prev = mom;
  mom = mom.left;
 } else {
  prev = mom;
  mom = mom.right;
 }
}

if (found == false) {
 //System.out.println("The element was not found");
 return;
}

Node orig = mom;

if ((orig.left == null)&&(orig.right == null)) {
 // we remove the node
 mom = orig.parent;
 if (mom.left == orig) {
  mom.left = null;
 } else {
  mom.right = null;
 }
 orig = null;

 // we should be sure that the subtree with mom with it's main root element
 // has correct heights and as parametar we give valid element
 mom.height = 1;
 ballanceTreeDeletion(root, mom);
 return;
}

if ((orig.left == null)^(orig.right == null) == true) {
 // if there is exactly one subtree
 mom = orig.parent;
 if (orig.left != null) {
  T = orig.left;
  if (mom.left == orig) {
   mom.left = orig.left;
   orig.left.parent = mom;
  } else {
   mom.right = orig.left;
   orig.left.parent = mom;
  }
 } else {
  T = orig.right;
  if (mom.left == orig) {
   mom.left = orig.right;
   orig.right.parent = mom;
  } else {
   mom.right = orig.right;
   orig.right.parent = mom;
  }
 }
 orig = null;
 ballanceTreeDeletion(root, T);
 return;
}

// the node has 2 subtrees, we need to find the smallest element of the right subtree of mom
mom = orig.right;

if (mom.left == null) {
 // special case, it is more complicated to change the relations
 if (orig.parent.left == orig) {
  orig.parent.left = mom;
 } else {
  orig.parent.right = mom;
 }

 orig.left.parent = mom;
 mom.left = orig.left;
 mom.parent = orig.parent;
 orig = null;
 ballanceTreeDeletion(root, mom);
 return;
}

prev = mom;

while (mom != null) {
 prev = mom;
 mom = mom.left;
}

mom = prev;
prev = mom.parent;

// we are changing the relations instead of just changing the value

if (mom.right != null) {
 mom.right.parent = mom.parent;
}

T = mom.parent;
mom.parent.left = mom.right;

mom.parent = orig.parent;
mom.left = orig.left;
mom.right = orig.right;

if (orig.parent.left == orig) {
 orig.parent.left = mom;
} else {
 orig.parent.right = mom;
}

orig.left.parent = mom;
orig.right.parent = mom;

// now we need to balance the tree
T.height = Math.max(getHeight(T.left), getHeight(T.right))+1;
ballanceTreeDeletion(root, T);

}

Бришењето на јазел од стеблото е малку покомплицирано. Оваа функција како аргумент прима референца кон коренот и клучната вредност на јазелот што сакаме да биде избришан. Прво го пронаоѓаме јазелот во стеблото. Потоа разгледуваме неколку специјални случаи.

Доколку јазелот е лист, т.е. нема лево и десно потстебло, тогаш јазелот едноставно го бришеме, така што ги отстрануваме врските на неговиот родител кон него, и потоа ги балансираме сите јазли додека не стигнеме нагоре до коренот на стеблото.

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

Доколку јазелот Т има две потстебла, тогаш го бараме најмалиот елемент од неговото десно потстебло т.е. го бараме јазелот L (ја употребувам оваа ознака за да објаснам поубаво, во кодот е имплеменирано со променливи со друго име) кој се наоѓа "најлево" во неговото десно потстебло. Ја отстрануваме врската од неговиот родител кон L и овој јазел го ставаме на местото на Т. Т го отстрануваме. Разбирливо, потоа вршиме балансирање на стеблото од јазелот кој претходно беше родител на L. Овде разгледав специјален случај кога L e дете на T. Малку е покомплицирано да се менуваат врските доколку јазлите се директно поврзани. На крај се одвива балансираност која започнува од претходниот родител на L.


void inorder(Node mom) {
if (mom == null) return;

inorder(mom.left);
System.out.println(mom.value);
inorder(mom.right);
}


void inorderRoot(Node root) {
inorder(root.left);
}

Со повикувањето на inorderRoot(Node root) се врши inorder изминување на стеблото, а тоа значи дека ќе бидат отпечатени вредностите што ги содржи стеблото и тие ќе бидат сортирани во неопаѓачки редослед.

Се надевам дека сега некои работи ќе бидат појасни за AVL стеблата и ќе пробате самите да искодирате AVL стебло. За некои од можните примени на овие интересни и многу ефикасни структури во некоја следна прилика.

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

Доколку сакате повеќе да прочитате за AVL стеблата ви препорачувам:

Introduction to Algorightms
Algorithms in C
http://en.wikipedia.org/wiki/AVL_tree

и уште многу ресурси кои можете да ги најдете пребарувајќи на google
http://www.google.com/search?hl=en&source=hp&q=avl+tree&aq=f&oq=&aqi=g7g-s1g2

Кодот заедно со некои тестови кои ги правев можете да го симнете овде:

http://www.mediafire.com/?2vnjyn2nguj

Збор два за O(logN) и стеблата

noreply@blogger.com (igormk) — Sun, 11 Oct 2009 21:57:00 +0000

Структурите секогаш одат заедно со алгоритмите. Ефикасна имплементација е збир од ефикасни податочни структури и ефикасен алгоритам. Некогаш треба и да се прави компромис. Кај многу решенија големата комплексност може да се намали со користење на добри податочни структури. На пример, кај сортирањето, комплексноста од O(N*N) значи дека за N = 1000000 програмата нема во разумно време да даде решение.

Проблемот на сортирање е добро проучен и познати се алгоритми кои даваат решение во време O(N*logN). Овде ќе ги спомнам merge sort и мојот омилен heap sort. Другите сортирања имаат комлексност од O(N*N) во најлош случај. Но, другите сортирања освен оригиналната низа не користат друга меморија и некои релативно комплицирани структури (со исклучок на некои променливи како бројачи и променливи во кои привремено се чуваат податоци).

Кај merge sort и heap sort приказната е поинаква. Merge sort користи две низи, значи оригиналната низа и уште една низа со иста мемориска големина (едно од следните мои пишувања ќе го посветам целосно на сортирања). Heap sort пак користи само една низа, но таа низа е организирана на друг начин кој овозможува сите операции како вметнување на елемент во структурата, бришење, наоѓање на максимум или минимум да се извршуваат во O(1) или O(logN), овие неколку операции индиректно придонесуваат во она што се бара, сортирање на низата.

Стеблото е структура или поим кој се поврзува со посакуваната комплексност O(logN). Значи директно или индиректно, доколку некој проблем бара решение кое е од ред O(logN), тогаш ние ќе треба да се занимаваме со стебло, иако понекогаш стеблото не е очигледно на прв поглед, овде мислам општо, на стебло како структура и стебло како поим, како логичка организација која во својата суштина го има гранењетo.

Очекувана вредност

noreply@blogger.com (igormk) — Thu, 10 Sep 2009 22:00:00 +0000

Последниот SRM 448 ме натера да размислувам за една од моите омилени теми - Веројатност. Првата задача беше поврзана со оваа тема. Како прва и најлесна задача, решението се добиваше рекурзивно, со собирање на веројатностите за сите можни настани. Брзо го напишав ова затоа што инстинктот ми велеше дека ова мора да биде главниот начин за добивање на конечниот резултат. Требаше да се погоди очекуваниот број на карти кои ќе се извлечат, а кои ќе донесат победа. Нема да објаснувам што се бара во задачата, неа можете да ја погледнете на topcoder. Она што не знаев е како сите информации за веројатноста да се искористат за да се добие конечниот резултат. Брзо го искодирав кодот за пресметување на веројатноста. Прво размислував малку како да го искористам она што веќе го имав, но не ми доаѓаше идеја. Потоа на 40 минути до крај малку погуглав и за среќа најдов една страна каде што многу едноставно беше објаснето како се добива очекувана вредност. Формулата е следна:

очекувана вредност = Сума од на сите настани(веројатноста за настан i * вредноста за тој настан i)

Еве да објаснам за еден едноставен пример. Имаме коцка, таа има 6 страни и на секоја страна има по една вредност од 1 до 6. При фрлање на коцката која е очекуваната вредност што ќе ја добиеме?

Значи според формулата:

expected = (1/6)*1+(1/6)*2+(1/6)*3+(1/6)*4+(1/6)*5+(1/6)*6 = (1/6)*21 = 3.5

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

Повеќе за ова можете да прочитате на wikipedia.

Инаку да се вратам на приказната со настапот на SRM 448. Го имплементирав ова, и програмата не ми ги даваше потребните резултати. Значи имаше две потенцијални работи кои се причина за грешното решение. Прво, алгоритмот не е точен, и второ, имам некоја грешка во кодот. Втората опција брзо ја елиминирав мислејќи дека во толку прост код и не може да има некоја грешка, скенирајќи го набрзина кодот за да имам време да размислувам за точноста на алгоритмот. Бидејќи малку бев скептичен во врска со точноста на формулата се обидував да наоѓам други малку поинакви пристапи во крајниот алгоритам и менував некои работи во кодот кои не ми донесоа успех. На крај се откажав. Моја среќа што имаше многу натпреварувачи со ниедна решена па не ми падна многу рејтингот, сега е 1224 и останувам во DIV 1.

Кога заврши натпреварот одлучив да одморам малку. Размислував што би можело да ми биде грешката и полека го анализирав мојот код во главата. Наеднаш дојдов до проблематичниот дел. Наместо for (j=0;j0) што е грешка при брзање... Оваа грешка ме чинеше добар пласман. Алгоритмот бил добар, но сум имал грешка во имплемнтацијата.

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

Тест задача

noreply@blogger.com (igormk) — Wed, 02 Sep 2009 21:49:00 +0000

Случајно најдов на еден многу интересен сајт http://www.scarky.com/ каде може да се постави задача по програмирање. Сите параметри се местат од страна на креаторот, кодот за натпреварот сам се генерира. Можеби тоа што не би го сметал за професионален начин за организирање на натпревари е што нема можност повеќе input-и. Се надевам тоа ќе се поправи во иднина. Ајде сега да го тестираме системот. Производ на два броеви :) Напишете кодче и праќајте. Ќе се обидам наредниве денови да ставам некој попредизвикувачки проблем од областа на програмирањето.

USACO

noreply@blogger.com (igormk) — Sat, 01 Aug 2009 23:48:00 +0000

USACO (http://ace.delos.com/usacogate) е тренинг сајт за програмирање каде секој може да се регистрира и да решава. Според мене, секој кој има елементарни познавања од програмирање и се интересира за решавање на проблеми мора задолжително да го посети сајтот. Вкупно има околу 100 задачи кои се групирани во 6 chapters. Секој chapter се состои од sections. Во секоја секција има околу 3-4 задачи. Убавата и интересната работа е тоа што задачите мора да се решаваат по ред. Не може да се решава задача од некоја повисока секција додека не се решат сите претходни задачи. Во почетокот задачите се лесни, а како се напредува задачите се се потешки. Покрај задачите има и посебни лекции наречени TEXTS. Во секој TEXT е обработена некоја одредена тема од областа на програмирањето и алгоритмите. Сите основни принципи на програмирање и најбитни и најосновни алгоритми се обработени во овој тренинг. Овој тренинг пред се е наменет за средношколци кои се спремаат за натпреварите по информатика, овде пред се мислам на IOI (International Olympiad in Informatics).

На овој тренинг сајт почнав да решавам кон крајот на четврта година средно (пред 2 години) кога се спремав за IOI 2007. Поради обврски кон факултетот пред се, решавав на сајтот со повремени прекини, па така дури денес можам да кажам дека ги решив сите задачи :) Сите задачи се предизвикувачки, но сепак најинтересни ми беа последните три од chapter 6. При решавање се вежба логиката и размислувањето. Некои задачи некогаш и би рекол дека се невозможни на почетокот но кога навистина добро ќе се размисли - за се има решение, само треба да се најде. Начин на решавање на задачите, прво добро да се прочита и да се сфати што е проблемот. Потоа анализа, разгледување на примери, размислување како да се тргне кон решавање. Разгледување на разни начини. Треба да се одбере најлогичниот начин кој претходно треба да е добро анализиран, прво умствено да се изврши па потоа тоа да се преточи во програмски код. Доколку некоја од овие фази се обидете да ја прескокнете или да ја поминете набрзина без добро размислување тоа најчесто се одразува на време и на нерви :) Кога ќе напишете неколку стотина линии код, гледате дека се грешка, па потоа пак од почеток - секако никој не го сака ова. Во кој програмски јазик ќе се програмира мислам дека е најмал проблем иако ова не е баш работа која може да се занемари. Предноста е кај оние кои знаат повеќе програмски јазици бидејќи ги знаат предностите и недостатоците на секој па во дадена ситуација ќе знаат да го искористат најдобриот избор. Во почетокот, кога почнав да навлегувам во водите на програмирањето кодирав во Pascal, тогаш за мене Pascal беше програмски јазик со кој можев буквално се да искодирам :) толку бев уверен и во себе и во моќта на Pascal. Потоа научив C, овој програмски јазик би го споредил во брзината и перформансите со брза спортска кола, но недостатокот е во тешкото управување со воланот :) За попрости проблеми лесно е да се пишува код во C, но кога ќе наидете на посложени проблеми кои бараат користење на посложени структури и кои имаат потреба од готови библиотеки доаѓа потреба од друг програмски јазик кој ќе ги надмине недостатоците на C, а сепак ќе ја задржи брзината. Погодувате, тоа е C++. Немам баш многу искуство во C++ bидејќи брзо мигрирав од C во Java, но тоа е јазикот кој ми беше алтернатива при решавањето доколку наидев на проблем кој го надминува временскиот лимит во Java. Иста програма напишана во Java и C++ не дава иста брзина на извршување. C++ e далеку побрз. Но сепак Java ми е омилен програмски јазик за програмирање пред се заради неговата едноставност и моќ. Во Java може да се напише буквално се и тоа процесот на кодирање е многу побрз затоа што нуди подршка од многу корисни библиотеки и добри IDE како Eclipse

It's time for a new challenge :)

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

noreply@blogger.com (igormk) — Sat, 17 Jan 2009 20:21:00 +0000

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

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

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

Algoritmi.pdf

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

noreply@blogger.com (igormk) — Wed, 03 Dec 2008 15:46:00 +0000

Транспортна мрежа е ориентиран граф, без циклуси во кој на секое ребро (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!

noreply@blogger.com (igormk) — Mon, 01 Dec 2008 20:54:00 +0000

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

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

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

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

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

noreply@blogger.com (igormk) — Wed, 19 Nov 2008 23:10:00 +0000

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

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


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++;
   }
}

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

noreply@blogger.com (igormk) — Wed, 19 Nov 2008 15:21:00 +0000

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). Нема да навлегувам во понатамошни анализи :)

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

noreply@blogger.com (igormk) — Mon, 17 Nov 2008 20:44:00 +0000

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

Во математиката, веројатноста да се случи еден настан А се претставува како реален број во опсегот од 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 за да се постигне бараниот резултат.

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

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

noreply@blogger.com (igormk) — Sat, 15 Nov 2008 16:53:00 +0000

Евклидов алгоритам за најголем заеднички делител и најмал заеднички содржател. Може да послужи некогаш за натпревари по програмирање, па го постирам овде за да имам брз пристап до него и да го користам 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);
}

Ојлеров циклус

noreply@blogger.com (igormk) — Thu, 04 Sep 2008 01:17:00 +0000

Да се одреди дали еден граф има Ојлеров пат или циклус е лесно, се применуваат две правила.

Граф има Ојлеров циклус ако и само ако е поврзан (кога ќе ги извадиме сите темиња со степен 0) и секое теме има "парен степен".
Граф има Ојлеров пат ако и само ако е поврзан и сите темиња освен две имаат парни степени
Во вториот случај, едно од двете темиња кое има непарен степен мора да биде почетно теме, додека другото е крајното теме.

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

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

Ако темето нема соседи, тогаш го додаваме темето на циклусот и се враќаме
Ако темето има соседи, тогаш правиме листа на сите соседи и нив ги обработуваме (што вклучува нивно бришење од листата на темиња на кои треба да работиме) додека темето нема повеќе соседи
За да процесираме теме, го бришеме реброто помеѓу моменталното теме и неговиот сосед, вршиме рекурзија на соседот, и го додаваме моменталното теме на циклусот

Овој алгоритам работи во O(m + n) време, каде m е бројот на ребра и n е бројот на темиња, ако се чува графот во "листа на соседи".

Литература: USACO

Google Code Jam

noreply@blogger.com (igormk) — Tue, 15 Jul 2008 02:46:00 +0000

Google Code Jam е алгоритамско натпреварување на кое може да учествува секој. Има примамливи награди, а и натпреварот е одлично организиран (претпоставувам бидејќи го организира Google, но до сега не сум учествувал). Значи на 16 јули ќе има квалификациска рунда каде што ќе се одберат најдобрите 500 кои ќе одат понатаму.

Квалификациската рунда ќе трае 24 часа. Во правилата пишува дека ќе има од 4-6 задачи. Оние што ги дадоа за practice рундата ми се интересни, не се баш многу тешки, но за добар успех сепак треба рутина во кодирање.

Им го препорачувам овој натпревар на сите кои што се разбираат од програмирање, и за почетници се разбира. Нема ништо да изгубат, туку само ќе добијат. Јас можеби ќе учествувам, но имам еден технички проблем кој се обидувам да го решам. Таму треба да се работи со датотеки и се чита влез од фајл, и излезот се испраќа до главниот сервер. Е сега не можам да се одлучам во кој програмски јазик да програмирам. Од кога научив Java пред 2-3 месеци заради codefu натпреварот тој ми стана омилен јазик за програмирање, само проблем е што не знам како да работам со датотеки. Втор омилен јазик ми е C++, го знам прилично добро овој јазик, но имам еден проблем кога читам од датотеки. Се надевам во брзо време ќе го решам ова. C го знам и може да ми послужи, но сепак ми е "понапорен" од C++. За Pascal нема ни да зборувам, него го баталив со завршувањето на Светската Олимпијада по Информатика. Значи ако го решам овој технички проблем со читање и запишување во датотеки учествувам на Google Code Jam. Да си ја пробам среќата.

Здраво

noreply@blogger.com (igormk) — Tue, 15 Jul 2008 02:13:00 +0000

Здраво на сите што случајно или намерно ќе налетаат на мојот блог.

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

Инаку овој блог е наменет пред се за објавување на моите размислувања, истражувања, искуства во, околу и надвод од светот на компјутерите. Пред се ќе се фокусирам на алгоритмите како основа на информатиката. Исто така и ќе се осврнувам на новата технологија. Се надевам дека овој блог ќе биде интересно место на Интернет.

Кој сум јас? Јас сум Игор Кулев, студент на ФЕИТ (или како си го викаме електро) прва година, всушност сега завршив прва. Имам искуство во натпревари по информатика и ме интересира компјутерската наука, логиката и вештачката интелигенција најмногу.