1 of 139

Algoritmi i strukture podataka

Predavanja - 1

2 of 139

Način polaganja

  • Kolokvijum
  • Seminarski rad
  • Završni ispit

3 of 139

Literatura

  • Živković: Strukture podataka i algoritmi
  • Slajdovi sa predavanja

4 of 139

Programiranje

5 of 139

Programiranje

  • Dva osnovna pristupa
    • Iterativni
    • vodopad

6 of 139

Dva pristupa

7 of 139

Podaci

  • Problem klasifikacije podataka
  • Tip podataka
    • Skup vrednosti sa dozvoljenim operacijama
    • Odgovor na pitanje: Šta je neki podatak po osobinama, koje zajedničke osobine imaju svi podaci toga tipa?
    • Npr. Imena ili pol ljudi imaju zajedničke osobine

8 of 139

Tipovi podataka

  • Primitivni
    • Nema smisla da se razlažu dalje
      • Broj, slovo, logička vrednost
  • Složeni
    • Nastaju kombinovanjem primitivnih tipova podataka
      • Zapis, niz

9 of 139

Primitivni tipovi podataka

  • Najčešće
    • Celobrojni
    • Realni
    • Logički
    • Znakovni

10 of 139

Celobrojni tip podataka

  • INTEGER
  • Upotreba: negativni i pozitivni celi brojevi, prebrojavanje, indeksi, brojači, diskretne pojave
  • Vrednosti: -32768 do 32767
  • Operacije: sabiranje, oduzimanje, množenje i celobrojno deljenje, poređenje

​

11 of 139

Realni tip podataka

  • REAL
  • Upotreba: numerička izračunavanja u najširem smislu
  • Vrednosti: 2.9E-39 do 1.7E38
  • Operacije: sabiranje, oduzimanje, množenje, deljenje, poređenje i skup dodatnih operacija koje uzimaju realan argument

​

12 of 139

Logički tip podataka

  • BOOLEAN
  • Upotreba: odlučivanje, grananje
  • Vrednosti: true i false
  • Operacije: konjukcija, disjunkcija, negacija

​

13 of 139

Znakovni tip podataka

  • CHAR
  • Upotreba: operacije nad tekstom
  • Vrednosti: a-z, A-Z, 0-9 i specijalni znakovi
  • Operacije: nalaženje dužine niza, poređenje, odsecanje, spajanje

14 of 139

Vežba

  • Odrediti tip podataka za sledeće veličine i pojave koje treba da se koriste u nekom programu
    • Ime
    • Prezime
    • Ime i prezime
    • Dan rođenja
    • Datum rođenja
    • pol

15 of 139

Vežba

  • Masa broda
  • Ime broda
  • Odgovor u anketi tačno/netačno
  • Kalibar puščane cevi meren u fabrici
  • Cena hleba
  • Broj indeksa
  • Godina upisa fakulteta
  • Ocena na ispitu

16 of 139

Apstraktni tip podataka (ATP)

  • Generalizacija primitivnih tipova podataka
  • Naučni princip generalizacije
  • Naučni princip apstrakcije
    • Proceduralna apstrakcija
    • Asptrakcija podataka

17 of 139

Proceduralna apstrakcija

  • Ideja: razdvajanje onoga šta neki modul radi od načina kako se to postiže
  • Modul: samostalan program koji je deo većeg programa

18 of 139

Apstrakcija podataka

  • Razdvajanje logičke slike podataka od njihove fizičke realizacije

19 of 139

Apstrakcija podataka

20 of 139

Apstrakcija podataka

  • Realizuje se kroz logički model podataka (LMP)
  • LMP ima četiri važne osobine

21 of 139

LMP

22 of 139

LMP

Šta su podaci i kako se obrađuju?

23 of 139

LMP

Kako su podaci implementirani?

24 of 139

LMP

Apstraktni tipovi podataka

25 of 139

LMP

Strukture podataka

26 of 139

ATP i strukture podataka

  • ATP su nezavisni od programskog jezika i implementacije
  • Strukture podataka nemaju to svojstvo

27 of 139

Algoritmi

  • Računarski problem: zadatak koji treba izvršiti na računaru
  • Zadatak mora da se opiše preciznom specifikacijom odnosa ulaza i izlaza

28 of 139

Primeri računarskih problema

  • Problem sortiranja niza celih brojeva
  • Problem nalaženja najduže reči u knjizi

​

29 of 139

Formalna specifikacija problema

  • Ulazni parametri
  • Izlazni parametri
  • Instanca problema
  • Instanca rešenja

​

30 of 139

Primer

31 of 139

Primer

  • Nalaženje najboljeg učenika u školi ako postoji niz srednjih vrednosti ocena svih đaka

32 of 139

Primer

  • Nalaženje kvadrata kompleksnog broja ako računar nema podržane operacije nad kompleksnim brojevima

33 of 139

Primer

  • Nalaženje broja kanti boje potrebne za krečenje kuće ako znamo dimenzije soba

34 of 139

Primer

  • Provera da li je broj paran

35 of 139

Primer

  • Provera da li je broj prost

36 of 139

Primer

  • Provera da li su dva broja međusobno prosta

37 of 139

Formalna specifikacija problema

  • Instanca problema
    • Primer valjanih ulaznih parametara
  • Instanca rešenja
    • Primer valjanih rešenja

​

38 of 139

39 of 139

Algoritam

  • Specifikacija niza koraka koji se izvršavaju na računaru
  • Procedura koja pretvara ulazne podatke u izlazne podatke

40 of 139

Algoritam

41 of 139

Osobine algoritma

42 of 139

Osobine algoritma

43 of 139

Osobine algoritma

44 of 139

Operacije nad algoritmima

  • Dizajn
  • Analiza

45 of 139

Dobar algoritam

  • Ima sledeće osobine
    • Diskretnost
    • Determinisanost
    • Efektivnost
    • Rezultativnost
    • Masovnost
    • optimalnost

​

46 of 139

Dobar algoritam

47 of 139

Dobar algoritam

48 of 139

Dobar algoritam

49 of 139

Dobar algoritam

50 of 139

Dobar algoritam

51 of 139

Dobar algoritam

52 of 139

Vežba

  • Napišimo jedan dobar algoritam
    • Problem: spremanje omiljenog jela
    • Problem: nalaženje srednje vrednosti ocene za 10 đaka
      • Varijanta problema: za 100 đaka, za 1000 đaka, za neograničen broj đaka

53 of 139

Računarski model

  • Koji to koraci (instrukcije) čine jedan algoritam?
  • Pojednostavljen opis stvarnosti računara
  • Idealizovan računar sa jednim procesorom

​

54 of 139

Operacije u računarskom modelu

  • Sabiranje
  • Množenje
  • Deljenje, ostatak deljenja, celobrojno deljenje
  • Logičke operacije (i, ili, ne)
  • Ulazne i izlazne operacije (čitaj, piši)

​

​

​

​

55 of 139

Operacije u računarskom modelu

  • Operacije za premeštanje (kopiranje iz memorije u procesor)
  • Operacije grananja
  • Operacije poziva potprograma

​

56 of 139

Izmišljeni računar RAM

  • Random access machine
    • Jednoprocesorska mašina
    • Sekvencijalna obrada

​

57 of 139

Brojevi u RAM

  • Celi brojevi
  • Memorijska reč širine w
  • Celi brojevi: 2w-1

58 of 139

Realni brojevi

  • IEEE standard, tzv pokretni zarez

​

59 of 139

Realni brojevi

60 of 139

Jedinični model složenosti

  • Svaka se instrukcija izvršava u jednoj jedinici vremena
  • Svaki broj zauzima jednu memorijsku reč

61 of 139

Načini zapisa algoritma

  • Narativno
  • Pseudokod
  • Dijagram toka

62 of 139

Pseudokod

  • Pseudokod pišemo u pseudojeziku
  • Pseudojezik: nije programski jezik, ali je sličan Javi, jeziku C i Pascalu
  • Sintaksna pravila nisu striktna

63 of 139

64 of 139

65 of 139

66 of 139

67 of 139

68 of 139

69 of 139

70 of 139

71 of 139

72 of 139

73 of 139

74 of 139

75 of 139

76 of 139

77 of 139

78 of 139

Primer

  • Zadate su dve promenljive. Zameniti im vrednosti.

79 of 139

80 of 139

Dijagram toka

81 of 139

Osnovne algoritamske strukture

  • Prethodni primer: sekvencijalna struktura
  • Koraci se nižu jedan za drugim

82 of 139

Primer

  • Naći proizvod dva broja ukoliko računarski sistem omogućava samo operaciju sabiranja

83 of 139

84 of 139

Selekcija

85 of 139

Prethodni primer

  • Struktura selekcije
  • Struktura iteracije

86 of 139

Selekcija

Uslov je izraz koji ima vrednost logičkog tipa

87 of 139

Selekcija

  • Primer uslova

a>3

x<2

ime=“Petar”

88 of 139

Selekcija

  • Struktura selekcije omogućava grananje programa
  • U pseudokodu:

if uslov then

proces1

else proces 2

89 of 139

Iteracija

90 of 139

Iterativna struktura

  • Jedna sekvencijalna struktura ponavlja se sve dok se ne ispuni neki selekcioni uslov
  • Iteracija je kombinacija sekvencije i selekcije i omogućava ponavljanje neke operacije – ciklični rad programa

91 of 139

Vrste iterativnih struktura

  • Strukture sa definisanim brojem iteracija
  • Strukture bez definisanog broja iteracija
    • Sa selekcijom na početku
    • Sa selekcijom na kraju

92 of 139

Iterativna struktura sa definisanim brojem iteracija

93 of 139

Komentar primera

  • Prethodni primer ispisuje brojeve počevši od 1 pa do n, sa korakom uvećanja 1.
  • To je primer iterativne strukture sa unapred definisanim brojem koraka
  • Struktura se u programiranju naziva FOR petlja

94 of 139

Selekcija

  • Struktura iteracije omogućava ciklično izvršenje programa
  • U pseudokodu:

for i=1 to n do

write i;

95 of 139

Primer

  • Neka korisnik unosi broj koji program odmah zatim ispisuje. Zatim program traži unos novog broja koji ispisuje. Proces se ponavlja dok korisnik ne unese broj 0. Tada prestaje rad programa (ništa se ne ispisuje)

96 of 139

Iterativna struktura sa selekcijom na početku (bez definisanog broja iteracija)

97 of 139

Iterativna struktura sa selekcijom na početku (bez definisanog broja iteracija)

SELEKCIJA

REZULTAT

98 of 139

Iterativna struktura sa selekcijom na početku (bez definisanog broja iteracija)

  • Prvo proveravamo ispunjenost uslova, a tek onda realizujemo proces (dobijemo rezultat)

99 of 139

Iteracija sa sa selekcijom na početku (bez definisanog broja iteracija)

  • Struktura iteracije omogućava ciklično izvršenje programa
  • U pseudokodu:

while n!=0 do

read n;

write n;

100 of 139

Komentar primera

  • Prethodni primer ponavlja neki proces sve do ispunjenja uslova
  • To je primer iterativne strukture bez unapred definisanog broja koraka
  • Struktura se u programiranju naziva WHILE petlja

101 of 139

Iteracija sa sa selekcijom na kraju(bez definisanog broja iteracija)

  • Primer
    • Neka korisnik unosi broj koji program odmah zatim ispisuje. Zatim program traži unos novog broja koji ispisuje. Proces se ponavlja dok korisnik ne unese broj 0. Tada prestaje rad programa (ali se poslednja uneta nula ispisuje)

​

102 of 139

Iteracija sa sa selekcijom na kraju(bez definisanog broja iteracija)

103 of 139

Iteracija sa sa selekcijom na kraju(bez definisanog broja iteracija)

SELEKCIJA

REZULTAT

104 of 139

Iterativna struktura sa selekcijom na kraju (bez definisanog broja iteracija)

  • Prvo realizujemo proces, a tek onda proveravamo uslov

105 of 139

Iteracija sa sa selekcijom na kraju(bez definisanog broja iteracija)

  • Struktura iteracije omogućava ciklično izvršenje programa
  • U pseudokodu:

repeat

read n;

write n;

until n=0

106 of 139

Komentar primera

  • Prethodni primer ponavlja neki proces sve do ispunjenja uslova
  • To je primer iterativne strukture bez unapred definisanog broja koraka
  • Struktura se u programiranju naziva REPEAT – UNTIL petlja

107 of 139

WHILE i REPEAT - UNTIL

  • Zašto postoje ove dve ciklične strukture?
  • Pogledajmo šta se dešava u našim primerima

108 of 139

Poređenje

while n!=0 do

read n;

write n;

repeat

read n;

write n;

until n=0

Unosimo brojeve 1,2,3,0

Ispisuje se

1

2

3

Unosimo brojeve 1,2,3,0

Ispisuje se

1

2

3

0

109 of 139

Poređenje

while n!=0 do

read n;

write n;

repeat

read n;

write n;

until n=0

Unosimo broj 0

Ispisuje se

​

​

​

Unosimo broj 0

Ispisuje se

​

0

110 of 139

Zaključak

  • Kod petlje REPEAT – UNTIL proces će se realizovati najmanje jednom, dok kod WHILE petlje proces može da se realizuje niti jednom ili više puta

111 of 139

Ponavljanje

  • Osnovne algoritamske strukture su
  • Sekvenca
  • Selekcija
  • Iterativna struktura
    • Sa poznatim brojem iteracija
    • Bez poznatog broja iteracija
      • Sa uslovom na početku
      • Sa uslovom na kraju

112 of 139

Sekvenca

113 of 139

Selekcija

114 of 139

Iterativna struktura bez poznatog broja iteracija

Iteracija sa selekcijom na početku

Iteracija sa selekcijom na kraju

115 of 139

Primer projektovanja algoritma

  • Problem: održavanje stalne temperature u kući tokom zimskog perioda
  • Pretpostavke
    • Napolju je hladnije od željene temperature
    • Imamo grejač koji može da se uključi i isključi programski
    • Imamo termometar sa programskim očitavanjem

116 of 139

Analiza

  • Ulazno stanje i ulazni podaci
    • Temperatura u kući i izmerena vrednost temperature
  • Izlazno (krajnje) stanje i izlazni podaci
    • Željena temperatura u kući i izmerene vrednost temperature

117 of 139

Narativni opis algoritma

  • Očitaćemo izmerenu vrednost temperature i uporediti je sa željenom temperaturom.
  • Ako je izmerena vrednost temperature manja od željene, uključićemo grejač, inače grejač isključujemo.
  • Zatim ponavljamo ceo postupak

118 of 139

Dijagram toka

119 of 139

Pseudokod

read tZelj;

repeat

tSobe=senzor.ocitaj;

D=tZelj-tSobe;

if (D>0) then grejac.ukljuci;

else grejac.iskljuci;

until false

120 of 139

Analiza

  • Nije moguće isključenje grejača
  • Nema novog podešavanja temperature
  • Nije definsan interval očitavanja temperature

121 of 139

Profinjenje rezultata

  • Uvodimo nove činjenice iz analize
  • Prvo, da dozvolimo isključenje grejača
    • Pre nove iteracije očitavanja temperature proveri stanje prekidača
    • Ako je isključen – kraj programa
    • Na kraju isključi grejač

122 of 139

read tZelj;

repeat

tSobe=senzor.ocitaj;

D=tZelj-tSobe;

if (D>0) then grejac.ukljuci;

else grejac.iskljuci;

until prekidac.iskljucen=true

grejac.iskljuci

123 of 139

Zadatak

  • Modifikujte dijagram toka prema pseudokodu

124 of 139

Profinjenje rezultata

  • Uvodimo nove činjenice iz analize
  • Drugo, da dozvolimo promenu podešene temperature
    • Pre poređenja temperature proveri stanje termostata
    • Koristi očitanu temperaturu

125 of 139

​

repeat

tSobe=senzor.ocitaj;

tZelj=termostat.ocitaj;

D=tZelj-tSobe;

if (D>0) then grejac.ukljuci;

else grejac.iskljuci;

until prekidac.iskljucen=true

grejac.iskljuci

126 of 139

Zadatak

  • Modifikujte dijagram toka prema pseudokodu

127 of 139

Profinjenje rezultata

  • Uvodimo nove činjenice iz analize
  • Treće, da podesimo vreme očitavanja

128 of 139

read tCekanja;

repeat

tSobe=senzor.ocitaj;

tZelj=termostat.ocitaj;

D=tZelj-tSobe;

if (D>0) then grejac.ukljuci;

else grejac.iskljuci;

cekaj(tCekanja);

until prekidac.iskljucen=true

grejac.iskljuci

129 of 139

Modul

  • Važno cekaj() je neka komanda koja je očigkedno programska, ali ne znato tačno kako funkcioniše
  • Sa druge strane, očitavanja senzora nisu programske komande, nego samo malo drugačiji način učitavanja ulaznih podataka (kao read)
  • Modul je samostalan program koji je deo većeg programa

130 of 139

Realizacija

  • Na primer, cekaj() može da se realizuje kao FOR petlja koja ništa ne radi, ali se ponavlja kontrolisan broj puta

//cekaj(n)

read n

for i=1 to n do

;

131 of 139

132 of 139

Modul: grafički simbol

133 of 139

Primer

  • Naći najveći element niza

134 of 139

135 of 139

136 of 139

137 of 139

Primer-zadatak

  • Sastaviti dijagram toka za problem ispisa proizvoda dva broja
  • Ako je bar jedan uneti broj nula ne računati proizvod već ispisati 0

138 of 139

139 of 139

Pseudokod

read (x,y);

if (x=0) then m=0;

else if y=0 then m=0;

else m=x*y;

write (m);