Algoritam i programiranje (osnovni pojmovi). Uvod u programski jezik Python

Neke definicije algoritma:

• precizno uputstvo za obavljanje zadatka… sa određenim osobinama: diskretnost ili razloživost; rezultativnost ili delotvornost, učinkovitost; determinisanost ili određenost(v. https://petlja.org)
• niz precizno opisanih koraka čijim se doslednim sprovođenjem dolazi do rešenja problema (v. Milena Marić. Škologija : iz učionice jedne beogradske gimnazije, https://skologija.wordpress.com/)
• konačan niz jasno definisanih koraka koji za date početne uslove vode do rešenja ili skup nedvosmislenih pravila u cilju rešavanja određenog tipa zadatka (v. Slavimir Stošović i Miloš Kosanović. Algoritmi i strukture podataka : Predavanja 1 do 6. Akademija tehničko-vaspitačkih strukovnih studija – Odsek Niš)

Stari, već poznati primeri algoritama:

• kuhinjski recepti (koh, šubarice, čupavci, supa, prženice)
• matematički algoritmi:
  • sabiranje, oduzimanje, množenje i deljenje dva prirodna broja u dekadnom brojnom sistemu (prva 4 razreda osnovne škole)
  • konstrukcija uglova od 90, 60 i 45 stepeni (5. razred osnovne škole)
  • pronalaženje kvadratnog korena datog pozitivnog broja (7. razred osnovne škole)
  • rešavanje sistema 2 linearne jednačine sa dve nepoznate (8. razred osnovne škole)
  • rešavanje kvadratne jednačine (2. razred srednje škole)
  • sabiranje i oduzimanje dva prirodna broja u binarnom i heksadekadnom brojnom sistemu (prva godina fakulteta, Informatika za bibliotekare 1)

Novi primeri algoritama (statistika):

• Algoritam zaokruživanja broja na zadati broj decimala
• Algoritam određivanja donje i gornje egzaktne granice broja (mere)
• Oba prethodna algoritma moraju najpre da odrede broj decimala u zapisu datog broja, što znači da koriste isti pomoćni algoritam za određivanje broja decimala.

Primeri programa zapisanih u programskom jeziku Python

• ispisivanje zbira dva uneta broja. Prvi (neuspešni) pokušaj (zbir-v1.py) i ispravno rešenje (zbir-v2.py)
• zapis jednostavnog algoritma za pretvaranje vrednosti memorijskog kapaciteta:
  • iz jedinice bajt (B) u jedinicu bit (b). Pogrešno (tebi-v1a.py) i ispravno rešenje (tebi-v1b.py)
  • iz jedinice tebibajt (TiB) u jedinice gibibajt (GiB), mebibajt (MiB), kibibajt (kiB), bajt (B) i bit (b) na programskom jeziku Python. Rešenje sa ispisivanjem u posebnom redu (tebi-v2.py) i rešenje koje ilustruje 5 načina za ispisivanje poruke i rezultata u istom redu (tebi-v3.py)

Osnovni pojmovi u programiranju na primeru programskog jezika Python:

• konstante (celobrojne konstante: 8, 1024; konstantne niske: 'Unesite prvi sabirak: ', 'Unesite drugi sabirak: ', 'Zbir unetih brojeva je: ')
• promenljive (sabirak1, sabirak2, zbir u programu tebi-v1a.py i tebi-v1b.py; tebi, gibi, mebi, kibi, bajt, bit u programima tebi-v2.py i tebi-v3.py)
• naredbe:
  • naredba dodele (promenljiva = izraz)
  • poziv funkcije (input() i print()). Sve što se unosi sa tastature kao ulaz programa, Python tretira kao tekst (nisku).
• komentari:
  • jednolinijski (#)
  • višelinijski ('''tekst između trostrukih apostrofa'''), pre zamena za komentar nego pravi komentar.
• tipovi podataka i njihove operacije:
  • niske (str), operacija dopisivanja (+)
  • celi brojevi (int), operacije sabiranja, oduzimanja, množenja, celobrojnog količnika i ostatka, stepenovanja (+, -, *, //, %, **)
  • vrednosti pojedinih tipova se mogu pretvoriti u odgovarajuće vrednosti drugog tipa (niska '25' u broj 25 i obrnuto) pomoću funkcija koje se zovu isto kao i sami tipovi (engl. casting):

    broj = int('25') #vrednost je ceo broj 25
niska = str(25) #vrednost je niska '25'

    Iako na prvi pogled deluje da nema razlike, postoji i razlika između internih reprezentacija konstanti 25 i '25', kao i razlika u pogledu operacija koje mogu da se izvode nad tim konstantama.
• potprogrami:
  • procedure. Nemaju povratnu vrednost i ne mogu se koristiti u okviru izraza, samo izvršavaju određeni niz naredbi.
  • funkcije.
    • Imaju (vraćaju) tačno jednu vrednost određenog tipa (vrednost funkcije). Vrednost funkcije se može koristiti u okviru izraza na mestu gde sme da se koristi konstanta ili promenljiva istog tipa:

      ime = 'Pera'
punoIme = ime + ' ' + input('Unesite prezime')
#Korisnik unosi sa tastature 'Mitić'
#Efekat je isti kao da je upotrebljena naredba
#punoIme = 'Pera' + ' ' + 'Mitić'

  • Python ima od potprograma ima samo funkcije, tj. uvek postoji neka vrednost, makar bila i ništa (None). Vrednost funkcije input() je niska koju je uneo korisnik. Vrednost funkcije print() je None (dakle, iako je funkcija, de facto se ponaša kao procedura).
• izrazi
  • konstante i promenljive su najprostiji izrazi, vrednost takvih izraza jednaka je vrednosti odgovarajuće konstante ili promenljive;
  • pozivi funkcija su takođe izrazi, vrednost takvih izraza je vrednost funkcije za ulazne argumente navedene u pozivu;
  • složeniji izrazi se dobijaju primenom operacija nad jednostavnijim izrazima, na primer:

    2 * (x % 4) ** int(input('Unesite ceo izložilac'))
#konstanta * (promenljiva % konstanta) ** poziv_fje(poziv_fje(konstanta))

Klase i objekti

Klase i objekti su uopštenja pojmova tip podataka i vrednost tipa podataka. Vrednosti konstanti i promenljivih u Python-u se realizuju kao objekti. Svaki objekat se može jednoznačno identifikovati adresom u memoriji, ima određena svojstva i ponašanje. Kao što smo vrednosti okupljali u određene tipove podataka (celi brojevi, realni brojevi, niske, logičke vrednosti), tako se objekti koji imaju zajednička svojstva i ponašanje okupljaju u klase. Klasa zapravo predstavlja apstraktan opis objekta (svojstva i ponašanje), njegov prototip i šablon, dok je objekat samo konkretan primerak (instanca) klase.

Svi do sada pomenuti tipovi podataka su klase u Python-u: int, bool, float, str.

Svaka klasa ima jedan specijalan metod (funkciju) koja se zove isto kao i sama klasa, a služi da konstruiše novi objekat klase. Konstruktori se takođe koriste za prividnu konverziju objekta jedne klase u objekat druge klase; u stvari, konverzije nema, već se konstruiše nov objekat od polaznog. Tipičan primer je kada se unosi ceo broj sa tastature pomoću funkcije input(); ova funkcija ima za rezultat nisku sa kojom ne može da se računa, pa je neophodno od te niske konstruisati ceo broj pozivom konstruktora klase int:

ceo_broj = int(input('Unesite ceo broj'))

Ovaj primer ujedno ilustruje kompoziciju funkcija, izlaz funkcije input() je ulaz konstruktora int().

Atributi i metodi objekta

Svojstva objekta klase se opisuju posebnim promenljivama koja se nazivaju atributi. Ugrađene klase kojima ćemo se baviti uglavnom nemaju atribute ili nam oni nisu od značaja, ali ako budemo pravili sopstvene klase, moći ćemo da definišemo atribute. Na primer, ako bismo obrađivali rezultate nekog ispita, mogli bismo definisati klasu Student koja bi imala atribute ime, prezime, indeks, poeni, prva tri kao objekte klase str, a poslednji kao objekat klase float. Dakle, jedan objekat može sadržati, kao svojstva, objekte drugih klasa.

Ponašanje objekta klase se opisuje pomoću posebnih funkcija koje se nazivaju metodi i sa njima ćemo najviše raditi. Nemoguće je naučiti sve metode čak ni osnovnih klasa poput str, a i za one čija imena upamtimo zbog čestog korišćenja, ne možemo držati u glavi broj i redosled njihovih argumenata; iz tih razloga uvek koristimo dokumentaciju ili podsetnik.

Ako je obj promenljiva koja sadrži neki objekat sa atributom svojstvo i metodom metod(), za pristup atributu, odnosno za pozivanje metoda objekta obj, koristi se tzv. tačka-notacija:

print(obj.svojstvo) #ispisujemo svojstvo objekta
obj.metod() #ako metod ne vraća nikakav rezultat, samo ga pozovemo
rezultat = obj.metod() #ako metod vraća rezultat, treba ga sačuvati u promenljivoj

Globalne funkcije

Postoje funkcije koje ne pripadaju nijednoj klasi. Tipičan primer su funkcije za ulaz i izlaz, input() i print(), a uskoro ćemo upoznati i funkciju len().

Klasa str i njen metod str.find(podniska)

• Nisku zamišljamo kao niz (uređenu kolekciju) karaktera.
• Dužina niske (ukupan broj karaktera) može se odrediti globalnom funkcijom len() koja se koristi i za određivanje broja elemenata drugih tipova kolekcija (listi, skupova, rečnika itd.).

  duzina = len('Python') # dužina niske je 6

• Specijalna vrsta niske je prazna niska '', niska koja ne sadrži nijedan karakter i ima dužinu 0.
• Svakom karakteru niske se može pristupiti pomoću naziva niske i njegove pozicije u okviru te niske. Ako je s niska dužine len(s), dozvoljene pozicije su rastuća lista brojeva od 0 do len(s) - 1 (kada se niz karaktera posmatra sleva nadesno), a takođe i opadajuća lista brojeva od -1 do -len(s) (kada se niz karaktera posmatra zdesna nalevo). Prema tome, s[0] = s[-len(s)] je prvi karakter niske sleva nadesno, odnosno poslednji karakter niske zdesna nalevo, dok je s[len(s)-1] = s[-1] poslednji karakter niske sleva nadesno, odnosno prvi karakter niske zdesna nalevo. Nenegativna pozicija niske je tačno za len(s) veća od odgovarajuće negatine pozicije.

  s = 'Python'
duzina = len(s) # dužina niske je 6
print(s[0]) # print(s[-6]) daje isti rezultat: 'P'
print(s[1]) # print(s[-5]) daje isti rezultat: 'y'
print(s[2]) # print(s[-4]) daje isti rezultat: 't'
print(s[3]) # print(s[-3]) daje isti rezultat: 'h'
print(s[4]) # print(s[-2]) daje isti rezultat: 'o'
print(s[5]) # print(s[-1]) daje isti rezultat: 'n'
  

• Podniskom ćemo nazivati bilo koji povezani deo niske. Podniska kojom niska počinje naziva se prefiks, podniska kojom se niska završava nazivamo sufiks, dok podnisku koja nije ni prefiks ni sufiks zovemo infiksom. S druge strane, podniz niske je bilo koji podskup karaktera niske uređen na isti način kao u okviru niske ili pak u obrnutom redosledu.
• Python nema poseban tip podataka za karaktere, već se karakter tretira kao podniska dužine 1.
• Izdvajanje podniski i podnizova se vrši posebnom tehnikom koju ćemo zvati seckanje (na kriške, engl. slicing). Seckanje se u opštem slučaju zapisuje na sledeći način:

  niska[početak:kraj:korak]

  Između srednjih zagrada navedeni su celi brojevi koji označavaju početnu i krajnju poziciju podniza, pri čemu se uzastopne pozicije razlikuju za vrednost korak. Ako je vrednost početak manja od vrednosti kraj i korak pozitivan broj, tada izraz u srednjim zagradama zapravo predstavlja skraćeni zapis sledećeg skupa

  [početak:kraj:korak] = {x | x = početak + n * korak < kraj, n = 0, 1, 2,…} =
= {početak, početak + korak, početak + 2 * korak, …} < kraj


  pri čemu sve vrednosti skupa moraju biti strogo manje od vrednosti kraj

  Na primer, [2:14:3] = {2, 2 + 3, 2 + 2 * 3, 2 + 3 * 3} = {2, 5, 8, 11},
  dok 2 + 3 * 4 = 14 ne dolazi u obzir jer nije manja od krajnje vrednosti (14), već joj je jednaka.

  Rezultat uvek sadrži karakter na početnoj poziciji početak i nikad ne sadrži karakter na krajnjoj poziciji kraj. Nijedan od brojeva u srednjim zagradama nije obavezno navesti i u tom slučaju se primenjuju podrazumevane vrednosti: 0 za početak, dužina niske za kraj i 1 za korak.
  Vrednosti sva tri broja mogu biti i negativne. Ako je vrednost za korak negativna, podniz se formira od karaktera sa pozicija u opadajućem redosledu (zdesna nalevo). Negativne vrednosti za početak i kraj označavaju poziciju karaktera u odnosu na desni kraj niske (pozicija -1 odgovara poslednjem karakteru, -2 pretposlednjem itd.).

• Primeri izvlačenja podniski pomoću opsega

Pretraga podniske

• str.find(podniska). Ako se zadata podniska nalazi u okviru niske koja poziva metod, rezultat je početna poziciju podniske (ceo broj veći od nule ili jednak nuli); u protivnom, rezultat je -1.

Metodi klase string (string methods)

Metodi su funkcije koje se mogu pozivati samo iz objekta čijoj klasi pripadaju (objektni metodi), a u pojedinim slučajevima i iz same klase (klasni ili statički metodi). Kao i u slučaju običnih funkcija, prilikom poziva se ne smeju razdvajati razmakom ime metoda i otvorena leva zagrada.

Ovde navodimo neke najvažnije objektne metode koje može pozvati proizvoljna niska:

Velika i mala slova

• str.lower(). Rezultat je dobijen prepisivanjem niske koja je pozvala metod pri čemu je svako veliko slovo zamenjeno malim.
• str.upper(). Rezultat je dobijen prepisivanjem niske koja je pozvala metod pri čemu je svako malo slovo zamenjeno velikim.

Prefiksi i sufiksi

• str.endswith(sufiks). Rezultat je logička vrednost (True ili False) koja ukazuje da li niska koja je pozvala metod sadrži zadati sufiks.
• str.startswith(prefiks). Rezultat je logička vrednost (True ili False) koja ukazuje da li niska koja je pozvala metod sadrži zadati prefiks.

Liste (klasa list). Petlje (for i while)

• Sa listom se radi na sličan način kao sa niskom:
  • funkcijom len() se određuje dužina liste,
  • elementima liste se pristupa preko indeksa (pozitivnih i negativnih koji se razlikuju od odgovarajućih pozitivnih tačno za dužinu liste),
  • a funkcioniše i seckanje kao način izdvajanja podliste.
• Ključne razlike su sledeće:
  • element liste može biti proizvoljnog tipa i različiti elementi ne moraju biti istog tipa;
  • za razliku od niske koja ne može da se menja (ne možete promeniti karakter niske, jedino možete napraviti novu nisku), lista može da se menja direktno na nivou pojedinačnih elemenata (promena vrednosti elementa, ubacivanje elementa na proizvoljnu poziciju, brisanje elementa sa proizvoljne pozicije).

Podela niske i spajanje u nisku

Sledeće funkcije omogućavaju da se niska razloži na listu podniski koristeći određeni separator, kao i da se od liste niski napravi jedinstvena niska primenom dopisivanja i eventualnog separatora.

• str.join (iterabilna kolekcija podataka). Rezultat je niska dobijena spajanjem (dopisivanjem) svih članova zadate iterabilne kolekcije podataka (obično niski kao članova), pri čemu su susedni članovi razdvojeni niskom koja je pozvala metod.
• str.split (separator). Rezultat je lista dobijena podelom niske koja je pozvala metod na listu njenih podniski koje su u okviru polazne niske razdvojene zadatim separatorom.

Pretvaranje niske u listu karaktera

Osim metoda str.split, niska se može razložiti na listu karaktera i pozivom funkcije list() (konstruktora klase list):

s = 'Python'
l = list(s)
print(l) #['P', 'y', 't', 'h', 'o', 'n']

Jednostavni algoritmi pretrage niske

• Problem: ispitivanje da li zadata niska s sadrži zadatu nisku t kao podnisku (s i t su proizvoljne niske). Pretpostavićemo da nemamo na raspolaganju metode poput str.find() i pokušaćemo da napišemo svoju verziju. Specijalni slučajevi: ako je dužina niske manja od dužine niske, onda je odgovor sigurno negativan; u slučaju kada je dužina niske 1, onda se problem svodi na traženje jednog karaktera u okviru niske.
• ispitivanje da li određeni karakter (tj. niska dužine 1) pripada zadatoj niski (specijalni slučaj problema).
• ispitivanje da li zadata niska s sadrži zadatu nisku t kao podnisku ( je proizvoljne dužine) metodom grube sile.