02_Nizovi

1. Algoritmi i Strukture Podataka

Nizovi

2. Zadatak 0

• Izvesti adresnu funkciju prilikom pristupa matrici
A[1:M,1:N], ukoliko se smeštanje matrice vrši:
– po vrstama (primer jezik C)
– po kolonama (primer jezik Fortran)
po vrstama
adresa
po kolonama
1
5
9
13
1
5
9
13
2
6
10
14
2
6
10
14
3
7
11
15
3
7
11
15
4
8
12
16
4
8
12
16
a
a+1 a+2 a+3 a+4 a+5
1
5
Elektrotehnički fakultet,
Beograd
9
13
2
6
...
Algoritmi i Strukture Podataka
a
a+1 a+2 a+3 a+4 a+5
1
2
3
4
5
6
...
2

3. Zadatak 0 - rešenje – po vrstama

Posmatra se neki element na poziciji A[i,j]:
– do i-te vrste ima (i-1)*N elemenata
– u i-toj vrsti, do j-te kolone ima j-1 element
Adresna funkcija:
– Ai,j = A1,1 + ((i - 1) * N + j - 1) * s
j
Primer za A[3,2], M=4, N=4, s=1:
– Ai,j = A1,1 + ((3 - 1) * 4 + 2 - 1) * 1 = A1,1 + 9
Analogno za kolone:
– Ai,j = A1,1 + ((j - 1) * M + i - 1) * s
i
1
2
3
4
1
1
5
9
13
2
2
6
10
14
3
3
7
11
15
4
4
8
12
16
Kako bi bilo da indeksi idu od 0?
– Opšti oblik za proizvoljnu donju i gornju granicu
Elektrotehnički fakultet,
Beograd
Algoritmi i Strukture Podataka
3

4. Zadatak 1

Matrica X[1:100,1:250] se linearizuje u memoriji po
kolonama počevši od neke adrese, a za smeštanje jednog
elementa se koriste dve memorijske reči. Ukoliko se
element matrice X[25,11] smešta na adresi 2250, odrediti
početnu adresu i napisati adresnu funkciju.
Elektrotehnički fakultet,
Beograd
Algoritmi i Strukture Podataka
4

5. Zadatak 1 - rešenje

Matrica se smešta po kolonama
Dakle, adresna funkcija je Xi,j = X1,1 + ((j - 1) * M + i - 1) * s
M = 100, s = 2 (element se smešta u dve memorijske reči)
2250 = X25,11 = X1,1 + ((11 - 1) * 100 + 25 - 1) * 2
2250 = X1,1 + (10*100 + 24) * 2
X1,1 = 2250 – 1024 * 2
X1,1 = 2250 – 2048
X1,1 = 202
• Početna adresa je 202, adresna funkcija je
Xi,j = 202 + ((j - 1) * 100 + i - 1) * 2
Elektrotehnički fakultet,
Beograd
Algoritmi i Strukture Podataka
5

6. Zadatak 2

Objasniti postupak smeštanja i izvesti adresnu funkciju pri
pristupu proizvoljnom elementu gornje trougaone matrice
smeštene po kolonama. Smatrati da se jedan element
matrice smešta u tačno jednu memorijsku reč.
j
x x x x x
x x x x
i
x x x
x x
x
j ( j 1)
k
2
k 0
Broj elemenata
u koloni j
pre traženog elementa:
i 1
Adresna funkcija:
Aij = A11 + (j(j-1)/2 + i – 1)*1
Elektrotehnički fakultet,
Beograd
j 1
Broj elemenata
pre prvog elementa
kolone j :
GET(A, i, j)
if (i > j) then
return default_element
else
return A [ j(j-1)/2 + i – 1 ]
Algoritmi i Strukture Podataka
6

7. Zadatak 3

Usvojiti efikasnu implementaciju kvadratne matrice realnih
brojeva za koju se zna da je simetrična u odnosu na glavnu
dijagonalu, a zatim napisati kompletne potprograme (na
jeziku C ili C++) za efikasno čitanje proizvoljnog elementa,
upisivanje proizvoljne vrednosti elementa i određivanje broja
nenultih elemenata matrice. Obavezno komentarisati
program.
1 1 3 8 9
1 4 6 7 5
3 6 5 2 3
8 7 2 1 2
9 5 3 2 8
Elektrotehnički fakultet,
Beograd
Matrica simetrična u odnosu na glavnu
dijagonalu:
– Dovoljno je pamtiti jednu trougaonu matricu
Program za C/C++:
– Matrica se smešta po vrstama
– Indeksi počinju od 0
– Potreban samo pomeraj, ne apsolutna adresa
7

8. Zadatak 3 - rešenje

Posmatra se neki element na poziciji A[i,j]
Primetiti da svaka sledeća vrsta ima
po jedan element manje
Do i-te vrste ima:
i
j
0
1
2
3
4
0
1 1 3 8 9
1
4 6 7 5
2
5 2 3
3
1 2
4
U i-toj vrsti treba primetiti da je element
na glavnoj dijagonali prvi nenulti element u vrsti
8
– i*n - (0 + 1 + … + i – 1) = i*n - i*(i-1)/2
– Razlika j-i definiše pomeraj od elementa na glavnoj dijagonali
Adresna funkcija:
– Ai,j = A0,0 + (i*n - i*(i-1)/2 + j-i) = A0,0 + (i*n + j - i*(i+1)/2) [za i ≤ j]
– za i > j, dohvata se element na poziciji Aj,i [simetričan]
Primer za A[2,3], N=5:
– Ai,j = A0,0 + (2*5 + 3 – 2*3/2) = A0,0 + 10
Elektrotehnički fakultet,
Beograd
Algoritmi i Strukture Podataka
8

9. Zadatak 3 - rešenje – kod

double &Matrica::dohvati
(unsigned int v, unsigned int k) {
unsigned int vrsta, kolona;
if (v > k) vrsta = k, kolona = v;
else vrsta = v, kolona = k;
unsigned int pomeraj =
vrsta*m_dim + kolona - vrsta*(vrsta+1)/2;
return m_matrica[pomeraj];
}
unsigned int Matrica::brojNenultih() const {
unsigned int broj = 0;
for (unsigned int i = 0; i < m_dim; i++)
for (unsigned int j = i; j < m_dim; j++)
if (dohvati(i, j) != 0)
broj += i == j ? 1 : 2;
return broj;
}
Elektrotehnički fakultet,
Beograd
Algoritmi i Strukture Podataka
9

10. Zadatak 4

Tridijagonalna matrica je matrica reda n×n, gde je A[i,j] = 0,
ako je |i-j|>1.
a) Koliki je maksimalan broj nenultih elemenata ?
b) Ako se matrica linearizuje po vrstama izvesti adresnu funkciju.
a11
a21
a) Max. broj nenultih elemenata: nnz = 3*n – 2
a12
b) Matrica se smešta po vrstama:
a22
a23
a32
a33
a34
a43
a44
a45
a54
a55
a11
a12
a21
a22
a23
a32
a33
...
0
1
2
3
4
5
6
...
Aij = A11 + (3(i-1) + j - i + 1 - 1)*s, ako je |i-j| ≤ 1
Aij = A11 + (2*i + j - 3)*s, ako je |i-j| ≤ 1
Elektrotehnički fakultet,
Beograd
Algoritmi i Strukture Podataka
10

11. Zadatak 4 - rešenje

a11
a12
a21
a22
a23
a32
a33
...
0
1
2
3
4
5
6
...
Do rešenja se može doći rešavanjem sistema linearnih
jednačina:
pomeraj = A*vrsta + B*kolona + C
Postoje 3 nepoznate potrebno je zadati 3 jednačine
1) A + B + C = 0
2) 2A + 2B + C = 3
3) 3A + 3B + C = 6
Problem!
1) C = – A –B
2) A+B = 3
3) 2A + 2B = 6
Nema rešenja!
Očigledno ne može se odabrati bilo koja kombinacija,
već kombinacija linearno nezavisnih jednačina. Npr:
1) A + B + C = 0
2) 2A + 3B + C = 4
3) 3A + 2B + C = 5
Elektrotehnički fakultet,
Beograd
A=2, B=1, C=-3
Algoritmi i Strukture Podataka
11

12. Zadatak 5 – (SI) jun 2020.

Neka se blok-dijagonalna matrica
definiše kao kvadratna matrica A
dimenzija n x n čiji su nenulti
elementi smešteni samo u okviru
blokova dimenzije k x k koji se
nalaze na glavnoj dijagonali matrice,
kao na slici i važi uslov n mod k = 0.
Ukratko
objasniti
postupak
smeštanja i izvesti adresnu funkciju
pri pristupu proizvoljnom elementu
matrice A[1:n, 1:n] smeštene po
vrstama. Smatrati da se jedan
element matrice smešta u tačno
jednu memorijsku reč.
Elektrotehnički fakultet,
Beograd
Algoritmi i Strukture Podataka
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
12

13. Zadatak 5 - rešenje

• Svaki blok k x k predstavlja matricu za sebe
• Potrebno je odrediti koliko elemenata ima u blokovima pre
posmatranog (svaki blok ima k2 elemenata), a zatim se
pozicionirati u okviru posmatranog bloka
• Broj blokova pre posmatranog: ((i-1) div k) * k2
– div označava celobrojno deljenje, tj. donji ceo deo
• U okviru bloka: ((i-1) mod k) * k + (j-1) mod k
– pozicije i i j u „velikoj“ matrici treba preslikati na pozicije
i i j u „maloj“ matrici (bloku k x k)
0
0
1
2
4
5
6
4 X X X
1 5 X X X
• Dakle, adresna je:
2 6 X X X
za (i-1) div k = (j-1) div k,
Ai,j = A1,1+((i-1) div k) * k2 + ((i-1) mod k) * k + (j-1) mod k
Elektrotehnički fakultet,
Beograd
Algoritmi i Strukture Podataka
13

14. Zadatak 5 - rešenje

Ili jednostavno
U svakom redu pre posmatranog ima k elemenata
U posmatranom redu ima (j-1) mod k elemenata
Dakle, adresna funkcija je:
za (i-1) div k = (j-1) div k,
Ai,j = A1,1+ (i-1)*k + (j-1) mod k
Elektrotehnički fakultet,
Beograd
Algoritmi i Strukture Podataka
14

15. Zadatak 6

Prikazati vektorsku prezentaciju retke matrice sa slike:
a) sa jednim vektorom zapisa od po tri polja,
b) sa tri posebna vektora.
0
0
0
X
0
9
0
0 0
0 4
0 0
0 0
0 0
0 15
0 0 0 0
0 0 0 0
5 0 11 0
0 0 0 0
8 10 0 0
0 0 0 0
Ideja – pamte se samo nenulti element i njihove pozicije
– Linearizacija ponovo po vrstama ili kolonama
– Različiti načini pamćenja pozicija
Elektrotehnički fakultet,
Beograd
Algoritmi i Strukture Podataka
15

16. Zadatak 6 - rešenje a)

• Coordinate of Objects format (COO)
• Svaki zapis se sastoji od
– broja vrste (R)
– broja kolone (C)
– vrednosti (V)
0
0
0
X
0
9
0
0 0
0 4
0 0
0 0
0 0
0 15
Elektrotehnički fakultet,
Beograd
0 0 0 0
0 0 0 0
5 0 11 0
0 0 0 0
8 10 0 0
0 0 0 0
Algoritmi i Strukture Podataka
R
C
V
1
2
3
4
2
3
4
5
3
3
6
11
4
5
1
9
5
5
4
8
6
5
5
10
7
6
3
15
16

17. Zadatak 6 - rešenje b) – CSR varijanta

Compressed sparse row (CSR)
– Alternativno CSC ukoliko se linearizuje po kolonama
Potrebno je formirati 3 nezavisna vektora
– Vektor V sadrži vrednosti i ima onoliko elemenata koliko ima
nenultih elemenata matrice
– Vektor C sadrži broj kolone odgovarajućeg elementa vektora V
– Vektor R sadrži indeks prvog elementa vektora C koji odgovara
datom elementu vektora R i ima onoliko elemenata koliko i vrsta
matrice uvećano za jedan
0
0
0
X
0
9
0
0 0
0 4
0 0
0 0
0 0
0 15
0 0 0 0
0 0 0 0
5 0 11 0
0 0 0 0
8 10 0 0
0 0 0 0
R
1
2
3
4
5
6
1
1
2
4
4
7
8
1
2
3
4
5
6
7
C
V
3
4
6
1
4
5
3
4
5
11
9
8
10
15
17

18. Zadatak 6 - rešenje b) – kao u knjizi

Potrebno je formirati 3 nezavisna vektora
– Vektor V sadrži vrednosti i ima onoliko elemenata koliko ima
nenultih elemenata matrice
– Vektor C sadrži broj kolone odgovarajućeg elementa vektora V
– Vektor R sadrži indeks prvog elementa vektora C koji odgovara
datom elementu vektora R i ima onoliko elemenata koliko i vrsta
matrice
0
0
0
X
0
9
0
0 0
0 4
0 0
0 0
0 0
0 15
Elektrotehnički fakultet,
Beograd
0 0 0 0
0 0 0 0
5 0 11 0
0 0 0 0
8 10 0 0
0 0 0 0
Algoritmi i Strukture Podataka
R
1
2
3
4
5
6
0
1
2
0
4
7
1
2
3
4
5
6
7
C
V
3
4
6
1
4
5
3
4
5
11
9
8
10
15
18

19. Zadatak 7 – za samostalnu vežbu

Podatke dužine 3, 4 i 5 bita potrebno je smestiti u nizove
A, B i C, respektivno.
Podaci se smeštaju pakovanjem više podataka u jednu
memorijsku reč. Na datom računaru memorijske reči mogu
biti dužine 8, 16 i 32 bita. Za svaki od navedenih vektora
potrebno je odabrati jednu od ponuđenih dužina
memorijske reči tako da iskorišćenje prostora bude što je
moguće veće. Nacrtati sliku koja prikazuje raspored
podataka po memorijskim rečima za izabranu dužinu
memorijske reči.
Elektrotehnički fakultet,
Beograd
Algoritmi i Strukture Podataka
19

20. Zadatak 7 - rešenje

• Niz A:
A
– Smeštaju se podaci od 3 bita.
– U 8 bita mogu da stanu najviše dva podatka veličine 3 bita, pri
čemu dva bita ostaju neiskorišćena;
iskorišćenje prostora = 6/8 = 0,75
– U 16 bita može da stane najviše 5 podataka veličine 3 bita, pri
čemu jedan bit ostaje neiskorišćen;
iskorišćenje prostora = 15/16 = 0,9375
– U 32 bita može da stane najviše 10 podataka veličine 3 bita, pri
čemu dva bita ostaju neiskorišćena;
iskorišćenje prostora = 30/32 = 15/16 = 0,9375
– Dakle, i memorijska reč od 16 bita i memorijska reč od 32 bita daju
maksimalno moguće iskorišćenje prostora za zadate uslove.
– Možemo odabrati npr. 16 bita.
Elektrotehnički fakultet,
Beograd
Algoritmi i Strukture Podataka
20

21. Zadatak 7 - rešenje

• Niz B:
B
– Smeštaju se podaci od 4 bita.
– U 8 bita mogu da stanu najviše dva podatka veličine 4 bita, pri
čemu 0 bita ostaje neiskorišćeno;
iskorišćenje prostora = 8/8 = 1
– U 16 bita može da stane najviše 4 podataka veličine 4 bita, pri
čemu 0 bita ostaje neiskorišćeno;
iskorišćenje prostora = 16/16 = 1
– U 32 bita može da stane najviše 8 podataka veličine 3 bita, pri
čemu 0 bita ostaje neiskorišćeno;
iskorišćenje prostora = 32/32 = 1
– Dakle, i memorijska reč od 8 bita, i memorijska reč od 16 bita, i
memorijska reč od 32 bita daju maksimalno moguće iskorišćenje
prostora za zadate uslove.
– Možemo odabrati npr. 8 bita.
Elektrotehnički fakultet,
Beograd
Algoritmi i Strukture Podataka
21

22. Zadatak 7 - rešenje

• Niz C:
C
– Smeštaju se podaci od 5 bita.
– U 8 bita može da stane najviše jedan podatak veličine 5 bita, pri
čemu tri bita ostaju neiskorišćena;
iskorišćenje prostora = 5/8 = 0,625
– U 16 bita mogu da stanu najviše 3 podataka veličine 5 bita, pri
čemu jedan bit ostaje neiskorišćen;
iskorišćenje prostora = 15/16 = 0,9375
– U 32 bita može da stane najviše 6 podataka veličine 5 bita, pri
čemu dva bita ostaju neiskorišćena;
iskorišćenje prostora = 30/32 = 15/16 = 0,9375
– Dakle, i memorijska reč od 16 bita i memorijska reč od 32 bita daju
maksimalno moguće iskorišćenje prostora za zadate uslove.
– Možemo odabrati npr. 16 bita.
Elektrotehnički fakultet,
Beograd
Algoritmi i Strukture Podataka
22

23. Zadatak 8 – za samostalnu vežbu

Neki računar može da manipuliše podacima dužine jedan,
dva i četiri bajta. U nekom programu pisanom za dati
računar, zapis se sastoji od tri polja: karakter, kratak ceo
broj i realan broj. Karakter se pamti na dužini od jednog
bajta, kratak ceo broj na dužini od dva bajta i realan broj na
dužini od četiri bajta. Precizno prikazati način smeštanja u
memoriju niza dužine tri, čiji su elementi opisani zapisi,
tako da se obezbedi efikasan pristup poljima zapisa (svako
polje može da se dohvati ili upiše u jednom pristupu
memoriji).
Smatrati da se niz smešta od adrese 100.
sadržaj
adresa
100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126
Elektrotehnički fakultet,
Beograd
Algoritmi i Strukture Podataka
23

24. Zadatak 8 - rešenje

• Zapis je predstavljen strukturom, gde je u# oznaka veličine
elementa (# predstavlja broj bajtova)
struct {
u1 karakter,
u2 kratak_ceo_broj,
u4 realan_broj
}
• Ukupna veličina ove strukture je 7B.
• Efikasan pristup bi podrazumevao da se uvede padding
dopune do veličine 8B, i to tako da su svi pomeraji stepeni
dvojke.
Elektrotehnički fakultet,
Beograd
Algoritmi i Strukture Podataka
24

25. Zadatak 8 - rešenje

struct {
u1 padding,
u1 karakter,
u2 kratak_ceo_broj,
u4 realan_broj
}
• Tada bi se adrese elementa niza (sa pojedinačnim
elementima strukture) bile 100 (101, 102, 104), 108 (109,
110, 112) i 116 (117, 118, 120), odnosno adresna funkcija
bi bila a[i].j = 100 + i * 8 + 2^j,
gde j je redni broj polja (karakter = 0, kratak_ceo_broj = 1,
realan_broj = 2) (simbolički predstavljeno sa .j)
sadržaj
adresa
c
s
s
f
f
f
f
c
s
s
f
f
f
f
c
s
s
f
f
f
f
c
…
100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126
Elektrotehnički fakultet,
Beograd
Algoritmi i Strukture Podataka
25

26. Zadatak za samostalnu vežbu

Izvesti adresnu funkciju za pristup proizvoljnom element kvadratne
matrice prikazane na slici, ako linearizacija radi po vrstama.
– Obratiti pažnju na uslov sporedne dijagonale
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
Elektrotehnički fakultet,
Beograd
Algoritmi i Strukture Podataka
26

27. Zadatak za samostalnu vežbu

Data je kvadratna matrica N×N, gde je N parno. Elementi
matrice se smeštaju u tačno jednu memorijsku reč. Ukratko
objasniti postupak smeštanja i izvesti adresnu funkciju pri
pristupu proizvoljnom elementu ove matrice, smeštene po
vrstama. Svaka vrsta matrice sadrži tačno dva elementa
nepodrazumevane vrednosti, smeštena u uzastopne
memorijske lokacije. U prvih N/2 vrsta, elementi
nepodrazumevane vrednosti u vrsti i smaknuti su za dva
mesta udesno u odnosu na elemente nepodrazumevane
vrednosti u vrsti i–1. Elementi prve vrste smešteni su
počevši od prve kolone. Po istom šablonu smešteni su
elementi u preostalih N/2 vrsta. Na slici je ilustrovan opisan
raspored elemenata za N=6.
U pseudokodu napisati funkciju GET(M, i, j) koja dohvata
vrednost matrice M sa lokacije (i, j).
Elektrotehnički fakultet,
Beograd
Algoritmi i Strukture Podataka
27

28. Zadatak za samostalnu vežbu

Adresna funkcija
– Ai,j=A1,1+(i–1)∙2+(j–1) mod 2
– Obratiti pažnju na upotrebu mod operatora
Funkcija za dohvatanje elementa
– Obratiti pažnju na uslov za nenulti element
GET(M, i, j)
if (i-1) mod N/2 = (j-1) div 2 then nenulti_element
A
B
0
0
0
0
0
0
C
D
0
0
0
0
0
0
E
F
G H
0
0
0
0
0
0
I
J
0
0
0
0
0
0
K
L
Algoritmi i Strukture Podataka
28