[ _Daki_ @ 23.10.2009. 23:26 ] @
sta je algoritam i kako se on moze predstaviti?
unaperd hvala :)
[ X Files @ 24.10.2009. 07:36 ] @
Pogledaj za početak ovde:
http://en.wikipedia.org/wiki/Algorithm
http://sr.wikipedia.org/wiki/Algoritam
[ Sini82 @ 24.10.2009. 10:05 ] @
Algoritam je potpuno specifičan niz koraka koji uvijek daje korektan odgovor.
[ Nedeljko @ 24.10.2009. 17:30 ] @
Algoritam može da radi neograničeno dugo i da ne da odgovor. Pokušavali su matematičari sa konceptom algoritma koji se uvek zaustavlja u konačnom broju koraka, pa nije išlo.
[ Nedeljko @ 25.10.2009. 08:04 ] @
Matematičarima je baš to trebalo, da ne ulazim sada u razloge. Na kraju, ne postoji opšteprihvaćena definicija algoritma (tj. osnovnih koraka u uzračunavanju), ali će se svi matematičari složiti oko toga koji su problemi algoritamski rešivi, a koji ne.

Postoje mnogi takvi formalni sistemi izračunljivosti, kod kojih se osnovni koraci biraju na različite načine, ali se u svima njima mogu rešavati potpuno isti problemi.
[ Sini82 @ 25.10.2009. 13:28 ] @
Nedeljko:
Citat:
Algoritam može da radi neograničeno dugo i da ne da odgovor.

Pod "korektan odgovor" sam mislio da radi ono što se od njega očekuje, e sad koliko dugo, to zavisi od prirode problema koji se rješava.

Možeš li da navedeš primjer algoritma koji radi neograničeno dugo i ne daje odgovor, nisam siguran da sam te u potpunosti shvatio?






[ vlaiv @ 26.10.2009. 07:45 ] @
Code:

while(true);


Recimo? :D

Algoritam bi se mogao definisati na sledeci nacin:

Tacno utvrdjen postupak da se u konacno mnogo, precizno definisanih koraka, za klasu problema i date ulazne
parametre koji precizno opisuju problem u okviru klase
pronadje resenje, ili izda obavestenje da resenje ne postoji ili pak obavestenje da resenje nije pronadjeno u
okviru ulaznih parametara (od koji je u tom slucaju jedan koji opisuje koliko dugo da se trazi pre nego sto
se odustane).

Algoritam se moze zapisati na vise nacina od kojih su neki na primer:

1. Opisno
2. Blok dijagramom operacija
3. Nekim pseudo jezikom

Jednostavnim recima algoritam je nacin kako da resis neki problem. Naravno ne problem stambenog pitanja :D
nego matematicki problem.
[ Nedeljko @ 26.10.2009. 14:55 ] @
Opis pojma algoritma je precizno određen niz koraka koji zavise od nekih ulaznih veličina i koji se za neke ulaze može završiti u konačnom broju koraka i dati konkretan rezultat, a koji za neke ulaze može da se izvršava neograničeno dugo i nikada ne da rezultat.

Program P izračunava funkciju f ako

1. Za sve vrednosti ulaza (x1,...,xn) za koje je funkcija f definisana se završava u konačnom broju koraka i daje rezultat vrednost f(x1,...,xn) funkcije f za te argumente.
2. Za sve vrednosti ulaza za koje funkcija f nije definisana program radi neograničeno dugo.

Za funkciju se kaže da je izračunljiva ako postoji bar jedan program koji je izračunava.

Postoje razni sistemi izračunljivosti, ali svi vode istom skupu izračunljivih funkcija.
[ retard378 @ 01.11.2009. 20:54 ] @
Let us formally define a computational method to be a quadruple (Q,I,O, f),
in which Q is a set containing subsets I and O, and f is a function from Q
into itself. Furthermore f should leave O pointwise fixed; that is, f(q) should
equal q for all elements q of O. The four quantities Q, I, O, f are intended
to represent respectively the states of the computation, the input, the output,
and the computational rule. Each input x in the set I defines a computational

sequence, x0, x1, x2, ... as follows:
x0 = x and Xk+i = f(xk) for k>= 0. (l)
The computational sequence is said to terminate in k steps if k is the smallest
integer for which Xk is in O and in this case it is said to produce the output
Xk from x. (Note that if Xk is in O, so is Xk+i, because Xk+i = Xk in such a
case.) Some computational sequences may never terminate; an algorithm is a
computational method that terminates in finitely many steps for all x in I
.


Knuth
Art of computer programming

[ Nedeljko @ 02.11.2009. 08:35 ] @
Knut jeste veliko ime, ali nisam siguran da bi se ostala eminentna imena složila sa njim oko ovoga.

1. Ovde nije dato nikakvo ograničenje za funkciju f. Šta ćemo sa algoritamski nerešivim problemima.
2. Klasu mehaničkih procedura, koje se završavaju u konačnom broju koraka nije moguće izdvojiti u sledećem smislu: Načiniti programski jezik na kome se mogu predstaviti sve takve procedure i samo one (tj. gde će svaki program biti zaustavljiv) i takav da se može napisati interpreter za njega. Na svim postojećim jezicima je moguće predstaviti sve mehaničke procedure uključujući i one koje nisu zaustavljive, tj. ni za jedan programski jezik nije garantovana zaustavljivost svih programa napisanih na njemu.
[ retard378 @ 02.11.2009. 10:53 ] @
1.funkcija f definise prelaz iz jednog stanja u sledece sto je u opstem slucaju proizvoljno i ne vidim zasto bi trebalo da ima neko ogranicenje
2.slazem se u svakom programskom jeziku mozes da napises program koji traje beskonacno ( whie(1); ) ali to ne govori nista o definiciji algoritma jer programski jezici su samo trenutna tehnologija implementacije algoritama i to sto oni mogu da urade i nesto sire nista ne govori o tome da definicija agoritma ne valja

i da dodam ja nisam pokusao da dam definiciju algoritma vec sam samo odgovorio na temu tako sto sam naveo definiciju iz ipak vodece knjige iz ove oblasti,ako mislis da se druga imena ne bi slozila sa njim mogo bi da das referene za ta neslaganja
u svakom slucaju svako moze da se "ne slozi" sa definicijom i da pod definisanim pojmom smatra nesto sire ili uze od toga sto definicija obuhvata ali je to toliko besmisleno i dovelo bi samo do radjanja milijardu teorija o jednoj stvari
[ Nedeljko @ 03.11.2009. 07:36 ] @
Citat:
retard378: 1.funkcija f definise prelaz iz jednog stanja u sledece sto je u opstem slucaju proizvoljno i ne vidim zasto bi trebalo da ima neko ogranicenje


Pa, problem je u tome što onda takva funkcija prelaza može da bude mehanički neostvariva. Upravo je u tome poenta cele priče. Nisu sve funkcije rekurzivne, već samo one koje se mogu dobiti od inicijalnih rekurzivnih konačnom primenom operatora supstitucije, rekurzije i minimizacije; nisu sve funkcije Tjuring izračunljive, već samo one koje se mogu izračunavati na Tjuringovoj mašini itd. Ako klasa funkcija koja definišu prelaze iz stanja u stanje nemaju nikakvo ograničenje, onda svi problemi ispadoše algoritamski rešivi u jednom koraku.

Sa druge strane, svi programski jezici, koliko god bili različiti, opisuju potpuno istu klasu procedura i izračunljivih funkcija. Slažem se da možemo formalno uvesti pojam algoritma kao one od tih procedura, koje se zaustavljaju za sve ulaze.

Malo ti je bezveze to korisničko ime, ali, to je na kraju tvoja stvar.
[ Nedeljko @ 03.11.2009. 11:01 ] @
Što se tiče Knutovog citata, to ipak nije definicija algoritma, već pojašnjenje čitaocu, dovoljno dobro za praćenje te knjige. U suprotnom ispade sve rešivo u jednom koraku - Neka je uz Knutovu simboliku g:I->O funkcija definisana na sledeći način:

1. Ako niz x=x0,x1,...,xk=y predstavlja izračunavanje po Knutu, onda je g(x)=y.
2. U suprotnom je g(x)=x.

Definiši izračunavanje sa istim skupovima Q,I,O, samo sa funkcijom prelaza g umesto f i dobićeš rešavanje potpuno istog problema u jednom koraku. Dakle, tako ispada da mu nizovi i ne trebaju.

Štaviše, to je "algoritamsko rešenje" za ma koji problem, gde je g(x) željeni izlaz za ulaz x, pa svi problemi ispadoše algoritamski rešivi u jednom koraku.

Neka je Q skup svih ASCII fajlova, I skup svih sintaksno ispravnih programa na nekom programskom jeziku, koji ne prihvataju nikakave ulaze, već su svi podaci upisani u pogram, O skup fajlova koji se sastoje od samo jednog znaka 0 ili 1, onda neka je f(x)=1 ako se program x zaustavlja u konačnom broju koraka, a inače f(x)=0. Funkcija prelaza je taman takva da problem zaustavljanja rešavaš u jednom koraku. Znači, dobio si "algoritam" za rešavanje problema zaustavljanja. Da li bi mogao da ga isprogramiraš?

Knut je inače iz pedagoških razloga umeo da daje u početku približne definicije, pa tek kasnije korektne, ako je potrebno. Inače, bez ikakvih ograničenja za funkciju prelaza ova definicija nema previše smisla

Citat:
retard378: i da dodam ja nisam pokusao da dam definiciju algoritma vec sam samo odgovorio na temu tako sto sam naveo definiciju iz ipak vodece knjige iz ove oblasti,ako mislis da se druga imena ne bi slozila sa njim mogo bi da das referene za ta neslaganja
u svakom slucaju svako moze da se "ne slozi" sa definicijom i da pod definisanim pojmom smatra nesto sire ili uze od toga sto definicija obuhvata ali je to toliko besmisleno i dovelo bi samo do radjanja milijardu teorija o jednoj stvari


Šta znam koja je vodeća. Možda je ta vodeća programerska iz te oblasti. Ima drugih knjiga sasvim drugačije koncepcije iz te oblasti, koje koriste studenti poslediplomskih studija, kao što su na primer

1. "Recursion theory", Joseph Schoenfeld,
2. "Computability", Nigel Cutland

i da ne navodim druge. Mogao bi ti da navedeš bar jednu teoriju gde je strogo zasnovan pojam zaustavljivih procedura nezavisno od opšteg pojma mehaničkih procedura (da ne bude definicija mehaničke procedutre, pa onda specijalan slučaj kada je ona zaustavljiva). Ja znam više sistema izračunljivosti (sistem rekurzivnih funkcija, URM mašine, Tjuringove mašine itd.), gde je obavezno opisan pojam mehaničkih procedura uključujući i nezaustavljive.
[ retard378 @ 03.11.2009. 11:20 ] @
pa za svaki problem ti i mozes da definises funkciju g:I->O tj. za svaki ulaz imas izlaz sto i jeste funkcija
knuth samo govori odekompoziciji tj. o nizu koraka kako do izlaza doci
ti bi teorijski uvek moga imati uz dovoljno memorije tablicu za sve probleme (navodim jos jednom teorijski uz beskonacno mnogo memorije) i sve resio u jednom koraku

takodje knuth nista ne govori o izracunljivosti funkcija ,vec definise algoritam na slican nacin kao konacni automat,tj ti kad dizajniras algoritam ti znas kako iz jednog koraka da predjes u sledeci
on ne razmatra teoriju izracunljivosti vec pokusava da formalno matematicki definise algoritam sto je po mom misljenju i postigao

slazem se da postoje jos mnogo dobrih knjiga,tj. boljih od ovih o teoriji izracunljivosti ali ovde to nije tema ,ova knjiga je o teoriji algoritama sta vise o analizi ciji je ,moras se sloziti , knuth zacetnik i ipak bi trebalo njgovu definiciju uvaziti

mozes videti i primer ispod definicije ako imas knjigu kako on formalno preko uredjenih parova zapisuje algoritam, tj. on nije hteo da koristi neki pseudo jezik ve je hteo da matematicki predstavi algoritme na slican nacin kao konacni automat i dao je nekoliko primera poznatih algoritama u tom zapisu

kao sto takodje mozes da vidis u definiciji on na ovaj nacin definise metod izracunavanja, a potom kaze da je algoritam metod izracunavanja koji se zavrsava u konacnom broju koraka tj. gde je k razlicito od beskonacno
[ Nedeljko @ 03.11.2009. 13:53 ] @
Citat:
retard378: pa za svaki problem ti i mozes da definises funkciju g:I->O tj. za svaki ulaz imas izlaz sto i jeste funkcija
knuth samo govori odekompoziciji tj. o nizu koraka kako do izlaza doci


A šta će mi dekompozicija? Zašto da ne stavim f=g i rešim sve u jednom koraku? Zar je smisao algoritma da ide izokola umesto direktno?

Ne, to je Knutov opis pojma algoritma za čitaoce koji nisu bili sigurni da se to možda ne maže na hleb, da bi mogli da prate nastavak teksta.

Citat:
retard378: ti bi teorijski uvek moga imati uz dovoljno memorije tablicu za sve probleme (navodim jos jednom teorijski uz beskonacno mnogo memorije) i sve resio u jednom koraku


Ma, hajde, molim te. Gde se u toj definiciji pominje memorija?

Citat:
retard378: takodje knuth nista ne govori o izracunljivosti funkcija ,vec definise algoritam na slican nacin kao konacni automat,tj ti kad dizajniras algoritam ti znas kako iz jednog koraka da predjes u sledeci
on ne razmatra teoriju izracunljivosti vec pokusava da formalno matematicki definise algoritam sto je po mom misljenju i postigao


Pa, funkcija je izračunljiva ako postoji mehanička procedura koja je izračunava, tj. zaustavlja se u konačnom broju koraka tačno za one ulazne vrednosti za koje je funkcija definisana i za te ulazne vrednosti na izlazu daje vrednost funkcije u toj tački. Nije šija nego vrat. Definiši algoritam i samim tim si definisao izračunljivost i obrnuto, svakim pristupom definisanju izračunljivosti dobijaš neku definiciju algoritma.

Drugi naziv za teoriju izračunljivosti je teorija algoritama. Treći je teorija rekurzija.

A to koliko je postigao definisanje pojma algoritma se vidi po tome što su mu svi problemi algoritamski rešivi u jednom koraku. Šta sa algoritamski nerešivim problemima i sa algoritamskom složenošću problema (tj. koliko je neki problem moguće efikasno rešavati). Ispade da su svi problemi rešivi, što nije tačno, i štaviše da su rešivi u jednom koraku, što je još manje tačno.

Da, kod Tjuringovih mašina se zna kakva može biti funkcija prelaza. Kod URM mašina se opet zna. Dakle, ne može funkcija prelaza da bude baš bilo šta bez ograničenja.

Citat:
retard378: mozes videti i primer ispod definicije ako imas knjigu kako on formalno preko uredjenih parova zapisuje algoritam, tj. on nije hteo da koristi neki pseudo jezik ve je hteo da matematicki predstavi algoritme na slican nacin kao konacni automat i dao je nekoliko primera poznatih algoritama u tom zapisu

kao sto takodje mozes da vidis u definiciji on na ovaj nacin definise metod izracunavanja, a potom kaze da je algoritam metod izracunavanja koji se zavrsava u konacnom broju koraka tj. gde je k razlicito od beskonacno


OK, on je dokazivao za neke algoritme, kojima treba više od jednog koraka, da su najefikasniji mogući za rešavanje nekog problema. Kako mu se to uklapa u tu definiciju?

Evo, ja ću da definišem funkciju f na sledeći način: f(n)=1 ako postoji beskonačno prirodnih brojeva k, takvih da na poziciji k2+n u zapisu broja stoji poslednja cifra broja k, a inače 0. Da li bi bio ljubazam da mi to isprogramiraš? Nikakav problem nije odvaliti preciznu definiciju funkcije, ali to ne znači da je ona određuje algoritam.
[ Nedeljko @ 03.11.2009. 13:59 ] @
Citat:
retard378: slazem se da postoje jos mnogo dobrih knjiga, tj. boljih od ovih o teoriji izracunljivosti ali ovde to nije tema, ova knjiga je o teoriji algoritama sta vise o analizi ciji je, moras se sloziti, knuth zacetnik i ipak bi trebalo njgovu definiciju uvaziti


Knut začetnik teorije algoritama? Otkad to? Ta knjiga jeste dobra, ali za programere. Bavi se problemima koji jesu algoritamski rešivi i metodama njihovog efikasnog rešavanja i to je to.
[ retard378 @ 03.11.2009. 14:17 ] @
rekao sam da je knut zacetnik ANALIZE algoritama
jos jednom cu reci da on opisuje algoritam kao konacni automat i f je funkcija prelaza iz stanja u stanje

na kraju krajeva kako kod,ja sam jednostavno dao najbolju mogucu definiciju algoritma koju sam naso ,ako se ne slaes sa njom obrati se autoru jer ova rasprava ne vodi nicemu

puno pozdrava
[ Nedeljko @ 03.11.2009. 16:45 ] @
A o kakvoj analizi govoriš?

Ta definicija jeste šuplja, a razlog svakako nije to da Knut ne zna šta je algoritam, već namena u okviru knjige kao celine.

Ako se ta definicija prihvati zdravo za gotovo, onda taj pojam nnije u skladu ni sa dokazima algoritamske nerešivosti i sa teorijom algoritamske složenosti problema. Naravno da Knut to zna kudikamo bolje nego što je napisao, ali namena te knjige nije razglabanje o Tjuringovoj mašini ili URM mašinama ili ne znam čemu. Od mašina, on pominje samo MIX i tu se zna kakva je funkcija prelaza iz stanja u stanje i onda ni definicija nema problem ako se odnosi na konkretnu mašinu gde se zna kako se prelazi iz stanja u stanje.