Računarski praktikum
O predmetu
Računarski praktikum
• dr Milan Vidaković
[email protected]
TMD 139/8
• Dejan Mijić
[email protected]
• Milorad Filipović
[email protected]
• http://www.informatika.ftn.uns.ac.rs/RP
2
Ocenjivanje
• Prisustvo na vežbama
– obavezno
– raspon poena: 3-5
– toleriše se do 20% izostanaka (80% prisustva – 3 poena, 100%
prisustva – 5 poena)
• Kolokvijumi
– računarska pismenost – 10-20 poena
– složeni zadatak – 15-25 poena
• Završni ispit (teorija)
– obavezan
– raspon poena: 15-30
• Zadatak iz algoritama (u sklopu teorije)
– 10-20 poena
3
Plan rada
•
•
•
•
Uvod – organizacija računara
Programski jezik Java
Algoritmi
Hardver i računarske mreže
4
Računarski praktikum
Uvod
Literatura
• dr Milan Vidaković
• email: [email protected]
• http://www.informatika.ftn.uns.ac.rs/RP
2/47
Osnovi računarstva
1. Istorija računara
2. Generacije računara
3. Osnovni pojmovi
Oblast 1
Istorija računara
istorija
• 1621. god. Vilijam Otred
(William Oughtred) –
engleski matematičar koji je
izmislio kružni klizni lenjir. To
se smatra prvim analognim
računarskim uređajem.
4/47
istorija
Šikardova mašina
• Vilhelm Šikard (Wilhelm
Schickard) je 1623.
osmislio mehanički
kalkulator.
• Mašina je mogla da
sabira, oduzima, množi
i deli.
• Ostalo je sve samo na
planovima.
5/47
• 1642. god. Blez Paskal (Blaise
Pascal) – napravio je “prvi”
automatski kalkulator.
Njegova mašina, nazvana
Paskalina (Pascaline) se
zasnivala na zupčanicima.
• Napravio je 50 primeraka za
prodaju, ali su računovođe
odbijale da ih koriste jer su se
bojali da će izgubiti posao.
istorija
6/47
istorija
• 1673. god. Gotfrid Lajbnic (Gottfried Leibniz) –
dizajnirao je novi tip mehaničkog kalkulatora
baziranog na nazubljenim cilindrima, koji se sada
zove Lajbnicov točak. Uređaj je mogao da sabira,
oduzima, množi i deli.
7/47
istorija
• 1804. god. Žozef Žakar
(Joseph Jacquard) –
izmislio je kartice sa rupama
koje su se koristile u uređaju
za tkanje. Kartice su se
koristile da propuste
određene niti, a da blokiraju
ostale.
• Iako njegov razboj nije
direktno povezan sa
računarima, ideju bušenih
kartica je kasnije preuzeo
Čarls Bebidž kao prvi
mehanički metod unošenja
informacija u računar.
8/47
istorija
Čarls Bebidž (Charles Babbage)
• 1822. god. Čarls Bebidž (Charles
Babbage) – napravio je prvu
mašinu za računanje konačnih
razlika. Izgradja uređaja je bila
finansirana od strane britanske
vlade, a namena je bila da rešava
polinomne jednačine.
• Bila je toliko osetljiva da se češće
kvarila nego što je radila, pa je
premijer izjavio da je jedina
namena ove mašine da izračuna
ogromnu količinu novca koja je
potrošena na njenu gradnju.
9/47
istorija
Čarls Bebidž (Charles Babbage)
• Bebidž je kasnije razvio analitičku
mašinu koja je bila dizajnirana kao
pravi mehanički računar. Iako nikada
nije bila napravljena, mašina se
sadržavala pet bitnih elemenata za
buduće računare:
– ulazni uređaj
– medijum za smeštanje brojeva za
obradu (memorija)
– jedinicu za obradu (aritmetičkologička jedinica)
– kontrolnu jedinicu da upravlja
zadacima koji će se izvršavati
(upravljačka jedinica)
– izlazni uređaj.
10/47
istorija
• 1833. god. Augusta Ada
(grofica od Lavlejsa) - amater
matemetičar i bliski prijatelj
Čarlsa Bebidža. Ada je prva
dala nacrt programa koji bi se
izvršavao u analitičkoj mašini.
• Ovo je bio prvi put da je
koncept računarskog
programa bio predložen, pa
se smatra da je Ada bila prvi
kompjuterski programer.
11/47
istorija
• 1886. god. Herman Holerit (Herman
Hollerith) – razvio je mašinu za
računanje koje je koristila bušene
kartice za elektronsko brojanje. Ovaj
uređaj je napravljen da bi se obavio
popis iz 1890. godine (u Americi).
Ručno brojanje bi trajalo čitavu
deceniju (rezultati prethodnog
popisa su se obrađivali ručno i
proces je trajao 7 godina).
• 1896. godine Holerit je osnovao
Tabulating Machine Company.
1924. godine, nakon nekoliko
spajanja i preuzimanja, kompanija je
postala International Business
Machines (IBM).
12/47
istorija
• 1936. god. Alan Tjuring (Alan
Turing) – napisao je rad o
hipotetičkom digitalnom
računaru, koji je kasnije
nazvan “Tjuringova mašina”.
• Postavio temelje modernog
računarstva.
• Tokom drugog svetskog rata,
Tjuring je razvio tzv. ”bombe”
(mehanički uređaji), a zatim
“kolose” (električni uređaji) koji
su razbijali nemačku šifru
(Enigma mašina).
13/47
Enigma
istorija
• Nemački uređaj za kriptovanje i dekriptovanje.
• Tjuringov kolos je uspešno dekriptovao poruke
šifrovane Enigmom.
14/47
istorija
Prvi digitalni računar?
• 1939-1942. god. napravljen je računar
ABC (Atanasoff-Berry Computer) koji su
dizajnirali dr Džon Astanasov (Dr. John
Astanasoff) i Kliford Beri (Clifford Berry) na
državnom univerzitetu u Ajovi (Iowa State
University).
• 1941. god. napravljen i predstavljen
računar Z3, koji je dizajnirao i napravio
nemački inženjer Konrad Zuse.
15/47
istorija
ABC
16/47
istorija
Z3
• 600 releja u numeričkoj
jedinici
•1600 releja u memorijskoj
jedinici
• frekvencija rada 5, 3 Hz
• ulaz – decimalna tastatura
• izlaz – 4 cifre, sijalice
• težina – 1 tona
• potrošnja struje – 4 kW
17/47
Oblast 2
Generacije računara
• 6 generacija računara
• Razlika je pre svega u tehnoloskim
osnovama
• Granica između 4., 5. i 6. generacije nije
jasna – ima preklapanja
18/47
Prva generacija
• Elektronske cevi, releji, otpornici
• Velika potrošnja struje
• Ogromne dimenzije
19/47
Prva generacija
• 1944. god. napravljen je Mark I – prvi računar opšte
namene. Korišćen je na Harvardu 15 godina.
– 150000 raznih komponenti
– 5 tona
20/47
Prva generacija
• 1946. god. napravljen je Electronic Numerical Integrator
and Computer (ENIAC). Sastojao se iz 18000
elektronskih cevi i 70000 otpornika. Trošio je 160 kW.
21/47
Prva generacija
• 1951. god. napravljen je UNIVAC (Universal Automatic
Computer).
• Karakteristike:
–
–
–
–
programi smešteni u memoriju (1000 memorijskih ćelija),
uređaj spoljne memorije na magnetnoj traci,
ulazno/izlazni uređaji (tastatura, bušene kartice, štampač)
54000 elektronskih cevi
22/47
Druga generacija
• Pojava tranzistora:
– smanjenje dimenzija
– smanjenje potrošnje el. energije
– povećanje brzine
• Tipičan predstavnik – IBM 1401
– 4 KB memorije
– ulaz - prekidači
23/47
Treća generacija
• Pojava integrisanih kola:
– smanjenje dimenzija
– smanjenje potrošnje
– ubrzanje rada
• Tipičan predstavnik –
IBM System/360
– tastatura, diskovi
– 8-bitna memorija,
magnetna jezgra, do 6 MB
24/47
Četvrta generacija
• Pojava VLSI (Very Large Scale
Integration) kola:
– milioni komponenti u integrisanim
kolima
– mikroprocesor izdvojen u jednom
integrisanom kolu (inženjer Ted
Hoff) - Intel 4004
– smanjenje dimenzija, potrošnje
– ubrzanje
• Tipičan predstavnik – IBM PC
računar:
–
–
–
–
8086 mikroprocesor
64 KB memorije (max 640 KB)
360 KB flopi disk
10 MB hard disk
25/47
Četvrta generacija
• 80286 procesor
–
–
–
–
16 bita
16 MB RAM
6 MHz – 12,5 MHz
134000 tranzistora
• 80386 procesor
–
–
–
–
32 bita
16 MHz – 40 MHz
4 GB RAM
275000 tranzistora
• 80486 procesor
–
–
–
–
32 bita
25 MHz – 100 MHz
4 GB RAM
1,2 miliona tranzistora
•
PENTIUM procesor (ime
ne prati seriju 80xxx zbog
prava AMD-a na mikrokod):
– P1
• 3,1 miliona tranzistora
• 60 MHz – 166 MHz
– P2
• 7,5 miliona tranzistora
• 233 – 333 MHz
– P3
• 9,5 miliona tranzistora
• 650 MHz – 1,4 GHz
– P4
• 55 – 200 miliona
tranzistora!
• 1,4 GHZ – 3,4 GHz
26/47
Peta generacija
•
•
•
•
Izraziti paralelizam.
Primena veštačke inteligencije.
Virtuelna realnost.
Intenzivan razvoj računarskih mreža.
27/47
Šesta generacija
• Optika.
• Biočipovi.
• Dramatičan razvoj računarskih mreža –
poboljšanje u domenu radnih stanica i
brzina prenosa informacija u
komunikacionim linijama.
28/47
3. Osnovni pojmovi
• Hardver (tehnička podrška)
– oprema koja predstavlja fizičku (materijalnu)
realizaciju bilo kog sistema koji obavlja
određene funkcije.
• Softver (programska podrška)
– sveukupnost instrukcija, programa i drugog
“operativnog oruđa” koji se generiše, aktivira i
koristi na razne načine da bi omogućio
hardveru da reši dati problem i obavi željene
poslove.
29/47
Organizacija hardvera
• Elementi:
– memorija,
– procesor,
•
•
•
•
upravljačka jedinica,
aritmetičko logička jedinica,
registri,
ultra brza memorija.
– ulazno-izlazni podsistem,
– periferijski uređaji.
30/47
Memorija
• Služi za prihvat, čuvanje
(pamćenje, memorisanje) i
predaju podataka i programa.
• Element koji pamti
elementarnu informaciju (1 bit)
je memorijski element.
• Memorijski elementi se
udružuju u memorijsku
lokaciju (memorijsku ćeliju).
• Skup memorijskih ćelija je
memorijski modul (blok).
• Memorijski modul je najčešće
adresibilan.
– adresa je jedinstveni prirodan
broj dodeljen svakoj ćeliji.
31/47
Podela memorije
• Sa aspekta pristupa:
– sa sekvencijalnim (serijskim) pristupom (magnetna traka, bušena traka,
...)
– sa cikličkim (periodičnim) pristupom (hard disk, floppy disk, CD-ROM)
– sa proizvoljnim (slučajnim) pristupom (RAM – Random Access
Memory).
• Sa aspekta mogućnosti promene:
– promenljiva memorija (RAM memorija)
• Statička (pamti sadržaj dok ima struje),
• Dinamička (pamti sadržaj dok ima struje, ali mora da se osvežava).
– polupromenljiva memorija
•
•
•
•
PROM – Programmable Read Only Memory,
EPROM – Erasable PROM,
EEPROM – Electrically EPROM),
flash memorija.
– stalna memorija (ROM – Read Only Memory)
32/47
Podela memorije
• Po načinu smeštanja sadržaja:
– adresne (pristup mem. ćeliji preko adrese),
– bezadresne (asocijativne mem., stek mem.,
...).
ključ
sadržaj
asocijativna
memorija
stek
33/47
Memorija u računaru
• Operativna memorija
• Ultra brza memorija
• Jedinice spoljne memorije (masovna memorija):
–
–
–
–
–
–
–
floppy disk,
hard disk,
CD-ROM,
DVD,
USB pocket drive,
ZIP drive,
...
34/47
Procesor
• Funkcije:
– izvršava operacije obrade
podataka definisane
programom
– vrši upravljanje
računarskim procesima i
interakcijama između
pojedinih jedinica računara
• Elementi:
–
–
–
–
aritmetičko-logička jedinica,
upravljačka jedinica,
registri,
ultrabrza memorija.
35/47
Aritmetičko-logička jedinica
• Izvršava aritmetičke operacije (sabiranje,
oduzimanje,...), logičke operacije
(konjukcija, disjunkcija, negacija, ...),
pomeranje bitova, itd.
• Elementi:
– kombinacione mreže (sabirači),
– registri u kojima se čuvaju operandi,
međurezultati i rezultati operacija,
– pomoćni registri (statusni registar, i dr.)
36/47
Upravljačka jedinica
• Upravlja pojedinim koracima u obradi
podataka i to na osnovu informacija
sadržanih u instrukciji koju upravljačka
jedinica zahvata iz memorije.
• Sinhronizuje U/I jedinice, memoriju i
aritmetičko-logičku jedinicu.
• Dva pristupa:
– direktan (hardverski) i
– mikroprogramski.
37/47
Registri
• Vrste:
– radni (Akumulator, ...),
– upravljački (PC, MAR, MBR,...).
38/47
Ultrabrza memorija
• Veoma brza i veoma skupa.
• Operativna memorija je sporija, ali je cena
niža.
• Posledica: između operativne memorije i
procesora se nalazi ultrabrza memorija.
• Registri procesora se takođe mogu
smatrati za ultrabrzu memoriju.
• Ovaj koncept se primenjuje i kod sporijih
periferijskih jedinica (bafer).
39/47
Ulazno-izlazni podsistem
• Omogućuje razmenu
poruka između
računara i spoljnog
sveta.
• Načini realizacije:
– programirani U/I,
– sistem prekida,
– direktan memorijski
pristup (DMA – Direct
Memory Access).
40/47
Programirani U/I
• Procesor stalno:
– proverava status periferijske jedinice
– uzima/šalje podatke iz/ka periferijskoj jedinici
• Mana: troši puno procesorskog vremena.
• Retko se koristi.
41/47
Sistem prekida
• Sistem prekida (interrupt) omogućava da se:
– regularan program prekine ako se pojavi određeni
događaj,
– upravljanje prenese na program zadužen za obradu
tog događaja, i po završetku tog programa
– nastavi sa izvršenjem regularnog programa
• Koristi se kod prenosa manje količine podataka.
• Sporo kod prenosa velikog broja podataka.
42/47
Direktan memorijski pristup
• Periferijska jedinica “sama” upisuje
podatke u operativnu memoriju (ili čita iz
nje), bez intervencije procesora.
• Završetak posla se prijavi procesoru
upotrebom prekida.
• Korisno kod prenosa velikog broja
podataka (tu su i programirani U/I i sistem
prekida spori).
43/47
Periferijske jedinice
• Služe za ulaz i/ili izlaz
podataka.
• Podela:
– Ulazne jedinice
• tastatura,
• miš,
• džojstik, itd.
– Izlazne jedinice
• štampač,
• monitor,
• ploter, itd.
– ulazno/izlazne jedinice
•
•
•
•
floppy,
hard disk,
modem,
mrežna kartica, itd.
44/47
Softverske karakteristike računara
• Aplikacioni programi (korisnički programi):
– skup programa koje obično koriste i/ili razvijaju
korisnici za rešavanje svojih specifičnih problema.
• Sistemski programi (upravljački programi):
– programi za organizaciju i upravljanje procesima rada
računarskog sistema.
•
•
•
•
operativni sistemi (upravljanje radom rač. sistema)
uslužni programi (dijagnostika, upravljanje podacima, itd.)
simulatori računarskih sistema
programski sistemi za programiranje (asembleri, prevodioci,
interpreteri).
45/47
Aplikacioni programi
• Neke klase aplikacionih programa:
– DTP (DeskTop Publishing)
• Quark Express, MS Publisher, Adobe Page Maker, ...
– CAD/CAM
• AutoCAD, ArhiCAD, ...
– Word processors/Spreadsheet
• MS Office, Open Office, ...
– Internet
• WWW: Internet Explorer, Mozilla Firefox, ...
• Email: Outlook Express, The Bat, ...
• Chat, voice chat: MS Messanger, Skype, ...
46/47
Sistemski programi
• Operativni sistemi
– Windows, Linux, Solaris, ...
• Dijagnostika
– Motherboard Monitor, Network Monitor, ...
• Simulatori računarskih sistema
– VMWare, Spectrum Emulator, Amiga
Emulator, ...
• Programski sistemi za programiranje
– Visual Studio, Eclipse, ...
47/47
Računarski praktikum
Matematičke osnove rada
računara
Matematičke osnove rada računara
• Brojni sistemi
– pozicioni i nepozicioni brojni sistemi
– računarske operacije
• Predstavljanje celobrojnih brojeva u računaru
– predstavljanje negativnih brojeva
• Predstavljanje razlomljenih brojeva u računaru
• Kodiranje informacija u računaru
• Kodovi za detekciju i korekciju grešaka
2/46
Brojni sistemi
• Pozicioni i nepozicioni brojni sistemi
– Nepozicioni brojni sistem – Rimski Brojni Sistem:
•
•
•
•
•
•
•
•
I – jedan
V – pet
X – deset
L – pedeset
C – sto
D – pet stotina
M – hiljadu
M – milion (broj crtica iznad slova M označava koliko puta
množimo sa hiljadu).
3/46
Pozicioni brojni sistem
• Svaka cifra ima zadatu težinu.
• Opšti oblik:
anan-1...a1a0 ,a-1a-2...a-m
tj.
an∙bn+an-1∙bn-1 + ... + a1∙b1 + a0∙b0 + a-1∙b-1+a-2∙b-2+...+a-m∙b-m
•
•
•
•
a – cifra
b – osnova (baza)
n+1 – broj celobrojnih cifara
m – broj decimala
4/46
Pozicioni brojni sistem - primeri
• 198410 = 1∙103 + 9∙102 + 8∙101 + 4∙100 =
1∙1000 + 9∙100 + 8∙10 + 4∙1 =
1000 + 900 + 80 + 4 = 1984
• 100112 = 1∙24 + 0∙23 + 0∙22 + 1∙21 + 1∙20 =
1∙16 + 0∙8 + 0∙4 + 1∙2 + 1∙1 = 16 + 2 + 1 =
19
• 12,310= 1∙101 + 2∙100 + 3∙10-1 =
1∙10 + 2∙1 + 3∙0,1 =
10+2+0,3 =
12,3
5/46
Predstavljanje brojeva u različitim
brojnim sistemima
• Cifre brojnog sistema su: 0 do (baza – 1)
• Primer:
– binarni (b=2): {0, 1}
– oktalni (b=8): {0, 1, 2, 3, 4, 5, 6, 7}
– decimalni (b=10): {0, 1, 2, 3,4 ,5 ,6 ,7 , 8, 9}
– heksadecimalni (b=16): {0, 1, 2, 3, 4, 5, 6, 7,
8, 9, A, B, C, D, E, F}
6/46
Primer
7/46
Računske operacije – binarni brojni
sistem
• Sabiranje:
• Oduzimanje:
8/46
Računske operacije – binarni brojni
sistem
• Množenje:
• Deljenje:
– nulom nije dozvoljeno
– jedinicom - trivijalno
9/46
Računske operacije – binarni brojni
sistem
11
+11
--110
110
-101
--001
110 x 11
-------110
+ 110
----------10010
1001 : 11 = 11
---100
-011
----0011
-0011
-----0000
10/46
Računske operacije – oktalni brojni
sistem
447
+652
---1321
54,3
-45,4
---6,7
123 x 21
-------123
+ 246
----------2603
2603 : 21 = 123
---26
-21
---50
-42
---63
-63
----0
11/46
Računske operacije –
heksadecimalni brojni sistem
127
+1AA
---2D1
2C
-25
---7
53 x 11
-------53
+ 53
----------583
1A0 x 13
-------4E0
+ 1A0
----------1EE0
583 : 11 = 53
---58
-55
---33
-33
---0
12/46
Konverzije brojnih sistema
• Opšta formula
– celobrojni deo:
celobrojni deo (a) u novu bazu b:
a : b = r1 i ostatak o1
r1 : b = r2 i ostatak o2
r2 : b = r3 i ostatak o3
...
rn : b = 0 i ostatak on
---------------------------------rezultat: on ... o3 o2 o1
13/46
Konverzije brojnih sistema
• Opšta formula
– razlomljeni deo:
razlomljeni deo (a) u novu bazu b:
a ∙ b = c1,r1 tj. celobrojni deo c1 i razlomljeni deo r1
r1 ∙ b = c2,r2 tj. celobrojni deo c2 i razlomljeni deo r2
r2 ∙ b = c3,r3 tj. celobrojni deo c3 i razlomljeni deo r3
...
rn ∙ b = cn,0 tj. celobrojni deo cn i razlomljeni deo 0
-----------------------------------------Rezultat: c1 c2 ... cn
– Problem: ako razlomljeni deo ne bude 0
14/46
Primer
• Broj 701,62510 konvertovati u
heksadecimalni brojni sistem.
701 : 16 = 43 i ostatak 13  D
43 : 16 = 2 i ostatak 11  B
2 : 16 = 0 i ostatak 2
---------------------------------rezultat: 2BD
15/46
Primer
• Razlomljeni deo: 0,625
0,625 ∙ 16 = 10,0 tj. celobrojni deo 10 A i razlomljeni deo 0
-----------------------
• Konačan rezultat: 2BD,A16
16/46
Primer
• Broj 701,062510 konvertovati u oktalni
brojni sistem.
701 : 8 = 87 i ostatak 5
87 : 8 = 10 i ostatak 7
10 : 8 = 1 i ostatak 2
1 : 8 = 0 i ostatak 1
---------------------------------rezultat: 1275
17/46
Primer
• Razlomljeni deo: 0,0625
0,0625 ∙ 8 = 0,5 tj. celobrojni deo 0 i razlomljeni deo 0,5
0,5 ∙ 8 = 4,0 tj. celobrojni deo 4 i razlomljeni deo 0
-----------------------
• Konačan rezultat: 1275,048
18/46
Primer
• Broj 37,62510 konvertovati u binarni brojni
sistem.
37 : 2 = 18 i ostatak 1
18 : 2 = 9 i ostatak 0
9 : 2 = 4 i ostatak 1
4 : 2 = 2 i ostatak 0
2 : 2 = 1 i ostatak 0
1 : 2 = 0 i ostatak 1
---------------------------------rezultat: 100101
19/46
Primer
• Razlomljeni deo: 0,625
0,625 ∙ 2 = 1,250 tj. celobrojni deo 1 i razlomljeni deo 0,250
0,250 ∙ 2 = 0,5
tj. celobrojni deo 0 i razlomljeni deo 0,5
0,5 ∙ 2 = 1,0
tj. celobrojni deo 1 i razlomljeni deo 0
-----------------------
• Konačan rezultat: 100101,1012
20/46
Konverzija iz binarnog u oktalni i
heksadecimalni brojni sistem
• Drugačijim grupisanjem bitova:
– po tri bita za oktalni brojni sistem
– po četiri bita za heksadecimalni brojni sistem
• Primer:
01 100 1112 = 1478
0110 01112 = 6716
21/46
heksadecimalni  oktalni
• Preko binarnog brojnog sistema.
• Primer:
A316 = 1010 00112
10 100 0112 = 2438
22/46
Predstavljanje celobrojnih brojeva
u računaru
• Svaka memorijska ćelija u računaru ima 8
bitova – jedan bajt.
– u jedan bajt se može smestiti broj u rasponu od
0 – 255
• Ako je celobrojna vrednost veća od 255,
uzme se više bajtova:
– dva bajta – 16 bita: 0 – 65535
– četiri bajta – 32 bita: 0 – 4.294.967.295
23/46
Predstavljanje negativnih brojeva
• Preko znaka i apsolutne vrednosti
– komplikovan algoritam za sabiranje i
oduzimanje
• Preko komplementa
– jednostavan algoritam za sabiranje i
oduzimanje
24/46
Predstavljanje negativnih brojeva
komplementom
• Potpuni komplement (u binarnom brojnom
sistemu se još zove i komplement dvojke).
• Nepotpuni komplement (u binarnom
brojnom sistemu se još zove i komplement
jedinice).
• U oba sistema se poslednja cifra koristi za
znak broja (pozitivan ili negativan).
25/46
Potpuni komplement
•
•
•
•
broj x
n cifara
baza b
PotpuniKomplement (x) = bn+1 – x
26/46
Potpuni komplement
• Primer:
znak!
x = 00102=210
n=3
b=2
PotpuniKomplement (2) = 23+1 – 2 =
100002 – 00102 = 11102
znak!
27/46
Potpuni komplement
• Primer:
znak!
x = 11102=-210
n=3
b=2
PotpuniKomplement (-2) = 23+1 – (-2) =
100002 – 11102 = 00102
znak!
28/46
Sabiranje sa potpunim
komplementom
• Pravilo:
A – B = A + PotpuniKomplement(B) =
Rezultat + Prenos
• Ako je Prenos = 1 onda je Rezultat
korektan.
• Ako je Prenos = 0 onda je rezultat
negativan (stvarni rezultat je potpuni
komplement od rezultata sa negativnim
predznakom).
29/46
Primer
• 01012 – 00102 = 01012 + 11102 = 100112
prenos
• 00012 – 00102 = 00012 + 11102 = 011112
prenos
Stvarni rezultat: - PotpuniKomplement(11112) =
100002 – 11112 = - 000012
30/46
Prekoračenje (overflow)
• Javlja se kada se prilikom sabiranja dva
broja dobije rezultat koji ne može da stane
u zadati broj bitova
• Pravilo:
– ako se prilikom sabiranja dva pozitivna ili dva
negativna broja dobije broj suprotnog znaka,
dogodilo se prekoračenje.
• Primer:
01012 + 01002 = 10012
10012 + 10102 = 100112
(5 + 4 = 9)
((-7)+(-6) = -13)
31/46
Nepotpuni komplement
•
•
•
•
broj x
n cifara
baza b
NepotpuniKomplement (x) = (bn+1 -1) – x
32/46
Nepotpuni komplement
• Primer:
znak!
x = 00102=210
n=3
b=2
NepotpuniKomplement (2) = (23+1 -1) – 2 =
(100002 – 00012)– 00102 = 11012
znak!
33/46
Nepotpuni komplement
• Primer:
znak!
x = 11012=-210
n=3
b=2
NepotpuniKomplement (-2) = (23+1 -1)– (-2) =
(100002 - 00012) – 11012 = 00102
znak!
34/46
Sabiranje sa nepotpunim
komplementom
• Pravilo:
A – B = A + NepotpuniKomplement(B) =
Rezultat + Prenos
• Ako je Prenos = 1 onda je
konačan rezultat = rezultat bez prenosa + 1.
• Ako je Prenos = 0 onda je rezultat
negativan (stvarni rezultat je nepotpuni
komplement od rezultata sa negativnim
predznakom).
35/46
Primer
• 01012 – 00102 = 01012 + 11012 = 1 00102
Pravi rezultat: 00102 + 1 = 00112
prenos
• 00012 – 00102 = 00012 + 11012 = 011102
prenos
Stvarni rezultat: - NepotpuniKomplement(11102) =
100002 – 00012 - 11102 = - 000012
36/46
Sračunavanje komplementa bez
oduzimanja!
• Potpuni komplement: invertovati sve
bitove i dodati 1.
– Primer: 00102 => 11012 + 1 = 11102
• Nepotpuni komplement: invertovati sve
bitove.
– Primer: 00102 => 11012
37/46
Predstavljanje celobrojnih brojeva
u računaru
• Svaka memorijska ćelija u računaru ima 8 bitova – jedan
bajt.
– u jedan bajt se može smestiti broj u rasponu od:
• 0 – 255, neoznačen
• -128 – 127, označen, u potpunom/nepotpunom komplementu
• Ako je celobrojna vrednost veća od 128/255, uzme se više
bajtova:
– dva bajta – 16 bita:
• 0 – 65535, neoznačen
• -32768 – 32767, označen, u potpunom/nepotpunom komplementu
– četiri bajta – 32 bita:
• 0 – 4.294.967.295, neoznačen
• -2.147.483.648 – 2.147.483.647, označen, u potpunom/nepotpunom
komplementu
38/46
Predstavljanje razlomljenih brojeva
u računaru
• U nepokretnom zarezu
– fiksna pozicija decimalnog zareza.
• U pokretnom zarezu (floating point)
– brojevi se predstavljaju u obliku: m ∙ be
m – mantisa
b – baza
e – eksponent
• U memoriji računara se pamte mantisa i
eksponent kao celobrojne označene vrednosti,
najčešće sa bazom 2.
39/46
Primer
• 2*102 + 1*101 = 2*102 + 0,1*102 =
(2+0,1)*102 = 2,1*102 = 210
• 2*102 * 3*101 = (2*3)*102+1 = 6*103 = 6000
40/46
Pokretni zarez
• Sabiranje odn. oduzimanje - pre sabiranja
(oduzimanja) brojevi se svedu na isti eksponent:
m1∙ be + m2 ∙ be = (m1 + m2) ∙ be
• Množenje, odn. deljenje:
(m1∙ be1) ∙ (m2 ∙ be2) = (m1 ∙ m2) ∙ b(e1+e2)
• Svođenje eksponenata na istu vrednost se svodi
na smanjenje/povećanje eksponenta, uz
istovremeno deljenje/množenje mantise bazom
– u računaru se deljenje/množenje matise bazom 2
svodi na pomeranje desno/levo bitova.
41/46
Pokretni zarez
• Normalizovana mantisa: kada je
b-1 ≤ |m| ≤ 1
• U praksi se normalizacija mantise svodi na
zapis: 1,xxxx, gde se 1 podrazumeva
• Tada je preciznost najveća.
• Pokretni zarez u računarnima, u nekim
situacijama nije dovoljno precizan!
– razlog je taj što je baza 2, pa konverzija decimalnih
brojeva u oblik m ∙2e ne daje okrugao broj.
– greška je veoma mala, ali se uzastopnim operacijama
može akumulirati.
42/46
Primer
• 2*102 + 1*101 = 2*102 + 0,1*102 =
(2+0,1)*102 = 2,1*102 = 210
• 2*102 * 3*101 = (2*3)*102+1 = 6*103 = 6000
43/46
Kodiranje alfanumeričkih
informacija
• Alfanumerički simboli:
–
–
–
–
numerički simboli (0, 1, ..., 9)
slovni simboli (A, B, ..., Z)
inteprunkcijski znakovi (, . ; : “ ...)
specijalni simboli (#, $, %, ...)
• Standardi:
– ASCII (American Standard Code for Information
Interchange)
– ISO 8859-1
– Windows CP 1250
– Unicode
44/46
Kodovi za detekciju i korekciju
grešaka
• Koncentrisaćemo se na binarni brojni
sistem. Sve informacije će biti kodirane
binarno!
• Uzrok pojave grešaka.
• Kodovi za detekciju grešaka
– u stanju su da detektuju grešku, ali ne i da je
koriguju
• Kodovi za korekciju grešaka
– detekcija i korekcija grešaka
45/46
Kodovi za detekciju grešaka
• Najjednostavnije je da se doda još jedan bit tako da
ukupan broj jedinica u poruci bude paran ili neparan.
• Primer:
– originalna poruka: 001101
– sa dodatnim bitom (uk. br. jedinica paran):
0011011
– sa greškom: 0001011
– vidimo da je došlo do greške pošto je ukupan broj jedinica
neparan!
• Greške od više od jednog bita mogu da prođu
nedetektovane!
1111011
46/46
Karakter za proveru bloka
b1 b2 b3 b4 p1
b5 b6 b7 b8 p2
p3 p4 p5 p6 p7
• U slučaju greške od jednog bita bilo gde,
moguće je detektovati i korigovati grešku:
b1 b2 b3 b4 p1
b5 b6 b7 b8 p2
p3 p4 p5 p6 p7
47/46
CRC kod
• Cyclic Redundancy Character
• Poruka se kao niz bitova deli sa nekim
unapred dogovorenim brojem, rezultat se
odbacuje a ostatak pri deljenju se doda uz
poruku.
• Na prijemnoj strani se primljena poruka
deli istim brojem i ostatak se poredi sa
primljenim ostatkom.
48/46
Računarski praktikum
Rešavanje problema primenom
računara
Rešavanje problema primenom
računara
• Tri faze (opšte):
– analiza problema
– specifikacija rešenja
– realizacija
2/36
Rešavanje problema primenom
računara
• Tri faze:
– analiza problema
– razvoj algoritma za rešavanje problema
– transformacija algoritma u računarski program
(programiranje).
3/36
Analiza problema
• Cilj: da pruži preciznu definiciju i opis
problema, specifikaciju ulaznih podataka,
specifikaciju izlaznih podataka (rezultate
koji se očekuju), kao i postupak da se do
takvih rezultata dođe.
• Specifikacija ulaznih i izlaznih podataka
određuje u izvesnom stepenu i algoritam
obrade podataka.
4/36
Algoritmi
• Algoritam predstavlja niz uputstava koja tačno
određuju redosled operacija koje će dovesti do
rešenja za probleme datog tipa.
• Karakteristike:
– broj operacija koje se moraju izvršiti za rešenje
konkretnog problema nije poznat unapred.
– procedura koja je određena algoritmom je
deterministički proces – data u obliku konačnog broja
instrukcija
– instrukcije koje čine algoritam definišu proceduru koja
se može izvršiti na odgovarajućem skupu podataka i
u svakom slučaju dovodi do korektnog rezultata.
5/36
Algoritmi
• 5 važnih osobina:
– konačnost
– definisanost (bez dvosmislenosti – opis u
odgovarajućem jeziku)
– ulaz
– izlaz
– efikasnost (vreme ili količina zauzete
memorije)
6/36
Predstavljanje algoritama
• Različite tehnike:
– prirodni jezici
– blok dijagrami algoritma (grafička predstava)
– meta jezici (između prirodnih i programskih
jezika)
– programski jezici
7/36
Blok dijagram algoritma
8/36
Simbol obrade
• Za predstavljanje svih operacija u kojima dolazi
do transformacije informacionih struktura
najčešće aritmetičkim, logičkim ili operacijama
prenosa informacionog sadržaja.
A <- B * 3
9/36
Simbol obrade
POČETAK
X2
YX*4
KRAJ
10/36
Simbol ulaza/Izlaza
• Za predstavljanje ulazno/izlaznih operacija koje
uvode podatke u obradu i/ili ispisuju rezultate
obrade.
POČETAK
UČITAJ
X
ULAZ N
REZ  N * N
IZLAZ REZ
KRAJ
11/36
Simbol odluke
• Za označavanje operacija
odlučivanja ili grananja
toka izvođenja algoritma,
a prema nekom
kriterijumu odlučivanja.
• Dve vrste:
– aritmetički
– logički
<
E1:E2
>
=
DA
L
NE
12/36
Simbol podalgoritma
• Da označi više
algoritamskih koraka
pogodno grupisanih u
celinu koju nazivamo
podalgoritam i koju nije
potrebno dalje razlagati u
detalje.
• Motivacija:
Sortiranje niza A po
rastućem redosledu
– ponavljajuće delove
grupisati u podalgoritam
– dekompozicija problema na
manje
13/36
Podalgoritmi
POČETAK
SABIR(X, M, SUMA)
X = {xi}, i = 1, ..., M
M - br. el.
SUMA - suma niza
POČETAK
I <- 1
SUMA <- 0
ULAZ
N, A
A = {ai}, i = 1, ..., N
N - br. el. niza
=
SUMA <- SUMA + X(i)
SABIR(A, N, REZ)
I <- I + 1
IZLAZ
REZ
NE
I>M
KRAJ
DA
POVRATAK
14/36
Osnovne algoritamske strukture
•
•
•
•
Linijska struktura
Struktura sa grananjem
Petlja
Struktura sa podalgoritmima
15/36
Linijska struktura
• Postoji samo jedna
grana izvršavanja.
• Svaki algoritamski
korak se izvršava
samo jednom.
POČETAK
ULAZ
A, B
SUMA <- A+B
RAZ<- A - B
IZLAZ
A, B, SUMA, RAZ
KRAJ
16/36
Struktura sa grananjem
POČETAK
• Kada se u algoritmu
pojavi korak
odlučivanja, odn.
aritmetičkog ili
logičkog testa.
ULAZ
A
<
>
A:0
=
ABS <- - (A)
ABS <- 0
ABS <- A
IZLAZ
A, ABS
KRAJ
17/36
Petlja (ciklična struktura)
• Odlikuje se višestrukim izvršavanjem
jednog ili više algoritamskih koraka.
18/36
Petlja (ciklična struktura)
POČETAK
• Suma niza:
ULAZ
N, A
– Niz:
A = {a1, a2, a3, ..., aN}
= {ai}, i = 1, ..., N
A = {ai}, i = 1, ..., N
I <- 1
SUMA <- 0
=
SUMA <- SUMA + A(i)
I <- I + 1
NE
I>N
DA
IZLAZ
SUMA
KRAJ
19/36
Struktura sa podalgoritmima
• Veza između algoritma i podalgoritma –
lista ulazno-izlaznih parametara
– stvarna lista parametara – parametri koji se
prosleđuju podalgoritmu iz glavnog algoritma
– formalna lista parametara – lista parametara
pozvanog algoritma
• Broj, redosled i vrsta parametara stvarne i
formalne liste mora da se poklapa.
20/36
Struktura sa podalgoritmima
POČETAK
SABIR(X, M, SUMA)
X = {xi}, i = 1, ..., M
M - br. el.
SUMA - suma niza
POČETAK
I <- 1
SUMA <- 0
ULAZ
N, A
A = {ai}, i = 1, ..., N
N - br. el. niza
=
SUMA <- SUMA + X(i)
SABIR(A, N, REZ)
I <- I + 1
IZLAZ
REZ
NE
I>M
KRAJ
DA
POVRATAK
21/36
POČETAK
Struktura sa podalgoritmima
ULAZ N, I
• Primer:
FAKT(N, FN)
n!
 
 
 i  i!(n  i )!
n
  ni n
 
 
 i 1  i  1  i 
n
n
  1
0
n
 n
1
FAKT(I, FI)
FAKT(N-I, FNI)
REZ  FN/(FI*FNI)
IZLAZ REZ
KRAJ
22/36
Struktura sa podalgoritmima
POČETAK
• Parametar N je
ulazni
• Parametar F je
izlazni
FAKT(N, F)
F – Faktorijel
od N
I1
F 1
FF*I
– u njemu je
sračunati faktorijel
(faktorijel od N)
I I+1
DA
I <=N
NE
POVRATAK
23/36
Struktura sa podalgoritmima
• Bolje rešenje:
POČETAK
n!
n
 
 i  i!(n  i )!
ULAZ N, I
 n  ni n
 
 
 i 1  i  1  i 
 
  1
0
n
n
 n
1
BIN(N, I, REZ)
IZLAZ REZ
KRAJ
24/36
Struktura sa podalgoritmima
POČETAK
• Bolje rešenje:
K0
REZ 1
n!
n
 
 i  i!(n  i )!
 n  ni n
 
 
 i 1  i  1  i 
REZ  (N-K)/(K+1)*REZ
n
  1
0
n
 n
1
BIN(N, I, REZ)
REZ – Bin. koef
od N nad I
K K+1
DA
K <=I
NE
POVRATAK
25/36
UML
• Objedinjeni jezik modeliranja (UNIFIED
MODELING LANGUAGE)
• Jezik za modeliranje koji je standardizovan
od strane OMG (Object Management
Group), najšire korišćen u Objektno
Orijentisanoj (OO) analizi i dizajnu
• Vizuelni jezik
• UML daje standardizovanu notaciju i
semantiku za skup OO apstrakcija
26/36
Dijagrami
• Slučajevi korišćenja (use-case diagram)
• Statički
– dijagram klasa (class diagram)
• Dinamički
–
–
–
–
dijagram sekvenci (sequence diagram)
dijagram saradnje (collaboration diagram)
dijagram stanja (statechart diagram)
dijagram aktivnosti (activity diagram)
• Fizički
– dijagram komponenti (component diagram)
– dijagram razmeštaja (deployment diagram)
27/36
Slučajevi korišćenja – primer
Podnošenje konačne prijave
Registacija spoljnjeg korisnika
Formiranje validne prijave kroz interakciju Aplikanta i Obrađivača
Obradjivač/ komisija : 9
Radnik kod aplikanta : 4
28/36
Dijagram klasa – primer
29/36
Dijagram sekvenci – primer
Dijagram saradnje - primer
Dijagram stanja – primer
32/36
Dijagram aktivnosti – primer
Radnik kod aplikanta
Obrađivač/ komisija
Provera da li je istekao
zvanican rok za
preliminarnu
obradupodataka
Sakupljanje dokumentacije potrebne za konkurs
Npr. Receno je da 5
(N) dana pre isteka
zvanicnog roka
sekretarijat nece imati
vremena za
preliminarnu obradu i
nece se time baviti
Sakupljena konkursna dokumentacija [inicijalno]
Sakupljena konkursna dokumentacija [dopunjeno]
Provera roka
[Istekao]
[Nije istekao]
Sakupljanje dodatne dokumentacije
Proveravanje kompletnosti primljene dokumentacije
<<decisionInput>>
Da li korisnik želi da
nastavi da sakuplja
dokumentaciju i da
konkurise?
[Ne]
<<decisionInput>>
Da li je prikupljena
Dokumentacija kompletna
dokumentacija
kompletna?
[Da]
Obaveštavanje aplikanta
[Da]
[Ne]
Nastavak sakupljanja dokumentacije
Obaveštavanje aplikanta o potrebnoj dodatnoj dokumentaciji
Dijagram komponenti – primer
ă
Primarni
agentski centar
Agentsk i
centar 1
Agentski
centar 2
Agentski
centar 4
Agentski
centar 3
Agentski
centar 5
Agentski
centar 6
Dijagram razmeštaja – primer
Server baze:
PowerPC
<<TCP/IP>>
<<TCP/IP>>
Atena:
PENTIUM
Afrodita:
PENTIUM
Programiranje
• Implementacija algoritma na računaru
• Program: niz naredbi (instrukcija) pisanih u
određenom programskom jeziku (izvornom
jeziku) koji poseduje implicitan ili eksplicitan
redosled izvršavanja na računaru.
• Nakon pisanja programa sledi:
– testiranje i
– otkrivanje grešaka (debagiranje – debugging):
• greška u lošoj definiciji problema
• logičke greške u algoritmu
• greške prilikom unosa programa.
36/36
Računarski praktikum
Masovna memorija
Masovna memorija
• Magnetni diskovi
– hard disk,
– flopi disk
• Optički uređaji
– CD-ROM
– CD-Recordable (CD-R)
– CD-R/W
– DVD
• Magnetna traka
2/41
Magnetni diskovi
• Podloga u obliku diska presvučena magnetnim
materijalom
• Podloga
– je ranije bila aluminijum
– je sada od stakla
• uniformnija površina
– povećana čitljivost podataka
• smanjen broj oštećenja površine
– smanjen broj grešaka
• manja udaljenost glave od površine
• čvršće?
• veća otpornost na udarce
3/41
Čitanje i pisanje po magnetnim
diskovima
•
•
•
Čitanje i pisanje preko navoja žice zvanog glava
Za vreme čitanja i pisanja, glava je fiksirana, a ploča se rotira ispod nje
Čitanje (nekada)
– magnetno polje koje se pomera ispod glave izaziva indukciju struje navoju glave
– isti navoj i za čitanje i za pisanje
•
Čitanje (sada)
– odvojene glave za čitanje i pisanje, jedna uz drugu
– delimično oklopljni senzor koji menja otpornost u zavisnosti od magnetnog polja
(magnetoresistive sensor – MR sensor)
• električna otpornost senzora zavisi od smera magnetnog polja
• ovo omogućuje rad na većim frekvencijama
– veća gustina zapisa i brzina
•
Pisanje
– struja kroz navoj izaziva pojavu magnetnog polja
– impulsi se šalju u navoj
– magnetno polje izaziva namagnetisanje materijala ispod glave
• različit smer struje izaziva različit smer namagnetisanja
4/41
Inductive Write MR Read
5/41
Organizacija podataka i
formatiranje
• Disk se sastoji iz koncentričnih krugova ili
staza
– postoji razmak između staza
• smanjenje razmaka povećava kapacitet
• Staze se dele na sektore
– najmanji blok podataka je sektor
• Isti broj bitova po stazi (varijabilna gustina
pakovanja)
– konstantna ugaona brzina
6/41
Staze i sektori
7/41
Brzina obrtanja diska
• Zbog konstantne ugaone brzine, bitovi bliže centru
putuju sporije od bitova na spoljnom delu diska
• Postoji razlika u razmaku između bitova na različitim
stazama (da bi ukupan protok bio isti na svim
stazama)
• Konstantna ugaona brzina (constant angular velocity
- CAV):
– sektori po stazama imaju oblik pite (pie shaped)
– glava se pomera do zadate staze i čeka da sektor prođe
ispod
– gubi se prostor na spoljnim stazama
• smanjena gustina podataka
8/41
Raspored sektora
9/41
Pronalaženje sektora
• Glava mora da pronađe stazu i početak
sektora
• Formatiranje diska
– zapisivanje dodatne informacije koja nije
dostupna korisniku
– označava staze i sektore
10/41
Fizičke karakteristike magnetnih
diskova
1. Fiksna ili pomerajuća glava
2. Promenljivi (removable) ili fiksni
3. Jednostran ili dvostran (single/double
sided) medijum
4. Jedna ili više ploča
5. Mehanizam glave:
– kontaktni (floppy)
– fiksan razmak
– plutajući (leteći) – Winchester
11/41
1. Fiksna ili pomerajuća glava
• Fiksna glava
– jedna glava po stazi
– glava montirane na fiksnom postolju, svaka
iznad svoje staze
• Pomerajuća glava
– jedna glava po strani
– glava montirana na postolju koje se može
pomerati iznad staza
12/41
2. Promenljivi ili fiksni diskovi
• Promenljivi (removable) disk
– može da se ukloni iz uređaja i da se zameni
drugim diskom
– “neograničen kapacitet”
– jednostavan prenos podataka (frisby net)
• Fiksni disk
– trajno montiran u uređaju
13/41
3. Jedna ili dve strane
• Magnetni sloj može biti na obe ili samo na
jednoj strani podloge
14/41
4. Jedna ili više ploča
• Više ploča:
– jedna glava po strani
– glave su poravnate i spojene na istu podlogu
– staze istog prečnika formiraju cilindre
• Podaci su razmešteni po cilindru
– cilindar je skup staza sa istim prečnikom
– smanjuje pomeranje glave
– povećava brzinu prenosa (transfer rate)
15/41
Više ploča
16/41
Staze istog prečnika formiraju cilindar
17/41
5. Mehanizam glave
• Procep na glavi bi trebalo da je što manji
– manji procep, veća gustina podataka
– manji procep, manja razdaljina od glave do površine
• veća verovatnoća greške zbog nečistoća i nesavršenosti
podloge
• Tri vrste mehanizma glave:
– kontaktni (floppy)
– fiksan razmak
– plutajući (leteći) – Winchester
• moderni hard diskovi
18/41
Floppy Disk
• 8”, 5.25”, 3.5”
• Mali kapacitet
– do 1.44Mbyte (2.88M nikada nije zaživeo)
• Sporo
• Jevtino
• Zastarelo!
19/41
Winchester Hard Disk
•
•
•
•
Razvijen u IBM-u, u Winchester (USA)
Hermetički zatvoren disk
Jedna ili više ploča
Lagane glave lebde na sloju vazduha koji
se pomera usled okretanja diska
• Veoma mali razmak između glave i ploče
20/41
Vreme za jednu operaciju
21/41
RAID
•
•
•
•
Redundant Array of Independent Disks
Redundant Array of Inexpensive Disks
6 nivoa u upotrebi
Skup fizičkih diskova koji se vide kao jedan od
strane operativnog sistema
• Podaci su distribuirani po fizičkim diskovima
• Podaci su izdeljeni na trake (strip)
– skup blokova ili staza
• Moguća upotreba redundantnih podataka da bi
se podaci sačuvali u slučaju otkaza diska
22/41
RAID 0
• Nema redundantosti
• Podaci su distribuirani po diskovima na
principu Round Robin
• Povećana brzina
– uzastopni zahtevi verovatno neće završiti na
istom disku
• velika verovatnoća da će podaci biti na više
diskova
– umesto da se pomeri na sledeću traku u jednom disku,
čita se sledeća traka drugog diska
23/41
Data Mapping For RAID 0
24/41
RAID 0
25/41
RAID 1
•
•
•
•
•
•
Podaci duplirani (Mirrored Disks)
Podaci su rapodeljeni po diskovima
Dve kopije svake trake na odvojenim diskovima
Čita se sa bilo kog diska
Piše se po svim diskovima
Spasavanje podataka je jednostavno:
– zameni se neispravan disk i prekopiraju se podaci
– nema gubitka vremena (podaci se uvek mogu pročitati
sa ispravnog diska)
• Skupo
26/41
RAID 1
27/41
SSD
• Solid State Disk
• Memorijska integrisana kola umesto magnetnog medijuma
• Realizovan električno izbrisivom memorijom (flash
memorija)
– čuva sadržaj i posle nestanka napajanja
• Problem: ograničen broj upisa u memorijske ćelije
– 10.000 ili 100.000 upisa
• Podaci se snimaju u stranice (4KB), organizovane u
blokove (512KB)
– najmanja količina podataka je jedna stranica
– može se pisati u stranicu, samo ako je prethodno obrisana
– brišu se čitavi blokovi, a ne stranice
28/41
Optički uređaji
•
•
•
•
CD-ROM
CD-Recordable (CD-R)
CD-R/W
DVD
29/41
Optički medijum CD-ROM
• Originalno zamišljen za audio zapise
• 650MB ili 70 minuta muzike
– u međuvremenu se kao standard pojavio CD
kapaciteta 700MB
• Polikarbonat presvučen refleksnom materijom,
obično aluminijumom
• Podaci su smešteni kao rupe
• Podaci se čitaju laserom
• Konstantna gustina podataka
– konstantna linearna brzina (promenljiva ugaona
brzina)
30/41
Način rada CD-a
31/41
CD-ROM Brzine
• Audio je jednobrzinski (150 KB/s)
– Konstantna linearna brzina (Constant linier
velocity)
– 1.2 m/s
– spiralna staza dugačka 5.27km
• Ostale brzine se daju kao umnošci
osnovne brzine
– primer: 24x
• Navedena brzina je maksimalna brzina
koju uređaj može da postigne
32/41
CD-ROM Format
• SYNC – identifikacija početka bloka
• ID – zaglavlje sa pozicijom bloka i modom (0 – prazan
blok, 1 – podaci sa korekcijom greške, 2 – podaci bez
korekcije greške)
• Data – podaci
• ECC – dodatni podaci za korekciju greške (u modu 1),33/41
još podataka u modu 2 (do ukupno 2336 bajtova)
Random Access na CD-ROM-u
• Teško se postiže:
– glava se pomeri na približnu poziciju
– brzina se prilagodi zadatoj poziciji
– pročita se adresa
– podesi se na željenu lokaciju
34/41
Dobre i loše osobine CD-ROM-a
• Dobre:
– velik kapacitet
– jednostavna tehnologija za masovnu
proizvodnju
– promenljiv medijum (removable)
– robusno
• Loše:
– skupo za male serije
– sporo
– može samo da se čita (read only)
35/41
Ostali optički medijumi
• CD-Recordable (CD-R)
– WORM (Write Once Read Many)
• fabrički se naprave "plikovi" jakim laserom
• u uređaju se zapisivanje svodi na "pucanje plikova" slabim
laserom
– Kompatibilno sa CD-ROM tehnologijom
• CD-RW
– Izbrisivi medijum
•
•
•
•
Promena faze (phase change)
materijal ima različitu refleksivnost u dva stanja
stanje se menja laserom
ograničen broj upisa laserom
– Kompatibilno sa CD-ROM tehnologijom
36/41
DVD
• Digital Video Disk
– zamena za VHS kasete
– u početku samo za puštanje filmova
– sada mogu i da se snimaju filmovi
• Digital Versatile Disk
– zamena za CD-ROM/CD-R/CD-RW
– ista tehnologija, samo u računaru, pa se zato
kloristi i ovo objašnjenje skraćenice
– velik kapacitet
37/41
DVD - tehnologija
• Višeslojni medijum (multi-layer)
• Veoma velik kapacitet (4.7GB po sloju)
– maksimalan kapacitet oko 17GB (dva sloja, dve
strane)
• Ceo film može da stane na jednom disku
– uz upotrebu MPEG kompresije
• Filmovi koriste regionalno kodiranje
– pokušaj sprečavanja piraterije 
– uređaji reprodukuju samo one filmove koji imaji
korektan region
– može da se "sredi"
38/41
Izmenjivi DVD
• Izmenjivi samo jednom:
– DVD -R
– DVD +R
• DVD-RW
– izbrisivi DVD
• DVD – RAM
– izbrisivi DVD
– nema spiralnu stazu, već sektore i staze
poput hard diska
39/41
CD and DVD
40/41
Magnetna traka
•
•
•
•
Serijski pristup podacima
Sporo
Veoma jevtino
Koristi se za arhiviranje (backup)
41/41
Računarski praktikum
1. Prenos podataka i računarske
mreže
2. Internet
1. Prenos podataka i računarske mreže
• Vrste veza
– Point-to-point – direktna veza.
– Deljene veze – više prijemnika i predajnika dele medijum za
prenos.
Prijemnik
Prijemnik
Medijum
Prijemnik
Predajnik
Predajnik
Predajnik
Medijum
2/36
Medijum
• Medijum - fizička veza
• žični
• bežični
• Karakteristike medijuma
• slabljenje
• kašnjenje
• šum
3/36
Medijum
Žični – Parice
• Koriste se za prenos signala u
• LAN – Lokalnim računarskim mrežama
• Udaljenosti prijemnika i predajnika do 100m
• Prenos podataka na brzinama 10, 100, 1000 Mbps
• Javnim telekomunikacionim mrežama
• Udaljenost prijemnika i predajnika je < 10km
4/36
Medijum
Žični – Koaksijalni kabel
• Širok propusni opseg
• Otporan na elektromagnetne smetnje
5/36
Medijum
Žični – Optički kablovi
6/36
Medijum
Bežične veze
• Neusmerene
• radio i televizija
• wireless mrežni uređaji (802.11g)
• Usmerene – point-to-point
• relejne veze
7/36
Računarske mreže
• LAN – Local Area Network
• Definicija: mreža za prenos podataka, optimizovana
za geografski mala područja, kao što su zgrada ili
kampus.
• MAN – Metropolitan Area Network
• Definicija: mreže koje spajaju geografski veća
područja se ponekad nazivaju.
8/36
Topologije: prsten
• Stanice su međusobno povezane direktnim (point-topoint) vezama.
• Podaci se prenose paketski; paketi putuju kroz prsten u
jednom smeru.
• Stanica koja želi da pošalje paket ubacuje ga u prsten.
• Ista stanica čeka da se paket vrati i izbacuje ga iz
cirkulacije.
9/36
Topologije: magistrala
• Sve stanice su priključene na zajednički prenosni
medijum.
• Svaka stanica može da primi svaki poslati paket.
• Zajednički problem: upravljanje pristupom medijumu.
10/36
Topologije: zvezda
• Stanice su direktnim vezama povezane sa centralnim
čvorištem.
• Klasičan primer: digitalna telefonska centrala.
• Mreža fizički izvedena u obliku zvezde može se logički
ponašati kao magistrala (ili prsten).
11/36
Realizacija Topologije
prstena:Token Ring
• Dok je mreža slobodna za slanje, po njoj cirkuliše naročit
kratak paket (token) koji to signalizira stanicama.
• Stanica koja želi da pošalje paket mora da sačeka
slobodan token, modifikuje ga u zauzeti i odmah iza
njega šalje podatke.
• Prsten se oslobađa kad stanica:
• završi sa slanjem paketa i
• ponovo primi zauzeti token.
12/36
Realizacija topologije magistrale
i zvezde:Ethernet
• Sistem sa zajedničkim medijumom.
• Fizička izvedba:
• 10BASE5
• 10BASE2
• 10BASE-T
• 100BASE-T
• IEEE 802.3z Gigabit Ethernet
13/36
Ethernet: koaksijalni kabel [1]
• 10BASE5 (debeli ethernet):
• 10 Mbits/s
• pojedinačni segment: 500m
• ukupna dužina: 2.5km
• 100 stanica
14/36
Ethernet: koaksijalni kabel [2]
• 10BASE2 (tanki ethernet):
• 10 Mbits/s
• pojedinačni segment: 185m
• ukupna dužina: 1km
• 30 stanica
15/36
Ethernet: parice [1]
• 10BASE-T (UTP):
– 10 MBits/s
– dužina segmenta između stanice i hub-a: 100m
(neoklopljene parice)
• 100BASE-T
• 100 Mbit/s
• IEEE 802.3z Gigabit Ethernet
• 1 Gbits/s
• Fizički se izvodi kao zvezda, sa hub-ovima ili switchevima kao čvorištima; logički funkcioniše kao magistrala.
• Razlika između switch-a i hub-a.
16/36
Ethernet: parice [2]
17/36
1. Internet
istorija
Počeci Interneta
• 1957. god. Sovjetski savez lansira Sputnjik
(prvi veštački satelit).
• 1958. god., kao odgovor na lansiranje
Sputnjik-a, SAD osnivaju Advanced
Research Projects Agency (ARPA).
• 1962. god., usvojena ideja da se počne
saradnja sa univerzitetima – osnova
ARPANET-a (preteča Interneta).
19/36
istorija
ARPANET
• 1969. god. mreža računara na ARPANETu se sastoji od 4 računara:
•UCLA (University of
California Los
Angeles)
•SRI (Stanford
Research Institute)
•UCSB (University of
California Santa
Barbara)
•University of Utah
Salt Lake City
20/36
istorija
ARPANET
• 1971. god. ARPANET proširen (15
čvorova):
21/36
istorija
ARPANET
• 1971. god. definisan email – Elektronska
pošta.
• 1973. god.
– definisan File Transfer – razmena datoteka,
– prvi čvor u ARPANET-u izvan SAD –
University College of London (Engleska),
– email čini 75% saobraćaja na ARPANET-u.
• 1975. god. definisane mailing liste –
diskusione grupe.
22/36
istorija
ARPANET
• 1979. god.
– dat predlog da se uvedu tekstualni znaci koji označavaju
emocije – smajliji: :-) ;-) :-(
– kreiran BITNET, kao još jedna mreža računara
• 1980. god. ARPANET u kompletnom zastoju zbog
virusa.
• 1981. god. ukupan broj servera u mreži: 213.
• kreiran CSNET, kao mreža institucija izvan
ARPANET-a.
• 1982. god. osnovan Europe Unix Network – EUnet
– u početku spajao Holandiju, Dansku, Švedsku i Veliku
23/36
Britaniju.
istorija
ARPANET i druge mreže
• 1983. god.
– ustanovljen Domain Name System – sistem
simboličkih adresa umesto numeričkih.
– ukupan broj servera na mreži: 562.
• 1984. god.
– iz CSNET-a kreiran NSFNET.
– ukupan broj servera na mreži: 1024.
• 1985. god. ukupan broj servera na mreži:
1.961.
24/36
istorija
Internet
• 1986. god. kreiran IETF (Internet Engineering Task
Force) – telo za tehničku koordinaciju mreža.
• 1989. god.
– broj servera na mreži prelazi 100.000.
– objavljena priča o hakeru iz Nemačke koji je provaljivao u
vojne računare u SAD i prodavao informacije Sovjetskom
Savezu.
• 1990. god.
– ARPANET prestaje da postoji.
– osmišljen hipertekst sistem koji će postati osnova WWW
(World Wide Web).
– prvi komercijalni provajder – World (world.std.com).
– ukupan broj servera na mreži 313.000.
25/36
istorija
Internet
• 1991. god. startovan prvi WWW server
(nxoc01.cern.ch – kasnije preimenovan u
info.cern.ch).
• 1992. god.
– broj servera na mreži prelazi 1.000.000,
– pojavio se izraz “surfovati po mreži”.
• 1993. god.
– Bela Kuća postavila svoju prezentaciju na internet:
www.whitehouse.gov
– broj servera na mreži: 2,056,000.
26/36
istorija
Internet
• 1994. god.
– kupovina preko Interneta (naručivanje pice kod Pizza Hut),
– broj servera: 3.864.000.
• 1995. god.
– WWW postaje servis broj jedan na Internetu,
– broj servera: 6.642.000.
• 1996. god.
– pojavljuju se kompanije koje omogućavaju telefoniranje preko
Interneta,
– provaljeni (uhakovani) sajtovi: US Dept of Justice, CIA, US Air
Force,
– pretraživači interneta (Altavista, Yahoo, i dr.),
– SR Jugoslavija dobila pristup na Internet (podignute sankcije).
27/36
istorija
Internet
• 1997 – danas:
– uvođenje e-commerce,
– prvi veliki sajber-rat za vreme bombardovanja SRJ
(napadi hakera na NATO i ostale institucije),
– panika zbog milenijumske greške (godina 2000.),
– mobilni telefoni pristupaju Internetu (WAP, GPRS),
– uvođenje Interneta v6 – više čvorova,
– 2003. god. broj servera na Internetu: 171.000.000.
28/36
Adresiranje na Internetu
• Aktuelna verzija Interneta je v4
• Računari se identifikuju preko IP adrese:
a.b.c.d
a, b, c, d su brojevi u rasponu od 0 do 255
• Primer:
147.91.173.1
• Podela IP adresa:
– javne (jedinstvene na Internetu, vidljive sa svake adrese na
Internetu),
– privatne (unutar privatnih mreža; primer: 192.168.0.1),
– specijalne namene (broadcast).
• Internet verzija 6 (v6) omogućuje postojanje većeg broja
adresa
– sve više računara podržava ovaj standard
– Internet v4 uskoro ostaje bez javnih IP adresa
29/36
Adresiranje na Internetu
• Alternativan način identifikacije – simbolička
adresa:
ime_računara.domen
domen = institucija.tip_institucije.lokacija
• Primeri:
www.uns.ac.rs
www.ftn.uns.ac.rs
www.whitehouse.gov
• Domeni:
– nacionalni,
– internacionalni/američki
30/36
Nacionalni domen
• Lokacija – dvoslovna skraćenica na kraju
adrese, prema ISO-3166 standardu (rs – Srbija, uk –
Velika Britanija, itd.).
• Tip institucije:
– ac (akademske ustanove),
– co (komercijalne ustanove),
– org (nekomercijalne organizacije),
– itd.
• Primer nacionalnog domena iskorišćenog u
internacionalne svrhe:
www.mtv.tv (tv je skraćenica za državu Tuvalu!)
31/36
Internacionalni/američki domen
• Tip institucije:
–
–
–
–
–
–
edu (akademske ustanove),
com (komercijalna ustanova),
org (nekomercijalne organizacije),
mil (vojne organizacije),
gov (vladine organizacije),
itd.
• Primer:
www.ibm.com
www.revlon.com
www.sony.com
• SAD uglavnom koriste domene: edu, gov, mil
(www.whitehouse.gov).
32/36
Servisi na Internetu
• Servisi su usluge.
• Vrste:
– WWW (World Wide Web) – multimedijalni
dokumenti na Internetu,
– Chat, voice chat, video telefonija,
– Elektronska pošta (email, e-mail, Email, ...),
– Prenos datoteka (FTP – File Transfer,
Protocol),
– Telnet – rad na udaljenom računaru.
33/36
WWW
• Sistem se sastoji iz klijenata i servera.
• Multimedijalni dokumenti se kreiraju upotrebom HTML
jezika (HyperText Markup Language).
• WWW Klijenti:
– spajaju se na WWW servere i zahtevaju resurse (html datoteke,
slike, muziku, itd.)
– trenutno aktuelni: Internet Explorer, Mozilla, Opera, itd.
• WWW Serveri:
– čekaju klijente i opslužuju njihove zahteve
– trenutno aktuelni: Apache, Internet Information Services (IIS), itd.
• Protokol za komunikaciju između klijenata i servera je
HTTP protokol (HyperText Transfer Protocol).
34/36
Chat, telefonija
• Chat – mogućnost komunikacije pisanim
porukama u realnom vremenu
• Voice chat – razgovor preko interneta
• Video telefonija – razgovor uz upotrebu
kamere preko interneta.
• Programi:
– MIRC, Yahoo messanger, MS Messanger,
Skype, ICQ, ...
35/36
email
• Sistem se sastoji iz klijenata i servera.
• Protokoli za komunikaciju između klijenata i servera:
SMTP (Simple Mail Transport Protocol), POP3 (Post
Office Protocol), IMAP (Internet Message Access
Protocol).
• Organizovano po principu postojeće pošte (elektronsko
sanduče prima poruke, klijenti preuzimaju poruke iz
sandučeta i prikazuju, postoji adresa primaoca, pošiljalac
ne mora da se identifikuje).
• Email adresa: [email protected]_računara
• Primer: [email protected]
• Trenutno aktuelni klijenti: Mozilla Thunderbird, Microsoft
Outlook, Microsoft Outlook Express, itd.
36/36
Programski jezik Java
Uvod
Uvod
• Dr Milan Vidaković
• Preporučena literatura:
Java i Internet programiranje,
Branko Milosavljević, Milan Vidaković,
FTN izdavaštvo, Novi Sad, 2007.
ISBN 978-86-7892-047-9
2/47
Programski jezik Java
1.
Java:: platforma za izvršavanje programa
Java
2.
Java:: programski jezik
Java
3/47
Java kao platforma
• dizajniran da što manje zavisi od
specifičnih karakteristika konkretnog
računarskog sistema
• jednom napisan i preveden program se
izvršava na bilo kojoj platformi koja
podržava Javu
4/47
Java kao platforma
• interpretirani jezik
– just in time compiler
• bajt-kod
– specifikacija je dostupna – više
implementacija kompajlera
• Java virtuelna mašina (JVM)
– specifikacija je dostupna – više
implementacija JVM
5/47
Java kao programski jezik
• jezik opšte namene
• konkurentno, objektno-orijentisano
programiranje
• literatura
– Referentna dokumentacija: JavaSoft homepage
http://java.sun.com
– Preporučena knjiga:
Milosavljević, Vidaković: Java i Internet
programiranje
Bruce Eckel: Thinking in Java,
http://www.bruceeckel.com
6/47
Izvršavanje programa
• metoda main()
Hello.java
class Hello {
public static void main(String args[]) {
System.out.println(“Hello world!”);
}
}
7/47
Prevođenje i pokretanje
• prevođenje:
javac Hello.java
• pokretanje:
java Hello
[ ovo važi sa standardni razvojni paket JDK (Java Development Kit) ]
8/47
Osnovni koncepti
• sintaksa: podseća na C++
• programski blok je ograđen vitičastim zagradama:
{ ... }
• tipovi podataka
– primitivni tipovi
• kao lokalne promenljive i parametri metoda, čuvaju se na steku
• kao parametri, uvek se prenose po vrednosti!
– objekti
• čuvaju se na heap-u
• postoje samo reference na objekte, nikada se ne može pristupiti
samom objektu
• kao lokalne promenljive i parametri metoda, reference se čuvaju na
steku
• metode: povratna_vrednost naziv(parametri) { }
9/47
Osnovni koncepti
• primitivni tipovi podataka
Primitivni tip
boolean
char
byte
short
int
long
float
double
void
Veličina
1-bit
16-bit
8-bit
16-bit
32-bit
64-bit
32-bit
64-bit
–
Minimum
–
Unicode 0
-128
-215
-231
-263
IEEE754
IEEE754
–
Maksimum
–
Unicode 216- 1
+127
+215 – 1
+231 – 1
+263 – 1
IEEE754
IEEE754
–
10/47
Konstante
• Celobrojne konstante:
– 2,
– 2000000L
• Razlomljene konstante: 3.14
• Heksadecimalne konstante: 0xF, 0xFF
• Znakovne konstante:
– ‘a’
– ‘\n’
– ‘\xxx’, gde je xxx oktalni ASCII kod karaktera
• String konstante: “ovo je tekst”
11/47
Deklaracija promenljive primitivnog
tipa
• Promenljiva se može deklarisati u bilo kom bloku
– ne mora na početku metode.
• int a;
• int a = 0;
• int a, b;
• int a = 0, b = 3;
12/47
Implicitna konverzija tipova
• Sa “užeg” ili “manjeg” tipa na “širi” ili “veći”
tip.
• Nema gubitka informacije jer “uži” tip
podatka staje u “širi” tip podatka.
• Primer:
long a;
int i = 5;
a = i;
13/47
Eksplicitna konverzija tipova
• Sa “šireg” na “uži” tip podatka – posledica
je gubljenje informacije.
• Primer:
Greška pri
long a = 5L;
kompajliranju!
int b = a;
14/47
Eksplicitna konverzija tipova
• Pravilna eksplicitna konverzija – upotreba
cast operatora:
• Primer:
long a = 5L;
int b = (int)a;
15/47
Enumeracije
• Nabrojivi tipovi podataka (celobrojni)
• Primer:
enum Size {SMALL, MEDIUM, LARGE,
EXTRA_LARGE};
Size s = Size.MEDIUM;
enum Days {MON, TUE, WEN, THU, FRI,
SAT, SUN};
Days d = Days.MON;
16/47
Operatori




aritmetički operatori
relacioni i logički
bit-operatori
operator dodele
17/47
Aritmetički operatori
• Osnovne operacije:
+, -, *, /, %
• Umesto x = x + 1
x += 1
• Automatski inkrement: ++x odn. x++
18/47
Aritmetički operatori
y = 5;
Operator
Rezultat
x=y+2
X 7
x=y-2
X 3
x=y%2
X 1
x=++y
X6, y6
x=y++
X5, y6
x=--y
X4, y4
Aritmetički operatori
x = 10;
y = 5;
Operator
Isto kao
x=y
Rezultat
x 5
x+=y
x=x+y
x 15
x-=y
x=x-y
x 5
x*=y
x=x*y
x 50
x/=y
x=x/y
x 2
x%=y
x=x%y
x 0
20/47
Relacioni i logički operatori
• Relacioni: < > <= >= == !=
• Logički: && (I), || (ILI), ! (NE)
21/47
Relacioni operatori
x = 5;
Operator
Rezultat
==
x == 8 je netačno (false)
!=
x != 8 je tačno (true)
>
x > 8 je netačno (false)
<
x < 8 je tačno (true)
>=
x >= 8 je netačno (false)
<=
x <= 8 je tačno (true)
22/47
Logički operatori
• Logički: &&
||
!
• Rezultat logičkih operatora je tačno (true) ili
netačno (false)
• Operandi logičkih operatora su logički izrazi
&&
false
true
||
false
true
!
false
false
false
false
false
true
false
true
true
false
true
true
true
true
true
false
Logički operatori
x = 6;
y = 3;
Operator
Objašnjenje
&&
konjukcija (and, i) (x < 10 && y > 1)
tačno (true)
disjunkcija (or, ili) (x==5 || y==5)
netačno (false)
negacija (not, ne) !(x==y)
tačno (true)
||
!
Primer
24/47
Bit operatori
•
•
•
•
Logičko I nad bitovima: &
Logičko ILI nad bitovima: |
Ekskluzivno ILI (XOR) nad bitovima: ^
Logička negacija nad bitovima -unarni
operator: ~
• Kombinacija sa =:
&= |= ^=
25/47
Bit operatori
• a = 3; // a=011 binarno
• b = 6; // b=110 binarno
• c = a & b;
011
& 110
-------010
• c  2;
26/47
Bit operatori
• Shift-ovanje (pomeranje):
a>>b – pomera bitove u a za b mesta
- ako je a pozitivan, ubacuje 0
- ako je a negativan, ubacuje 1
a<<b – pomera bitove u levo i ubacuje 0
a>>>b – pomera bitove u a u desno za b mesta i
ubacuje 0 bez obzira na znak a.
• Rezultat pomeranja je 32-bitan, osim ako
promenljiva koja prihvata rezultat nije long (tada
je 64-bitan)!
27/47
Pomeranje
• a = 3;
• b = a<<2;
// a = 011 binarno
// b = 01100 binarno
• a = 7;
• b = a>>2;
// a = 111 binarno
// b = 001 binarno
28/47
Operator dodele
21.10
• Ako su operandi primitivni tipovi, kopira se
sadržaj:
int i = 3, j = 6;
i = j; // u i ubačeno 6
• Ako su operandi reference, kopira se
sadržaj reference, a ne kompletni objekti
na koje ukazuju!
29/47
Kontrola toka
• if else
• switch
• for
• while
• do while
• break
• continue
30/47
if
if (uslov)
akcija
if (uslov)
akcija
else
druga_akcija
31/47
if else
int result = 0;
if(testval > target)
result = -1;
else if(testval < target)
result = +1;
else
result = 0; // match
32/47
if (bodovi >= 95)
ocena = 10;
else if (bodovi >= 85)
ocena = 9;
else if (bodovi >= 75)
ocena = 8;
else if (bodovi >= 65)
ocena = 7;
else if (bodovi >= 55)
ocena = 6;
else
ocena = 5;
33/47
Uslovni operator
a = i < 10 ? i * 100 : i * 10;
• isto kao:
if (i < 10)
a = i * 100;
else
a = i * 10;
34/47
switch
• Izraz u switch() izrazu mora da proizvede
celobrojnu vrednost.
• Ako ne proizvodi celobrojnu vrednost, ne
može da se koristi switch,() već if()!
• Ako se izostavi break; propašće u sledeći
case:
• Kod default: izraza ne mora break; - to se
podrazumeva.
35/47
switch
switch(c) {
case 'a':
case 'e':
case 'i':
case 'o':
case 'u':
System.out.println("samoglasnik");
break;
default:
System.out.println("suglasnik");
}
36/47
varijanta 1, bez switch
if (ocena == 5)
System.out.println(“odlican”);
else if (ocena == 4)
System.out.println(“vrlo dobar”);
else if (ocena == 3)
System.out.println(“dobar”);
else if (ocena == 2)
System.out.println(“dovoljan”);
else if (ocena == 1)
System.out.println(“nedovoljan”);
else
System.out.println(“nepostojeca ocena”);
37/47
varijanta 2
switch (ocena) {
case 5: System.out.println(“odlican”);
break;
case 4: System.out.println(“vrlo dobar”);
break;
case 3: System.out.println(“dobar”);
break;
case 2: System.out.println(“dovoljan”);
break;
case 1: System.out.println(“nedovoljan”);
break;
default: System.out.println(“nepostojeca ocena”);
}
38/47
for
• Za organizaciju petlji kod kojih se unapred
zna koliko puta će se izvršiti telo ciklusa.
• Petlja sa početnom vrednošću, uslovom za
kraj i blokom za korekciju.
• Opšta sintaksa:
for (inicijalizacija; uslov; korekcija)
telo
39/47
for
for (int i = 0; i < 10; i++)
System.out.println(i);
• može i višestruka inicijalizacija i step-statement:
for(int i = 0, j = 1;
i < 10 && j != 11;i++, j++)
• oprez (može da se ne završi):
for (double x = 0; x != 10; x+=0.1) ...
40/47
while
• Za cikličnu strukturu kod koje se samo zna
uslov za prekid.
• Telo ciklusa ne mora ni jednom da se
izvrši
• Opšta sintaksa:
while (uslov)
telo
• Važno: izlaz iz petlje na false!
41/47
while
int i = 0;
while (i <= 10)
{
System.out.println("Trenutno
je " + i);
i=i+1;
}
• Važno: izlaz iz petlje na false!
42/47
do while
• Za cikličnu strukturu kod koje se samo zna
uslov za prekid
• Razlika u odnosu na while petlju je u tome
što se telo ciklusa izvršava makar jednom.
• Opšta sintaksa:
do
telo
while (uslov);
• Važno: izlaz iz petlje na false!
43/47
do while
int i = 0;
do {
System.out.println(i++);
} while (i < 10);
• Važno: izlaz iz petlje na false!
44/47
break i continue
• break – prekida telo tekuće ciklične
strukture (ili case: dela) i izlazi iz nje.
• continue – prekida telo tekuce ciklične
strukture i otpočinje sledeću iteraciju
petlje.
45/47
break i continue
for(int i = 0; i < 10; i++) {
if (i==7) {
break;
}
if (i == 2)
continue;
System.out.println("Broj je:" + i);
}
46/47
Izlaz iz ugnježdene petlje
for (...)
{
for (...)
{
...
if (uslov)
break;
}
}
47/47
Računarski pratikum
Nizovi, kolekcije i asocijativne mape
Stringovi
Nizovi
int a[]; // još uvek nije napravljen niz!
a = new int[5]; // niz od 5 nula
ili
int a[] = new int[5]; // niz od 5 nula
ili
int a[] = { 1, 2, 3, 4, 5 };
2/26
Nizovi primitivnih tipova 1/3
a
stek
heap
int a[];
3/26
Nizovi primitivnih tipova 2/3
0
0
0
0
0
a
stek
heap
a = new int[5];
4/26
Nizovi primitivnih tipova 3/3
1
2
3
4
5
a
stek
heap
a[0]=1; a[1]=2; a[2]=3; a[3]=4; a[4]=5;
5/26
Nizovi primitivnih tipova
jednim potezom
1
2
3
4
5
a
stek
heap
int a[] = { 1, 2, 3, 4, 5 };
6/26
Višedimenzionalni nizovi
int a[][] = { {1, 2, 3 },
6 } };
{4, 5,
int a[][] = new int[2][3];
int a[][] = new int[2][];
for(int i = 0; i < a.length; i++)
{
a[i] = new int[3];
}
7/26
Klasa String
• Niz karaktera je podržan klasom String. String nije samo
niz karaktera – on je klasa!
• Objekti klase String se ne mogu menjati (immutable)!
• Reprezentativne metode:
–
–
–
–
–
–
str.length()
str.charAt(i)
str.indexOf(s)
str.substring(a,b), str.substring(a)
str.equals(s), str. equalsIgnoreCase(s) – ne koristiti ==
str.startsWith(s)
8/26
Klasa String
class StringTest {
public static void main(String args[]) {
String s1 = "Ovo je";
String s2 = "je string";
System.out.println(s1.substring(2));
// karakter na zadatoj poziciji
System.out.println(s2.charAt(3));
// poređenje po jednakosti
System.out.println(s1.equals(s2));
// pozicija zadatog podstringa
System.out.println(s1.indexOf("je"));
// dužina stringa
System.out.println(s2.length());
// skidanje whitespace-ova sa poč. i kraja
System.out.println(s1.trim());
// provera da li string počinje podstringom
System.out.println(s2.startsWith("je"));
Ispis na konzoli:
o je
s
false
4
9
Ovo je
true
}
}
9/26
Redefinisan + operator sa
stringovima
• Ako je jedan od operanada klase String, ceo
izraz je string!
String a = “Vrednost i je: “ + i;
• metoda toString()
10/26
Metoda split() klase String
• "cepa" osnovni string na niz stringova po
zadatom šablonu
– originalni string se ne menja
– parametar je regularni izraz
• Poziv: String[] rez = s.split(“regex”);
• Primer:
String s = "ja sam svetski mega car";
String[] rez = s.split(" ");
11/26
Metoda split() klase String
class SplitTest {
public static void main(String args[]) {
String text = "Ovo je probni tekst";
String[] tokens = text.split(" ");
for (int i = 0; i < tokens.length; i++)
System.out.println(tokens[i]);
}
}
}
12/26
Kolekcije
• Nizovi imaju jednu manu – kada se
jednom naprave nije moguće promeniti
veličinu.
• Kolekcije rešavaju taj problem.
• Zajedničke metode:
– dodavanje elemenata,
– uklanjanje elemenata,
– iteriranje kroz kolekciju elemenata
13/26
Kolekcije
Implementacija
Hash
table
Resizable
Array
Balanced Linked
Tree
List
Hash table +
Linked list
TreeSet
LinkedHashSet
Koncept
Set
HashSet
List
Map
LinkedList
ArrayList
HashMap
TreeMap
LinkedHashMap
Tipizirane kolekcije - Generics
• U dosadašnjim kolekcijama mogli su da se smeste bilo koji objekti.
• Mana: prilikom pristupa elementu iz kolekcije, obavezno se kastuje
u konkretan tip:
ArrayList kolekcija = new ArrayList();
kolekcija.add("tekst");
String s = (String)kolekcija.get(0);
Potencijalan problem
prilikom pogrešnog
kastovanja
• Tipizirane kolekcije omogućavaju smeštaj samo jednog tipa podatka
u kolekciju.
• Primer:
ArrayList<String> kolekcija = new ArrayList<String>();
kolekcija.add("tekst");
String s = kolekcija.get(0);
15/26
for bez indeksiranja
(poznat i kao foreach)
• Omogućuje prolazak kroz niz ili kolekciju.
• Opšta sintaksa:
for (varijabla : niz) {
... // telo
}
• Primer:
for (int i : niz) {
System.out.println(i);
}
for (Auto a : kolekcija) {
System.out.println(a.radi);
}
16/26
Klasa ArrayList
• Predstavlja kolekciju, odn. dinamički niz
• Elementi se u ArrayList dodaju metodom
add()
• Elementi se iz ArrayList uklanjaju
metodom remove()
• Elementi se iz ArrayList dobijaju (ne
uklanjaju se, već se samo čitaju) metodom
get()
17/26
Klasa ArrayList
ArrayList<Integer> lista = new
ArrayList<Integer>();
lista.add(5);
lista.add(10);
lista.add(1, 15);
System.out.println("Velicina je: " +
lista.size());
lista.remove(0);
int broj = lista.get(0);
System.out.println(broj);
System.out.println("Velicina je: " +
lista.size());
Klasa ArrayList
import java.util.ArrayList;
class ArrayListTest {
public static void main(String args[]) {
ArrayList v = new ArrayList();
v.add("Ovo");
v.add("je");
v.add("probni");
v.add("tekst");
for (int i = 0; i < v.size(); i++)
System.out.println(v.get(i));
}
}
19/26
Tipizirana klasa ArrayList
import java.util.ArrayList;
class ArrayListTest {
public static void main(String args[]) {
ArrayList<String> v = new ArrayList<String>();
v.add("Ovo");
v.add("je");
v.add("probni");
v.add("tekst");
for (int i = 0; i < v.size(); i++)
System.out.print((String)v.get(i) + " ");
}
}
20/26
Asocijativne mape
• Memorijske strukture koje omogućuju brzu
pretragu sadržaja po ključu
21/26
Klasa HashMap
• Predstavlja asocijativnu mapu
• U HashMap se stavljaju dva podatka:
– ključ po kojem će se pretraživati
– vrednost koja se skladišti u HashMap i koja se
pretražuje po ključu
• Metodom put() se ključ i vrednost
smeštaju u HashMap
• Metodom get() se na osnovu ključa
dobavlja (samo čita) vrednost iz HashMap
22/26
Klasa HashMap
import java.util.HashMap;
public class HashMapTest {
public static void main(String args[]) {
HashMap ht = new HashMap();
ht.put("E10020", "Marko Markovic");
ht.put("E10045", "Petar Petrovic");
ht.put("E10093", "Jovan Jovanovic");
String indeks = "E10045";
System.out.println("Student sa brojem indeksa " +
indeks + " je " + ht.get(indeks));
indeks = "E10093";
System.out.println("Student sa brojem indeksa " +
indeks + " je " + ht.get(indeks));
}
23/26
Tipizirana klasa HashMap
import java.util.HashMap;
public class HashMapTest {
public static void main(String args[]) {
HashMap<String, String> ht =
new HashMap<String, String>();
ht.put("E10020", "Marko Markovic");
ht.put("E10045", "Petar Petrovic");
ht.put("E10093", "Jovan Jovanovic");
String indeks = "E10045";
System.out.println("Student sa brojem indeksa " +
indeks + " je " + ht.get(indeks));
indeks = "E10093";
System.out.println("Student sa brojem indeksa " +
indeks + " je " + ht.get(indeks));
}
24/26
Klasa StringTokenizer
• Radi sličan posao kao i metoda split()
klase String – "cepa" zadati string po
delimiteru (ili delimiterima)
• Ne radi sa regularnim izrazima
• Reziltat cepanja je kolekcija stringovva
kroz koju se iterira metodama
hasMoreTokens() i nextToken()
25/26
Klasa StringTokenizer
import java.util.*;
class TokenizerTest {
public static void main(String args[]) {
String text = "Ovo je probni tekst";
StringTokenizer st = new StringTokenizer(text, " ");
while (st.hasMoreTokens()) {
System.out.println(st.nextToken());
}
}
}
26/26
Računarski praktikum
Funkcije
Funkcije
• Motivacija:
– ponavljanje koda
– dekompozicija na manje celine
• Osnovni elementi:
– definicija
– poziv
2/16
Definicija
• Opšta sintaksa:
povratni_tip ime_funkcije(parametri) {
...
}
• Povratni tip je bilo koji tip podatka ili void ako funkcija ne vraća
vrednost.
– funkcija vraća najviše jednu vrednost!
• Parametri se deklarišu na isti način kao i promenljive.
– Ako funkcija nema parametara ostave se prazne zagrade.
• Ako funkcija vraća vrednost, to se postiže return naredbom:
– return a;
– return (a);
3/16
Parametri i rezultat metoda
• parametri mogu biti:
– primitivni tipovi
– reference na objekte
• rezultat može biti:
– primitivni tip
– referenca na objekat
• Metoda vraća vrednost naredbom:
return vrednost
ili
return (vrednost)
4/16
Primeri definicije
static int max(int a, int b) {
if (a > b)
return a;
else
return b;
}
static void printInt(int i) {
System.out.printf("%d", i);
}
5/16
Primer
Sinus.java
• Napisati funkciju sinus koja izračunava sinus razvojem u
Tejlorov red, tačnosti 10-6, po formuli:
sinus(x) = x/1! - x3/3! + x5/5! - x7/7! + ...
sabirak = x; znak = 1; stepen = 1;
while (Math.abs(sabirak) > 1E-6)
{
s = s + sabirak;
znak = znak*-1;
stepen = stepen + 2;
sabirak = znak *
Math.pow(x,stepen)/fakt(stepen);
}
6/16
Parametri funkcija
• Parametri funkcija se u nekim
programskim jezicima prenose po
vrednosti ili po referenci
– u programskom jeziku Java, prenos je
isključivo po vrednosti
7/16
Prenos parametara
po vrednosti
• Prenos parametara po vrednosti:
– prave se kopije parametara i te kopije se
prosleđuju funkciji
– posledica: nije moguće promeniti prosleđenu
promenljivu iz funkcije
8/16
Prenos parametara
po vrednosti
Vrednost.java
static void f(int i)
{
i = 3;
}
public static void main(String[] a) {
int i = 5;
f(i);
System.out.printf("%d", i);
}
Šta će biti
odštampano?
9/16
Nizovi kao parametri funkcija
• U listi parametara funkcije ne navode se
dimenzije.
Ovo će promeniti a[3] u pozivajućoj
• Primer:
funkciji!
void f(int a[]) {
...
a[3] = 5;
}
POSLEDICA:
• Niz se može promeniti iz funkcije!
• Nizovi se ne prosleđuju po vrednosti,
tj. ne pravi se kopija niza!
• Ako je potrebna veličina niza, ona se može
saznati iz atributa length:
a.length
Nizovi.java
10/16
Višedimenzionalni nizovi kao
parametri funkcija
• U listi parametara funkcije se ne navode
dimenzije
– ta informacija se može saznati iz same promenljive
• a.length – broj vrsta
• a[0].length – broj kolona
• Primer:
void f(int a[][]) {
...
a[3][3] = 5;
}
Nizovi.java
11/16
Opseg vidljivosti promenljivih
• Promenljive deklarisane unutar funkcije se
“vide” samo u funkciji
– to su lokalne promenljive
• Pomenljive deklarisane izvan funkcije se
“vide” i u ostalim funkcijama
– to su atributi
12/16
Opseg vidljivosti promenljivih
void f(int i) {
i = 3;
}
int a;
void f2(int i) {
int b;
a = 5;
i = 3;
}
void f3(int i) {
int a;
a = 5;
i = 3;
}
13/16
Rekurzivne funkcije
• Rekurzija: funkcija poziva
samu sebe
• Svaka rekurzivna funkcija
mora da ima uslov za
izlaz iz rekurzije!
• Pozitivno:
– razumljivije
– ponekad i jedino moguće
(Akermanova funkcija)
• Mana:
– opterećuje stek
– brzina
14/16
Rekurzivne funkcije
int fakt(int n)
{
int i, f=1;
for (i = 1; i <= n; i++)
{
f *= i;
}
return f;
}
Fakt1.java
int fakt(int n)
{
if (n < 2)
return 1;
return n * fakt(n-1);
}
Fakt2.java
15/16
Varijabilan broj parametara
• Ako želimo da metoda ima varijabilan broj
parametara, deklarišemo na sledeći način:
void f(int... params) {...}
• Parametrima se pristupa kao elementima
niza:
int a = params[2];
16/16
Računarski praktikum
Ulazno izlazni podsistem
Ulazno izlazni podsistem
•
standardna biblioteka za ulazno/izlazne operacije
•
izvorišta/odredišta:
•
•
tastatura/konzola
•
fajl sistem
•
memorija
•
mrežne konekcije
oslanja se na tokove (streams) i čitače/pisače
(reader/writer)
2/20
Štampanje na ekran
• System.out je izlazni tok:
System.out.print(“Poruka”);
System.out.println(“Poruka”);
• Ispis se može i formatirati:
System.out.printf(“format”, argumenti);
System.out.printf(“%.2f %d”, (10000.0 / 3), 5);
3/20
Štampanje na ekran
• Funkcija printf iz biblioteke stdio.h
• Prvi parametar je specifikator formata ispisa,
a ostali parametri su varijable čija se vrednost
štampa.
• Specifikator formata:
%[širina][.preciznost]tip
4/20
printf - širina
• Definiše broj cifara
[širina]¦ Kako utiče na preciznost
---------+-------------------------------------------------------n
¦ Štampa zadati broj cifara.
0n
¦ Štampa zadati broj cifara.
¦ Ako broj nema toliko cifara, sa leve se popunjava nulama.
5/20
printf – tip - brojevi
Tip ¦ Očekivan ulaz ¦ Format rezultat
-----------------------------------------------------------------------------Brojevi
-----------------------------------------------------------------------------b ¦ Boolean
¦ Boolean
d ¦ Integer
¦ Signed decimal integer
o ¦ Integer
¦ Unsigned octal integer
u ¦ Integer
¦ Unsigned decimal integer
h,x¦ Integer
¦ Unsigned hexadecimal int (with a, b, c, d, e, f)
H,X¦ Integer
¦ Unsigned hexadecimal int (with A, B, C, D, E, F)
f ¦ Floating point ¦ Signed value oblika [-]dddd.dddd.
e ¦ Floating point ¦ Signed value oblika [-]d.dddd or e[+/-]ddd
g ¦ Floating point ¦ Kraći zapis od %f i %e
E ¦ Floating point ¦ Isto kao e; samo ima ‘E’ za eksponent
G ¦ Floating point ¦ Isto kao e; samo ima ‘E’ za eksponent ako je e format
------------------------------------------------------------------------------
6/20
printf – tip - karakteri
Tip ¦ Očekivan ulaz ¦ Format rezultat
--------------------------------------------------------------------------Karakteri
--------------------------------------------------------------------------c ¦ Character
¦ Jedno slovo
s ¦ String
¦ Štampa string do kraja ili do zadatog broja slova
% ¦ Ništa
¦ Štampa znak %
---------------------------------------------------------------------------
7/20
printf - primeri
System.out.printf("celobrojni: %d\n", c);
System.out. printf("celobrojni: %6d\n", c);
System.out. printf("celobrojni: %-6d\n", c);
System.out. printf("celobrojni: %+6d\n", c);
System.out. printf("celobrojni: %+6d\n", -c);
System.out.
System.out.
System.out.
System.out.
System.out.
printf("razlomljeni:
printf("razlomljeni:
printf("razlomljeni:
printf("razlomljeni:
printf("razlomljeni:
-->
-->
-->
-->
-->
%f\n", 3.141);
%6.2f\n", 3.141);
%e\n", 3.141);
%6.2e\n", 3.141);
%g\n", 3.141);
-->
-->
-->
-->
-->
celobrojni: 356
celobrojni:
356
celobrojni: 356
celobrojni:
+356
celobrojni:
-356
razlomljeni:
razlomljeni:
razlomljeni:
razlomljeni:
razlomljeni:
TestPrintf.java
3.141000
3.14
3.141000e+00
3.14e+00
3.14100
8/20
Unos sa tastature
• System.in je ulazni tok:
BufferedReader in = new BufferedReader(new
InputStreamReader(System.in));
String s = in.readLine();
• Alternativa je klasa Scanner koja ne
učitava samo stringove:
Scanner sc = new Scanner(System.in);
String s = sc.nextLine();
int i = sc.nextInt();
float f = sc.nextFloat();
9/20
Unos drugih primitivnih tipova sa
tastature
• Koristi se wrapper klasa i njena metoda
parseXxx():
BufferedReader in = new BufferedReader( new
InputStreamReader(System.in));
String s = in.readLine();
int i = Integer.parseInt(s);
• Kraće je klasom Scanner:
Scanner sc = new Scanner(System.in);
int i = sc.nextInt();
10/20
Klasa Console
• Sistemska konzola:
– Console c = System.console();
• Metode:
– printf("format", promenljive)
– readLine()
– readLine("format", promenljive)
• ispiše promenljive u zadatom formatu, pa učita jedan red
teksta
– readPassword()
• čita šifru sa tastature, bez prikazivanja slova
– readPassword("format", promenljive)
• ispiše promenljive u zadatom formatu, pa učita šifru sa
tastature, bez prikazivanja slova
ConsoleTest.java
11/20
File klasa
• Za manipulaciju datotekama i
direktorijumima:
– kreiranje datoteka i direktorijuma
– brisanje datoteka i direktorijuma
– pristup atributima datoteka i direktorijuma
– modifikacija naziva i atributa datoteka i
direktorijuma
FileTest.java
12/20
File klasa
•
•
•
•
File f = new File(".");
File f = new File("C:\Windows");
f = new File(f, "pera");
f = new File(f, "..");
• if(f.exists()) ...
• if(f.isDirectory()) ...
• f.createNewfile();
13/20
Tokovi (streams) 1/4
• Bazirani na bajtovima
– prenos jednog bajta
– prenos niza bajtova
– rad sa primitivnim tipovima podataka (int,
boolean, float, ...)
14/20
Tokovi (streams) 2/4
• Osmišljeni kao mehanizam koji omogućuje unificiran
pristup podacima
• Isti kôd se koristi za čitanje/pisanje iz, na primer,
datoteke ili mrežne konekcije
• Koncept filtera - donose dodatnu funkcionalnost
tokovima:
– prenos primitivnih tipova na mašinski nezavisan način
(DataInputStream, DataOutputStream)
– baferizovan prenos podataka (BufferedInputStream,
BufferedOutputStream)
FileStreamTest.java
15/20
Tokovi (streams) 3/4
• Metode u tokovima:
– read() – čita jedan bajt iz toka
– read(byte[]) – čita niz bajtova
• vraća pročitan broj bajtova ili -1 ako je stigla do
kraja datoteke
– skip(long n) – preskače zadati broj bajtova
– available() – vraća broj raspoloživih bajtova iz
toka koji se mogu pročitati pre blokiranja
sledećeg čitanja
– close() – zatvara tok
16/20
Tokovi (streams) 4/4
• Primer upotrebe – kopiranje sadržaja datoteke:
byte[] buffer = new byte[BUFFER_LENGTH];
while((read=in.read(buffer, 0,BUFFER_LENGTH)) != -1) {
// obrada učitanog niza bajtova
out.write(buffer);
}
CopyFile.java
17/20
Čitači/pisači (readers/writers) 1/2
• Koriste se za prenos Unicode teksta:
• Čitači/pisači ne zamenjuju tokove – oni ih
dopunjuju
• Čitači/pisači se koriste kada je potrebno
preneti Unicode stringove ili karaktere – u
ostalim situacijama koriste se tokovi
18/20
Čitači/pisači (readers/writers) 2/2
• Metode u čitačima:
–
–
–
–
read() – čita jedan karakter iz toka
read(char[]) – čita niz karaktera
skip(long n) – preskače zadati broj karaktera
close() – zatvara čitač
• Baferizovani čitač (BufferedReader)
– metoda readLine vraća učitan string ili null ako je
stigao do kraja datoteke
• Štampanje stringova u datoteku (PrintWriter)
– metoda println štampa tekst u datoteku
FileReaderWriterTest.java
19/20
Zaključak
• Podaci se u čitaju iz ulaznih tokova, a pišu u
izlazne tokove
• Iz programa se retko radi direktno sa bajtovima
– zato se tokovi ugrađuju u Filter klase koje imaju
odgovarajuće metode za čitanje/pisanje
– zato imamo tokove objekata, tokove primitivnih tipova
itd.
• Ako radimo sa karakterima/stringovima,
koristimo čitače i pisače
20/20
Računarski praktikum
Sortiranje
Sortiranje
• Sortiranje ili uređenje
• Preuređenje niza tako da svi elementi
nakon toga zauzimaju rastući ili opadajući
poredak
• Vreme za sortiranje raste sa brojem
elemenata u nizu
– kvadratno (n2): selection sort, bubble sort, itd.
– logaritamski (n log n): quick sort, merge sort, itd.
2
Kvadratna zavisnost vremena
• Vreme za sortiranje raste sa kvadratom broja
elemenata niza
3
Logaritamska zavisnost vremena
• Vreme za sortiranje raste u skladu sa formulom
n * log(n), gde je n broj elemenata niza
4
Selection sort
• Prolazi se kroz niz i traži se najmanji
element.
• Najmanji element se stavlja na prvo mesto
niza.
• Zatim se prođe kroz preostali niz (od
drugog elementa, pa na dalje) i traži se
najmanji element.
• Ovo se ponavlja dok se ne dođe do kraja
niza.
Select.java
5
Selection sort
• Pronalaženje najmanjeg elementa:
– prvi element se fiksira
– polazi se od drugog, pa do kraja
– traženje najmanjeg elementa se odvija
uzastopnom zamenom ova dva elementa
kada god se ustanovi da je drugi manji od
prvog.
6
Bubble sort
• Porede se dva uzastopna elementa niza i
zamenjuju se ako je drugi manji od prvog.
• Nakon prvog prolaza, na kraju niza je najveći
element.
• Algoritam se ponavlja za preostali deo niza (od
prvog do pretposlednjeg elementa) i na mestu
pretposlednjeg elementa će ostati najveći
element iz tog podniza.
• Algoritam se ponavlja dok ne smanjimo podniz
na prva dva elementa.
Bubble.java
7
SearchB.java
SearchL.java
Pretraga niza
• Tražimo element u nizu
• Razlika između pretrage u uređenom i
neuređenom nizu
– ako je neuređen, nemamo izbora
• prolazimo kroz sve elemente niza dok ne nađemo element ili
stignemo do kraja
– ako je niz uređen, imamo dve mogućnosti:
• prolazimo kroz sve elemente niza dok ne nađemo element ili
stignemo do kraja
• krenemo od sredine niza i proverimo koji je element tu
– ako je traženi element veći od tekućeg, znači da moramo da
tražimo u gornjoj polovini niza
– ako je traženi element manji od tekućeg, znači da moramo da
tražimo donjoj polovini niza
– ponavljamo ovu proceduru za odabranu polovinu niza dok ne
nađemo element, ili dok ne iscrpimo niz
8
Download

Računarski praktikum