4-ProgramiranjeS
system:sage


<p>Isti matematički problem je često moguće rije&scaron;iti na različite načine, putem algoritama iza kojih stoje sasvim različiti načini razmi&scaron;ljanja. Razložimo to na primjeru funkcije faktorijel.</p>

{{{id=1|
factorial(7)
///
}}}

<p>Klasični način programiranja, upotrebljavan od dana prvih računala, je tzv. proceduralno (ili imperativno) programiranje kod kojeg&nbsp; na program gledamo kao na niz naredbi koje obično postupno mijenjaju vrijednosti nekih varijabli pohranjenih u memoriji računala:</p>

{{{id=2|
def factorialProc(n):
    fac = 1
    i = 1
    while i<n:
        i = i + 1
        fac = fac * i
    return fac
factorialProc(7)
///
}}}

<p>Zanemarite zasad preciznu sintaksu komande while. Ovdje je očito riječ o standardnom algoritmu kakvog bismo isprogramirali u bilo kojem proceduralnom jeziku poput Fortrana ili C-a: Imamo petlju koja se prolazi n puta i svaki puta množimo rezultat pro&scaron;log prolaza sa za 1 većim brojem.</p>
<p>Međutim, postoje i drugačiji pristupi. Tako je&nbsp; kod funkcionalnog programiranja naglasak na izvrijednjavanju funkcija tj. primjeni funkcija na izraze. Faktorijel prirodno zami&scaron;ljamo kao funkciju koja daje "umnožak svih brojeva od 1 do zadanog broja".</p>
<p>Kao prvo, treba nam modul 'operator' koji implementira <a href="http://docs.python.org/library/operator.html#mapping-operators-to-functions">funkcije</a> koje odgovaraju standardnim matematičkim operacijama *, +, -,...</p>

{{{id=5|
import operator
(operator.mul(2,3), operator.add(2,3))
///
}}}

<p>Zatim koristimo funkciju reduce(), koja kumulativno primjenjuje prvi argument (koji mora biti funkcija) na elemente drugog argumenta:</p>

{{{id=81|
f = function('f')
reduce(f, range(1,5))
///
}}}

{{{id=84|
reduce(operator.mul, range(1,8))
///
}}}

<p>Primijetite da nam ovdje nisu trebale pomoćne varijable (poput i i fac iz factorialProc), ali nam je trebalo vi&scaron;e memorije jer smo trebali pohraniti čitavu listu [1, 2, ...] koju daje range().</p>

<h2>Proceduralno programiranje</h2>
<p>Osnovna paradigma proceduralnog programiranja je da se kreće od nekog definiranog stanja programa (vrijednosti varijabli i nizova varijabli u memoriji računala). To stanje&nbsp; se specificira početnim naredbama pridruživanja (x=0, i=1)&nbsp; (assignment) i onda se algoritam izvodi primjenom raznih grananja, petlji i potprograma koji svi mijenjaju to stanje i vode na konačno stanje u kojem vrijednosti nekih varijabli odgovaraju rje&scaron;enju problema.</p>
<h3>if-then grananje</h3>
<ul>
</ul>
<p>Sintaksa je očita iz primjera:</p>

{{{id=87|
if 2>3:
    print "veći je"
elif 2==3:
    print "jednak je"
else:
    print "manji je"
///
}}}

<p>Ovdje treba paziti na uvlačenje blokova koda (tamo gdje bi u C-u bile vitičaste zagrade).</p>
<p>U uvjetima se mogu koristiti standardni logički operatori and, or, not, ...</p>

{{{id=89|
if 2>3 or 2<3:
    print "nisu isti"
///
}}}

<h3>Petlje</h3>
<p>Do-petlje ne postoje, ali postoje standardne while- i for-petlje. Primjer while petlje se vidi u primjeru factorialProc() na početku ovog odjeljka. For petlja ima specifičnu sintaksu</p>
<pre>for x in &lt;iterable&gt;:
    &lt;body&gt;</pre>
<p>gdje je &lt;iterable&gt; lista, tuple, skup, riječnik, ... Za prijevremeno iskakanje iz petlje postoji komanda "break". Npr. slijedeći algoritam pronalazi prvi cijeli broj čiji rastav sadrži vi&scaron;e od pet različitih prostih faktora.</p>

{{{id=11|
%time
for i in range(1,1e5):
    if len(factor(i))>5:
        break
print i
///
}}}

<p>Ovo je relativno neelegantan program za pronalaženje najmanjeg broja koji ima vi&scaron;e od pet različitih faktora. Bolje bi bilo</p>

{{{id=13|
%time
i = 1
while len(factor(i))<6:
    i +=1
print i
///
}}}

<p>a najbolje</p>

{{{id=14|
reduce(operator.mul, primes_first_n(6))
///
}}}

<p>ali ovo zadnje spada već u funkcionalno programiranje.</p>

<p><span id="cell_outer_29"><span id="cell_outer_10"><span id="cell_outer_5">&diams; </span></span><strong>Zadatak 4.1</strong>: </span>Isprogramirajte proceduralno funkciju fibProc(n) koja računa n-ti član <a href="http://en.wikipedia.org/wiki/Fibonacci_number">Fibonaccijevog niza</a> (niz kod kojeg&nbsp; je&nbsp; svaki član definiran kao zbroj prethodna dva, a javlja se pri analizi idealizirane populacije zečeva).</p>


<p><span id="cell_outer_29"><span id="cell_outer_10"><span id="cell_outer_5">&diams; </span></span><strong>Zadatak 4.2:</strong></span> Konstruirajte funkciju brown(n) koja daje listu $[ (x_0, y_0), (x_1, y_1), \ldots ]$ pozicija čestice koja se giba u ravnini slučajnim gibanjem koje je definirano rekurzijama $x_i=x_{i-1}+r$&nbsp; i&nbsp; $y_i=y_{i-1}+s$&nbsp; gdje su $r$ i $s$ slučajni brojevi između -1 i 1. Nacrtajte odgovarajuću putanju čestice.</p>
<p>Naputak:</p>
<ul>
<li>Inicijalizirajte listu pozicija tako da sadrži (0,0) kao prvi vektor pozicije i putem petlje dodajte u svakom koraku toj listi novi slučajni vektor.</li>
</ul>
<ul>
<li>Za crtanje možete koristiti list_plot(&lt;točke&gt;, plotjoined=True) </li>
</ul>
<p>&nbsp;</p>


<p><span id="cell_outer_104"><span id="cell_outer_29"><span id="cell_outer_10"><span id="cell_outer_5">&diams; </span></span><strong>Zadatak 4.3:</strong></span></span> Konstruirajte funkciju walk1D() tako da simulira tzv. jednodimenzionalnog nasumičnog &scaron;etača. Svaki &scaron;etačev korak treba biti iste, jedinične duljine, ulijevo ili udesno. Dakle, umjesto vektora (r, s) iz gornjeg Brownovog gibanja trebamo slučajan odabir koraka +1 ili -1. Provjerite ispravnost tvrdnje da je očekivana udaljenost nasumičnog jednodimenzionalnog &scaron;etača od ishodi&scaron;ta nakon $n$ koraka $\sqrt{n}$.</p>

<h2>Funkcionalno programiranje</h2>
<p>Funkcionalno programiranje je stil programiranja koji stavlja naglasak na izvrijednjavanje izraza,&nbsp; a ne na sukcesivno izvr&scaron;avanje komandi. Kod čistih funkcionalnih programa obično nema pomoćnih varijabli i nepotrebnih popratnih efekata izvrijednjavanja funkcija. U tom smislu funkcionalno programiranje je pomalo slično radu s tabličnim kalkulatorom (npr. MS Excel): redosljed izračunavanja ćelija je <br />nebitan tj. očekujemo automatsku konzistenciju. Isto, vrijednosti ćelija su dane izrazima, a ne slijedovima komandi. (Misli se na Excel, a ne Sage ćelije.)<br />(Vi&scaron;e informacija o funkcionalnom programiranju nudi&nbsp; <a href="http://www.cs.nott.ac.uk/~gmh//faq.html">Functional Programming FAQ</a> ili <a href="http://www.haskell.org/haskellwiki/Functional_programming">WWW stranice</a>&nbsp; Haskell funkcionalnog jezika.)<br /><br />Takav stil programiranja često rabi nekoliko specijalnih funkcija (mogli bismo ih zvati "meta-funkcije") čija je uloga upravljanje primjenivanjem drugih funkcija koje dolaze kao argumenti ovih meta-funkcija. Možda najvažnija takva funkcija je map():</p>

{{{id=29|
f = function('f')
map(f, range(4))
///
}}}

<p>Ukoliko funkcija prima vi&scaron;e argumenata, može se map()-irati na vi&scaron;e listi:</p>

{{{id=30|
map(f, range(4), range(3,7))
///
}}}

<p>Recimo da sad želimo ispisati tablicu s nizom prirodnih brojeva i njihovih faktorijela. Možemo prvo postupiti tako da prvo definiramo pomoćnu funkciju koja generira jedan red tablice i onda je pomoću map() primijenimo na niz brojeva:</p>

{{{id=53|
def auxfun(k):
    return (k, factorial(k))
///
}}}

{{{id=54|
map(auxfun, range(7))
///
}}}

<p>Međutim, ba&scaron; kao i pomoćne varijable, tako ni pomoćne funkcije nisu u duhu funkcionalnog programiranja. Zato postoje tzv. lambda-funkcije koje su bezimene i definiraju se i upotrebljavaju na slijedeći način:</p>

{{{id=55|
map(lambda k: (k, factorial(k)), range(7))
///
}}}

{{{id=128|
matrix(_)  # čitljiviji ispis bez uptrebe formatirajućih stringova
///
}}}

<p>Treba uočiti kako je često upotrebu funkcije map() i lambda-funkcija moguće izbjeći kori&scaron;tenjem obuhvaćanja liste. Npr, gornji primjer se elegantnije realizira ovako:</p>

{{{id=135|
[(k, factorial(k)) for k in range(7)]
///
}}}

<p>Kako su sage/python funkcije punopravni objekti, možemo i sami definirati funkcije koje primaju druge funkcije kao argumente (to smo već radili u pro&scaron;lom odjeljku). Evo funkcije koja implementira kompoziciju funkcija:</p>

{{{id=38|
def compose(f, n, x):
    """Uzastopno komponiranje funkcije sa samom sobom n puta."""
    if n <= 0: 
        return x
    x = f(x)
    for i in range(n-1): 
        x = f(x)
    return x
///
}}}

<p>Npr. tzv. zlatni omjer $(\sqrt{5}+1)/2$ se može izraziti kao beskonačni razlomak</p>
<p>$$ \frac{\sqrt{5}+1}{2} = 1+\frac{1}{1+\frac{1}{1+\frac{1}{1+\frac{1}{\cdots}}}} = 1.618034\ldots $$</p>
<p>Takav razlomak možemo izvrijedniti na slijedeći način:</p>
<p>&nbsp;</p>

{{{id=56|
gr = compose(lambda x: 1+1/x, 5, x); gr
///
}}}

{{{id=57|
gr.subs(x=1).n()
///
}}}

<p>Ili, uz povećanje točnosti:</p>

{{{id=58|
print "Golden ratio =\n%.14f" % n((1+sqrt(5))/2)
compose(lambda x: 1+1/x, 32, x).subs(x=1).n()
///
}}}

<h3>Primjer razvoja funkcionalnog programa</h3>
<p>Promotrimo razvoj programa koji ispisuje tablicu frekvencija pojavljivanja elemenata u listi. Načinimo prvo jednostavnu testnu listu</p>

{{{id=59|
lst = ['a', 'c','b', 'a', 'c', 'a', 'd', 'b', 'c','d', 'c']
///
}}}

<p>Metoda liste koja daje broj pojavljivanja nekog elementa je count()</p>

{{{id=60|
lst.count('c')
///
}}}

<p>Da bismo ispisivali tablicu trebamo listu oblika [(element1, frekvencija elementa1), (element2, frekvencija elementa2),...]. Element te liste (red tablice) se može dobiti ovako:</p>

{{{id=61|
def el(x):
    return (x, lst.count(x))
el('c')
///
}}}

<p>Tablicu frekvencija za različite elemente dobijemo kori&scaron;tenjem lambda-funkcije analogne el() i njenom primjenom pomoću funkcije map() na popis elemenata:</p>

{{{id=62|
map(el, ['a', 'b', 'c', 'd'])
///
}}}

{{{id=166|
map(lambda x: (x, lst.count(x)), ['a', 'b', 'c', 'd'])
///
}}}

<p>To je sad to, jedino jo&scaron; želimo izbjeći da sami moramo ručno identificirati koji se sve elementi pojavljuju u listi. To nam može raditi funkcija uniq() koja izbacuje duplikate iz liste:</p>

{{{id=63|
res = map(lambda x: (x, lst.count(x)), uniq(lst)); res
///
}}}

<p>Kao zadnju stvar, poželjno je listu sortirati po frekvencijama. Funkcija sorted()&nbsp; je već definirana tako da zna sortirati liste različitih objekata, no ovdje bi po defaultu sortirala parove po prvom elementu i to po abecednom redu, ...</p>

{{{id=146|
sorted(res)
///
}}}

<p>... a nama treba sortiranje po drugom elementu i to po veličini. Stoga moramo putem opcionalnog argumenta 'key' funkciji sorted() proslijediti funkciju koja će vraćati onaj dio elementa liste po kojem želimo sortiranje:</p>

{{{id=70|
def keyfun(item):
    """Return last element of item."""
    return item[-1]
///
}}}

{{{id=65|
sorted(res, key=keyfun, reverse=True)
///
}}}

<p>(Opcionalni argument reverse daje silazno sortiranje umjesto defaultnog uzlaznog.)</p>

<p>Naravno, i ovu pomoćnu funkciju keyfun() možemo zamijeniti lambda funkcijom:</p>

{{{id=69|
sorted(res, key=lambda it: it[-1], reverse=True)
///
}}}

<p>I to je to.&nbsp; Sad definiramo kompletnu funkciju:</p>

{{{id=67|
def frequencies(lst):
    """Elements of list lst with their frequencies."""
    return sorted(map(lambda x: (x, lst.count(x)), set(lst)), 
           key=lambda it: it[-1], reverse=True)
///
}}}

{{{id=68|
for it in frequencies(lst):
    print "%s: %d" % it
///
}}}

<p>Primijenimo to na frekvenciju pojavljivanja slova u Shakespeareovom Mletačkom trgovcu (zapravo koristimo engleski original The Merchant of Venice, skinut sa WWW stranica projekta Gutenberg)</p>

{{{id=71|
load('http://www.phy.hr/~kkumer/sp/venice.py')
///
}}}

{{{id=74|
print venice[:300]
len(venice)
///
}}}

{{{id=75|
for it in frequencies(venice)[:10]:
    print "%s:  %d" % it
///
}}}

<p>Vidimo da je "e" daleko najče&scaron;će slovo (poslije razmaka), činjenica vrlo važna pri de&scaron;ifriranju engleskih tekstova.</p>
<p>Kao netrivijalniji primjer upotrebe gore definirane funkcije compose() možemo nacrtati tzv. Mandelbrotov skup, definiran kao skup svih točaka $c$ kompleksne ravnine za koje iteracija</p>
<p>$$</p>
<p>z_0 = 0\;; \qquad&nbsp; z_{n+1} = z_{n}^2 + c</p>
<p>$$</p>
<p>ne divergira.</p>

{{{id=33|
complex_plot(compose(lambda z: z^2+x, 8, x), (-2, 1), (-1, 1))
///
}}}

<p>(Analizirajte sami kako radi ovaj "program".)</p>
<p><span id="cell_outer_104"><span id="cell_outer_29"><span id="cell_outer_10"><span id="cell_outer_5">&diams; </span></span><strong>Zadatak 4.4:</strong></span></span> Definirajte funkciju allequal() koja testira da li su svi elementi neke liste jednaki i iskoristite je da pronađete neprekidni niz od 6 istih znamenki u prvih 1000 decimala broja $\pi$. (Za pretvaranje broja u listu znamenaka možete iskoristiti funkciju str().) Koristite ili obuhvaćanje liste ili map() tj. nije dopu&scaron;teno kori&scaron;tenje petlji (for, while, ...) osim eventualno unutar funkcije allequal(), gdje to isto nije nužno (Hint: all()).</p>

<p><span id="cell_outer_104"><span id="cell_outer_29"><span id="cell_outer_10"><span id="cell_outer_5">&diams; </span></span><strong>Zadatak 4.5:</strong></span></span> Logističko preslikavanje je dano iteracijskom formulom $x_{n+1}= \lambda x_n(1-x_n)$.&nbsp; Za male vrijednosti parametra $\lambda$, to preslikavanje za veliki $n$ konvergira k jednoj vrijednosti. Kad $\lambda$ raste, negdje blizu $\lambda=3$, dolazi do bifurkacije i iteracije vi&scaron;e ne konvergiraju već skaču između dvije vrijednosti. S daljnjim rastom $\lambda$ dolazi do nove bifurkacije i sustav se za veliki $n$ ponavlja s periodom četiri, itd. Rezultat se može prikazati kao tzv. Feigenbaumov bifurkacijski dijagram (vidi sliku <a href="http://en.wikipedia.org/wiki/Logistic_map">ovdje</a>). Nacrtajte ga tako da prvo definirate funkciju composelist() koja je analogna gornjoj funkciji compose(), ali ne vraća samo kranji rezultat kompozicije funkcija već i listu sa svom međukoracima. Nakon toga iskoristite tu funkciju za iteriranje logističkog preslikavanja. Eliminirajte prvi dio liste (dok se iteracije ne stabiliziraju) i nacrtajte drugi dio pomoću list_plot(...., pointsize=1). Uočite da svaka vrijednost apscise lambda() traži posebno iteriranje.</p>

<p><span id="cell_outer_104"><span id="cell_outer_29"><span id="cell_outer_10"><span id="cell_outer_5">&diams; </span></span><strong>Zadatak 4.6(*)</strong></span></span>: Odredite najmanji prirodni broj koji se <em>ne može</em> dobiti iz brojeva 2, 3, 4 i 5 kori&scaron;tenjem operacija zbrajanja, oduzimanja i množenja, a gdje se svaki broj smije koristiti najvi&scaron;e jednom. (Npr. 1=3-2, 2=3-5+4, ..., 6=2*3, ..., 14=4*5-3*2, ... Naputak: Od koristi se možda može pokazati već ranije kori&scaron;teni modul 'operator', te funkcije permutations() i combinations().</p>

<p><span id="cell_outer_48"><span id="cell_outer_104"><span id="cell_outer_29"><span id="cell_outer_10"><span id="cell_outer_5">&diams; </span></span><strong>Zadatak 4.7</strong></span></span>:</span> Prim-brojevi blizanci su parovi prim-brojeva koji se razlikuju za dva, poput (3,5) ili (17,19). V. Brun je 1919. dokazao da suma recipročnih vrijednosti prim-brojeva blizanaca konvergira</p>
<p>$$</p>
<p>B=\left(\frac{1}{3}+\frac{1}{5}\right) + \left(\frac{1}{5}+\frac{1}{7}\right) + \left(\frac{1}{11}+\frac{1}{13}\right)&nbsp; + \left(\frac{1}{17}+\frac{1}{19}\right) + \cdots = 1.902160583104</p>
<p>$$</p>
<p>Ovako preciznu vrijednost je vrlo te&scaron;ko dobiti, no napi&scaron;ite funkciju brun(n) koja izračunava B koristeći listu od prvih n prim-brojeva. Inače, zanimljivo je da je upravo računalno određivanje ove konstante ukazalo na bug u prvoj generaciji Pentium procesora.</p>

<p>Literatura:</p>
<ul>
<li><a href="http://www.sagemath.org/doc/thematic_tutorials/functional_programming.html">Functional programming for Mathematicians</a></li>
</ul>
<ul>
<li><a href="http://docs.python.org/howto/functional.html">Opsežniji tekst</a> koji i kritizira upotrebu funkcionalnog programiranja u pythonu.</li>
</ul>

{{{id=187|

///
}}}