i
i
“1430-Vidmar-Stavek” — 2010/8/23 — 8:49 — page 1 — #1 i
i
i
i
i
i
List za mlade matematike, fizike, astronome in računalnikarje
ISSN 0351-6652
Letnik 28 (2000/2001)
Številka 1
Strani 29–31
Tim Vidmar in Andrej Likar:
STAVEK SE PREDSTAVI
Ključne besede: računalništvo, zgradba besedila, štetje črk, simuli-
rano kaljenje, programiranje.
Elektronska verzija:
http://www.presek.si/28/1430-Vidmar-Likar.pdf
c© 2000 Društvo matematikov, fizikov in astronomov Slovenije
c© 2010 DMFA – založništvo
Vse pravice pridržane. Razmnoževanje ali reproduciranje celote ali
posameznih delov brez poprejšnjega dovoljenja založnika ni dovo-
ljeno.
IRačunalništvo
STAVEK SE PREDSTAVI
Denimo, da beremo stavek , ki se glasi: "V te m stavku se poj avi a štiriin-
t rid esetkrat , b enkrat , c enkrat , č enkrat , d t rinajstkrat , e sedemint ride-
setkrat, f enkrat, genkrat , h enkrat , i dvajsetkrat, j sedemkrat , k sedemin-
dvajset krat , 1enkrat, m osemkrat, n devetnaj stkr at , o petkrat, p št irikr at,
r št ir iintridesetkrat , s osemkrat , š petkrat, t devetinš t ir idesetkrat, u dva-
kr at , v osemkrat, z enkrat in ženkrat ."
Resn ici na ljubo je to pr av dolgočasen stavek . Je pa zanimiv, saj
povs em drži. Vsaka črka se res pojavi to likokrat , kot je v stavku zapisano.
Poskusite zap isat i kak drug stavek, ki bo imel podobno lastnost . Staviva,
da ne bo prav pr eprosto.
Kako je uspelo nama? Najprej sva izbrala preprosto obliko st avka,
kot jo vidimo zapisano zgoraj - kratek uvodni del in nato naštevanje,
kolikokrat se pojavi posamezna črka. Nato sva uporabila računalnik , sa j s
poizkušanjem s svinčnikom in papirjem ne pridemo nikamor. Vendar t ud i
z računalnikom ne gre kar na slepo pr egledovati različnih mož nost i, saj
j ih je res zelo veliko. Poskusimo jih pr ešt et i. Sistematično bi lahko iskali
prave besede za črkami tako, da najprej za vse pr ivzamemo , da se poj avijo
"enkrat" , potem pa začnemo za črko a spreminjat i besedo na "dvakrat",
"t rikrat" in tako dalj e. Vedno pr everimo , ali srno uspeli sestavit i resnično
izjavo, in če ne, nadaljujemo. Nato spremenimo besedo za črko b na
"dvakrat" t er ponovimo t udi ves postopek s črko a . Tako nadaljuj emo
tudi z drugimi črkami . Vseh pr eizkusov bi bilo tako za vseh 25 črk 10025 ,
če privzamemo , da se nobena črka ne pojavi več kot stokrat. To je zelo
veliko število. Če bi veni sekundi preverili sto milijonov možnost i, bi vse
pr egledali šele v 3 x 1034 letih , kar je nepojmljivo dolg čas . Vedet i moramo,
da obstaja vesolje "le" kakih 1010 let . Napravo reš itev bi seveda naleteli
po manjšem številu pr eizku sov, a še vedno prevelikem za še tako hit er
superračunalnik. Število smiselnih možnost i lah ko s premislekom krepko
zmanjšamo. Hitro se da ugotoviti , da se bo do nekatere črke pojavile le
enkrat . Ker se pri vsaki črki pojavi besedica "krat" , začnemo pr i črkah ,
ki jih t a besed ica vsebuje , poskušanje z besedo "pe t indvajsetkrat " , saj
število po javitev teh črk ne bo manjše od 25. S te m se število možnost i
zelo zmanjša, a je še vedno pr eveliko , da bi stavek iskali na op isani način.
Naloge se lotimo drugače . Najprej pot rebujemo mero, ki pove, kako
dobro je stavek usklaj en s sami m sebo j . Kar sam se ponuja kvad rat
razlike med tem, kolikokrat se posamezna črka za res po javi v stavku in
kolikokrat je zapisano, da se po javi. Kvadrate razlik seveda seštejemo po
vseh petindvaj setih črkah . Če uspemo našo mero zmanjšati na nič , bo sta-
vek samousk laj en . Poskusimo s postopnim , a usmerje nim pr ibliževa njem
Računalništvo I
rešitvi: naključno izberemo eno izm ed črk , preštejemo, kolikokrat se za-
res pojavlja v st avku, in to vanj t ud i zapišemo. Seveda lahko s t em
ustvarimo novo neskladje , vendar upamo, da bomo s ponavljanjem takih
potez nazadnje uspeli . Potezo sprejmemo le, če se naša mera uspešnosti
po njej zmanjša, sicer pa vzpostavimo stanje pred njo in izb eremo novo
potezo . Izkaže se, da postopek deluje tako, da se mera uspešnosti sprva
hitro zmanjšuj e, nato pa obstane pri vr ednosti mere uspešnosti , ki je sicer
majhna , a ni enaka nič - naš postopek se je ujel v zanko brez konca. Tedaj
je smiselno vsaj začasno sprejeti tudi poteze, ki mere uspešnosti sice r ne
zmanjšajo, a vsaj prekinejo vrtenje v krogu. Nato pa se znova spustimo
v zmanjševanje razlik med resničnim in zapisanim stanjem.
V resn ici se lot imo st var i tako, da vedno dovolimo tudi poteze, ki mero
povečajo , vendar le z zelo majhno verjetnostjo, če je razlika med stanjem
na papirju in v resnici velika. Bolj ko se ta m anjša, bolj dopuščamo
možnost , da za trenutek napravimo tudi korak v napačno sm er , da se le
izognemo stopicanju na mestu. Naš algoritem izgleda takole:
Preberi stavek v začetni obliki.
Ponavljaj :
izberi eno izm ed črk ;
preštej št evilo pojavljanj te črke v stavku;
zapiši število pojavljanj t e črke v st avek;
za vsako od petindvajsetih črk:
preštej število pojavljanj te črke v stavku;
izračunaj mero ujemanja med dejanskim in zapisanim stanjem;
preveri, ali se je ujemanje izboljšalo:
da - skoči na konec zanke (na pogoj "dokler" );
ne - izračunaj verjetnost, da sprem embo vseeno odobrimo:
sprememba od obrena - skoči na konec zanke;
sprememba zavrnjena - vzpostavi stanje pr ed spremembo;
dokler ni popolnega ujemanja.
Zapi ši st avek na izhodno enoto.
Za ti ste , ki bi algor ite m želeli zapisati tudi v kakem programskem
jeziku, naj povemo, da kor ak, pri katerem se je mera uspešnosti spremenil a
za 6.8, sprejmemo z verjetnostjo e- f:',.s/T . Tu je T pozitivno št evilo, ki je
bilo v našem primeru enako 10, sicer pa pove nekaj o t em , kako zlahka
dovo limo poteze, ki stanje začasno po slabšajo. Če je T zelo velik , so
dovolj ene prav vse poteze, če pa je zelo majhen, ni mogoča prav nobena
poteza , ki stanja ne popravi . Vidimo tudi, da je vrednost zgornjega izraza
nti mah potem, ki &anj.e hbaljh, Mja od 1, mj je tds4j A$ d 
n%. To ilI%e~rdk=~ ti&, da Idso potem vedno tudi qx~tjfo~mc). 
-mN~m @ a  tmagM, je-kot 
lir- kdjtmjes, s a j  s p o w a  ma m p e k  abdhve kcwine, ki jo aajpqj 
mgr&m~o in nsta o h h i b o ,  da dmk.mo kar mjboQ aabflno in we- 
fern $truktm md. N h j u  temperatwe (n& paranetm 2') nstrw 
~ j ~ ~ e  m j e t n d  odobrhv sgrea-mib, Jri ne mdZjo v bQaj WE+ 
jeno stan&. V ~t~vW prb& upor& tdqp piwtopb je? kljuwo prav 
pravko postopno ~ m a q j w j e  t  verjWwd, deer se Iahko zgadi, 
da progrwi ner mjde najboljb dim, mpak bnEa v ndioniini %ankle 
Kmmhepcatcpkh~1~t ctmdbmW, kjtrr l&h sa&mio preide 
Y ~YIanje z *jo mefpjjjo, verj&& aa ka pa je pcmmma E; njegma temp 
m t m ,  Pa qjeg;wem avCcrrju ga imenujemo tPrdi M-olim pmbp&, 
Mjegrw apb najdemo nra primm v Wig$ 'Tlummilcal Wpwn, d d &  
10s [http://m..tir.cd). 
Za konec p-r&ejmo &b L enkrat. Ce u p o 3 t m  h d i  nsslov, 
i m d  in p r i b  avtarjev t.er opis dgdtmrs* se v %em sestavh pojarlja a 
~ 8 t O h ~ t ~ h ~ h ,  b # h k t ~ k r & ,  C dv(ad&h&, E d& 
h d e ~ t b t ,  d stoendnmdmdeatkrat, e ~t9t,~pethpetd&t, f dm- 
krat, g d&rid&ti, h pdhtrideeetkrat, i W i s t & t m I  j d e  
-dvtqj13eWI k dm-t, 1 sto* 1 
m d x & . & m  n t, o & k i & o ~ p e t W W ~  p 
d9leseop&aaj&t, r Wto+rnixtd'v&j-f, s tcM-&a& 
a3 dminmd&ht ,  t m a t ; ,  u p & d d w t h t J  v d&u- 
~ ~ j & ~ e i t ,  5 t&xi%staa*tt, in f tr lnaj&~t~ B;c#lte pmmdi? 
!Em V5oEmar, A&f L & ~ P