algoritmi.1toca,
Pišem jedan program i imam problem sa štampanjem, ne znam kako da izbegnem
'siročiće' i 'udovice'. Siroče je red teksta koji pripada jednoj celini (pa-
susu ili sl.) koji je prešao sam na sledeću stranu, a udovica isto to samo što
je ostala na prethodnoj strani
K│/tDsdfogsdepofhdsgohjsedrŠoghjkedtojhnsdetogjnsdgonsdognmsdgonm
eipogbjsdigbnsdŠoifgbndosigbnsdopignbosdignbosdginbosdgnibosdingb
eopifbneoifnboeaibneoifgnboeinboerinboetbneotinbeotniboetnboetnb
---------------------------------------------------------------- <- krej
sfoigneoirtgneoitnbhotnihborenbthornewbortnboern <- siroče
(red minusa '-' predstavlja kraj jedne strane)
sodufgnvoweruntepourtyhvpeotnvheoswtirnbvoewbntowertnboretnbret
rnuewtunworeitjbwoevhowernugcoweiurhvg3we5uthvwoerhgvosdfnvosdfnvgoseiur
wrigvowerhgvepowrhugvwoerhgvpweorhugvpweonpeoruvpeourhvgpeowurhgvpeowurh
ewourthvepwouheonfvndioj eitrj oietrjypoieptroiyjhpoewijc ooeit eoth
werghvpweorughv erotpoehvopehvrpoehoeh eptouvihepothvepohvpoehtyvpeohv
wrohfgweovurhpeouwhvgwpeovhwepouhvtweuhvpweotuvhpewtuhv <- udovica
-------------------------------------------------------------- <- kraj str.
writjvweiry3Šei5hyŠwerhybwesfovigaslfnvgsard'fgvweproiuhgvwe
werutghvqwpruoehvtgqwporhgvqwporhgvpoqwerhgvpoqwreuihgvqwer
yqwervythqw-4856vhqwolrehglshfgvpasoryhtvgaskjdvfnaswureytvba
WER8TYV AL CVAJoiehrtgviorwevnoiwrvepourtbnŠaqswvenŠqwertv
Nadam se da su vam ovi primeri pokazali šta su udovice i siročići.
Da li neko zna algoritam koji rešava ovo. Redove možete zamisliti i kao
deo sloga koji se sastoji od polja za tekst(red) i polja koje označava pasus.
Pomoći će mi bilo koje rešenje (pseudo jezik, Pascal, Clipper, Basic) sem onih
napisanuh u C-u ili Asembleru jer sam za njih nepoznajem nimalo.
Hvala▄╔ĐŚ,cÔxß.
algoritmi.2dcolak,
│ Nadam se da su vam ovi primeri pokazali šta su udovice i siročići.
│ Da li neko zna algoritam koji rešava ovo. Redove možete zamisliti i kao
│ deo sloga koji se sastoji od polja za tekst(red) i polja koje označava
Odredi kako znaš šta je paragraf (enter recimo), broj redove između
dva entera (razmaka između paragrafa) i vidi da li se pri brojanju
nailazi na kraj strane. Ako se nailazi, proveri broj redova u onom
pre i u onom posle "ivice" ekrana. Simple.. Ubilo se za C, no... ;)
Sledge DAMMIR!
algoritmi.3nbatocanin,
> Pišem jedan program i imam problem sa štampanjem, ne znam
> kako da izbegnem 'siročiće' i 'udovice'.
žini mi se da je dosta pravolinijski problem: štampaš pasus po pasus,
s tim što pre štampanja pasusa proveravaš koliko ima redova do kraja
strane. Ako vidiš da neće stati ceo pasus i da će biti prenet mali
broj redova na sledeću stranu, skraćuješ tekuću stranu za neki broj
redova. Slično i za udovice.
algoritmi.4zsiz,
Dali neko zna neku knjigu sa algoritmima za crtanje
linija, kriva itd.
HPozdrav.
algoritmi.5goxx,
Mislim da su takve stvari bile nekada u nekim praistorijskim računarima.
Doduše, to je bilo za komodor i spektrum, ali princip je isti, sve su
ostalo nijanse...
Goran
algoritmi.6markom,
*** Dali neko zna neku knjigu sa algoritmima za crtanje
*** linija, kriva itd.
Uh, jedan moj ortak je pominjao neku knjigu, u stila grafika kroz Turbo Pascal.
Pitaću ga da mi da pa ću ti reči jel to to, kao i ima knjige ...
algoritmi.7isekulovic,
>> Uh, jedan moj ortak je pominjao neku knjigu, u stila grafika kroz
>> Turbo Pascal. Pitaću ga da mi da pa ću ti reči jel to to, kao i ima
>> knjige ...
Ako misliš na Turbo Pascal sa grafičkim aplikacijam by A.Jorno, tu nema
ni a od algoritama, a i pisana je za TP trojku ili četvorku.
algoritmi.8mmitrovic,
Ů█▀█Ţ Uh, jedan moj ortak je pominjao neku knjigu, u stila grafika
Ů█▀█Ţ Pascal. Pitaću ga da mi da pa ću ti reči jel to to, kao i ima
To je knjiga "Turbo Vision i Grafika", i prilično je beskorisna
po pitanju grafike. Radi se u stvari o objektima koji rade sa
grafikom, sve u svemu prilično beskorisno. Prvi deo je OK, za
one koje malo znaju o TVisionu. Inače takvu knjigu (o algoritmima)
sam zadnji put video u Petnici (izdanje Imperial College, London)
pa sam prepisao par algoritama. Pa ako nekog interesuje...
algoritmi.9markom,
*** Ako misliš na Turbo Pascal sa grafičkim aplikacijam by A.Jorno, tu nema
*** ni a od algoritama, a i pisana je za TP trojku ili četvorku.
Znam za tu knjigu, a znam i par ortaka koji su je kupili, ali koliko sam razu-
meo, ovo nije to ...
algoritmi.10markom,
*** pa sam prepisao par algoritama. Pa ako nekog interesuje...
...Pa ne bilo ti teško ... :))
algoritmi.11ladislavs,
Ima li neko listing(pascal/c) ili algoritam programa za deljenje polinoma
polinomom? Potreban je jednom kolegi, deadline nedelja popodne.
Najzgodnije je da prilog šaljete na mail, da ne gušimo. Tnx.
ciLa.
algoritmi.12paki,
> Ima li neko listing(pascal/c) ili algoritam programa za deljenje
> polinoma polinomom? Potreban je jednom kolegi, deadline nedelja popodne.
> Najzgodnije je da prilog šaljete na mail, da ne gušimo. Tnx.
To bi trebalo i meni, pa ako neka dobra duša ima...
algoritmi.13m.hristodulo,
>> To bi trebalo i meni, pa ako neka dobra duša
>> ima...
Već sam poslao Cili ceo unit a Pakiju samo
polynome.divide (nadam se da će biti shvatljivo):
procedure polynome.divide ( p1 , p2 : polynome ) ;
var n1 , n2 , i , j : byte ;
begin
for i := 0 to maxdim do
coef [ i ] := 0 ;
n1 := p1.dim ;
n2 := p2.dim ;
for i := n1 downto n2 do
begin
coef [ i - n2 ] := p1.coef [ i ] div p2.coef [ n2 ] ;
for j := 0 to n2 do
p1.coef [ j + i - n2 ] :=
p1.coef [ j + i - n2 ] - coef [ i - n2 ] * p2.coef [ j ]
end
end ;
algoritmi.14omega,
Da li bi neko bio ljubazan da mi da pointer na konacno resenje vezano za
diskusiju o uklanjanju ansi sekvenci?
algoritmi.15dejanr,
Možda će vas zanimati fajl sa porukama sa BIX-a koje su vezane za
kriptografsku zaštitu podataka i razbijanje nekih šifara. Uvodna
poruka sledi:
==========
security/encryption #921, from gnikoloff, 1027 chars, Sun May 15 18:44:07 1994
Comment(s).
----------
TITLE: Videocrypt
I see that there is quite a lot of activity on the Internet in this area;
apparently the basic algorithm has been well and truly cracked. I guess you
can only implement a simple algorithm in the internal ROM of a smartcard.
An interesting point; does anyone know of any research into random numbers
whereby using tests such as the ones documented in Knuth, you can determine
the equation used by the PRBS (e.g if it were a linear congruential
generator, then the coefficients used). I assume unlimited access to the
pseudo-random number stream.
I surmise this is how Videocrypt was cracked. They were, after all, able
to reseed the random number algorithm at regular intervals via the
downlink to the encoder, so the generic algorithm would have had to have
been cracked.
Note to moderators: I regard speculation on this and related issues as
bona-fide discussion of encryption issues; I do not encourage or support
efforts to attack Videocrypt specifically.
(Hopefully that should keep your lawyers happy).
sifre.zipalgoritmi.16djelovic,
> Možda će vas zanimati fajl sa porukama sa BIX-a koje su vezane za
> kriptografsku zaštitu podataka i razbijanje nekih šifara.
Sad si me podsetio da treba da te ispravim: Kada smo u CIVILIZACIJI pričali
o filmu "Sneakers", ti si rekao da se tamo najverovatnije priča o RSA algoritmu
za public-key šifrovanje. Međutim, u Americi se za public-key šifrovanje u
državnim organima i bankama koristi takozvani DSS - Digital Signiture Standard.
Nevezano za to: Trenutno imam najnoviji Dr. Dobb's koji za temu broja ima
kriptografiju. U jednom članku koji se bavi veličinama ključeva autor
objašnjava da su veličine ključeva današnjih algoritama jednostavno previše
male, i da je za pravu sigurnost potrebno imati ključ od nekih 256 bitova kako
bi se efektivno odbili svi brute-force napadi. Kao primer navodi DES (!), koji
je sa svojih 56 bitova jednostavno previše slab: neki naučnik je Belovih
labaratorija je dizajnirao čipove i smislio celu mašinu koja bi mogla da
razbije DES za svega par sati. Cena pravljenja tog kompjutera: milion dolara.
Nešto što bi, priznaćete, svaka vlada mogla da plati ako bi im trebalo.
algoritmi.17szeman,
Već duže vreme pokušavam da nadjem zbirku knjiga 'The Art of Computer
Programming' od Knuth-a, ali bezuspešno. Ako neko zna...
algoritmi.18omega,
Da li je brzi crc-32 _sa_ ili _bez_ konsultacionih tabela?
algoritmi.19dejanr,
>> Da li je brzi crc-32 _sa_ ili _bez_ konsultacionih tabela?
Brže je sa tabelama, ali je zato program (sa sve tabelama) duži, tj.
zauzima više memorije.
algoritmi.20omega,
Ţ Brze je sa tabelama, ali je zato program (sa sve tabelama) duzi, tj.
Ţ zauzima vise memorije.
1kb duzi? Zar je to neka cifra?
algoritmi.21kriss,
˙˙ 1kb duzi? Zar je to neka cifra?
Jeste. Mnogo što šta može da stane u 1 kb. Jel treba primer?
algoritmi.22dejanr,
>> > Brze je sa tabelama, ali je zato program (sa sve tabelama) duzi, tj.
>> > zauzima vise memorije.
>>
>> 1kb duzi? Zar je to neka cifra?
Ja sam ti odgovorio na ono što si pitao, a da li je cifra ili nije, to
sam odluči. I razlika u brzini bi bila, šta znam, neki mikrosekund, i
to nije cifra.
algoritmi.23omega,
Ţ ˙˙ 1kb duzi? Zar je to neka cifra?
Ţ
Ţ Jeste. Mnogo sto sta moze da stane u 1 kb. Jel treba primer?
Ovo sam pitao vise da vidim da li zaista pricamo o istoj stvari :)
Ok, zaista je neki put (?) i 1 kb mnogo...
algoritmi.24omega,
Ţ Ja sam ti odgovorio na ono sto si pitao, a da li je cifra ili nije, to
Ţ sam odluci. I razlika u brzini bi bila, sta znam, neki mikrosekund, i
Ţ to nije cifra.
Hvala na odgovoru. Nego zar je to zaista tako malo (o ne, opet sam
poceo :) ) ubrzanje? ;)
algoritmi.25szinf,
Da li je neko zainteresovan za teorijsko razmatranje igre marienbad iz
kviza (ili sibice, po nasem), ruski algoritam sa stabilnim i nestabilnim
stanjima, pa cak i program (u fortranu, a bice u qbasicu) radi eventualne
dogradnje u recimo visual basic?
Mozda sam pogresio konferenciju/temu?
zainteresovani reply...
algoritmi.26vlaslo,
> Da li je neko zainteresovan za teorijsko razmatranje igre
> marienbad iz kviza (ili sibice, po nasem), ruski algoritam sa
> stabilnim i nestabilnim stanjima,
Mene interesuju algoritmi, a u vezi programa jel' moze BP
ili BC++.
cu Zoli
algoritmi.27nbulatovic,
> Da li je neko zainteresovan za teorijsko razmatranje igre marienbad
iz
> kviza (ili sibice, po nasem), ruski algoritam sa stabilnim i
nestabilnim
mene to u principu zanima, ali ne znam o kakvoj se igri radi. jel
moze
nesto preciznije?
algoritmi.28dkrstic,
Imam izazov za programere koji se ne plaše da mućnu glavom!
Radi se na razvijanju rutina za računanje osnovnih računskih operacija
(ADD, SUB, MUL, DIV). Caka je u tome što bi trebale da podržavaju brojeve
proizvoljne dužine (npr. 64-bitne, 128-bitne, 256-bitne).
Znam da postoje jednostavni algoritmi, ali je neophodno da budu što je
moguće brži! Zapravo, pravi izazov su množenje i NAROžITO deljenje.
(Deljenje treba da daje ceo deo i ostatak - znači dva rezultata!).
Nisam pomenuo, ali se na osnovu gore rečenog može zaključiti da se radi
o računskim operacijama nad integer-ima (i to unsigned integer).
Znači, ako neko zna kako ili zna gde se mogu naći algoritmi ili gotovi
programi (u C-u, Pascal-u, Fortran-u, Basic-u ili još bolje asembleru)
neka napiše nešto o tome u ovoj temi ili neka kontaktira samnom mail-om.
algoritmi.29djelovic,
> Radi se na razvijanju rutina za računanje osnovnih računskih operacija
> (ADD, SUB, MUL, DIV). Caka je u tome što bi trebale da podržavaju brojeve
> proizvoljne dužine (npr. 64-bitne, 128-bitne, 256-bitne).
Zašto ne pogledaš izvorni kod PGP-a? U njemu bi trebale da budu rutine
za operacije na brojevima proizvoljne dužine, na koje su neki ljudi potrošili
puno puno puno :) vremena.
algoritmi.30dkrstic,
U međuvremenu sam od dejanr-a već dobio identičnu sugestiju i odmah je usvojio
naravno :)
Zahvaljujem se i tebi.
Voleo bih da čujem još neko mišljenje - može li to bitnije da se ubrza (npr. da
pod istim uslovima radi nekoliko puta brže)? Ima li nekog ko se time bavio?
algoritmi.31janko,
> Voleo bih da čujem još neko mišljenje - može li to bitnije
> da se ubrza (npr. da pod istim uslovima radi nekoliko puta
> brže)? Ima li nekog ko se time bavio?
Slučajno, lično sam se bavio, u praksi, raznim aspektima optimizacije,
pogotovu razvojem kritičnih delova koda u asembleru.
Postoje samo dva puta za ubrzavanje -- istom algoritmu "izvaditi creva"
što kvalitetnijim kodiranjem, i drugi -- smisliti novi algoritam.
Konkretno: add i sub nisu operacije koje možeš da izmisliš brže, i treba
ih iskodirati u mašincu za maksimalne performanse. mul i div su već
operacije za koje se može izmisliti više algoritama. Intidžerski mul i
div na većim brojevima od onih koji su ugrađeni u procesore su teme
kojima se teoretičari i programeri bave bar četrdeset godina, tako da je
mala verovatnoća da ćeš ti smisliti brže algoritme od već postojećih.
Treba samo da nađeš najbrže postojeće i opet iskodiraš tako da budu
najbrži na ciljnoj mašini.
Npr. ako si siguran da program treba da radi na 386 ili jačoj mašini,
i pišeš kritične delove programa na asembleru, treba da koristiš
operacije nad 32-bitnim podacima itd.
PGP je sors koji je pisan tako da bude portabilan na što više različitih
platformi i ima dosta prostora za optimizacije, ako znaš da praviš
program za određenu mašinu. Recimo, PGP sors ne sme ni da računa na to
da li je viši bajt pre nižeg u memoriji ili obratno.
Optimizacija na mašinskom nivou može da pruži značajna ubrzanja u odnosu
na bilo koji kompajlirani kod. Značaj takvih optimizacija postaje sve
šire poznat upravo zahvaljujući pojavi RISC procesora (i njihove ružne
braće ;) ). Npr. neki proizvođači kompajlera tvrde da kada kod koji
optimizuju za Pentijum puste na 486, opet se primeti ubrzanje od nekih
30% (!).
algoritmi.32mdrazic,
>> Radi se na razvijanju rutina za računanje osnovnih
>> računskih operacija (ADD, SUB, MUL, DIV). Caka je u tome
>> što bi trebale da podržavaju brojeve proizvoljne dužine
> (npr. 64-bitne, 128-bitne, 256-bitne).
>
> Zašto ne pogledaš izvorni kod PGP-a? U njemu bi trebale da
> budu rutine za operacije na brojevima proizvoljne dužine,
> na koje su neki ljudi potrošili puno puno puno :) vremena.
Jesmo li se dali u kriptografiju, šta li...
Šalim se. Ako je namena ovih rutina da služe u kriptografske
svrhe tada mu treba i nešto jače: modularna aritmetika sa
velikim integerima. Naime, to je isto kao klasične operacije
samo modulo neki treći broj. Primer:
12345678987654321*123456543313132 (mod 123456)
Rezultat ima najviše 6 cifara i to je ono što treba za
algoritme faktorisanja i slične. Naravno algoritam ne sme
prvo da računa proizvod (>30 cifara) nego direktno rezultat.
Dok sam imao vremena algoritme za modularnu aritmetiku (iz
neke knjige, na Pascalu, do knjige više ne mogu doći) sam
preradio za FORTRAN. Ideja je da se veliki integeri pamte
u nizovima integera i svaki registar da pamti nekoliko
(ovde 8) cifara velikog broja. Kao brojni sistem sa osnovom
10**8. Ograničenje je da moraš unapred da dimenzionišeš niz
na maksimalno očekivane integere. Sve aritmetičke operacije
su modularne, izvedene su kao potprogrami, a ima: sabiranje
(oduzimanje), množenje, deljenje, stepenovanje (? možda).
Za neke poboljšane algoritme faktorisanja bilo je potrebno
i korenovanje (samo kvadratni koren, integerski deo) ali to
nisam uradio, niti sad imam vremena.
Ako aritmetika nije modularna, to je lakši problem, samo je
veša opasnost od overflow-a, jer rezultati tipično rastu
eksponencijalno (Marfi radi).
Ako samo treba da se odradi nešto jednokratno, možda je rešenje
da se uzme UBASIC koji radi sa brojevima jako velike tačnosti
(koliko sam zadaš).
Milan
algoritmi.33wolf,
Ako sam shvatio, treba ti:
X veliki broj
Y veliki broj
X*Y mnogo veliki broj (izbeci direktno mnozenje pa moduo)
X=a*Z+b b = X mod Z
Y=c*Z+d d = Y mod Z
(X*Y) mod Z = [(a*Z+b)(c*Z+d)] mod Z =
(a*c*Z*Z + (a*d+b*c)*Z + b*d) mod Z =
(b * d) mod Z = [(X mod Z)*(Y mod Z)] mod Z
Dakle imas racunanje dva modula manjeg broja, jedan proizvod ciji je rezultat
uvek manji od Z*Z, i na kraju jos jedan moduo.
(X*Y) mod Z = [(X mod Z)*(Y mod Z)] mod Z
algoritmi.34djelovic,
Firma pod imenom RSA Data Security (zvuči poznato? ;)) je pustila kao PD
dve arhive:
1. RIPEM/SIG digital signature encryption softver.
2. RSAREF toolkit za kriptografiju.
Obe arhive se mogu nabaviti sa anonimnog ftp-a ripem@ripem.msu.edu. Ima li
šanse da neko to dovuče ovamo?
algoritmi.35spantic,
> Firma pod imenom RSA Data Security (zvuči poznato? ;)) je pustila kao PD
> dve arhive:
> 1. RIPEM/SIG digital signature encryption softver.
> 2. RSAREF toolkit za kriptografiju.
Jesu li u sorsu ili kako? Mislim vlada SAD je vlada SAD ;)
algoritmi.36spantic,
> Firma pod imenom RSA Data Security (zvuči poznato? ;)) je pustila kao PD
> dve arhive:
> 1. RIPEM/SIG digital signature encryption softver.
> 2. RSAREF toolkit za kriptografiju.
Jesu li u sorsu ili kako? Mislim vlada SAD je vlada SAD ;)
algoritmi.37djelovic,
> Jesu li u sorsu ili kako? Mislim vlada SAD je vlada SAD ;)
Ne znam. Što se tiče zloglasne vlade SAD, čujem da se RSA DS dogovorio sa
njima tako da paket može da se iznosi i u inozemstvo. Ma propada taj
kapitalizam, kažem ti ja :).
algoritmi.38jovca.car,
I šta je nakraju sa PGP 2.6? Jel izašao source ili je sigurnost još uvek
sumnjiva?
algoritmi.39szeman,
Može li neko da kaže nešto više ovome: kao što je poznato ARJ ima
opciju -je kojom se pravi self-extract arhiva u kojoj se nalazi program
za dearhiviranje i sama arhiva (to se već zna, al' da ponovim ;). Zanima me
na koji način se ovo postiže. Ako se o ovome vodila rasprava i/ili ima
poučnih primera, molim da me uputite...
Neupućeni
(ovo bi trbalo da bude poruka "Lične prirode" ;)
P.S. Zahvaljujem unapred na odgovorima.
algoritmi.40.ken.,
Jedno pitanje (ako moze).
Kako da resim problem koji najlakse mogu objasniti kao problem CD-kasetofon.
Treba da od pesama koje postoje na CD-u snimim na kasetofon pesme koje
po minutazi najblize odgovaraju duzini kasete (ne sme da se prekoraci duzina
kasete - da se ne bi odsekla neka pesma).
Znaci od 20 pesama na CD-u treba da izaberu 5-6 koje mogu da stanu na jednu
stranu kasete.
algoritmi.41djelovic,
> Znaci od 20 pesama na CD-u treba da izaberu 5-6 koje mogu da stanu na jednu
> stranu kasete.
Problem je ekvivalentan pitanju kako spakovati ogroman broj fajlova na što
manje disketa. Iako možeš da tražiš i nešto bolja rešenja, mislim da će ti
najbolje doći sledeći jednostavan algoritam:
1. Pesme (fajlovi) se sortiraju po dužini.
2. Na kasetu (disketu) pakuješ najduži fajl koji može da stane, pa ako je
preostalo prostora najduži fajl koji staje u to malo prostora, itd.
algoritmi.42skerl,
│ 1. RIPEM/SIG digital signature encryption softver.
└────
Dear FTP user,
To access the RIPEM cryptographic software archive at ripem.msu.edu,
you must have an "account" on my custom FTP server. Traditional
anonymous FTP login is allowed, but anonymous users are prevented
from doing GETs on files containing cryptographic software.
Anonymous access is allowed so that you can get README-type files
like this one, and files containing descriptions of software
licensing terms.
This FTP server is not an official service at all. Although
accounts have no specific expiration dates, your account (or
more likely, the service as a whole) could be discontinued at
any time without any advance notice (even to me).
To apply for FTP access to rpub.cl.msu.edu, send an email message
to ripem@ripem.msu.edu. State the following:
1. Your citizenship (must be USA or Canadian)
2. Your willingness to comply with relevant export laws.
3. Your willingness to comply with relevant software license terms.
(You should get and read the file "rsaref-license.txt" on this host,
so you know what you are agreeing to if you get RIPEM.)
4. The "canonical" Internet domain name of your host.
(If you are not sure of the primary name of your host, FTP to
ripem.msu.edu under user anonymous. The FTP server will inform
you of your hostname.) Also state the country in which your host
resides.
*****
***** NOTE: It is very important that you get the hostname correct.
***** As odd as it may seem, many requestors have
***** not correctly specified their host address. This
***** causes extra effort for both of us. Please check
***** (via anonymous FTP) unless you are certain of your
***** hostname as known by domain name servers. Your
***** hostname does *** NOT *** have an "@" in it, and
***** in general cannot be derived from your email address.
*****
Here's a sample email message you might send to ripem@ripem.msu.edu:
To: ripem@ripem.msu.edu
Subject: Access to ripem.msu.edu
Dear Mark,
Please give me access to ripem.msu.edu. I am an American
citizen, and I agree to comply with crypto export laws and
RSAREF license terms. My hostname is hobbit.egr.bigu.edu;
this host is located in the United States.
Thank you.
When I receive your message, with luck I'll promptly issue you
a special FTP username and password by return email. This username
will work only from the hostname you specify in your message.
In the case of RIPEM, you may redistribute the code, but only
to others in the USA and Canada, and only under the terms of
the RSAREF license agreement mentioned above.
Thank you.
This method of distribution is due to local site requirements
and is not required by RSAREF license terms, FYI.
Mark Riordan mrr@scss3.cl.msu.edu
P.S. I realize that going through this account application process
is not your idea of a good time. It doesn't take much imagination
to figure that it isn't my idea of a good time, either. Please
help this process go smoothly by giving me all the informative
requested above, so I can issue your account on the first try.
I receive hundreds of these requests and many are lacking information.
Ali, ipak ce biti uskoro :)
Pozdrav,
Skerl.
algoritmi.43skerl,
RSA brief explanation
Pozdrav,
Skerl.
From msuinfo!caen!malgudi.oar.net!witch!cyberg!fb Tue Jan 11 22:02:44 1994
Path: msuinfo!caen!malgudi.oar.net!witch!cyberg!fb
Newsgroups: sci.crypt
Message-ID: <46@cyberg.win.net>
Reply-To: fb@cyberg.win.net (Francis Barrett)
From: fb@cyberg.win.net (Francis Barrett)
Date: Sat, 08 Jan 1994 05:18:32 GMT
Subject: Re: Factoring N+P*Q when (e,N,d) is known.
Lines: 115
Theo Van Dinter <THEOVD@delphi.com> writes...
> Hello. Excuse me for jumping in the conversation, but the topic
> is something I am currently working on. Also excuse me because
> I'm a novice at RSA type encryption. Would you be able to
> explain, or tell me where to find a description of how
> (generalistic ally or precisely) the method works?
There's a nice explanation in "Cryptography: A Primer" by Konheim if
you want all the gory details but I can easily give you a simple
example.
> from what I've read, you take E (odd number), and P and Q
> (primes). get N by multiplying Q and P, and then find D by
> taking (p-1)(q-1)(e-1)+1 all divided by E.
Some of that is correct. More precisely, you pick two distinct odd
primes, P and Q. You then multiply them together to get a modulus
N = P*Q. If you pick any number E which is relatively prime to
(P-1)*(Q-1), exponentiation to E modulo N will be a permutation on the
integers modulo N. If D is a number such that E*D = 1 MOD (P-1)(Q-1),
exponentiation to D modulo N will be the inverse of that permutation.
> I have tried this with significantly small values of the numbers
> (E as 5, P as 3 and Q as 5), and the method doesn't work.
N = 15 works fine, although it is somewhat less exciting because E
always equals D and raising to the 5th power modulo 15 is the identity
transformation. The smallest modulus you can pick where something
interesting happens is 33, which is 11*3. Then you can pick E to be
3 and D to be 7. (P-1)*(Q-1) is 10*2 or 20. Observe that
E*D = 7*3 = 21 which is 1 mod 20. You could also have used 13 and 17
for E and D because 13*17 is 221 which is also 1 mod 20.
Raising the numbers 0...32 to the third power modulo 33 yields...
0 1 8 27 31 26 18 13 17 3 10
11 12 19 5 9 4 29 24 28 14 21
22 23 30 16 20 15 7 2 6 25 32
Raising the numbers 0...32 to the seventh power modulo 33 yields...
0 1 29 9 16 14 30 28 2 15 10
11 12 7 20 27 25 8 6 13 26 21
22 23 18 31 5 3 19 17 24 4 32
These two permutations are inverses of each other. Looking up a number
in the first table and then looking up that number in the second will
give you back the number you started with.
> I would try larger values, but my computer tends to not like
> things such as 66 to the 7th power mod 35.. (at least I
> haven't found the method to do this yet.)
This is because 66^7 is about 5 trillion. When doing modular
exponentiation, it is necessary to modulo frequently to keep things
within range. Then everything works nicely.
If you make yourself a little table of geometrically increasing powers
of 66 modulo 35, like this...
66 ^1 MOD 35 = 31
66 ^2 MOD 35 = 16
66 ^4 MOD 35 = 11
66 ^8 MOD 35 = 16
66^16 MOD 35 = 11
66^32 MOD 35 = 16
66^64 MOD 35 = 11
Then you can calculate 66 to any power by simply selecting the entries
corresponding to the bits of the exponent and multiplying them
together modulo 35. For instance...
66^7 = 66^1*66^2*66^4 = 31*16*11 = 31 MOD 35
This method of modular exponentiation works nicely even when the
modulus and the exponent are many hundreds of bits in length.
Now let's encrypt something using RSA with a modulus of 33. Our
public key will be (E,N) or (3,33). Our secret key will be
(D,N) or (7,33).
Our plaintext will be the familiar C string "Hello World.\n", which is
the following hexadecimal integer...
48656C6C6F20576F726C642E0A
A quick conversion to base 33 yields...
2 14 22 27 18 31 6 23 0 4 4 21 31 21 15 20 13 10 16 1 31
Raising this modulo 33 to the power of the public exponent E=3
yields...
8 5 22 15 24 25 18 23 0 31 31 21 25 21 9 14 19 10 4 1 25
And now back to hexadecimal to yield the ciphertext...
F1F4A7DEFC4E7FFE546F94B09F
We now send this data to the owner of the secret key who reverses the
process by converting to base 33, raising each number to the power of
his secret exponent D=7, and upon conversion back gets the familiar
message "Hello World.\n".
Of course in real life, we use much larger numbers for P, Q, E, and D.
Also, since RSA is somewhat slow when encrypting large messages, we
use a strong product cipher like DES or IDEA with a random session key
to encrypt the message, and then encrypt the session key with RSA.
Since the session key is usually much smaller than the modulus, we
don't have to go through a base conversion, but simply pad with
additional random data in unused bit positions.
That's RSA in a nutshell.
---------------------------------------------------------------
Francis Barrett, F.R.C. | Thou canst not travel on the path |
The Cybernetics Guild | before thou hast become the Path |
fb@cyberg.win.net | itself. |
---------------------------------------------------------------
algoritmi.44skerl,
Answers To
FREQUENTLY ASKED QUESTIONS
About Today's Cryptography
Paul Fahn
RSA Laboratories
100 Marine Parkway
Redwood City, CA 94065
Copyright (c) 1993 RSA Laboratories, a division of RSA Data Security,
Inc. All rights reserved.
------------------------------------------------------------------------
Table of Contents
[ part 1 ]
1 General
1.1 What is encryption?
1.2 What is authentication? What is a digital signature?
1.3 What is public-key cryptography?
1.4 What are the advantages and disadvantages of public-key
cryptography over secret-key cryptography?
1.5 Is cryptography patentable in the U.S.?
1.6 Is cryptography exportable from the U.S.?
2 RSA
2.1 What is RSA?
2.2 Why use RSA rather than DES?
2.3 How fast is RSA?
2.4 How much extra message length is caused by using RSA?
2.5 What would it take to break RSA?
2.6 Are strong primes necessary in RSA?
2.7 How large a modulus (key) should be used in RSA?
2.8 How large should the primes be?
2.9 How does one find random numbers for keys?
2.10 What if users of RSA run out of distinct primes?
2.11 How do you know if a number is prime?
2.12 How is RSA used for encryption in practice?
2.13 How is RSA used for authentication in practice?
2.14 Does RSA help detect altered documents and transmission errors?
2.15 What are alternatives to RSA?
2.16 Is RSA currently in use today?
2.17 Is RSA an official standard today?
2.18 Is RSA a de facto standard? Why is a de facto standard important?
2.19 Is RSA patented?
2.20 Can RSA be exported from the U.S.?
[ part 2 ]
3 Key Management
3.1 What key management issues are involved in public-key
cryptography?
3.2 Who needs a key?
3.3 How does one get a key pair?
3.4 Should a public key or private key be shared among users?
3.5 What are certificates?
3.6 How are certificates used?
3.7 Who issues certificates and how?
3.8 What is a CSU, or, How do certifying authorities store their
private keys?
3.9 Are certifying authorities susceptible to attack?
3.10 What if the certifying authority's key is lost or compromised?
3.11 What are Certificate Revocation Lists (CRLs)?
3.12 What happens when a key expires?
3.13 What happens if I lose my private key?
3.14 What happens if my private key is compromised?
3.15 How should I store my private key?
3.16 How do I find someone else's public key?
3.17 How can signatures remain valid beyond the expiration dates of
their keys, or, How do you verify a 20-year-old signature?
3.18 What is a digital time-stamping service?
4 Factoring and Discrete Log
4.1 What is a one-way function?
4.2 What is the significance of one-way functions for cryptography?
4.3 What is the factoring problem?
4.4 What is the significance of factoring in cryptography?
4.5 Has factoring been getting easier?
4.6 What are the best factoring methods in use today?
4.7 What are the prospects for theoretical factoring breakthroughs?
4.8 What is the RSA Factoring Challenge?
4.9 What is the discrete log problem?
4.10 Which is easier, factoring or discrete log?
5 DES
5.1 What is DES?
5.2 Has DES been broken?
5.3 How does one use DES securely?
5.4 Can DES be exported from the U.S.?
5.5 What are the alternatives to DES?
5.6 Is DES a group?
[part 3]
6 Capstone, Clipper, and DSS
6.1 What is Capstone?
6.2 What is Clipper?
6.3 How does the Clipper chip work?
6.4 Who are the escrow agencies?
6.5 What is Skipjack?
6.6 Why is Clipper controversial?
6.7 What is the current status of Clipper?
6.8 What is DSS?
6.9 Is DSS secure?
6.10 Is use of DSS covered by any patents?
6.11 What is the current status of DSS?
7 NIST and NSA
7.1 What is NIST?
7.2 What role does NIST play in cryptography?
7.3 What is the NSA?
7.4 What role does the NSA play in commercial cryptography?
8 Miscellaneous
8.1 What is the legal status of documents signed with digital
signatures?
8.2 What is a hash function? What is a message digest?
8.3 What are MD2, MD4 and MD5?
8.4 What is SHS?
8.5 What is Kerberos?
8.6 What are RC2 and RC4?
8.7 What is PEM?
8.8 What is RIPEM?
8.9 What is PKCS?
8.10 What is RSAREF?
--------------------------------------------------------------------
Pozdrav,
Skerl.
rsa-faq.zipalgoritmi.45skerl,
Subject: Re: RUMOUR: RSA has been broken! Comments please!
Pozdrav,
Skerl.
p.s. Sorry na malo duzoj poruci.
From
msuinfo!agate!howland.reston.ans.net!europa.eng.gtefsd.com!uunet!bloom-beacon.m
it.edu!senator-bedfellow.mit.edu!athena.mit.edu!burt Sat Jan 22 17:09:40 1994
Path:
msuinfo!agate!howland.reston.ans.net!europa.eng.gtefsd.com!uunet!bloom-beacon.m
it.edu!senator-bedfellow.mit.edu!athena.mit.edu!burt
From: burt@chirality.rsa.com (Burt Kaliski)
Newsgroups: sci.crypt
Subject: Re: RUMOUR: RSA has been broken! Comments please!
Date: 19 Jan 94 16:53:58
Organization: RSA Data Security, Inc.
Lines: 92
Distribution: world
Message-ID: <BURT.94Jan19165358@chirality.rsa.com>
References: <TLB.94Jan13132133@chardonnay.harvard.edu>
<2h4a60$nd@linus.mitre.org> <WCS.94Jan13210220@anchor.ATT.COM>
<2h6e88$2vui@ep130.wg2.waii.com>
NNTP-Posting-Host: rsa.com
In-reply-to: mwj@se17.wg2.waii.com's message of 14 Jan 1994 15:37:44 GMT
In article <2h6e88$2vui@ep130.wg2.waii.com> mwj@se17.wg2.waii.com (Michael W.
Johnson) writes:
Pardon me. I missed the early posts on this thread. Who is supposed
to have broken RSA, and how was it done? Would someone please
repost this?
Actually, I was just about to fill in the details. The
supposed break is due to Bill Payne, who sent me a copy of
his paper "Public Key Cryptography is Easy to Break" and gave
me permission by phone to post a description.
The quick summary is that his result, while clever, actually
confirms that RSA is still hard to break. Payne says he has
better methods, though, which he hasn't published.
RSA BACKGROUND
An RSA key pair consists of a public key (n,e) and a private
key (n,d), where n, the RSA modulus, is the product of
distinct primes p and q, and where e and d (respectively the
public and private exponents) satisfy the equation
ed = 1 mod (p-1)(q-1)
To break RSA (i.e., solve for the private key, given the
public key), one need only find the product (p-1)(q-1),
which is usually denoted phi(n). Given phi(n) one can easily
find p and q, so a method that finds phi(n) also factors n.
PAYNE'S RESULT
According to Fermat's little theorem, for all a, one has
a^phi(n) = 1 mod n
Consequently, for a = 2, one has that 2^phi(n)-1 is
divisible by n. One can therefore find phi(n) (or a divisor
of it) by constructing a multiple of n whose binary
representation is all 1's.
Payne's algorithm finds such a multiple by simple binary
operations. The algorithm sets bits of an accumulator to 1
by adding shifts of the modulus n, working from least
significant to most significant bit of the accumulator.
Eventually the accumulator is all 1's, and the number of 1's
yields a divisor of phi(n).
Here is the algorithm:
x := 0
i := 0
while x contains a 0 bit (other than leading bits) do
if bit i of x is 0
then x := x + (n << i)
i := i + 1
return length of x in bits
By considering only the window of bits starting at bit i,
one can view Payne's algorithm as applying repeatedly the
following permutation on the set {0, ..., n-1}:
/ (w + n - 1) / 2 if w is odd
f(w) = |
\ (w - 1) / 2 if w is even
The window w at iteration i corresponds to the accumulator
value x = 2^i w + 2^i - 1. Since the function f is a
permutation, repeated application of f will eventually
return to any given starting value. To find a multiple of n
whose binary representation is all 1's, it suffices to start
with w = 0. When repeated application of f arrives at w = 0
again, the value x = 2^i - 1 will be a multiple of n whose
binary representation is all 1's.
There's only one problem: Finding x can take up to phi(n)
steps! Since phi(n) is almost as large as n, if n is just
tens of digits long (not to mention the hundreds of digits
in RSA), the amount of work is enormous. Indeed, this is an
``exponential-time'' algorithm for finding phi(n), the
slowest kind. While Payne's algorithm is curious, public key
is no easier to break.
-------------------------------------------------------
Burt Kaliski, Chief Scientist
RSA Laboratories (415) 595-7703
100 Marine Parkway, Suite 500 (415) 595-4126 (fax)
Redwood City, CA 94065 USA burt@rsa.com
-------------------------------------------------------
From
msuinfo!agate!library.ucla.edu!europa.eng.gtefsd.com!howland.reston.ans.net!cs.
utexas.edu!news.unt.edu!sol.acs.unt.edu!fc14 Sat Jan 22 17:10:16 1994
Path:
msuinfo!agate!library.ucla.edu!europa.eng.gtefsd.com!howland.reston.ans.net!cs.
utexas.edu!news.unt.edu!sol.acs.unt.edu!fc14
From: fc14@sol.acs.unt.edu (Steve Tate)
Newsgroups: sci.crypt
Subject: Re: RUMOUR: RSA has been broken! Comments please!
Date: 20 Jan 1994 02:24:40 GMT
Organization: University of North Texas
Lines: 17
Distribution: world
Message-ID: <2hkq18$rc6@hermes.unt.edu>
References: <TLB.94Jan13132133@chardonnay.harvard.edu>
<BURT.94Jan19165358@chirality.rsa.com>
NNTP-Posting-Host: sol.acs.unt.edu
X-Newsreader: TIN [version 1.2 PL2]
Burt Kaliski (burt@chirality.rsa.com) wrote:
> [Description of Bill Payne's algorithm deleted]
> There's only one problem: Finding x can take up to phi(n)
> steps! Since phi(n) is almost as large as n, if n is just
> tens of digits long (not to mention the hundreds of digits
> in RSA), the amount of work is enormous.
That's actually a very cute trick, even if it's totally useless.
One thing to point out if anyone still thinks that might prove
some danger to RSA: The described method can take approximately
n steps, but the most entirely stupid factoring algorithm you can
think of takes only square_root(n) steps. In other words, the
proposed method is lots worse than even the worst previously proposed
technique (and both are highly unpractical).
From
msuinfo!agate!howland.reston.ans.net!europa.eng.gtefsd.com!MathWorks.Com!news.k
ei.com!bloom-beacon.mit.edu!senator-bedfellow.mit.edu!senator-bedfellow.mit.edu
!not-for-mail Sun Feb 27 19:34:12 1994
Path:
msuinfo!agate!howland.reston.ans.net!europa.eng.gtefsd.com!MathWorks.Com!news.k
ei.com!bloom-beacon.mit.edu!senator-bedfellow.mit.edu!senator-bedfellow.mit.edu
!not-for-mail
From: tytso@ATHENA.MIT.EDU (Theodore Ts'o)
Newsgroups: sci.crypt
Subject: Re: Non invertible encryption
Date: 26 Feb 1994 10:39:02 -0500
Organization: The Internet
Lines: 132
Sender: news@athena.mit.edu
Distribution: world
Message-ID: <2knqem$o40@senator-bedfellow.MIT.EDU>
Reply-To: tytso@ATHENA.MIT.EDU (Theodore Ts'o)
NNTP-Posting-Host: senator-bedfellow.mit.edu
From: Colin James <cjames@dsc.blm.gov>
X-Mailer: SCO System V Mail (version 3.2)
Who is the academic / industrial (non NSA) authority(s) on the subject.
Dr. Burt Kaliski, Ph.D is certinaly one of the authorities; so is
Professor Ron Rivest at MIT. Unfortunately, you may consider their
views biased. :-)
Seriously, though, I suggest you find any professor in mathematics, and
ask them; the mathematics involved here are not hard. My degree was in
computer science, but nevertheless, it seems fairly clear to me that
Bill Payne has convinced himself that he has "squared the circle", and
is squawking because no one is taking him seriously.
If he really thinks RSA is so easy to crack, he should take some
well-known public key, say one of RSADSI's PEM Public Certification
Authority public keys, and demonstrate that he knows the factors of
them. That will get him immediate attention, I promise you!
Here are the details why RSA is broken (so Ada developers of RSA
and DES algorithms will know)......
3. The letter of Bill Payne to Kaliski of January 30, 1994
pointing out an enormous blunder by Kaliski in his "post".
There were no enormous blunders by Dr. Kaliski, at least that I can
detect. Let's review what was said in Payne's letter:
Your statement, "Given phi(n) one can easily find p and q, so a
method that finds phi(n) also factors n.", I believe is false.
Knowledge of phi(n) does not always lead to factors of n.
Only a few minutes thought is required to show that Dr. Kaliski's
statement is true. Given n and phi(n), where n=pq, it is trivial to
find p and q. In fact, it is so obvious that I can't fault Dr. Kaliski
for not including the proof. (I'm not sure it would even make it as a
homework question on an undergraduate math course. :-) Considering that
Payne was not able to figure this out, my respect of him as a
mathematician has taken another quantuum leap downward. Consider, and
judge for yourself:
Phi(n) = (p-1)(q-1) (Definition of Phi(n))
Phi(n) = pq - q - p + 1 (polynomial expansion)
Phi(n) = n - q - p + 1 (substitution of n=pq)
p = n - Phi(n) + 1 - q (rearranging the above)
Since n and Phi(n) is known, one can easily compute n - Phi(n) + 1.
So let K = n - Phi(n) + 1.
p = K - q (from definition of K)
n = (K-q)q (from n=pq)
n = Kq - q^2 (algebraic manipulation)
We now solve for q using the quadratic formula, and I will leave the
rest as an exercise to the reader.
Your statement, "There's only one problem: Finding x can take up
to phi(n) steps." may be, I believe inaccurate. But your
statement is correct. Let me explain this apparent anomaly.
....
Therefore, the two algorithms can work simultaneously and meet in
the middle of the sequence of even numbers. Phi(n)/2 maximum.
Not phi(n).
Dr. Kaliski had just shown the following: ``Indeed, this is an
"exponential-time" algorithm for finding phi(n), the slowest kind.''
You don't refute that argument by saying that you can reduce the time in
half. A multiplicative factor of two is completely meaningless when you
are talking about exponential-time algorithms. If Payne doesn't even
realize this, he is completely ignorant of some of the fundamental
principals of mathematic algorithm analysis. Even if you grant that his
"indefinite division" buys you a factor of two, this doesn't change the
fact that his algorthm is still O(2^n).
Consider what an algorithm which is O(2^n) means; let's look at how fast
various other different types of algorithms are:
n O(1) O(n) O(n^2) O(2^n)
1 1 1 1 1
2 1 2 4 2
3 1 3 9 8
4 1 4 16 16
5 1 5 25 32
6 1 6 36 64
7 1 7 49 128
8 1 8 64 256
9 1 9 81 512
10 1 10 100 1024
11 1 11 121 2048
Do you see how rapidly the O(2^n) numbers are growing? They are
doubling at every step. So just imagine how big 2**1024 is. And you
will immediately realize that a factor of two is just completely in the
noise. This is why for the purposes of computing "the big O" of an
algorithm, O(0.5 * 2^n - 2n - 12) is still considered equivalent to
O(2^n). If you don't believe me, ask any math professor, or indeed any
computer science graduate from MIT --- at MIT, all C.S. students are
required to take an algorithm class. One of the reasons for this is so
that they won't embarass themselves as Payne has. :-)
In summary, I see no evidence in the papers you have submitted to me
that Payne has managed to "break" RSA. I do see evidence that Payne is
missing a fundamental education in mathematics, or at least as far as
algorithms analysis is concerned.
This reminds me of the continuous streams of "proofs" submitted by
people who know nothing about mathemtics that they are able to "square
the circle", and are complaining that there is a conspiracy by the
mathematical community since everyone refuses to look at their "proofs".
The reason for this, of course, is that it has already been
mathematically *proven* that it is impossible to "square the circle",
and so matheticians, unless they are being very generous with their
time, aren't going to bother looking for the hole in the proof which
they know is there.
Payne's case is somewhat different, since there is no conclusive proof
that RSA is impossible to break. However, it shares similar elements in
that someone who is an "outsider", who is apparently not trained in
mathematics, is sure that he has found something which the rest of the
mathematical community has completely missed. To be fair, this is
possible, and has happened. However, in most cases, it is the outsider
who is pathetically wrong.
- Ted
P.S. If someone could forward this analysis back to the ADA development
list, I'd appreciate it.
algoritmi.46djelovic,
> 1.42 ->34 algoritmi skerl 05.09.Pon 17:29
> 1.43 algoritmi skerl 05.09.Pon 17:29
> 1.44 algoritmi skerl 05.09.Pon 17:30 rsa-faq.zip
> 1.45 algoritmi skerl 05.09.Pon 17:33
Hvala na zanimljivim prilozima!
algoritmi.47skerl,
ripemsig: {Riordan's|RSAREF-based} Internet Privacy Enhanced Mail, v.1.2a
*** Exportable signature-only version ***
Signs/verifies mail messages using RSA and MD5, and generates keys.
ripem is in the public domain, but requires agreeing to the RSAREF license
from RSA Data Security; contact rsaref-info@rsa.com. It's free but limited.
ripem was written by Mark Riordan (mrr@scss3.cl.msu.edu). See doc for credits.
Usage: ripem {-e | -d | -g | -c} <in >out
[-r recipient] [-m {mic-only | mic-clear}]
[-u myusername] [-h head] [-b #_of_bits_in_gen_key]
[-p publickey_infile(s)] [-s privatekey_infile] [-k key_to_private_key or -]
[-P publickey_outfile] [-S privatekey_outfile] [-A enc_alg]
[-y pub_key_server_name] [-Y key_sources] [-T recip_opts]
[-i infile] [-o outfile] [-D debug_level] [-Z debug_out_file]
[-R random_sources] [-F random_input_file] [-C random_string]
[-v #_of_validity_months] [-K new_key_to_private_key] [-H home_dir]
where:
enc_alg is the encryption algorithm: des-cbc (default) or des-ede-cbc.
key_sources is a string of one or more of "fgs", which tell ripem to look
for public keys from a File, finGer, or Server, in the order specified.
head is one or more of "ipr", for Include headers in msg; Prepend headers
to output; get Recipients from headers.
random_sources is one or more of "cefkms", specifying "random" input from
Command line, Entire command, File, Keyboard, Message, or running System.
recip_opts is one or more of "amn", for Abort if can't find keys for
all users; include Me as a recipient if encrypting; None of the above.
Relevant environment variables: RIPEM_HOME_DIR,
RIPEM_PUBLIC_KEY_FILE, RIPEM_PRIVATE_KEY_FILE, RIPEM_KEY_TO_PRIVATE_KEY,
RIPEM_USER_NAME, RIPEM_RANDOM_FILE, RIPEM_SERVER_NAME, RIPEM_ARGS
Pozdrav,
Skerl.
ripemsig.zipalgoritmi.48miljko,
>> Znaci od 20 pesama na CD-u treba da izaberu 5-6 koje
>> mogu da stanu na jednu stranu kasete.
Teorijski, problem je poznat kao PROBLEM RUKSAKA, i spada u
klasu celobrojnog programiranja, odnosno. dinamičkog programiranja.
Jednom rečju, ako hoćeš stvarno optimalno, koska.
Postoji program, koji se zove FFIT, za prebacivanje grupe fajlova
na diskete, što je praktično isto kao prebacivanje pesama na CD.
Uz malo mašte možeš ga iskoristiti za svoje potrebe!
algoritmi.49dejanr,
Uz poruku je zanimljiva diskusija sa BIX-a o raznim pitanjima vezanim
za kriptografiju, RSA, njegovu "povredivost", etičke aspekte, pravo
države da kontroliše građane itd.
Vredi pogledati.
encr.zipalgoritmi.50janko,
> I šta je nakraju sa PGP 2.6? Jel izašao source ili je
> sigurnost još uvek sumnjiva?
PGP 2.6 ne treba da koristite ako nekome šaljete poštu. Jedino ga treba
koristiti ako primite poštu od nekog Amera koji je "taze" kupio baš tu
verziju, jer od prvog septembra 2.3 ne dešifruje fajlove napravljene sa
2.6 (2.6 je tako napravljen da 1. septembar bude prelomni datum).
2.6 je, inače, 2.3 prerađen za američko tržište (tj. tako da ima
najmanje pravnih prepreka). Evropa bi trebalo da i dalje koristi 2.3.
Ko ima sors za 2.3 može za par minuta da prepravi 2.3 da radi i sa
2.6 fajlovima generisanim posle 1. septembra (nisu menjali ništa u
algoritmima i strukturi, samo su upisali drugi broj u heder info, opet,
samo iz pravnih razloga).
Sve ove predostrožnosti nisu pomogle jadnom Filu Cimermanu -- u toku je
suđenje na kome samo što ga ne obese zbog "odavanja vojnih tajni" iako
je SVE što se nalazi u PGP sorsu bilo dostupno i vanameričkoj civilnoj
javnosti i pre tog programa. Ovo sve prema takstu iz .DOC. Ima li neko
svežije vesti, kako teče suđenje?
algoritmi.51janko,
> za dearhiviranje i sama arhiva (to se već zna, al' da
> ponovim ;). Zanima me na koji način se ovo postiže. Ako se
> o ovome vodila rasprava i/ili ima
Vrlo jednostavno -- u izvršnom fajlu se nalazi program i podaci koji će
se dešifrovati. Ne razumem šta ti tu nije jasno?
algoritmi.52janko,
> Problem je ekvivalentan pitanju kako spakovati ogroman
> broj fajlova na što manje disketa. Iako možeš da tražiš i
> nešto bolja rešenja, mislim da će ti najbolje doći sledeći
> jednostavan algoritam: 1. Pesme (fajlovi) se sortiraju po
> dužini. 2. Na kasetu (disketu) pakuješ najduži fajl koji
> može da stane, pa ako je preostalo prostora najduži fajl
> koji staje u to malo prostora, itd.
To je OK, ali, normalno, ne daje optimalne rezultate.
Problem se može formulisati ovako:
A) Imamo gredice fiksne dužine, koje treba iseći na gredice zadatih
dužina, tako da potrošimo što manje gredica fiksnih dužina.
Ova formulacija ima smisla, ako smo sigurni da "škart" nećemo da
koristimo kasnije (u priči sa disketama, da na te diskete dalje ne
snimamo ništa novo). Dakle, cilj optimizacije je da se potroši što manje
gredica (disketa).
Ono što radi DJ-ov algoritam je da pokušava da dužine "škartova" budu
što manje (što, je dakle, modifikovani cilj A, tako da se već samom
postavkom ne garantuje optimalnost) ali i to radi, opet, na
najjednostavniji mogući način -- uzima šta stigne, pa postupak ne
garantuje ni optimalost sa tim, promenjenenim zahtevima.
Pošto ovakva ukrojavanja treba da rade sa diskretnim veličinama,
ovo se (verovatno) mora rešavati tzv. diskretnim programiranjem. Poznato
je da zbog kombinatorne eksplozije ovakvi problemi nisu laki za
rešavanje. Ako neko ima u literaturi neki _dobar_ algoritam koji daje
_prihvatljivo_ dobre rezultate, molim da mi preporuči.
Negde se pominje i tzv. "knapsack problem" -- problem pakovanja ranca.
Mi smo formulisali problem u jednoj dimenziji, ali je lako zamisliti
problem u dve ("ukrojavanje" delova od kojih se seku limovi za
automobile, delova za odeću i sl.) ili u tri dimenzije (pakovanje
raznovrsnih oblika u kutije).
Bilo kako bilo, volo bih da nađem nešto bar za 1 D problem.
algoritmi.53miljko,
>> Bilo kako bilo, volo bih da nađem nešto bar za 1 D
>> problem.
Mene je mučio taj problem, pa da izložim svoja iskustva.
Uz ogradu da sam imao skroman uvid u literaturu, sve što
sam našao je da je problem klase celobrojnog programiranja,
koja je pak podklasa linearnog programiranja. Problem se
može tretirati i metodama dinamičkog programiranja, ali
koliko ja shvatam dinamičko programiranje je samo generalni
pristup odredjenoj klasi problema. Ne nudi, dakle, ništa
konkretno, već se svakom konkretnom problemu pristupa
zasebno. (sigurno postoje razradjeni algoritmi za neke češće
probleme ali ovaj izgleda nije mnogo tretiran).
Meni se lično činilo najpametnijim da problem tretiram kao
celobrojno programiranje. To znači otprilike da se ispituje
stablo kombinacija koje se zatim potkresuje raznim sitnim
heuristikama. Zvuči komplikovano, ali nije naročito teško za
implementaciju i što je najvažnije daje gotovo optimalne
rezultate (ne postoji garancija, ali u većini slučajeva, čak
i u najgorem slučajevima).
Konkretno primenjeno na fajlove u direktoriju to izgleda
otprilike ovako:
- (pokupe se informacije o skupu koji se prebacuje, i
veličini odredišta, uzme u obzir fragmentacija i sl.)
- fajlovi se sortiraju po dužini.
- nadje se prosečna dužina i na osnovu toga koliko
prosečnih fajlova staje na odredište = K
- (1) generišemo kombinacije od N el. klase K ali tako da
ukupan zbir ide od najvećeg ka najmanjem zbiru.
- (2) pretraživanje se nastavlja na komb. (N nad K+1) itd.
do (N nad N).
Koraci (1) i (2) se mogu jako puno optimizovati sa par
očilednih heuristika, tako da se stablo pretrage drastično
smanji. žak i u slučajevima (N=100, K=50) algoritam deluje
gotovo trenutno jer vrlo brzo dodje do optimalnog rešenja
(koje je u slučaju tako velikog broja kombinacija vrlo
verovatno.) U manjim slučajevima, bez problema se prodje kroz
stablo.
Postoji naravno i implementacija u C++ - u, ali pisana
je malo navrat - nanos (za interne potrebe).
Toliko od mene. Nadam se da je od pomoći.
algoritmi.54szeman,
Re: Self-extract sistemi
========================
>> Vrlo jednostavno -- u izvršnom fajlu se nalazi program i
>> podaci koji će se dešifrovati. Ne razumem šta ti tu nije
>> jasno?
Bio sam vrlo precizan, ali ajde da ponovim ;) Hoću iz mog EXE fajla
(npr. INDEX.EXE) koji vrći obradu nad nekom text datotekom (npr. TEST.TXT)
i rezultat smešta u REZULT.IDX. Pomoću INDEX -v RESULT.TXT ja mogu da vidim
šta je program uradio. Medjutim, hoću da napravim jedan EXE fajl koji će da
radi to isto ( pravi se hipotetički nečto kao kod ARJ-a, naredbom
INDEX -jr TEST.TXT RESULT.EXE). Startovanjem REZULT.EXE dobijam iste
rezultate koje bi dobio i sa INDEX -v RESULT.TXT. Poentu si sad ukapirao,
dakle u INDEX.EXE bi trebao da bude kod koji bi napravio jedan takav
izvršan fajl (self-extract metod). Kako da to napravim? Jasnije od ovoga ?
Teško da meže... Nisam upoznat sa ovom problematikom, pa ako znaš nešto
više...
algoritmi.55djelovic,
> dakle u INDEX.EXE bi trebao da bude kod koji bi napravio jedan takav
> izvršan fajl (self-extract metod). Kako da to napravim? Jasnije od ovoga ?
Na kraj EXE fajla možeš da dopišeš bilo šta, to neće uticati na rad
programa. Dakle, program treba da otvori samog sebe :), i da od nekog N-tog
bajta (gde je N dužina programa bez dopunskih informacija) čita podatke koji mu
trebaju.
algoritmi.56omega,
Ţ PGP 2.6 ne treba da koristite ako nekome saljete postu. Jedino ga treba
Ţ koristiti ako primite postu od nekog Amera koji je "taze" kupio bas tu
Ţ verziju, jer od prvog septembra 2.3 ne desifruje fajlove napravljene sa
Ţ 2.6 (2.6 je tako napravljen da 1. septembar bude prelomni datum).
E sad mi nista nije jasno :( Znaci PGP 2.6 nista ne valja, a na Sezamu
nema v<2.6!? Zasto onda stoji na disku?
pgp23asr a01 180963 Izvorni kod programa pgp23a (#1/3)
pgp23asr a02 180958 Izvorni kod programa pgp23a (#2/3)
pgp23asr a03 179635 Izvorni kod programa pgp23a (#3/3)
pgp25doc zip 99854 Dokumentacija za PGP v2.5
pgp26 zip 241927 PGP v2.6: neprobojno sifrovanje podataka
Znaci preostaje jedino da sam iskompajliram pgp23!?
algoritmi.57skerl,
RSAREF(TM) 2.0: A Free Cryptographic Toolkit
General Information
RSA Laboratories
Revised April 15, 1994
WHAT IS IT?
RSAREF is a free, portable software developer's library of popular
encryption and authentication algorithms. The name "RSAREF" means
"RSA reference." RSA Laboratories intends RSAREF to serve as a free,
educational reference implementation of modern public- and secret-key
cryptography.
RSAREF 2.0 supports the following algorithms:
o RSA encryption and key generation, as defined by RSA
Laboratories' Public-Key Cryptography Standards (PKCS)
o MD2 and MD5 message digests
o DES (Data Encryption Standard) in cipher-block chaining mode
o Diffie-Hellman key agreement
o DESX, RSA Data Security's efficient, secure DES enhancement
o Triple-DES, for added security with three DES operations
Version 2.0 offers three other improvements over RSAREF 1.0: the
ability to process messages of arbitrary length in parts; the option
to process either binary data, or data encoded in printable ASCII;
and support for encrypting messages for more than one recipient.
RSAREF is written in the C programming language as a library that can
be called from an application program. A simple Internet Privacy-
Enhanced Mail (PEM) implementation can be built directly on top of
RSAREF, together with message parsing and formatting routines and
certificate-management routines. RSAREF is distributed with a
demonstration program that shows how one might build such an
implementation.
WHAT YOU CAN (AND CANNOT) DO WITH RSAREF
1. RSAREF is free for personal or corporate use under the
following conditions:
o RSAREF, RSAREF applications, and services based on
RSAREF applications may not be sold.
o You must give RSA the source code of any free RSAREF
application you plan to distribute or deploy within
your company. RSA will make these applications
available to the public, free of charge.
2. RSAREF applications and services based on RSAREF
applications may be sold under the following conditions:
o You must sign and return the RSAREF Commercial License
Agreement to RSA (call RSA for a copy of this
agreement). Remember, RSAREF is an unsupported toolkit.
If you are building an application to sell, you should
consider using fully supported libraries like RSA's
BSAFE or TIPEM SDK's.
3. RSAREF applications and services based on RSAREF
applications may be "sharewared" under the following
conditions:
o Shareware authors do not need to sign a separate
agreement with RSA, provided that their per-copy asking
price is less than $50 and total RSAREF application
revenue is less than $10,000 annually. Otherwise,
shareware authors must sign and return the RSAREF
Commercial License Agreement.
4. You must use the interface described in the RSAREF
documentation.
o The published interface of RSAREF consists of those
procedures and data types listed in the files
"global.h" and "rsaref.h", as described in the RSAREF
library reference manual (the file "rsaref.txt"). If a
procedure is not documented in the library reference
manual, then it is not considered published, even if an
application could access it without modification to
RSAREF.
o Furthermore, the published interface is understood as
the reasonable interpretation of the descriptions in
the library reference manual. Although it may well be
possible to perform other operations with procedures
listed in "rsaref.h" than what is described in
"rsaref.txt", only the intended operations (e.g.,
Diffie-Hellman key agreement with the Diffie-Hellman
procedures) are considered to follow the published
interface.
5. You can modify RSAREF to port it to other platforms, or to
improve its performance, as long as you give a copy of the
resulting source code to RSA. Other changes to the RSAREF
code require written consent from RSA.
6. You can't send or transmit (or cause to be transmitted)
RSAREF outside the United States or Canada, or give it to
anyone who is not a U.S. or Canadian citizen or doesn't have
a "green card."
Pozdrav,
Skerl.
rsaref20.zipalgoritmi.58skerl,
Contents
November 1993 Release
An Overview of the PKCS Standards.
A Layman's Guide to a Subset of ASN.1, BER, and DER.
PKCS #1: RSA Encryption Standard. Version 1.5.
PKCS #3: Diffie-Hellman Key-Agreement Standard. Version 1.4.
PKCS #5: Password-Based Encryption Standard. Version 1.5.
PKCS #6: Extended-Certificate Syntax Standard. Version 1.5.
PKCS #7: Cryptographic Message Syntax Standard. Version 1.5.
PKCS #8: Private-Key Information Syntax Standard. Version 1.2.
PKCS #9: Selected Attribute Types. Version 1.1.
PKCS #10: Certification Request Syntax Standard. Version 1.0.
Some Examples of the PKCS Standards.
Pozdrav,
Skerl.
pkcs-doc.zipalgoritmi.59kriss,
˙˙ 2.6 je, inače, 2.3 prerađen za američko tržište (tj. tako da
˙˙ ima najmanje pravnih prepreka). Evropa bi trebalo da i dalje
˙˙ koristi 2.3. Ko ima sors za 2.3 može za par minuta da prepravi
Da li je neko ovo uradio, i ako jeste, da li mu nije teško da to okači
ovde negde, ili da otvori privremenu grupu pa da krenemo na DL. Valjda
se ovim činom ne povređuju autorska prava?
algoritmi.60mmitrovic,
Ů█▀█Ţ za dearhiviranje i sama arhiva (to se već zna, al' da ponovim ;). Zanima
Ů█▀█Ţ me na koji način se ovo postiže. Ako se o ovome vodila rasprava i/ili
Ů█▀█Ţ ima poučnih primera, molim da me uputite...
Vrlo prosto.
Na disku ti se nalazi jedan fajl (.exe) koji je sastavljen iz
dva dela: izvršnog modula (dearhivera) i same arhive. Na osnovu headera
exe fajla izračuna se veličina modula, postavi se file pointer na
sledeći baj i krene sa raspakivanjem.
algoritmi.61.ken.,
Da li neko mozda ima nesto za rad sa retkim matricama.
Matrica ima maksimalno do 10 clanova u vrsti i dimenzija matrice moze
ici do 2000.
Potrebni su mi programi za resavanje linearnog sistema i za inverziju
matrice.
U obzir dolaze Fortran i/ili C
Unapred hvala
algoritmi.62omega,
Ţ Da li je neko ovo uradio, i ako jeste, da li mu nije tesko da to okaci
Ţ ovde negde, ili da otvori privremenu grupu pa da krenemo na DL. Valjda
Ţ se ovim cinom ne povreduju autorska prava?
Put me in, too :)
algoritmi.63jovca.car,
/* javnosti i pre tog programa. Ovo sve prema takstu iz .DOC. Ima li neko
/* svežije vesti, kako teče suđenje?
Ne znam za suđenje, ali je neko skoro okačio na FON (tin) Cimermanovo pismo
u kome on tvrdi da je 2.6 OK, da nema backdoorova i da on lično nadgleda rad
na njemu. Na žalost, obrisao sam log, pa bi zamolio nekog umešnijeg u radu
sa tinom da iskopa tu poruku i okači ovde. Verujem da će interesovati mnoge.
algoritmi.64.ken.,
> Postoji program, koji se zove FFIT, za prebacivanje grupe
> fajlova na diskete, sto je prakticno isto kao prebacivanje
> pesama na CD.
Gde ovo cudo moze da se nadje ? ( ima li sors? )
Hvala mnogo i za teorisko razmatranje problema.
algoritmi.65szeman,
>>> dakle u INDEX.EXE bi trebao da bude kod koji bi napravio
>>> jedan takav izvršan fajl (self-extract metod). Kako da
>> to napravim? Jasnije od ovoga ?
>>
>> Na kraj EXE fajla možeš da dopišeš bilo šta, to neće
>> uticati na rad programa. Dakle, program treba da otvori
>> samog sebe :), i da od nekog N-tog bajta (gde je N dužina
>> programa bez dopunskih informacija) čita podatke koji mu
Izgleda da se ne razumemo dobro :( Evo ti samo jedno pitanje:
Kako bi ti napravio ARJ sa self-extract mogućnošću. Kao što znaš, ARJ.EXE
je samo JEDAN fajl i iz njega se dobija drugi EXE. Ako je sad jasnije, baci
malo koda, ako imaš vremena.
algoritmi.66vitez.koja,
#=> Izgleda da se ne razumemo dobro :(
Jesi li razmotrio mogućnost da se baviš nečim manje mentalno
zahtevnim nego što je programiranje ? ;) Ako nisi, sad je pravi
trenutak. (Možda si samo neispavan?:)
ps. Za potrebe primera, neka je ARJ, kada se iskompajlira,
dugačak 100 bajtova. Nezavisno od njega napraviš samo modul
za raspakivanje koji je iskompajliran dugačak 30 bajtova.
Jednostavnim nadovezivanjem ova dva izvršna fajla dobijaš
izvršni fajl AA koji je dugačak 130 bajtova, ali je funkcionalno
identičan programu ARJ (onaj nastavak, modul za raspakivanje, kao
da nije tu). Sad, kad ARJ treba da napravi self-extracting
arhivu, on iz 'svog' fajla izvlači onih poslednjih 30 bajtova,
na njih nadovezuje arhivu i tako dobija izvršni fajl. Naravno,
potrebno je da modul za raspakivanje zna svoju dužinu, da bi znao
gde počinje arhiva, i to je to...
algoritmi.67peca.st,
!-> Kako bi ti napravio ARJ sa self-extract mogućnošću. Kao što znaš,
!-> ARJ.EXE je samo JEDAN fajl i iz njega se dobija drugi EXE. Ako je
!-> sad jasnije, baci malo koda, ako imaš vremena.
Ako hoćeš da praviš exe - moraš da praviš kompajler, a to nije lako. :)
Međutim, ono što radi ARJ je moguće napraviti ovako:
1) Napraviti nešto što se zove recimo "unarj.exe", dakle program koji
služi samo za otpakivanje.
2) Pročitati taj unarj.exe u neki niz bajtova (koji pripada programu arj).
3) Kada se želi napraviti self-extract program, ispisati taj niz u fajl
željenog imena i na kraju tog fajla, na način koji je ovde već pomenut
dopisati arhivu - kao da je pravljena obična arhiva.
Naravno, kada se startuje tako dobijen program on nađe svoj kraj i odatle
počne normalno da otpakuje - kao da otpakuje običnu arhivu. Podrazumeva se
da je ovo implementirano u "unarj.exe".
Peđa.
algoritmi.68miljko,
>> Gde ovo cudo moze da se nadje ? ( ima li sors? )
Imaš ga vezanog za poruku: PC.UTIL.2 poruka 9.130.
Nažalost nema sors.
algoritmi.69janko,
> /* javnosti i pre tog programa. Ovo sve prema takstu iz
> .DOC. Ima li neko /* svežije vesti, kako teče suđenje?
>
> Ne znam za suđenje, ali je neko skoro okačio na FON (tin)
> Cimermanovo pismo u kome on tvrdi da je 2.6 OK, da nema
> backdoorova i da on lično nadgleda rad
Valjda je OK, ali Evropa nema pravo da ga koristi. Ja držim 2.6 na
disketi (ako neko neobavešten pošalje poruku šifrovanu sa 2.6) a 2.3a na
disku, i koristim. Ovo je i prostije rešenje od pačovanja 2.3.
Usput, u 2.6 su ograničili i dužinu ključa na 1024 bita. Proračuni da je
512 bita dovoljno su stari četrnaestak godina (još uvek je sasvim
dovoljno, ali za razbijanje na mašinama koje nisu u vlasništvu vlada ;) ).
algoritmi.70bulaja,
**** new file ****
R:\IBMPC\PROGRAM\*.*
----------------------
crc_v3 zip 27490 Vodič kroz CRC algoritme za detekciju grešaka
A PAINLESS GUIDE TO CRC ERROR DETECTION ALGORITHMS
==================================================
"Everything you wanted to know about CRC algorithms, but were afraid
to ask for fear that errors in your understanding might be detected."
Table of Contents
-----------------
Abstract
1. Introduction: Error Detection
2. The Need For Complexity
3. The Basic Idea Behind CRC Algorithms
4. Polynomical Arithmetic
5. Binary Arithmetic with No Carries
6. A Fully Worked Example
7. Choosing A Poly
8. A Straightforward CRC Implementation
9. A Table-Driven Implementation
10. A Slightly Mangled Table-Driven Implementation
11. "Reflected" Table-Driven Implementations
12. "Reversed" Polys
13. Initial and Final Values
14. Defining Algorithms Absolutely
15. A Parameterized Model For CRC Algorithms
16. A Catalog of Parameter Sets for Standards
17. An Implementation of the Model Algorithm
18. Roll Your Own Table-Driven Implementation
19. Generating A Lookup Table
20. Summary
21. Corrections
A. Glossary
B. References
C. References I Have Detected But Haven't Yet Sighted
algoritmi.71omega,
Ţ PGP 2.6 ne treba da koristite ako nekome saljete postu. Jedino ga treba
Ţ koristiti ako primite postu od nekog Amera koji je "taze" kupio bas tu
Ţ verziju, jer od prvog septembra 2.3 ne desifruje fajlove napravljene sa
Ţ 2.6 (2.6 je tako napravljen da 1. septembar bude prelomni datum).
Ne vidim zasto ne treba da ga koristimo!?
Ţ 2.6 je, inace, 2.3 preraden za americko trziste (tj. tako da ima
Ţ najmanje pravnih prepreka). Evropa bi trebalo da i dalje koristi 2.3.
Ţ Ko ima sors za 2.3 moze za par minuta da prepravi 2.3 da radi i sa
Ţ 2.6 fajlovima generisanim posle 1. septembra (nisu menjali nista u
Ţ algoritmima i strukturi, samo su upisali drugi broj u heder info, opet,
Ţ samo iz pravnih razloga).
I ne vidim zasto je to razlog da se vratimo na v2.3!? Pored te prerade
koju pominjes, ispravljeni su i neki bagovi.
algoritmi.72dragisha,
-> Radi se na razvijanju rutina za računanje osnovnih računskih operacija
-> (ADD, SUB, MUL, DIV). Caka je u tome što bi trebale da podržavaju
-> brojeve proizvoljne dužine (npr. 64-bitne, 128-bitne, 256-bitne).
GNU gmp-1.3.2.tar.gz, GNU multi prec. library.
--
[Stand back! I don't know how big this thing gets!]
algoritmi.73petkovicd,
U "Racunarima 101" u clipper savetniku pise kako se neki
podaci upisuju neku datoteku 'mag*.ntx' "...ali tako da formiraju
specijalnu strukturu (B-stablo)...".
Interesuje me da li se ova stuktura simulira pomocu relativnih
datoteka ili postoji i neko drugo resenje?
Ovo pitanje mozda spada u temu clipper ali mene ovo zanima
(zasad) samo s idejne strane jer kliper ne znam (jos!?) a
treba mi za neku datoteku koja bi se lepo organizovala uz pomoc
neke vrste pokazivaca.
:)ejan
algoritmi.74dr.grba,
>> Interesuje me da li se ova stuktura simulira pomocu relativnih
>> datoteka ili postoji i neko drugo resenje?
Kolega, da nisi ti neki GCOS ili HVS programer? (((:
algoritmi.75petkovicd,
A sta znaci GCOS ili HVS ?
algoritmi.76dr.grba,
>> A sta znaci GCOS ili HVS ?
Operativni sistemi Honeywell mašina. (:
algoritmi.77nbatocanin,
> Interesuje me da li se ova stuktura simulira pomocu
> relativnih datoteka ili postoji i neko drugo resenje?
NTX datoteke se sastoje iz zaglavlja u kome su zajedničke informacije
o indeksu (izraz, artibuti i sl.) i strana od po 1K koje sadrže
vrednosti ključa i pokazivače. Sama podela od po 1K nema značaja za
algoritam, već olakšava kasniju obradu (učitaš stranicu, analiziraš
vrednost, pa na osnovu odgovarajućeg pokazivača tražiš sledeću
stranicu). Sve se to radi u sasvim standardnoj DOS datoteci i koriste
se standardni DOS pozivi za čitanje/pisanje.
algoritmi.78dragisha,
-> Ovo pitanje mozda spada u temu clipper ali mene ovo zanima
-> (zasad) samo s idejne strane jer kliper ne znam (jos!?) a
-> treba mi za neku datoteku koja bi se lepo organizovala uz pomoc
-> neke vrste pokazivaca.
Pa ti si perspektivan!:) Nemoj ni da ga saznaš, najbolje:)).
Helem, B drveće imaš pristojno opisano, sa sve Pascal implementacijama, u
A+DS=P (po srpski to je Algoriths + Data Structures = Programs) od Wirtha.
A&DS=P je Modula-2 varijanta iste knjige.
Da ne bude da sam pristrasan (gdje bi ja?!:), po Sezam dirovima imaš
nekoliko C toolkitova sa sve sorsevima, koji rade sličan posao.
--
[Buddhism means never having to say you're sorry.]
algoritmi.79spantic,
> A+DS=P (po srpski to je Algoriths + Data Structures = Programs) od Wirtha.
> A&DS=P je Modula-2 varijanta iste knjige.
Što je svet mali :) Imam ja tu knjigu, doduše na ruskom. Ako kome
treba lako ćemo se dogovoriti. Ja je ionako ne koristim.
algoritmi.80dejanr,
Evo izvoda iz jedne, bojim se malo poduže, diskusije o šiframa sa BIX-a.
Vrlo detaljno razmatranje jedine šifre koja će zauvek ostati sigurna
(one-time pad), kao i drugih postojećih metoda... Vredi pogledati.
sifre.zipalgoritmi.81dragisha,
-> > A+DS=P (po srpski to je Algoriths + Data Structures = Programs) od
-> Wirtha. > A&DS=P je Modula-2 varijanta iste knjige.
->
-> Što je svet mali :) Imam ja tu knjigu, doduše na ruskom. Ako kome
-> treba lako ćemo se dogovoriti. Ja je ionako ne koristim.
Treba meni. :) Svoju (i rusku i englesku) sam ostavio za potpalu sretnom
nalazaču. Cijenu na mail :).
--
[Marriage is the main cause for divorce.]
algoritmi.82petkovicd,
>>Što je svet mali..
Jeste mali! I ja imam tu knjigu na ruskom .
:)ejan
algoritmi.83vsasa,
Da li neko ima algoritam racunanja kontrolnog broja fakture? To je
broj koji se dodaje na redni broj fakture. Sluzba platnog prometa
komitentima deli neke tabele sa vec izracunatim kontr. br., pa reko',
da ne idem da trazim od njih, ako vec ima na SEZAM-u...
Ako je vec bilo, dajte pointer...
CAO, Vsasa :)
algoritmi.84szeman,
>># => Izgleda da se ne razumemo dobro :(
>>
>> Jesi li razmotrio mogućnost da se baviš nečim manje
>> mentalno zahtevnim nego što je programiranje ? ;) Ako
>> nisi, sad je pravi trenutak. (Možda si samo neispavan?:)
Mogao bi da budeš malo pametniji i ovakve "dubokoumne" poruke preskočiš
i ukoliko znaš odgovor na pitanje, isto i napišeš.
>> Naravno, potrebno je da modul za raspakivanje zna svoju
>> dužinu, da bi znao gde počinje arhiva, i to je to...
Vidim da si došao do suštine problematike ;) Poenta je bila izračunavanje
funkcionalnog dela EXE na osnovu njegovog (EXE) header-a. O konstrukciji EXE
fajlova postoji nekoliko tekstova u R. koje nisam imao vremena da pročitam,
pa sam ovde pitao, ali kao što vidiš ;), nedovoljno precizno. Sve što je do
sada napisano je bilo vrlo očigledno, tako da je moja krivica što sam nejasno
formulisao pitanje. Izvinjavam se.
algoritmi.85dejanr,
>> Da li neko ima algoritam racunanja kontrolnog broja fakture? To je
>> broj koji se dodaje na redni broj fakture.
Bilo je u "Bajtovima lične prirode" pre dve godine, kada su uveli te
brojeve... evo ti paskal procedura koja ga računa, valjda se sa njom
snađeš ako treba u nekom drugom jeziku.
function kbroj(ulaz: string): integer;
var i, tmp: longint;
begin
tmp:=0;
for i:=length(ulaz) downto 1 do
begin
if (red[i]>='0') and (red[i]<='9') then
tmp:=tmp+(ord(red[i])-ord('0'))*(length(ulaz)-i+2)
else
begin
kbroj:=-1; exit;
end;
end;
tmp:=11-(tmp mod 11);
if tmp=10 then tmp:=0;
kbroj:=tmp;
end;
algoritmi.86petkovicd,
>>-> treba mi za neku datoteku koja bi se lepo organizovala uz pomoc
>>-> neke vrste pokazivaca.
>>
>> Pa ti si perspektivan!:) Nemoj ni da ga saznaš, najbolje:)).
Ja ne znam zašto ovo pitanje tako gadno zviči ali od 3 čoveka koja su
replicirala 2 su imala sličan komentar :))
>> Helem, B drveće imaš pristojno opisano, sa sve Pascal implementacijama, u
>>A+DS=P (po srpski to je Algoriths + Data Structures = Programs) od Wirtha.
Koliko sam ja video tamo se radi o B drveću koje se pravi od pokazivača
ali onih koji sadrže adresu memorijske lokacije dinamičke promenljive.To
nije tako strašno i s tim bi se izašlo na kraj.
Mene je interesovalo isto to samo malo drugačije. I to u radu sa datotekama.
Nbatocanin je opisao ono što me je intersovalo.Samo da je malo detaljnije...
Mada je i ideja bila sasvim OK.
:)ejan
algoritmi.87snemcev,
>> Da li neko ima algoritam racunanja kontrolnog broja fakture?
Bilo je nekoliko puta. Pointer? Sorry, nema ga. Uglavnom, radi se o
kontrolnom broju po modulu 11.
algoritmi.88dragisha,
-> Koliko sam ja video tamo se radi o B drveću koje se pravi od pokazivača
-> ali onih koji sadrže adresu memorijske lokacije dinamičke promenljive.To
-> nije tako strašno i s tim bi se izašlo na kraj.
-> Mene je interesovalo isto to samo malo drugačije. I to u radu sa
-> datotekama. Nbatocanin je opisao ono što me je intersovalo.Samo da je
-> malo detaljnije... Mada je i ideja bila sasvim OK.
Algoritme iz knjige koje sam spomenuo sam modifikovao upravo za datoteke.
U polje koje je pokazivač na mem.lokaciju staviš redni broj sloga u
najobičnijoj sekvencijalnoj datoteci i to je to.
--
[Help stampout 'smart mouthed' Sysops!]
algoritmi.89petkovicd,
>> ajobicnijoj sekvencijalnoj datoteci
A sto sekvencijalnoj? Valjd┐╗a relativnoj... jer sta se dobija time sto
nadjes mesto u sekvencijalnoj datoteci a onda prodjes kroz celu datoteku a bi
pronasao trazeni slog?
algoritmi.90dragisha,
-> >> ajobicnijoj sekvencijalnoj datoteci
->
-> A sto sekvencijalnoj? Valjd┐╗a relativnoj... jer sta se dobija time sto
-> nadjes mesto u sekvencijalnoj datoteci a onda prodjes kroz celu datoteku
-> a bi pronasao trazeni slog?
Svejedno, na DOS nivou postoji samo jedna vrsta datoteka, i ta vrsta nije
striktno ni sekvencijalna niti relativna. Svaki od dva pojma je podjednako
tačan i pogrešan :).
--
[Ask not for whom the bell tolls; let the machine get it]
algoritmi.91nbatocanin,
> A sto sekvencijalnoj? Valjda relativnoj...
Hm... DOS i nema ono što se u literaturi zove "sekvencijalna"
datoteka.
algoritmi.92petkovicd,
>>HM..DOS i nema..
Ja sam samo odreagovao na "sekvencijalna" a šta dos ima to ustvari i ne znam
na nivou DOSa (tj kako on radi sa datotekama).MM(Svako objašnjenje je
dobrodošlo na mail)
algoritmi.93mdrazic,
> Hm... DOS i nema ono što se u literaturi zove
> "sekvencijalna" datoteka.
Zar nije termin 'sekvencijalna' vezan za logički, a ne
fizički pristup datoteci? Šta koga briga kako operativni
sistem nju beleži na disk, važno je kako se sa njom radi,
odnosno kako se pristupa istoj. Onda bi DOS valjda imao
i ovaj tip datoteke. :)
Milan
algoritmi.94milan,
>> Hm... DOS i nema ono što se u literaturi zove
>> "sekvencijalna" datoteka.
>
> Zar nije termin 'sekvencijalna' vezan za logički, a ne
> fizički pristup datoteci? Šta koga briga kako operativni
> sistem nju beleži na disk, važno je kako se sa njom radi,
> odnosno kako se pristupa istoj. Onda bi DOS valjda imao
> i ovaj tip datoteke. :)
Pa da.
Upravo zato DOS i nema ono što se "u literaturi zove
'sekvencijalna' datoteka". ;>
Pl poz M
algoritmi.95nbatocanin,
> na nivou DOSa (tj kako on radi sa datotekama).MM(Svako
> objašnjenje je dobrodošlo na mail)
Pretpostavljam da može i ovde? DOS ima funkcije za elementarne
operacije sa datotekama. Prvo se datoteka kreira ili otvara (ako već
postoji). Zatim se može upisati zadati niz bajtova ili pročitati niz
bajtova u bafer od tekuće pozicije specijalnog pokazivača koji se po
otvaranju postavlja na početak datoteke. Ovaj pokazivač se može
pomerati posebnom funkcijom na zadatu poziciju (izraženu u bajtovima
počev od početka, kraja datoteke ili tekuće pozicije pokazivača). Na
kraju rada se datoteka zatvara i to je to. Postojanje funkcije za
pomeranje pokazivača omogućava da se u datoteku smesti proizvoljna
grafoidna struktura: jednostavno podeliš datoteku na blokove, pri
čemu svaki blok sadrži adrese blokova sa kojima je u vezi.
algoritmi.96nbatocanin,
> Zar nije termin 'sekvencijalna' vezan za logički, a ne
> fizički pristup datoteci?
Zavisi kako ga definišeš :) U principu se pod sekvencijalnom
datotekom podrazumeva datoteka na trakama gde možeš samo redom da
čitaš/upisuješ podatke i nema previše slobodnog skakanja napred/nazad.
Po ovome više i nema sekvencijalnih datoteka ;)
algoritmi.97dragisha,
-> > Zar nije termin 'sekvencijalna' vezan za logički, a ne
-> > fizički pristup datoteci?
->
-> Zavisi kako ga definišeš :) U principu se pod sekvencijalnom
-> datotekom podrazumeva datoteka na trakama gde možeš samo redom da
-> čitaš/upisuješ podatke i nema previše slobodnog skakanja napred/nazad.
-> Po ovome više i nema sekvencijalnih datoteka ;)
Ima, i biće ih dok je traka :).
Na 'normalnim' medijima, sve je do apstrakcije koja se koristi.
--
[Love of money is the root of all politics.]
algoritmi.98.braca,
Potreban mi je algoritam za dekompresiju JPG format.
algoritmi.99djelovic,
***************************************************************************
* *
* SEZAMOVO TAKMIžENJE U PROGRAMIRANJU JE OTVORENO OVOM PORUKOM *
* *
***************************************************************************
1. Zadatak se nalazi niže o ovoj poruci.
2. Takmičenje je u tome ko brže reši zadatak - prvo tačno rešenje poslato
na Sezam donosi svom tvorcu jednogodišnju pretplatu na Sezam. Kao i u
životu, nema nagrade za drugo mesto :).
3. Takmičenje se zatvara sutra u ponoć. Ukoliko do tada na Sezam ne stigne
ni jedno tačno rešenje (program koji daje tačne rezultate za sve test
primere), onda se programi rangiraju po tome koliko su test primera
tačno "rešili".
4. Test primeri nisu unapred poznati takmičarima.
5. U slučaju pod (4) ukoliko programi više takmičara reše isti broj
test primera, onda oni dele nagradu.
------------------------------------------------------------------------
Ukoliko neko pošalje svoje rešenje u konferenciju, to ne znači da je
takmičenje gotovo - pitanje je da li njegovo/njeno rešenje može da prođe
sve test primere.
-------------------------------------------------------------------------
===========================================================================
ZADATAK
===========================================================================
Napravite program koji:
1. Učitava N tačaka u ravni iz datoteke koja mu je prosleđenja preko
komandne linije. Tačke su zadate svojim X i Y koordinatama.
2. Ispisuje na ekran površinu poligona zadatog gornjim tačkama. Pri tom se,
naravno, misli na poligon zadat linijama od prve do druge tačke, od
druge do treće, ... , od predposlednje do poslednje, i od poslednje do
prve.
3. Ulazna datoteka je data u obliku:
<broj tačaka>
<X koordinata prve tačke> <Y koordinata prve tačke>
<X koordinata druge tačke> <Y koordinata druge tačke>
<X koordinata treće tačke> <Y koordinata treće tačke>
...
<X koordinata poslednje tačke> <Y koordinata poslednja tačke>
**************************************************************************
NAPOMENA: Zadati poligon ne mora da da bude konveksan - može biti, recimo,
zvezdastog oblika.
**************************************************************************
PRIMER:
=========================================================================
Ulazna datoteka TEST.DAT:
--------------------
4
0 0
100 0
100 100
0 100
--------------------
Startovanje programa:
--------------------
POLIGON TEST.DAT
--------------------
Izlaz:
--------------------
Površina unetog poligona je 10000.
--------------------
algoritmi.100djelovic,
Izvinjavam se što je ova poruka kasnila pa takmičenje nije počelo tačno
u 11:00, ali proradio je Marfi: vezu sam uporno pokušavao da dobijem sat
vremena.
BTW, priloge šaljite u ovu temu.
algoritmi.101dvesic,
Evo jednog resenja u TP6.0.
Bez komentara je (obicna analiticka geometrija), jer sam zurio ;)
Dacu ih naknadno (ako osvojim nagradu :))))
Pozdrav,
Dejan.
poligon.arjalgoritmi.102bojt,
da li linije poligona mogu da se seku?
algoritmi.103omega,
Ţ * SEZAMOVO TAKMICENJE U PROGRAMIRANJU JE OTVORENO OVOM PORUKOM *
Evo...Ako nije dovoljno 5000 koordinata, javite da prekompajliram ;)
omega.exealgoritmi.104eagle,
> ===========================================================================
> ZADATAK
> ===========================================================================
eagle.exealgoritmi.105djelovic,
> da li linije poligona mogu da se seku?
Ne.
algoritmi.106de.pavlov,
Zadatak ...
dp.exealgoritmi.107mmitrovic,
Ů█▀█Ţ 2. Takmičenje je u tome ko brže reši zadatak - prvo tačno rešenje
Oće'l biti neko duže takmičenje (dok sam ja pročitao o takm. već
je bilo pola dvanaest) za nas koji ne visimo na sezamu 24h. ;)
Nešto sa težim pitanjima i nekim cakama.
algoritmi.108djelovic,
*****************************************************************************
Pobednik SPrvog Sezamovog Takmičenja u Programiranju je dvesic. Njegov
program je prošao sve test primere, a usput ga je uradio za samo 1:40
od ostavljanja zadatka!
Kao pobednik dvesic je dobio godišnju pretplatu na Sezam. žestitamo!
*****************************************************************************
algoritmi.109djelovic,
> Oće'l biti neko duže takmičenje (dok sam ja pročitao o takm. već
> je bilo pola dvanaest) za nas koji ne visimo na sezamu 24h. ;)
> Nešto sa težim pitanjima i nekim cakama.
Zavisi od interesovanja.
(Upravo pokušavam da sortiram podatke koliko je ljudi učestvovalo u ovom
takmičenju. S obzirom na prirodu takmičenja takav podatak je nemoguće direktno
prikupiti, već se koristim "indeksom zauzetosti pri zvanju Sezama u nedelju",
što priznaćeš, i nije baš najpouzdanija metoda :).)
algoritmi.110dvesic,
>> Kao pobednik dvesic je dobio godisnju pretplatu na Sezam.
>> Cestitamo!
Hvala ! :)))
algoritmi.111de.pavlov,
[ 1.99 djelovic ]
>> 3. Takmičenje se zatvara sutra u ponoć. Ukoliko do tada na Sezam ne stigne
>> ni jedno tačno rešenje (program koji daje tačne rezultate za sve test
------------- ----------------------------------------------
>> primere), onda se programi rangiraju po tome koliko su test primera
-------
>> tačno "rešili".
[ 1.108 djelovic ]
> Pobednik SPrvog Sezamovog Takmičenja u Programiranju je dvesic. Njegov
> program je prošao sve test primere,
----------------------------------
Kada se radi sa test primerima, i na osnovu njih daje ocena o kvalitetu
programa, tada postoji rizik da test primeri nisu dobro odabrani.
Za test primer :
4
0 0
0 100
100 100
100 0
program poligon.exe daje rezultat -10000.00 , negativnu površinu.
Ali, nagrada ostaje jer je program prošao sve test primere :)
algoritmi.112dvesic,
>> program poligon.exe daje rezultat -10000.00 , negativnu
>> povrsinu.
Moja greska :), jer nisam stavio jedno Abs(Pov) ili napomenuo
da program ocekuje tacke rasporedjene u smeru kretanja suprotno
od kazaljke na satu.
algoritmi.113mdrazic,
> Kao pobednik dvesic je dobio godišnju pretplatu na Sezam. žestitamo!
Bravo, majstore!
Milan
algoritmi.114djelovic,
> program poligon.exe daje rezultat -10000.00 , negativnu površinu.
> Ali, nagrada ostaje jer je program prošao sve test primere :)
Negativnu povrsinu je "ulovio" jos prvi test primer, ali to
spada samo u "presentation error". Kako je naglasak takmicenja bio na
brzini rada, nije bilo svrhe sankcionisati ga.
algoritmi.115dr.grba,
>>> Kao pobednik dvesic je dobio godišnju pretplatu na Sezam. žestitamo!
>>
>> Bravo, majstore!
Dejan osvetla obraz PMF-u (((:
algoritmi.116de.pavlov,
> Negativnu povrsinu je "ulovio" jos prvi test primer, ali to
> spada samo u "presentation error". Kako je naglasak takmicenja bio na
> brzini rada, nije bilo svrhe sankcionisati ga.
Površina poligonske površi je po definiciji (tj. preciznije rečeno
po teoremi) nenegativan realan broj ( >= 0 ), pa je dakle negativna
površina nepriznata u Geometriji ("nauka o merenju").
Znači, _negativna površina_ je _suštinska greška_ i ne može se
podvesti pod _grešku u predstavljanju_ ("presentation error").
Zanimljivo je netačan rezultat nazvati "greškom u predstavljanju". :)
To na čemu je bio naglasak ne poriče netačnost rešenja. :)
algoritmi.117jmilovic,
Potrebna je pomoc studentu prve godine ETF u Novom Sadu, za predmet
osnovi racunarstva.
Profesor koji predaje ovaj predmet zove se Danilo Obradovic i
drzi katedru za racunarstvo na PMF u Novom Sadu.
Pomoc je potrebna za resavanje ispitnih zadataka iz prvog semestra.
Evo zadataka za koje je potrebno resenje:
Zadatak 1.
Dat je automat dijagram prelaza stanja. Izvrsiti projektovanje
minimalnog automata, pod uslovom da se stanja kodiraju 74-2-1 BCD KODOM
i da za realizaciju sekvencijalnog dela mreze raspolazete sa dva RS,
jedan T, jedan D i jedan JK ivicno okidana F/F BEZ PRESET/CLEAR ulaza.
Kombinacioni deo mreze realizovati:
a) UZ OSLONAC NA 2x MUX 8/1 i STAND. 2-ULAZNA NILI kola
b) ROM
Nacrtati logicku semu automata za obe varijante pobude
Zadatak 2.
Uz oslonac na PJ LILA 777 realizovati PRIJEMNIK i PREDAJNIK blokova
od po 32 x 32-bitnih reci. Ulazni blok predajnika kodiran je 2421 BCD
kodom. Blok koji se prenosi izmedju predajnika i prijemnika neophodno je
zastititi REDUDANTNIM kodom (m,3m). Na prijemnoj strani je neophodno
obaviti detekciju uz oslonac na princip najvece slicnosti i prijemni
blok predstaviti ASCII kodom.
Zadatak 3.
Data je realna kvadratna matrica X=(X ij) nxn za n < 20.
Nacrtati blok dijagram algoritma i napisati i napisati program u
programskom jeziku FORTRAN za odredjivanje elemenata jednodimenzionalnih
nizova A=(a1,..... an) i B=(b1,......bn) pri cemu su:
- elementi niza B maksimalni elementi iz vrsta matrica X.
sortirani po opadajucim velicinama
- elementi niza A mim\nimalni elementi iz kolona matrica X
sortirani po rastucim velicinama.
Za sortiranje elemenata koristiti podprogram opsteg tipa pod nazivom
SORT, a za odredjivanje maksimalnog odnosno minimalnog elementa koristiti
podprogram pod nazivom MAXMIN. Ulazne podatke ucitati proizvoljno, a na
izlazu stampati elemente nizova A i B ulazne matrice X sa odgovarajucim
naslovima.
algoritmi.118djelovic,
> pa je dakle negativna površina nepriznata u Geometriji ("nauka o merenju").
Ukoliko vec teramo mak na konac :(, postoje mnoge oblasti matematike u
kojima negativna povrsina i te kako ima smisla, zavisno od orijentacije.
Kada se razmislja o poligonima, geometrija nije jedina nauka na svetu :).
algoritmi.119omega,
Ţ Povrsina poligonske povrsi je po definiciji (tj. preciznije receno
Ţ po teoremi) nenegativan realan broj ( >= 0 ), pa je dakle negativna
Ţ povrsina nepriznata u Geometriji ("nauka o merenju").
Ţ Znaci, _negativna povrsina_ je _sustinska greska_ i ne moze se
Ţ podvesti pod _gresku u predstavljanju_ ("presentation error").
Ţ Zanimljivo je netacan rezultat nazvati "greskom u predstavljanju". :)
Ţ To na cemu je bio naglasak ne porice netacnost resenja. :)
Nesto se mislim, pa moj je bio sledeci primer i to tacan. Da krenem
i ja da se bunim ;>> Mislim da je de.pavlov u pravu.
algoritmi.120mdrazic,
> Znači, _negativna površina_ je _suštinska greška_ i ne može se
> podvesti pod _grešku u predstavljanju_ ("presentation error").
> Zanimljivo je netačan rezultat nazvati "greškom u predstavljanju". :)
> To na čemu je bio naglasak ne poriče netačnost rešenja. :)
Ne ljuti se, bio čovek brži od tebe, pa šta. Sledeći put ćeš
možda biti ti brži.
algoritmi.121omega,
Ţ Ukoliko vec teramo mak na konac :(, postoje mnoge oblasti matematike u
Ţ kojima negativna povrsina i te kako ima smisla, zavisno od orijentacije.
Ţ Kada se razmislja o poligonima, geometrija nije jedina nauka na svetu :).
Ali mi pricamo o geometriji.
algoritmi.122de.pavlov,
> Ukoliko vec teramo mak na konac :(, postoje mnoge oblasti matematike u
> kojima negativna povrsina i te kako ima smisla, zavisno od orijentacije.
> Kada se razmislja o poligonima, geometrija nije jedina nauka na svetu :).
Ovu diskvalifikaciju Geometrije ću shvatiti kao šalu.
U zadatku se tražila površina.
[ 1.99 djelovic ]
> 2. Ispisuje na ekran površinu poligona zadatog gornjim tačkama. Pri tom se,
--------
> naravno, misli na poligon zadat linijama od prve do druge tačke, od
> druge do treće, ... , od predposlednje do poslednje, i od poslednje do
> prve.
Stavimo na stranu to što ne postoji _površina poligona_ već
površina poligonske površi ("sinonimi" su : zatvorena poligonska linija,
poligon, mnogougao; unutrašnjost poligona p se naziva
_otvorena poligonska površ_ , a poligon p se zove rub te površi;
unija otvorene poligonske površi i njenog ruba se naziva
_zatvorena poligonska površ_ ). Značajno je to da se traži _površina_ .
A površina je nenegativan realan broj. Program poligon.exe daje
rezultat -10000.00 , negativnu površinu. Rezultat je netačan.
Naknadno tumačenje :
> postoje mnoge oblasti matematike u
> kojima negativna povrsina i te kako ima smisla, zavisno od orijentacije.
je samo po sebi kontradiktorno. Prvo se govori o negativnoj površini
a onda se uvodi u pomoć pojam orijentacije. Ne može se govoriti o
negativnoj površini već samo o orijentaciji. Površina ostaje nenegativna.
> Ukoliko vec teramo mak na konac :(
Zahtev za poštovanje egzaktnih matematičkih pojmova
zvati "teranje mak na konac" ? Duboko se ne slažem.
Nema problema da ko hoće gradi svoju matematičku teoriju.
Ali to onda treba saopštiti ostatku sveta. Ako se ne saopšti, onda ostaje
da se služimo onim što je do tada prihvaćeno.
algoritmi.123de.pavlov,
> Ne ljuti se, bio čovek brži od tebe, pa šta. Sledeći put ćeš
> možda biti ti brži.
Veoma mi je žao što si mi uputio ovakvu poruku. :(
algoritmi.124djelovic,
> Ali mi pricamo o geometriji.
Not realy, mi pricamo o izracunavanju povrsina, sto ne spada samo u
geometriju.
algoritmi.125dvesic,
Kako sam ja formalni pobednik (bar za sada ;) takmicenja, a kako
napadi i dalje traju osecam se pozvanim da odgovorim gospodi
de.pavlov i omega.
PC.PROG.4/1.116/ De.Pavlov
>> Povrsina poligonske povrsi je po definiciji (tj. preciznije
>> receno po teoremi) nenegativan realan broj ( >= 0 ), pa je
>> dakle negativna povrsina nepriznata u Geometriji ("nauka o
^^^^^^^^^^
Iz same postavke zadatka se vidi (ako treba, i objasnicu) da se
radi o ANALITICKOJ GEOMETRIJI, a tu je pojam negativne povrsine
poznat i priznat (zavisi od ORIJENTACIJE u ravni).
>> merenju"). Znaci, _negativna povrsina_ je _sustinska greska_ i
Iz gore navedenog sledi da ovo nije _sustinska greska_ :)
>> ("presentation error"). Zanimljivo je netacan rezultat nazvati
>> "greskom u predstavljanju". :) To na cemu je bio naglasak ne
>> porice netacnost resenja. :)
Porice, jer se trazila povrsina figure u analitickoj geometriji
(koliko mi je poznato, u Geometriji i ne postoji termin "koordinata
tacke" - mislim na standardnu Euklidsku Geometriju).
PC.PROG.4/1.122, 1.124
>> Ovu diskvalifikaciju Geometrije cu shvatiti kao salu.
Vidi gore.
Pozdrav,
Dejan Vesic.
algoritmi.126omega,
Ţ> Ne ljuti se, bio covek brzi od tebe, pa sta. Sledeci put ces
Ţ> mozda biti ti brzi.
Ţ
Ţ Veoma mi je zao sto si mi uputio ovakvu poruku. :(
Sta ces, ima takvih ljudi svuda...:(
algoritmi.127omega,
Ţ> Ali mi pricamo o geometriji.
Ţ
Ţ Not realy, mi pricamo o izracunavanju povrsina, sto ne spada samo u
Ţ geometriju.
Izracunavanje povrsine oblasti ogranicene poligonom nije CISTA
geometrija!?!?!?
algoritmi.128omega,
Ţ Iz same postavke zadatka se vidi (ako treba, i objasnicu) da se
Ţ radi o ANALITICKOJ GEOMETRIJI, a tu je pojam negativne povrsine
Ţ poznat i priznat (zavisi od ORIJENTACIJE u ravni).
Negativna povrsina priznata!?
algoritmi.129dvesic,
>> Negativna povrsina priznata!?
POJAM negativne povrsine, POJAM !
[ Ovo previse zamara, a i cemu vodi ? :(((((( ]
algoritmi.130dvesic,
>> Sta ces, ima takvih ljudi svuda...:(
Kakvih ljudi ?
algoritmi.131omega,
Ţ>> Negativna povrsina priznata!?
Ţ
Ţ POJAM negativne povrsine, POJAM !
???
Ţ [ Ovo previse zamara, a i cemu vodi ? :(((((( ]
Nicemu.
algoritmi.132omega,
Ţ>> Sta ces, ima takvih ljudi svuda...:(
Ţ
Ţ Kakvih ljudi ?
Nisam mislio na tebe...Procitaj ponovo...
algoritmi.133mdrazic,
>> 2. Ispisuje na ekran površinu poligona zadatog gornjim tačkama. Pri tom
> se, --------
>> naravno, misli na poligon zadat linijama od prve do druge tačke, od
>> druge do treće, ... , od predposlednje do poslednje, i od poslednje do
>> prve.
>
> Stavimo na stranu to što ne postoji _površina poligona_ već
> površina poligonske površi ("sinonimi" su : zatvorena poligonska linija,
> poligon, mnogougao; unutrašnjost poligona p se naziva
> _otvorena poligonska površ_ , a poligon p se zove rub te površi;
> unija otvorene poligonske površi i njenog ruba se naziva
> _zatvorena poligonska površ_ ). Značajno je to da se traži _površina_ .
Da se tražilo _bilo šta_ od ovoga što što ti navodiš (strogi termini)
tada bi ti bio u pravu. Ovako..., izgleda da ni tebi nije jasno šta se
tražilo u zadatku :)
> Naknadno tumačenje :
>
>> postoje mnoge oblasti matematike u
>> kojima negativna povrsina i te kako ima smisla, zavisno od orijentacije.
>
> je samo po sebi kontradiktorno. Prvo se govori o negativnoj površini
> a onda se uvodi u pomoć pojam orijentacije. Ne može se govoriti o
> negativnoj površini već samo o orijentaciji. Površina ostaje nenegativna.
>
>> Ukoliko vec teramo mak na konac :(
Kad već ti teraš. Ako posmatraš geometrijske likove samo kao skupove
tačaka bez orijentacije (koja je u zadatku bitno naglašena onim terminima
prva tačka, poslednja), tada ne bi postojali ni negativni uglovi. Da li
ćeš kao Don Kihot istrebljivati i pominjanje uglova kao što su -Pi/2 ?
To što ti do sada nisi naišao na zgodnu primenu negativno sračunatih
'površina' ne znači da nekim drugim ljudima to nije od koristi (mada
ni ja na takvu primenu još nisam naišao, ali ovo smatram potencijalno
korisnom mogućnošću).
Verujem da Dejan nije imao na umu ovakve primene, već mu se 'omaklo'.
Nije isterao 'šminku' algoritma, već je rešio suštinu problema, a na
(ipak za algoritam) manje važne detalje nije mislio. A i organizator
nije više bodovao šminku od suštine, što podržavam. Nemojte samo da
se preganjamo čiji je algoritam tačniji na devetoj decimali ako se to
nije tražilo u zadatku.
> Zahtev za poštovanje egzaktnih matematičkih pojmova
> zvati "teranje mak na konac" ? Duboko se ne slažem.
Kao što sam kažeš gore, egzaktan matematički pojam 'površine poligona'
nije ni pominjan u zadatku, već ga samo ti pominješ :) . Kakvo pitanje
(neegzaktno), takav je bio i odgovor (negativna 'površina'). Organizator
takmičenja i većina učesnika su se razumeli međusobno. Naravno da
postoji potreba za strogim definisanjem pojmova (i sam sam matematičar)
pa se pridružujem tvojoj sugestiji da se ubuduće više računa povede oko
definisanja problema. Ipak, ovu tvoju diskusiju ja shvatam kao
nepotrebno cepidlačenje. Zasviraj i za pojas zadeni.
Milan
P.S. Shvati ovo ipak kao igru (nagradnu, doduše), što i jeste, IGRA.
P.P.S. Dve pričice:
1. Nekad davno, početak 70tih, ispit iz FORTRAN-a. Posle pokazanog
odličnog znanja na pismenom i usmenom, poslednje pitanje:
Profesor: Kolega, koji se separator koristi u DATA komandi?
Student: ... _;_
Profesor: A, kolega, to je ozbiljna greška, koristi se _,_
I da mu 7.
2. Malo novije, pre desetak godina. Na pismenom ispitu iz Pascala
jedan student je sve lepo uradio, OSIM što je Pascal komande
napisao ćirilicom. Naravno, pao je, svi sa katedre za računarstvo
su se slatko zabavljali, nadam se samo da nije zabeležen u neki
crni tefter. U to vreme studenti NISU imali pristup računarima
da napiču ni "Hello world" (a ni danas na 4. godini većina stu-
denata na Matematičkom fakultetu osim sa smera za računarstvo nije
ništa napisala i prevela, a i za ove poslednje sumnjam da su svi),
a taj student i nije znao engleski. Greška postoji, ali da li je
za obaranje?
Sada se postavlja pitanje: šta je cilj ispita. Da li da ti naslepo
napišeš program koji radi bez ikakve greške, ili da rešiš problem u
smislu dobrog algoritma. Ono prvo je mnogo lakše pregledati i
samkcionisati, priznajem, ali...
algoritmi.134de.pavlov,
> Kako sam ja formalni pobednik (bar za sada ;) takmicenja, a kako
> napadi i dalje traju osecam se pozvanim da odgovorim gospodi
> de.pavlov i omega.
Nema napada. Ljudi razgovaraju o temi, iznose svoje argumente
i pokušavaju da nađu zajedničko rešenje. Danas se nalaze na raznim
stranama a sutra će već biti u istom poslu.
> >> To na cemu je bio naglasak ne porice netacnost resenja. :)
> Porice, jer se trazila povrsina figure u analitickoj geometriji
> (koliko mi je poznato, u Geometriji i ne postoji termin "koordinata
> tacke" - mislim na standardnu Euklidsku Geometriju).
Ne poriče, jer u :
[ 1.114 djelovic ]
> Negativnu povrsinu je "ulovio" jos prvi test primer, ali to
> spada samo u "presentation error". Kako je naglasak takmicenja bio na
----------------------------------
> brzini rada, nije bilo svrhe sankcionisati ga.
-----------
nema govora o naglasku na rešenju već o naglasku na brzini rada
( brzina slanja rešenja na Sezam ? ).
[ 1.125 dvesic ]
> (koliko mi je poznato, u Geometriji i ne postoji termin "koordinata
> tacke" - mislim na standardnu Euklidsku Geometriju).
Iz Aksioma Euklidske Geometrije se kao Posledica dobijaju koordinate.
---------------------------------------------------------------------
Mislim da je problem površine zanimljiv kako sa gnoseološkog,
ontološkog i lingvističkog tako i sa filosofsko-matematičkog aspekta.
Ostajem pri svojim argumentima.
algoritmi.135de.pavlov,
U principu mogu da se složim sa celom tvojom porukom, osim sa
delovima koji su pomalo "zlobno" intonirani. Pripišimo to temperamentu :) .
Zadenuo sam :)
algoritmi.136mdrazic,
>>> merenju"). Znaci, _negativna povrsina_ je _sustinska greska_ i
>
> Iz gore navedenog sledi da ovo nije _sustinska greska_ :)
Bug or feature ? :)))
algoritmi.137.ken.,
Haj,
Da li neko mozda zna kako se racuna obdanica tj.
racun kojim mogu dobiti kada izlazi a kada zalazi sunce
na ovom nasem podnevlju.
Potrebno mi je da bi ukljucivao/iskljucivao ulicnu rasvetu.
Znam da je problem vise vezan za astronome ali mozda neko zna.
algoritmi.138vlador,
> Potrebno mi je da bi ukljucivao/iskljucivao ulicnu rasvetu.
Zašto ne valja onaj standardni način sa foto-ćelijom?
algoritmi.139smoki,
>> površina nepriznata u Geometriji ("nauka o merenju").
Nauka o merenju bi trebala biti "Teorija mera", a Geometrija, kao što
sama reč kaže, je nauka o merenju zemlje (zemljišta). BTW, u Teoriji
mera SVE1 može imati meru, a ova može biti bilo šta tj. SVE2, pod
uslovom da SVE1 i SVE2 zadovoljavaju određena pravila. Tako imamo da
integral (koji je u 'matematici' većine tehničkih fakulteta 'priznat'
kao mera površine između neke krive i x-ose ) može biti pozitivan,
negativan ili čak kompleksan broj.
Naravno, ovo sa postavljenim problemom nema mnogo veze, jer se
prećutno podrazumeva prostor u kome se meri površina i način merenja
iste, pa tvoj prigovor stoji ( ZAISTA bi trebalo da površina bude
pozitivna), pod uslovom da se svi složimo oko ovih prećutanih detalja.
Dvesic bi, naprotiv, mogao da se pozove na površinu koja zavisi
od orjentacije (takav prostor - takva mera) i njegov program korektno
radi. Takođe, ako smo preko definicije površine prešli prećutno i
uzeli da je površina nenegativna, onda možemo preći i preko jednog
minusa ( koji se pojavi ponekad, tu i tamo :), pod uslovom da je ono
što stoji iza tog minusa korektno.
Dakle, obojica ste u pravu, a to vam je omogućio organizator ovog
natječaja, nepreciznom postavkom zadatka. Ali to nije jedini prigovor
organizatoru. (vidi sledeću poruku)
Miloš.
algoritmi.140smoki,
>> * SEZAMOVO TAKMIžENJE U PROGRAMIRANJU JE OTVORENO OVOM PORUKOM *
Da se u konferenciji (kao i više puta do sad) pojavila poruka tipa:
> Treba mi rešenje za taj-i-taj problem. Ko ga reši ima od mene
> zahvalnost, pivo u klubu, pretplatu ili letovanje na ________
> (upiši sam), sve ili nešto od toga...
razumeo bih hitnost (treba čoveku, a nema vremena da se sam bakće).
Međutim, takmičenje SEZAM-ovaca u programiranju! Takmičenje počinje
SAD a završava se ODMAH! Nikakva najava, priprema, (žiri?). Kao da su
na SEZAMU tri programera, pa da vidimo ko je brži. Ne čiji je PROGRAM
brži. Nego: ja ću da organizujem takmičenje u tome ko će se prvi
ulogovati posle mene, pročitati poruke iz pogodite-ako-vam-se-javi
konferencije i poslati odgovor u najkraćem mogućem vremenu.
Ako ne možete da dobijete SEZAM - loš ste programer :)))))))))))))
Dvesicu i pored svega čestitka. Na spretnosti i programiranju.
Ne bih želeo da se prigovor organizatoru shvati kao omalovažavanje
njegovog uspeha.
Gorčina u prigovoru potiče, delom, od toga što sam student koji od
programiranja (ovakvih i sličnih programa) živi i baš bi mi prijalo
da izvesno vreme ne razmišljam o tome gde da namaknem pare za
pretplatu ( o poskupljenju SEZAM-a i da ne govorim :( ). Ne kažem da
bih pobedio i da sam stigao da učestvujem, ali vredi pokušati, bio bi
to lep izazov. A deo gorčine je čisto principijelne prirode. Ko ima
nameru da organizuje nešto slično, nek svrati malo do kluba programe-
ra, pa da vidi kako se takmičenje SEZAM-ovaca u bilijaru odvija:
SLEDEĆEG PETKA U 20.00 TURNIR U BILIJARU! NAGRADA: PEžENO PRASE.
KO ZAKASNI - GLEDAĆE. KO PORANI - žEKAĆE. DOĐITE, PA DA VIDIMO
/pazi sad:/ KO JE BOLJI.
Organizatoru TAKMIžENJA U PROGRAMIRANJU nije bilo teško (nadam se) da
par dana ranije istakne propozicije, a sam zadatak u zakazano vreme.
Mislim da bi se time mnogo dobilo: više učesnika, a samim tim i više
rešenja (po zakonu prelaska kvantiteta u kvalitet i bolja rešenja);
relevantniji kriterijum za ocenjivanje, a o reklami za temu, odnosno
konferenciju i da ne govorim (sa svim propratnim pojavama).
Daklem, (nema ljutiš:) nadam se da će ove sugestije biti shvaćene
na pravi način, kao konstruktivne, te da ćemo uskoro imati novo,
masovnije takmičenje u programiranju.
Pozdrav, Miloš.
algoritmi.141djelovic,
> Međutim, takmičenje SEZAM-ovaca u programiranju! Takmičenje počinje
> SAD a završava se ODMAH! Nikakva najava, priprema, (žiri?). Kao da su
> na SEZAMU tri programera, pa da vidimo ko je brži. Ne čiji je PROGRAM
> brži.
Ideju za takmicenje ko brze pise program sam "ukrao" od ACM-a, sa
jednog takmicenja koje je sponzorisao Microsoft. Sto se tice najave, stvar
je u biltenima bila najavljena par dana unapred.
I najzad, nije bio cilj da se napravi nekakvo grandiozno takmicenje oko
koga bi se digla ovolika prasina (sta bi bila adekvatna nagrada pobedniku?
stogodisnja pretplata na Sezam?), vec nacin da se oprob snaga u odnosu na
druge, in good faith. Ukoliko si propustio ovu sansu, pa nije to tragedija
- slicnih takmicenja ce sasvim biti jos.
algoritmi.142de.pavlov,
> >> površina nepriznata u Geometriji ("nauka o merenju").
> Nauka o merenju bi trebala biti "Teorija mera", a Geometrija, kao što
> sama reč kaže, je nauka o merenju zemlje (zemljišta).
Potpuno se slažem, zato sam i stavio navodnike ("") u originalnoj
poruci. Ipak, ne samo o merenju zemljišta :)
Ali posle pominješ :
> Naravno, ovo sa postavljenim problemom nema mnogo veze, jer se
> prećutno podrazumeva prostor u kome se meri površina i način merenja
> iste, pa tvoj prigovor stoji ( ZAISTA bi trebalo da površina bude
> pozitivna), pod uslovom da se svi složimo oko ovih prećutanih detalja.
i to je bio moj glavni razlog prigovora.
O ostalom sam ponešto govorio u prethodnim porukama, ne bih da me
sada ponovo optuže za "cepidlačenje" :)
U sledećoj poruci si sasvim opravdano "razložio" takmičenje.
algoritmi.143omega,
Ţ Ideju za takmicenje ko brze pise program sam "ukrao" od ACM-a, sa
Ţ jednog takmicenja koje je sponzorisao Microsoft. Sto se tice najave, stvar
Ţ je u biltenima bila najavljena par dana unapred.
Zar je zaista bila najava? Koliko se secam bila je PORUKA tipa
"u nedelju iznenadjenje", ali BILTENA niti bilo kakve najave nije bilo.
algoritmi.144kriss,
˙˙ Međutim, takmičenje SEZAM-ovaca u programiranju! Takmičenje
˙˙ počinje SAD a završava se ODMAH! Nikakva najava, priprema,
A zadatke radite u MEĐUVREMENU! ;)
algoritmi.145.ken.,
>> Potrebno mi je da bi ukljucivao/iskljucivao ulicnu rasvetu.
>
> Zasto ne valja onaj standardni nacin sa foto-celijom?
Uh, znao sam da ovo nisam trebao napisati na kraju poruke.
Radim u Zrenjaninskoj distribuciji i imamo daljinsko paljenje
a i gasenje ulicne rasvete (radio vezom). Medjutim najgore je
sto mi i ne placamo struju koja se potrosi vec to radi grad
( a oni traze upravo da se pali po nekom algoritmu koji ne zavisi
od foto celije - oni kazu "pada kisa ceo dan 'gori' svetlo" ).
Sve u svemu, kriva je politika. Ako oni od gore tako kazu ja moram
da slusam. Zato pomagajte braco.
algoritmi.146djelovic,
> Zar je zaista bila najava? Koliko se secam bila je PORUKA tipa
> "u nedelju iznenadjenje", ali BILTENA niti bilo kakve najave nije bilo.
Bio je i BILTEN. BTW, uvek me je nerviralo sto dejanr na svaki bilten
stavi da se ponavlja dvestasezdesetsedam :) puta, ali sada vidim da takav
pristup i te kako ima dobrih strana :).
algoritmi.147paki,
> jednog takmicenja koje je sponzorisao Microsoft. Sto se tice najave,
> stvar je u biltenima bila najavljena par dana unapred.
Nešto se ne sećam da sam video bilo kakav bilten na tu temu...
algoritmi.148omega,
Ţ Bio je i BILTEN. BTW, uvek me je nerviralo sto dejanr na svaki bilten
Ţ stavi da se ponavlja dvestasezdesetsedam :) puta, ali sada vidim da takav
Ţ pristup i te kako ima dobrih strana :).
Bilten NIJE postojao. Toliko.
algoritmi.149kriss,
˙˙> jednog takmicenja koje je sponzorisao Microsoft. Sto se tice
˙˙> najave, stvar je u biltenima bila najavljena par dana
˙˙ unapred.
˙˙
˙˙ Nešto se ne sećam da sam video bilo kakav bilten na tu temu...
Moguće da je zaista nešto promaklo očima mojim, ali ni ja ne videh
bilten, već samo poruku ...
algoritmi.150kenza,
(;> Moguce da je zaista nesto promaklo ocima mojim, ali ni ja ne videh
(;> bilten, vec samo poruku ...
Ajde da se dodam i ja...
algoritmi.151szeman,
Svi koji se bave Clipperom, znaju čemu služi SOUNDEX() fj-a. Za one koji
ne znaju :) tom fj-om se konvertuje niz karaktera u "soundex" oblik pogodan
za indeksiranje ako nije tačno poznato spelovanje reči.
Postoji podatak da se algoritam nalazi u Knuth-ovoj knjizi "Sorting and
Searching, The Art of Computer Programming (Vol.3)", strana 392. E, bilo bi
lepo da onaj ko ima knjigu, ovo baci na uvid ovde ili meni na mail.
Pozdrav
algoritmi.152dpredovic,
> Postoji podatak da se algoritam nalazi u Knuth-ovoj knjizi
> "Sorting and Searching, The Art of Computer Programming
> (Vol.3)", strana 392. E, bilo bi lepo da onaj ko ima knjigu,
> ovo baci na uvid ovde ili meni na mail.
The following "Soundex" method, which was originally developed my
Margareth K. Odell and Robert C. Russell, has often been used for
encoding surnames:
1. Retain the first letter of the name, and drop all occurrences of a, e
h, i, o, u, w y in other positions.
2. Assign the following numbers to the remaining letters after the
first:
b,f,p,v -> 1
c,g,j,k,q,s,x,z -> 2
d,t -> 3
l -> 4
m,n -> 5
r -> 6
3. If two or more letters with same code were adjacent in the original
name (before step 1), omit all but first.
4. Convert to the form "letter, digit, digit, digit" by adding trailing
zeros (if there are less than three digits), or by droppping rightmost
digits (if there are more than three).
For example, the names Euler, Gauss, Hilbert, Knuth, LLoyd nd
Lukasiewicz have respective codes E460, G200, H416, L300, L222.
algoritmi.153szeman,
>> The following "Soundex" method, which was originally developed my
>> Margareth K. Odell and Robert C. Russell, has often been used for
>> encoding surnames:
Hvala ti puno.
Pozdrav, Saša