algoritmi.1ppekovic,
Ova tema je namenjena za sve one programerske probleme, predloge, ideje,...
koje nisu vezani ni za jedan programski jezik.
Paya
algoritmi.2janko,
Skoro sam dobio pismo čije delove citiram, jer mislim da mogu
još nekog zanimati i pitanje i odgovor...
> Nedavno sam radio neki install za neki program čiji je autor
> poodavno u inostranstvu i u okviru toga mi je trebalo prilagođavanje
> poruka rasporedu koji je instaliran na ciljnom računaru. Prvo
> sam mislio da upotrebim već gotove programe za konverziju, ali
> pošto je tu bilo i nekih uslovnih konverzija, napisao sam kod
> koji to vrši. Pri tom sam primenio princip koji sam video u
> tvom juk100.cpp, s tim što sam samu konverziju uradio u
> asembleru kao inline assembly (ostatak programa je urađen u
> C-u). Stvar radi dosta brzo, i kad je ceo install bio gotov,
> izdvojio sam samo taj deo za konverziju jer me zanimalo kako
> se po pitanju brzine odnosi sa programima kakvi su cconv i
> yuras (poskok tad još nije bio javno publikovan). Rezultat je
> bio da je moj program za konverziju između 2-4 puta sporiji od
> Zakovog cconv-a. Ništa čudno, obzirom da je u pitanju C
> program, ali me zanimalo da li se ipak stvar može ubrzati.
> Zato sam program preveo sa MSC-om sa max. optimizacijom i bio
> je za 7-8% brži nego kad je preveden sa BCC. E, sad, tu sam
> stao jer pretpostavljam da kad bi se ceo program napisao u
> asembleru da bi se jako približio cconv-u, ali nemam mnogo ni
> vremena ni živaca da se previše petljam sa asemblerom pa sam
> stao na ovom. Install rutina radi dovoljno brzo, a za lične
> potrebe ionako koristim poskok i cconv.
>
>
> P.S. Planiram i da prepravim taj program za koji sam radio
> install (kad se dokopam celog source-a) tako da radi u skladu
> sa UKRAS-om, pa onaj Install više neće ni biti potreban.
Krenuo si na pogrešnu stranu u ubrzavanju. Konkretno, da bi
znao šta treba da ubrzavaš, moraš da znaš šta je 'usko grlo'
programa. To bi trebalo, kao, da mere profajleri, ali oni koje
sam ja probao, i koliko sam uspeo da ih iskoristim, su dosta
nesavršeni kada se mere perfomanse programa koji imaju
intenzivan I/O.
Ukratko, očigledno da u tvom slučaju sama rutina za konverziju
NIJE usko grlo u programu.
Takođe, ako si slučajno pomislio suprotno, ni Yuras ni Poskok
nisu pisani u asembleru. I jedan i drugi su Turbo Paskal
programi, ni jednog ni drugog NISAM ja pisao, (drugom, čak, nisam
ni video sors) ali sam za oba napisao kratke rutinice koje JESU
u asembleru -- i koje bi trebalo da ubrzaju ono što bi trebalo
da je njima usko grlo -- samu konverziju. Primeti da ni u
jednom ni u drugom I/O operacije NISU pisane u asembleru.
Ovo sve, naravno, NE znači da je moguće napisati brži program
na Turbo Paksalu nego na C-u. Turbo Paskal ima interno
memorijski model koji je po brzini ekvivalentan 'compact'
(a zavisi od konfiguracije TP-a, nekad i 'large') memorijskom
modelu u C-u. Dakle, ako koristiš 'small' ili 'medium'
memorijski model, trebalo bi da ti je ekvivalentan program brži
u C-u. S druge strane, Turbo Paskal koristi interni format
brojeva u pokretnom zarezu, dok C programi (ako se ne varam,
možda može nekako da se promeni emulacioni kod?) uvek rade
unekoliko okrnjenu emulaciju IEEE standarda, pa je moguće da u
aplikacijama koje rade sa takvim brojevima, ako nemaš numerički
koprocesor, TP varijanta radi brže?
Dakle ti si uradio u svom programu, ako sam dobro razumeo
(pomenuo si neke inline assembly rutine) isto ono što sam i ja
u programima koje pominješ.
Međutim, sporije rezultate si dobio verovatno jer su rutine za
rad I/O operacija očigledno sporije od onih koje su primenjene
u pomenutim programima.
Na primer, pošto pominješ C, već sam svojevremno pisao da je
scanf ili fscanf
na primer, naredba koja SVAKI PUT kada se pozove INTERPRETIRA
svoj format string. Naravno, u petlji to može traje primetno...
Ali ni to nije sve. Verovatno u svom programu nisi podešavao
veličnu bafera, što se može učiniti naredbom setvbuf u C-u,
kojom ćeš (potencijalno, SAMO na Dosu) primetno ubrzati svoj
program čak iako koristiš fscanf (koji je ponekad nezamenljiv).
I na kraju, žao mi je što do sada nisam video da je iko
iskoristio pomenute Ukras rutine za C i C++. Možda neko nije
shvatio da te rutine rade i na svakom ANSI C kompajleru, (iako
u zahlavljima to piše?) i nisu isključivo C++ programi iako im
je ekstenzija .cpp?
algoritmi.3dzakic,
Treba mi par funkcija koje ostvaruju 1-1 preslikavanje između skupa
datuma (oblika dd, mm, yyyy) i skupa celih brojeva. žini mi se da je
tako nešto dejanr ostavio u starom pc.prog-u, čini mi se da je se to čak
našlo i u bajtovima lične prirode, ali nikako ne uspevam da pronađem ni
jedno ni drugo (a nisam baš raspoložen da pronalazim toplu vodu). Help!
algoritmi.4bojanp,
> Treba mi par funkcija koje ostvaruju 1-1 preslikavanje između skupa
> datuma (oblika dd, mm, yyyy) i skupa celih brojeva. žini mi se da je
Pogledaj sledeće poruke u ORKA.1 konferenciji: 14.184, 14.186, 14.206.
Pozdrav, Bojan
algoritmi.5dejanr,
program datumi;
{
KONVERZIJE DATUM<--->JULIAN DAY NO
Copyright (C) 1980-1988 Dejan Ristanovic
}
var d,m,g: integer;
function cj (d,m,g: integer): longint;
var gp,izlaz: real;
begin
gp:=g+(m-2.85)/12.0;
izlaz:=int(367*gp)-int(gp)-0.75*int(gp)+d;
izlaz:=int(izlaz)-0.75*int(gp/100);
izlaz:=int(izlaz)+1721115;
cj:=trunc(izlaz);
end;
function day(d,m,g: integer): integer;
begin
day:=(cj(d,m,g)+1) mod 7
end;
procedure jc(jdn: longint; var d,m,y: integer);
var n,c,np,yp,npp,mp: longint;
begin
n:=jdn-1721119;
c:=trunc((n-0.2)/36524.25);
np:=n+c-trunc(c/4);
yp:=trunc((np-0.2)/365.25);
npp:=np-trunc(365.25*yp);
mp:=trunc((npp-0.5)/30.6);
d:=trunc(npp-30.6*mp+0.5);
if mp<=9 then begin m:=mp+3; y:=yp end
else begin y:=yp+1; m:=mp-9 end
end;
begin
repeat
write ('Datum (DD): ');
readln (d);
write ('Mesec (MM): ');
readln (m);
write ('Godina (YYYY): ');
readln (g);
writeln('Julian day = ', cj(d,m,g));
jc(cj(d,m,g),d,m,g);
writeln(d,' ',m,' ',g);
writeln('Dan (0=nedelja): ',day(d,m,g));
until false;
end.
algoritmi.7dzakic,
Znam da se ovo neće svideti mjogiju, ali...
Hvala i tebi i dejanu.
cu
algoritmi.8janko,
Pogledajte ovaj deo teksta iz PGP 2.0 paketa:
> When I was in college in the early seventies, I devised what I
> believed was a brilliant encryption scheme. A simple
> pseudorandom number stream was added to the plaintext stream to
> create ciphertext. This would seemingly thwart any frequency
> analysis of the ciphertext, and would be uncrackable even to the
> most resourceful Government intelligence agencies. I felt so
> smug about my achievement. So cock-sure.
>
> Years later, I discovered this same scheme in several
> introductory cryptography texts and tutorial papers. How nice.
> Other cryptographers had thought of the same scheme.
> Unfortunately, the scheme was presented as a simple homework
> assignment on how to use elementary cryptanalytic techniques to
> trivially crack it. So much for my brilliant scheme.
>
> From this humbling experience I learned how easy it is to fall
> into a false sense of security when devising an encryption
> algorithm.
Zna li neko kako se 'elementarnim tehnikama trivijalno
razbijaju' tako kriptovane datoteke? (MNOGI komercijalni
programi upravo ovako kriptuju datoteke!)
algoritmi.9zormi,
* > A simple pseudorandom number stream was added to the plaintext
* > stream to create ciphertext.
*
* Zna li neko kako se 'elementarnim tehnikama trivijalno
* razbijaju' tako kriptovane datoteke?
Odmah da kažem: ne znam i nisam se time bavio. Možda samo da dam
poneku laičku ideju.
Npr. ako je pseudorandom niz kraći (mnogo puta?) od teksta onda se
ponavlja, pa na odredjenom rastojanju (dužine niza) se dodaju isti
brojevi na slova. Kada se ovo rastojanje ulovi (naravno računarom)
može da se napravi statistika i dovede u korelaciju sa učestanošću
pojavljivanja slova u jeziku ili sl. tj. može da se izvuče na koja
su najverovatnija slova dodati pojedini članovi pseudo slučajnog
niza, što je elementarna tehnika.
Kada je niz mnogo kraći od teksta, ne "ispuca" se ceo pa je statistika
neujednačena i sigurno može nešto da se izvuče.
U svakom slučaju, kakve su sve šifre razbijane ovo mi ne "miriše" na
nešto mnogo sigurno.
algoritmi.10dusanp,
=> Zna li neko kako se 'elementarnim tehnikama trivijalno
=> razbijaju' tako kriptovane datoteke? (MNOGI komercijalni
=> programi upravo ovako kriptuju datoteke!)
Jedino meni logično objašnjenje je da se mogu dekriptovati
fajlovi koji imaju bar neki deo koji standardno izgleda - na
primer kriptovani WP5 tekstovi, koji imaju identične hedere...
Ima li nekog ko nije i sam "smislio" ovaj sistem ??? Ja
svojevremeno jesam, i dalje ga smatram jako pouzdanim.
algoritmi.11dejanr,
>> > Zna li neko kako se 'elementarnim tehnikama trivijalno
>> > razbijaju' tako kriptovane datoteke?
>>
>> Jedino meni logično objašnjenje je da se mogu dekriptovati
>> fajlovi koji imaju bar neki deo koji standardno izgleda - na
>> primer kriptovani WP5 tekstovi, koji imaju identične hedere...
>>
>> Ima li nekog ko nije i sam "smislio" ovaj sistem ??? Ja
>> svojevremeno jesam, i dalje ga smatram jako pouzdanim.
Nisi u pravu. To jest u pravu si za WP tekstove, ali nisi u pravu
ako misliš da probijanje šifra slovo:=(slovo+rnd) mod xxx predstavlja
pomena vredan problem. Ja sam na toj šifri jednom zaradio 100 dem a
jednom izgubio 10,000 dinara (ili tako nešto).
Što se tiče zarade, davno je to bilo, imali neki moji drugari neki
programčić za šifrovanje (tad nije bilo PKZIP-a, PGP-a i tako dalje,
sve se to dešava na nekakvom PDP-ju 11) koji radi otprilike ovako
(ovo nije nikakav konkretan programski jezik ali verujem da će svi
razumeti):
input seed
randomize(seed)
repeat
input txt
for i=1 to length(txt)
print chr((ord(txt(i))+rnd(128)) mod 128); ((())) <-- ovo su
zagrade, dodajte kolko
treba da bude ok izraz
next i
print
until false
Program za dešifrovanje je otprilike isti takav, samo što je umesto
plusa minus i tako to. Elem, genije koji je smislio taj program je
bio silno ubeđen u njegovu sigurnost, i tako su se oni mesecima
"dobacivali" šifrovanim porukama. Ja sam ih duže vreme ubeđivao da
je ta šifra golo go*no i najzad se opkladimo u 100 dem da ću im
probiti šifru za 24 sata (to je u srećno vreme kad sam bio dokon
pa sam mogao da se majem sa takvim glupostima... mada 100 maraka
za sat-dva posla... hmmm... možda bi se i sad našlo vremena ;).
Pokupim ja sve šifrovane poruke koje su stajale po disku, i krenem
otprilike ovako:
1. razne poruke su šifrovane istim ključem (nisu valjda dogovarali
nov ključ za svaku poruku ;)
2. ispišem prva slova iz 100 poruka jedno do drugog
3. svih tih 100 slova je šifrovano istim slučajnim brojem. Recimo ako
je taj broj 15, onda je svako slovo pomereno za 15 mesta u odnosu
na originalnu poziciju.
4. prebrojim koliko među tim prvim slovima ima A, koliko B, itd.
Ispostavi se da najviše ima slova M (recimo!), negde 10 od 100.
Dakle M je verovatno zamena za A, onda je N zamena za B, O zamena
sa C i tako dalje. Malo probam da li to važi (ako se ispostavi da
je drugo slovo po učestanosti č, onda pretpostavka da M menja A nije
dobra, nego je M zamena za neko drugo često slovo, recimo I ili O)
i ispadne da važi, dakle znam da dešifrujem prvo slovo svih poruka
5. Ponovim 2, 3, 4 za drugo, treće, četvrto, peto itd slovo iz 100
poruka i eto dešifrovanih poruka. Naravno da se to 2-4 ne ponavlja
ručno nego pomoću programčeta, ali programče se napiše za cca sat.
Na metod koji sam izmislio sam bio strrrrrašno ponosan, ali sam posle
saznao da je isti još hiljadu osamsto i neke predložio Kerkhofs, a pre
toga nešto slično i Bazeri, Valerio... i da je sve to deo nečega što
se zove "opšti metod za sve polialfabetske kriptograme". Šta da se radi,
nije lako na ovaj svet doneti nešto novo, ali 100 DEM sam uredno inkasirao ;)
Inače, kad sam kod tih kriptografskih metoda, na mene je najjači utisak
ostavila Kerkohofsova ideja kako se određuje dužina ključa kod Vižnerove,
de la Portine, Belazove i sličnih tablica za polialfabetsko šifrovanje.
Tako to komplikovano i neprobojno izgleda a štos je tako prost i tako
genijalan da nemam reči. Koga zanima... Pitalice, januar 1993 :)
Što se tiče gubitka, pre par godina sam u "Galaksiji" objavio jedan
program koji šifruje baš opisanim algoritmom i uz njega sam dao JEDAN
malo duži kriptogram. Dakle, ništa 100 kriptograma šifrovanih istom
šifrom. Ponudio sam 10,000 dinara (ili je možda bilo 1,000, 100,000
ili tako nešto, ko će se razabrati sa tim parama, tek nije bila neka
silna lova) prvome ko reši... rešilo njih 7 ;)
Metod da se razbije takva šifra je za nijansu složeniji (mada je na
sličnu foru) pa me mrzi da ga sad opisujem, možda nekom drugom
prilikom.
Uzgred, kad bih ja hteo da nešto šifrujem a ne bi imao neki stvarno
neprobojan alat kao što je RSA (to dal' je stvarno neprobojan ne
znam(o), ali u našim uslovima garant jeste ;), ja se nikako ne bih
opredelio za neki od polialfabetskih metoda poput opisanog jer isti,
ma koliko da zvuče zaguljeno, jako lako padaju i jer se pri rešavanju
može sjajno primeniti računar. Obavezno bih uzeo neku metodu zamenjivanja
poligrama, makar najobičniju Plejferovu šifru, ili ako me ne bi mrzelo
da se više bakćem sa šifrovanjem onda Delastelovu trifidnu šifru, a onda
bih je nečim sasvim jednostavnim nadšifrovao. Tako bih dobio šifru
koja se, nema sumnje, može probiti i to na način koji je više ili
manje poznat, ali bih bio siguran da "napadač" ima da se naradi k'o
crnac da to probije, da mu trebaju silni ljudski resursi (kod probijanja
tako nadšifrovanih poligramskih šifri računar mu je lepa alatka, ali da
vidi vajdu od njegove brzine... slabo) i dosta vremena. Pa ako baš voli...
algoritmi.12dusanp,
=> Nisi u pravu.
Majkumubožjuimperijalističku! Baš mi se sistem činio
elegantnim :(
algoritmi.13janko,
> Metod da se razbije takva šifra je za nijansu složeniji
> (mada je na sličnu foru) pa me mrzi da ga sad opisujem,
> možda nekom drugom prilikom.
Mene zanima...
algoritmi.14vili,
U knjizi: "C: The Complete Reference", na strani 474 se nalazi
algoritam za Quick sort. Taj algoritam kod mene ne radi, tj. za
vrlo mali broj slucajeva radi, a za ostale daje cudne rezultate.
Da l' je u pitanju greska u knjizi ili sta?
Vili
void quick(item,left,right)
char *item;
int left,right;
{
register int i,j;
char x,y;
i=left;
j=right;
x=item[(left+right)/2];
do {
while (item[i]<x && j<right) i++;
while (x<item[j] && j>left) j--;
if (i<=j){
y=item[i];
item[i]=item[j];
item[j]=y;
i++;
j--;
}
} while (i<=j);
if (left < j ) quick(item,left ,j);
if (i < right) quick(item,i,right);
}
#include <stdio.h>
main(){
char s[80];
printf("enter a string:");
gets(s);
quick(s,0,strlen(s)-1);
printf("the sorted string is: %s\n",s);
}
algoritmi.15prvul,
Ů while (item[i]<x && j<right) i++;
Ů while (x<item[j] && j>left) j--;
Ů▄▄
Mislim da u prvom od ovih redova treba (item[i]<x && i<right)
Ovako se na početku promenljiva i nikada ne pomeri nagore, pa
se sortiranje ubrlja.
algoritmi.16isekulovic,
Da li postoji neki opštepoznati algoritam (da se ne mučim da otkrivam
Ameriku, pa da je još ne otkrijem :) za najkraći put između dve tačke
koje su povezane mrežom različitih puteva. Npr. najkraći put od Zelenog
Venca do Krsta ali da ne idem kroz zgrade ili preko Banovog Brda. Kapirate
šta pitam? Meni je palo napamet za sada jedino prava linija između te dve
tačke pa pratiti puteve koji idu najbliže toj pravoj.
algoritmi.17jtitov,
> Da li postoji neki opstepoznati algoritam (da se ne mucim
> da otkrivam
Uh, malo mi pitanje nije jasno. Inace Operaciona istrazivanja (pitaj
FON-ovce o tom predmetu) resavaju taj problem 'najkraceg puta'. Naravno i
programska podrska postoji.
algoritmi.18kenza,
[;> Da li postoji neki opstepoznati algoritam (da se ne mucim da otkrivam
[;> Ameriku, pa da je jos ne otkrijem :) za najkraci put izmedu dve tacke
[;> koje su povezane mrezom razlicitih puteva. Npr. najkraci put od Zelenog
Mislim da se zove Dijkstra,potrazi pod tim imenom ;)
algoritmi.19zolika,
Elem, kada se već priča o algoritmima: zna li neko neki dobar algo-
ritam (i po mogućnosti jednostavan, tj. neki kongruencioni fazon) kojim bi se
dobijali pseudoslučajni brojevi od 0 do N, gde to N može da bude proizvoljno
veliko? Drugim rečima, da li se može napraviti (tj. da li već postoji) način
generisanja pseudoslučajnih brojeva, ali CELIH pseudoslučajnih brojeva proiz-
voljne tačnosti?
Reći će neko: "Imaš algoritam objavljen u 'Galaksiji' broj 186 ili
tu negde, prepiši ga i rešio si stvar". Da, ali taj algoritam daje slučajne
brojeve između 0 i 1, a ja od svega imam samo CELOBROJNU aritmetiku više-
struke preciznosti, tj. ne mogu da množim MALI realan broj VELIKIM (više
od 100 cifara) celim brojem i da tu onda 'kao nešto dobijem'.
Reći će neko drugi: "Imaš algoritam u DejanRovom fajlu IZAZOV.TXT,
pa analiziraj njega". Jeste, analizirao sam i to, ali kako god da ga prila-
godim, brojevi koje dobijam nisu mi dovoljno pseudoslučajni.
Reći će neko treći: "Šta si toliko zapeo za tu aritmetiku višestruke
preciznosti i slučajne brojeve?" Pa, programiram Miler-Rabinov test za
prostotu brojeva, a tu se radi I sa velikim I sa slučajnim brojevima. Taj
program mi dođe za seminarski...
žekajući pomoć,
Zolika
algoritmi.20spantic,
> Elem, kada se već priča o algoritmima: zna li neko neki
> dobar algo- ritam (i po mogućnosti jednostavan, tj. neki
> kongruencioni fazon) kojim bi se
Najlakše bi bilo da ti dostavim Knutovu rvu knjigu iz serije "The Art Of
Computer Programming" ili bar skripte sa PJMPa 2 na ETF Beograd. Ako niko
ne bude dobar uradićemo tako :)
Ali evo za prvu pomoć, ovo je za praktičnu primenu. Ako ti treba teorija
javljaj da šaljem literaturu.
Mašinski zavistan ( linearno kongrulentni ) generator:
N(i+1) = ( a * N(i) + c ) mod M, 0 <= N(i) < M
M je sekvenca maksimalne dužine.
Za binarnu mašinu je M = 2**B
pa za B = 16 ( šesnaestobitni ) imamo:
a = 31413
c = 13849
B = 32
a = 314159269
c = 907633409
gde su i A i B dobijeni Knutovim postupkom.
algoritmi.21dejanr,
>> Elem, kada se već priča o algoritmima: zna li neko neki dobar algo-
>> ritam (i po mogućnosti jednostavan, tj. neki kongruencioni fazon)
>> kojim bi se dobijali pseudoslučajni brojevi od 0 do N, gde to N
>> može da bude proizvoljno veliko? Drugim rečima, da li se može
>> napraviti (tj. da li već postoji) način generisanja pseudoslučajnih
>> brojeva, ali CELIH pseudoslučajnih brojeva proizvoljne tačnosti?
Problem teorijske prirode je to "proizvoljno veliko". Naime, prilikom
projektovanja kongruencionog generatora slučajnih brojeva koristi se
formula Xn+1=(A*Xn+B) mod N pri čemu najpre treba usvojiti N (najčešće
prema dužini mašinske reči) a onda "računati" A i B. Potom, kada se te
vrednosti usvoje, čitav generator treba testirati nizom testova, pa
prihvatiti ili odbaciti. Dakle, ako se naknadno ukaže potreba za
brojevima *većim* od N, moraš početi sve iz početka.
Kao što vidiš, kongruencioni metod generiše cele brojeve, racionalni
brojevi iz intervala (0,1) dobijaju se kada izračunaš Y=X/N. Tek ti
tu treba floating point.
>> Reći će neko drugi: "Imaš algoritam u DejanRovom fajlu IZAZOV.TXT,
>> pa analiziraj njega". Jeste, analizirao sam i to, ali kako god da
>> ga prilagodim, brojevi koje dobijam nisu mi dovoljno pseudoslučajni.
Taj algoritam sam "pokupio" na predavanjima prof. Joze Dujmovića iz
"Metoda programiranja" (ETF, nekad bilo na petoj godini, sada je
mislim pomereno na neku raniju). Obzirom da se prof. Dujmović godinama
bavi simulacijama a, u okviru njih, i generatorima slučajnih brojeva,
i obzirom da je u okviru istog tog kursa veoma detaljno predavao o
tome kako se neki kongruencioni generator testira, sklon sam da mu
poverujem kada kaže da je taj generator detaljno testirao i da su
mu karakteristike optimalne. Naravno, ako su "lagali" mene onda i
ja "lažem" vas, lično ga nisam testirao.
Jedina stvar koju sam primetio a koju prof. Dujmović nije pomenuo
(ili sam ja taj čas prespavao ;) jeste da se, ako ti ne treba broj
između 1 i N nego recimo između 1 i M pri čemu je M<N, uzimanjem
tih par potrebnih bitova sa *kraja* broja dobija veoma ne-slučajna
sekvenca - brojevi se, ako ništa drugo, smenjuju paran-neparan-paran
-neparan što ne liči mnogo na slučajnost (da nisi ti tako radio?).
Prelistao sam Knutha i tamo je zbilja pomenut takav problem, i
izričito se kaže da te potrebne bitove treba uzimati sa *početka*
(leve strane) psuedoslučajnog broja. Tako je i urađeno u IZAZOV.TXT.
>> Pa, programiram Miler-Rabinov test za prostotu brojeva, a tu se
>> radi I sa velikim I sa slučajnim brojevima. Taj program mi dođe
>> za seminarski...
Obzirom da je to verovatno ozbiljnije od nekog igranja sa programima,
bojim se da ti nema druge nego da prelistaš literaturu. A mesto od
koga možeš lepo da počneš je D.E.Knuth, "The Art of Computer Programming",
druga knjiga. Veliki prostor je posvećen generatorima slučajnih brojeva,
tekst je na prvi pogled malo "težak" ali se u stvari sasvim lepo može
čitati (kada naučiš da mnogo komplikovane delove preskočiš ;). Svakako
je i kasnije bilo mnogo radova na ovu temu, ali verujem da je bilo koji
od njih teško mogao da prođe bez referenciranja Knutha kao nekakve
osnove. Uzgred, kongruencioni generatori nisu jedini na svetu, možda
ćeš se odlučiti da probaš sa nekim drugim metodom.
Kada smo već kod ove tematike, da pomenem i ja dva problema koji me
zanimaju, premda ne verujem da će neko biti raspoložen da ih reši ;)
1. Recimo da imamo kongruencioni generator pseudoslučajnih brojeva
Xn+1=(AXn+B) mod N i da nam je N poznato a A, B i X0 nisu. Ali,
dato nam je "nekoliko" slučajnih brojeva iz tog niza, naravno
ne u punoj dužini nego svedeni na neki interval, recimo ako je
N=2^32 data su nam po dva najviša bita svakog od prvih 200 elemenata
niza. Na osnovu toga treba odrediti A, B i X0. Zanimljivo je da
Knuth pominje ovaj problem u okviru zadataka za rešavanje na kraju
poglavlja uz "koeficijent složenosti" koji odgovara semestralnom
radu (eto ideje! :) No, kada okrenete rešenje ;) tamo piše "to se
može uraditi relativno lako, 150 brojeva je dosta za "razbijanje"
32-bitnog generatora, pogledajte moj rad "taj i taj" koji će
uskoro biti objavljen". Slično sam i ja prošao kada sam isto pitanje
postavio ovde, neko od matematičara kaže "može to da se uradi" ali
ne reče KAKO :)
2. Projektovati generator (teško da će biti kongruencioni) koji generiše
uniformno raspoređeni pseudoslučajan broj iz intervala [0,+beskonačno).
Neka radi koliko treba (ako je nužno i milion godina, dakle pitanje
je teorijsko a ne praktično), i neka mi generiše takav broj. Da li
je to uopšte moguće?
algoritmi.22bradenkovic,
>Masinski zavistan ( linearno kongrulentni ) generator:
> N(i+1) = ( a * N(i) + c ) mod M, 0 <= N(i) < M
> M je sekvenca maksimalne duzine.
> Za binarnu masinu je M = 2**B
> pa za B = 16 ( sesnaestobitni ) imamo:
> a = 31413
> c = 13849
> B = 32
> a = 314159269
> c = 907633409
> gde su i A i B dobijeni Knutovim postupkom.
Ima malih ispravki, najpre u nazivu. Navedeni generator se zove mesani
kongruentni.
Najverovatnije da ce siri auditorijum interesovati da procita malo vise
detalja o generatorima pseudoslucajnih brojeva, pa pre nego sto napisem
nesto o najsire koriscenom multiplikativnom linearnom kongruentnom
generatoru, nije lose da najpre definisemo osnovne pojmove o
kongruentnim brojevima:
Brojevi Z(i-1) i Z(i) su kongruentni po modulu m ako je njihova
razlika deljiva sa m bez ostatka, sto se zapisuje sa: Z(i)=Z(i-1) mod m ;
Prema tome multiplikativni kongruentni generator je definisan izrazom:
Z(i)=(a*Z(i-1)) mod M
gde je: a - multiplikator i odredjuje se po obrascu 8j+-3 (j=1,2,3,4...)
Z(0)=1,3,5,7.... - seme generatora (seed);
Maksimalna moguca duzina niza bez ponavljanja je: Nmax = m - 1;
Zato se kod binarnih masina uzima m=2^(b-1)
gde je: b - duzina masinske reci u bitovima (najvisi bit predstavlja znak)
Pri takvim uslovima u zavisnosti od izabranog multiplikatora dobija
se najduza sekvenca bez ponavljanja u intervalu m/4 <= Nmax <=m-1
Duzina niza i kvalitet generatora zavise iskljucivo od duzine masinske
reci i multiplikatora. S obzirom da je duzina masinske reci obicno
fiksirana na 4 bajta, kvalitet generatora iskljucivo zavisi od izabranog
multiplikatora. I dan danas se pojavljuju radovi gde autori tvrde da su
pronasli multiplikator koji obezbedjuje bolju statistiku od poznatih u
literaturi. Navedene reference (Knut) su odavno popljuvane (jos dok sam
ja bio djak) i navedene kao primer dokle moze da nas dovede (ne ova
visoka hiperinflacija) nego siroka primena nepouzdanih generatora.
Takodje je popljuvan i IBM-ov generator iz SSP-a i to jos crnje i gore.
Na osnovu prakse od nekoliko godina ratovanja sa generatorima slucajnih
brojeva, mogu da kao najednostavnije ali sigurno resenje preporucim
portabilni generator sa uniformnom raspodelom (poznat kao UNIRAN) koji
se pojavio 1980 godine. Ako ima zainteresovanih mogu da obezbedim kopiju
rada iz casopisa Simulation.
Inace kod kongruentnih generatora najveci problem je kako realizovati
modulo deljenje sa sto manje masinskih operacija. Jos pedesetih godina
bistri programeri su se dosetili kako da iskoriste neprijavljivanje
greske za integer overflow i naprave vrlo jednostavan emulator za modulo
delenje.
Napomena: rezultat modulo delenja je ostatak od celobrojnog delenja dva broja
Program SlucajanBroj;
Var Z,m : longint;
Procedure Uniform(var Randu: longint);
Begin
Randu := Randu * m; If Randu < 0 then Randu:= Randu + m + 1;
End;
Begin
Z := 1; m := 1220703125;
Uniform(Z); Writeln(Z)
end.
Ukoliko je prilikom mnozenja Randu * m rezultat pozitivan, tada se taj
pozitivan broj uzima kao ostatak celobrojnog delenja sa m, u suprotnom
je doslo do prekoracenja pa je bit znaka setovan. Rezultat modulo
delenja je sada zbog setovanog bita znaka negativan. Da bi ga
konvertovali u pozitivan, u skladu sa zapisom celog broja u obliku
dvostrukog komplementa, dobijenom negativnom broju dodajemo m + 1.
Kao sto vidite vrlo kvalitetan generator slucajnih brojeva moze se
napisati iz dve naredbe koje staju u jedan programski red. To nije
nikakva nauka. Najveca nauka je kako odabrati multiplikator.
Takodje se zbog razlicitog nacina predstavljanja celih i realnih brojeva
u racunaru kao problem javlja i nacin preslikavanja slucajnog broja iz
celobrojnog domena (integer) u domen racionalnih brojeva (real) tako da
se gustina iz jednog domena ekvivalentno preslika na drugi bez
nagomilavanja na granicama ili unutar intervala za koji generisemo
slucajan broj npr: [0,1).
Pozdrav Boza.
algoritmi.23bradenkovic,
Daklem dosao sam do zakljucka da ne valja u sitne sate pisati duge poruke.
Mogu mangupi posle da zajebavaju. Evo svecano se obavezujem da vise necu.
U poruci 1.22 ima jedna greska. Zaboravio sam da metnem multiplikator.
To sam primetio tek kad sam procitao poruku. Ovde je ispravljen pseudo kod.
Program SlucajanBroj;
Var a,Z,m : longint;
Procedure Uniform(var Randu: longint);
Begin
Randu := Randu * a; If Randu < 0 then Randu:= Randu + m + 1;
End;
Begin
Z := 1; a := 1220703125; m:= 2147483647;
Uniform(Z); Writeln(Z)
end.
algoritmi.24janko,
> Duzina niza i kvalitet generatora zavise iskljucivo od
> duzine masinske reci i multiplikatora. S obzirom da je
> duzina masinske reci obicno fiksirana na 4 bajta, kvalitet
> generatora iskljucivo zavisi od izabranog multiplikatora.
> I dan danas se pojavljuju radovi gde autori tvrde da su
> pronasli multiplikator koji obezbedjuje bolju statistiku
> od poznatih u literaturi. Navedene reference (Knut) su
> odavno popljuvane (jos dok sam ja bio djak) i navedene kao
> primer dokle moze da nas dovede (ne ova visoka
> hiperinflacija) nego siroka primena nepouzdanih
> generatora.
Ti si takođe bacio ljudima prašinu u oči. Prvo, pošto je čisto
multiplikativan, tvoj generator se jako lepo ZAKUCA u nulu, u
prvom pogodnom trenutku. ;)
Drugo, to što je neko pronašao neku zgodnu konstantu za 32 bita
ne znači da Knut nije bio u pravu. žovek je dao razne metode i
načine KAKO napraviti generator. Nije rekao: 'moja konstanta za
32 bita je najbolja.' On je matematičar. :)
Treće, ono što Zoliki treba je upravo NAžIN kako da napravi
generator koji će da radi sa znatno VIŠE od 32 bita!
Ja (napamet, možda ima i nešto bolje) Zoliki preporučujem neki
aditivni generator slučajnih brojeva, za koje mu ne treba
određivanje egzotičnih konstanti, i, usto, ne zavise od broja
bita broja -- lako će napraviti neki za broj bita koji njemu
treba.
Referenca: Knut, druga knjiga The Art...
algoritmi.25janko,
> Taj algoritam sam "pokupio" na predavanjima prof. Joze
> Dujmovića iz "Metoda programiranja" (ETF, nekad bilo na
> petoj godini, sada je
> Jedina stvar koju sam primetio a koju prof. Dujmović nije
> pomenuo (ili sam ja taj čas prespavao ;) jeste da se, ako
> ti ne treba broj između 1 i N nego recimo između 1 i M pri
> čemu je M<N, uzimanjem tih par potrebnih bitova sa *kraja*
> broja dobija veoma ne-slučajna sekvenca - brojevi se, ako
> ništa drugo, smenjuju paran-neparan-paran -neparan što ne
> liči mnogo na slučajnost (da nisi ti tako radio?).
Osim što to lepo pominje Knut u knjizi, kod nas je to pominjao
i Laslo na vežbama, a Laslo to zna odavno, jer je to ilustrovao
pomoću printauta koje je napravio još na PDP-11. Verovatno
nisi išao na vežbe, već samo na predavanja. ;))
> 2. Projektovati generator (teško da će biti kongruencioni)
> koji generiše uniformno raspoređeni pseudoslučajan broj iz
> intervala Š0,+beskonačno). Neka radi koliko treba (ako je
> nužno i milion godina, dakle pitanje je teorijsko a ne
> praktično), i neka mi generiše takav broj. Da li je to
> uopšte moguće?
Odgovoriću ti rečenicom iz tvoje poruke ;)
> Problem teorijske prirode je to "proizvoljno veliko".
Hoću da kažem, +beskonačno se može predstaviti na računaru, ali
se opseg 0.. +beskonačno NE MOčE raspodeliti uniformno na
računaru, sve dok nemamo beskonačno veliku mantisu i beskonačno
veliki eksponent na raspolaganju. Problem si zadao kao da nisi
familijaran sa računarskom reprezentacijom brojeva ili nikada
nisi slušao numeričku analizu. :(
algoritmi.26zkehler,
Ŕ> Elem, kada se već priča o algoritmima: zna li neko neki
Ŕ> dobar algo- ritam (i po mogućnosti jednostavan, tj. neki
Ŕ> kongruencioni fazon) kojim bi se
Ŕ
Ŕ Najlakše bi bilo da ti dostavim Knutovu rvu knjigu iz serije
Ŕ "The Art Of Computer Programming" ili bar skripte sa PJMPa 2 na
Ŕ ETF Beograd. Ako niko ne bude dobar uradićemo tako :)
čiveo J. Dujmović, koji je imao i dobrih strana :) spanticu, zar ne
stoji još uvek na ETF-u u Oglasima fajl sa nekoliko generatora slučajnih
brojeva?
Zolika, imam "The Art of..." od Knutha i "The Art of Numerical
Computing" od tri autora. Možeš da kopiraš, ako želiš.
ZK
algoritmi.27bradenkovic,
> Ti si takode bacio ljudima prasinu u oci. Prvo, posto je cisto
> multiplikativan, tvoj generator se jako lepo ZAKUCA u nulu, u
> prvom pogodnom trenutku. ;)
Polako mladi gospodine,
nije bas tako kako ti se cini. Da si malo ozbiljnije pogledao formule
>>Z(i)=(a*Z(i-1)) mod M
>>gde je: a - multiplikator i odredjuje se po obrascu 8j+-3 (j=1,2,3,4...)
>> Z(0)=1,3,5,7.... - seme generatora (seed);
>>
>>Maksimalna moguca duzina niza bez ponavljanja je: Nmax = m - 1;
>>Zato se kod binarnih masina uzima m=2^(b-1)
>>gde je: b - duzina masinske reci u bitovima (najvisi bit predstavlja znak)
Video bi da su seme (i dobijena sekvenca slucajnih brojeva) pozitivni
neparni brojevi. Multiplikator je takodje pozitivan neparan broj. Da bi
se generator "zakucao" potrebno je da je rezultat celobrojnog delenja
modula sa multiplikatorom pozitivan neparan broj. Pogodnim izborom
multiplikatora (8j+-3) j=1,2,3,4.. obezbedjuje se da se takav slucaj
nikada ne desi.
Prema tome, nema nikakvog bacanja prasine u oci. Sve funkcionise
besprekorno.
>Drugo, to sto je neko pronasao neku zgodnu konstantu za 32 bita
>ne znaci da Knut nije bio u pravu. Covek je dao razne metode i
>nacine KAKO napraviti generator. Nije rekao: 'moja konstanta za
>32 bita je najbolja.' On je matematicar. :)
Coveku niko ne spori da je lepo sto je dao pregled nacina kako napraviti
generator, cak stavise to je sa obrazovne strane vrlo korisno. Medjutim
kad neko proba da u profesionalne svrhe (recimo simulacija sistema sa
vise mesta opsluzivanja sa duzim redovima cekanja) koristi takav
generator, tada njegove statisticke nesavrsenosti obicno dovode do toga
da se redovi cekanja znatno produze. S vremena na vreme se na
simpozijumima i casopisima pojavi neko ko neoprezno kao referencu za
multiplikator navodi Knut-a. Onda ga drustvo sa zadovoljstvom slozno
popljuje. Ja sam eto sa svoje strane hteo da ukazem na tu pojavu.
> Trece, ono sto Zoliki treba je upravo NACIN kako da napravi
> generator koji ce da radi sa znatno VISE od 32 bita!
Da bi napravio generator sa vise od 32 bita potrebno je da zna kako
funkcionise generator sa 32 bita. Ako je mangup, ona dva reda programa
ce prosirii sa jos dva reda i par promenljivih i napraviti generator od
64 bita. Pretpostavljam da je Zoliki za njegov rad generator sa 4 bajta
dovoljan. Pri generisanju slucajnog broja glavni problem je postizanje
odgovarajuce rezolucija generatora kao i odgovarajuci statisticki
kvalitet. U svakom slucaju da bi Zoliki pomogli, on mora da kaze u kojim
granicama hoce slucajan broj, sa kojom rezolucijom i kakvim statistickim
kvalitetom. E onda cemo da prekopamo ormane da vidimo sta su drugi
radili da ne izmisljamo toplu vodu.
>Ja (napamet, mozda ima i nesto bolje) Zoliki preporucujem neki
>aditivni generator slucajnih brojeva, za koje mu ne treba
>odredivanje egzoticnih konstanti, i, usto ne zavise od broja
>bita broja -- lako ce napraviti neki za broj bita koji njemu
>treba.
U strucnim krugovima na osnovu teorijskih i empirijskih istrazivanja
vlada misljenje da aditivni generatori imaju vrlo lose statisticke
performanse. Zato se jos jedino koriste u obrazovanju da deca vide da i
tako moze. A odredjivanje parametara za aditivni generator je vece
bajanje nego kod multiplikativnog generatora ali sa neizvesnijim
posledicama po statisticki kvalitet. E sad ako Zoliki treba neki
generator da bi testom dokazao da nije bas najbolji, onda je aditivni
generator za njega bas po meri.
Pozdrav
Boza.
algoritmi.28dejanr,
>> Hoću da kažem, +beskonačno se može predstaviti na računaru, ali
>> se opseg 0.. +beskonačno NE MOčE raspodeliti uniformno na
>> računaru, sve dok nemamo beskonačno veliku mantisu i beskonačno
>> veliki eksponent na raspolaganju. Problem si zadao kao da nisi
>> familijaran sa računarskom reprezentacijom brojeva ili nikada
>> nisi slušao numeričku analizu. :(
Zašto ne bi mogao? Naime, slučajan broj iz intervala [0,+beskonačno)
je konačan broj, može da ima 10^10^10^10 itd cifara, ali je i dalje
konačan broj. Dakle, može se predstaviti u okviru memorije koja
je dovoljno velika. Najzad, nek se štampa na papiru, cifru po cifru.
Evo jednog programa koji generiše pseudoslučajan broj iz intervala
[0,+beskonačno). Samo je mali problem što raspodela nije uniformna,
ali broj svejedno može da ispadne proizvoljno veliki:
repeat
print rnd(10);
until rnd(1000)<>1
Nema to veze sa računarskom reprezentacijom brojeva, to je pitanje
imaginacije :)
algoritmi.29dejanr,
>> zar ne stoji još uvek na ETF-u u Oglasima fajl sa
>> nekoliko generatora slučajnih brojeva?
Ne da ne stoji nekoliko generatora slučajnih brojeva,
nego ne stoje ni sami OGLASI ;) Ukinuto "zbog zloupotreba".
algoritmi.30zolika,
>> Treće, ono što Zoliki treba je upravo NAžIN kako da napravi
>> generator koji će da radi sa znatno VIŠE od 32 bita!
Tačno, Janko, TO je ono što mi ne da mira... :-)))))
>> Ja (napamet, možda ima i nešto bolje) Zoliki preporučujem neki
>> aditivni generator slučajnih brojeva, za koje mu ne treba
>> određivanje egzotičnih konstanti, i, usto, ne zavise od broja
>> bita broja -- lako će napraviti neki za broj bita koji njemu
>> treba.
>> Referenca: Knut, druga knjiga The Art...
Kod nas na faksu nabaviše SAMO treću knjigu, gledali smo bibliotekarka
i ja zajedno sve signature...
algoritmi.31zolika,
>> Kao što vidiš, kongruencioni metod generiše cele brojeve, racionalni
>> brojevi iz intervala (0,1) dobijaju se kada izračunaš Y=X/N. Tek ti
>> tu treba floating point.
Odustajem, jer nemam floating-point aritmetiku (a i ne treba mi).
>> sekvenca - brojevi se, ako ništa drugo, smenjuju paran-neparan-paran
>>- neparan što ne liči mnogo na slučajnost (da nisi ti tako radio?).
Nisam tako radio, nešto sam muvao sa onim tvojim generatorom, ali
bez ozbiljnijih rezultata... :-(((
>> Obzirom da je to verovatno ozbiljnije od nekog igranja sa programima,
>> bojim se da ti nema druge nego da prelistaš literaturu. A mesto od
>> koga možeš lepo da počneš je D.E.Knuth, "The Art of Computer
>> Programming", druga knjiga. Veliki prostor je posvećen generatorima
>> slučajnih brojeva,
OK, OK, ubedili ste me svi: počeću od Knuth-a i njegove "Umetnosti...",
drugi tom. Je l' TAKO TREBA???? :-))))
algoritmi.32robert,
<:> stoji još uvek na ETF-u u Oglasima fajl sa nekoliko generatora
Oglasna tabla je već poooduže ukinuta!
algoritmi.33spantic,
> čiveo J. Dujmović, koji je imao i dobrih strana :)
> spanticu, zar ne stoji još uvek na ETF-u u Oglasima fajl
> sa nekoliko generatora slučajnih brojeva?
Kao što Dejan lepo reče nema OGLASa. A pošto ne želim da i mene ukinu
nema ni tih listinga pošto je Joza to zabranio :)
Zbilju na stranu, veoma bih voleo da se dokopam tih listinga. Ili još
bolje ako neko ima generator pseudoslučajnih brojeva na ADA :) Nije
problem ali ako je neko već bio dobar :) Simuliram vreme odziva
telefonske centrale sa njim. Mislim da kao granice ipak neću staviti
vreme odziva NAŠIH centrala ;)
algoritmi.34spantic,
> literaturi. Navedene reference (Knut) su odavno popljuvane
Pa ni sam Knut nigde ne tvrdi da su sjajni. Reč je o teoriji algoritama
pseudoslučajnih brojeva. E sad, ako neko pogreši pa se prevari... :) Ali
koliko sam razumeo Zoliku on je tražio nešto ovako, a pošto sam žurio,
dao sam osnovu bez teorije, mada sam verovatno trebao i više :)
algoritmi.35janko,
> nije bas tako kako ti se cini. Da si malo ozbiljnije
> pogledao formule
>>> Z(i)=(a*Z(i-1)) mod M
>>> gde je: a - multiplikator i odredjuje se po obrascu
>>> 8j+-3 (j=1,2,3,4...) Z(0)=1,3,5,7.... - seme
>>> generatora (seed);
> Video bi da su seme (i dobijena sekvenca slucajnih
> brojeva) pozitivni neparni brojevi. Multiplikator je
> takodje pozitivan neparan broj. Da bi se generator
> "zakucao" potrebno je da je rezultat celobrojnog delenja
> modula sa multiplikatorom pozitivan neparan broj. Pogodnim
> izborom multiplikatora (8j+-3) j=1,2,3,4.. obezbedjuje se
> da se takav slucaj nikada ne desi.
>
> Prema tome, nema nikakvog bacanja prasine u oci. Sve
> funkcionise besprekorno.
Hvala na objašnjenju. Izvinjavam se na iskazanim sumnjama, ali
drugačije ne bih saznao ove detalje, jer ih nisi napisao u
svojoj prvoj poruci. Imam još pitanja:
DA LI SVAKI MULTIPLIKATOR oblika 8j+-3 ima dobre osobine?
Ako ne, kojim postupkom odrediti neki drugi multiplikator, osim
onog koji si ti dao? (Ovo pitam jer si istakao da su oni Knutovi
postupci pogrešni, a postupak nam je ipak bitniji od jedne
konstante. A ako znamo postupak, lako ćemo i Zoliki isporučiti
jedan primerak dobrog generatora.)
I, da, koje su glavne slabosti mešovitih LK generatora
dobijenih Knutovim postupkom (konkretno, onakvog kakvog je
prikazao spantic) u odnosu na generator koji si nam prikazao?
algoritmi.36janko,
> 2. Projektovati generator (teško da će biti kongruencioni)
> koji generiše uniformno raspoređeni pseudoslučajan broj iz
> intervala Š0,+beskonačno). Neka radi koliko treba (ako je
> nužno i milion godina, dakle pitanje je teorijsko a ne
> praktično), i neka mi generiše takav broj. Da li je to
> uopšte moguće?
>>> Hoću da kažem, +beskonačno se može predstaviti na
>>> računaru, ali se opseg 0.. +beskonačno NE MOčE
>>> raspodeliti uniformno na računaru, sve dok nemamo
>>> beskonačno veliku mantisu i beskonačno veliki eksponent
>>> na raspolaganju. Problem si zadao kao da nisi
> Zašto ne bi mogao? Naime, slučajan broj iz intervala
> Š0,+beskonačno) je konačan broj, može da ima 10ž10ž10ž10
> itd cifara, ali je i dalje konačan broj. Dakle, može se
> predstaviti u okviru memorije koja je dovoljno velika.
> Najzad, nek se štampa na papiru, cifru po cifru.
>
> Evo jednog programa koji generiše pseudoslučajan broj iz
> intervala Š0,+beskonačno). Samo je mali problem što
> raspodela nije uniformna, ali broj svejedno može da
> ispadne proizvoljno veliki:
>
> repeat
> print rnd(10);
> until rnd(1000)<>1
>
> Nema to veze sa računarskom reprezentacijom brojeva, to je
> pitanje imaginacije :)
žekao sam nekog matematičara da se javi, ali, izgleda da ću
morati sam da pišem o stvarima koje mi nisu uža specijalnost (i
rizikujem da ne budem u pravu).
Malo sam razmišljao o tvojoj i svojoj poruci. Prvo, moj zahtev
za beskonačnom mantisom NE stoji. Mantisa sasvim mirno može
biti i VRLO konačna. S druge strane, imam utisak da je
beskonačni eksponent neophodan. (I to ne u tom smislu da se
ne može ispisati. Neka i pretpostvimo da imamo printer sa
beskonačnim papirom. Nije u tome problem.)
Pogledaj opet svoj program:
> repeat
> print rnd(10);
> until rnd(1000)<>1
Svaki nama poznati generator RND ima svoju periodu. Posle te
periode se brojevi ponavljaju. U gornjem primeru, maksimalna
veličina broja je određena periodom generatora. Tako da ti
NIKAD ne dobijaš brojeve iz (.0..+oo .) već iz daleko užeg
(daleko užeg od beskonačnosti ;) opsega (koji zavisi od
generatora koga koristiš).
(Da napomenem onima koji nisu razumeli: Dejan ovde koristi
rnd(n) kao oznaku generatora koji daje cele slučajne brojeve u
opsegu 0..n-1)
Sad zamisli da si, umesto da generišeš samo cifre broja, ovakav
postupak primenio na eksponent (za koji smo zaključili da je
bitniji). Opet, i tako ćeš dobijati brojeve iz daleko užeg
opsega od onog beskonačnog. (Beskonačnost je tako velika ;)
Kako bi tvoj program davao dobre rezultate? Ovako:
> repeat
> print rnd(10);
> until rnd(+oo)<>1
I šta sad? Da bismo dobili generator koji daje brojeve iz
opsega 0..+oo moramo da imamo generator koji daje brojeve iz
opsega 0..+oo. ;)
algoritmi.37zolika,
Vidim da se Zolika intenzivno pominje u vašim porukama (toliko me nisu
pominjali ni kada sam prodavao XT računar :-)) ), pa da obrazložim:
>> Trece, ono sto Zoliki treba je upravo NACIN kako da napravi
>> generator koji ce da radi sa znatno VISE od 32 bita!
Tačno, interesuje me KAKO da napravim (ili da iskoristim neki od
postojećih) generator slučajnih brojeva koji će davati slučajne prirodne
brojeve od 0 do N, gde to N može biti proizvoljno veliko. Ajd' da ne kaže-
te "A koliko je to veliko VELIKO?", neka bude na pr. 2^1000.
>> 64 bita. Pretpostavljam da je Zoliki za njegov rad generator sa 4 bajta
>> dovoljan.
Ne, Zoliki nije dovoljan generator sa 4 bajta. Treba mu neki generator
koji će davati brojeve čija reprezentacija ima više bajtova od 4.
>> U svakom slucaju da bi Zoliki pomogli, on mora da kaze u kojim
>> granicama hoce slucajan broj, sa kojom rezolucijom i kakvim statistickim
>> kvalitetom. E onda cemo da prekopamo ormane da vidimo sta su drugi
>> radili da ne izmisljamo toplu vodu.
Zolika je rekao granice generatora, i hteo bi da su brojevi što
ravnomernije raspoređeni u tom intervalu. Beše li to uniformna raspodela
(još nisam polagao Verovatnoću i statistiku, pa mi nemojte zameriti).
>> posledicama po statisticki kvalitet. E sad ako Zoliki treba neki
>> generator da bi testom dokazao da nije bas najbolji, onda je aditivni
>> generator za njega bas po meri.
Zolika uopšte neće da se upušta u ocenjivanje generatora slučajnih broje-
va i njihovih karakteristika. Njemu generator treba samo kao SREDSTVO, tj.
ALAT za problem koji treba da reši. Naime, kao što je poznato, za Miler-
Rabinov test prostote nekog broja treba izabrati SLUžAJAN broj u intervalu
od 0 do N-1, gde je N uneti broj.
Dakle, bilo bi dobro kada bi neko predložio takav generator slučajnih
brojeva koji bi se "automatski" (koliko je to moguće) prilagođavao intervalu
brojeva, koji je poznat kada korisnik unese broj N čiju prostotu treba pro-
veriti. Zolika će (bar koliko ga poznajem) isprogramirati takav generator,
ako sazna postoji li fazon da se generator prilagodi gornjoj granici. To zna-
či da N može da bude 13, 98457694856749501, 84787, 2674537, sve zavisi od
toga šta korisnik unese.
Nadam se da je Zolika bio dovoljno jasan. Ako nije, slobodno pitajte,
objasniće koliko to bude bilo u njegovoj moći.
algoritmi.38bradenkovic,
> DA LI SVAKI MULTIPLIKATOR oblika 8j+-3 ima dobre osobine?
Jok. To se uglavnom odredjuje empirijski i tu je najveci problem. Izbor
8j+-3 je stavljen da se generator nikako ne zaglupi. U opstem slucaju
dozvoljen je izbor bilo kog multiplikatora koji pomnozen bilo kojim
neparnim brojem daje proizvod razlicit od modula. Postoji neka tanana
teorija koja se oslanja na preslikavanja definisana operacijom modulo
delenja i morfizme prilikom mnozenja nenegativnih celih brojeva, koja
daje odgovor u kojim oblastima treba traziti dobar multiplikator ali su
rezultati dosta siroki tako da su u praksi neupotrebljivi. Ceo posao se
svodi na sac bod metod. Osacuje se multiplikator (Na osnovu neke
kvaziteorije), urade se statisticki testovi i uporede sa poznatim
rezultatima, pa ako je bolje onda se objavljuje da i drugi mogu da
koriste. Dosta se na tom polju radilo tako da postoje testirani dosta
dobri multiplikatori. Prilicno dobar multiplikator dat je u [3],
a=630360016.
>Ako ne, kojim postupkom odrediti neki drugi multiplikator, osim
>onog koji si ti dao? (Ovo pitam jer si istakao da su oni Knutovi
>postupci pogresni, a postupak nam je ipak bitniji od jedne
>konstante. A ako znamo postupak, lako cemo i Zoliki isporuciti
>jedan primerak dobrog generatora.)
Nisu postupci pogresni nego su rezultati tih postupaka losiji od nekih
novijih koji su dobijeni empirijskim istrazivanjima. E ako je neko
empirijski odredio da nesto bolje funkcionise, ne postoji razlog da se
to ne koristi.
>I, da, koje su glavne slabosti mesovitih LK generatora
>dobijenih Knutovim postupkom (konkretno, onakvog kakvog je
>prikazao spantic) u odnosu na generator koji si nam prikazao?
Problem je u neujednacenim statistickim performansama za razlicite
opsege generisanih slucajnih brojeva. Vise detalja mogu se naci u
navedenoj literaturi. Ako nekoga interesuje, moze dobiti radove da
kopira, najbolje subotom kad svrati u klub (preko ppekovica).
LITERATURA:
1. Fishman G.S and Moroe L.R,
"A statistical evaluation of multiplicative congruential generators
with modulus 2^31 -1", Tehnical report 78-11, University of North
Carolina at Chapel Hill, (1980).
2. Fishman G.S and Moroe L.R,
"In search of correlation in multiplicative congruential generators
with modulus 2^31 -1", Tehnical report 80-5, University of North
Carolina at Chapel Hill, (1980).
3. Ken Marse and Stephen D. Roberts,
"Implementing a portable FORTRAN Uniform (0,1) generator"
Simulation, october, (1983).
P.S. Generator slucajnih brojeva UNIRAN opisan u referenci 3 je masinski
nezavisan i stvarno dobar. Kad proradi fakultet (pocnu da greju) uzecu fajlu
i proslediti ovde.
algoritmi.39bradenkovic,
> Zolika uopste nece da se upusta u ocenjivanje generatora slucajnih broje-
>va i njihovih karakteristika. Njemu generator treba samo kao SREDSTVO, tj.
>ALAT za problem koji treba da resi. Naime, kao sto je poznato, za Miler-
>Rabinov test prostote nekog broja treba izabrati SLUCAJAN broj u intervalu
>od 0 do N-1, gde je N uneti broj.
Ako hoces da ti test bude dobar, slucajan broj mora da ima rezoluciju 1,
t.j. da je verovatnoca da se izvuce neki broj u intervalu [0,N-1)
podjednaka za sve brojeve. Posledica toga je da slucajan broj mora da
ima odgovarajuci broj znacajnih cifara pa su sva petljanja sa mantisama
necelishodna.
> Dakle, bilo bi dobro kada bi neko predlozio takav generator slucajnih
> brojeva koji bi se "automatski" (koliko je to moguce) prilagodavao intervalu
> brojeva, koji je poznat kada korisnik unese broj N ciju prostotu treba pro-
> veriti. Zolika ce (bar koliko ga poznajem) isprogramirati takav generator,
> ako sazna postoji li fazon da se generator prilagodi gornjoj granici. To
zna-
> ci da N moze da bude 13, 98457694856749501, 84787, 2674537, sve zavisi od
> toga sta korisnik unese.
Da bi resio problem postoji vise nacina. Jedan od jednostavnijih je da
koristis neki gotov paket koji podrzava beskonacne integere, cija je
duzina ogranicena memorijom (ja sam koristio pre par godina REDUCE) i da
u njemu realizujes neki od algoritama koji je predlozen u predhodnim
porukama.
Drugi postupak je da algoritam realizujes tako sto ces da umesto jedne
promenljive Z, napravis niz od 250 longint promenljivih. Mnozenje mozes
da realizujes na isti nacin kako se radi u procesoru, uzmes zadnji
pomnozis sa multiplikatorom i ako postoji prenos na sledeci broj dodas
jedan i mnozis. Ispitivanje da li postoji promena znaka vrsis samo na
prvom elementu niza. Mozda je malo glupo ali moze da se realizuje. Pri
tome je zgodno da multiplikator bude u okviru 4 bajta.
Pozdrav Boza.
algoritmi.40dejanr,
>> I šta sad? Da bismo dobili generator koji daje brojeve iz
>> opsega 0..+oo moramo da imamo generator koji daje brojeve iz
>> opsega 0..+oo. ;)
Pa, ja i nisam rekao da je to što sam napisao generator koji
zadovoljava uslove, zato i postavljam problem. Šta znam, i "luđe"
stvari su na kraju ispadale moguće.
Šteta što Alexa nije tu, sa njim sam na ovu temu svojevremeno imao
poduži razgovor i svašta smo smislili... ali problem rešili nismo ;)
algoritmi.41sirius,
Da li neko zna algoritam pomocu kojeg bi se ugrubo, ali prilicno brzo
iscrtavali TTF ili naki vektorski fontovi?
algoritmi.42zolika,
>> Da bi resio problem postoji vise nacina. Jedan od jednostavnijih je da
>> koristis neki gotov paket koji podrzava beskonacne integere, cija je
>> duzina ogranicena memorijom (ja sam koristio pre par godina REDUCE) i da
>> u njemu realizujes neki od algoritama koji je predlozen u predhodnim
>> porukama.
Pa TO i hoću. Programe za supertačnu celobrojnu aritmetiku imam, samo
mi još algoritmi fale. Elem, da rezimiramo:
MOLIM SVE ONE KOJI SU SE U DISKUSIJI OKO SLUžAJNIH BROJEVA I NJIHOVOG
GENERISANJA JAVLJALI U OVOJ TEMI, A IMAJU NEKE ALGORITME KOJI BI MI KORIS-
TILI - AKO SU VOLJNI DA TE ALGORITME DAJU (POZAJME, POKLONE), NEKA DOĐU
DONOSEĆI ISTE U SUBOTU, 16. JANUARA 1993. NA SASTANAK KLUBA U "SLAVIJU".
Dolazim u BG, pa da spojimo lepo s korisnim... Ako nekome nešto nije
jasno, molim da sva prepiska ide preko privatne pošte, da ne gnjavimo cenjeni
auditorijum.
Unapred zahvalan,
Zolika
algoritmi.43kareem,
>>
>> Onima koji traze genetator slucajnih brojeva od 0..+beskonacno
>>
E sad ovako..Prvo i Prvo Nisam matematicar iako idem u mat.gim.
Dakle onako ,ovo je nesto najbolje sto sam smislio
randseed:=??????..................??????????????????
for i:= 1 to randseed
begin
rastavimo randseed u niz od po n cifara
od clanova tog niza napravimo brojeve
for j:= 1 to koliko vec ima tih brojeva
begin
randseed:= trunc(randseed (onda neka random operacija koju izaberemo
uz pomoc nekog malog i prostog generatora slucajnih brojeva)
a[j]);
end;
end;
e sad Da nadjem matematicara koji ce potvrditi da je kodomen ove funkcije
ceo N i na konju sam..
E da jos i ovo. Ako sam nesto pogrijesio pazite nisam matematicar.
a nisam ni provjeravao. Dakle Ak vam posluzi posluzi ak ne Oprostite za
izgubljeno vrijeme.(ipak sam se potrudio,da me ne pece savest)
algoritmi.44djelovic,
Povodom diskusije o slučajnim brojevima koja se ovde vodila
proteklih nedelja, evo diskusije dejanr-ovog problema i rešenja zolikinog:
█ Für dejanr: Problem je bio da li je moguće naći generator
slučajnih brojeva od nule do beskonačnosti, uniformne raspodele. Ja
mislim da nije, a evo i zašto:
Matematika se, barem do sada, razvijala manje-više iz potrebe
(2 ovce + 2 ovce = 4 ovce :)). Još važnije od toga, svo matematičko
znanje koje mi imamo su stvorili *ljudi*. Prema tome, ono je i
ograničeno našim poimanjem sveta. Linija kao matematički pojam nije
nastala sve dok ljudi nisu počeli da prave noževe (kuće, sekire, ili šta ti
ja znam drugo) pravih ivica.
Elem, naći ću ti generator kakav želiš ako mi smisliš i
jedan događaj iz prirode koji ima uniformnu verovatnoću od 0 do
beskonačno. Bez toga, nema generatora.
Već vidim kako se ljutiš: "Pa zar matematika nije apstraktna
nauka koja nema veze sa prirodom? Mi je čisto primenjujemo na prirodu
kada nam to odgovara. Možemo recimo na osnovu našeg znanja algebre da
stvorimo matematičku strukturu koja ne bi imala nikakve veze sa stvarnim
svetom." Naravno, naravno da možemo. Ali nećemo znati da je koristimo
zbog toga što smo ograničeni ovim našim svetom...
Nadam se da smo se razumeli. Ovo gore nije naravno nikakav dokaz,
već je samo moj kratki pokušaj da objasnim zašto mislim da sa našim
matematičkim alatkama nećemo nikada moći da napravimo generator
slučajnih brojeva kakav si ti naveo. Isto kao što ne bi uopšte stigli do
integrala da smo ostali na rimskim brojevima umesto što koristimo
arapske.
█ Für zolika: Za razliku od ove "mekane" diskusije dejanr-ovog
problema, za tebe imam konkretan algoritam. Da se podsetimo, traži se
algoritam koji bi davao slučajan broj iz opsega 0 do N, gde je N
proizvoljno. Rešenje je banalno:
Ako je N broj od K cifara, jednostavno uzmeš i složiš
proizvoljnu kombinaciju od K cifara. Recimo:
A$ = ""
FOR I = 1 TO N
A$ = A$+CHR$ (ODR ('0') + RND (9))
NEXT I
Sada proveriš da li je broj koji si tako dobio veći od N, i ako
jeste, samo zatražiš sledeći slučajan broj od generatora. Ako nije, to
je tvoj broj. žudno kao što to možda izgleda, raspodela je uniformna, a
slučajan broj može biti iz proizvoljnog opsega. Sve što ti treba jeste
generator slučajnih brojeva od 0 do 9.
BTW, ne postoji *savršen* generator slučajnih brojeva, tj. svaki
od njih ima neku periodu posle koje počinje da se ponavlja. Ukoliko ćeš
ovaj svoj generator koristiti za statističku analizu a ne za neku igricu
koja mora svaki put da se drugačije ponaša, idealan način da dobiješ niz
stvarno slučajnih cifara jeste da "vadiš" cifre iz nekog iracionalnog
broja, kao što je pi, sqrt 2, sqrt 3, itd.
algoritmi.45dejanr,
>> Elem, naći ću ti generator kakav želiš ako mi smisliš i
>> jedan događaj iz prirode koji ima uniformnu verovatnoću od 0 do
>> beskonačno. Bez toga, nema generatora.
To je lako, svet je pun takvih događaja. Recimo, trenutak rođenja
DJelovića :)
algoritmi.46djelovic,
> To je lako, svet je pun takvih događaja. Recimo, trenutak rođenja
> DJelovića :)
Not so. Dobar matematičar bi, na osnovu znanja o mestu i vektorima
brzina svih čestica ovoga univerzuma mogao da izračuna stanje univerzuma
u bilo kom trenutku. Prema tome, slučajna verovatnoća rađanja moj e (a
bogami i tvoje) malenkosti zapravo i nije slučajna. Radi se pre o tome
da su babice imale nepotpune informacije :).
algoritmi.47dejanr,
>> Not so. Dobar matematičar bi, na osnovu znanja o mestu i vektorima
>> brzina svih čestica ovoga univerzuma mogao da izračuna stanje univerzuma
>> u bilo kom trenutku.
Ako je tako, onda se i svaka druga stvar može tačno predvideti pa uopšte
ne postoji slučaj a samim tim ni slučajan događaj/slučajan broj. Dakle,
svet je potpuno determinisan. Ovo je već filozofsko pitanje.
Za mene je slučajan događaj nešto na šta utiče toliko stvari da se ishod
ne može predvideti (recimo, ako bi dva puta bacio novčić identičnim
vektorom brzine, u uslovima istih vazdušnih strujanja itd, novčić bi uvek
isto pao, pa se opet to bacanje novčića uzima kao "školski primer"
slučajnog događaja).
Dakle, da je neko pre samo 5-6 hiljada godina opisao tebe i pitao kada
ćeš se roditi, jedini odgovor koji se mogao dati je "između sada i
plus beskonačno"... naravno, ako se uzme da će vasiona postojati do
"plus beskonačno".
algoritmi.48djelovic,
> Dakle, da je neko pre samo 5-6 hiljada godina opisao tebe i pi
> ćeš se roditi, jedini odgovor koji se mogao dati je "između sa
> plus beskonačno"... naravno, ako se uzme da će vasiona postoja
> "plus beskonačno".
Ajmo ovako: Vasiona ima početak i vasiona ima kraj (Big Beng). S obzirom na
to, verovatnoća događaja nije uniformna od nula do beskonačno, nego od nula do
vremena Big Benga.
No, ukoliko ostanemo na tvojim premisama, onda bi tvoj algoritam bio
sledeći:
1. Uključi štopericu.
2. Proveri da li se rodilo dete po imenu Slafirtblatfast Ristanović.
3. Ukoliko jeste, tj. ukoliko si ti to uspeo da otkriješ, zaustavi
štopericu. Broj proteklih sekundi je naš slučajan broj.
4. Ukoliko se nije rodilo takvo dete, idi na 2.
Naravno, ovakav algoritam bi morao da radi na specifičnom hardveru
(kompjuter bi morao da bude sposoban da pretrči svet tražeći dete, a bogami
trebalo bi mu i dosta memorije da upamti broj sekundi od danas do Big Benga),
ali bi radio to što ti želiš.
Kao događaj, opet, ne moraš da upotrebiš ime deteta, dovoljno je recimo da
na kompjuter priključiš kameru, da na ekranu iscrtaš neku sliku, i da čekaš da
se ulaz sa kamere potrefi sa slikom. Ili, da čekaš da neki elektron izleti iz
orbite, ili bilo šta slično.
algoritmi.49inesic,
> bogami i tvoje) malenkosti zapravo i nije slučajna. Radi
> se pre o tome
Sve, sve... ali reći za Dejana njegova malenkost...
algoritmi.50bradenkovic,
> Ako je N broj od K cifara, jednostavno uzmes i slozis
> proizvoljnu kombinaciju od K cifara. Recimo:
>
> A$ = ""
> FOR I = 1 TO N
> A$ = A$+CHR$ (ODR ('0') + RND (9))
> NEXT I
>
> Sada proveris da li je broj koji si tako dobio veci od N, i ako
> jeste, samo zatrazis sledeci slucajan broj od generatora. Ako nije, to
> je tvoj broj. Cudno kao sto to mozda izgleda, raspodela je uniformna, a
> slucajan broj moze biti iz proizvoljnog opsega. Sve sto ti treba jeste
> generator slucajnih brojeva od 0 do 9.
Bilo bi lepo kad bi bilo tako jednostavno.
Najpre rezolucija od 1/10 je vrlo mala za bilo kakav ozbiljan generator.
Dalje na osnovu osobina centralne granicne teoreme moze se predpostaviti
da tvoj generator generise neki slucajan broj koji verovatno "lici" na
normalnu raspodelu. U svakom slucaju taj broj nije sa uniformnom raspodelom.
U slobodnoj (prilagodjenoj za ovaj auditorijum) interpretaciji centralna
granicna teorema glasi: Zbir n slucajnih brojeva sa uniformnom raspodelom
predstavlja jednu realizaciju slucajne promenljive sa normalnom raspodelom,
kada n tezi beskonacno. U praksi je dovoljno da n bude 12.
Na osnovu centralne granicne teoreme moguce je napraviti skoro savrsen
generator slucajnih brojeva sa normalnom raspodelom tako sto u petlji
saberete 12 slucajnih brojeva sa uniformnom raspodelom i dobijeni zbir
proglasite za jednu realizaciju slucajne promenljive sa normalnom raspodelom.
Pozdrav Boza
algoritmi.51djelovic,
> Najpre rezolucija od 1/10 je vrlo mala za bilo kakav ozbiljan generator.
Nisam siguran na šta misliš kada kažeš rezolucija, ali ukoliko misliš na
broj ponavljanja pre nego što se generator vrati u početno stanje, tj. ukoliko
misliš da posle deset slučajnih brojeva generator počinje da se ponavlja, onda
se slažem s tobom. No, sama funkcija RND ne mora da radi po modulu 10, već može
da bude i recimo dvadesetobajtna, mi je samo svodimo na opseg 0-9.
E sad, ovaj generator koji sam ja izneo, iako je daleko od savršenog, radi
zoliki posao ko bog, prema tome što dalje teoretisati?
BTW, Evo na šta se algoritam svodi:
1. uzmi par slučajnih brojeva.
2. Provuci ih kroz HASH funkciju (ono slepljivanje cifara se na to svodi!),
i time im povećaj rezoluciju.
algoritmi.52vpetrovic,
>> Not so. Dobar matematičar bi, na osnovu znanja o mestu i vektorima
>> brzina svih čestica ovoga univerzuma mogao da izračuna stanje univerzuma
>> u bilo kom trenutku. Prema tome, slučajna verovatnoća rađanja moj e (a
>> bogami i tvoje) malenkosti zapravo i nije slučajna. Radi se pre o tome
>> da su babice imale nepotpune informacije :).
Ali nikad ne bi mogao da dođe do tih podataka zbog principa neodređenosti,
pa bi jedino mogao da izračuna verovatnoću ;))
Vlada
algoritmi.53bradenkovic,
> Nisam siguran na sta mislis kada kazes rezolucija, ali ukoliko mislis na
>broj ponavljanja pre nego sto se generator vrati u pocetno stanje, tj. ukoliko
>mislis da posle deset slucajnih brojeva generator pocinje da se ponavlja, onda
>se slazem s tobom. No, sama funkcija RND ne mora da radi po modulu 10, vec
moze
>da bude i recimo dvadesetobajtna, mi je samo svodimo na opseg 0-9.
Rezolucija generatora je najmanja distanca izmedju dva razlicita slucajna
broja.
U tvom slucaju uzeo si celobrojnu vrednost od rnd(9) i time ukinuo sve brojeve
izmedju cifara. Najmanja distanca izmedju tako generisana dva broja je 1. Ako
normalizujes na interval [0-1) dobijes 1/10. Funkcija gustine raspodele takve
promenljive bice stepenice sa 10 stepenika umesto fine gladke funkcije.
Kakva ce se raspodela promenjive dobiti kad se takav broj sa kilavom uniformnom
raspodelom pomnozi sa istim takvim brojem pomnozenim sa 10, Bog sveti zna.
Ako se zanemare raznorazne autokorelacije koje su u ovom slucaju moguce,
trebala bi da bude nesto sto pomalo lici na normalnu raspodelu a malo vise
na studentovu za odgovarajuci broj stepeni slobode. No ovo vec prelazi u
bajanje tako da dalja diskusija po ovom pitanju bez detaljnijeg uvida u
literaturu ili nekog dodatnog istrazivanja nema smisla.
Pozdrav Boza.
algoritmi.54nenadb.,
>> Not so. Dobar matematicar bi, na osnovu znanja o mestu i vektorima
>> brzina svih cestica ovoga univerzuma mogao da izracuna stanje univerzuma
>> u bilo kom trenutku.
Konacni odgovor u svakom slucaju je '42'.
algoritmi.55janko,
> █ Für zolika: Za razliku od ove "mekane" diskusije
> dejanr-ovog problema, za tebe imam konkretan algoritam. Da
> se podsetimo, traži se algoritam koji bi davao slučajan
> broj iz opsega 0 do N, gde je N proizvoljno. Rešenje je
> banalno: Ako je N broj od K cifara, jednostavno uzmeš i
> složiš proizvoljnu kombinaciju od K cifara. Recimo:
>
> A$ = ""
> FOR I = 1 TO N
> A$ = A$+CHR$ (ODR ('0') + RND (9))
> NEXT I
>
> Sada proveriš da li je broj koji si tako dobio veći od N,
> i ako jeste, samo zatražiš sledeći slučajan broj od
> generatora. Ako nije, to je tvoj broj. žudno kao što to
> možda izgleda, raspodela je uniformna, a slučajan broj
> može biti iz proizvoljnog opsega. Sve što ti treba jeste
> generator slučajnih brojeva od 0 do 9.
:( Ovako bi se onda svi generatori pravili... a ne prave se.
Kao dalja varijacija tvoje ideje: napraviš RND generator u
opsegu 0..1 pa praviš proizvoljno velike RND generatore.
To se ne radi. Zašto? Piše u nekim knjigama...
> BTW, ne postoji *savršen* generator slučajnih brojeva, tj.
> svaki od njih ima neku periodu posle koje počinje da se
> ponavlja. Ukoliko ćeš ovaj svoj generator koristiti za
> statističku analizu a ne za neku igricu koja mora svaki
> put da se drugačije ponaša, idealan način da dobiješ niz
> stvarno slučajnih cifara jeste da "vadiš" cifre iz nekog
> iracionalnog broja, kao što je pi, sqrt 2, sqrt 3, itd.
I ovo se ne koristi. ;) To što ne znamo kako se ponašaju cifre
iracionalnih brojeva ne znači da njihovo pojavljivanje ima
uniformnu raspodelu.
algoritmi.56zzile,
Razmisljao sam malo na temu beskonacnog slucajnog broja. Cinimi se
da ne stoji da je broj RND(ý) (za uniformnu raspodelu) konacniji od
broja ý, sto cu pokusati da obrazlozim:
Ako je raspodela uniformna onda ce matematicko ocekivanje te
raspodele opet da bude beskonacan broj, a ako razmatramo bilo koji
ogranicen interval u kome bi se nasao generisani broj, verovatnoca
da broj bude van tog intervala tezi sigurnom dogadjaju. Znaci da
ako generator da konacan broj, skoro sigurno raspodela nije uniformna!
U skladu s tim meni se cini da nema razlike u koriscenju oznaka
RND(ý) i ý, tj. sumnjam u primenjivost broja RND(ý), a da se ona
razlikuje od primenjivosti broja ý. Na primer: ako integral sa
nekom granicom ý tezi konacnom broju onda ce i integral sa granicom
RND(ý) takoce da tezi tom broju, sa verovatnocom koja tezi jedinici,
takodje verovatno vazi sa verovatnocom koja tezi jedinici:
abs(RND(ý)-RND(ý)) = ý, itd.
Za matematicke primene je verovatno RND(ý) = ý, a za programerske
bi bilo dovoljno naci algoritam za bilo koji unapred zadati interval,
ili generator koji do kraja svog postojanja izbacuje cifre, ili
generator za neku raspodelu koja nije uniformna (kao sto u prirodi
uglavnom nije) npr. za gausovu raspodelu na intervalu do +ý, sto je
lakse napraviti (potrebno je da imamo generator slucajnog broja izmedju
0 i 1, kao i samu raspodelu sa proizvoljnom tacnoscu).
algoritmi.57nenadp,
>> Not so. Dobar matematicar bi, na osnovu znanja o mestu i
>> vektorima brzina svih cestica ovoga univerzuma mogao da
>> izracuna stanje univerzuma u bilo kom trenutku.
Eh bas bi voleo da vidim tog dobrog matematicara kada pocne da se bavi
kvantnom fizikom da li bi i dalje tvrdio ovo gore.
Pozdrav, Nenad
P.S. Da potsetim na poznatu relacija neodredjenosti po kojoj sto je
tacnije poznat polozaj cestice to netacnije poznajemo impuls cestice.
algoritmi.58zzile,
Sva ova diskusija kao problem ima sustinu pojma beskonacno.
Ako za primer primene ovog generatora uzmemo ipak ograniceno
trajanje vasione i jedan proizvoljan trenutak onda je to problem
odgovarajuceg hardvera, a o pravoj beskonacnosti mi je tesko
diskutovati. Ako je vasiona beskonacna onda u njoj ima susednih
cestica samo zato sto i njih mora da ima beskonacno mnogo?!
Neka neko za pocetak predlozi generator realnihbrojeva u opsegu
0 do 1, ali sa beskonacno velikim brojem decim
algoritmi.59dejanr,
>> Neka neko za pocetak predlozi generator realnihbrojeva u opsegu
>> 0 do 1, ali sa beskonacno velikim brojem decim
Pa, to je isto - ako bi imao onaj "moj" generator, generišeš ceo
slučajan broj između 1 i beskonačno (recimo, broj M) i izračunaš
1/M.
algoritmi.60zsiz,
> Ajmo ovako: Vasiona ima početak i vasiona ima kraj (Big Beng). S obzirom
na
> to, verovatnoća događaja nije uniformna od nula do beskonačno, nego od nula
do
> vremena Big Benga.
žitao sam u jednom kompjuterskom listu da za pravljenje programa
software-ske firme sve više angažuju diplomirane filozofe kao
konsultante. Ako ovako nastaviš neka od tih firmi ima garantovano
da te angažuje ;)).
Pozdrav.
zsiz
algoritmi.61darone,
>> da ne stoji da je broj RND(ý) (za uniformnu
>> raspodelu) konacniji od broja ý, sto cu pokusati
>> da obrazlozim:
Šta konkretno, na primeru, znači konačniji? To je
kao crnji. Ako je već crn, kako može da bude crnji?
darone
algoritmi.62dejanr,
>> Ajmo ovako: Vasiona ima početak i vasiona ima kraj (Big Beng).
Hmmm... valjda je Big Beng početak, a za kraj se još naučnici nisu
"dogovorili", 'oćel' ga biti il' neće.
>> S obzirom na to, verovatnoća događaja nije uniformna od nula do
>> beskonačno, nego od nula do vremena Big Benga.
Ako se uzme da će vasiona "zauvek" postojati, onda je to uniformno
raspoređen broj između trenutka nastanja ljudi u današnjem obliku
i plus beskonačno. Šanse da će se neko nalik na čoveka roditi
u prvih pola sata posle Big Banga su, recimo, nikakve ;)
U tom smislu, mislim da bi se sve to moglo uzeti kao generator
slučajnog broja u intervalu [0, +beskonačno) E još da napravimo
nešto slično za računar...
Uzgred, neki ljudi na BIX-u sa kojima sam diskutovao o istom problemu
su me uputili na neki rad (premda još nemam tačnu referencu) u kome
su neki treći ljudi navodno (k'o što se vidi, sve same sigurne
informacije ;) dokazali da bi se takav generator mogao konstruisati
(eto, ispade da nisam izmislio problem, ništa novo na ovome svetu :( )
ali izgleda da još niko nije uspeo da ga konstruiše. Jedna faca sa nekog
manjeg USA univerziteta (za koji nikad nisam čuo :) kaže da bi čak i
najugledniji časopis rado objavio rad u kome se opisuje takav generator
(ja dodajem "po skidanju sankcija" ;)
algoritmi.63zzile,
>Pa, to je isto - ako bi imao onaj "moj" generator, generises
>ceo slucajan broj izmedu 1 i beskonacno (recimo, broj M) i
>izracunas 1/M.
Problem je naravno slicne tezine ali se navedenom transformacijom
raspodela drasticno menja.
algoritmi.64inesic,
> Hmmm... valjda je Big Beng početak, a za kraj se još
> naučnici nisu "dogovorili", 'oćel' ga biti il' neće.
Grešiš! Sve se zna. Kraj se zove Gneb Gib i ako u neku od
intergalaktičkih banaka uložiš paru, od kamata ćeš moći dooobro
da se najedeš posmatrajući to čudo. U retoranu na kraju
univerzuma.
algoritmi.65zzile,
> Sta konkretno, na primeru, znaci konacniji? To je
> kao crnji. Ako je vec crn, kako moze da bude crnji?
More, bice nam sve crnje i crnje :)). Salu na stranu pridev konacan
stvarno ne vredi porediti.
algoritmi.66tomae,
> P.S. Da potsetim na poznatu relacija neodredjenosti po kojoj sto je
> tacnije poznat polozaj cestice to netacnije poznajemo impuls
Da dodamo i koeficijent eta (potreban za određivanje momenta rođenja
određene osobe) koji karakteriše položaj mama<->tata :)
on ona eta
======================
G D 0.2
D G 0.21
B B 0.03
NZ NP 0.18
. . .
legenda
-------
G - gore D - dole
B - bok NZ - nazad ...
Tabela se može smatrati PD. "Dobri matematičari", napred! :)))))
algoritmi.67ndragan,
/>> da ne stoji da je broj RND(ý) (za uniformnu
/ Šta konkretno, na primeru, znači konačniji? To je
Pa RND(ý) bi morao da daje slučajne brojeve u intervalu od 0 do ý;
vrednosti koje daje bi mogle da budu konačne ili ne. Ja sam 'konačniji'
shvatio kao 'više puta ispadne konačan' ili 'ima više osobina konačnog
broja nego beskonačnog', sasvim u duhu matematičarskog jezika.
algoritmi.68ndragan,
/>> bogami i tvoje) malenkosti zapravo i nije slučajna. Radi se pre o
/>> tome da su babice imale nepotpune informacije :).
/ Ali nikad ne bi mogao da dođe do tih podataka zbog principa
/ neodređenosti,
A bogami, da su se babice malo pozabavile očitavanjem relevantnih
činjenica, ne bi se rodio do dana današnjeg... one bi još čitale
preliminarna opšta mesta.
algoritmi.69janko,
Pitanje:
Koji brojevi od onih koje često nalazimo kod nas u praksi imaju
osobinu da može da im se proveri ispravnost pri ukucavanju i
koji su odgovarajući algoritmi za odgovarajuće brojeve? Drugim
rečima, koji brojevi imaju u sebi ugrađene kontrolne sume?
Npr: ako neko otkuca neispravan matični broj, ili broj tekućeg
računam ili... može li to program da detektuje, i ako može
kako?
(Dobio sam inspiraciju za pitanje kada su mom tati na nekom
dokumentu koji su generisali kompjuterom zeznuli njegov MB, pa
je morao još jedan dan da ide da se zeza po šalterima)
algoritmi.70ppekovic,
>> Koji brojevi od onih koje često nalazimo kod nas u praksi imaju
>> osobinu da može da im se proveri ispravnost pri ukucavanju i
>> koji su odgovarajući algoritmi za odgovarajuće brojeve? Drugim
>> rečima, koji brojevi imaju u sebi ugrađene kontrolne sume?
Uvek sam se pitao što u metičnom broju predstavljaju
poslednjih 6 cifara. Početak je naravno dan, mesec i godina (bez
hiljada) rođenja.
Paya
algoritmi.71djelovic,
> Uvek sam se pitao što u metičnom broju predstavl
> poslednjih 6 cifara.
Šifru mesta rođenja, bolnice i valjda informacija koje si dete na bolničkom
spisku. Ni za jedan zvanični podatak ne postoji CRC-32 :).
algoritmi.72wizard,
> Uvek sam se pitao što u metičnom broju predstavljaju
> poslednjih 6 cifara.
Od tih 6, prve dve predstavljaju opštinu, sledeća označava pol, 0 i još
jedan (ne sećam se koji) za muškarce i 5 i još jedan (opet se ne sećam
koji) za žene, a poslednje 3 cifre su i meni neobjašnjive i za sada
smatram da i ne znače ništa osim što učestvuju u kontrolnoj sumi.
Inače - odgovor na Jankovo pitanje: postoji kontrolna suma, verovatno se
poslednje tri cifre "nameštaju" tako da kontolna suma bude svima ista.
algoritmi.73dejanr,
>> Koji brojevi od onih koje često nalazimo kod nas u praksi imaju
>> osobinu da može da im se proveri ispravnost pri ukucavanju i
>> koji su odgovarajući algoritmi za odgovarajuće brojeve? Drugim
>> rečima, koji brojevi imaju u sebi ugrađene kontrolne sume?
Bojim se da je takvih jako malo, ako ih uopšte ima. Neki od brojeva
koji sigurno *nemaju* checksum su: matični broj firme, šifra delatnosti,
šifra oblika udruživanja (termin iz drugog vremena ;), žiro račun...
Kažu da matični broj građanina ima zadnju cifru koja predstavlja kontrolu
tačnosti, ali izgleda da niko nije baš siguran da je stvarno tako niti
zna kako se šifra određuje.
Od prošle godine svi brojevi faktura imaju poslednju cifru kojom se
utvrđuje tačnost. Algoritam je poznat i ima ga negde na Sezamu iz
vremena kada je to bilo aktuelno (prošle godine su svi Clipper programi
morali da se prepravljaju tim povodom, kad će nešto novo pa da opet
naplaćujemo? :)).
Taj algoritam je otprilike ovakav:
function checksum (broj: longint): longint;
var brojs: string;
suma,i: longint;
begin
str(broj, brojs);
suma:=0;
for i:=1 to length(brojs) do
begin
suma:=suma+(ord(brojs[i])-ord('0'))*(length(brojs)+2-i)
end;
suma:=suma mod 11;
if suma<>0 then suma:=(11-suma) mod 10;
checksum:=broj*10+suma;
end;
algoritmi.74ivanna,
> Uvek sam se pitao sto u meticnom broju predstavljaju
> poslednjih 6 cifara. Pocetak je naravno dan, mesec i godina
10-ta cifra je za pol
0 - muski
5 - zenski
algoritmi.75mladenp,
> Uvek sam se pitao što u metičnom broju
> predstavljaju poslednjih 6 cifara. Početak je naravno dan,
> mesec i godina (bez hiljada) rođenja.
Posle godine idu dve cifre koje označavaju mesto rođenja.
Za Beograd - 71. Neko reče da je to oznaka opštine. Ne bih
rekao. Mogao bi neko rođen u Zemunu da nam kaže šta kod
njega piše.
Sledeće tri cifre su redni broj bebe (od 0 do 499 za muške
i 500 do 999 za ženske). Tako su mi svojevremeno rekli u
gradskom zavodu za statistiku. Ne znam da li se sortiraju po
vremenu rođenja (sumnjam) ili po redosledu prijavljivanja.
Poslednja cifra je kontrolni broj.
algoritmi.76bulaja,
│Uvek sam se pitao sto u meticnom broju predstavljaju poslednjih
│6 cifara. Pocetak je naravno dan, mesec i godina (bez hiljada) rodenja.
└───
Neke od cifara su i sifra grada (za beograd su valjda 7. i 8. cifra 71)
i pol. Ima jos i neka random cifra i that's all. Nisam siguran da li
postoji kontrolna cifra. U brojevima ziro i tekucih racuna uvek postoji
kontrolna cifra, bilo je negde u staroj PC.PROG temi diskusije oko toga.
algoritmi.77dtadic,
>> Posle godine idu dve cifre koje oznacavaju mesto rodenja.
>> Za Beograd - 71. Neko rece da je to oznaka opstine. Ne bih
>> rekao. Mogao bi neko roden u Zemunu da nam kaze sta kod
>> njega pise.
Za Zemun je takodje 71.
DT
algoritmi.78dejanr,
>> U brojevima ziro i tekucih racuna uvek postoji kontrolna cifra, bilo
>> je negde u staroj PC.PROG temi diskusije oko toga.
Ne znam za broj tekućeg, ali za broj žiro računa veoma sumnjam da ima
kontrolnu sumu. čiro računi za firme su obično rrxxx-mmm-n gde je rr
Republika/Pokrajina (još od exYU je bilo Bosna, CG, Hrv, Mak, Slo
redom 10,20,30,40,50, Srbija 60-64, Vojvodina 65-66 i Kosovo 68.
xxx označava banku, mmm je tip žiro računa (firme su obično 601, 603,
ali ima i raznih internih banki, siz-ova itd sa 664 i raznim drugim
brojevima) a N je redni broj, i to ti brojevi N idu redom, dakle recimo
postoje žiro računi tipa 60811-601-10, pa onda 60811-601-11 i tako dalje,
"rupe" uglavnom dolaze od firmi koje su vremenom propadale, integrisale
se itd.
U svemu ovome nema mesta za kontrolnu sumu. Jedina mala kontrola je da
žiro nije ispravan ako počinje na 67 ili 69, ali od toga slaba vajda.
algoritmi.79milan,
> Kažu da matični broj građanina ima zadnju cifru koja predstavlja kontrolu
> tačnosti, ali izgleda da niko nije baš siguran da je stvarno tako niti
> zna kako se šifra određuje.
Zaboravio sam modul, ali je checksum po sredi. žini mi se da je to
zbir prethodnih cifara modulo 11 ili 13.
Pl poz M
algoritmi.80jtitov,
>>> Koji brojevi od onih koje cesto nalazimo kod nas u
>>> praksi imaju osobinu da moze da im se proveri ispravnost
>>> pri ukucavanju i
> Uvek sam se pitao sto u meticnom broju
> predstavljaju
U maticnom broju radnih ljudi i gradjana, postoji kontrola po modulu 11 i
to je ona zadnja cifra.
algoritmi.81djelovic,
> U maticnom broju radnih ljudi i gradjana, postoji kontrola po modulu 11 i
> to je ona zadnja cifra.
Jok. Probao sam - kod mene radi, kod moje babe ne :).
algoritmi.82robert,
>> Sledeće tri cifre su redni broj bebe (od 0 do 499 za muške
>> i 500 do 999 za ženske). Tako su mi svojevremeno rekli u
Sve je to lepo ali kako se određuju brojevi onima rođeni u
inostranstvu? Teško da imaju onda taj 'broj bebe'.
algoritmi.83dragisak,
║ Neke od cifara su i sifra grada (za beograd su valjda 7. i 8. cifra
║ 71) i pol. Ima jos i neka random cifra i that's all. Nisam siguran
║ da li postoji kontrolna cifra. ...
Evo ga algoritam za izračunavanje kontrolne cifre kod matičnog broja građana :
MBG = a1,a2,a3,a4,a5,a6,a7,a8,a9,a10,a11,a12,a13
sum = a1 * 7 +
a2 * 6 +
a3 * 5 +
a4 * 4 +
a5 * 3 +
a6 * 2 +
a7 * 7 +
a8 * 6 +
a9 * 5 +
a10* 4 +
a11* 3 +
a12* 2;
ctrl = 11 - mod( sum, 11 );
if ( ctrl < 10 )
a13 = ctrl;
else
a13 = 0;
algoritmi.84vitez.koja,
#=> Sve je to lepo ali kako se određuju brojevi onima rođeni
#=> u inostranstvu? Teško da imaju onda taj 'broj bebe'.
Onda im daju 666 ;)
algoritmi.85mjova,
> Evo ga algoritam za izračunavanje kontrolne cifre kod
> matičnog broja građana :
probah, moj broj paše ;)
algoritmi.86mladenp,
> Sve je to lepo ali kako se određuju brojevi onima rođeni u
> inostranstvu? Teško da imaju onda taj 'broj bebe'.
Odmah da kažem: ne znam. Ako ide po redosledu prijavljivanja
(upisivanja u matične knjige), nema problema.
Mnogo zanimljivije pitanje u vezi sa bebama rođenim
u inostranstvu: koja je oznaka mesta rođenja? :)
algoritmi.87dnikolic,
>> suma:=suma+(ord(brojs[i])-ord('0'))*(length(brojs)+2-i)
Ne razumem se bas u Pascal, sta radi funkcija ORD? Inace, ovo je veoma
interesantan programcic, to mi zaista treba!
dn
algoritmi.88darone,
>> MBG = a1,a2,a3,a4,a5,a6,a7,a8,a9,a10,a11,a12,a13
Samo još da neko kaže šta je *tačno* koja od
cifara...
darone
algoritmi.89zolika,
>> Uvek sam se pitao što u metičnom broju predstavljaju
>> poslednjih 6 cifara. Početak je naravno dan, mesec i godina (bez
>> hiljada) rođenja.
Zar nije poslednja cifra ostatak po modulu 11 ili 13 ?
algoritmi.90ladislavs,
> Posle godine idu dve cifre koje označavaju mesto rođenja.
> Za Beograd - 71. Neko reče da je to oznaka opštine. Ne bih
Izgleda da to nije baš to. Po ovome bi Novi Sad bio deo Beograda,
a čini mi se da (još uvek ;) nije.
Možda su pretpostavili da ću o'ma da se preselim u BG ;))).
ciLa.
algoritmi.91smiloradovic,
)>> Sve je to lepo ali kako se određuju brojevi onima rođeni u
)>> inostranstvu? Teško da imaju onda taj 'broj bebe'.
)>
)> Odmah da kažem: ne znam. Ako ide po redosledu prijavljivanja
)> (upisivanja u matične knjige), nema problema.
Znam par ljudi koji nisu rođeni u Beogradu, ali pošto im je lična
karta izdata ovde, u MB imaju 71 kao oznaku mesta. Znači, biće da nema
baš puno veze sa bebama :)
algoritmi.92mbole,
Ja sam rođen u Kragujevcu a u matičnom broju imam 71. Možda to ide na
osnovu mesta izdavanja lične karte.
algoritmi.93janko,
> Evo ga algoritam za izračunavanje kontrolne cifre kod
> matičnog broja građana :
Super! Samo još da ga probam... nadam se da oni koji su
izmišljali broj za svakog čoveka nisu davali peške službenicima
da ga računaju. ;)
Izuzetno mi je drago što smo došli do nekih rezultata! Idemo
dalje! Hajde da nađemo još 'bezbednih' brojeva!
A već smo načeli i drugu temu:
Očigledno postoji i dosta brojeva koji u sebi, osim što imaju
osobinu ključa, sadrže još neke korisne podatke. Videli smo i
par primera. Npr. u pomenutom matičnom broju se krije
informacija o datumu rođenja osobe i njenom polu. Zne li neko
još neke brojeve, koje do sada nismo pomenuli, a koji u sebi
sadrže dodatne korisne informacije?
algoritmi.94mladenp,
> Ja sam rođen u Kragujevcu a u matičnom broju imam 71.
> Možda to ide na osnovu mesta izdavanja lične karte.
Sve što mogu da zaključim na temu JMBG (jedinstveni
matični broj građana) je JBMG ('bem li ga ;)).
Matični brojevi su uvedeni relativno skoro (petnaestak
godina) a svi mi smo rođeni ranije. Trebalo bi videti
kakav broj imaju oni koji će ličnu kartu prvi put dobiti
za dve-tri godine. :)
algoritmi.95wizard,
> Ja sam rođen u Kragujevcu a u matičnom broju imam 71. Možda to ide na
> osnovu mesta izdavanja lične karte.
Ma naravno, nema veze gde si rođen. :) Ja sam nejasan bio kad sam
rekao da je to broj za opštinu (mislio sam na prebivalište - uostalom,
samo u Srbiji ima preko 100 opština), pre će biti da su u pitanju malo
veće enklave. ;)
algoritmi.96bulaja,
│Ne razumem se bas u Pascal, sta radi funkcija ORD?
└───
Da ne bi mnogo objasnjavao :), evo Wirthove definicije - Ord(x) je redna
funkcija koja vraca redni broj (celobrojnu vrednost) rednog parametra x
u skupu vrednosti definisanih tipom podataka od x.
Npr. ako je x tipa char, onda bi Ord(x) vratio ascii kod od x.
algoritmi.97mbole,
> kakav broj imaju oni koji će ličnu kartu prvi put dobiti
> za dve-tri godine. :)
Matični broj se dobija pri rođenju, a ne pri izdavanju lične karte. Ne
znam koji je sistem bio za nas koji smo već bili rođeni kada su ga uveli.
Izgleda da tu dolazi do zbrke.
algoritmi.98dejanr,
>> Ja sam nejasan bio kad sam rekao da je to broj za opštinu (mislio sam
>> na prebivalište - uostalom, samo u Srbiji ima preko 100 opština), pre
>> će biti da su u pitanju malo veće enklave. ;)
Garant su te enklave tzv. "bivši srezovi". Ti srezovi su ukinuti još
Bog-zna-pre-koliko-godina ali što se administracije tiče i dan danas
funkcionišu. Svaki izgleda ima neki svoj računski centar (sa svojim
rasporedom YU slova :( ) i onda se to samo sliva u neki centar.
algoritmi.99mbacic,
Da li neko zna neki algoritam za crtanje kruga sem Bresham's algorithm i
trigonometrijskog nacina.
algoritmi.100pedjak,
> ctrl = 11 - mod( sum, 11 );
A kako bi izgledala ova funkcija mod ? Pojam modula mi je nepoznat,
pa bih bio vrlo zahvalan da mi ga neko objasni.
pedja
algoritmi.101ppekovic,
>> A kako bi izgledala ova funkcija mod ? Pojam modula mi je nepoznat,
>> pa bih bio vrlo zahvalan da mi ga neko objasni.
Modul/moduo je ostatak deljenja dva broja.
Paya
algoritmi.102dejanr,
>> A kako bi izgledala ova funkcija mod ? Pojam modula mi je nepoznat,
>> pa bih bio vrlo zahvalan da mi ga neko objasni.
mod (a,b) = a - int(a/b)*b
algoritmi.103peca.st,
!-> Da li neko zna neki algoritam za crtanje
!-> kruga sem Bresham's algorithm i
!-> trigonometrijskog nacina.
A kako ide taj Breshamov algoritam, ako smem da znam?
Peđa.
algoritmi.104milan,
> Garant su te enklave tzv. "bivši srezovi". Ti srezovi su ukinuti još
> Bog-zna-pre-koliko-godina ali što se administracije tiče i dan danas
> funkcionišu. Svaki izgleda ima neki svoj računski centar (sa svojim
> rasporedom YU slova :( ) i onda se to samo sliva u neki centar.
Pa baš da su ih ukinuli i nisu! Samo su ih ojačali uvođenjem
pojma "okrug" i "načelnika okruga", k'o za vreme kralja Milana.
Jedino su Beograd i valjda Niš i Novi Sad ostali sa statusom
"grada". Tako su i delili izborne jedinice (po dva okruga u
jednu) jer Faraon lično imenuje načelnike i oni direktno
kontrolišu policiju i odgovaraju njemu. Lepo i praktično, a
neprimetno. Niko nije ni oučio kakvu su važnu izmenu u
teritorijalni sistem Srbije uneli. A?
Pl poz M
algoritmi.105milan,
> Da li neko zna neki algoritam za crtanje kruga sem Bresham's algorithm i
> trigonometrijskog nacina.
A šta fali imentovanima?
Pl poz M
algoritmi.106janko,
> Super! Samo još da ga probam... nadam se da oni koji su
> izmišljali broj za svakog čoveka nisu davali peške
> službenicima da ga računaju. ;)
Probao sam na bazi od više stotina matičnih brojeva, unesenih
'na suvo' (bez provere pri kucanju). žetiri posto brojeva imaju
neispravnu kontrolnu sumu, ostali se svi slažu. Pretpostavljam
da je tih četiri posto greška operatera. Dakle, RADIIIII!
algoritmi.107dragisak,
║ A kako bi izgledala ova funkcija mod ? Pojam modula mi je nepoznat,
║ pa bih bio vrlo zahvalan da mi ga neko objasni.
U bre, šta su te učili u osnovnoj školi ? :)
Moduo je celobrojni ostatak pri deljenju.
Na primer mod(13,7)=6 ili mod(12,6)=0
algoritmi.108zamahajev,
Mislim da poslednja cifra za korekciju greške po modulu 11, a dve cifre
(za Beograd 71) predstavljaju grad u kome je dotični boravio kada je dodeljivan
matični broj. Za novorodjene se odmah posle rodjenja dodeljuje ovaj broj.
Sledeće cifre se dodeljuju kao neki redni broj pri čemu se za muški pol
dodeljuju brojevi do 499, a preko za ženski.
algoritmi.109pedjak,
> Modul/moduo je ostatak deljenja dva broja.
Ah, to je to ! Hvala !
pedja
algoritmi.110draganm,
*> A sta fali imentovanima?
*>
Spori su i zahtevaju realne promenjive ...
algoritmi.111drmarke,
> mod (a,b) = a - int(a/b)*b
Long Live BASIC ! ;)
Pozdrav DrMarke
algoritmi.112drmarke,
> Garant su te enklave tzv. "bivši srezovi". Ti srezovi su
> ukinuti još
Srezovi ---> Regioni ---> Okrugi ;)
Pozdrav DrMarke
algoritmi.113dejanr,
>> > mod (a,b) = a - int(a/b)*b
>>
>> Long Live BASIC ! ;)
Long Live BASIC, mada ta naredba tako glasi i u većini drugih
jezika, npr. u FORTRAN-u koji takođe "long live" :)
Zapravo, u bejziku bi moralo da se napiše DEFFNmod(a,b), ako se
dobro sećam.
algoritmi.114milan,
> Spori su i zahtevaju realne promenjive ...
U odnosu na koje druge algoritme za crtanje kruga su spori?
Sa čime si ih poredio, pa si zaključio da su spori?
Pl poz M
algoritmi.116nbatocanin,
Zamolio me moj prijatelj da prenesem njegovu poruku:
Drage kolege,
evo da citiram materijal koji sam dobio interesujući se za kontrolu JMBG.
On je u formi fotokopije neidentifikovanog originala. Nadam se da će vam
svima pomoći, a i vi meni nekim informacijama (vidi posle materijala)
#POžETAK MATERIJALA
NAžIN ODREĐIVANJA KONTROLNOG BROJA JEDINSTVENOG MATIžNOG BROJA GRAĐANA
Kontrolni broj (trinaesta cifra) JMBG određuje se po modulu 11 na
sledeći način:
1) -prva cifra se množi sa 7
-druga 6
-treća 5
-četvrta 4
-peta 3
-šesta 2
-sedma 7
-osma 6
-deveta 5
-deseta 4
-jedanaesta 3
-dvanaesta 2
2) dobijeni parcijalni proizvodi iz tačke 1. se saberu i dobijeni zbir se
deli sa 11, pri čemu se deljenje ograničava samo na cele brojeve.
3) ostatak koji se dobije pri deljenju oduzima se od broja 11 i dobijena
razlika predstavlja kontrolni broj.
Primeri:
a) za građanina rođenog 10.januara 1939. godine, sa registarskog područja 01,
muškog pola, upisanog pod rednim brojem 001, matični broj (bez kontrolnog
broja) j
e:
1 0 0 1 9 3 9 0 1 0 0 1
X 7 6 5 4 3 2 7 6 5 4 3 2
----------------------------------
7 0 0 4 27 6 63 0 5 0 0 2
Zbir je:
7+0+0+4+27+6+63+0+5+0+0+2 = 114
114 : 11 = 10
110
---
4
Kontrolni broj je 11-4=7
Za tog građanina matični broj je 1001939010017 ;
b) za građanina rođenog 20.januara 1939. godine, sa regostarskog područja 01,
muškog pola, upisanog pod rednim brojem 001, matični broj (bez kontrol
nog
broja) je:
2 0 0 1 9 3 9 0 1 0 0 1
X 7 6 5 4 3 2 7 6 5 4 3 2
----------------------------------
14 0 0 4 27 6 63 0 5 0 0 2
Zbir je:
14+0+0+4+27+6+63+0+5+0+0+2 = 121
121 : 11 = 11
121
---
0
Za kontrolni broj uzima se 0.
Za tog građanina matični broj je 2001939010010 ;
4) ako je ostatak pri deljenju jednak 1, za kontrolni broj ne uzima se 10,
jer kontrolni broj ne može biti dvocifren nego se broj koji izražava
kombinaciju pola i rednog broja za lica rođena istog datuma (V grupa cifara
matičnog broja) uvećava za 1 i način određivanja kontrolnog broja se
ponavlja.
Primer:
Za građanina rođenog 22.januara 1939. godine, sa regostarskog područja 01,
muškog pola, upisanog pod rednim brojem 001, matični broj (bez kontrolnog
broja) je:
2 2 0 1 9 3 9 0 1 0 0 1
X 7 6 5 4 3 2 7 6 5 4 3 2
----------------------------------
14 12 0
4 27 6 63 0 5 0 0 2
Zbir je:
14+12+0+4+27+6+63+0+5+0+0+2 = 133
133 : 11 = 12
132
---
1
Kontrolni broj je 11-1=10.
U tom slučaju uzima se sledeći broj 002, odnosno broj koji izražava
kombinaciju pola i rednog broja za lica rođena istog datuma (V grupa cifara
matičnog broja) - u datom primeru 001 i uvećava za 1, a način određivanja
kontrolnog broja se ponavlja:
2 2 0 1 9 3 9 0 1 0 0 2
X 7 6 5 4 3 2 7 6 5 4 3 2
--
--------------------------------
14 12 0 4 27 6 63 0 5 0 0 4
Zbir je:
14+12+0+4+27+6+63+0+5+0+0+4 = 135
135 : 11 = 12
132
---
3
Kontrolni broj je 11-3=8.
Za tog građanina matični broj je 2201939010028.
#KRAJ MATERIJALA
Uz ovu fotokopiju dobio sam i sledeći listing (valjda COBOL):
#POžETAK LISTINGA
;01 WMBR.
; 02 WDATUMR.
; 03 C1 PIC 9.
; 03 C2 PIC 9.
; 03 C3 PIC 9.
; 03 C4 PIC 9.
; 03 C5 PIC 9.
; 03 C6 PIC 9.
; 03 C7 PIC 9.
; 02 WFIKSB.
; 03 C8 PIC 9.
; 02 WSIFREG.
; 03 C9 PIC 9.
; 02 WRBR.
; 03 C10 PIC 9.
; 03 C11 PIC 9.
; 03 C12 PIC 9.
; 02 WKONBR PIC 9.
*****************************************************************************
*----------------ODREDJIVANJE KONTROLNE SIFRE---------------------*
:BLOK-3
: COMPUTE Z = C1 * 7 + C2 * 6 + C3 * 5 + C4 * 4 + C5 * 3
: + C6 * 2 + C7 * 7 + C8 * 6 + C9 * 5 + C10 * 4 + C11 * 3
: + C12 * 2.
: DIVIDE Z BY 11 GIVING Z1 REMAINDER OSTAT.
: IF OSTAT = 1 COMPUTE KRBR = KRBR + 1
: MOVE KRBR TO WRBR GO TO BLOK-3.
: IF OSTAT = 0 MOVE 0 TO WKONBR ELSE
: COMPUTE WKONBR = 11 - OSTAT.
*****************************************************************************
#KRAJ LISTINGA
Ko razume, shvatiće!
Meni se čini da je ovo samo (isčupan) deo iz većeg listinga. Izvinjavam se
COBOL-ašima ako ovo ipak radi samo za sebe.
Na osnovu dobijenog materijala (preko osobe koja je nekad radila u RC nekog
SUP-a - valjda oni dele te brojeve) zaključujem sledeće:
1. U svakom regostarskom području (šta god da je) postoji neka knjiga u koju
se za svaki dan državljani upisuju redom (uz eventualne preskoke, vidi
dalje) i to mučkarci od 001, a žene od 501 nadalje. Valjda se novorođeni
upisuju po nekom automatizmu, a svi izuzeci (pridošli iz tuđine, gazda
Jezdina žena i sl.) pod prvim slobodnim brojem kad stignu do upisa.
2.
Uputstvo je pisano za glupe službenike i ima primere ali i dalje je
nejasno šta treba raditi u slučaju 4) :
- da li se samo računa druga kontrolna cifra (sa istih prvih 12 cifara)
povećavanjem za 1 zadnjeg trocifrenog broja a same te tri cifre
ostaju na starom kako su bile (prema uputstvu bi i taj broj trebalo
promeniti-uvećati)
- ili se stvarno menja JMBG građana da bi se uklopila regularna
kontrolna cifra. Ovo drugo povlači da se neki redni brojevi u knjizi
preskaču u startu zbog kontrolnih cifara (oko 10% njih).
Moja pretpostavka je da je uputstvo pisano za samo kreiranje JMBG i da
tu stvarno ima preskočenih brojeva, što će reći da u praksi provere broja
ovi neregularni slučajevi ne bi trebalo da se dese. Molim sve koji ovo
čitaju i imaju neke JMBG na raspolaganju da provere da li se dešava da
računajući ovako dobiju ostatak 10 pri deljenju i jave da mi ostali
znamo na čemu smo povodom ovog pitanja.
3. Opisani algoritam je dobar kod kreiranja JMBG, ali za kontrolu da li je
kontrolna cifra dobra ili ne (to mi radimo uglavnom, zar ne?) je lakše i
brže sledeće:
Svih 13 cifara se množe redom brojevima: 7 6 5 4 3 2 7 6 5 4 3 2 1
( da, poslednja, 13. sa 1 ) i saberu. Zbir mora biti deljiv sa 11.
Toliko oko JMBG.
Do sada sam imao prilike da vidim i kontrolnu cifru (znak) za ISBN kod
knjiga. Opet se radi o modulo 11 aritmetici. Ovde, međutim, kontrolna cifra
može biti i 10 i tada se zamenjuje znakom "X". Provera je na sledeći način:
broj se očisti od blankova i crtica ukoliko postoje (to vole da stavljaju,
da bi odvojili celine za koje ne znam šta znače tačno). Zatim se od zadnje
cifre do prve (unatraške) cifre ISBN ("X"=10) množe redom sa 1,2,3,4,...
koliko već cifara ima. Zbir mora biti deljiv sa 11.
Na kraju, čemu služe ove kontrolne cifre? Pri unosu su relativno česte
greške. Najčešće se radi o permutaciji cifara i o pogrešno unetoj cifri. U
oba slučaja (ako nema drugih grešaka) metod sa kontrolnom cifrom mora 100%
da signalizira grešku. Ne znam kolika je verovatnoća otkrivanja višestrukih
grešaka, o tome bi mogao neko upućeniji, ali verovatno bitno veća nego kod
recimo običnog zbira. Pošto je 11 prost broj, kod jedne pogrešne cifre,
metod može i da predvidi šta je najverovatnije pogrešno uneto.
Toliko od mene, a ako neko zna za druge podatke koji se štite kontrolnim
ciframa, molim da podeli radost saznanja sa drugim smrtnicima koji te podatke
(treba da) kontrolišu.
Srdačan pozdrav,
Milan Dražić,
matematičar
bavi se bazama podataka za život
a numeričkom analizom za slavu
algoritmi.117janko,
> Uputstvo je pisano za glupe službenike i ima primere ali i
> dalje je nejasno šta treba raditi u slučaju 4) :
> - da li se samo računa druga kontrolna cifra (sa istih
> prvih 12 cifara) povećavanjem za 1 zadnjeg trocifrenog
> broja a same te tri cifre ostaju na starom kako su bile
> (prema uputstvu bi i taj broj trebalo promeniti-uvećati)
> - ili se stvarno menja JMBG građana da bi se uklopila
> regularna kontrolna cifra. Ovo drugo povlači da se neki
> redni brojevi u knjizi preskaču u startu zbog kontrolnih
> cifara (oko 10% njih). Moja pretpostavka je da je uputstvo
> pisano za samo kreiranje JMBG i da tu stvarno ima
> preskočenih brojeva, što će reći da u praksi provere broja
> ovi neregularni slučajevi ne bi trebalo da se dese. Molim
> sve koji ovo čitaju i imaju neke JMBG na raspolaganju da
> provere da li se dešava da računajući ovako dobiju ostatak
> 10 pri deljenju i jave da mi ostali znamo na čemu smo
> povodom ovog pitanja.
Probao sam. U bazi od nekoliko stotina, nema nijednog broja
koji bi se okarakterisao kao "za preskakanje." Zato sam ubeđen
da se algoritam poštuje: neki redni brojevi SE PRESKAžU (što
nedvosmisleno piše u onom uputstvu).
> Na kraju, čemu služe ove kontrolne cifre? Pri unosu su
> relativno česte greške. Najčešće se radi o permutaciji
> cifara i o pogrešno unetoj cifri. U oba slučaja (ako nema
> drugih grešaka) metod sa kontrolnom cifrom mora 100% da
> signalizira grešku. Ne znam kolika je verovatnoća
> otkrivanja višestrukih grešaka, o tome bi mogao neko
> upućeniji, ali verovatno bitno veća nego kod recimo
> običnog zbira. Pošto je 11 prost broj, kod jedne pogrešne
> cifre, metod može i da predvidi šta je najverovatnije
> pogrešno uneto.
E, ovo bih baš voleo da mi objasni neki matematičar upućeniji
od mene (ovo su filozofska pitanja, a ne odnose se direktno na
JMBG): zašto baš moduo 11? Zar u određivanju ovih brojeva nisu
kritičnije težine cifara a ne moduo? Zar moduo ne bi mogao da
bude i 10?
algoritmi.118dragisak,
║ 4) ako je ostatak pri deljenju jednak 1, za kontrolni broj ne uzima
║ se 10, jer kontrolni broj ne može biti dvocifren nego se broj koji
║ izražava kombinaciju pola i rednog broja za lica rođena istog datuma
║ (V grupa cifara matičnog broja) uvećava za 1 i način određivanja
║ kontrolnog broja se ponavlja.
Ovo se razlikuje od onog mog algoritma (po njemu je u ovom slučaju
kontrolni broj jednak nula). Da li neko ima matični broj
sa zadnjom cifrom 0, da proveri ? Onaj algoritam koji sam ja dao
koristi se već par godina za vođenje matičnih knjiga rođenih u Kraljevu.
Do sada nisam čuo da je bilo nekih primedbi na to.
algoritmi.119snemcev,
SOR mi je malo pobrkao lončiće, ali mislim da se ovde vodila diskusija
o žiro računima. Dakle...
>> a N je redni broj, i to ti brojevi N idu redom, dakle recimo postoje
>> žiro računi tipa 60811-601-10, pa onda 60811-601-11 i tako dalje,
>> "rupe" uglavnom dolaze od firmi koje su vremenom propadale,
>> integrisale se itd.
Nisi u pravu. U broju žiro računa poslednja cifra je kontrolna. Dakle
65500-625-21 označava drugu firmu u klasi 625 u filijali 500 u Vojvodini
tj. Kikindi. Ona jedinica na kraju je kontrolna cifra.
Pogledaj malo i spiskove čekova kod predaje na naplatu. Daj tri spiska
i neće imati susedne brojeve, ali ako zanemariš poslednju cifru, shvatićeš
da je sve OK i da je ta poslednja cifra ponovo kontrolna. Izgleda da je
SDK (da ne kažem SPPFN) otišao daleko u kontoli ispravnosti podataka.
algoritmi.120snemcev,
>> Zne li neko još neke brojeve, koje do sada nismo pomenuli, a koji u
>> sebi sadrže dodatne korisne informacije?
Imaš li čekove Jugobanke? Prva dva broja označavaju tvoju matičnu banku,
sledećih pet su broj tvog računa i poslednja je kontrolna.
algoritmi.121snemcev,
>> šifra oblika udruživanja (termin iz drugog vremena ;), žiro račun...
čiro račun ima kontrolnu cifru.
algoritmi.122miljko,
> Da li neko zna neki algoritam za crtanje kruga sem
> Bresham's algorithm i trigonometrijskog nacina.
Ako nije kasno...
U Raccunarima 24 (str 56.), tekst 'osam krugova kredom' elaborira
tematiku crtanja krugova.
Inacce, po mom skromnom missljenju, jedan od boljih cclanaka u
Raccunarima, ever.
algoritmi.123dr.grba,
Ne mogu da precutim, mada ne mogu ni konkretno da pomognem :
Pre cetiri - pet godina, dok sam vrzmao po nekoj beogradskoj knjizari,
naleteo sam na neku idiotski jeftinu knjigu (sto je ne kupih, ***** *** *****!)
naslova "Informacioni sistemi u organima uprave" ili nesto slicno. Detaljnih
podataka o knjizi se ne secam, imala je ociglednu formu udzbenika i bavila se,
je li, naslovljenom temom.
Dobro se secam, na samom pocetku knjige, poglavlje 1.1 ili slicno, bilo je
detaljno opisano modeliranje JMBG, cak je prilozeno i par tabela koje su
nosile u sebi nekakve nomenklature.
I stoga bi mozda bio kunst iskopati tu knjigu. Ona bi sigurno pomogla.
Kad je ne kupih, #@$#$^^&^* !!! ))):
Pozdrav, dr ÔpŰa
algoritmi.124janko,
> Imaš li čekove Jugobanke? Prva dva broja označavaju tvoju
> matičnu banku,
Beobankine.
O kom broj pričaš, broju čeka? Kod mene ti brojevi rastu
linearno.
A čeksum u broju tekućeg računa? Ima ga ili ne?
algoritmi.125janko,
> Ovo se razlikuje od onog mog algoritma (po njemu je u ovom
> slučaju kontrolni broj jednak nula). Da li neko ima
> matični broj sa zadnjom cifrom 0, da proveri ? Onaj
Kao što rekoh. Ja pokušao da proverim. U bazi do koje sam
došao, ako je 0 na kraju, nastala je isključivo od 11 a ne od
10. Tj. nema brojeva koji bi se po onom algoritmu preskočili.
Po meni, dakle, stvarno se brojevi preskaču.
algoritmi.126bulaja,
│O kom broj pricas, broju ceka? Kod mene ti brojevi rastu linearno.
└───
Pretpostavljam o broju tekuceg racuna (cekovne kartice), on bi trebalo
da ima neki checksum (ima ga kod mene - Slavija banka, a izgleda i kod
ostalih banaka).
algoritmi.127ndragan,
/ - da li se samo računa druga kontrolna cifra (sa istih prvih 12
/ cifara) povećavanjem za 1 zadnjeg trocifrenog broja a same te tri
Ne, nego se zamenjuje, dakle postoje nemogući brojevi (statistički,
svaki jedanaesti je nemoguć) i ako neko naleti na nemoguć broj,
dodeljuje mu se sledeći.
Veći je problem što se može desiti da se ti brojevi dodeljuju na malo
više 'registarskih područja' nego što može da pokrije dvocifrena šifra.
U prvo vreme sam mislio da je to redni broj upisa u matičnu knjigu
rođenih (ili useljenih) ili državljana, ali takve knjige postoje i po
selima. Srećna okolnost je što ta brojka kreće svakog dana od 1, pa može
malo da se zonira (svakom selu po 20 brojeva dnevno i gotovo).
/ Toliko od mene, a ako neko zna za druge podatke koji se štite
/ kontrolnim ciframa, molim da podeli radost saznanja sa drugim
/ smrtnicima koji te podatke (treba da) kontrolišu.
Od maja prošle godine broj računa treba da je pod kontrolom po modulu 11
(bez ostatka 10). To je SDK uvela radi TK prenosa; za primenu toga ima
više modela, s tim da je model 99 (bez kontrole) kao ukinut (?). Obično
se koristi model 05, ima format 05-xxxxxxx-yyyyyyy - grupa sa xxxx se
kontroliše po mod11, grupa sa yyyy ne.
TK prenos znači da uplata mo(nu)mentalno ide teleksom iz jedne SDK u
drugu, i važeća je bez da se čeka da virman stigne. Modul 11 je način da
se kontroliše valjanost prenosa.
algoritmi.128ndragan,
/ Pogledaj malo i spiskove čekova kod predaje na naplatu. Daj tri spiska
Banatska Banka uporno izdaje čekove bez kontrolne cifre.
algoritmi.129dragisak,
║ Kao što rekoh. Ja pokušao da proverim. U bazi do koje sam
║ došao, ako je 0 na kraju, nastala je isključivo od 11 a ne od
║ 10. Tj. nema brojeva koji bi se po onom algoritmu preskočili.
║ Po meni, dakle, stvarno se brojevi preskaču.
Jesi li uporedio onaj algoritam koji sam ja dao sa onim drugim ? Koji
daje 'bolje' rezultate ?
algoritmi.130dejanr,
>> > šifra oblika udruživanja (termin iz drugog vremena ;), žiro račun...
>>
>> čiro račun ima kontrolnu cifru.
Može li malo detaljnije? Da li misliš na žiro ili na tekući račun? Ja
sam prilično ubeđen da žiro računi (barem oni koji pripadaju RO, kao
i žiro računi građana u Beobanci) nemaju kontrolnu cifru.
algoritmi.131janko,
> Jesi li uporedio onaj algoritam koji sam ja dao sa onim
> drugim ? Koji daje 'bolje' rezultate ?
Očigledno je da brojeve koje odbacuje tvoj algoritam odbacuje i
onaj drugi. Očigledno je tvoj NE odbacuje neke brojeve koje
odbacuje onaj drugi.
U toj bazi koju imam, jednostavno nije bilo brojeva koje bi
tvoj program pustio a onaj drugi ne bi. Zaključak, izgleda da
su brojevi generisani po 'onom drugom,' strožem kriterijumu.
Što opet znači da su u _____ (kom beše gradu? Izvini, zaboravio
sam, ali ti ponovi) falširali? Eto problema! Zamisli koliko je
falš brojeva, koje će sada ispravno napisani programi da
odbacuju, a jadnik ni kriv ni dužan, ima nekompatibilan broj,
i šta će onda?!? "Druže, (gospodine) vaš broj je neispravan."
A on? Kome da objasni da su neki služebnici slabije ukapirali
algoritam? Šta da radi sa silnim dokumentima?
algoritmi.132janko,
> Veći je problem što se može desiti da se ti brojevi
> dodeljuju na malo više 'registarskih područja' nego što
> može da pokrije dvocifrena šifra. U prvo vreme sam mislio
> da je to redni broj upisa u matičnu knjigu rođenih (ili
> useljenih) ili državljana, ali takve knjige postoje i po
> selima. Srećna okolnost je što ta brojka kreće svakog dana
> od 1, pa može malo da se zonira (svakom selu po 20 brojeva
=========================
> dnevno i gotovo).
====== !!!!!
Ehhh, dipl. matemetičaru! ;)
Recimo da je ceo Beograd jedno evidenciono mesto (koja još ne
umemo da nazovemo).
Neka Beograd ima 2 miliona stanovnika. Neka je broj rođenih
jednak broju umrlih u istom vremenskom periodu. Ako je životni
vek 50 godina, za 50 godina se rodi 2 miliona ljudi. To je
40000 godišnje, ili 109 beba dnevno. Neka su 51% muške, to mu
dođe 56 muških beba dnevno u dvomilionskom gradu. (*)
Ili, selo iz tvog teksta (dvadeset mali muški deca dnevno) ima
sedamsto hiljada stanovnika. ;) (Ili, možda nije pravoslavno
nego... ;)
---
(*) Zanimljivo je da je, kada je počela ova priča, i meni dve i
po cifre izgledalo, odoka, malo, ali mi je na ovakav rezon
skrenuo pažnju jedan prijatelj (kome je nedavno istekla
pretplata na Sezamu, tek toliko da se zna. Kaže, sada ima dva
sata dnevno više:).
algoritmi.133mjova,
>>> čiro račun ima kontrolnu cifru.
a da li broj telefona sadrži kontrolnu cifru? ;)
nego, janko (on je 'kriv' za lanac poruka ;) bi mogao lepo da popakuje
poruke sa algoritmima za sve te razne čeksume i da okači neđe ovde.
možda nekome promakne..
algoritmi.134bpetrovic,
*> U odnosu na koje druge algoritme za crtanje kruga su spori?
*> Sa cime si ih poredio, pa si zakljucio da su spori?
Pogledaj konferenciju PC.PROG temu algoritmi ... imas algoritam
za crtanje kruga bez realnih promenjivih ....
algoritmi.135spantic,
>*> U odnosu na koje druge algoritme za crtanje kruga su
>*> spori? Sa cime si ih poredio, pa si zakljucio da su
> spori?
>
> Pogledaj konferenciju PC.PROG temu algoritmi ... imas
> algoritam za crtanje kruga bez realnih promenjivih ....
Pošto je reč o standardnom "školskom" algoritmu, da to Milan ne zna
verovatno bi pun PMF bio studenata koji bi urlikali da im se vrate
pare :)
algoritmi.136dejanr,
>> Neka Beograd ima 2 miliona stanovnika. Neka je broj rođenih
>> jednak broju umrlih u istom vremenskom periodu. Ako je životni
>> vek 50 godina, za 50 godina se rodi 2 miliona ljudi. To je
>> 40000 godišnje, ili 109 beba dnevno. Neka su 51% muške, to mu
>> dođe 56 muških beba dnevno u dvomilionskom gradu. (*)
>>
>> Ili, selo iz tvog teksta (dvadeset mali muški deca dnevno) ima
>> sedamsto hiljada stanovnika. ;)
>>
>> (*) Zanimljivo je da je, kada je počela ova priča, i meni dve i
>> po cifre izgledalo, odoka, malo, ali mi je na ovakav rezon
>> skrenuo pažnju jedan prijatelj...
Ima kod Pereljmana ("Zanimljiva matematika") priča o nekom "pabu"
u kome je matematičar objasnio prisutnima šta je verovatnoća, oni
nekako shvatili, i sad ih on pita kolika je verovatnoća da će
sledećih 100 ljudi koji prođu ulicom biti muškarci. Obzirom da je
to negde oko 2^-100 što je za sve praktične primene jednako nuli,
svi su bili spremni da se u proizvoljan iznos klade da se to neće
desiti. I kladili su se, beše u neki bicikl. A onda je naišla
kolona vojnika... ;>
U datom primeru, šta li se radi onoga dana koji nastupa 9 meseci
posle (daleko bilo ;) raspada elektroenergetskog sistema? ;)
algoritmi.137dragisak,
║ Što opet znači da su u _____ (kom beše gradu? Izvini, zaboravio
║ sam, ali ti ponovi) falširali? Eto problema! Zamisli koliko je
║ falš brojeva, koje će sada ispravno napisani programi da
║ odbacuju, a jadnik ni kriv ni dužan, ima nekompatibilan broj,
║ i šta će onda?!? "Druže, (gospodine) vaš broj je neispravan."
║ A on? Kome da objasni da su neki služebnici slabije ukapirali
║ algoritam? Šta da radi sa silnim dokumentima?
Koliko sam ja ukapirao, moj algoritam uvek radi. Nije mi jasno kako
može da se desi da propusti neispravan broj. Napomena je jedino da se
'moj' algoritam ne može koristiti za ODREĐIVANJE novog matičnog broja
nego samo za KONTROLU već postojećeg.
Inače što se tiče pomenutog grada (Kraljevo, Leskovac ...) tu ne bi smelo
da ima problema koje si opisao. Evo o čemu se radi. Matične službe NE
određuju matični broj građana (MBG) nego to radi murja. Kada se dete
rodi oni ga upišu u matičnu knjigu rođenih ali privremeno bez matičnog
broja. Onda oni pošalju podatke o dotičnom detetu Tamo-gde-treba, a oni
mu odrede MBG koji se onda upiše u matičnu knjigu. Dakle, ovaj se algoritam
koristi samo zato da bi se spreičilo da oni bezveznjaci po opštinama
upisuju gluposti u bazu podataka. Kako to panduri izračunavaju, nemam
pojma.
algoritmi.138janko,
> nego, janko (on je 'kriv' za lanac poruka ;) bi mogao lepo
> da popakuje poruke sa algoritmima za sve te razne čeksume
> i da okači neđe ovde. možda nekome promakne..
Do sada su samo dva algoritma dovoljno precizna:
- za brojeve faktura (poslao dejanr)
- za matičini broj (poslao Milan Dražić) (dragisak je dao
nešto jednostavniji, pa verujem da je zato ovaj bolji)
Za brojeve žiro i tekućeg računa sada ljudi tvrde da postoje
kontrolne sume, ali još niko nije prikazao algoritam.
Inače, ma kako to izgledalo, ja nisam ni moderator ni tako
nešto. Uz to, čini mi se da (još) nema smisla kačiti komadiće
diskusije. Možda tek kada se skupi dovoljno algoritama da bi
postojala potreba da se sistematizuju (sumnjam?). Za sada, kome
treba, na dodir tastature može da pokupi celu temu.
algoritmi.139ndragan,
/ Ehhh, dipl. matemetičaru! ;)
Da. Matematika, a ne račun.
/ 40000 godišnje, ili 109 beba dnevno. Neka su 51% muške, to mu
žuj, šifra ne sme da pukne. Pa neka svim bebama iz Prćilovice taj brojač
počinje od 041 a iz Džambukovice na 061, i neka nikad ne prebace 044
odnosno 064 (ako jedna rodi četvorke), i stvar je sistemski rešena.
Uzmi u obzir da je u vreme kad je jebi_ga_broj uvođen trebalo prvo
iznumerisati postojećih dvadesetak miliona ljudi, a to je onda već 'šira
društvena akcija', i da se moglo očekivati udarničko upisivanje, ako
treba, drugovi. Za takve slučajeve, za udarne dane, mogla se očekivati
koja stotina na pojedinim mestima. Hoću da kažem da šifra nije
predimenzionirana; na bilo kom delu šifre da skineš jednu cifru,
rizikuješ da ti pukne kroz koju godinu.
/ Ili, selo iz tvog teksta (dvadeset mali muški deca dnevno) ima
A šta misliš šta rade kad im odjednom nestane struje? :)
algoritmi.140madamov,
******
A onda je naišla kolona vojnika... ;>
******
Primer sa nekog fakulteta: Pita profa studenta na ispitu koja je
verovatnoća da će iz špila sa 52 karte izvući sedmicu herc, na šta ovaj
odgovara 50%. Pita ga profa kako to, a on odgovara: "Pa lepo, 'oš je izvuć,
ne'š je izvuć.". B)))
algoritmi.141ematic,
> da ima problema koje si opisao. Evo o čemu se radi. Matične
> službe NE određuju matični broj građana (MBG) nego to radi
> murja. Kada se dete rodi oni ga upišu u matičnu knjigu rođenih
> ali privremeno bez matičnog broja. Onda oni pošalju podatke o
> dotičnom detetu Tamo-gde-treba, a oni mu odrede MBG koji se
> onda upiše u matičnu knjigu. Dakle, ovaj se algoritam
Tačno tako. Ja sam za klinca morao da tražim broj u lokalnoj
žandarmeriji, a rođen je u Kraljevu.
algoritmi.142snemcev,
>> O kom broj pričaš, broju čeka? Kod mene ti brojevi rastu
>> linearno.
Jok bre, o broju tekućeg računa! Recimo
15-70-13317-6
gde je samo 13317 broj mog računa, 15-70 je banka (nešto kao 15-Novi
Sad, 70-Glavna filijala Kikinda), a 6 je kontrolna cifra. A brojevi
čekova idu linearno, s tim što je PŠ i ovde izuzetak. Kod njih izgleda
nema pravila. Ili pak ima?
algoritmi.143snemcev,
>> Pretpostavljam o broju tekuceg racuna (cekovne kartice), on bi
Broj tekućeg računa i broj čekovne kartice nisu isti! I brojevi čekovnih
kartica idu linearno, kao i brojevi čekova.
algoritmi.144snemcev,
>> Banatska Banka uporno izdaje čekove bez kontrolne cifre.
I Vojvođanska banka dd Novi Sad, Glavna filijala Kikinda. Kao da su
deo iste banke (a i jesu :)))
algoritmi.145janko,
> nekako shvatili, i sad ih on pita kolika je verovatnoća da
> će sledećih 100 ljudi koji prođu ulicom biti muškarci.
> Obzirom da je to negde oko 2ž-100 što je za sve praktične
> primene jednako nuli, svi su bili spremni da se u
> proizvoljan iznos klade da se to neće desiti. I kladili su
> se, beše u neki bicikl. A onda je naišla kolona vojnika...
> ;>
:) A taj koji je pokrenu opkladu ima strica u kasarni, pa
pričao s njim tog jutra. :) Sjajno.
> U datom primeru, šta li se radi onoga dana koji nastupa 9
> meseci posle (daleko bilo ;) raspada elektroenergetskog
> sistema? ;)
I ovo nije ništa neobično. To su osobine toka novorođenih.
Nigde nisam tvrdio da je raspodela baš ravnomerna, ali čisto
sumnjam da je onako žešće eksponencijalna. Uostalom, ako iko
može da proveri koliko je maksimalno rođenih u Beogradu u
jednom danu, još uvek ne verujem da je broj ni blizu onih
granica koje postoje: oko četrsto četrdeset beba jednog pola u
jednoj evidencionoj jedinici. Još bolja mera bi bila, rekordni
broj rođenih u jednom danu na Kosovu?
algoritmi.146janko,
> Koliko sam ja ukapirao, moj algoritam uvek radi. Nije mi
> jasno kako može da se desi da propusti neispravan broj.
> Napomena je jedino da se 'moj' algoritam ne može koristiti
> za ODREĐIVANJE novog matičnog broja nego samo za KONTROLU
> već postojećeg.
SVAKI metod sa kontrolnom sumom, kada se koristi za proveru
ispravnosti, MOčE da propusti neispravan broj (u smislu, broj
sa kontrolnom sumom koja je ispravan, ali broj koji nije onaj
koji smo želeli). 'Tvoj' algoritam nije izuzetak. A ni onaj
'jači.' I taj 'jači' pokriva sledeći slučaj: otkucan je broj
koji tamo onaj rezultat (pre kontrolne cifre) daje 10. I on
kaže 'jok, ovo je neispravno.' U tom trenutku 'tvoj' algoritam
kaže 'ajde da vidim da li je čeksum cifra nula, ako jeste, onda
je ispravan.
> broja. Onda oni pošalju podatke o dotičnom detetu
> Tamo-gde-treba, a oni mu odrede MBG koji se onda upiše u
> matičnu knjigu. Dakle, ovaj se algoritam
Super. Ako se koristi samo za proveru, onda teško da je bilo
neke štete.
algoritmi.147snemcev,
>> Može li malo detaljnije? Da li misliš na žiro ili na tekući račun? Ja
>> sam prilično ubeđen da žiro računi (barem oni koji pripadaju RO, kao
>> i žiro računi građana u Beobanci) nemaju kontrolnu cifru.
čiro račun je u pitanju. Nešto kao
xxyyy-zzz-aaa-bbbbbbc
xx - Okrug, šta li!? Dejanr je ostavio brojeve za pojedina mesta.
yyy - Oznaka filijale
zzz - Grupa računa (npr. 601-preduzeća
603-kojekakve društvene organizacije
604-delovi preduzeća sa posebnim ovlašćenjima
623-banke
625-ostale finansijske organizacije)
aaa - Nekakve podgrupe (pretpostavljam)
bbbbbbb - broj samog računa
c - kontrolna cifra
Za sve to evo i primer
65500-623-16 (u stvari, 65500-623-000-0000016)
65 - Vojvodina
500 - Kikinda
623 - banka
000 - nema podgrupe (ili šta je već to)
1 - broj računa
6 - kontrolna cifra
algoritmi.148snemcev,
>> - za brojeve faktura (poslao dejanr)
Kako mi je ovo promaklo? Koja je poruka u pitanju?
algoritmi.149kuki,
> odgovara 50%. Pita ga profa kako to, a on odgovara: "Pa lepo, 'oš je izvuć,
> ne'š je izvuć.". B)))
Verovatnoća za bilo koji događaj je 50%
Ili će se desiti, ili neće :))) (marfi)
algoritmi.150dr.grba,
>> I Vojvodanska banka dd Novi Sad, Glavna filijala Kikinda. Kao da su
>> deo iste banke (a i jesu :)))
E, nemaju kontrolnu cifru; nemaju ni pare.
Zato je moja malenkost preselila svoj ziro-racun u Invest banku.
Ima kontrolni broj, ima pare. (((: Veselje za mali deca.
Zlobo, pravac Invest banka!
Pozdrav, dr ÔpŰa
algoritmi.151janko,
> Uzmi u obzir da je u vreme kad je jebi_ga_broj uvođen
> trebalo prvo iznumerisati postojećih dvadesetak miliona
> ljudi, a to je onda već 'šira društvena akcija', i da se
> moglo očekivati udarničko upisivanje, ako treba, drugovi.
> Za takve slučajeve, za udarne dane, mogla se očekivati
> koja stotina na pojedinim mestima. Hoću da kažem da šifra
Ali, opet se brojevi daju ne po danu prijave, već po danu
ROĐENJA!
algoritmi.152janko,
>>> - za brojeve faktura (poslao dejanr)
>
> Kako mi je ovo promaklo? Koja je poruka u pitanju?
Ne da ti je promaklo, nego... Otprilike ista priča o fakturama
je bila i u prethodnoj konferenciji u kojoj je bila tema
algoritmi. Priča o fakturama je mesecima starija od ove sad
priče o matičnom broju i ostalim.
Adrese su:
PC.PROG: (možda sada ima .1 na kraju?) 9.12 od aprila 92.
PC.PROG.2: 1.73 od marta 93.
algoritmi.153janko,
> čiro račun je u pitanju. Nešto kao
>
> xxyyy-zzz-aaa-bbbbbbc
Dajte, ako je neko blizak sa bankama, da iskopa te podatke
direktno od njih. Da konačno i to proveravamo automatski.
Valjda je i njima lakše kada dobijaju više ispravnih brojeva?
(Sad se setih -- nije! Ovako imaju izgovor da zadržavaju pare
koje nikom ne uplaćuju, dok se taj neko ne seti da interveniše
;)
algoritmi.154snemcev,
>> Valjda je i njima lakše kada dobijaju više ispravnih brojeva?
>> (Sad se setih -- nije! Ovako imaju izgovor da zadržavaju pare
>> koje nikom ne uplaćuju, dok se taj neko ne seti da interveniše
>> ;)
Jok! Provereno tri puta (toliko znam sigurno)! Eksperimentalno sam pustio
neke bezveze pare na račun kojekakvih poreza i umesto poslednje (kontrolne)
cifre koja je bila 9, stavio sam 4 (dakle umesto 2159 stavio sam 2154).
Sutra na izvodu tj. na košuljici (ko razume, shvatiće), kao račun na koji
su otišle pare pisalo je 2159 iako je na virmanu bilo 2154. I tako tri puta
sa tri različita računa (za svaki slučaj, uvek porezi ;) Za mene je ovo
dovoljan dokaz da SPPFN u Kikindi zna šta radi.
algoritmi.155snemcev,
>> PC.PROG: (možda sada ima .1 na kraju?) 9.12 od aprila 92.
>> PC.PROG.2: 1.73 od marta 93.
Thanx, potražiću.
algoritmi.156snemcev,
>> Zato je moja malenkost preselila svoj ziro-racun u Invest banku.
>> Ima kontrolni broj, ima pare. (((: Veselje za mali deca.
Mislim da ću te potražiti povodom ove tvoje izjave ;))))
algoritmi.157ndragan,
/ Ali, opet se brojevi daju ne po danu prijave, već po danu
/ ROĐENJA!
Za novorođene da, a ne znam kako ide sa naknadno upisanim. Uostalom,
čim imaš teoretsku mogućnost da negde imaš više od 99 odjednom, moraš
imati tri cifre i gotovo.
algoritmi.158ndragan,
/ 65500-623-16 (u stvari, 65500-623-000-0000016)
/ 65 - Vojvodina
Ne znam baš, ovde je 66900-601-xxxxx; 66900 je SDK Zrenjanin, 601 kako
si rekao, i xxxxx sam broj žiro računa. Za radnje je strava jedna, drže
ih na nekom podpodračunu, pa ima tridesetak znakova, od čega pešes "-".
algoritmi.159janko,
> / Ali, opet se brojevi daju ne po danu prijave, već po
> danu / ROĐENJA!
>
> Za novorođene da, a ne znam kako ide sa naknadno upisanim.
> Uostalom, čim imaš teoretsku mogućnost da negde imaš više
> od 99 odjednom, moraš imati tri cifre i gotovo.
Pa ima dve i po cifre: 000-499 za muške, 500-999 za ženske.
Naknadno upisani se OPET upisuju po datumu rođenja. Ili,
informatičkim rečnikom, u "ključ" ovog broja se računa i datum
rođenja. Ili, još preciznije rečeno, čitav broj je ključ.
algoritmi.160dgrbic,
:: Za novorođene da, a ne znam kako ide sa naknadno
:: upisanim. Uostalom, čim imaš teoretsku mogućnost da negde
:: imaš više od 99 odjednom, moraš imati tri cifre i gotovo.
"Znate, ponestalo nam brojeva... Dođite sutra ili idite u Niš pa se tamo
upišite..."
algoritmi.161janko,
> :: upisanim. Uostalom, čim imaš teoretsku mogućnost da
> negde :: imaš više od 99 odjednom, moraš imati tri cifre i
> gotovo.
>
> "Znate, ponestalo nam brojeva... Dođite sutra ili idite u
> Niš pa se tamo upišite..."
Nema šanse. Pročitaj priču od pre.
algoritmi.162snemcev,
>> Ne znam baš, ovde je 66900-601-xxxxx; 66900 je SDK Zrenjanin, 601
>> kako si rekao, i xxxxx sam broj žiro računa. Za radnje je strava
>> jedna, drže ih na nekom podpodračunu, pa ima tridesetak znakova, od
>> čega pešes "-".
Pogledaj košuljicu od izvoda. 100% imaš i podgrupu. Raspitaj se malo po
firmi na koji žiro račun plaćate poreze - sigurno je 66900-843-215-?
(ili 846). Još jednostavnije, otiđi u SUP i pitaj koliko treba da
uplatiš za produženje pasoša ili nešto slično. Daće ti neki račun i
trebao bi kao treći broj da ima 215. Ali, čak i ako ga na virmanu ili
uplatnici izostaviš, pare nepogrešivo stižu na pravi račun. Kako? Samo
SDK (SPPFN) zna!
algoritmi.163ndragan,
/ uplatnici izostaviš, pare nepogrešivo stižu na pravi račun. Kako? Samo
Baš sam malopre sreo jednu poznanicu, radila u SDK, sad je u finoj
muriji. Što ne pročitah ovo ranije, mogao sam da je priupitam. Imaju
neki sistem, čini mi se da u tim brojevima ima i nekih suvišnih stvari,
ali logika je izgleda jako dobro postavljena. Ko zna kolika može da bude
greška u broju, a da se i dalje prepozna, i obratno: ko zna koliko broj
može da bude tačan, a da pare opet zalutaju :)
algoritmi.164dejanr,
Prigodno pitanje: zna li neko kako se za zadatu godinu može izračunati
kog datuma pada Uskrs? Nešto se prisećam da je to išlo po modulu 11 i da
je pisalo u nekoj od onih knjiga tipa "večiti kalendar", ali ne mogu da
nađem ni jednu takvu.
Pročitah u enciklopediji da Uskrs pada "u prvu nedelju posle punog meseca
koji pada posle prolećne ravnodnevice". Obzirom da su oba fenomena čisto
astronomske prirode, pomislih da Pravoslavni i Katolički Uskrs padaju u
isti dan, i nađoh u nekim programerskim novinama algoritam za Katolički,
ali na primeru ove godine greši, dakle ne padaju u isti dan :( žak se ne
razlikuju za 14 dana, pošto izgleda da mi pogrešno računamo kada je
ravnodnevica, a to pomera i taj "pun mesec" svake godine za različit
broj dana.
algoritmi.165bulaja,
│Prigodno pitanje: zna li neko kako se za zadatu godinu moze izracunati
│kog datuma pada Uskrs? Nesto se prisecam da je to islo po modulu 11 i da
│je pisalo u nekoj od onih knjiga tipa "veciti kalendar", ali ne mogu da
│nadem ni jednu takvu.
└───
Ima u NFLib (za Clipper) funkcija FT_EASTER() za koja bi trebalo radi
bas to, ali takodje gresi (?) za ovu godinu - daje 11. april. Algoritam
koji se koristi je Knuth-ov (iz "The Art..", deo 1.3.2), verovatno je
isti kao taj koji si ti nasao.
Ako se ne varam pun mesec je bio prosle nedelje/ponedeljka, moguce je da
su nesuglasice oko toga kada je bas pun mesec :).
algoritmi.166ppekovic,
>> Ima u NFLib (za Clipper) funkcija FT_EASTER() za koja bi trebalo radi
>> bas to, ali takodje gresi (?) za ovu godinu - daje 11. april. Algoritam
>> koji se koristi je Knuth-ov (iz "The Art..", deo 1.3.2), verovatno je
>> isti kao taj koji si ti nasao.
Ima na FFS-u programčić uskrs koji tačno (?) određuje kada
pada pravoslavni uskrs. S obzirom da je propratni tekst na srpskom
jeziku, verovatno je to delo našeg čoveka. Dakle, naš čoveče javi
se :) ili ako čoveka nema na sezamu: traži se "naš čovek" kriv za
program uskrs. Nalazaču vredna nagrada :)
Paya
algoritmi.167milan,
> Pročitah u enciklopediji da Uskrs pada "u prvu nedelju posle punog meseca
> koji pada posle prolećne ravnodnevice". Obzirom da su oba fenomena čisto
> astronomske prirode, pomislih da Pravoslavni i Katolički Uskrs padaju u
> isti dan, i nađoh u nekim programerskim novinama algoritam za Katolički,
> ali na primeru ove godine greši, dakle ne padaju u isti dan :( žak se ne
> razlikuju za 14 dana, pošto izgleda da mi pogrešno računamo kada je
> ravnodnevica, a to pomera i taj "pun mesec" svake godine za različit
> broj dana.
Prvo, načelno si pogrešio, čak i da se računanje Uskrsa
obavlja po astronomskim pravilima. Jer "prva nedelja posle prvog
punog meseca u proleće", zahvaljujući razlici u kalendaru, može
napraviti razliku između Uskrsa po julijanskom i po
gregorijanskom kalendaru i do 4 nedelje! Jer, ako recimo proleće
po gregorijanskom kalendaru padne 22 marta, Uskrs može nastupiti
već u nedelju 23. (ako bude nedelja i ako je 22. bio pun mesec).
Međutim, onda pun mesec nastupa tek 29 dana kasnije - 20. aprila
(i to je prvi pun mesec posle prolećnje ravnodnevice (5. april)
po julijanskom kalendaru) pa julijanski Uskrs može da bude tek
27. aprila.
Stvar komplikuje okolnost da se Uskrs NE računa po
astronomskim pravilima (stvarni pun mesec i stvaran sat i minut
prolećne ravnodnevice) već po DEKRETNOM punom mesecu i DEKRETNOJ
ravnodnevici koje su za julijanski kalendar tablicama (poslednji
put) utvrđivane u XI a za gregorijanski kalendar u XVI veku!
Jedan od Nikejskih vaseljenskih sabora (početak IV veka,
iako je tačna godina još uvek sporna) je ustanovio hronološke
tablice tzv *pashalije*. Pashalije su se sastojale iz
periodičnih ponavljanja bogosluženja prema datumima koji su se
raspoređivali unutar *indiktiona*. Indiktioni se sastoje od 532
godine, posle čega se pashalije u potpunosti ponavljaju.
Dvanaesti indiktion je bio (zatvoreni) interval između 345 i 876
godine (a prvi, računalo se od "nastanka sveta", je počinjao
jedno 5400 godina p.n.e - po crkvi je Big Beng izgleda zaista
bio veoma skoro ;))) ostalo je lako izračunati. Pashalije su
pravljene i prema dogmatskim intervencijama. Tako su se tablice
morale praviti tako da 1) Uskrs ne pada u isti dan sa jevrejskom
Pashom (antisemitizam;)), 2) Uskrs pada najbliže (!) prvom
prolećnjem polumesecu (ima nešto u Bibliji da je bio polumesec
kada je predmetni raspet, mada mi nije jasno kako se to može
uskladiti sa zahtevom da padne u prvu nedelju posle ravnodnevice?!).
Već u XIV veku je Matija Blastar primetio da se za dva dana,
ovako utvrđeni, pashalni polumeseci razlikuju od astronomskih
ali je tek u XVI veku kalendar reformisan jer su primetili
grešku koja akumuliše jedan dan na 128 godina.
Svi "algoritmi" su zapravo zapisi pravilnosti uočenih u ovim
pashalijama unutar indiktiona (ponavljanja su nužna zbog
samerljivosti intervala koji se tretiraju) i "omanjuju"
otprilike jednom u pedesetak godina.
I ja imam nekoliko "algoritama" za gregorijanski Uskrs ali
ne i za julijanski. Za julijanski valja pitati Patrijaršiju.
Svake godine mi to oko Uskrsa padne na pamet, ali zaboravim.
Dobro da si me podsetio. Raspitaću se!
Pl poz M
algoritmi.168mjova,
> Pročitah u enciklopediji da Uskrs pada "u prvu nedelju
> posle punog meseca koji pada posle prolećne ravnodnevice".
> Obzirom da su oba fenomena čisto
zavisi od godine do godine: čini mi se da je katolički uskrs bio
prošle nedelje, a naš ove. takođe, prošle godine je naš uskrs bio
istog dana kad i njihov. svašta, čak kažu da uma situacija da može
pasti i poslednje nedelje u aprilu.
imam neki programčić koji daje datum uskrsa (našeg) za sve moguće
godine, pa koga zanima nek proba. nema nikakve poruke o tome ko je
napisao ni da li je (c) ili PD.
uskrs.arjalgoritmi.169dejanr,
>> > Pročitah u enciklopediji da Uskrs pada "u prvu nedelju posle punog meseca
>> > koji pada posle prolećne ravnodnevice". Obzirom da su oba fenomena čisto
>> > astronomske prirode,
>>
>> Prvo, načelno si pogrešio, čak i da se računanje Uskrsa
>> obavlja po astronomskim pravilima. Jer "prva nedelja posle prvog
>> punog meseca u proleće", zahvaljujući razlici u kalendaru, može
>> napraviti razliku između Uskrsa po julijanskom i po
>> gregorijanskom kalendaru i do 4 nedelje! Jer, ako recimo proleće
>> po gregorijanskom kalendaru padne 22 marta, Uskrs može nastupiti
>> već u nedelju 23. (ako bude nedelja i ako je 22. bio pun mesec).
>> Međutim, onda pun mesec nastupa tek 29 dana kasnije - 20. aprila
>> (i to je prvi pun mesec posle prolećnje ravnodnevice (5. april)
>> po julijanskom kalendaru) pa julijanski Uskrs može da bude tek
>> 27. aprila.
Hmmmm... zar je julijanska ravnodnevica (gregorijanskog) 5 aprila?
Manje-više početak proleća, ali ravnodnevica je (već i po imenu) vreme
kada je dužina dana jednaka dužini noći. (Gregorijanskog) 5. aprila
je dan "primetno" duži od noći, dakle to teško može da se računa u
RAVNOdnevicu. Ja sam mislio da se smatra da je julijanska ravnodnevica
u istom trenutku kad i gregorijanska, samo se taj datum drugačije piše.
No izgleda da je julijanski kalendar još gluplji no što sam mislio :(
>> Svi "algoritmi" su zapravo zapisi pravilnosti uočenih u ovim
>> pashalijama unutar indiktiona (ponavljanja su nužna zbog
>> samerljivosti intervala koji se tretiraju) i "omanjuju"
>> otprilike jednom u pedesetak godina.
Ja sam, ne znam zašto, mislio da se datum Uskrsa ponavlja po modulu
11. U stvari, znam i zašto sam tako mislio: one godine kada sam se
ja rodio 16. april je pao na treći dan Uskrsa. Isto se ponovilo i
o mom 11. rođendanu, a i o 22. Kladio bih se da će se ponoviti i o
33-ćem. Mada, kad razmislim, nešto ne bih rekao da se ikad desilo
da mi rođendan padne na Veliki Petak, kao juče :)
Pogledaću kako radi onaj program što je mjova poslao.
algoritmi.170darone,
>> Ima u NFLib (za Clipper) funkcija FT_EASTER() za
>> koja bi trebalo radi bas to, ali takodje gresi
>> (?) za ovu godinu - daje 11. april.
Ne greši, katolički Uskrs je bio pre nedelju dana.
darone
algoritmi.171skerl,
│ 33-cem. Mada, kad razmislim, nesto ne bih rekao da se ikad desilo
│ da mi rodendan padne na Veliki Petak, kao juce :)
└────
Pa, srecan ti rodjendan!
Pozdrav,
Skerl.
algoritmi.172dragisak,
║ Prigodno pitanje: zna li neko kako se za zadatu godinu može
║ izračunati kog datuma pada Uskrs? Nešto se prisećam da je to išlo po
║ modulu 11 i da je pisalo u nekoj od onih knjiga tipa "večiti
║ kalendar", ali ne mogu da nađem ni jednu takvu.
Ja sam svojevremeno napravio jedan takav program. Prilažem ga uz
poruku. Nažalost od tada je prošlo mnogo vremena, sors sam izgubio. :(
Znam samo da je bilo nešto komplikovano. Algoritam sam našao u nekoj
knjizi o crkvenim praznicima, na kraju je bio mali BASIC program
koji je to izračunavao (imao je par bagova). Nažalost nemam ni tu knjigu
niti moj C sosr. :((
uskrs.zipalgoritmi.173dragisak,
║ ... Nažalost nemam ni tu knjigu niti moj C sosr. :((
Eureka !!
Nakon mukotrpnog preturanja po hrpama papira, našao sam onaj 'uskršnji'
algoritam. Srećom, nemam naviku da sređujem svoju sobu, tako da mi se
po stolovima vuku papiri još od studija.
/* (c) Dragisa Krsmanovic 1989. */
main(argc,argv)
int argc;
char *argv[];
{
int god, dan, i, j, k;
char mesec[10];
if (argc!=2) printf("Usage: uskrs godina"), exit(0);
if ((god=atoi(argv[1]))<=0) printf("Greska!"), exit(0);
i = god % 19 ;
j = god % 4 ;
k = god % 7 ;
i = ((19*i)+15) % 30 ;
j = (2*j + 4*k + 6*i +6) % 7 ;
dan = 4 + i + j ;
if ( dan<=30 )
strcpy(mesec,"aprila") ;
else
dan -= 30, strcpy(mesec, "maja");
printf("Pravoslavni Uskrs je po novom kalendaru %2.2d. %s %4.4d. godine",
dan, mesec, god);
}
algoritmi.174dejanr,
Hvala za source, videćeš ga u "Bajtovima lične prirode", mislim da će
i mnoge druge interesovati :)
Koliko vidim, formule su prilično "abrakadabra" ali važno je da radi :)
algoritmi.175zormi,
* Svi "algoritmi" su zapravo zapisi pravilnosti uočenih u ovim
* pashalijama unutar indiktiona.
U prevodu, lakše je ugraditi tabelu Uskrsa nego ih računati :)
algoritmi.176milan,
>* Svi "algoritmi" su zapravo zapisi pravilnosti uočenih u ovim
>* pashalijama unutar indiktiona.
>
> U prevodu, lakše je ugraditi tabelu Uskrsa nego ih računati :)
Ah, to već ne. :)
Naime ugraditi tabelu od 532 različita datuma nije baš neko
zadovoljstvo. Verovatno se za sasvim tačne programe koristi prvo
"algoritam" a onda se pojedine, "trapave", godine izuzmu u stilu
if(godina==trt)printf("Uskrs pada %2.2d maja",datum);.
Mada, sad mi je palo na pamet, možda se uskrsi ponavljaju
unutar malih a ne velikih indiktiona, pa je onda i tabelu lakše
ugraditi.
Na kraju ćete me naterati da odem do popova da proverim
stvar. ;))
Pl poz M
algoritmi.177milan,
Ecce!
> i = god % 19 ;
> j = god % 4 ;
> k = god % 7 ;
19*4*7 = 532, tj. niz datuma Uskrsa se ponavlja posle
velikog indiktiona odnosno svakih 532 godine. Znači ipak sam
dobro nab'o 532 jer kada sam napisao u prethodnoj poruci
presek'o sam se da je interval 632 a ne 532! ;)))
Pl poz M
algoritmi.178ematic,
U vezi prethodne rasprave, napomenuo bih samo da se verski praznik
pominjan pod imenom "uskrs" u pravoslavnom kalendaru naziva *vaskrs*.
algoritmi.179almi,
Kako da date tačke A[i] (x,y,z) preslikavam na ekran u perspektivi tj.
┌───────────────────────┐
│ \ / │
│ \ / │
│ \ / │
│ \ / │
│ \ / │
│ / \ │
│ / \ │
│ / \ │
│ / \ │
│ / \ │
│/ │
└───────────────────────┘
u ovakvom stilu da mi bude preslikan 3D prostor u dotični prostor.
Unapred zahvalan Mišel.
algoritmi.180ppekovic,
>> Kako da date tačke A[i] (x,y,z) preslikavam na ekran u perspektivi tj.
Preporučujem ti knjigu g. Majkića "Kompjuterska grafika"
(nisam siguran za naziv). Možeš je naći, kao što ti zkr reče, u RK
Nikola Tesla. Pored nje, potraži i neki udžbenik iz analitičke
geometrije koju ćeš morati dobro da savladaš da bi se uspešno
bavio grafikom.
Paya
algoritmi.181almi,
Hvala nbavio sam knjigu i ona ima sve što mi je potrebno.
Pozdrav Mišel.
algoritmi.182prvul,
ŮKako da date tačke A[i] (x,y,z) preslikavam na ekran u perspektivi tj.
Ů▄▄
Ima to u svakoj knjizi koja se bavi računarskom grafikom... kao i matrice
(iz kojih se izvode forumule) za sve ostale projekcije i transformacije. Ako
baš ne možeš da nađeš, javi pa ću napisati, ali je priča malo poduža (ne
volim da dajem formule bez objašnjenja skoro isto onoliko koliko ne volim
kada mi daju formulu bez objašnjenja).
Pozdrav,
Prvul
algoritmi.183ndragan,
/ Kako da date tačke AŠiĆ (x,y,z) preslikavam na ekran u perspektivi tj.
Eve ga jedno moje programče vo Qbejzikot, crta istina dve slike (za levo
i desno oko), crvenu i zelenu, pa se može lepo sve u 010H stereo gledati
kroz one naočari što su izašle u Zabavniku pre godinu-dve, ili ih ima i
uz neke knjige iz nacrtne ('nacrtna geometrija u anaglifskim slikama'):
3d.bas:
DECLARE SUB fig ()
DECLARE SUB doshow ()
DECLARE SUB roth (fi!)
DECLARE SUB rotv (fi!)
DECLARE SUB dodraw (ofs!)
DECLARE SUB project (i!, of!)
OPTION BASE 1
last = 12
dist = 80
ofs = 5.8
lastt = 1
DIM SHARED telo(200, 5)
DIM SHARED veza(200, 2)
CALL fig
SCREEN 12
CALL doshow
; ovde malo čitucka tastaturu da izabere rotiranje, uvećanje,
; razmicanje/primicanje očiju
DO
ky$ = ""
DO WHILE ky$ = ""
ky$ = INKEY$
LOOP
IF ky$ = CHR$(27) THEN
STOP
END IF
IF LEFT$(ky$, 1) = CHR$(0) THEN
kx = ASC(MID$(ky$, 2, 1))
SELECT CASE kx
CASE &H4D
CALL roth(-.1)
CASE &H4B
CALL roth(.1)
CASE &H50
CALL rotv(.1)
CASE &H48
CALL rotv(-.1)
END SELECT
ELSE
SELECT CASE ky$
CASE "+"
ofs = ofs * 1.05
CASE "-"
ofs = ofs / 1.04
CASE "/"
dist = dist * 1.05
CASE "*"
dist = dist / 1.045
END SELECT
END IF
CALL doshow
LOOP
SUB dodraw (ofset) ; iscrtavanje svih linija
SHARED lastt, last, telo(), veza()
FOR i = 1 TO lastt
CALL project(i, ofset)
NEXT i
FOR i = 1 TO last
a1 = veza(i, 1)
a2 = veza(i, 2)
LINE (telo(a1, 4), telo(a1, 5))-(telo(a2, 4), telo(a2, 5))
NEXT i
END SUB
; crtaj sve dvaput za levo i desno oko
SUB doshow
SHARED last, lastt, ofs
CLS
COLOR 4
CALL dodraw(ofs)
COLOR 2
CALL dodraw(-ofs)
END SUB
SUB fig ; učitavanje figure. ovde bi trebalo ubaciti neki
; zglavan fajl selektor
SHARED lastt, last, telo(), veza()
OPEN "i", #4, "kocka.fig"
INPUT #4, lastt
WHILE lastt
INPUT #4, telo(lastt, 1), telo(lastt, 2), telo(lastt, 3)
l = lastt
INPUT #4, lastt
WEND
lastt = l
INPUT #4, last
WHILE last
INPUT #4, veza(last, 1), veza(last, 2)
l = last
INPUT #4, last
WEND
last = l
END SUB
;********* ovo ti treba: projekcija 3d u 2d
SUB project (i, of)
SHARED lastt, last, telo(), veza(), dist
STATIC tc
tc = telo(i, 3) - dist
telo(i, 4) = ((telo(i, 1) * dist - of * telo(i, 3)) / tc + 320)
telo(i, 5) = telo(i, 2) * dist / tc + 200
END SUB
; horizontalna rotacija
SUB roth (fi)
STATIC i, tx, ty
SHARED lastt, last, telo(), veza()
FOR i = 1 TO lastt
tx = COS(fi) * telo(i, 1) + SIN(fi) * telo(i, 3)
ty = -SIN(fi) * telo(i, 1) + COS(fi) * telo(i, 3)
telo(i, 1) = tx
telo(i, 3) = ty
NEXT i
END SUB
; i vertikalna
SUB rotv (fi)
STATIC i, tx, ty
SHARED lastt, telo()
FOR i = 1 TO lastt
tx = COS(fi) * telo(i, 2) + SIN(fi) * telo(i, 3)
ty = -SIN(fi) * telo(i, 2) + COS(fi) * telo(i, 3)
telo(i, 2) = tx
telo(i, 3) = ty
NEXT i
END SUB
I, to je to. Evo i primera fajla sa koordinatama:
kocka.fig:
1,60,60,60
2,60,60,-60
3,60,-60,60
4,60,-60,-60
5,-60,60,60
6,-60,60,-60
7,-60,-60,60
8,-60,-60,-60
0
1,1,2
2,3,4
3,5,6
4,7,8
5,1,3
6,2,4
7,5,7
8,6,8
9,1,5
10,2,6
11,3,7
12,4,8
0
Prvo ide niz koordinata u formatu redni_broj,x,y,z, i jedna linija koja
sadrži samo 0, da znam da nema više. Onda spisak parova tačaka koje čine
duži, u formatu redni_broj_para, rb_prve, rb_druge.
Nabaci negde onaj crveno-zeleni cviker, mnogo dobro izgleda (na VGA) kad
ti kocka izađe iz ekrana. Tj. ne znam gde sam se zeznuo, na Atariju je
izgledalo mnogo bolje.
Ovo je inače rađeno prostim vektorskim računom, tražim presek zraka koji
ide iz oka i prolazi kroz projektovanu tačku, sa ravni koja prolazi kroz
koordinatni početak normalno na pravu oko-centar. Pošto ima dva oka,
onda o stvari imam dve tačke malo pomerene levo i desno (to je onaj
ofset, stavi na nulu i izbaci duplo crtanje ako hoćeš 2D) u odnosu na
teoretsku tačku gledišta.
Ako makneš neku lovu za ovo, meni godišnja pretplata ističe u decembru :)
algoritmi.184snemcev,
>> U vezi prethodne rasprave, napomenuo bih samo da se verski praznik
>> pominjan pod imenom "uskrs" u pravoslavnom kalendaru naziva *vaskrs*.
A ja bih napomenuo da je gospodin dekan teološkog fakulteta izjavio za
štampu da su oba naziva ravnopravna - ako on nezna, niko nezna.
algoritmi.185ematic,
> A ja bih napomenuo da je gospodin dekan teološkog fakulteta
> izjavio za štampu da su oba naziva ravnopravna - ako on nezna,
> niko nezna.
Nisam znao šta je gospodin dekan izjavio. Ja samo kažem da u
kalendaru piše *vaskrs* ("Kalendar za prostu 1993. godinu", izdanje
svetog arhijerejskog sinoda SPC).
algoritmi.186asterix,
> Preporučujem ti knjigu g. Majkića "Kompjuterska grafika"
> (nisam siguran za naziv). Možeš je naći, kao što ti zkr reče, u
> RK Nikola Tesla. Pored nje, potraži i neki udžbenik iz
> analitičke
Gde je RK Nikola Tesla ? :)
algoritmi.187robert,
>> Gde je RK Nikola Tesla ? :)
U Timočkoj 18. to ti je u okolini C. krsta. tj. kad se spustiš pored
pozorišta nadole pa jedna od ulica koje su paralelne sa onom gde voze
trole.
algoritmi.188spantic,
>>> U vezi prethodne rasprave, napomenuo bih samo da se
>>> verski praznik pominjan pod imenom "uskrs" u
> pravoslavnom kalendaru naziva *vaskrs*.
>
> A ja bih napomenuo da je gospodin dekan teološkog
> fakulteta izjavio za štampu da su oba naziva ravnopravna -
> ako on nezna, niko nezna.
Koliko se sećam isto je izjavio da SPC preferira i podržava *vaskrs*, a
ne *uskrs*.
algoritmi.189mdimitrijevic,
Da li bi neko mogao da jos malo objasni 3D grafiku rotaciju kocke i slicno.
Sa nekim primerom.
Please,
Pozdrav,
Marjan Dimitrijevic
algoritmi.190sslavko,
Izvinjavam se što upadam u razgovor ali me živo interesuje kakve veze
ima ova rasprava sa algoritmima?
algoritmi.191dejanr,
>> Izvinjavam se što upadam u razgovor ali me živo interesuje kakve veze
>> ima ova rasprava sa algoritmima?
Pa, radi se o IMENU algoritma :) Ali bi bilo mnogo bolje da se diskusija
polako seli u CIVILIZACIJA/o.jeziku.
algoritmi.192ematic,
> Izvinjavam se što upadam u razgovor ali me živo interesuje
> kakve veze ima ova rasprava sa algoritmima?
Pa, razlikuju se algoritmi za određivanje *uskrsa* i *vaskrsa*...
...ma pusti, naša posla... :))) Neću više :))))))
algoritmi.193asterix,
> U Timočkoj 18. to ti je u okolini C. krsta. tj. kad se spustiš
> pored pozorišta nadole pa jedna od ulica koje su paralelne sa
> onom gde voze trole.
OK. Idem u ponedeljak da pogledam. Hvala :)
algoritmi.194spantic,
> Izvinjavam se što upadam u razgovor ali me živo interesuje
> kakve veze ima ova rasprava sa algoritmima?
Pa, krenulo je od diskusije o algoritmu određivanja datuma Vaskrsa, a
završili na terminologiji ;)
algoritmi.195spantic,
> Da li bi neko mogao da jos malo objasni 3D grafiku
> rotaciju kocke i slicno. Sa nekim primerom.
Najjasnije će ti biti ako nabaviš literaturu u kojoj su detaljno objašnjene
trensformacije. Ima dosta toga da se iznese da bi principi bili jasni.
Implementacija je onda lakša stavka.
algoritmi.196dragisak,
║ Pa, razlikuju se algoritmi za određivanje *uskrsa* i *vaskrsa*...
║
║ ...ma pusti, naša posla... :))) Neću više :))))))
Da ne bude zabune, ja sam dao algoritam za USKRS, a ne VASKRS. ;>
A, vaskoliko Srpstvo nek ponudi vaskršnji algoritam, pa da kažemo da
vaistinu postoje dva algoritma. ;>>>
algoritmi.197ematic,
> Da ne bude zabune, ja sam dao algoritam za USKRS, a ne VASKRS.
> ;>
>
> A, vaskoliko Srpstvo nek ponudi vaskršnji algoritam, pa da
> kažemo da vaistinu postoje dva algoritma. ;>>>
Dobro de, samo sam malko bacio kosku, pa da vidim ko će da se zakači
;). Valjda vam je jasno iz moje prethodne poruke :). Drago mi je da
se podigla prašina :))))).
p.s. Pušio sam Ronhil, išao sam u Rovinj na more -10 bodova :))))
algoritmi.198asterix,
> U Timočkoj 18. to ti je u okolini C. krsta. tj. kad se spustiš
> pored pozorišta nadole pa jedna od ulica koje su paralelne sa
> onom gde voze trole.
Da ali tamo više nema knjige :(((( Prodata je :( Da li neko zna
gde može da se kupi ?...
algoritmi.199asterix,
> Hvala nbavio sam knjigu i ona ima sve što mi je potrebno.
> Pozdrav Mišel.
Gde si je nabavio? Reci mi, i ja bih je rado :) kupio !
Pozdrav Nenad :)
algoritmi.200vpekovic,
Koliko je meni poznato, Vaskrs se praznuje u nedelju, prvu posle
punog meseca iza prolecne ravnodnevnice. U slucaju da je pun mesec
u petak, subotu ili nedelju, Vaskrs se slavi druge nedelje. Prvi
pun mesec iza prolecne ravnodnevnice je uvek u martu. U slucaju da
je pun mesec pre 19. marta, Vaskrs se slavi prve nedelje posle
drugog punog meseca u aprilu (ovo je da Vaskrs ne bi bio pre
jevrejske Pashe). Iz navedenog proizilazi da Vaskrs moze pasti od
22. marta (kao sto je bio slucaj 1915. a bice i 2010. godine) do
25. aprila (kao sto je bio 1983. godine). Datumi su naravno po
starom kalendaru.
U periodu od 1850. do 2050. godine pravoslavni Vaskrs i katolicki
Uskrs se slave istog datuma 60 puta: 1851, 1852, 1855, 1858, 1859,
1862, 1865, 1868, 1871, 1876, 1879, 1882, 1885, 1886, 1889, 1892,
1895, 1896, 1906, 1909, 1912, 1915, 1916, 1919, 1922, 1930, 1933,
1936, 1939, 1942, 1943, 1946, 1950, 1953, 1957, 1960, 1963, 1966,
1974, 1977, 1980, 1984, 1987, 1990, 2001, 2004, 2007, 2010, 2011,
2014, 2017, 2025, 2028, 2031, 2034, 2037, 2038, 2041, 2045 i 2048.
godine.
algoritmi.201peca.st,
!-> p.s. Pušio sam Ronhil, išao sam u Rovinj
!-> na more -10 bodova :))))
Gde ne udarih CopyLeft na - X bodova, sad bih bio bogataš...
Peđa.
P.S. Sori na poruci.
algoritmi.202vpekovic,
Sto se tice brojeva tekucih i ziro-racuna neke od banaka imaju
a neke nemaju kontrolnu cifru. Verovatno je to jos na nivou banaka
da odlucuju.
Kod BEOBANKE broj tekuceg racuna ima oblik:
aaaaa-bbb-cc-ddd-eeee-fffffff
a ziro-racuna kod iste banke:
aaaaa-bbb-cc-ddd-gg-fffffff.
Kod INVESTBANKE broj tekuceg racuna ima oblik:
aaaaa-bbb-cc-hhhh-ii-fffff-j
a kod POSTANSKE STEDIONICE:
aaaaa-bbb-cc-fffffff.
Znacenja su sledeca:
aaaaa - operativni broj sluzbe
bbb - grupa racuna (620 - banke, 283 - postanska stedionica)
cc - vlasnik racuna (16 - BEOBANKA, 63 - INVESTBANKA)
ddd - ekspozitura
eeee - pretpostavljam da oznacava vrstu racuna
fffffff - broj racuna
gg - pretpostavljam da oznacava da li su u pitanju gradjani,
radne organizacije, ...
hhhh - nije mi poznato
ii - nije mi poznato
j - kontrolna cifra
Operativni broj sluzbe oznacava nadleznu jedinicu sluzbe za platni
promet i finansijski nadzor u Republici Srbiji. Neki od brojeva su:
60800 Beograd glavna filijala
60812 Beograd Cukarica
60808 Beograd Lazarevac
60807 Beograd Obrenovac
60803 Beograd Palilula
60802 Beograd Savski Venac
60801 Beograd Stari Grad
60804 Beograd Beograd-4
60806 Beograd Beograd-6
60811 Beograd
60816 Beograd Vozdovac
60809 Beograd Mladenovac
60813 Beograd Sopot
60805 Zemun
60815 Novi Beograd
61300 Cacak
61700 Kragujevac
61800 Kraljevo
61900 Krusevac
62100 Leskovac
62200 Loznica
62500 Nis
62600 Novi Pazar
62800 Pirot
62900 Pozarevac
63000 Prijepolje
63100 Prokuplje
63200 Smederevo
63500 Jagodina
63600 Sabac
63700 Uzice
63900 Valjevo
64100 Vranje
64200 Zajecar
65100 Backa Palanka
65200 Backa Topola
65300 Becej
65500 Kikinda
65700 Novi Sad
66000 Pancevo
66300 Sombor
66600 Subotica
66800 Vrsac
66900 Zrenjanin
68600 Gnjilane
68200 Kosovska Mitrovica
68300 Pec
68400 Pristina
68500 Prizren
algoritmi.203vpekovic,
Sto se brojeva cekova tice kod BEOBANKE oni idu linerno i nemaju
nikakvu kontrolnu cifru. To su jednostavno osmocifreni brojevi koji
sekvencijalno rastu. Ukoliko ih slucajno ne izmesaju (desilo se to
par puta), svaka serija cekova koju dobijete je veca od one prethodne.
Ne samo da ne postoji kontrolna cifra vec ne postoji ni kontrola
cekova koje su vam izdali. Iako se kroz izvod proknjizi prvi broj
ceka iz serije i broj cekova koji ste dobili, nekoliko puta mi se
desilo da mi se u izvodu pojavi cek koji nije moj (broj je pogresno
unet ili su neke cifre permutovane).
Kod POSTANSKE STEDIONICE je vec druga stvar. I kod njih se cekovi
oznacavaju osmocifrenim brojevima pri cemu se prvih sedam cifara
sekvencijalno uvecava za jedan u seriji a osma cifra je kontrolna.
Sto je interesantno kod PS nije pravilo da naredna serija bude veca
od prethodne. Izgleda kao da se pocetni broj serije odredjuje random.
To znaci da mora da postoji i istorija koje su vam vec serije izdate
da se ne desi da "ubodu" istu seriju. Na koji nacin se odredjuje
kontrolna cifra za broj ceka nije mi poznato ali bih voleo da znam.
U koliko je nekom na SEZAMU poznato molio bih ga za objasnjenje.
algoritmi.204dejanr,
>> Kod BEOBANKE broj tekuceg racuna ima oblik:
Hvala na zanimljivom prilogu, sigurno će zanimati mnoge koji pišu
programe koji barataju sa parama.
algoritmi.205wizard,
> P.S. Sori na poruci.
Ok, primamo izvinjenje. ;) A sad je obriši. ;>>
algoritmi.206snemcev,
>> Kod BEOBANKE broj tekuceg racuna ima oblik:
>>
>> aaaaa-bbb-cc-ddd-eeee-fffffff
Da se razjasnimo: ono aaaaa-bbb-cc je broj žiro računa banke koji se vodi
kod Službe za platni promet i finansijski nadzor i to ti SPPFN određuje,
a sve ono iza toga, banka sama po svom sopstvenom nahođenju uvodi. Isto važi
i za sve druge banke, štedionice, preduzeća itd.
Recimo, kad plaćaš račun, kao poziv na broj stavljaš broj računa, a kad na
pošti uplaćuješ preko opšte uplatnice na svoj tekući račun, kao poziv na
broj stavljaš broj tekućeg. I jedno i drugo određuje onaj ko izdaje račun
(odnosno otvara tekući račun).
algoritmi.207ficus,
hi
Ima li neko algoritam za prikazivanje pcx-fajlova
onaj na sezamu u fajlu nije bas najtacniji.
algoritmi.208peca.st,
!-> Ima li neko algoritam za prikazivanje
!-> pcx-fajlova onaj na sezamu u fajlu nije
!-> bas najtacniji.
Ne znam na koji misliš, ali onaj u pascal diru (samo tpu, nema source)
meni vrlo fino & lepo radi. Do duše, samo u rezoluciji 640 480 16. :(
Peđa.
algoritmi.209maksa,
Evo moje tužne priče:
Bakćem se sa jednom stvari koja se svodi na pitanje optimizacije,t.j.
traženje minimuma NEanalitički date funkcije (3 < n < 8 promenjivih).
Ovako mladom,zelenom i neiskusnom učinio mi se zanimljivim algoritam
prikazan u RAžUNARIMA br.? god.92.To je,elem,onaj tzv. "genetski algoritam".
Prihvatajući rizik da me ljudi smatraju neozbiljnim,ne budem ja lenj
(kao inače :)) pa napravim program koji po tamo izloženom principu
traži (eksperimenta radi) minimum funkcije dve promenjive.Algoritam mi
se učinio zgodnim zato što za razliku od onih koje poznajem (simplex,
steepest descent <- ne poznajem ih baš puno,a?) spada u tip "pohlepnih"
(greedy-oxford dictionary of mathematcs) što se dobro uklapa u prirodu
mog problema.Gorepomenuti program sam napravio u MS Basicu 7.1 (da se
odmah opravdam :)) zato što je on sa svojom Quick-okolinom,za mene kao
nekog ko se ne bavi profesionalno programiranjem,mnogo zgodniji od
DO edituj-prevedi-probaj-nerviraj se LOOP MS Fortrana,a u računanju
u proseku za oko 60-70% brži od TP 6.0.
Epilog: skoro totalni krah.
Tačke počnu da konvergiraju (wishfull thinking?) pa onda nastave da "veselo
skakuću" na sigurnoj udaljenosti od mesta lokalnog minimuma i tako u nedogled.
Dali neko ima ideju u čemu je stvar?
Meni je palo na pamet nekoliko odgovora:
a) Genetski algoritam je čista egzotika (s njim ne može da se uradi ništa
korisno)
b) Microsoft-ov generator slučajnih brojeva ništa ne valja (sluč. brojevi
se INTENZIVNO koriste u pomenutom algoritmu)
c) vidi pod a)
Aj'te ljudi ako boga znate,kažite mi dal' da se manem ćorava posla.
Bio bi jako zahvalan ako bi me neko uputio na literaturu iz te pro-
-blematike.Svi komentari su dobrodošli (čak i zlonamerni,al' ne pre-
-više).
Maksa
algoritmi.210milan,
Tačan odgovor je a) ali se za to ne dobija nagrada. :(
Spasa ti tu nema, postoji, naravno, prepuna biblioteka
literature iz numeričke analize al' jurenje minimuna
NEanalitičke funkcije je eksperimentalan a ne naučni posao.
Mogao bi, na primer, da splajnovima ili nekim hiperpovršima
u višedimenzionom prostoru analitički aproksimiraš funkciju pa
da joj onda tražiš minimum, međutim ako je NEanalitički data to
znači da je data tabelom a iz tabele se vidi koja joj je
najmanja vrednost! Ne razumem u čemu je problem?
Pl poz M
algoritmi.211maksa,
<><> Tačan odgovor je a) ali se za to ne dobija nagrada. :(
:((
<><> literature iz numeričke analize al' jurenje minimuna
<><> NEanalitičke funkcije je eksperimentalan a ne naučni
Ne razumem ovo: eksperimentalan, a ne naučni...
Dali bi pojasnili?
<><> posao. Mogao bi, na primer, da splajnovima ili nekim
<><> hiperpovršima u višedimenzionom prostoru analitički
<><> aproksimiraš funkciju pa da joj onda tražiš minimum,
Meni je to palo na pamet (i dobro se ugruvalo :)) ali sam
to odbacio baš zato što je meni palo na pamet. :)
Šalu na stranu,dali je to neko pokušao? Hoću reći,dali to postoji
kao registrovan način optimizacije?
Knjige koje ja imam o num. analizi (nemam puno) pominju razne
načine interpolacije,al' se nijedna ne bavi hiper-površima.:(
<><> međutim ako je NEanalitički data to znači da je data
<><> tabelom a iz tabele se vidi koja joj je najmanja
<><> vrednost! Ne razumem u čemu je problem?
Nisam hteo da budem opširan,pa sam ispao nejasan.:(
Stvar je ovakva:
Vrednosti (funkcije) se dobijaju numerički,iterativno kao output
programa.To znači da nisu u pitanju neke eksperimentalno dobijene
vrednosti koje su u nekoj tabeli,pa da sad meni treba najmanja od
njih.Ono što pokušavam je da nađem način za automatsko traženje
najmanje vrednosti u okviru mog programa.
Dali neko zna kakav je to Fletcher-Powell-ov metod?
Ili bar za neku literaturu iz TE oblasti (optimizacija,automatsko
traženje) ? Dolaze u obzir engleski,francuski i jezici naroda i
narodnosti RIP Jugoslavije.
pozdrav, Maksa
P.S. "Interpolation=the art of reading between the lines - in a table"
Carl-Erik Froberg
algoritmi.212milan,
> Dali neko zna kakav je to Fletcher-Powell-ov metod?
> Ili bar za neku literaturu iz TE oblasti (optimizacija,automatsko
> traženje) ? Dolaze u obzir engleski,francuski i jezici naroda i
> narodnosti RIP Jugoslavije.
Postoje tri biblioteke gde se, u ne baš pretranim ali
razumnim količinama, može naći ta vrsta literature - Matematički
fakultet, Matematički Institut (Akademija Nauka) i ETF. Kod nas
na MF ima čak cela katedra i studijska grupa koja se bavi
numerikom i optimizacijom na možeš nekog i da malo propitaš.
Pl poz M
algoritmi.213zolika,
>> Da li neko zna kakav je to Fletcher-Powell-ov metod?
Neko zna. Javi se na MAIL, pa da se dogovorimo.
algoritmi.214ndragan,
/ Vrednosti (funkcije) se dobijaju numerički,iterativno kao output
/ programa.To znači da nisu u pitanju neke eksperimentalno dobijene
Da nisu dobijene vrednosti malko blizu nuli pa da ti rečena rutina daje
simptome numeričke nestabilnosti, tj. da u okolini traženog minimuma
počinje da biva manje glatka nego inače? Probaj da ispitaš kako se
ponašaju 'izvodi' te funkcije u okolini minimuma. Ako mnogo skakuće,
moglo bi da bude to.
U tom slučaju preostaje da se poveća tačnost računa (dvostruka tačnost
promenljivih) ili da se malo prorešeta programče koje računa funkciju.
algoritmi.215maksa,
<><> Da nisu dobijene vrednosti malko blizu nuli pa da ti
<><> rečena rutina daje simptome numeričke nestabilnosti,
<><> tj. da u okolini traženog minimuma počinje da biva
<><> manje glatka nego inače? Probaj da ispitaš kako se
<><> ponašaju 'izvodi' te funkcije u okolini minimuma. Ako
<><> mnogo skakuće, moglo bi da bude to.
Ne,ne.Ako misliš na onaj nesretni Genetski Algoritam,
njega sam isprobavao na funkcijama 2 promenjive iz
zbirki za Matematiku 1,koje su "tipske" i analitički
rešive,a i "glatke".
Sa onim za šta mi cela stvar treba,G.A. nisam ni isprobao
(sva sreća) pa sad tražim neki proveren algoritam za nalaženje
minimuma.
Maksa
algoritmi.216janko,
> zbirki za Matematiku 1,koje su "tipske" i analitički
> rešive,a i "glatke".
Prvo što sam naučio iz numeričke analize kod pok. Dušana
Slavića je "na računaru nijedna funkcija nije glatka."
Verovao ili ne, to je tako.
algoritmi.217sjeremic,
Zadatak: Realizovati kretanje poligona po ekranu. Poligon je slika
sa n temena koji su spojeni duzima koje se međusobno mogu seći.
Pitanje: Kako efikasno realizovati brisanje stare slike?
Postojeća rešenja:
1) Zamena stranica slike - pravi probleme sa nekim karticama.
Iz neutvrđenih razloga puni deo slike đubretom, kao kad
je preklopljen prikaz grafičkog i tekstualnog ekrana,
samo mnogo gore.
2) Brisanje aktivne površine ekrana.
3) Prepisivanje poligona bojom pozadine. Neelegantno, zbog dvostrukog
preračunavanja nekih stvari - sporo.
Ima li ko neki bolji predlog?
algoritmi.218djelovic,
> Zadatak: Realizovati kretanje poligona po ekranu. Poligon je slika
> sa n temena koji su spojeni duzima koje se međusobno mogu seći.
Ako hoćeš imam nekoliko Dr. Dobb'a časopisa koji se bave baš
animacijom poligona. Ako hoćeš javi se pa da ugovorimo primopredaju.
algoritmi.219zzile,
> Zadatak: Realizovati kretanje poligona po ekranu. Poligon je
> slika sa n temena koji su spojeni duzima koje se medusobno mogu
> seci.
>
> Pitanje: Kako efikasno realizovati brisanje stare slike?
Resenje radi solidno brzo ali je malo komplikovano:
- napises proceduru koja crta liniju i pamti u neki vektor boje i
kordinate svih tacka "ispod" te linije (najbolje u asembleru :( )
nacrtaj_poligon { pomocu te procedure ( makar i na sarenoj pozadini)}
repeat
vrati_tacke_iz_vektora
nacrtaj_poligon { novi, naravno }
...
until ...
Pozdrav ZZile
algoritmi.220valhala,
Ko moze da mi pokaze neki brz algoritam za sortiranje.
U pitanju je gomila reci koja se sortira po korenu
prva cetiri slova.
Algoritam koji sam koristio je ubitacno spor:(
algoritmi.221dejanr,
>> Ko moze da mi pokaze neki brz algoritam za sortiranje.
>> U pitanju je gomila reci koja se sortira po korenu
>> prva cetiri slova.
Preporučujem tekst Zorana čivotića "Brže od najbržeg", "Računari 41",
strana 53. Tu je prezentiran jedan algoritam za sortiranje (radix
sort) koji je kao stvoren za to što tebi treba, a zbilja je munjevit.
Uopšte, vredi prelistati RIND - "Računari" su za ovih (skoro) 10 godina
pisali o mnogim vrlo korisnim stvarima.
algoritmi.222isekulovic,
>> Ko moze da mi pokaze neki brz algoritam za sortiranje.
Pogledaj Računare 86-88, ima serija tekstova o raznim algoritmima za
sortiranje.
algoritmi.223nnedovic,
>> Ko moze da mi pokaze neki brz algoritam za sortiranje.
>> U pitanju je gomila reci koja se sortira po korenu
>> prva cetiri slova.
Možeš da uzimaš reč po reč i da ih stavljaš u binarno stablo:
manji - levo, veći -desno. Posle samo pročitaš stablo u inorderu
i đotovo. Jes da jede memoriju, al je brz u peršun.