SI Wiki - Кориснички доприноси [sr]

Пројектовање софтвера/К2 2021

2021-12-09T16:41:07Z

Mladen Žurkić: /* 3. zadatak */

{{tocright}}
{{rešenja}}

== 1. zadatak ==
Izabrati odgovarajuću sintaksu za sekvenciranje poruka, koja odgovara sledećem opisu:

U toku posmatrane interakcije, u aktivnosti koja sledi na strani prijema 2. poruke dolazi do konkuretnog grananja; u niti B se poziva 1. operacija po redu, koja izaziva aktivnost u kojoj se kao 4. poruka po redu, dok god je uslov <code>x>5</code> ispunjen, pokreće aktivnost iz koje se poziva operacija <code>f()</code> kao 3. po redu.
<div class="abc-list" data-solution="single">
# <span class="solution">2B.1.4*[x>5].3:f()</span>
# 3.1B.4[x>5].2:f()
# 2.B1.4*||[x>5].3:f()
# 2.1B.*[x>5]4.3:f()
# 2.B1.[x>5]*4.3:f()
</div>

== 2. zadatak ==
Povezati načine pristupa drugoj strani konektora kod dijagrama komunikacije sa njihovim ukrasima:
{| class="wikitable"
|+ Opcije
! Pristup
! Ukras
|-
| <div data-solution="select" data-options="a,b,c,d,e,f,g">
* Objektu uloge se pristupa preko primerka asocijacije - veze <span class="spoiler">b</span>
* Objekat uloge je u nekom okružujućem dosegu imena <span class="spoiler">c</span>
* Objekat uloge je argument operacije <span class="spoiler">e</span>
* Objekat uloge je u lokalnom dosegu imena <span class="spoiler">d</span>
* Objekat uloge sam sebi može da šalje poruku <span class="spoiler">f</span>
</div>
| <div class="abc-list">
# argument
# association
# global
# local
# parameter
# self
# this
</div>
|}

== 3. zadatak ==
Kako se na jeziku UML označava sekcija slučaja korišćenja, u kojoj se naznače tačke ponašanja u kojim se dati slučaj korišćenja proširuje drugim slučajevima korišćenja?

Odgovor: <span class="spoiler" data-solution="text">extension points</span>

== 4. zadatak ==
Koje od navedenih tvrdnji su tačne za sledeći dijagram stanja:
[[Датотека:PS K2 2021 zadatak 3.svg|center|frame|Slika uz četvrti zadatak.]]
<div class="abc-list" data-solution="multiple">
# Ovakav automat stanja prihvata kao ispravnu i kompletnu praznu sekvencu znakova.
# Ovakav automat stanja prihvata kao ispravnu i kompletnu sledeću sekvencu znakova: <code>;</code>
# Ovo je primer automata ''Moor''-ovog tipa.
# <span class="solution">Ovakav automat stanja prihvata kao ispravnu i kompletnu sledeću sekvencu znakova: <code><>;</code></span>
# <span class="solution">Ovakav automat stanja prihvata kao ispravnu i kompletnu sledeću sekvencu znakova: <code><a>bbb;</code></span>
# <span class="solution">Ovaj automat radi beskonačno.</span>
</div>

== 5. zadatak ==
Sistem modelovan priloženim dijagramom stanja se pušta u rad. Redom se dešavaju događaji e1, e3, e2. Navesti akcije koje sistem izvršava kao posledicu navedene sekvence događaja, po redosledu izvršavanja. Odgovor (sekvencu akcija) dati navođenjem naziva akcija razdvojenih zapetama, bez razmaka. Primer: ako se redom izvršavaju akcije sa nazivima akcija1, akcija2 i akcija3, odgovor treba dati u formatu "akcija1,akcija2,akcija3" (bez znakova navoda).
[[Датотека:PS K2 2021 zadatak 5.svg|center|frame|Slika uz peti zadatak.]]
Odgovor: <span class="spoiler" data-solution="text">z,z1,z11,t11,f1,z12,t12,t1,t,f3,z,z1,z12,t12,t1,t,f2,x,x1</span>

== 6. zadatak ==
Koje od sledećih tvrdnji su tačne za projektni uzorak ''Iterator'':
<div class="abc-list" data-solution="multiple">
# <span class="solution">Kurzor je naziv specifične vrste iteratora.</span>
# Unutrašnji iterator je fleksibilniji od spoljašnjeg.
# <span class="solution">Kod spoljašnjeg iteratora je na klijentu odgovornost za progres obilaska.</span>
# Agregat ne sme da definiše algoritam obilaska ni za jednu vrstu iteratora.
# Unutrašnji iterator mora posedovati javni metod za dohvatanje tekućeg elementa.
</div>

== 7. zadatak ==
Koje od navedenih tvrdnji su tačne za projektni uzorak ''Stanje'':
<div class="abc-list" data-solution="multiple">
# Predstavlja klasni uzorak ponašanja.
# Mana uzorka je što prelasci između stanja konteksta nisu eksplicitni.
# <span class="solution">Objekti stanja se često realizuju preko projektnog uzorka ''Unikat''.</span>
# <span class="solution">Prilikom promene stanja, spolja izgleda kao da objekat konteksta menja svoju klasu.</span>
# Konkretan objekat stanja ne sme da menja stanje svog konteksta.
</div>

== 8. zadatak ==
Koje od navedenih tvrdnji su tačne za projektni uzorak ''Podsetnik''?
<div class="abc-list" data-solution="multiple">
# <span class="solution">Klasa ''Podsetnik'' ispoljava dva interfejsa - uski prema klasi ''Čuvar'' i široki prema klasi ''Subjekat''.</span>
# ''Čuvar'' proverava i koristi stanje objekta ''Podsetnik''.
# <span class="solution">''Subjekat'' odlučuje u kom trenutku će da sačuva svoje kompletno stanje ili deo stanja.</span>
# <span class="solution">''Subjekat'' kreira objekat ''Podsetnika''.</span>
# Objekat ''Podsetnika'' nema unutrašnje stanje.
</div>

== 9. zadatak ==
Koje od navedenih tvrdnji su tačne za projektni uzorak ''Muva''?
<div class="abc-list" data-solution="multiple">
# Klijenti stvaraju objekte muve njenim kloniranjem ili direktnom konstrukcijom.
# <span class="solution">Objekti deljenih muva mogu biti varijacije ''Unikata'' sa ograničenim brojem objekata.</span>
# <span class="solution">Glavna mana ovog uzorka su potencijalni troškovi pronalaženja ili izračunavanja spoljašnjeg stanja muve.</span>
# Često se kombinuje sa uzorkom ''Sastav'', tako da se formira stablo sa deljenim muvama u čvorovima i nedeljivim muvama u listovima.
# <span class="solution">Koristi se sa ciljem da se izbegne hiperprodukcija objekata.</span>
</div>

== 10. zadatak ==
Koje od navedenih tvrdnji su tačne za projektni uzorak Adapter?
<div class="abc-list" data-solution="multiple">
# Klasa ''Cilj'' predstavlja klasu koju treba adaptirati prema očekivanom interfejsu za klijenta.
# <span class="solution">Objektni uzorak ''Adapter'' treba koristiti kada je potrebno istovremeno adaptirati više potklasa neke klase.</span>
# <span class="solution">Klasa ''Adapter'' sme imati metode koje nisu deo interfejsa ''Cilj''.</span>
# Dvosmerni adapter i klasni i objektni adapter.
# <span class="solution">Klasni uzorak ''Adapter'' dopušta klasi ''Adapter'' da nadjača i tako redefiniše neke metode adaptirane klase.</span>
</div>

[[Категорија:Рокови]]
[[Категорија:Пројектовање софтвера]]

Пројектовање софтвера/К2 2021

2021-12-09T16:40:37Z

Mladen Žurkić: /* 3. zadatak - izbacena slika koja je u sledećem zdtku*/

{{tocright}}
{{rešenja}}

== 1. zadatak ==
Izabrati odgovarajuću sintaksu za sekvenciranje poruka, koja odgovara sledećem opisu:

U toku posmatrane interakcije, u aktivnosti koja sledi na strani prijema 2. poruke dolazi do konkuretnog grananja; u niti B se poziva 1. operacija po redu, koja izaziva aktivnost u kojoj se kao 4. poruka po redu, dok god je uslov <code>x>5</code> ispunjen, pokreće aktivnost iz koje se poziva operacija <code>f()</code> kao 3. po redu.
<div class="abc-list" data-solution="single">
# <span class="solution">2B.1.4*[x>5].3:f()</span>
# 3.1B.4[x>5].2:f()
# 2.B1.4*||[x>5].3:f()
# 2.1B.*[x>5]4.3:f()
# 2.B1.[x>5]*4.3:f()
</div>

== 2. zadatak ==
Povezati načine pristupa drugoj strani konektora kod dijagrama komunikacije sa njihovim ukrasima:
{| class="wikitable"
|+ Opcije
! Pristup
! Ukras
|-
| <div data-solution="select" data-options="a,b,c,d,e,f,g">
* Objektu uloge se pristupa preko primerka asocijacije - veze <span class="spoiler">b</span>
* Objekat uloge je u nekom okružujućem dosegu imena <span class="spoiler">c</span>
* Objekat uloge je argument operacije <span class="spoiler">e</span>
* Objekat uloge je u lokalnom dosegu imena <span class="spoiler">d</span>
* Objekat uloge sam sebi može da šalje poruku <span class="spoiler">f</span>
</div>
| <div class="abc-list">
# argument
# association
# global
# local
# parameter
# self
# this
</div>
|}

== 3. zadatak ==
Kako se na jeziku UML označava sekcija slučaja korišćenja, u kojoj se naznače tačke ponašanja u kojim se dati slučaj korišćenja proširuje drugim slučajevima korišćenja?
Odgovor: <span class="spoiler" data-solution="text">extension points</span>

== 4. zadatak ==
Koje od navedenih tvrdnji su tačne za sledeći dijagram stanja:
[[Датотека:PS K2 2021 zadatak 3.svg|center|frame|Slika uz četvrti zadatak.]]
<div class="abc-list" data-solution="multiple">
# Ovakav automat stanja prihvata kao ispravnu i kompletnu praznu sekvencu znakova.
# Ovakav automat stanja prihvata kao ispravnu i kompletnu sledeću sekvencu znakova: <code>;</code>
# Ovo je primer automata ''Moor''-ovog tipa.
# <span class="solution">Ovakav automat stanja prihvata kao ispravnu i kompletnu sledeću sekvencu znakova: <code><>;</code></span>
# <span class="solution">Ovakav automat stanja prihvata kao ispravnu i kompletnu sledeću sekvencu znakova: <code><a>bbb;</code></span>
# <span class="solution">Ovaj automat radi beskonačno.</span>
</div>

== 5. zadatak ==
Sistem modelovan priloženim dijagramom stanja se pušta u rad. Redom se dešavaju događaji e1, e3, e2. Navesti akcije koje sistem izvršava kao posledicu navedene sekvence događaja, po redosledu izvršavanja. Odgovor (sekvencu akcija) dati navođenjem naziva akcija razdvojenih zapetama, bez razmaka. Primer: ako se redom izvršavaju akcije sa nazivima akcija1, akcija2 i akcija3, odgovor treba dati u formatu "akcija1,akcija2,akcija3" (bez znakova navoda).
[[Датотека:PS K2 2021 zadatak 5.svg|center|frame|Slika uz peti zadatak.]]
Odgovor: <span class="spoiler" data-solution="text">z,z1,z11,t11,f1,z12,t12,t1,t,f3,z,z1,z12,t12,t1,t,f2,x,x1</span>

== 6. zadatak ==
Koje od sledećih tvrdnji su tačne za projektni uzorak ''Iterator'':
<div class="abc-list" data-solution="multiple">
# <span class="solution">Kurzor je naziv specifične vrste iteratora.</span>
# Unutrašnji iterator je fleksibilniji od spoljašnjeg.
# <span class="solution">Kod spoljašnjeg iteratora je na klijentu odgovornost za progres obilaska.</span>
# Agregat ne sme da definiše algoritam obilaska ni za jednu vrstu iteratora.
# Unutrašnji iterator mora posedovati javni metod za dohvatanje tekućeg elementa.
</div>

== 7. zadatak ==
Koje od navedenih tvrdnji su tačne za projektni uzorak ''Stanje'':
<div class="abc-list" data-solution="multiple">
# Predstavlja klasni uzorak ponašanja.
# Mana uzorka je što prelasci između stanja konteksta nisu eksplicitni.
# <span class="solution">Objekti stanja se često realizuju preko projektnog uzorka ''Unikat''.</span>
# <span class="solution">Prilikom promene stanja, spolja izgleda kao da objekat konteksta menja svoju klasu.</span>
# Konkretan objekat stanja ne sme da menja stanje svog konteksta.
</div>

== 8. zadatak ==
Koje od navedenih tvrdnji su tačne za projektni uzorak ''Podsetnik''?
<div class="abc-list" data-solution="multiple">
# <span class="solution">Klasa ''Podsetnik'' ispoljava dva interfejsa - uski prema klasi ''Čuvar'' i široki prema klasi ''Subjekat''.</span>
# ''Čuvar'' proverava i koristi stanje objekta ''Podsetnik''.
# <span class="solution">''Subjekat'' odlučuje u kom trenutku će da sačuva svoje kompletno stanje ili deo stanja.</span>
# <span class="solution">''Subjekat'' kreira objekat ''Podsetnika''.</span>
# Objekat ''Podsetnika'' nema unutrašnje stanje.
</div>

== 9. zadatak ==
Koje od navedenih tvrdnji su tačne za projektni uzorak ''Muva''?
<div class="abc-list" data-solution="multiple">
# Klijenti stvaraju objekte muve njenim kloniranjem ili direktnom konstrukcijom.
# <span class="solution">Objekti deljenih muva mogu biti varijacije ''Unikata'' sa ograničenim brojem objekata.</span>
# <span class="solution">Glavna mana ovog uzorka su potencijalni troškovi pronalaženja ili izračunavanja spoljašnjeg stanja muve.</span>
# Često se kombinuje sa uzorkom ''Sastav'', tako da se formira stablo sa deljenim muvama u čvorovima i nedeljivim muvama u listovima.
# <span class="solution">Koristi se sa ciljem da se izbegne hiperprodukcija objekata.</span>
</div>

== 10. zadatak ==
Koje od navedenih tvrdnji su tačne za projektni uzorak Adapter?
<div class="abc-list" data-solution="multiple">
# Klasa ''Cilj'' predstavlja klasu koju treba adaptirati prema očekivanom interfejsu za klijenta.
# <span class="solution">Objektni uzorak ''Adapter'' treba koristiti kada je potrebno istovremeno adaptirati više potklasa neke klase.</span>
# <span class="solution">Klasa ''Adapter'' sme imati metode koje nisu deo interfejsa ''Cilj''.</span>
# Dvosmerni adapter i klasni i objektni adapter.
# <span class="solution">Klasni uzorak ''Adapter'' dopušta klasi ''Adapter'' da nadjača i tako redefiniše neke metode adaptirane klase.</span>
</div>

[[Категорија:Рокови]]
[[Категорија:Пројектовање софтвера]]

Пројектовање софтвера/К2 2021

2021-12-09T16:40:06Z

Mladen Žurkić: /* 4. zadatak - slika je bila u 3.*/

{{tocright}}
{{rešenja}}

== 1. zadatak ==
Izabrati odgovarajuću sintaksu za sekvenciranje poruka, koja odgovara sledećem opisu:

U toku posmatrane interakcije, u aktivnosti koja sledi na strani prijema 2. poruke dolazi do konkuretnog grananja; u niti B se poziva 1. operacija po redu, koja izaziva aktivnost u kojoj se kao 4. poruka po redu, dok god je uslov <code>x>5</code> ispunjen, pokreće aktivnost iz koje se poziva operacija <code>f()</code> kao 3. po redu.
<div class="abc-list" data-solution="single">
# <span class="solution">2B.1.4*[x>5].3:f()</span>
# 3.1B.4[x>5].2:f()
# 2.B1.4*||[x>5].3:f()
# 2.1B.*[x>5]4.3:f()
# 2.B1.[x>5]*4.3:f()
</div>

== 2. zadatak ==
Povezati načine pristupa drugoj strani konektora kod dijagrama komunikacije sa njihovim ukrasima:
{| class="wikitable"
|+ Opcije
! Pristup
! Ukras
|-
| <div data-solution="select" data-options="a,b,c,d,e,f,g">
* Objektu uloge se pristupa preko primerka asocijacije - veze <span class="spoiler">b</span>
* Objekat uloge je u nekom okružujućem dosegu imena <span class="spoiler">c</span>
* Objekat uloge je argument operacije <span class="spoiler">e</span>
* Objekat uloge je u lokalnom dosegu imena <span class="spoiler">d</span>
* Objekat uloge sam sebi može da šalje poruku <span class="spoiler">f</span>
</div>
| <div class="abc-list">
# argument
# association
# global
# local
# parameter
# self
# this
</div>
|}

== 3. zadatak ==
Kako se na jeziku UML označava sekcija slučaja korišćenja, u kojoj se naznače tačke ponašanja u kojim se dati slučaj korišćenja proširuje drugim slučajevima korišćenja?
[[Датотека:PS K2 2021 zadatak 3.svg|center|frame|Slika uz treći zadatak.]]
Odgovor: <span class="spoiler" data-solution="text">extension points</span>

== 4. zadatak ==
Koje od navedenih tvrdnji su tačne za sledeći dijagram stanja:
[[Датотека:PS K2 2021 zadatak 3.svg|center|frame|Slika uz četvrti zadatak.]]
<div class="abc-list" data-solution="multiple">
# Ovakav automat stanja prihvata kao ispravnu i kompletnu praznu sekvencu znakova.
# Ovakav automat stanja prihvata kao ispravnu i kompletnu sledeću sekvencu znakova: <code>;</code>
# Ovo je primer automata ''Moor''-ovog tipa.
# <span class="solution">Ovakav automat stanja prihvata kao ispravnu i kompletnu sledeću sekvencu znakova: <code><>;</code></span>
# <span class="solution">Ovakav automat stanja prihvata kao ispravnu i kompletnu sledeću sekvencu znakova: <code><a>bbb;</code></span>
# <span class="solution">Ovaj automat radi beskonačno.</span>
</div>

== 5. zadatak ==
Sistem modelovan priloženim dijagramom stanja se pušta u rad. Redom se dešavaju događaji e1, e3, e2. Navesti akcije koje sistem izvršava kao posledicu navedene sekvence događaja, po redosledu izvršavanja. Odgovor (sekvencu akcija) dati navođenjem naziva akcija razdvojenih zapetama, bez razmaka. Primer: ako se redom izvršavaju akcije sa nazivima akcija1, akcija2 i akcija3, odgovor treba dati u formatu "akcija1,akcija2,akcija3" (bez znakova navoda).
[[Датотека:PS K2 2021 zadatak 5.svg|center|frame|Slika uz peti zadatak.]]
Odgovor: <span class="spoiler" data-solution="text">z,z1,z11,t11,f1,z12,t12,t1,t,f3,z,z1,z12,t12,t1,t,f2,x,x1</span>

== 6. zadatak ==
Koje od sledećih tvrdnji su tačne za projektni uzorak ''Iterator'':
<div class="abc-list" data-solution="multiple">
# <span class="solution">Kurzor je naziv specifične vrste iteratora.</span>
# Unutrašnji iterator je fleksibilniji od spoljašnjeg.
# <span class="solution">Kod spoljašnjeg iteratora je na klijentu odgovornost za progres obilaska.</span>
# Agregat ne sme da definiše algoritam obilaska ni za jednu vrstu iteratora.
# Unutrašnji iterator mora posedovati javni metod za dohvatanje tekućeg elementa.
</div>

== 7. zadatak ==
Koje od navedenih tvrdnji su tačne za projektni uzorak ''Stanje'':
<div class="abc-list" data-solution="multiple">
# Predstavlja klasni uzorak ponašanja.
# Mana uzorka je što prelasci između stanja konteksta nisu eksplicitni.
# <span class="solution">Objekti stanja se često realizuju preko projektnog uzorka ''Unikat''.</span>
# <span class="solution">Prilikom promene stanja, spolja izgleda kao da objekat konteksta menja svoju klasu.</span>
# Konkretan objekat stanja ne sme da menja stanje svog konteksta.
</div>

== 8. zadatak ==
Koje od navedenih tvrdnji su tačne za projektni uzorak ''Podsetnik''?
<div class="abc-list" data-solution="multiple">
# <span class="solution">Klasa ''Podsetnik'' ispoljava dva interfejsa - uski prema klasi ''Čuvar'' i široki prema klasi ''Subjekat''.</span>
# ''Čuvar'' proverava i koristi stanje objekta ''Podsetnik''.
# <span class="solution">''Subjekat'' odlučuje u kom trenutku će da sačuva svoje kompletno stanje ili deo stanja.</span>
# <span class="solution">''Subjekat'' kreira objekat ''Podsetnika''.</span>
# Objekat ''Podsetnika'' nema unutrašnje stanje.
</div>

== 9. zadatak ==
Koje od navedenih tvrdnji su tačne za projektni uzorak ''Muva''?
<div class="abc-list" data-solution="multiple">
# Klijenti stvaraju objekte muve njenim kloniranjem ili direktnom konstrukcijom.
# <span class="solution">Objekti deljenih muva mogu biti varijacije ''Unikata'' sa ograničenim brojem objekata.</span>
# <span class="solution">Glavna mana ovog uzorka su potencijalni troškovi pronalaženja ili izračunavanja spoljašnjeg stanja muve.</span>
# Često se kombinuje sa uzorkom ''Sastav'', tako da se formira stablo sa deljenim muvama u čvorovima i nedeljivim muvama u listovima.
# <span class="solution">Koristi se sa ciljem da se izbegne hiperprodukcija objekata.</span>
</div>

== 10. zadatak ==
Koje od navedenih tvrdnji su tačne za projektni uzorak Adapter?
<div class="abc-list" data-solution="multiple">
# Klasa ''Cilj'' predstavlja klasu koju treba adaptirati prema očekivanom interfejsu za klijenta.
# <span class="solution">Objektni uzorak ''Adapter'' treba koristiti kada je potrebno istovremeno adaptirati više potklasa neke klase.</span>
# <span class="solution">Klasa ''Adapter'' sme imati metode koje nisu deo interfejsa ''Cilj''.</span>
# Dvosmerni adapter i klasni i objektni adapter.
# <span class="solution">Klasni uzorak ''Adapter'' dopušta klasi ''Adapter'' da nadjača i tako redefiniše neke metode adaptirane klase.</span>
</div>

[[Категорија:Рокови]]
[[Категорија:Пројектовање софтвера]]

Рачунарске мреже 2/Питања

2021-10-31T19:16:36Z

Mladen Žurkić: /* Pitanje 11 typo*/

{{tocright}}
Ovde su skupljena razna pitanja iz izvora poput RM1 baze pitanja koja se može naći u odeljku sa [[Рачунарске мреже 1#Корисне везе|korisnim vezama]] na stranici predmeta.
{{rešenja}}

== K1 ==
=== Pitanje 1 ===
Ako ruter A sa ulogom ''route reflector''-a dobije rutu od rutera koji je njegov klijent, ruta može da bude prosleđena:
<div class="abc-list" data-solution="multiple">
# <span class="solution">eBGP susedima rutera A</span>
# <span class="solution">klijentima rutera A</span>
# <span class="solution">iBGP susedima koji nisu klijenti A</span>
# nikome
</div>

=== Pitanje 2 ===
''Route reflector'' i njegovi klijenti čine:
<div class="abc-list" data-solution="multiple">
# autonomni sistem
# <span class="solution">klaster</span>
# konfederaciju
# federaciju
</div>

=== Pitanje 3 ===
Internet provajderi su primer:
<div class="abc-list" data-solution="single">
# autonomnog sistema sa jednim izlazom
# autonomnog sistema sa više izlaza bez tranzita saobraćaja
# <span class="solution">autonomnog sistema sa više izlaza i tranzitom saobraćaja</span>
</div>

=== Pitanje 4 ===
''MED'' atribut je:
<div class="abc-list" data-solution="single">
# dobro poznat opcioni atribut
# <span class="solution">opcioni netranzitivni atribut</span>
# opcioni tranzitivni atribut
# dobro poznat obavezan atribut
</div>

=== Pitanje 5 ===
''AS-Set''' atribut pokazuje:
<div class="abc-list" data-solution="single">
# ID rutera koji je agregirao rutu
# <span class="solution">skup autonomnih sistema iz kojih potiču komponente agregirane rute</span>
# da li je data ruta agregirana
</div>

=== Pitanje 6 ===
Za BGP je tačno sledeće:
<div class="abc-list" data-solution="multiple">
# <span class="solution">''Next Hop'' je obavezan atribut u svim BGP Update-ima</span>
# iBGP ima manju administrativnu distancu od eBGP
# <span class="solution">Ruta dobijena putem iBGP-a sme da bude oglašena eBGP susedima</span>
# ''AS-Set'' je obavezan atribut u svim BGP Update-ima
# Koristi ICMP za prenos svojih poruka
# <span class="solution">eBGP ima manju administrativnu distancu od iBGP</span>
</div>

=== Pitanje 7 ===
''Local preference'' atribut:
<div class="abc-list" data-solution="multiple">
# <span class="solution">određuje kako će saobraćaj izlaziti iz datog AS</span>
# se dodeljuje rutama koje izlaze iz datog AS
# određuje kako će saobraćaj ulaziti u dati AS
# <span class="solution">se dodeljuje rutama koje ulaze u dati AS</span>
</div>

=== Pitanje 8 ===
Autonomni sistem AS1 je podeljen u 4 pod-autonomnih sistema koji čine konfederaciju. Svaki pod-AS ima po 3 rutera. Koliko mora da bude iBGP sesija unutar AS1 da bi mreža pravilno funkcionisala?
<div class="abc-list" data-solution="single">
# 4
# 14
# 13
# <span class="solution">15</span>
# 12
</div>

=== Pitanje 9 ===
Autonomni sistem ima 10 rutera. Od toga postoji jedan ''route reflector'' koji ima 7 svojih klijenata. Ostali ruteri su klasični iBGP ruteri. Koliko najmanje mora da postoji iBGP sesija da bi autonomni sistem pravilno funkcionisao?
<div class="abc-list" data-solution="single">
# 7
# 45
# <span class="solution">10</span>
# 12
# 9
</div>

=== Pitanje 10 ===
''Local preference'' atribut se pridružuje rutama koje:
<div class="abc-list" data-solution="single">
# <span class="solution">ulaze u ruter</span>
# izlaze iz rutera
# i ulaze u ruter i izlaze iz rutera
# ništa od navedenog
</div>

=== Pitanje 11 ===
BGP kao kriterijum za izbor najbolje rute koristi sledeće:
<div class="abc-list" data-solution="multiple">
# kašnjenje duž linka
# ''Aggregator'' atribut
# <span class="solution">''Origin'' atribut</span>
# propusni opseg linka
# <span class="solution">vreme dolaska rute u ruter</span>
# ukupan broj rutera na putanji
</div>

=== Pitanje 12 ===
Atribut ''Community'' se koristi za :
<div class="abc-list" data-solution="single">
# <span class="solution">uticanje na rute u udaljenim AS</span>
# informisanje drugih rutera o promenama u ruting tabeli
# sprečavanja petlji u rutiranju
# ništa od navedenog
</div>

=== Pitanje 13 ===
Za BGP je tačno sledeće:
<div class="abc-list" data-solution="multiple">
# Koristi UDP za prenos svojih poruka
# <span class="solution">Koristi TCP za prenos svojih poruka</span>
# BGP metrika je broj rutera na putanji
# iBGP susedi moraju da budu direktno povezani
# <span class="solution">iBGP ruter ne prosleđuje iBGP susedima rutu dobijenu od iBGP suseda</span>
</div>

=== Pitanje 14 ===
Pravilo sinhronizacije unutar AS glasi:
<div class="abc-list" data-solution="single">
# Da bi se neka ruta oglasila eBGP susedu, mora pre toga da bude dobijena od iBGP suseda
# <span class="solution">Da bi se neka ruta oglasila eBGP susedu, mora pre toga da bude oglasena network komandom</span>
# Da bi se neka ruta oglasila eBGP susedu, mora pre toga da bude u ruting tabeli dobijena iz nekog internog protokola rutiranja
# Da bi se neka ruta oglasila eBGP susedu, ne sme da bude dobijena od eBGP suseda
# Da bi se neka ruta oglasila eBGP susedu, ne sme da bude dobijena od iBGP suseda
</div>

=== Pitanje 15 ===
Šta je tačno?
<div class="abc-list" data-solution="multiple">
# Simetričnost saobraćaja označava situaciju gde se saobraćaj šalje naizmenično na dva linka
# <span class="solution">Simetričan saobraćaj je onaj koji u oba smera između dve lokacije putuje istom putanjom</span>
# Simetričnost saobraćaja označava situaciju kada su količine odlaznog i dolaznog saobraćaja iste
# Simetričnost saobraćaja služi za obezbeđenje rezervnih putanja saobraćaja
# Simetričan saobraćaj otežava otkrivanje problema u mreži
# Ništa od navedenog
</div>

=== Pitanje 16 ===
Redosled kriterijuma za izbor najbolje rute u BGP je sledeći:
<div class="abc-list" data-solution="multiple">
# kraći ''AS-Path'', veća ''LP'' vrednost, niža ''MED'' vrednost
# <span class="solution">veća ''LP'' vrednost, kraći ''AS-Path'', niža ''MED'' vrednost</span>
# niža ''MED'' vrednost, kraći ''AS-Path'', veća ''LP'' vrednost
# veća ''LP'' vrednost, kraći ''AS-Path'', viša ''MED'' vrednost
# kraći ''AS-Path'', veća ''LP'' vrednost, niža ''MED'' vrednost
# niža ''MED'' vrednost, veća ''LP'' vrednost, kraći ''AS-Path''
</div>

[[Категорија:Рокови]]
[[Категорија:Рачунарске мреже 2]]

Информациони системи 1

2021-10-21T11:07:33Z

Mladen Žurkić: /* Начин оцењивања - PR уместо P */

{{tocright}}
Информациони системи 1 је обавезан предмет из петог семестра.

== Странице ==
* [https://rti.etf.bg.ac.rs/rti/temp/is1_proba Страница предмета]

== Корисне везе ==
{{Материјали
| vuk = 11oSzQNNsC_pXCYTZirbMi4moyoi-TRqG
}}

== Начин оцењивања ==
* <math>K_1, K_2</math> — Бодови са колоквијума (0-15). '''На сваки колоквијум је могуће изаћи само једном.'''
* <math>L_1</math> — Бодови са прве лабораторијске вежбе (0-8)
* <math>L_2</math> — Бодови са друге лабораторијске вежбе (0-12)
* <math>PR</math> — Бодови са пројекта (0-20)
* <math>I</math> — Бодови са испита (0-30)
* Укупни бодови: <math>P = K_1 + K_2 + L_1 + L_2 + PR + I</math>
{| class="wikitable"
! Бодови
| <math>P \leq 50</math> || <math>50 < P \leq 60</math> || <math>60 < P \leq 70</math> || <math>70 < P \leq 80</math> || <math>80 < P \leq 90</math> || <math>90 < P</math>
|-
! Оцена
| 5 || 6 || 7 || 8 || 9 || 10
|}

=== Рачунање ===
<div class="calculator">
* <math>K_1</math>: <span data-variable="K1" data-max="15"></span>
* <math>K_2</math>: <span data-variable="K2" data-max="15"></span>
* <math>L_1</math>: <span data-variable="L1" data-max="8"></span>
* <math>L_2</math>: <span data-variable="L2" data-max="12"></span>
* <math>PR</math>: <span data-variable="PR" data-max="20"></span>
* <math>I</math>: <span data-variable="I" data-max="30"></span>
* <math>P</math>: <span data-variable="P" data-expression="K1 K2 L1 L2 PR I + + + + +"></span>
* Оцена: <span data-expression="P 10 / ceil 5 max 10 min"></span>
</div>

== Потребна помоћ ==
* {{zadaci|postavke}}

[[Категорија:Пети семестар]]
[[Категорија:Обавезни предмети]]

ОРТ2/Јул 2021

2021-07-06T00:48:31Z

Mladen Žurkić: /* Операциона јединица */

{{tocright}}
{{нерешено}}

== Поставка ==

Посматра се део рачунара који чине меморија и процесор. Меморија је капацитета 2<sup>16</sup> бајтова. Ширина меморијске речи је 1 бајт. Процесор је са једноадресним форматом инструкција.Адресе и подаци су дужине 16 бита и заузимају по две суседне меморијске локације, при чему се старији бајт налази на нижој, а млађи бајт на вишој адреси.

У процесору постоји регистар програмског бројача PC дужине 2 бајта, адресни регистар меморије MAR дужине 2 бајта, прихватни регистар податка меморије MDR дужине 1 бајт, прихватни регистар инструкције IR дужине 4 бајта, акумулатор A дужине 2 бајта, прихватни регистар податка B дужине 2 бајта, регистри опште намене R0 до R31 дужине 2 бајта, програмска статусна реч PSW дужине 1 бајт. Инструкције су дужине 1, 2, 3 или 4 бајта.

Битови 7 и 6 првог бајта инструкције су 11 за све инструкције скока. Код инструкција условног скока битови 5 и 4 првог бајта инструкције су 00, док код инструкција безусловног скока битови 5 и 4 првог бајта инструкције су 11. Инструкција условног скока је инструкција условног скока уколико постоји пренос/позајмица (JC), а инструкције безусловног скока су инструкција безусловног скока (JMP) и инструкција скока на потпрограм (JSR). Битовима 3 до 0 првог бајта инструкције специфира се код операције и на основу тога су за инструкције JC, JMP и JSR усвојени кодови операције 11000000, 11110000 и 11110001, респективно. Инструкције JC, JMP и JSR се реализују као апсолутни скокови, при чему је адреса дата другим и трећим бајтом инструкције. Дужина инструкција је 3 бајта.

Битови 7 и 6 првог бајта инструкције су 00 за све адресне и безадресне инструкције.

Бит 5 првог бајта инструкције је 0 за безадресне инструкције. Безадресне инструкције су инструкције стављања садржаја акумулатора на стек (PUSH), пуњења акумулатора садржајем са стека (POP) и повратка из потпрограма (RTS). Битовима 4 до 0 првог бајта инструкције специфицира се код операције за безадресне инструкције. На основу тога су за инструкције PUSH, POP и RTS усвојени кодови операција 00000000, 00000001 и 00000011, респективно. Дужина инструкција је 1 бајт.

Битови 5 и 4 првог бајта инструкције су 11 за адресне инструкције. Адресне инструкције су инструкција преноса у акумулатор (LD), инструкција преноса из акумулатора (ST), логичка инструкција комплементирања операнда која смешта резултат у акумулатор (NOT), инструкција логичког померања операнда једно место улево која смешта резултат у акумулатор (LSL) и инструкција безусловног скока на срачунату адресу (JADR). Битовима 3 до 0 првог бајта инструкције специфицира се код операције за адресне инструкције. На основу тога су за инструкције LD, ST, NOT, LSL и JADR усвојени кодови операција 00110000, 00110001, 00110010, 00110011 и 00110100 респективно. Дужина инструкција је 2 или 4 бајта и зависи од специфицираног начина адресирања.

Начини адресирања су специфицирани битовима 7, 6 и 5 другог бајта инструкције и то на следећи начин: 000-меморијско директно адресирање (memdir), 001-регистарско директно адресирање (regdir), 010-регистарско индиректно (regind), 011-релативно адресирање са померајем (pcrel), и 100-непосредно адресирање (immed). Код меморијског директног адресирања 16 битна адреса меморијске локације је дата трећим и четвртим бајтом инструкције. Битови 4 до 0 другог бајта инструкције се не користе. Дужина инструкција је 4 бајта. Код регистарског директног и регистарског индиректног адресирања, користи се неки од регистара опште намене R0 до R31 специфицираних битовима од 4 до 0 другог бајта. Дужина инструкција је 2 бајта. Код релативног адресирања са померајем трећи и четврти бајт инструкције садрже 16 битни померај који је дат као целобројна величина без знака. Битови 4 до 0 другог бајта инструкције се не користе. Дужина инструкција је 4 бајта. Код непосредног адресирања 16 битни операнд дат је трећим и четвртим бајтом инструкције. Битови 4 до 0 другог бајта инструкције се не користе. Дужина инструкција је 4 бајта.

Стек расте према вишим меморијским локацијама, а регистар SP указује на прву слободну меморијску локацију. Процесор нема могућност обраде прекида

<strong>1. (К2) (20)</strong>

<div class="abc-list">
# Написати израз за генерисање сигнала gradr који је активан уколико прочитана инструкција има грешку при адресирању.
# Написати изразе за генерисање сигнала свих начина адресирања. IR регистар се попуњава од виших ка нижим битовима.
# Написати изразе за генерисање сигнала операција и то само за JC и NOT.
# Нацртати дијаграм тока фаза формирања адресе и читања операнда и фазе извршавање инструкције.
</div>

<strong>2. (К3) (20)</strong>

<div class="abc-list">
# Пројектовати део операционе јединице процесора која је потребна да се изврши (FETCH, ADDR и EXEC) инструкција <strong>NOT 000Dh</strong>.
# Дати су почетни садржаји регистара и индикатора: PC=1000h, SP=3000h, ACC=0001h, R0=0002h, R1=030Ch, R2=10A2h, R3=FAE3h, N=0, Z=0, V=0 и C=0. Индикатори статусне речи на које инструкција не утиче треба да остану непромењени. Извршити 7 сукцесивних наредби и за сваку наредбу одредити следеће: у фази читања инструкције - меморијске адресе са којих је прочитана инструкција, садржај регистра IR, инструкцију која је прочитана и нови садржај регистра PC; у фази одређивања адресе операнда и читања операнда - меморијске адресе са којих је прочитана адреса операнда, меморијске адресе са којих је прочитан операнд, вредност операнда и нови садржај регистара опште намене који су у овој фази промењени; у фази извршавања операције - меморијске адресе којима се у овој фази приступа, садржај акумулатора A и индикатора N, Z, V и C након извршавања инструкције и нови садржај регистара и меморијских локација који су у овој фази промењени. Резултате представити у табелама 1, 2 и 3 формулара.
</div>
{| class="wikitable"
|+ Садржај дела меморије из поставке задатка
! ЛОКАЦИЈА
| 000A || 000B || 000C || 000D || 000E || 000F || 0010 || 0011 || 0012 || 0013
|-
! ВРЕДНОСТ
| 10 || 01 || 00 || C1 || 21 || 77 || 11 || 00 || 0A || 83
|-
! ЛОКАЦИЈА
| 1000 || 1001 || 1002 || 1003 || 1004 || 1005 || 1006 || 1007 || 1008 || 1009
|-
! ВРЕДНОСТ
| 30 || 20 || F0 || 10 || 06 || 10 || 00 || 31 || 00 || 00
|-
! ЛОКАЦИЈА
| 100A || 100B || 100C || 100D || 100E || 100F || 1010 || 1011 || 1012 || 1013
|-
! ВРЕДНОСТ
| 13 || 32 || 00 || 00 || 13 || C0 || 00 || 10 || 01 || 52
|-
! ЛОКАЦИЈА
| 1014 || 1015 || 1016 || 1017 || 1018 || 1019 || 101A || 101B || 101C || 101D
|-
! ВРЕДНОСТ
| 22 || 41 || F0 || 00 || 03 || E3 || 21 || B8 || 10 || 13
|}

== Решење ==
=== Кодови операција ===
{| class="wikitable"
|-
! colspan="8" | Битови IR31..24
! rowspan="2" | Класа инструкције<br />
|-
| 31
| 30
| 29
| 28
| 27
| 26
| 25
| 24
|-
| 1
| 1
| 0
| 0
| colspan="4" | Код операције<br />
| Условни скок<br />
|-
| 1
| 1
| 1
| 1
| colspan="4" | Код операције<br />
| Безусловни скок
|-
| 0
| 0
| 0
| colspan="5" | Код операције
| Безадресне инструкције
|-
| 0
| 0
| 1
| 1
| colspan="4" | Код операције
| Адресне инструкције
|}

{| class="wikitable"
|-
! colspan="8" | Битови IR31..24
! rowspan="2" | Инструкција<br />
! rowspan="2" | 2. бајт
! rowspan="2" | 3. бајт
! rowspan="2" | 4. бајт
! rowspan="2" | Дужина
|-
| 31
| 30
| 29
| 28
| 27
| 26
| 25
| 24
|-
| colspan="13" style="font-weight:bold;" | Условни скок
|-
| 1
| 1
| 0
| 0
| 0
| 0
| 0
| 0
| JC
| ст.<br />
| мл.
| /
| 3 б
|-
| colspan="13" style="font-weight:bold;" | Безусловни скок
|-
| 1
| 1
| 1
| 1
| 0
| 0
| 0
| 0
| JMP
| ст.<br />
| мл.
| /
| 3 б
|-
| 1
| 1
| 1
| 1
| 0
| 0
| 0
| 1
| JSR
| ст.<br />
| мл.
| /
| 3 б
|-
| colspan="13" style="font-weight:bold;" | Безадресне инструкције
|-
| 0
| 0
| 0
| 0
| 0
| 0
| 0
| 0
| PUSH
| /
| /
| /
| 1 б
|-
| 0
| 0
| 0
| 0
| 0
| 0
| 0
| 1
| POP
| /
| /
| /
| 1 б
|-
| 0
| 0
| 0
| 0
| 0
| 0
| 1
| 1
| RTS
| /
| /
| /
| 1 б
|-
| colspan="13" style="font-weight:bold;" | Адресне инструкције<br />
|-
| 0
| 0
| 1
| 1
| 0
| 0
| 0
| 0
| LD
| Адр.
|
|
|
|-
| 0
| 0
| 1
| 1
| 0
| 0
| 0
| 1
| ST
| Адр.
|
|
|
|-
| 0
| 0
| 1
| 1
| 0
| 0
| 1
| 0
| NOT<br />
| Адр.
|
|
|
|-
| 0
| 0
| 1
| 1
| 0
| 0
| 1
| 1
| LSL
| Адр.
|
|
|
|-
| 0
| 0
| 1
| 1
| 0
| 1
| 0
| 0
| JADR
| Адр.
|
|
|}

{| class="wikitable"
|-
! colspan="8" | Битови IR23..16
! rowspan="2" | Адресирање<br />
! rowspan="2" | 3. бајт
! rowspan="2" | 4. бајт
! rowspan="2" | Дужина
|-
| 23
| 22
| 21
| 20
| 19<br />
| 18<br />
| 17
| 16
|-
| 0
| 0
| 0
| /
| /
| /<br />
| /
| /
| Мем. дир.<br />
| ст.
| мл.
| 4 б
|-
| 0
| 0
| 1<br />
| R<br />
| R
| R
| R
| R
| Рег. дир.
| /
| /
| 2 б
|-
| 0
| 1
| 0
| R<br />
| R
| R
| R
| R
| Рег. инд.
| /
| /
| 2 б
|-
| 0
| 1
| 1
| /
| /<br />
| /<br />
| /
| /
| PC релативно
| ст.<br />
| мл.
| 4 б
|-
| 1
| 0
| 0
| /
| /<br />
| /<br />
| /
| /
| Непосредно<br />
| ст.<br />
| мл.
| 4 б
|}

=== Операциона јединица ===
{{делимично решено}}

=== Меморија ===
{| class="wikitable"
|-
! #<br />
! Адресе у меморији са којих је учитана инструкција
! IR31..24<br />
! IR23..16
! IR15..8
! IR7..0
! Инструкција
! PC
|-
| 1
| 1000, 1001
| 30
| 20
|
|
| LD R0<br />
| 1002
|-
| 2
| 1002, 1003, 1004
| F0
| 10
| 06
|
| JMP 1006h
| 1005
|-
| 3
| 1006
| 00
|
|
|
| PUSH
| 1007
|-
| 4
| 1007, 1008, 1009, 100A
| 31
| 00
| 00
| 13
| ST 0013h
| 100B
|-
| 5
| 100B, 100C, 100D, 100E
| 32
| 00
| 00
| 13
| NOT 0013h
| 100F
|-
| 6
| 100F, 1010, 1011
| C0
| 00
| 10
|
| JC 0010h
| 1012
|-
| 7
| 1012
| 01
|
|
|
| POP
| 1013
|}

{| class="wikitable"
|-
! #<br />
! Адресе у меморији или регистри<br />са којих је учитана адреса операнда
! Адресе у меморији или регистри <br />са којих је учитан операнд
! Операнд
! Нови садржај регистара опште намене<br />
|-
| 1
|
|
| 0002
|
|-
| 2
|
|
|
|
|-
| 3
|
|
|
|
|-
| 4
|
|
|
|
|-
| 5
|
| 0013, 0014
| 0002
|
|-
| 6
|
|
|
|
|-
| 7
|
|
|
|
|}

{| class="wikitable"
|-
! #<br />
! Меморијске адресе којима се <br />приступа у овој фази
! Акумулатор<br />
! N
! Z
! V
! C
! Нови садржај регистара и меморијских локација<br />који су промењени у овој фази
|-
| 1
|
| 0002
| 0
| 0
| 0
| 0
|
|-
| 2
|
| 0002
| 0
| 0
| 0
| 0
| PC = 1006
|-
| 3
| 3000, 3001
| 0002
| 0
| 0
| 0
| 0
| MEM[3000] = 00, MEM[3001] = 02, SP = 3002
|-
| 4
|
| 0002
| 0
| 0
| 0
| 0
| MEM[0013] = 00, MEM[0014] = 02
|-
| 5
|
| FFFD
| 1
| 0
| 0
| 0
|
|-
| 6
|
| FFFD
| 1
| 0
| 0
| 0
|
|-
| 7
| 3001, 3000
| 0002
| 0
| 0
| 0
| 0
| SP = 3000
|}

[[Категорија:ОРТ2]]
[[Категорија:Рокови]]

ОРТ2/Јул 2021

2021-07-06T00:48:24Z

Mladen Žurkić: /* Операциона јединица */

{{tocright}}
{{нерешено}}

== Поставка ==

Посматра се део рачунара који чине меморија и процесор. Меморија је капацитета 2<sup>16</sup> бајтова. Ширина меморијске речи је 1 бајт. Процесор је са једноадресним форматом инструкција.Адресе и подаци су дужине 16 бита и заузимају по две суседне меморијске локације, при чему се старији бајт налази на нижој, а млађи бајт на вишој адреси.

У процесору постоји регистар програмског бројача PC дужине 2 бајта, адресни регистар меморије MAR дужине 2 бајта, прихватни регистар податка меморије MDR дужине 1 бајт, прихватни регистар инструкције IR дужине 4 бајта, акумулатор A дужине 2 бајта, прихватни регистар податка B дужине 2 бајта, регистри опште намене R0 до R31 дужине 2 бајта, програмска статусна реч PSW дужине 1 бајт. Инструкције су дужине 1, 2, 3 или 4 бајта.

Битови 7 и 6 првог бајта инструкције су 11 за све инструкције скока. Код инструкција условног скока битови 5 и 4 првог бајта инструкције су 00, док код инструкција безусловног скока битови 5 и 4 првог бајта инструкције су 11. Инструкција условног скока је инструкција условног скока уколико постоји пренос/позајмица (JC), а инструкције безусловног скока су инструкција безусловног скока (JMP) и инструкција скока на потпрограм (JSR). Битовима 3 до 0 првог бајта инструкције специфира се код операције и на основу тога су за инструкције JC, JMP и JSR усвојени кодови операције 11000000, 11110000 и 11110001, респективно. Инструкције JC, JMP и JSR се реализују као апсолутни скокови, при чему је адреса дата другим и трећим бајтом инструкције. Дужина инструкција је 3 бајта.

Битови 7 и 6 првог бајта инструкције су 00 за све адресне и безадресне инструкције.

Бит 5 првог бајта инструкције је 0 за безадресне инструкције. Безадресне инструкције су инструкције стављања садржаја акумулатора на стек (PUSH), пуњења акумулатора садржајем са стека (POP) и повратка из потпрограма (RTS). Битовима 4 до 0 првог бајта инструкције специфицира се код операције за безадресне инструкције. На основу тога су за инструкције PUSH, POP и RTS усвојени кодови операција 00000000, 00000001 и 00000011, респективно. Дужина инструкција је 1 бајт.

Битови 5 и 4 првог бајта инструкције су 11 за адресне инструкције. Адресне инструкције су инструкција преноса у акумулатор (LD), инструкција преноса из акумулатора (ST), логичка инструкција комплементирања операнда која смешта резултат у акумулатор (NOT), инструкција логичког померања операнда једно место улево која смешта резултат у акумулатор (LSL) и инструкција безусловног скока на срачунату адресу (JADR). Битовима 3 до 0 првог бајта инструкције специфицира се код операције за адресне инструкције. На основу тога су за инструкције LD, ST, NOT, LSL и JADR усвојени кодови операција 00110000, 00110001, 00110010, 00110011 и 00110100 респективно. Дужина инструкција је 2 или 4 бајта и зависи од специфицираног начина адресирања.

Начини адресирања су специфицирани битовима 7, 6 и 5 другог бајта инструкције и то на следећи начин: 000-меморијско директно адресирање (memdir), 001-регистарско директно адресирање (regdir), 010-регистарско индиректно (regind), 011-релативно адресирање са померајем (pcrel), и 100-непосредно адресирање (immed). Код меморијског директног адресирања 16 битна адреса меморијске локације је дата трећим и четвртим бајтом инструкције. Битови 4 до 0 другог бајта инструкције се не користе. Дужина инструкција је 4 бајта. Код регистарског директног и регистарског индиректног адресирања, користи се неки од регистара опште намене R0 до R31 специфицираних битовима од 4 до 0 другог бајта. Дужина инструкција је 2 бајта. Код релативног адресирања са померајем трећи и четврти бајт инструкције садрже 16 битни померај који је дат као целобројна величина без знака. Битови 4 до 0 другог бајта инструкције се не користе. Дужина инструкција је 4 бајта. Код непосредног адресирања 16 битни операнд дат је трећим и четвртим бајтом инструкције. Битови 4 до 0 другог бајта инструкције се не користе. Дужина инструкција је 4 бајта.

Стек расте према вишим меморијским локацијама, а регистар SP указује на прву слободну меморијску локацију. Процесор нема могућност обраде прекида

<strong>1. (К2) (20)</strong>

<div class="abc-list">
# Написати израз за генерисање сигнала gradr који је активан уколико прочитана инструкција има грешку при адресирању.
# Написати изразе за генерисање сигнала свих начина адресирања. IR регистар се попуњава од виших ка нижим битовима.
# Написати изразе за генерисање сигнала операција и то само за JC и NOT.
# Нацртати дијаграм тока фаза формирања адресе и читања операнда и фазе извршавање инструкције.
</div>

<strong>2. (К3) (20)</strong>

<div class="abc-list">
# Пројектовати део операционе јединице процесора која је потребна да се изврши (FETCH, ADDR и EXEC) инструкција <strong>NOT 000Dh</strong>.
# Дати су почетни садржаји регистара и индикатора: PC=1000h, SP=3000h, ACC=0001h, R0=0002h, R1=030Ch, R2=10A2h, R3=FAE3h, N=0, Z=0, V=0 и C=0. Индикатори статусне речи на које инструкција не утиче треба да остану непромењени. Извршити 7 сукцесивних наредби и за сваку наредбу одредити следеће: у фази читања инструкције - меморијске адресе са којих је прочитана инструкција, садржај регистра IR, инструкцију која је прочитана и нови садржај регистра PC; у фази одређивања адресе операнда и читања операнда - меморијске адресе са којих је прочитана адреса операнда, меморијске адресе са којих је прочитан операнд, вредност операнда и нови садржај регистара опште намене који су у овој фази промењени; у фази извршавања операције - меморијске адресе којима се у овој фази приступа, садржај акумулатора A и индикатора N, Z, V и C након извршавања инструкције и нови садржај регистара и меморијских локација који су у овој фази промењени. Резултате представити у табелама 1, 2 и 3 формулара.
</div>
{| class="wikitable"
|+ Садржај дела меморије из поставке задатка
! ЛОКАЦИЈА
| 000A || 000B || 000C || 000D || 000E || 000F || 0010 || 0011 || 0012 || 0013
|-
! ВРЕДНОСТ
| 10 || 01 || 00 || C1 || 21 || 77 || 11 || 00 || 0A || 83
|-
! ЛОКАЦИЈА
| 1000 || 1001 || 1002 || 1003 || 1004 || 1005 || 1006 || 1007 || 1008 || 1009
|-
! ВРЕДНОСТ
| 30 || 20 || F0 || 10 || 06 || 10 || 00 || 31 || 00 || 00
|-
! ЛОКАЦИЈА
| 100A || 100B || 100C || 100D || 100E || 100F || 1010 || 1011 || 1012 || 1013
|-
! ВРЕДНОСТ
| 13 || 32 || 00 || 00 || 13 || C0 || 00 || 10 || 01 || 52
|-
! ЛОКАЦИЈА
| 1014 || 1015 || 1016 || 1017 || 1018 || 1019 || 101A || 101B || 101C || 101D
|-
! ВРЕДНОСТ
| 22 || 41 || F0 || 00 || 03 || E3 || 21 || B8 || 10 || 13
|}

== Решење ==
=== Кодови операција ===
{| class="wikitable"
|-
! colspan="8" | Битови IR31..24
! rowspan="2" | Класа инструкције<br />
|-
| 31
| 30
| 29
| 28
| 27
| 26
| 25
| 24
|-
| 1
| 1
| 0
| 0
| colspan="4" | Код операције<br />
| Условни скок<br />
|-
| 1
| 1
| 1
| 1
| colspan="4" | Код операције<br />
| Безусловни скок
|-
| 0
| 0
| 0
| colspan="5" | Код операције
| Безадресне инструкције
|-
| 0
| 0
| 1
| 1
| colspan="4" | Код операције
| Адресне инструкције
|}

{| class="wikitable"
|-
! colspan="8" | Битови IR31..24
! rowspan="2" | Инструкција<br />
! rowspan="2" | 2. бајт
! rowspan="2" | 3. бајт
! rowspan="2" | 4. бајт
! rowspan="2" | Дужина
|-
| 31
| 30
| 29
| 28
| 27
| 26
| 25
| 24
|-
| colspan="13" style="font-weight:bold;" | Условни скок
|-
| 1
| 1
| 0
| 0
| 0
| 0
| 0
| 0
| JC
| ст.<br />
| мл.
| /
| 3 б
|-
| colspan="13" style="font-weight:bold;" | Безусловни скок
|-
| 1
| 1
| 1
| 1
| 0
| 0
| 0
| 0
| JMP
| ст.<br />
| мл.
| /
| 3 б
|-
| 1
| 1
| 1
| 1
| 0
| 0
| 0
| 1
| JSR
| ст.<br />
| мл.
| /
| 3 б
|-
| colspan="13" style="font-weight:bold;" | Безадресне инструкције
|-
| 0
| 0
| 0
| 0
| 0
| 0
| 0
| 0
| PUSH
| /
| /
| /
| 1 б
|-
| 0
| 0
| 0
| 0
| 0
| 0
| 0
| 1
| POP
| /
| /
| /
| 1 б
|-
| 0
| 0
| 0
| 0
| 0
| 0
| 1
| 1
| RTS
| /
| /
| /
| 1 б
|-
| colspan="13" style="font-weight:bold;" | Адресне инструкције<br />
|-
| 0
| 0
| 1
| 1
| 0
| 0
| 0
| 0
| LD
| Адр.
|
|
|
|-
| 0
| 0
| 1
| 1
| 0
| 0
| 0
| 1
| ST
| Адр.
|
|
|
|-
| 0
| 0
| 1
| 1
| 0
| 0
| 1
| 0
| NOT<br />
| Адр.
|
|
|
|-
| 0
| 0
| 1
| 1
| 0
| 0
| 1
| 1
| LSL
| Адр.
|
|
|
|-
| 0
| 0
| 1
| 1
| 0
| 1
| 0
| 0
| JADR
| Адр.
|
|
|}

{| class="wikitable"
|-
! colspan="8" | Битови IR23..16
! rowspan="2" | Адресирање<br />
! rowspan="2" | 3. бајт
! rowspan="2" | 4. бајт
! rowspan="2" | Дужина
|-
| 23
| 22
| 21
| 20
| 19<br />
| 18<br />
| 17
| 16
|-
| 0
| 0
| 0
| /
| /
| /<br />
| /
| /
| Мем. дир.<br />
| ст.
| мл.
| 4 б
|-
| 0
| 0
| 1<br />
| R<br />
| R
| R
| R
| R
| Рег. дир.
| /
| /
| 2 б
|-
| 0
| 1
| 0
| R<br />
| R
| R
| R
| R
| Рег. инд.
| /
| /
| 2 б
|-
| 0
| 1
| 1
| /
| /<br />
| /<br />
| /
| /
| PC релативно
| ст.<br />
| мл.
| 4 б
|-
| 1
| 0
| 0
| /
| /<br />
| /<br />
| /
| /
| Непосредно<br />
| ст.<br />
| мл.
| 4 б
|}

=== Операциона јединица ===

=== Меморија ===
{| class="wikitable"
|-
! #<br />
! Адресе у меморији са којих је учитана инструкција
! IR31..24<br />
! IR23..16
! IR15..8
! IR7..0
! Инструкција
! PC
|-
| 1
| 1000, 1001
| 30
| 20
|
|
| LD R0<br />
| 1002
|-
| 2
| 1002, 1003, 1004
| F0
| 10
| 06
|
| JMP 1006h
| 1005
|-
| 3
| 1006
| 00
|
|
|
| PUSH
| 1007
|-
| 4
| 1007, 1008, 1009, 100A
| 31
| 00
| 00
| 13
| ST 0013h
| 100B
|-
| 5
| 100B, 100C, 100D, 100E
| 32
| 00
| 00
| 13
| NOT 0013h
| 100F
|-
| 6
| 100F, 1010, 1011
| C0
| 00
| 10
|
| JC 0010h
| 1012
|-
| 7
| 1012
| 01
|
|
|
| POP
| 1013
|}

{| class="wikitable"
|-
! #<br />
! Адресе у меморији или регистри<br />са којих је учитана адреса операнда
! Адресе у меморији или регистри <br />са којих је учитан операнд
! Операнд
! Нови садржај регистара опште намене<br />
|-
| 1
|
|
| 0002
|
|-
| 2
|
|
|
|
|-
| 3
|
|
|
|
|-
| 4
|
|
|
|
|-
| 5
|
| 0013, 0014
| 0002
|
|-
| 6
|
|
|
|
|-
| 7
|
|
|
|
|}

{| class="wikitable"
|-
! #<br />
! Меморијске адресе којима се <br />приступа у овој фази
! Акумулатор<br />
! N
! Z
! V
! C
! Нови садржај регистара и меморијских локација<br />који су промењени у овој фази
|-
| 1
|
| 0002
| 0
| 0
| 0
| 0
|
|-
| 2
|
| 0002
| 0
| 0
| 0
| 0
| PC = 1006
|-
| 3
| 3000, 3001
| 0002
| 0
| 0
| 0
| 0
| MEM[3000] = 00, MEM[3001] = 02, SP = 3002
|-
| 4
|
| 0002
| 0
| 0
| 0
| 0
| MEM[0013] = 00, MEM[0014] = 02
|-
| 5
|
| FFFD
| 1
| 0
| 0
| 0
|
|-
| 6
|
| FFFD
| 1
| 0
| 0
| 0
|
|-
| 7
| 3001, 3000
| 0002
| 0
| 0
| 0
| 0
| SP = 3000
|}

[[Категорија:ОРТ2]]
[[Категорија:Рокови]]

ОРТ2/Јул 2021

2021-07-06T00:46:48Z

Mladen Žurkić: /* Решење - Меморија цела - проверити, чекам рез*/

ОРТ2/Јул 2021

2021-07-06T00:28:10Z

Mladen Žurkić: /* Решење */

{{tocright}}
{{нерешено}}

== Поставка ==

Посматра се део рачунара који чине меморија и процесор. Меморија је капацитета 2<sup>16</sup> бајтова. Ширина меморијске речи је 1 бајт. Процесор је са једноадресним форматом инструкција.Адресе и подаци су дужине 16 бита и заузимају по две суседне меморијске локације, при чему се старији бајт налази на нижој, а млађи бајт на вишој адреси.

У процесору постоји регистар програмског бројача PC дужине 2 бајта, адресни регистар меморије MAR дужине 2 бајта, прихватни регистар податка меморије MDR дужине 1 бајт, прихватни регистар инструкције IR дужине 4 бајта, акумулатор A дужине 2 бајта, прихватни регистар податка B дужине 2 бајта, регистри опште намене R0 до R31 дужине 2 бајта, програмска статусна реч PSW дужине 1 бајт. Инструкције су дужине 1, 2, 3 или 4 бајта.

Битови 7 и 6 првог бајта инструкције су 11 за све инструкције скока. Код инструкција условног скока битови 5 и 4 првог бајта инструкције су 00, док код инструкција безусловног скока битови 5 и 4 првог бајта инструкције су 11. Инструкција условног скока је инструкција условног скока уколико постоји пренос/позајмица (JC), а инструкције безусловног скока су инструкција безусловног скока (JMP) и инструкција скока на потпрограм (JSR). Битовима 3 до 0 првог бајта инструкције специфира се код операције и на основу тога су за инструкције JC, JMP и JSR усвојени кодови операције 11000000, 11110000 и 11110001, респективно. Инструкције JC, JMP и JSR се реализују као апсолутни скокови, при чему је адреса дата другим и трећим бајтом инструкције. Дужина инструкција је 3 бајта.

Битови 7 и 6 првог бајта инструкције су 00 за све адресне и безадресне инструкције.

Бит 5 првог бајта инструкције је 0 за безадресне инструкције. Безадресне инструкције су инструкције стављања садржаја акумулатора на стек (PUSH), пуњења акумулатора садржајем са стека (POP) и повратка из потпрограма (RTS). Битовима 4 до 0 првог бајта инструкције специфицира се код операције за безадресне инструкције. На основу тога су за инструкције PUSH, POP и RTS усвојени кодови операција 00000000, 00000001 и 00000011, респективно. Дужина инструкција је 1 бајт.

Битови 5 и 4 првог бајта инструкције су 11 за адресне инструкције. Адресне инструкције су инструкција преноса у акумулатор (LD), инструкција преноса из акумулатора (ST), логичка инструкција комплементирања операнда која смешта резултат у акумулатор (NOT), инструкција логичког померања операнда једно место улево која смешта резултат у акумулатор (LSL) и инструкција безусловног скока на срачунату адресу (JADR). Битовима 3 до 0 првог бајта инструкције специфицира се код операције за адресне инструкције. На основу тога су за инструкције LD, ST, NOT, LSL и JADR усвојени кодови операција 00110000, 00110001, 00110010, 00110011 и 00110100 респективно. Дужина инструкција је 2 или 4 бајта и зависи од специфицираног начина адресирања.

Начини адресирања су специфицирани битовима 7, 6 и 5 другог бајта инструкције и то на следећи начин: 000-меморијско директно адресирање (memdir), 001-регистарско директно адресирање (regdir), 010-регистарско индиректно (regind), 011-релативно адресирање са померајем (pcrel), и 100-непосредно адресирање (immed). Код меморијског директног адресирања 16 битна адреса меморијске локације је дата трећим и четвртим бајтом инструкције. Битови 4 до 0 другог бајта инструкције се не користе. Дужина инструкција је 4 бајта. Код регистарског директног и регистарског индиректног адресирања, користи се неки од регистара опште намене R0 до R31 специфицираних битовима од 4 до 0 другог бајта. Дужина инструкција је 2 бајта. Код релативног адресирања са померајем трећи и четврти бајт инструкције садрже 16 битни померај који је дат као целобројна величина без знака. Битови 4 до 0 другог бајта инструкције се не користе. Дужина инструкција је 4 бајта. Код непосредног адресирања 16 битни операнд дат је трећим и четвртим бајтом инструкције. Битови 4 до 0 другог бајта инструкције се не користе. Дужина инструкција је 4 бајта.

Стек расте према вишим меморијским локацијама, а регистар SP указује на прву слободну меморијску локацију. Процесор нема могућност обраде прекида

<strong>1. (К2) (20)</strong>

<div class="abc-list">
# Написати израз за генерисање сигнала gradr који је активан уколико прочитана инструкција има грешку при адресирању.
# Написати изразе за генерисање сигнала свих начина адресирања. IR регистар се попуњава од виших ка нижим битовима.
# Написати изразе за генерисање сигнала операција и то само за JC и NOT.
# Нацртати дијаграм тока фаза формирања адресе и читања операнда и фазе извршавање инструкције.
</div>

<strong>2. (К3) (20)</strong>

<div class="abc-list">
# Пројектовати део операционе јединице процесора која је потребна да се изврши (FETCH, ADDR и EXEC) инструкција <strong>NOT 000Dh</strong>.
# Дати су почетни садржаји регистара и индикатора: PC=1000h, SP=3000h, ACC=0001h, R0=0002h, R1=030Ch, R2=10A2h, R3=FAE3h, N=0, Z=0, V=0 и C=0. Индикатори статусне речи на које инструкција не утиче треба да остану непромењени. Извршити 7 сукцесивних наредби и за сваку наредбу одредити следеће: у фази читања инструкције - меморијске адресе са којих је прочитана инструкција, садржај регистра IR, инструкцију која је прочитана и нови садржај регистра PC; у фази одређивања адресе операнда и читања операнда - меморијске адресе са којих је прочитана адреса операнда, меморијске адресе са којих је прочитан операнд, вредност операнда и нови садржај регистара опште намене који су у овој фази промењени; у фази извршавања операције - меморијске адресе којима се у овој фази приступа, садржај акумулатора A и индикатора N, Z, V и C након извршавања инструкције и нови садржај регистара и меморијских локација који су у овој фази промењени. Резултате представити у табелама 1, 2 и 3 формулара.
</div>
{| class="wikitable"
|+ Садржај дела меморије из поставке задатка
! ЛОКАЦИЈА
| 000A || 000B || 000C || 000D || 000E || 000F || 0010 || 0011 || 0012 || 0013
|-
! ВРЕДНОСТ
| 10 || 01 || 00 || C1 || 21 || 77 || 11 || 00 || 0A || 83
|-
! ЛОКАЦИЈА
| 1000 || 1001 || 1002 || 1003 || 1004 || 1005 || 1006 || 1007 || 1008 || 1009
|-
! ВРЕДНОСТ
| 30 || 20 || F0 || 10 || 06 || 10 || 00 || 31 || 00 || 00
|-
! ЛОКАЦИЈА
| 100A || 100B || 100C || 100D || 100E || 100F || 1010 || 1011 || 1012 || 1013
|-
! ВРЕДНОСТ
| 13 || 32 || 00 || 00 || 13 || C0 || 00 || 10 || 01 || 52
|-
! ЛОКАЦИЈА
| 1014 || 1015 || 1016 || 1017 || 1018 || 1019 || 101A || 101B || 101C || 101D
|-
! ВРЕДНОСТ
| 22 || 41 || F0 || 00 || 03 || E3 || 21 || B8 || 10 || 13
|}

== Решење ==
=== Кодови операција ===
{| class="wikitable"
|-
! colspan="8" | Битови IR31..24
! rowspan="2" | Класа инструкције<br />
|-
| 31
| 30
| 29
| 28
| 27
| 26
| 25
| 24
|-
| 1
| 1
| 0
| 0
| colspan="4" | Код операције<br />
| Условни скок<br />
|-
| 1
| 1
| 1
| 1
| colspan="4" | Код операције<br />
| Безусловни скок
|-
| 0
| 0
| 0
| colspan="5" | Код операције
| Безадресне инструкције
|-
| 0
| 0
| 1
| 1
| colspan="4" | Код операције
| Адресне инструкције
|}

{| class="wikitable"
|-
! colspan="8" | Битови IR31..24
! rowspan="2" | Инструкција<br />
! rowspan="2" | 2. бајт
! rowspan="2" | 3. бајт
! rowspan="2" | 4. бајт
! rowspan="2" | Дужина
|-
| 31
| 30
| 29
| 28
| 27
| 26
| 25
| 24
|-
| colspan="13" style="font-weight:bold;" | Условни скок
|-
| 1
| 1
| 0
| 0
| 0
| 0
| 0
| 0
| JC
| ст.<br />
| мл.
| /
| 3 б
|-
| colspan="13" style="font-weight:bold;" | Безусловни скок
|-
| 1
| 1
| 1
| 1
| 0
| 0
| 0
| 0
| JMP
| ст.<br />
| мл.
| /
| 3 б
|-
| 1
| 1
| 1
| 1
| 0
| 0
| 0
| 1
| JSR
| ст.<br />
| мл.
| /
| 3 б
|-
| colspan="13" style="font-weight:bold;" | Безадресне инструкције
|-
| 0
| 0
| 0
| 0
| 0
| 0
| 0
| 0
| PUSH
| /
| /
| /
| 1 б
|-
| 0
| 0
| 0
| 0
| 0
| 0
| 0
| 1
| POP
| /
| /
| /
| 1 б
|-
| 0
| 0
| 0
| 0
| 0
| 0
| 1
| 1
| RTS
| /
| /
| /
| 1 б
|-
| colspan="13" style="font-weight:bold;" | Адресне инструкције<br />
|-
| 0
| 0
| 1
| 1
| 0
| 0
| 0
| 0
| LD
| Адр.
|
|
|
|-
| 0
| 0
| 1
| 1
| 0
| 0
| 0
| 1
| ST
| Адр.
|
|
|
|-
| 0
| 0
| 1
| 1
| 0
| 0
| 1
| 0
| NOT<br />
| Адр.
|
|
|
|-
| 0
| 0
| 1
| 1
| 0
| 0
| 1
| 1
| LSL
| Адр.
|
|
|
|-
| 0
| 0
| 1
| 1
| 0
| 1
| 0
| 0
| JADR
| Адр.
|
|
|}

{| class="wikitable"
|-
! colspan="8" | Битови IR23..16
! rowspan="2" | Адресирање<br />
! rowspan="2" | 3. бајт
! rowspan="2" | 4. бајт
! rowspan="2" | Дужина
|-
| 23
| 22
| 21
| 20
| 19<br />
| 18<br />
| 17
| 16
|-
| 0
| 0
| 0
| /
| /
| /<br />
| /
| /
| Мем. дир.<br />
| ст.
| мл.
| 4 б
|-
| 0
| 0
| 1<br />
| R<br />
| R
| R
| R
| R
| Рег. дир.
| /
| /
| 2 б
|-
| 0
| 1
| 0
| R<br />
| R
| R
| R
| R
| Рег. инд.
| /
| /
| 2 б
|-
| 0
| 1
| 1
| /
| /<br />
| /<br />
| /
| /
| PC релативно
| ст.<br />
| мл.
| 4 б
|-
| 1
| 0
| 0
| /
| /<br />
| /<br />
| /
| /
| Непосредно<br />
| ст.<br />
| мл.
| 4 б
|}

[[Категорија:ОРТ2]]
[[Категорија:Рокови]]

ОРТ2/Јул 2021

2021-07-06T00:25:45Z

Mladen Žurkić: /* Решење - Кодови операција - табела*/

{{tocright}}
{{нерешено}}

== Поставка ==

Посматра се део рачунара који чине меморија и процесор. Меморија је капацитета 2<sup>16</sup> бајтова. Ширина меморијске речи је 1 бајт. Процесор је са једноадресним форматом инструкција.Адресе и подаци су дужине 16 бита и заузимају по две суседне меморијске локације, при чему се старији бајт налази на нижој, а млађи бајт на вишој адреси.

У процесору постоји регистар програмског бројача PC дужине 2 бајта, адресни регистар меморије MAR дужине 2 бајта, прихватни регистар податка меморије MDR дужине 1 бајт, прихватни регистар инструкције IR дужине 4 бајта, акумулатор A дужине 2 бајта, прихватни регистар податка B дужине 2 бајта, регистри опште намене R0 до R31 дужине 2 бајта, програмска статусна реч PSW дужине 1 бајт. Инструкције су дужине 1, 2, 3 или 4 бајта.

Битови 7 и 6 првог бајта инструкције су 11 за све инструкције скока. Код инструкција условног скока битови 5 и 4 првог бајта инструкције су 00, док код инструкција безусловног скока битови 5 и 4 првог бајта инструкције су 11. Инструкција условног скока је инструкција условног скока уколико постоји пренос/позајмица (JC), а инструкције безусловног скока су инструкција безусловног скока (JMP) и инструкција скока на потпрограм (JSR). Битовима 3 до 0 првог бајта инструкције специфира се код операције и на основу тога су за инструкције JC, JMP и JSR усвојени кодови операције 11000000, 11110000 и 11110001, респективно. Инструкције JC, JMP и JSR се реализују као апсолутни скокови, при чему је адреса дата другим и трећим бајтом инструкције. Дужина инструкција је 3 бајта.

Битови 7 и 6 првог бајта инструкције су 00 за све адресне и безадресне инструкције.

Бит 5 првог бајта инструкције је 0 за безадресне инструкције. Безадресне инструкције су инструкције стављања садржаја акумулатора на стек (PUSH), пуњења акумулатора садржајем са стека (POP) и повратка из потпрограма (RTS). Битовима 4 до 0 првог бајта инструкције специфицира се код операције за безадресне инструкције. На основу тога су за инструкције PUSH, POP и RTS усвојени кодови операција 00000000, 00000001 и 00000011, респективно. Дужина инструкција је 1 бајт.

Битови 5 и 4 првог бајта инструкције су 11 за адресне инструкције. Адресне инструкције су инструкција преноса у акумулатор (LD), инструкција преноса из акумулатора (ST), логичка инструкција комплементирања операнда која смешта резултат у акумулатор (NOT), инструкција логичког померања операнда једно место улево која смешта резултат у акумулатор (LSL) и инструкција безусловног скока на срачунату адресу (JADR). Битовима 3 до 0 првог бајта инструкције специфицира се код операције за адресне инструкције. На основу тога су за инструкције LD, ST, NOT, LSL и JADR усвојени кодови операција 00110000, 00110001, 00110010, 00110011 и 00110100 респективно. Дужина инструкција је 2 или 4 бајта и зависи од специфицираног начина адресирања.

Начини адресирања су специфицирани битовима 7, 6 и 5 другог бајта инструкције и то на следећи начин: 000-меморијско директно адресирање (memdir), 001-регистарско директно адресирање (regdir), 010-регистарско индиректно (regind), 011-релативно адресирање са померајем (pcrel), и 100-непосредно адресирање (immed). Код меморијског директног адресирања 16 битна адреса меморијске локације је дата трећим и четвртим бајтом инструкције. Битови 4 до 0 другог бајта инструкције се не користе. Дужина инструкција је 4 бајта. Код регистарског директног и регистарског индиректног адресирања, користи се неки од регистара опште намене R0 до R31 специфицираних битовима од 4 до 0 другог бајта. Дужина инструкција је 2 бајта. Код релативног адресирања са померајем трећи и четврти бајт инструкције садрже 16 битни померај који је дат као целобројна величина без знака. Битови 4 до 0 другог бајта инструкције се не користе. Дужина инструкција је 4 бајта. Код непосредног адресирања 16 битни операнд дат је трећим и четвртим бајтом инструкције. Битови 4 до 0 другог бајта инструкције се не користе. Дужина инструкција је 4 бајта.

Стек расте према вишим меморијским локацијама, а регистар SP указује на прву слободну меморијску локацију. Процесор нема могућност обраде прекида

<strong>1. (К2) (20)</strong>

<div class="abc-list">
# Написати израз за генерисање сигнала gradr који је активан уколико прочитана инструкција има грешку при адресирању.
# Написати изразе за генерисање сигнала свих начина адресирања. IR регистар се попуњава од виших ка нижим битовима.
# Написати изразе за генерисање сигнала операција и то само за JC и NOT.
# Нацртати дијаграм тока фаза формирања адресе и читања операнда и фазе извршавање инструкције.
</div>

<strong>2. (К3) (20)</strong>

<div class="abc-list">
# Пројектовати део операционе јединице процесора која је потребна да се изврши (FETCH, ADDR и EXEC) инструкција <strong>NOT 000Dh</strong>.
# Дати су почетни садржаји регистара и индикатора: PC=1000h, SP=3000h, ACC=0001h, R0=0002h, R1=030Ch, R2=10A2h, R3=FAE3h, N=0, Z=0, V=0 и C=0. Индикатори статусне речи на које инструкција не утиче треба да остану непромењени. Извршити 7 сукцесивних наредби и за сваку наредбу одредити следеће: у фази читања инструкције - меморијске адресе са којих је прочитана инструкција, садржај регистра IR, инструкцију која је прочитана и нови садржај регистра PC; у фази одређивања адресе операнда и читања операнда - меморијске адресе са којих је прочитана адреса операнда, меморијске адресе са којих је прочитан операнд, вредност операнда и нови садржај регистара опште намене који су у овој фази промењени; у фази извршавања операције - меморијске адресе којима се у овој фази приступа, садржај акумулатора A и индикатора N, Z, V и C након извршавања инструкције и нови садржај регистара и меморијских локација који су у овој фази промењени. Резултате представити у табелама 1, 2 и 3 формулара.
</div>
{| class="wikitable"
|+ Садржај дела меморије из поставке задатка
! ЛОКАЦИЈА
| 000A || 000B || 000C || 000D || 000E || 000F || 0010 || 0011 || 0012 || 0013
|-
! ВРЕДНОСТ
| 10 || 01 || 00 || C1 || 21 || 77 || 11 || 00 || 0A || 83
|-
! ЛОКАЦИЈА
| 1000 || 1001 || 1002 || 1003 || 1004 || 1005 || 1006 || 1007 || 1008 || 1009
|-
! ВРЕДНОСТ
| 30 || 20 || F0 || 10 || 06 || 10 || 00 || 31 || 00 || 00
|-
! ЛОКАЦИЈА
| 100A || 100B || 100C || 100D || 100E || 100F || 1010 || 1011 || 1012 || 1013
|-
! ВРЕДНОСТ
| 13 || 32 || 00 || 00 || 13 || C0 || 00 || 10 || 01 || 52
|-
! ЛОКАЦИЈА
| 1014 || 1015 || 1016 || 1017 || 1018 || 1019 || 101A || 101B || 101C || 101D
|-
! ВРЕДНОСТ
| 22 || 41 || F0 || 00 || 03 || E3 || 21 || B8 || 10 || 13
|}

== Решење ==
== Решење ==
=== Кодови операција ===
{| class="wikitable"
|-
! colspan="8" | Битови IR31..24
! rowspan="2" | Класа инструкције<br />
|-
| 31
| 30
| 29
| 28
| 27
| 26
| 25
| 24
|-
| 1
| 1
| 0
| 0
| colspan="4" | Код операције<br />
| Условни скок<br />
|-
| 1
| 1
| 1
| 1
| colspan="4" | Код операције<br />
| Безусловни скок
|-
| 0
| 0
| 0
| colspan="5" | Код операције
| Безадресне инструкције
|-
| 0
| 0
| 1
| 1
| colspan="4" | Код операције
| Адресне инструкције
|}

{| class="wikitable"
|-
! colspan="8" | Битови IR31..24
! rowspan="2" | Инструкција<br />
! rowspan="2" | 2. бајт
! rowspan="2" | 3. бајт
! rowspan="2" | 4. бајт
! rowspan="2" | Дужина
|-
| 31
| 30
| 29
| 28
| 27
| 26
| 25
| 24
|-
| colspan="13" style="font-weight:bold;" | Условни скок
|-
| 1
| 1
| 0
| 0
| 0
| 0
| 0
| 0
| JC
| ст.<br />
| мл.
| /
| 3 б
|-
| colspan="13" style="font-weight:bold;" | Безусловни скок
|-
| 1
| 1
| 1
| 1
| 0
| 0
| 0
| 0
| JMP
| ст.<br />
| мл.
| /
| 3 б
|-
| 1
| 1
| 1
| 1
| 0
| 0
| 0
| 1
| JSR
| ст.<br />
| мл.
| /
| 3 б
|-
| colspan="13" style="font-weight:bold;" | Безадресне инструкције
|-
| 0
| 0
| 0
| 0
| 0
| 0
| 0
| 0
| PUSH
| /
| /
| /
| 1 б
|-
| 0
| 0
| 0
| 0
| 0
| 0
| 0
| 1
| POP
| /
| /
| /
| 1 б
|-
| 0
| 0
| 0
| 0
| 0
| 0
| 1
| 1
| RTS
| /
| /
| /
| 1 б
|-
| colspan="13" style="font-weight:bold;" | Адресне инструкције<br />
|-
| 0
| 0
| 1
| 1
| 0
| 0
| 0
| 0
| LD
| Адр.
|
|
|
|-
| 0
| 0
| 1
| 1
| 0
| 0
| 0
| 1
| ST
| Адр.
|
|
|
|-
| 0
| 0
| 1
| 1
| 0
| 0
| 1
| 0
| NOT<br />
| Адр.
|
|
|
|-
| 0
| 0
| 1
| 1
| 0
| 0
| 1
| 1
| LSL
| Адр.
|
|
|
|-
| 0
| 0
| 1
| 1
| 0
| 1
| 0
| 0
| JADR
| Адр.
|
|
|}

{| class="wikitable"
|-
! colspan="8" | Битови IR23..16
! rowspan="2" | Адресирање<br />
! rowspan="2" | 3. бајт
! rowspan="2" | 4. бајт
! rowspan="2" | Дужина
|-
| 23
| 22
| 21
| 20
| 19<br />
| 18<br />
| 17
| 16
|-
| 0
| 0
| 0
| /
| /
| /<br />
| /
| /
| Мем. дир.<br />
| ст.
| мл.
| 4 б
|-
| 0
| 0
| 1<br />
| R<br />
| R
| R
| R
| R
| Рег. дир.
| /
| /
| 2 б
|-
| 0
| 1
| 0
| R<br />
| R
| R
| R
| R
| Рег. инд.
| /
| /
| 2 б
|-
| 0
| 1
| 1
| /
| /<br />
| /<br />
| /
| /
| PC релативно
| ст.<br />
| мл.
| 4 б
|-
| 1
| 0
| 0
| /
| /<br />
| /<br />
| /
| /
| Непосредно<br />
| ст.<br />
| мл.
| 4 б
|}

[[Категорија:ОРТ2]]
[[Категорија:Рокови]]

ОРТ2/К3 2021

2021-07-06T00:03:36Z

Mladen Žurkić: /* Меморија */

{{tocright}}

== Поставка ==
Посматра се део рачунара који чине меморија и процесор. Меморија је капацитета 2<sup>16</sup> бајтова. Ширина меморијске речи је 1 бајт. Процесор је са једноадресним форматом инструкција. Адресе и подаци су дужине 16 бита и заузимају по две суседне меморијске локације, при чему се старији бајт налази на нижој, а млађи бајт на вишој адреси.

У процесору постоји регистар програмског бројача PC дужине 2 бајта, адресни регистар меморије MAR дужине 2 бајта, прихватни регистар податка меморије MDR дужине 1 бајт, прихватни регистар инструкције IR дужине 4 бајта, акумулатор A дужине 2 бајта, прихватни регистар податка B дужине 2 бајта, регистри опште намене R0 до R15 дужине 2 бајта, програмска статусна реч PSW дужине 1 бајт. Инструкције су дужине 1, 2, 3 или 4 бајта.

Бит 7 првог бајта инструкције је 0 за све инструкције скока. Код инструкција условног скока бит 6 првог бајта инструкције је 0, док код инструкција безусловног скока бит 6 првог бајта инструкције је 1. Инструкција условног скока је инструкција условног скока уколико резултат није нула (JNZ), а инструкције безусловног скока су инструкција безусловног скока (JMP). Битовима 5 до 0 првог бајта инструкције специфицира се код операције и на основу тога су за инструкције JNZ и JMP усвојени кодови операције 00000000 и 01000000, респективно. Инструкције JNZ и JMP се реализују као апсолутни скокови, при чему је адреса дата другим и трећим бајтом инструкције. Дужина инструкција је 3 бајта.

Бит 7 првог бајта инструкције је 1 за све адресне и безадресне инструкције.

Битови 6 и 5 првог бајта инструкције су 01 за безадресне инструкције. Безадресне инструкције су инструкције стављања садржаја акумулатора на стек (PUSH), пуњења акумулатора садржајем са стека (POP) и декрементирање акумулатора (DEC). Битовима 4 до 0 првог бајта инструкције специфицира се код операције за безадресне инструкције. На основу тога су за инструкције PUSH, POP и DEC усвојени кодови операција 10100000, 10100001 и 10100010, респективно. Дужина инструкција је 1 бајт.

Битови 6 и 5 првог бајта инструкције су 11 за адресне инструкције. Адресне инструкције су инструкција преноса у акумулатор (LD), инструкција преноса из акумулатора (ST), логичка инструкција "или" (OR), инструкција ротирања операнда једно место удесно која смешта резултат у акумулатор (ROR), инструкција безусловног скока на срачунату адресу (JADR), инструкција сабирања (ADD) и инструкција одузимања (SUB). Битовима 4 до 0 првог бајта инструкције специфицира се код операције за адресне инструкције. На основу тога су за инструкције LD, ST, OR, ROR, JADR, ADD и SUB усвојени кодови операција 11100000, 11100001, 11100010, 11100011, 11100100, 11100101 и 11100110 респективно. Дужина инструкција је 2 или 4 бајта и зависи од специфицираног начина адресирања.

Начини адресирања су специфицирани битовима 7, 6 и 5 другог бајта инструкције и то на следећи начин: 000-меморијско директно адресирање (memdir), 001-регистарско индиректно адресирање (regind), 010-регистарско директно адресирање (regdir), 011-релативно адресирање са померајем (pcrel), 100-непосредно адресирање (immed) и 101-регистарско индиректно са померајем адресирање (regindpom). Код меморијског директног адресирања 16 битна адреса меморијске локације је дата трећим и четвртим бајтом инструкције. Битови 4 до 0 другог бајта инструкције се не користе. Дужина инструкција је 4 бајта. Регистарско индиректно адресирање користи неке од регистара опште намене R0 до R15 специфициране битовима од 3 до 0 другог бајта. Бит 4 другог бајта инструкције се не користи. Дужина инструкција је 2 бајта. Регистарско директно адресирање користи неке од регистара опште намене R0 до R15 специфициране битовима од 3 до 0 другог бајта. Бит 4 другог бајта инструкције се не користи. Дужина инструкција је 2 бајта. Код релативног адресирања са померајем трећи и четврти бајт инструкције садрже 16 битни померај који је дат као целобројна величина са знаком. Битови 4 до 0 другог бајта инструкције се не користе. Дужина инструкција је 4 бајта. Код непосредног адресирања 16 битни операнд дат је трећим и четвртим бајтом инструкције. Битови 4 до 0 другог бајта инструкције се не користе. Дужина инструкција је 4 бајта. Код регистарског индиректног адресирања са померајем трећи и четврти бајт инструкције садрже 16 битни померај који је дат као целобројна величина са знаком. Један од регистара опште намене R0 до R15 који се користи специфициран је битовима од 3 до 0 другог бајта инструкције. Бит 4 другог бајта инструкције се не користи. Дужина инструкција је 4 бајта.

Стек расте према вишим меморијским локацијама, а регистар SP указује на последњу заузету меморијску локацију. Процесор нема могућност обраде прекида.

<div class="abc-list">
# Пројектовати део операционе јединице процесора која је потребна да се изврши (FETCH + ADDR + EXEC) инструкција '''JADR (1234h)'''.
# Дати су почетни садржаји регистара и индикатора: PC=1000h, SP=2000h, ACC = 0002h, R0=00F2h, R1=000Ch, R2=00A2h, R3=FFE3h, N=0, Z=0, V=0 и C=0. Индикатори статусне речи на које инструкције не утиче треба да остану непромењени. Извршити 7 сукцесивних наредби и за сваку наредбу одредити следеће: у фази читања инструкције - меморијске адресе са којих је прочитана инструкција, садржај регистра IR, инструкцију која је прочитана и нови садржај регистра PC; у фази одређивања адресе операнда и читања операнда - меморијске адресе са којих је прочитана адреса операнда, меморијске адресе са којих је прочитан операнд, вредност операнда и нови садржај регистара опште намене који су у овој фази промењени; у фази извршавања операције - меморијске адресе којима се у овој фази приступа, садржај акумулатора A и индикатора N, Z, V и C након извршавања инструкције и нови садржај регистара и меморијских локација који су у овој фази промењени. Резултате представити у табелама 1, 2 и 3 формулара.
</div>
{| class="wikitable"
|+ Садржај дела меморије из поставке задатка
! ЛОКАЦИЈА
| 000A || 000B || 000C || 000D || 000E || 000F || 0010 || 0011 || 0012 || 0013
|-
! ВРЕДНОСТ
| 10 || 01 || 00 || C1 || 21 || 77 || 11 || 00 || 0A || 83
|-
! ЛОКАЦИЈА
| 1000 || 1001 || 1002 || 1003 || 1004 || 1005 || 1006 || 1007 || 1008 || 1009
|-
! ВРЕДНОСТ
| E0 || 00 || 00 || 0A || 00 || 10 || 09 || 10 || E8 || A2
|-
! ЛОКАЦИЈА
| 100A || 100B || 100C || 100D || 100E || 100F || 1010 || 1011 || 1012 || 1013
|-
! ВРЕДНОСТ
| E2 || 60 || 00 || 08 || A0 || 40 || 10 || 19 || 00 || 52
|-
! ЛОКАЦИЈА
| 1014 || 1015 || 1016 || 1017 || 1018 || 1019 || 101A || 101B || 101C || 101D
|-
! ВРЕДНОСТ
| 21 || 41 || F0 || 00 || 03 || E3 || 21 || B8 || 10 || 13
|}

== Решење ==
=== Кодови операција ===
{| class="wikitable"
|-
! colspan="8" | Битови IR31..24
! rowspan="2" | Класа инструкције<br />
|-
| 31
| 30
| 29
| 28
| 27
| 26
| 25
| 24
|-
| 0
| 0
| colspan="6" | Код операције<br />
| Условни скок<br />
|-
| 0
| 1
| colspan="6" | Код операције<br />
| Безусловни скок
|-
| 1
| 0
| 1
| colspan="5" | Код операције
| Безадресне инструкције
|-
| 1
| 1
| 1
| colspan="5" | Код операције
| Адресне инструкције
|}

{| class="wikitable"
|-
! colspan="8" | Битови IR31..24
! rowspan="2" | Инструкција<br />
! rowspan="2" | 2. бајт
! rowspan="2" | 3. бајт
! rowspan="2" | 4. бајт
! rowspan="2" | Дужина
|-
| 31
| 30
| 29
| 28
| 27
| 26
| 25
| 24
|-
| colspan="13" style="font-weight:bold;" | Условни скок
|-
| 0
| 0
| 0
| 0
| 0
| 0
| 0
| 0
| JNZ
| ст.<br />
| мл.
| /
| 3 б
|-
| colspan="13" style="font-weight:bold;" | Безусловни скок
|-
| 0
| 1
| 0
| 0
| 0
| 0
| 0
| 0
| JMP
| ст.<br />
| мл.
| /
| 3 б
|-
| colspan="13" style="font-weight:bold;" | Безадресне инструкције
|-
| 1
| 0
| 1
| 0
| 0
| 0
| 0
| 0
| PUSH
| /
| /
| /
| 1 б
|-
| 1
| 0
| 1
| 0
| 0
| 0
| 0
| 1
| POP
| /
| /
| /
| 1 б
|-
| 1
| 0
| 1
| 0
| 0
| 0
| 1
| 0
| DEC
| /
| /
| /
| 1 б
|-
| colspan="13" style="font-weight:bold;" | Адресне инструкције<br />
|-
| 1
| 1
| 1
| 0
| 0
| 0
| 0
| 0
| LD
| Адр.
|
|
|
|-
| 1
| 1
| 1
| 0
| 0
| 0
| 0
| 1
| ST
| Адр.
|
|
|
|-
| 1
| 1
| 1
| 0
| 0
| 0
| 1
| 0
| OR<br />
| Адр.
|
|
|
|-
| 1
| 1
| 1
| 0
| 0
| 0
| 1
| 1
| ROR
| Адр.
|
|
|
|-
| 1
| 1
| 1
| 0
| 0
| 1
| 0
| 0
| JADR
| Адр.
|
|
|
|-
| 1
| 1
| 1
| 0
| 0
| 1
| 0
| 1
| ADD
| Адр.
|
|
|
|-
| 1
| 1
| 1
| 0
| 0
| 1
| 1
| 0<br />
| SUB
| Адр.
|
|
|
|}

{| class="wikitable"
|-
! colspan="8" | Битови IR23..16
! rowspan="2" | Адресирање<br />
! rowspan="2" | 3. бајт
! rowspan="2" | 4. бајт
! rowspan="2" | Дужина
|-
| 23
| 22
| 21
| 20
| 19<br />
| 18<br />
| 17
| 16
|-
| 0
| 0
| 0
| /
| /
| /<br />
| /
| /
| Мем. дир.<br />
| ст.
| мл.
| 4 б
|-
| 0
| 0
| 1<br />
| R<br />
| R
| R
| R
| R
| Рег. инд.
| /
| /
| 2 б
|-
| 0
| 1
| 0
| R<br />
| R
| R
| R
| R
| Рег. дир.
| /
| /
| 2 б
|-
| 0
| 1
| 1
| /
| /<br />
| /<br />
| /
| /
| PC релативно
| ст.<br />
| мл.
| 4 б
|-
| 1
| 0
| 0
| /
| /<br />
| /<br />
| /
| /
| Непосредно<br />
| ст.<br />
| мл.
| 4 б
|-
| 1
| 0
| 1
| R<br />
| R
| R
| R
| R
| Рег. инд. са пом.
| ст.<br />
| мл.
| 4 б
|}

=== Операциона јединица ===
{{делимично решено}}

=== Меморија ===
{| class="wikitable"
|-
! #<br />
! Адресе у меморији са којих је учитана инструкција
! IR31..24<br />
! IR23..16
! IR15..8
! IR7..0
! Инструкција
! PC
|-
| 1
| 1000, 1001, 1002, 1003
| E0
| 00
| 00
| 0A
| LD 000Ah<br />
| 1004
|-
| 2
| 1004, 1005, 1006
| 00
| 10
| 09
|
| JNZ 1009h
| 1007
|-
| 3
| 1009
| A2
|
|
|
| DEC
| 100A
|-
| 4
| 100A, 100B, 100C, 100D
| E2
| 60
| 00
| 08
| OR (PC+08h)
| 100E
|-
| 5
| 100E
| A0
|
|
|
| PUSH
| 100F
|-
| 6
| 100F, 1010, 1011
| 40
| 10
| 19
|
| JMP 1019h
| 1012
|-
| 7
| 1019, 101A
| E3
| 21
|
|
| ROR (R1)
| 101B
|}

{| class="wikitable"
|-
! #<br />
! Адресе у меморији или регистри<br />са којих је учитана адреса операнда
! Адресе у меморији или регистри <br />са којих је учитан операнд
! Операнд
! Нови садржај регистара опште намене<br />
|-
| 1
|
| 000A, 000B
| 1001
|
|-
| 2
|
|
|
|
|-
| 3
|
|
|
|
|-
| 4
|
| 1017, 1018
| 0003
|
|-
| 5
|
|
|
|
|-
| 6
|
|
|
|
|-
| 7
|
| 000C, 000D
| 00C1
|
|}

{| class="wikitable"
|-
! #<br />
! Меморијске адресе којима се <br />приступа у овој фази
! Акумулатор<br />
! N
! Z
! V
! C
! Нови садржај регистара и меморијских локација<br />који су промењени у овој фази
|-
| 1
|
| 1001
| 0
| 0
| 0
| 0
|
|-
| 2
|
| 1001
| 0
| 0
| 0
| 0
| PC = 1009
|-
| 3
|
| 1000
| 0
| 0
| 0
| 0
|
|-
| 4
|
| 1003
| 0
| 0
| 0
| 0
|
|-
| 5
| 2001, 2002
| 1003
| 0
| 0
| 0
| 0
| MEM[2001] = 10, MEM[2002] = 03
|-
| 6
|
| 1003
| 0
| 0
| 0
| 0
| PC = 1019
|-
| 7
|
| 8060
| 1
| 0
| 1
| 0
|
|}

[[Категорија:ОРТ2]]
[[Категорија:Рокови]]

ОРТ2/К3 2021

2021-07-06T00:01:25Z

Mladen Žurkić: /* Меморија - трећа фаза - табела*/

{{tocright}}

== Поставка ==
Посматра се део рачунара који чине меморија и процесор. Меморија је капацитета 2<sup>16</sup> бајтова. Ширина меморијске речи је 1 бајт. Процесор је са једноадресним форматом инструкција. Адресе и подаци су дужине 16 бита и заузимају по две суседне меморијске локације, при чему се старији бајт налази на нижој, а млађи бајт на вишој адреси.

У процесору постоји регистар програмског бројача PC дужине 2 бајта, адресни регистар меморије MAR дужине 2 бајта, прихватни регистар податка меморије MDR дужине 1 бајт, прихватни регистар инструкције IR дужине 4 бајта, акумулатор A дужине 2 бајта, прихватни регистар податка B дужине 2 бајта, регистри опште намене R0 до R15 дужине 2 бајта, програмска статусна реч PSW дужине 1 бајт. Инструкције су дужине 1, 2, 3 или 4 бајта.

Бит 7 првог бајта инструкције је 0 за све инструкције скока. Код инструкција условног скока бит 6 првог бајта инструкције је 0, док код инструкција безусловног скока бит 6 првог бајта инструкције је 1. Инструкција условног скока је инструкција условног скока уколико резултат није нула (JNZ), а инструкције безусловног скока су инструкција безусловног скока (JMP). Битовима 5 до 0 првог бајта инструкције специфицира се код операције и на основу тога су за инструкције JNZ и JMP усвојени кодови операције 00000000 и 01000000, респективно. Инструкције JNZ и JMP се реализују као апсолутни скокови, при чему је адреса дата другим и трећим бајтом инструкције. Дужина инструкција је 3 бајта.

Бит 7 првог бајта инструкције је 1 за све адресне и безадресне инструкције.

Битови 6 и 5 првог бајта инструкције су 01 за безадресне инструкције. Безадресне инструкције су инструкције стављања садржаја акумулатора на стек (PUSH), пуњења акумулатора садржајем са стека (POP) и декрементирање акумулатора (DEC). Битовима 4 до 0 првог бајта инструкције специфицира се код операције за безадресне инструкције. На основу тога су за инструкције PUSH, POP и DEC усвојени кодови операција 10100000, 10100001 и 10100010, респективно. Дужина инструкција је 1 бајт.

Битови 6 и 5 првог бајта инструкције су 11 за адресне инструкције. Адресне инструкције су инструкција преноса у акумулатор (LD), инструкција преноса из акумулатора (ST), логичка инструкција "или" (OR), инструкција ротирања операнда једно место удесно која смешта резултат у акумулатор (ROR), инструкција безусловног скока на срачунату адресу (JADR), инструкција сабирања (ADD) и инструкција одузимања (SUB). Битовима 4 до 0 првог бајта инструкције специфицира се код операције за адресне инструкције. На основу тога су за инструкције LD, ST, OR, ROR, JADR, ADD и SUB усвојени кодови операција 11100000, 11100001, 11100010, 11100011, 11100100, 11100101 и 11100110 респективно. Дужина инструкција је 2 или 4 бајта и зависи од специфицираног начина адресирања.

Начини адресирања су специфицирани битовима 7, 6 и 5 другог бајта инструкције и то на следећи начин: 000-меморијско директно адресирање (memdir), 001-регистарско индиректно адресирање (regind), 010-регистарско директно адресирање (regdir), 011-релативно адресирање са померајем (pcrel), 100-непосредно адресирање (immed) и 101-регистарско индиректно са померајем адресирање (regindpom). Код меморијског директног адресирања 16 битна адреса меморијске локације је дата трећим и четвртим бајтом инструкције. Битови 4 до 0 другог бајта инструкције се не користе. Дужина инструкција је 4 бајта. Регистарско индиректно адресирање користи неке од регистара опште намене R0 до R15 специфициране битовима од 3 до 0 другог бајта. Бит 4 другог бајта инструкције се не користи. Дужина инструкција је 2 бајта. Регистарско директно адресирање користи неке од регистара опште намене R0 до R15 специфициране битовима од 3 до 0 другог бајта. Бит 4 другог бајта инструкције се не користи. Дужина инструкција је 2 бајта. Код релативног адресирања са померајем трећи и четврти бајт инструкције садрже 16 битни померај који је дат као целобројна величина са знаком. Битови 4 до 0 другог бајта инструкције се не користе. Дужина инструкција је 4 бајта. Код непосредног адресирања 16 битни операнд дат је трећим и четвртим бајтом инструкције. Битови 4 до 0 другог бајта инструкције се не користе. Дужина инструкција је 4 бајта. Код регистарског индиректног адресирања са померајем трећи и четврти бајт инструкције садрже 16 битни померај који је дат као целобројна величина са знаком. Један од регистара опште намене R0 до R15 који се користи специфициран је битовима од 3 до 0 другог бајта инструкције. Бит 4 другог бајта инструкције се не користи. Дужина инструкција је 4 бајта.

Стек расте према вишим меморијским локацијама, а регистар SP указује на последњу заузету меморијску локацију. Процесор нема могућност обраде прекида.

<div class="abc-list">
# Пројектовати део операционе јединице процесора која је потребна да се изврши (FETCH + ADDR + EXEC) инструкција '''JADR (1234h)'''.
# Дати су почетни садржаји регистара и индикатора: PC=1000h, SP=2000h, ACC = 0002h, R0=00F2h, R1=000Ch, R2=00A2h, R3=FFE3h, N=0, Z=0, V=0 и C=0. Индикатори статусне речи на које инструкције не утиче треба да остану непромењени. Извршити 7 сукцесивних наредби и за сваку наредбу одредити следеће: у фази читања инструкције - меморијске адресе са којих је прочитана инструкција, садржај регистра IR, инструкцију која је прочитана и нови садржај регистра PC; у фази одређивања адресе операнда и читања операнда - меморијске адресе са којих је прочитана адреса операнда, меморијске адресе са којих је прочитан операнд, вредност операнда и нови садржај регистара опште намене који су у овој фази промењени; у фази извршавања операције - меморијске адресе којима се у овој фази приступа, садржај акумулатора A и индикатора N, Z, V и C након извршавања инструкције и нови садржај регистара и меморијских локација који су у овој фази промењени. Резултате представити у табелама 1, 2 и 3 формулара.
</div>
{| class="wikitable"
|+ Садржај дела меморије из поставке задатка
! ЛОКАЦИЈА
| 000A || 000B || 000C || 000D || 000E || 000F || 0010 || 0011 || 0012 || 0013
|-
! ВРЕДНОСТ
| 10 || 01 || 00 || C1 || 21 || 77 || 11 || 00 || 0A || 83
|-
! ЛОКАЦИЈА
| 1000 || 1001 || 1002 || 1003 || 1004 || 1005 || 1006 || 1007 || 1008 || 1009
|-
! ВРЕДНОСТ
| E0 || 00 || 00 || 0A || 00 || 10 || 09 || 10 || E8 || A2
|-
! ЛОКАЦИЈА
| 100A || 100B || 100C || 100D || 100E || 100F || 1010 || 1011 || 1012 || 1013
|-
! ВРЕДНОСТ
| E2 || 60 || 00 || 08 || A0 || 40 || 10 || 19 || 00 || 52
|-
! ЛОКАЦИЈА
| 1014 || 1015 || 1016 || 1017 || 1018 || 1019 || 101A || 101B || 101C || 101D
|-
! ВРЕДНОСТ
| 21 || 41 || F0 || 00 || 03 || E3 || 21 || B8 || 10 || 13
|}

== Решење ==
=== Кодови операција ===
{| class="wikitable"
|-
! colspan="8" | Битови IR31..24
! rowspan="2" | Класа инструкције<br />
|-
| 31
| 30
| 29
| 28
| 27
| 26
| 25
| 24
|-
| 0
| 0
| colspan="6" | Код операције<br />
| Условни скок<br />
|-
| 0
| 1
| colspan="6" | Код операције<br />
| Безусловни скок
|-
| 1
| 0
| 1
| colspan="5" | Код операције
| Безадресне инструкције
|-
| 1
| 1
| 1
| colspan="5" | Код операције
| Адресне инструкције
|}

{| class="wikitable"
|-
! colspan="8" | Битови IR31..24
! rowspan="2" | Инструкција<br />
! rowspan="2" | 2. бајт
! rowspan="2" | 3. бајт
! rowspan="2" | 4. бајт
! rowspan="2" | Дужина
|-
| 31
| 30
| 29
| 28
| 27
| 26
| 25
| 24
|-
| colspan="13" style="font-weight:bold;" | Условни скок
|-
| 0
| 0
| 0
| 0
| 0
| 0
| 0
| 0
| JNZ
| ст.<br />
| мл.
| /
| 3 б
|-
| colspan="13" style="font-weight:bold;" | Безусловни скок
|-
| 0
| 1
| 0
| 0
| 0
| 0
| 0
| 0
| JMP
| ст.<br />
| мл.
| /
| 3 б
|-
| colspan="13" style="font-weight:bold;" | Безадресне инструкције
|-
| 1
| 0
| 1
| 0
| 0
| 0
| 0
| 0
| PUSH
| /
| /
| /
| 1 б
|-
| 1
| 0
| 1
| 0
| 0
| 0
| 0
| 1
| POP
| /
| /
| /
| 1 б
|-
| 1
| 0
| 1
| 0
| 0
| 0
| 1
| 0
| DEC
| /
| /
| /
| 1 б
|-
| colspan="13" style="font-weight:bold;" | Адресне инструкције<br />
|-
| 1
| 1
| 1
| 0
| 0
| 0
| 0
| 0
| LD
| Адр.
|
|
|
|-
| 1
| 1
| 1
| 0
| 0
| 0
| 0
| 1
| ST
| Адр.
|
|
|
|-
| 1
| 1
| 1
| 0
| 0
| 0
| 1
| 0
| OR<br />
| Адр.
|
|
|
|-
| 1
| 1
| 1
| 0
| 0
| 0
| 1
| 1
| ROR
| Адр.
|
|
|
|-
| 1
| 1
| 1
| 0
| 0
| 1
| 0
| 0
| JADR
| Адр.
|
|
|
|-
| 1
| 1
| 1
| 0
| 0
| 1
| 0
| 1
| ADD
| Адр.
|
|
|
|-
| 1
| 1
| 1
| 0
| 0
| 1
| 1
| 0<br />
| SUB
| Адр.
|
|
|
|}

{| class="wikitable"
|-
! colspan="8" | Битови IR23..16
! rowspan="2" | Адресирање<br />
! rowspan="2" | 3. бајт
! rowspan="2" | 4. бајт
! rowspan="2" | Дужина
|-
| 23
| 22
| 21
| 20
| 19<br />
| 18<br />
| 17
| 16
|-
| 0
| 0
| 0
| /
| /
| /<br />
| /
| /
| Мем. дир.<br />
| ст.
| мл.
| 4 б
|-
| 0
| 0
| 1<br />
| R<br />
| R
| R
| R
| R
| Рег. инд.
| /
| /
| 2 б
|-
| 0
| 1
| 0
| R<br />
| R
| R
| R
| R
| Рег. дир.
| /
| /
| 2 б
|-
| 0
| 1
| 1
| /
| /<br />
| /<br />
| /
| /
| PC релативно
| ст.<br />
| мл.
| 4 б
|-
| 1
| 0
| 0
| /
| /<br />
| /<br />
| /
| /
| Непосредно<br />
| ст.<br />
| мл.
| 4 б
|-
| 1
| 0
| 1
| R<br />
| R
| R
| R
| R
| Рег. инд. са пом.
| ст.<br />
| мл.
| 4 б
|}

=== Операциона јединица ===
{{делимично решено}}

=== Меморија ===
{{делимично решено}}
{| class="wikitable"
|-
! #<br />
! Адресе у меморији са којих је учитана инструкција
! IR31..24<br />
! IR23..16
! IR15..8
! IR7..0
! Инструкција
! PC
|-
| 1
| 1000, 1001, 1002, 1003
| E0
| 00
| 00
| 0A
| LD 000Ah<br />
| 1004
|-
| 2
| 1004, 1005, 1006
| 00
| 10
| 09
|
| JNZ 1009h
| 1007
|-
| 3
| 1009
| A2
|
|
|
| DEC
| 100A
|-
| 4
| 100A, 100B, 100C, 100D
| E2
| 60
| 00
| 08
| OR (PC+08h)
| 100E
|-
| 5
| 100E
| A0
|
|
|
| PUSH
| 100F
|-
| 6
| 100F, 1010, 1011
| 40
| 10
| 19
|
| JMP 1019h
| 1012
|-
| 7
| 1019, 101A
| E3
| 21
|
|
| ROR (R1)
| 101B
|}

{| class="wikitable"
|-
! #<br />
! Адресе у меморији или регистри<br />са којих је учитана адреса операнда
! Адресе у меморији или регистри <br />са којих је учитан операнд
! Операнд
! Нови садржај регистара опште намене<br />
|-
| 1
|
| 000A, 000B
| 1001
|
|-
| 2
|
|
|
|
|-
| 3
|
|
|
|
|-
| 4
|
| 1017, 1018
| 0003
|
|-
| 5
|
|
|
|
|-
| 6
|
|
|
|
|-
| 7
|
| 000C, 000D
| 00C1
|
|}

{| class="wikitable"
|-
! #<br />
! Меморијске адресе којима се <br />приступа у овој фази
! Акумулатор<br />
! N
! Z
! V
! C
! Нови садржај регистара и меморијских локација<br />који су промењени у овој фази
|-
| 1
|
| 1001
| 0
| 0
| 0
| 0
|
|-
| 2
|
| 1001
| 0
| 0
| 0
| 0
| PC = 1009
|-
| 3
|
| 1000
| 0
| 0
| 0
| 0
|
|-
| 4
|
| 1003
| 0
| 0
| 0
| 0
|
|-
| 5
| 2001, 2002
| 1003
| 0
| 0
| 0
| 0
| MEM[2001] = 10, MEM[2002] = 03
|-
| 6
|
| 1003
| 0
| 0
| 0
| 0
| PC = 1019
|-
| 7
|
| 8060
| 1
| 0
| 1
| 0
|
|}

[[Категорија:ОРТ2]]
[[Категорија:Рокови]]

ОРТ2/К3 2021

2021-07-05T23:47:56Z

Mladen Žurkić: /* Меморија - фаза одређивања адресе операнда и читања операнда*/

{{tocright}}

== Поставка ==
Посматра се део рачунара који чине меморија и процесор. Меморија је капацитета 2<sup>16</sup> бајтова. Ширина меморијске речи је 1 бајт. Процесор је са једноадресним форматом инструкција. Адресе и подаци су дужине 16 бита и заузимају по две суседне меморијске локације, при чему се старији бајт налази на нижој, а млађи бајт на вишој адреси.

У процесору постоји регистар програмског бројача PC дужине 2 бајта, адресни регистар меморије MAR дужине 2 бајта, прихватни регистар податка меморије MDR дужине 1 бајт, прихватни регистар инструкције IR дужине 4 бајта, акумулатор A дужине 2 бајта, прихватни регистар податка B дужине 2 бајта, регистри опште намене R0 до R15 дужине 2 бајта, програмска статусна реч PSW дужине 1 бајт. Инструкције су дужине 1, 2, 3 или 4 бајта.

Бит 7 првог бајта инструкције је 0 за све инструкције скока. Код инструкција условног скока бит 6 првог бајта инструкције је 0, док код инструкција безусловног скока бит 6 првог бајта инструкције је 1. Инструкција условног скока је инструкција условног скока уколико резултат није нула (JNZ), а инструкције безусловног скока су инструкција безусловног скока (JMP). Битовима 5 до 0 првог бајта инструкције специфицира се код операције и на основу тога су за инструкције JNZ и JMP усвојени кодови операције 00000000 и 01000000, респективно. Инструкције JNZ и JMP се реализују као апсолутни скокови, при чему је адреса дата другим и трећим бајтом инструкције. Дужина инструкција је 3 бајта.

Бит 7 првог бајта инструкције је 1 за све адресне и безадресне инструкције.

Битови 6 и 5 првог бајта инструкције су 01 за безадресне инструкције. Безадресне инструкције су инструкције стављања садржаја акумулатора на стек (PUSH), пуњења акумулатора садржајем са стека (POP) и декрементирање акумулатора (DEC). Битовима 4 до 0 првог бајта инструкције специфицира се код операције за безадресне инструкције. На основу тога су за инструкције PUSH, POP и DEC усвојени кодови операција 10100000, 10100001 и 10100010, респективно. Дужина инструкција је 1 бајт.

Битови 6 и 5 првог бајта инструкције су 11 за адресне инструкције. Адресне инструкције су инструкција преноса у акумулатор (LD), инструкција преноса из акумулатора (ST), логичка инструкција "или" (OR), инструкција ротирања операнда једно место удесно која смешта резултат у акумулатор (ROR), инструкција безусловног скока на срачунату адресу (JADR), инструкција сабирања (ADD) и инструкција одузимања (SUB). Битовима 4 до 0 првог бајта инструкције специфицира се код операције за адресне инструкције. На основу тога су за инструкције LD, ST, OR, ROR, JADR, ADD и SUB усвојени кодови операција 11100000, 11100001, 11100010, 11100011, 11100100, 11100101 и 11100110 респективно. Дужина инструкција је 2 или 4 бајта и зависи од специфицираног начина адресирања.

Начини адресирања су специфицирани битовима 7, 6 и 5 другог бајта инструкције и то на следећи начин: 000-меморијско директно адресирање (memdir), 001-регистарско индиректно адресирање (regind), 010-регистарско директно адресирање (regdir), 011-релативно адресирање са померајем (pcrel), 100-непосредно адресирање (immed) и 101-регистарско индиректно са померајем адресирање (regindpom). Код меморијског директног адресирања 16 битна адреса меморијске локације је дата трећим и четвртим бајтом инструкције. Битови 4 до 0 другог бајта инструкције се не користе. Дужина инструкција је 4 бајта. Регистарско индиректно адресирање користи неке од регистара опште намене R0 до R15 специфициране битовима од 3 до 0 другог бајта. Бит 4 другог бајта инструкције се не користи. Дужина инструкција је 2 бајта. Регистарско директно адресирање користи неке од регистара опште намене R0 до R15 специфициране битовима од 3 до 0 другог бајта. Бит 4 другог бајта инструкције се не користи. Дужина инструкција је 2 бајта. Код релативног адресирања са померајем трећи и четврти бајт инструкције садрже 16 битни померај који је дат као целобројна величина са знаком. Битови 4 до 0 другог бајта инструкције се не користе. Дужина инструкција је 4 бајта. Код непосредног адресирања 16 битни операнд дат је трећим и четвртим бајтом инструкције. Битови 4 до 0 другог бајта инструкције се не користе. Дужина инструкција је 4 бајта. Код регистарског индиректног адресирања са померајем трећи и четврти бајт инструкције садрже 16 битни померај који је дат као целобројна величина са знаком. Један од регистара опште намене R0 до R15 који се користи специфициран је битовима од 3 до 0 другог бајта инструкције. Бит 4 другог бајта инструкције се не користи. Дужина инструкција је 4 бајта.

Стек расте према вишим меморијским локацијама, а регистар SP указује на последњу заузету меморијску локацију. Процесор нема могућност обраде прекида.

<div class="abc-list">
# Пројектовати део операционе јединице процесора која је потребна да се изврши (FETCH + ADDR + EXEC) инструкција '''JADR (1234h)'''.
# Дати су почетни садржаји регистара и индикатора: PC=1000h, SP=2000h, ACC = 0002h, R0=00F2h, R1=000Ch, R2=00A2h, R3=FFE3h, N=0, Z=0, V=0 и C=0. Индикатори статусне речи на које инструкције не утиче треба да остану непромењени. Извршити 7 сукцесивних наредби и за сваку наредбу одредити следеће: у фази читања инструкције - меморијске адресе са којих је прочитана инструкција, садржај регистра IR, инструкцију која је прочитана и нови садржај регистра PC; у фази одређивања адресе операнда и читања операнда - меморијске адресе са којих је прочитана адреса операнда, меморијске адресе са којих је прочитан операнд, вредност операнда и нови садржај регистара опште намене који су у овој фази промењени; у фази извршавања операције - меморијске адресе којима се у овој фази приступа, садржај акумулатора A и индикатора N, Z, V и C након извршавања инструкције и нови садржај регистара и меморијских локација који су у овој фази промењени. Резултате представити у табелама 1, 2 и 3 формулара.
</div>
{| class="wikitable"
|+ Садржај дела меморије из поставке задатка
! ЛОКАЦИЈА
| 000A || 000B || 000C || 000D || 000E || 000F || 0010 || 0011 || 0012 || 0013
|-
! ВРЕДНОСТ
| 10 || 01 || 00 || C1 || 21 || 77 || 11 || 00 || 0A || 83
|-
! ЛОКАЦИЈА
| 1000 || 1001 || 1002 || 1003 || 1004 || 1005 || 1006 || 1007 || 1008 || 1009
|-
! ВРЕДНОСТ
| E0 || 00 || 00 || 0A || 00 || 10 || 09 || 10 || E8 || A2
|-
! ЛОКАЦИЈА
| 100A || 100B || 100C || 100D || 100E || 100F || 1010 || 1011 || 1012 || 1013
|-
! ВРЕДНОСТ
| E2 || 60 || 00 || 08 || A0 || 40 || 10 || 19 || 00 || 52
|-
! ЛОКАЦИЈА
| 1014 || 1015 || 1016 || 1017 || 1018 || 1019 || 101A || 101B || 101C || 101D
|-
! ВРЕДНОСТ
| 21 || 41 || F0 || 00 || 03 || E3 || 21 || B8 || 10 || 13
|}

== Решење ==
=== Кодови операција ===
{| class="wikitable"
|-
! colspan="8" | Битови IR31..24
! rowspan="2" | Класа инструкције<br />
|-
| 31
| 30
| 29
| 28
| 27
| 26
| 25
| 24
|-
| 0
| 0
| colspan="6" | Код операције<br />
| Условни скок<br />
|-
| 0
| 1
| colspan="6" | Код операције<br />
| Безусловни скок
|-
| 1
| 0
| 1
| colspan="5" | Код операције
| Безадресне инструкције
|-
| 1
| 1
| 1
| colspan="5" | Код операције
| Адресне инструкције
|}

{| class="wikitable"
|-
! colspan="8" | Битови IR31..24
! rowspan="2" | Инструкција<br />
! rowspan="2" | 2. бајт
! rowspan="2" | 3. бајт
! rowspan="2" | 4. бајт
! rowspan="2" | Дужина
|-
| 31
| 30
| 29
| 28
| 27
| 26
| 25
| 24
|-
| colspan="13" style="font-weight:bold;" | Условни скок
|-
| 0
| 0
| 0
| 0
| 0
| 0
| 0
| 0
| JNZ
| ст.<br />
| мл.
| /
| 3 б
|-
| colspan="13" style="font-weight:bold;" | Безусловни скок
|-
| 0
| 1
| 0
| 0
| 0
| 0
| 0
| 0
| JMP
| ст.<br />
| мл.
| /
| 3 б
|-
| colspan="13" style="font-weight:bold;" | Безадресне инструкције
|-
| 1
| 0
| 1
| 0
| 0
| 0
| 0
| 0
| PUSH
| /
| /
| /
| 1 б
|-
| 1
| 0
| 1
| 0
| 0
| 0
| 0
| 1
| POP
| /
| /
| /
| 1 б
|-
| 1
| 0
| 1
| 0
| 0
| 0
| 1
| 0
| DEC
| /
| /
| /
| 1 б
|-
| colspan="13" style="font-weight:bold;" | Адресне инструкције<br />
|-
| 1
| 1
| 1
| 0
| 0
| 0
| 0
| 0
| LD
| Адр.
|
|
|
|-
| 1
| 1
| 1
| 0
| 0
| 0
| 0
| 1
| ST
| Адр.
|
|
|
|-
| 1
| 1
| 1
| 0
| 0
| 0
| 1
| 0
| OR<br />
| Адр.
|
|
|
|-
| 1
| 1
| 1
| 0
| 0
| 0
| 1
| 1
| ROR
| Адр.
|
|
|
|-
| 1
| 1
| 1
| 0
| 0
| 1
| 0
| 0
| JADR
| Адр.
|
|
|
|-
| 1
| 1
| 1
| 0
| 0
| 1
| 0
| 1
| ADD
| Адр.
|
|
|
|-
| 1
| 1
| 1
| 0
| 0
| 1
| 1
| 0<br />
| SUB
| Адр.
|
|
|
|}

{| class="wikitable"
|-
! colspan="8" | Битови IR23..16
! rowspan="2" | Адресирање<br />
! rowspan="2" | 3. бајт
! rowspan="2" | 4. бајт
! rowspan="2" | Дужина
|-
| 23
| 22
| 21
| 20
| 19<br />
| 18<br />
| 17
| 16
|-
| 0
| 0
| 0
| /
| /
| /<br />
| /
| /
| Мем. дир.<br />
| ст.
| мл.
| 4 б
|-
| 0
| 0
| 1<br />
| R<br />
| R
| R
| R
| R
| Рег. инд.
| /
| /
| 2 б
|-
| 0
| 1
| 0
| R<br />
| R
| R
| R
| R
| Рег. дир.
| /
| /
| 2 б
|-
| 0
| 1
| 1
| /
| /<br />
| /<br />
| /
| /
| PC релативно
| ст.<br />
| мл.
| 4 б
|-
| 1
| 0
| 0
| /
| /<br />
| /<br />
| /
| /
| Непосредно<br />
| ст.<br />
| мл.
| 4 б
|-
| 1
| 0
| 1
| R<br />
| R
| R
| R
| R
| Рег. инд. са пом.
| ст.<br />
| мл.
| 4 б
|}

=== Операциона јединица ===
{{делимично решено}}

=== Меморија ===
{{делимично решено}}
{| class="wikitable"
|-
! #<br />
! Адресе у меморији са којих је учитана инструкција
! IR31..24<br />
! IR23..16
! IR15..8
! IR7..0
! Инструкција
! PC
|-
| 1
| 1000, 1001, 1002, 1003
| E0
| 00
| 00
| 0A
| LD 000Ah<br />
| 1004
|-
| 2
| 1004, 1005, 1006
| 00
| 10
| 09
|
| JNZ 1009h
| 1007
|-
| 3
| 1009
| A2
|
|
|
| DEC
| 100A
|-
| 4
| 100A, 100B, 100C, 100D
| E2
| 60
| 00
| 08
| OR (PC+08h)
| 100E
|-
| 5
| 100E
| A0
|
|
|
| PUSH
| 100F
|-
| 6
| 100F, 1010, 1011
| 40
| 10
| 19
|
| JMP 1019h
| 1012
|-
| 7
| 1019, 101A
| E3
| 21
|
|
| ROR (R1)
| 101B
|}

{| class="wikitable"
|-
! #<br />
! Адресе у меморији или регистри<br />са којих је учитана адреса операнда
! Адресе у меморији или регистри <br />са којих је учитан операнд
! Операнд
! Нови садржај регистара опште намене<br />
|-
| 1
|
| 000A, 000B
| 1001
|
|-
| 2
|
|
|
|
|-
| 3
|
|
|
|
|-
| 4
|
| 1017, 1018
| 0003
|
|-
| 5
|
|
|
|
|-
| 6
|
|
|
|
|-
| 7
|
| 000C, 000D
| 00C1
|
|}

{| class="wikitable"
|-
! #<br />
! Меморијске адресе којима се <br />приступа у овој фази
! Акумулатор<br />
! N
! Z
! V
! C
! Нови садржај регистара и меморијских локација<br />који су промењени у овој фази
|-
| 1
|
|
|
|
|
|
|
|-
| 2
|
|
|
|
|
|
|
|-
| 3
|
|
|
|
|
|
|
|-
| 4
|
|
|
|
|
|
|
|-
| 5
|
|
|
|
|
|
|
|-
| 6
|
|
|
|
|
|
|
|-
| 7
|
|
|
|
|
|
|
|}

[[Категорија:ОРТ2]]
[[Категорија:Рокови]]

ОРТ2/К3 2021

2021-07-05T23:44:01Z

Mladen Žurkić: /* Меморија - фаза читања инструкције - табела*/

{{tocright}}

== Поставка ==
Посматра се део рачунара који чине меморија и процесор. Меморија је капацитета 2<sup>16</sup> бајтова. Ширина меморијске речи је 1 бајт. Процесор је са једноадресним форматом инструкција. Адресе и подаци су дужине 16 бита и заузимају по две суседне меморијске локације, при чему се старији бајт налази на нижој, а млађи бајт на вишој адреси.

У процесору постоји регистар програмског бројача PC дужине 2 бајта, адресни регистар меморије MAR дужине 2 бајта, прихватни регистар податка меморије MDR дужине 1 бајт, прихватни регистар инструкције IR дужине 4 бајта, акумулатор A дужине 2 бајта, прихватни регистар податка B дужине 2 бајта, регистри опште намене R0 до R15 дужине 2 бајта, програмска статусна реч PSW дужине 1 бајт. Инструкције су дужине 1, 2, 3 или 4 бајта.

Бит 7 првог бајта инструкције је 0 за све инструкције скока. Код инструкција условног скока бит 6 првог бајта инструкције је 0, док код инструкција безусловног скока бит 6 првог бајта инструкције је 1. Инструкција условног скока је инструкција условног скока уколико резултат није нула (JNZ), а инструкције безусловног скока су инструкција безусловног скока (JMP). Битовима 5 до 0 првог бајта инструкције специфицира се код операције и на основу тога су за инструкције JNZ и JMP усвојени кодови операције 00000000 и 01000000, респективно. Инструкције JNZ и JMP се реализују као апсолутни скокови, при чему је адреса дата другим и трећим бајтом инструкције. Дужина инструкција је 3 бајта.

Бит 7 првог бајта инструкције је 1 за све адресне и безадресне инструкције.

Битови 6 и 5 првог бајта инструкције су 01 за безадресне инструкције. Безадресне инструкције су инструкције стављања садржаја акумулатора на стек (PUSH), пуњења акумулатора садржајем са стека (POP) и декрементирање акумулатора (DEC). Битовима 4 до 0 првог бајта инструкције специфицира се код операције за безадресне инструкције. На основу тога су за инструкције PUSH, POP и DEC усвојени кодови операција 10100000, 10100001 и 10100010, респективно. Дужина инструкција је 1 бајт.

Битови 6 и 5 првог бајта инструкције су 11 за адресне инструкције. Адресне инструкције су инструкција преноса у акумулатор (LD), инструкција преноса из акумулатора (ST), логичка инструкција "или" (OR), инструкција ротирања операнда једно место удесно која смешта резултат у акумулатор (ROR), инструкција безусловног скока на срачунату адресу (JADR), инструкција сабирања (ADD) и инструкција одузимања (SUB). Битовима 4 до 0 првог бајта инструкције специфицира се код операције за адресне инструкције. На основу тога су за инструкције LD, ST, OR, ROR, JADR, ADD и SUB усвојени кодови операција 11100000, 11100001, 11100010, 11100011, 11100100, 11100101 и 11100110 респективно. Дужина инструкција је 2 или 4 бајта и зависи од специфицираног начина адресирања.

Начини адресирања су специфицирани битовима 7, 6 и 5 другог бајта инструкције и то на следећи начин: 000-меморијско директно адресирање (memdir), 001-регистарско индиректно адресирање (regind), 010-регистарско директно адресирање (regdir), 011-релативно адресирање са померајем (pcrel), 100-непосредно адресирање (immed) и 101-регистарско индиректно са померајем адресирање (regindpom). Код меморијског директног адресирања 16 битна адреса меморијске локације је дата трећим и четвртим бајтом инструкције. Битови 4 до 0 другог бајта инструкције се не користе. Дужина инструкција је 4 бајта. Регистарско индиректно адресирање користи неке од регистара опште намене R0 до R15 специфициране битовима од 3 до 0 другог бајта. Бит 4 другог бајта инструкције се не користи. Дужина инструкција је 2 бајта. Регистарско директно адресирање користи неке од регистара опште намене R0 до R15 специфициране битовима од 3 до 0 другог бајта. Бит 4 другог бајта инструкције се не користи. Дужина инструкција је 2 бајта. Код релативног адресирања са померајем трећи и четврти бајт инструкције садрже 16 битни померај који је дат као целобројна величина са знаком. Битови 4 до 0 другог бајта инструкције се не користе. Дужина инструкција је 4 бајта. Код непосредног адресирања 16 битни операнд дат је трећим и четвртим бајтом инструкције. Битови 4 до 0 другог бајта инструкције се не користе. Дужина инструкција је 4 бајта. Код регистарског индиректног адресирања са померајем трећи и четврти бајт инструкције садрже 16 битни померај који је дат као целобројна величина са знаком. Један од регистара опште намене R0 до R15 који се користи специфициран је битовима од 3 до 0 другог бајта инструкције. Бит 4 другог бајта инструкције се не користи. Дужина инструкција је 4 бајта.

Стек расте према вишим меморијским локацијама, а регистар SP указује на последњу заузету меморијску локацију. Процесор нема могућност обраде прекида.

<div class="abc-list">
# Пројектовати део операционе јединице процесора која је потребна да се изврши (FETCH + ADDR + EXEC) инструкција '''JADR (1234h)'''.
# Дати су почетни садржаји регистара и индикатора: PC=1000h, SP=2000h, ACC = 0002h, R0=00F2h, R1=000Ch, R2=00A2h, R3=FFE3h, N=0, Z=0, V=0 и C=0. Индикатори статусне речи на које инструкције не утиче треба да остану непромењени. Извршити 7 сукцесивних наредби и за сваку наредбу одредити следеће: у фази читања инструкције - меморијске адресе са којих је прочитана инструкција, садржај регистра IR, инструкцију која је прочитана и нови садржај регистра PC; у фази одређивања адресе операнда и читања операнда - меморијске адресе са којих је прочитана адреса операнда, меморијске адресе са којих је прочитан операнд, вредност операнда и нови садржај регистара опште намене који су у овој фази промењени; у фази извршавања операције - меморијске адресе којима се у овој фази приступа, садржај акумулатора A и индикатора N, Z, V и C након извршавања инструкције и нови садржај регистара и меморијских локација који су у овој фази промењени. Резултате представити у табелама 1, 2 и 3 формулара.
</div>
{| class="wikitable"
|+ Садржај дела меморије из поставке задатка
! ЛОКАЦИЈА
| 000A || 000B || 000C || 000D || 000E || 000F || 0010 || 0011 || 0012 || 0013
|-
! ВРЕДНОСТ
| 10 || 01 || 00 || C1 || 21 || 77 || 11 || 00 || 0A || 83
|-
! ЛОКАЦИЈА
| 1000 || 1001 || 1002 || 1003 || 1004 || 1005 || 1006 || 1007 || 1008 || 1009
|-
! ВРЕДНОСТ
| E0 || 00 || 00 || 0A || 00 || 10 || 09 || 10 || E8 || A2
|-
! ЛОКАЦИЈА
| 100A || 100B || 100C || 100D || 100E || 100F || 1010 || 1011 || 1012 || 1013
|-
! ВРЕДНОСТ
| E2 || 60 || 00 || 08 || A0 || 40 || 10 || 19 || 00 || 52
|-
! ЛОКАЦИЈА
| 1014 || 1015 || 1016 || 1017 || 1018 || 1019 || 101A || 101B || 101C || 101D
|-
! ВРЕДНОСТ
| 21 || 41 || F0 || 00 || 03 || E3 || 21 || B8 || 10 || 13
|}

== Решење ==
=== Кодови операција ===
{| class="wikitable"
|-
! colspan="8" | Битови IR31..24
! rowspan="2" | Класа инструкције<br />
|-
| 31
| 30
| 29
| 28
| 27
| 26
| 25
| 24
|-
| 0
| 0
| colspan="6" | Код операције<br />
| Условни скок<br />
|-
| 0
| 1
| colspan="6" | Код операције<br />
| Безусловни скок
|-
| 1
| 0
| 1
| colspan="5" | Код операције
| Безадресне инструкције
|-
| 1
| 1
| 1
| colspan="5" | Код операције
| Адресне инструкције
|}

{| class="wikitable"
|-
! colspan="8" | Битови IR31..24
! rowspan="2" | Инструкција<br />
! rowspan="2" | 2. бајт
! rowspan="2" | 3. бајт
! rowspan="2" | 4. бајт
! rowspan="2" | Дужина
|-
| 31
| 30
| 29
| 28
| 27
| 26
| 25
| 24
|-
| colspan="13" style="font-weight:bold;" | Условни скок
|-
| 0
| 0
| 0
| 0
| 0
| 0
| 0
| 0
| JNZ
| ст.<br />
| мл.
| /
| 3 б
|-
| colspan="13" style="font-weight:bold;" | Безусловни скок
|-
| 0
| 1
| 0
| 0
| 0
| 0
| 0
| 0
| JMP
| ст.<br />
| мл.
| /
| 3 б
|-
| colspan="13" style="font-weight:bold;" | Безадресне инструкције
|-
| 1
| 0
| 1
| 0
| 0
| 0
| 0
| 0
| PUSH
| /
| /
| /
| 1 б
|-
| 1
| 0
| 1
| 0
| 0
| 0
| 0
| 1
| POP
| /
| /
| /
| 1 б
|-
| 1
| 0
| 1
| 0
| 0
| 0
| 1
| 0
| DEC
| /
| /
| /
| 1 б
|-
| colspan="13" style="font-weight:bold;" | Адресне инструкције<br />
|-
| 1
| 1
| 1
| 0
| 0
| 0
| 0
| 0
| LD
| Адр.
|
|
|
|-
| 1
| 1
| 1
| 0
| 0
| 0
| 0
| 1
| ST
| Адр.
|
|
|
|-
| 1
| 1
| 1
| 0
| 0
| 0
| 1
| 0
| OR<br />
| Адр.
|
|
|
|-
| 1
| 1
| 1
| 0
| 0
| 0
| 1
| 1
| ROR
| Адр.
|
|
|
|-
| 1
| 1
| 1
| 0
| 0
| 1
| 0
| 0
| JADR
| Адр.
|
|
|
|-
| 1
| 1
| 1
| 0
| 0
| 1
| 0
| 1
| ADD
| Адр.
|
|
|
|-
| 1
| 1
| 1
| 0
| 0
| 1
| 1
| 0<br />
| SUB
| Адр.
|
|
|
|}

{| class="wikitable"
|-
! colspan="8" | Битови IR23..16
! rowspan="2" | Адресирање<br />
! rowspan="2" | 3. бајт
! rowspan="2" | 4. бајт
! rowspan="2" | Дужина
|-
| 23
| 22
| 21
| 20
| 19<br />
| 18<br />
| 17
| 16
|-
| 0
| 0
| 0
| /
| /
| /<br />
| /
| /
| Мем. дир.<br />
| ст.
| мл.
| 4 б
|-
| 0
| 0
| 1<br />
| R<br />
| R
| R
| R
| R
| Рег. инд.
| /
| /
| 2 б
|-
| 0
| 1
| 0
| R<br />
| R
| R
| R
| R
| Рег. дир.
| /
| /
| 2 б
|-
| 0
| 1
| 1
| /
| /<br />
| /<br />
| /
| /
| PC релативно
| ст.<br />
| мл.
| 4 б
|-
| 1
| 0
| 0
| /
| /<br />
| /<br />
| /
| /
| Непосредно<br />
| ст.<br />
| мл.
| 4 б
|-
| 1
| 0
| 1
| R<br />
| R
| R
| R
| R
| Рег. инд. са пом.
| ст.<br />
| мл.
| 4 б
|}

=== Операциона јединица ===
{{делимично решено}}

=== Меморија ===
{{делимично решено}}
{| class="wikitable"
|-
! #<br />
! Адресе у меморији са којих је учитана инструкција
! IR31..24<br />
! IR23..16
! IR15..8
! IR7..0
! Инструкција
! PC
|-
| 1
| 1000, 1001, 1002, 1003
| E0
| 00
| 00
| 0A
| LD 000Ah<br />
| 1004
|-
| 2
| 1004, 1005, 1006
| 00
| 10
| 09
|
| JNZ 1009h
| 1007
|-
| 3
| 1009
| A2
|
|
|
| DEC
| 100A
|-
| 4
| 100A, 100B, 100C, 100D
| E2
| 60
| 00
| 08
| OR (PC+08h)
| 100E
|-
| 5
| 100E
| A0
|
|
|
| PUSH
| 100F
|-
| 6
| 100F, 1010, 1011
| 40
| 10
| 19
|
| JMP 1019h
| 1012
|-
| 7
| 1019, 101A
| E3
| 21
|
|
| ROR (R1)
| 101B
|}

{| class="wikitable"
|-
! #<br />
! Адресе у меморији или регистри<br />са којих је учитана адреса операнда
! Адресе у меморији или регистри <br />са којих је учитан операнд
! Операнд
! Нови садржај регистара опште намене<br />
|-
| 1
|
|
|
|
|-
| 2
|
|
|
|
|-
| 3
|
|
|
|
|-
| 4
|
|
|
|
|-
| 5
|
|
|
|
|-
| 6
|
|
|
|
|-
| 7
|
|
|
|
|}

{| class="wikitable"
|-
! #<br />
! Меморијске адресе којима се <br />приступа у овој фази
! Акумулатор<br />
! N
! Z
! V
! C
! Нови садржај регистара и меморијских локација<br />који су промењени у овој фази
|-
| 1
|
|
|
|
|
|
|
|-
| 2
|
|
|
|
|
|
|
|-
| 3
|
|
|
|
|
|
|
|-
| 4
|
|
|
|
|
|
|
|-
| 5
|
|
|
|
|
|
|
|-
| 6
|
|
|
|
|
|
|
|-
| 7
|
|
|
|
|
|
|
|}

[[Категорија:ОРТ2]]
[[Категорија:Рокови]]

ОРТ2/Јул 2021

2021-07-05T20:48:45Z

Mladen Žurkić: /* ОРТ2 Јул К2 и К3 */

== Поставка ==

Посматра се део рачунара који чине меморија и процесор. Меморија је капацитета 2<sup>16</sup> бајтова. Ширина меморијске речи је 1 бајт. Процесор је са једноадресним форматом инструкција.Адресе и подаци су дужине 16 бита и заузимају по две суседне меморијске локације, при чему се старији бајт налази на нижој, а млађи бајт на вишој адреси.

У процесору постоји регистар програмског бројача PC дужине 2 бајта, адресни регистар меморије MAR дужине 2 бајта, прихватни регистар податка меморије MDR дужине 1 бајт, прихватни регистар инструкције IR дужине 4 бајта, акумулатор A дужине 2 бајта, прихватни регистар податка B дужине 2 бајта, регистри опште намене R0 до R31 дужине 2 бајта, програмска статусна реч PSW дужине 1 бајт. Инструкције су дужине 1, 2, 3 или 4 бајта.

Битови 7 и 6 првог бајта инструкције су 11 за све инструкције скока. Код инструкција условног скока битови 5 и 4 првог бајта инструкције су 00, док код инструкција безусловног скока битови 5 и 4 првог бајта инструкције су 11. Инструкција условног скока је инструкција условног скока уколико постоји пренос/позајмица (JC), а инструкције безусловног скока су инструкција безусловног скока (JMP) и инструкција скока на потпрограм (JSR). Битовима 3 до 0 првог бајта инструкције специфира се код операције и на основу тога су за инструкције JC, JMP и JSR усвојени кодови операције 11000000, 11110000 и 11110001, респективно. Инструкције JC, JMP и JSR се реализују као апсолутни скокови, при чему је адреса дата другим и трећим бајтом инструкције. Дужина инструкција је 3 бајта.

Битови 7 и 6 првог бајта инструкције су 00 за све адресне и безадресне инструкције.

Бит 5 првог бајта инструкције је 0 за безадресне инструкције. Безадресне инструкције су инструкције стављања садржаја акумулатора на стек (PUSH), пуњења акумулатора садржајем са стека (POP) и повратка из потпрограма (RTS). Битовима 4 до 0 првог бајта инструкције специфицира се код операције за безадресне инструкције. На основу тога су за инструкције PUSH, POP и RTS усвојени кодови операција 00000000, 00000001 и 00000011, респективно. Дужина инструкција је 1 бајт.

Битови 5 и 4 првог бајта инструкције су 11 за адресне инструкције. Адресне инструкције су инструкција преноса у акумулатор (LD), инструкција преноса из акумулатора (ST), логичка инструкција комплементирања операнда која смешта резултат у акумулатор (NOT), инструкција логичког померања операнда једно место улево која смешта резултат у акумулатор (LSL) и инструкција безусловног скока на срачунату адресу (JADR). Битовима 3 до 0 првог бајта инструкције специфицира се код операције за адресне инструкције. На основу тога су за инструкције LD, ST, NOT, LSL и JADR усвојени кодови операција 00110000, 00110001, 00110010, 00110011 и 00110100 респективно. Дужина инструкција је 2 или 4 бајта и зависи од специфицираног начина адресирања.

Начини адресирања су специфицирани битовима 7, 6 и 5 другог бајта инструкције и то на следећи начин: 000-меморијско директно адресирање (memdir), 001-регистарско директно адресирање (regdir), 010-регистарско индиректно (regind), 011-релативно адресирање са померајем (pcrel), и 100-непосредно адресирање (immed). Код меморијског директног адресирања 16 битна адреса меморијске локације је дата трећим и четвртим бајтом инструкције. Битови 4 до 0 другог бајта инструкције се не користе. Дужина инструкција је 4 бајта. Код регистарског директног и регистарског индиректног адресирања, користи се неки од регистара опште намене R0 до R31 специфицираних битовима од 4 до 0 другог бајта. Дужина инструкција је 2 бајта. Код релативног адресирања са померајем трећи и четврти бајт инструкције садрже 16 битни померај који је дат као целобројна величина без знака. Битови 4 до 0 другог бајта инструкције се не користе. Дужина инструкција је 4 бајта. Код непосредног адресирања 16 битни операнд дат је трећим и четвртим бајтом инструкције. Битови 4 до 0 другог бајта инструкције се не користе. Дужина инструкција је 4 бајта.

Стек расте према вишим меморијским локацијама, а регистар SP указује на прву слободну меморијску локацију. Процесор нема могућност обраде прекида

<strong>1. (К2) (20)</strong>

<div class="abc-list">
# Написати израз за генерисање сигнала gradr који је активан уколико прочитана инструкција има грешку при адресирању.
# Написати изразе за генерисање сигнала свих начина адресирања. IR регистар се попуњава од виших ка нижим битовима.
# Написати изразе за генерисање сигнала операција и то само за JC и NOT.
# Нацртати дијаграм тока фаза формирања адресе и читања операнда и фазе извршавање инструкције.
</div>

<strong>2. (К3) (20)</strong>

<div class="abc-list">
# Пројектовати део операционе јединице процесора која је потребна да се изврши (FETCH, ADDR и EXEC) инструкција <strong>NOT 000Dh</strong>.
# Дати су почетни садржаји регистара и индикатора: PC=1000h, SP=3000h, ACC=0001h, R0=0002h, R1=030Ch, R2=10A2h, R3=FAE3h, N=0, Z=0, V=0 и C=0. Индикатори статусне речи на које инструкција не утиче треба да остану непромењени. Извршити 7 сукцесивних наредби и за сваку наредбу одредити следеће: у фази читања инструкције - меморијске адресе са којих је прочитана инструкција, садржај регистра IR, инструкцију која је прочитана и нови садржај регистра PC; у фази одређивања адресе операнда и читања операнда - меморијске адресе са којих је прочитана адреса операнда, меморијске адресе са којих је прочитан операнд, вредност операнда и нови садржај регистара опште намене који су у овој фази промењени; у фази извршавања операције - меморијске адресе којима се у овој фази приступа, садржај акумулатора A и индикатора N, Z, V и C након извршавања инструкције и нови садржај регистара и меморијских локација који су у овој фази промењени. Резултате представити у табелама 1, 2 и 3 формулара.
</div>
{| class="wikitable"
|+ Садржај дела меморије из поставке задатка
! ЛОКАЦИЈА
| 000A || 000B || 000C || 000D || 000E || 000F || 0010 || 0011 || 0012 || 0013
|-
! ВРЕДНОСТ
| 10 || 01 || 00 || C1 || 21 || 77 || 11 || 00 || 0A || 83
|-
! ЛОКАЦИЈА
| 1000 || 1001 || 1002 || 1003 || 1004 || 1005 || 1006 || 1007 || 1008 || 1009
|-
! ВРЕДНОСТ
| 30 || 20 || F0 || 10 || 06 || 10 || 00 || 31 || 00 || 00
|-
! ЛОКАЦИЈА
| 100A || 100B || 100C || 100D || 100E || 100F || 1010 || 1011 || 1012 || 1013
|-
! ВРЕДНОСТ
| 13 || 32 || 00 || 00 || 13 || C0 || 00 || 10 || 01 || 52
|-
! ЛОКАЦИЈА
| 1014 || 1015 || 1016 || 1017 || 1018 || 1019 || 101A || 101B || 101C || 101D
|-
! ВРЕДНОСТ
| 22 || 41 || F0 || 00 || 03 || E3 || 21 || B8 || 10 || 13
|}

[[Категорија:ОРТ2]]
[[Категорија:Рокови]]

ОРТ2/К3 Фебруар 2021

2021-07-05T00:32:01Z

Mladen Žurkić: /* Колоквијум 3 - Садржај дела меморије из поставке задатка - Иван */

{{tocright}}
{{нерешено}}

== Колоквијум 2 ==

Посматра се део рачунара који чине меморија и процесор. Меморија је капацитета 2<sup>16</sup> бајтова. Ширина меморијске речи је 1 бајт. Процесор је са једноадресним форматом инструкција. Подаци су дужине 8 бита без знака, а адресе дужине 16 бита и заузимају по две суседне меморијске локације, при чему се старији бајт налази на вишој, а млађи бајт на нижој адреси.

У процесору постоји регистар програмског бројача PC дужине 2 бајта, адресни регистар меморије MAR дужине 2 бајта, прихватни регистар податка меморије MDR дужине 1 бајт, прихватни регистар инструкције IR дужине 4 бајта, акумулатор A дужине 1 бајт, прихватни регистар податка B дужине 1 бајт, регистри опште намене R0 до R15 дужине 2 бајта, програмска статусна реч PSW дужине 1 бајт. Инструкције су дужине 1, 2, 3 или 4 бајта.

Приликом читања податка из регистара опште намене, узима се нижих 8 бита.

Битови 7 и 6 првог бајта инструкције су 00 за све инструкције скока. Код инструкција условног скока бит 5 првог бајта инструкције је 0, док код инструкција безусловног скока бит 5 првог бајта инструкције је 1. Инструкција условног скока је инструкција условног скока уколико је резултат нула (JZ), а инструкције безусловног скока су инструкције безусловног скока (JMP) и инструкција скока на потпрограм (JSR). Битовима 4 до 0 првог бајта инструкције специфира се код операције и на основу тога су за инструкције JZ, JMP и JSR усвојени кодови операције 00000000, 00100000 и 00100001, респективно. Инструкције JZ, JMP и JSR се реализују као апсолутни скокови, при чему је адреса дата другим и трећим бајтом инструкције. Дужина инструкција је 3 бајта.

Битови 7 и 6 првог бајта инструкције су 11 за све адресне и безадресне инструкције.

Бит 5 првог бајта инструкције је 0 за безадресне инструкције. Безадресне инструкције су инструкције стављања садржаја акумулатора на стек (PUSH), пуњења акумулатора садржајем са стека (POP), инкрементирање акумулатора (INC) и повратка из потпрограма (RTS). Битовима 4 до 0 првог бајта инструкције специфицира се код операције за безадресне инструкције. На основу тога су за инструкције PUSH, POP, INC и RTS усвојени кодови операција 11000000, 11000001, 11000010 и 11000011, респективно. Дужина инструкција је 1 бајт.

Бит 5 првог бајта инструкције је 1 за адресне инструкције. Адресне инструкције су инструкција преноса у акумулатор (LD), инструкција преноса из акумулатора (ST), логичка инструкција "и" (AND), инструкција аритметичког померања операнда једно место удесно која смешта резултат у акумулатор (ASR) и инструкција безусловног скока на срачунату адресу (JADR). Битовима 4 до 0 првог бајта инструкције специфицира се код операције за адресне инструкције. На основу тога су за инструкције LD, ST, AND, ASR и JADR усвојени кодови операција 11100000, 11100001, 11100010, 11100011 и 11100100 респективно. Дужина инструкција је 2, 3 или 4 бајта и зависи од специфицираног начина адресирања.

Начини адресирања су специфицирани битовима 7, 6 и 5 другог бајта инструкције и то на следећи начин: 000-регистарско индиректно адресирање (regind), 001-регистарско директно адресирање (regdir), 010-меморијско индиректно адресирање (memind), 011-релативно адресирање са померајем (pcrel) и 100-непосредно адресирање (immed). Код регистарско директног и регистарског индиректног адресирања, користи се неки од регистара опште намене R0 до R15 специфицираних битовима од 4 до 1 другог бајта. Бит 0 другог бајта се не користи. Дужина инструкција је 2 бајта. Код меморијског индиректног адресирања 16 битна адреса меморијске локације је дата трећим и четвртим бајтом инструкције. Битови 4 до 0 другог бајта инструкције се не користе. Дужина инструкције је 4 бајта. Код релативног адресирања са померајем трећи и четврти бајт инструкције садрже 16 битни померај који је дат као целобројна величина без знака. Битови 4 до 0 другог бајта инструкције се не користе. Дужина инструкција је 4 бајта. Код непосредног адресирања 8 битни операнд дат је трећим бајтом инструкције. Битови 4 до 0 другог бајта инструкције се не користе. Дужина инструкције је 3 бајта.

Стек расте према нижим меморијским локацијама, а регистар SP указује на последњу заузету меморијску локацију. Процесор нема могућност обраде прекида.

Процесор нема подршку за детектовање грешке у адресирању у првој фази, већ тако прочитане инструкције се игноришу у осталим фазама.

Први корак сваке фазе сматрати да се означава са FETCH, ADDR, EXEC.

<div class="abc-list">
# Написати изразе за генерисање сигнала свих начина адресирања. IR регистар се попуњава од виших ка нижим битовима.
# Написати изразе за генерисање сигнала операција и то само за INC, AND и ASR.
# Нацртати дијаграм тока фаза формирања адресе и читања операнда и фазе извршавање операције.
</div>

== Колоквијум 3 ==
Посматра се део рачунара који чине меморија и процесор. Меморија је капацитета 2<sup>16</sup> бајтова. Ширина меморијске речи је 1 бајт. Процесор је са једноадресним форматом инструкција. Адресе и подаци су дужине 16 бита и заузимају по две суседне меморијске локације, при чему се старији бајт налази на вишој, а млађи бајт на нижој адреси.

У процесору постоји регистар програмског бројача PC дужине 2 бајта, адресни регистар меморије MAR дужине 2 бајта, прихватни регистар податка меморије MDR дужине 1 бајт, прихватни регистар инструкције IR дужине 3 бајта, акумулатор A дужине 2 бајта, прихватни регистар податка B дужине 2 бајта, регистри опште намене R0 до R3 дужине 2 бајта, програмска статусна реч PSW дужине 1 бајт. Програмска статусна реч PSW садржи битове N, Z, C и V који се ажурирају приликом рада процесора. Инструкције су дужине 1, 2 или 3 бајта.

Битови 7, 6 и 5 првог бајта инструкције је 000 за све инструкције скока. Код инструкције условног скока бит 4 првог бајта инструкције је 0, док код инструкција безусловног скока бит 4 првог бајта инструкције је 1. Инструкција условног скока је инструкција условног скока уколико је резултат негативан (BN) и инструкције безусловног скока су инструкција безусловног скока (JMP) и инструкција скока на потпрограм JSR. Битовима 3 до 0 првог бајта инструкције специфицира се код операције и на основу тога су за инструкције BN, JMP и JSR усвојени кодови операције 00000000, 00010000 и 00010001, респективно. Инструкције JMP и JSR се реализују као апсолутни скокови, при чему је адреса дата другим и трећим бајтом инструкције. Дужина инструкција је 3 бајта. Инструкција BN се реализује као релативни скок у односу на текућу вредност програмског бројача PC, а померај је 8 битна целобројна величина са знаком дата другим бајтом инструкције. Дужина инструкције је 2 бајта.

Битови 7, 6 и 5 првог бајта инструкције је 001 за све безадресне инструкције. Безадресне инструкције су инструкције стављања садржаја акумулатора на стек (PUSH), пуњења акумулатора садржајем са стека (POP) и инструкција комплементирања садржаја акумулатора (NOT). Битовима 4 до 0 првог бајта инструкције специфира се код операције за безадресне инструкције. На основу тога су за инструкције PUSH, POP и NOT усвојени кодови операција 00100000, 00100001 и 00100010, респективно. Дужина инструкција је 1 бајт.

Битови 7, 6 и 5 првог бајта инструкције имају вредности од 010 до 111 за адресне инструкције. Адресне инструкције су инструкција преноса у акумулатор (LD), инструкција преноса из акумулатора (ST), инструкција аритметичког померања удесно за једно место (ASR), инструкција упоређивања акумулатора са операндом (CMP), инструкција сабирања (ADD) и инструкција одузимања (SUB). На основу тога су за инструкције LD, ST, ASR, CMP, ADD и SUB усвојени кодови операција 010, 011, 100, 101, 110 и 111, респективно. Дужина инструкција је 2 или 3 бајта и зависи од специфичног начина адресирања.

Начини адресирања су специфицирани битовима 4, 3 и 2 другог бајта инструкције и то на следећи начин: 000-меморијско директно адресирање (memdir), 001-меморијско индиректно адресирање (memind), 010-регистарско директно адресирање (regdir), 011-регистарско индиректно адресирање (regind), 100-релативно адресирање са померајем (pcrel), 101-непосредно адресирање (immed) и 110-регистарско индиректно адресирање са преинкрементирањем (preincr). Код меморијског директног и меморијског индиректног адресирања 16 битна адреса меморијске локације је дата другим и трећим бајтом инструкције. Битови 1 и 0 првог бајта инструкције се не користе. Дужина инструкције је 3 бајта. Регистарско директно, регистарско индиректно и регистарско индиректно адресирање са преинкрементирањем користе неке од регистара опште намене R0 до R3 специфициране битовима 1 и 0 првог бајта. Дужина инструкција је 1 бајт. Код релативног адресирања са померајем други бајт инструкције садржи 8 битни померај који је дат као целобројна величина са знаком. Битови 1 и 0 првог бајта инструкције се не користе. Дужина инструкција је 2 бајта. Код непосредног адресирања 16 битни операнд дат је другим и трећим бајтом инструкције. Битови 1 и 0 првог бајта инструкције се не користе. Дужина инструкција је 3 бајта.

Стек расте према вишим меморијским локацијама, а регистар SP указује на прву слободну меморијску локацију. Процесор нема могућност обраде прекида.

<div class="abc-list">
# Пројектовати део операционе јединице процесора (фазе: FETCH, ADDR и EXEC) која је потребна да се изврши инструкција '''CMP +(R0)'''. Цртати само неопходне компоненте које су потребне за извршавање наведене инструкције.
# Дати су почетни садржаји регистара и индикатора: PC=1000h, SP=2000h, ACC=FFF7h, R0=0000h, R1=0001h, R2=0002h, R3=0003h, N=1, Z=0, V=0 и C=0. Индикатори статусне речи на које инструкција не утиче треба да остану непромењени. Извршити 7 сукцесивних наредби и за сваку наредбу одредити следеће: у фази читања инструкције - меморијске адресе са којих је прочитана инструкција, садржај регистра IR, инструкцију која је прочитана и нови садржај регистра PC; у фази одређивања адресе операнда и читања операнда - меморијске адресе са којих је прочитана адреса операнда, меморијске адресе са којих је прочитан операнд, вредност операнда и нови садржај регистара опште намене који су у овој фази промењени; у фази извршавања операције - меморијске адресе којима се у овој фази приступа, садржај акумулатора A и индикатора N, Z, V и C након извршавања инструкције и нови садржај регистара и меморијских локација који су у овој фази промењени. Резултате представити у табелама 1, 2 и 3 формулара.
</div>
{| class="wikitable"
|+ Садржај дела меморије из поставке задатка
! ЛОКАЦИЈА
| 0000 || 0001 || 0002 || 0003 || 0004 || 0005 || 0006 || 0007 || 0008 || 0009
|-
! ВРЕДНОСТ
| 07 || FF || 00 || 00 || 21 || 77 || 11 || 00 || 0A || 83
|-
! ЛОКАЦИЈА
| 1000 || 1001 || 1002 || 1003 || 1004 || 1005 || 1006 || 1007 || 1008 || 1009
|-
! ВРЕДНОСТ
| 60 || 00 || 00 || D4 || F6 || FF || 00 || 0C || D4 || F6
|-
! ЛОКАЦИЈА
| 100A || 100B || 100C || 100D || 100E || 100F || 1010 || 1011 || 1012 || 1013
|-
! ВРЕДНОСТ
| FF || 30 || 00 || 08 || A0 || 40 || 10 || 19 || 00 || 52
|-
! ЛОКАЦИЈА
| 1014 || 1015 || 1016 || 1017 || 1018 || 1019 || 101A || 101B || 101C || 101D
|-
! ВРЕДНОСТ
| 22 || E9 || 84 || 02 || 00 || 11 || 00 || 30 || E8 || E8
|}

[[Категорија:ОРТ2]]
[[Категорија:Рокови]]

ОО2

2021-06-27T21:57:59Z

Mladen Žurkić: /* Испитни рокови - линк ка ОО1 */

{{tocright}}
'''Објектно оријентисано програмирање 2''' је обавезан предмет у четвртом семестру, настављајући се на [[ОО1|Објектно оријентисано програмирање 1]].

== Странице ==
* [https://rti.etf.bg.ac.rs/rti/ir2oo2/ Страница предмета]

== Корисне везе ==
{{Материјали
| suetf = ir2oo2
| vuk = 1tsApPhN_66xrdBYYFg_4PAivufJ4cBVQ
| box = 8381893109
}}
* [[github:nikolabebic95/Fakultet/tree/master/Godina2/OO2|''nikolabebic95'' GitHub налог]]

== Домаћи ==
Погледати [[ОО1#Домаћи]].

== Лаб вежбе ==
Исто као и на [[ОО1#Лаб вежбе|ОО1]].
{{#dpl:
| titleregexp = ОО2/Лаб
| noresultsheader = Тренутно нема модификација.
| format = ,\n* [[%PAGE%|²{#invoke:String¦sub¦%PAGE%¦5¦-1}²]],,
}}

== Испитни рокови ==
Слична прича као и за [[ОО1#Испитни рокови|ОО1]] .

=== Пробни тестови ===
Овде се налазе пробни тестови дати за вежбу пред колоквијум на Moodle платформи.
{{#dpl:
| titleregexp = ОО2/Пробни тестови
| noresultsheader = Тренутно нема решених рокова.
| format = ,\n* [[%PAGE%|²{#invoke:String¦sub¦%PAGE%¦5¦-1}²]],,
}}

=== Колоквијум 1 ===
{{#dpl:
| titleregexp = ОО2/К1
| noresultsheader = Тренутно нема решених рокова.
| format = ,\n* [[%PAGE%|²{#invoke:String¦sub¦%PAGE%¦5¦-1}²]],,
}}

=== Колоквијум 2 ===
{{#dpl:
| titleregexp = ОО2/К2
| noresultsheader = Тренутно нема решених рокова.
| format = ,\n* [[%PAGE%|²{#invoke:String¦sub¦%PAGE%¦5¦-1}²]],,
}}

=== Испит ===
{{#dpl:
| titleregexp = ОО2/.* \d+$
| nottitleregexp = ОО2/К\d
| nottitleregexp = ОО2/Пробни тестови
| nottitleregexp = ОО2/Лаб
| noresultsheader = Тренутно нема решених рокова.
| format = ,\n* [[%PAGE%|²{#invoke:String¦sub¦%PAGE%¦5¦-1}²]],,
}}

== Начин оцењивања ==
Исто као и на [[ОО1#Начин оцењивања|ОО1]].

== Литература ==
Предмет је могуће положити са највишом оценом без коришћења литературе. Градиво предмета покривено је у ширини у уџбеницима:
* '''[https://akademska-misao.rs/index.html#/info/book/576 Програмски језик Java са решеним задацима]''' 3. издање, Ласло Краус, ''Издавач: Академска Мисао, Београд''
* '''[https://akademska-misao.rs/index.html#/info/book/308 Програмски језик C# са решеним задацима]''' 1. издање, Ласло Краус, ''Издавач: Академска Мисао, Београд''
Збирке су од мањег значаја након увођења новог формата колоквијума:
* '''[https://akademska-misao.rs/index.html#/info/book/678 Решени задаци из програмског језика Java]''' 5. издање, Ласло Краус, ''Издавач: Академска Мисао, Београд''
* '''[https://akademska-misao.rs/index.html#/info/book/9 Решени задаци из програмског језика C#]''' 2. издање, Ласло Краус, ''Издавач: Академска Мисао, Београд''

== Потребна помоћ ==
* {{zadaci|postavke}}
** Од користи су такође модификације добијене на лабораторијским вежбама, како би студенти знали отприлике шта их на лабораторијским вежбама чека.

[[Категорија:Четврти семестар]]
[[Категорија:Обавезни предмети]]
[[Категорија:ОО2]]

ОО2

2021-06-27T21:56:57Z

Mladen Žurkić: /* Начин оцењивања - линк */

{{tocright}}
'''Објектно оријентисано програмирање 2''' је обавезан предмет у четвртом семестру, настављајући се на [[ОО1|Објектно оријентисано програмирање 1]].

== Странице ==
* [https://rti.etf.bg.ac.rs/rti/ir2oo2/ Страница предмета]

== Корисне везе ==
{{Материјали
| suetf = ir2oo2
| vuk = 1tsApPhN_66xrdBYYFg_4PAivufJ4cBVQ
| box = 8381893109
}}
* [[github:nikolabebic95/Fakultet/tree/master/Godina2/OO2|''nikolabebic95'' GitHub налог]]

== Домаћи ==
Погледати [[ОО1#Домаћи]].

== Лаб вежбе ==
Исто као и на [[ОО1#Лаб вежбе|ОО1]].
{{#dpl:
| titleregexp = ОО2/Лаб
| noresultsheader = Тренутно нема модификација.
| format = ,\n* [[%PAGE%|²{#invoke:String¦sub¦%PAGE%¦5¦-1}²]],,
}}

== Испитни рокови ==
Слична прича као и за ОО1.

=== Пробни тестови ===
Овде се налазе пробни тестови дати за вежбу пред колоквијум на Moodle платформи.
{{#dpl:
| titleregexp = ОО2/Пробни тестови
| noresultsheader = Тренутно нема решених рокова.
| format = ,\n* [[%PAGE%|²{#invoke:String¦sub¦%PAGE%¦5¦-1}²]],,
}}

=== Колоквијум 1 ===
{{#dpl:
| titleregexp = ОО2/К1
| noresultsheader = Тренутно нема решених рокова.
| format = ,\n* [[%PAGE%|²{#invoke:String¦sub¦%PAGE%¦5¦-1}²]],,
}}

=== Колоквијум 2 ===
{{#dpl:
| titleregexp = ОО2/К2
| noresultsheader = Тренутно нема решених рокова.
| format = ,\n* [[%PAGE%|²{#invoke:String¦sub¦%PAGE%¦5¦-1}²]],,
}}

=== Испит ===
{{#dpl:
| titleregexp = ОО2/.* \d+$
| nottitleregexp = ОО2/К\d
| nottitleregexp = ОО2/Пробни тестови
| nottitleregexp = ОО2/Лаб
| noresultsheader = Тренутно нема решених рокова.
| format = ,\n* [[%PAGE%|²{#invoke:String¦sub¦%PAGE%¦5¦-1}²]],,
}}

== Начин оцењивања ==
Исто као и на [[ОО1#Начин оцењивања|ОО1]].

== Литература ==
Предмет је могуће положити са највишом оценом без коришћења литературе. Градиво предмета покривено је у ширини у уџбеницима:
* '''[https://akademska-misao.rs/index.html#/info/book/576 Програмски језик Java са решеним задацима]''' 3. издање, Ласло Краус, ''Издавач: Академска Мисао, Београд''
* '''[https://akademska-misao.rs/index.html#/info/book/308 Програмски језик C# са решеним задацима]''' 1. издање, Ласло Краус, ''Издавач: Академска Мисао, Београд''
Збирке су од мањег значаја након увођења новог формата колоквијума:
* '''[https://akademska-misao.rs/index.html#/info/book/678 Решени задаци из програмског језика Java]''' 5. издање, Ласло Краус, ''Издавач: Академска Мисао, Београд''
* '''[https://akademska-misao.rs/index.html#/info/book/9 Решени задаци из програмског језика C#]''' 2. издање, Ласло Краус, ''Издавач: Академска Мисао, Београд''

== Потребна помоћ ==
* {{zadaci|postavke}}
** Од користи су такође модификације добијене на лабораторијским вежбама, како би студенти знали отприлике шта их на лабораторијским вежбама чека.

[[Категорија:Четврти семестар]]
[[Категорија:Обавезни предмети]]
[[Категорија:ОО2]]

ОО2

2021-06-27T21:55:19Z

Mladen Žurkić: /* Линк за ОО1*/

{{tocright}}
'''Објектно оријентисано програмирање 2''' је обавезан предмет у четвртом семестру, настављајући се на [[ОО1|Објектно оријентисано програмирање 1]].

== Странице ==
* [https://rti.etf.bg.ac.rs/rti/ir2oo2/ Страница предмета]

== Корисне везе ==
{{Материјали
| suetf = ir2oo2
| vuk = 1tsApPhN_66xrdBYYFg_4PAivufJ4cBVQ
| box = 8381893109
}}
* [[github:nikolabebic95/Fakultet/tree/master/Godina2/OO2|''nikolabebic95'' GitHub налог]]

== Домаћи ==
Погледати [[ОО1#Домаћи]].

== Лаб вежбе ==
Исто као и на [[ОО1#Лаб вежбе|ОО1]].
{{#dpl:
| titleregexp = ОО2/Лаб
| noresultsheader = Тренутно нема модификација.
| format = ,\n* [[%PAGE%|²{#invoke:String¦sub¦%PAGE%¦5¦-1}²]],,
}}

== Испитни рокови ==
Слична прича као и за ОО1.

=== Пробни тестови ===
Овде се налазе пробни тестови дати за вежбу пред колоквијум на Moodle платформи.
{{#dpl:
| titleregexp = ОО2/Пробни тестови
| noresultsheader = Тренутно нема решених рокова.
| format = ,\n* [[%PAGE%|²{#invoke:String¦sub¦%PAGE%¦5¦-1}²]],,
}}

=== Колоквијум 1 ===
{{#dpl:
| titleregexp = ОО2/К1
| noresultsheader = Тренутно нема решених рокова.
| format = ,\n* [[%PAGE%|²{#invoke:String¦sub¦%PAGE%¦5¦-1}²]],,
}}

=== Колоквијум 2 ===
{{#dpl:
| titleregexp = ОО2/К2
| noresultsheader = Тренутно нема решених рокова.
| format = ,\n* [[%PAGE%|²{#invoke:String¦sub¦%PAGE%¦5¦-1}²]],,
}}

=== Испит ===
{{#dpl:
| titleregexp = ОО2/.* \d+$
| nottitleregexp = ОО2/К\d
| nottitleregexp = ОО2/Пробни тестови
| nottitleregexp = ОО2/Лаб
| noresultsheader = Тренутно нема решених рокова.
| format = ,\n* [[%PAGE%|²{#invoke:String¦sub¦%PAGE%¦5¦-1}²]],,
}}

== Начин оцењивања ==
Исто као и на ОО1.

== Литература ==
Предмет је могуће положити са највишом оценом без коришћења литературе. Градиво предмета покривено је у ширини у уџбеницима:
* '''[https://akademska-misao.rs/index.html#/info/book/576 Програмски језик Java са решеним задацима]''' 3. издање, Ласло Краус, ''Издавач: Академска Мисао, Београд''
* '''[https://akademska-misao.rs/index.html#/info/book/308 Програмски језик C# са решеним задацима]''' 1. издање, Ласло Краус, ''Издавач: Академска Мисао, Београд''
Збирке су од мањег значаја након увођења новог формата колоквијума:
* '''[https://akademska-misao.rs/index.html#/info/book/678 Решени задаци из програмског језика Java]''' 5. издање, Ласло Краус, ''Издавач: Академска Мисао, Београд''
* '''[https://akademska-misao.rs/index.html#/info/book/9 Решени задаци из програмског језика C#]''' 2. издање, Ласло Краус, ''Издавач: Академска Мисао, Београд''

== Потребна помоћ ==
* {{zadaci|postavke}}
** Од користи су такође модификације добијене на лабораторијским вежбама, како би студенти знали отприлике шта их на лабораторијским вежбама чека.

[[Категорија:Четврти семестар]]
[[Категорија:Обавезни предмети]]
[[Категорија:ОО2]]

Рачунарске мреже 1

2021-03-17T12:56:19Z

Mladen Žurkić: /* Начин оцењивања */

{{tocright}}
'''Рачунарске мреже 1''' су обавезан предмет у четвртом семестру.

== Странице ==
* [https://rti.etf.bg.ac.rs/rti/ir2rm/ Страница предмета]
* [https://elearning.rcub.bg.ac.rs/moodle/course/view.php?id=1095 ''Moodle'' курс предмета]

== Корисне везе ==
{{Материјали
| vuk = 1--8WGiKMDDu9VxWT_6gr0pNUEGAPPi2K
| box = 8376150409
}}

== Пројекат ==
На предмету од 2020. године постоји пројекат који замењује лабораторијске вежбе. Доступне су следеће поставке пројеката из претходних година:
{{#dpl:
| titleregexp = RM1 Projekat \d+.pdf
| namespace = File
| noresultsheader = Тренутно нема поставки пројекта
| format = ,\n* [[Медиј:%TITLE%|²{#invoke:String¦sub¦%PAGE%¦24¦-5}²]],,
| ordermethod = title
}}

== Испитни рокови ==
Доступан је [[Рачунарске мреже 1/Испитни пример 2020|испитни пример из 2020. године]] који је пре испита био постављен на ''Moodle'' курсу предмета.

== Начин оцењивања ==
* <math>K_1, K_2, K_3</math> — Бодови са првог, другог и трећег колоквијума (0-50)
* <math>I</math> — Бодови са интегралног испита (0-50)
* <math>T</math> — Укупни бодови са теоријског дела, рачунају се као <math>T = max\left(\frac{K_1 + K_2 + K_3}{3}, I\right)</math> (0-50)
* <math>Z</math> — Бодови са задатка (0-30)
* <math>PR</math> — Бодови са пројекта (0-20)
* Укупни бодови: <math>P = T + Z + PR</math>
* Услов: <math>T \geq 25 \land Z \geq 15</math>
{| class="wikitable"
! Бодови
| <math>P \leq 50</math> || <math>50 < P \leq 60</math> || <math>60 < P \leq 70</math> || <math>70 < P \leq 80</math> || <math>80 < P \leq 90</math> || <math>90 < P</math>
|-
! Оцена
| 5 || 6 || 7 || 8 || 9 || 10
|}

[[Категорија:Четврти семестар]]
[[Категорија:Обавезни предмети]]
[[Категорија:Рачунарске мреже 1]]

Рачунарске мреже 1

2021-03-17T12:54:34Z

Mladen Žurkić: /* Начин оцењивања T > 25 (50%)*/

{{tocright}}
'''Рачунарске мреже 1''' су обавезан предмет у четвртом семестру.

== Странице ==
* [https://rti.etf.bg.ac.rs/rti/ir2rm/ Страница предмета]
* [https://elearning.rcub.bg.ac.rs/moodle/course/view.php?id=1095 ''Moodle'' курс предмета]

== Корисне везе ==
{{Материјали
| vuk = 1--8WGiKMDDu9VxWT_6gr0pNUEGAPPi2K
| box = 8376150409
}}

== Пројекат ==
На предмету од 2020. године постоји пројекат који замењује лабораторијске вежбе. Доступне су следеће поставке пројеката из претходних година:
{{#dpl:
| titleregexp = RM1 Projekat \d+.pdf
| namespace = File
| noresultsheader = Тренутно нема поставки пројекта
| format = ,\n* [[Медиј:%TITLE%|²{#invoke:String¦sub¦%PAGE%¦24¦-5}²]],,
| ordermethod = title
}}

== Испитни рокови ==
Доступан је [[Рачунарске мреже 1/Испитни пример 2020|испитни пример из 2020. године]] који је пре испита био постављен на ''Moodle'' курсу предмета.

== Начин оцењивања ==
* <math>K_1, K_2, K_3</math> — Бодови са првог, другог и трећег колоквијума (0-50)
* <math>I</math> — Бодови са интегралног испита (0-50)
* <math>T</math> — Укупни бодови са теоријског дела, рачунају се као <math>T = max\left(\frac{K_1 + K_2 + K_3}{3}, I\right)</math> (0-50)
* <math>Z</math> — Бодови са задатка (0-30)
* <math>PR</math> — Бодови са пројекта (0-20)
* Укупни бодови: <math>P = T + Z + PR</math>
* Услов: <math>T \geq 25 \land Z \geq 50</math>
{| class="wikitable"
! Бодови
| <math>P \leq 50</math> || <math>50 < P \leq 60</math> || <math>60 < P \leq 70</math> || <math>70 < P \leq 80</math> || <math>80 < P \leq 90</math> || <math>90 < P</math>
|-
! Оцена
| 5 || 6 || 7 || 8 || 9 || 10
|}

[[Категорија:Четврти семестар]]
[[Категорија:Обавезни предмети]]
[[Категорија:Рачунарске мреже 1]]

ОО2

2021-02-19T13:30:37Z

Mladen Žurkić: /* Домаћи */

{{tocright}}
'''Објектно оријентисано програмирање 2''' је обавезан предмет у четвртом семестру, настављајући се на [[ОО1|Објектно оријентисано програмирање 1]].

== Странице ==
* [https://rti.etf.bg.ac.rs/rti/ir2oo2/ Страница предмета]


== Корисне везе ==
{{Материјали
| suetf = ir2oo2
| vuk = 1tsApPhN_66xrdBYYFg_4PAivufJ4cBVQ
| box = 8381893109
}}
* [https://github.com/nikolabebic95/Fakultet/tree/master/Godina2/OO2 Бебићев гитхуб]


== Домаћи ==
Погледати [[ОО1#Домаћи]].

== Лаб вежбе ==
Исто као и на ОО1.

== Испитни рокови ==
Слична прича као и за ОО1.
=== Пробни тестови ===
Овде се налазе пробни тестови дати за вежбу пред колоквијум на Moodle платформи.
{{#dpl:
| titleregexp = ОО2/Пробни тестови
| noresultsheader = Тренутно нема решених рокова.
| format = ,* [[%PAGE%|²{#invoke:String¦sub¦%PAGE%¦5¦-1}²]]\n,,
}}
=== Колоквијум 1 ===
{{#dpl:
| titleregexp = ОО2/К1
| noresultsheader = Тренутно нема решених рокова.
| format = ,* [[%PAGE%|²{#invoke:String¦sub¦%PAGE%¦5¦-1}²]]\n,,
}}
=== Колоквијум 2 ===
{{#dpl:
| titleregexp = ОО2/К2
| noresultsheader = Тренутно нема решених рокова.
| format = ,* [[%PAGE%|²{#invoke:String¦sub¦%PAGE%¦5¦-1}²]]\n,,
}}
=== Испит ===
{{#dpl:
| titleregexp = ОО2/.* \d+$
| nottitleregexp = ОО2/К\d
| nottitleregexp = ОО2/Пробни тестови
| nottitleregexp = ОО2/Лаб
| noresultsheader = Тренутно нема решених рокова.
| format = ,* [[%PAGE%|²{#invoke:String¦sub¦%PAGE%¦5¦-1}²]]\n,,
}}

== Начин оцењивања ==
Исто као и на ОО1.

== Литература ==
Предмет је могуће положити са највишом оценом без коришћења литературе. Градиво предмета покривено је у ширини у уџбеницима:
* '''[https://akademska-misao.rs/index.html#/info/book/576 Програмски језик Java са решеним задацима]''' 3. издање, Ласло Краус, ''Издавач: Академска Мисао, Београд''
* '''[https://akademska-misao.rs/index.html#/info/book/308 Програмски језик C# са решеним задацима]''' 1. издање, Ласло Краус, ''Издавач: Академска Мисао, Београд''
Збирке су од мањег значаја након увођења новог формата колоквијума:
* '''[https://akademska-misao.rs/index.html#/info/book/678 Решени задаци из програмског језика Java]''' 5. издање, Ласло Краус, ''Издавач: Академска Мисао, Београд''
* '''[https://akademska-misao.rs/index.html#/info/book/9 Решени задаци из програмског језика C#]''' 2. издање, Ласло Краус, ''Издавач: Академска Мисао, Београд''

[[Категорија:Четврти семестар]]
[[Категорија:Обавезни предмети]]
[[Категорија:ОО2]]

ОРТ2

2021-02-09T20:51:26Z

Mladen Žurkić: /* Начин оцењивања */

{{tocright}}
'''Основи рачунарске технике 2''' је обавезан предмет у трећем семестру.

== Странице ==
* [https://rti.etf.bg.ac.rs/rti/ir2ort2/ Страница предмета]
* [https://elearning.rcub.bg.ac.rs/moodle/course/view.php?id=604 Moodle курс]

== Корисне везе ==
{{Материјали
| vuk = 1-4dW6LftaVw6CtwuuXwUEVrnrH9TgfER
| box = 8374329465
}}
* [https://sourceforge.net/projects/circuit/ ''Logisim''] — Симулатор дигиталне логике који се користи при изради пројекта, као и за решења рокова на викију.
* ''[[github:reds-heig/logisim-evolution|Logisim-evolution]]'' — Унапређена верзија ''Logisim''
* [https://mega.nz/folder/As1A1TZY#z-SnQ4VsucNAwTLQgZjFug Рокови и решења (РТИ)]

== Пројекат ==
Пројекат се од 2020/21. године ради на ''Logisim'' симулатору дигиталне логике. У одељку [[#Корисне везе|Корисне везе]] изнад доступне су везе за преузимање ''Logisim'' и ''Logisim-evolution'' симулатора, а потребне су и ЕТФ библиотеке са компонентама које су доступне за:
* Стари ''Logisim'', на страници предмета под одељком "Пројекат"
* [[Медиј:ORT2 ETF-evolution.circ|''Logisim-evolution'']] - препоручује се именовање преузете датотеке као <code>ETF-evolution.circ</code>
Ове библиотеке је најбоље поставити у исти директоријум као шеме које преузимате са викија, али ће вас ''Logisim'' свакако питати да изаберете путању до ових библиотека уколико то не урадите.

== Испитни рокови ==
=== Колоквијум 1 ===
{{#dpl:
| titleregexp = ОРТ2/К1
| noresultsheader = Тренутно нема решених рокова.
| format = ,* [[%PAGE%|²{#invoke:String¦sub¦%PAGE%¦6¦-1}²]]\n,,
}}
=== Колоквијум 2 ===
{{#dpl:
| titleregexp = ОРТ2/К2
| noresultsheader = Тренутно нема решених рокова.
| format = ,* [[%PAGE%|²{#invoke:String¦sub¦%PAGE%¦6¦-1}²]]\n,,
}}
=== Колоквијум 3 ===
{{#dpl:
| titleregexp = ОРТ2/К3
| noresultsheader = Тренутно нема решених рокова.
| format = ,* [[%PAGE%|²{#invoke:String¦sub¦%PAGE%¦6¦-1}²]]\n,,
}}

== Лаб вежбе ==
На предмету се одржавају две лабораторијске вежбе од којих свака носи по 5 бодова. Лабораторијска вежба почиње улазним тестом од 10 минута и 3 питања, за који се примери могу наћи на страници предмета у одељку "Лабораторијске вежбе" (питалице су истог облика као на лабораторијској вежби). После улазног теста се прелази на рад у симулатору и за тај део се пишу одговори на задата питања у вези са задатим програмом у документу који се на крају вежбе предаје на мрежни диск. Током лабораторијске вежбе демонстратор такође испитује студента за 3 бода. Уколико је студент на улазном тесту освојио 2 бода, на бодове демонстратора се додаје 1 бод, а уколико је освојио 3 бода, на бодове демонстратора се додају 2 бода. Ако је студент освојио 0 или 1 бод на улазном тесту, не наставља с радом лабораторијске вежбе и добија 0 бодова. Збир бодова са улазног теста и од демонстратора се скалира са процентом урађености дела лабораторијске вежбе са симулатором, и тако се израчунавају коначни бодови на тој лабораторијској вежби.

Укратко:
* <math>T</math> — Бодови освојени на улазном тесту (од 0 до 3)
* <math>D</math> — Бодови освојени од демонстратора (од 0 до 3)
* <math>S</math> — Проценат урађености дела лабораторијске вежбе са симулатором (од 0 до 1)
* Коначна оцена: <math>\left\{\begin{array}{ll} 0 & T < 2 \\ (T - 1 + D) \cdot S & T \geq 2 \end{array}\right.</math>

== Начин оцењивања ==
* '''K1''', '''K2''' — Бодови са првог и другог колоквијума, носе по 20 бодова.
* '''L1''', '''L2''' — Бодови са лабораторијских вежби, носе по 5 бодова.
* '''I''' - Испитни део, носи 20 бодова.
* '''Projekat''' — Носи 30 бодова.
* '''P''' — Коначан број бодова: <math>P = K_1 + K_2 + I + L_1 + L_2 + Projekat </math>.
{| class="wikitable"
! Бодови
| <math>P \leq 50</math> || <math>50 < P \leq 60</math> || <math>60 < P \leq 70</math> || <math>70 < P \leq 80</math> || <math>80 < P \leq 90</math> || <math>90 < P</math>
|-
! Оцена
| 5 || 6 || 7 || 8 || 9 || 10
|}

[[Категорија:Трећи семестар]]
[[Категорија:Обавезни предмети]]
[[Категорија:ОРТ2]]

ОРТ2

2021-02-09T20:50:48Z

Mladen Žurkić: /* Начин оцењивања */

{{tocright}}
'''Основи рачунарске технике 2''' је обавезан предмет у трећем семестру.

== Странице ==
* [https://rti.etf.bg.ac.rs/rti/ir2ort2/ Страница предмета]
* [https://elearning.rcub.bg.ac.rs/moodle/course/view.php?id=604 Moodle курс]

== Корисне везе ==
{{Материјали
| vuk = 1-4dW6LftaVw6CtwuuXwUEVrnrH9TgfER
| box = 8374329465
}}
* [https://sourceforge.net/projects/circuit/ ''Logisim''] — Симулатор дигиталне логике који се користи при изради пројекта, као и за решења рокова на викију.
* ''[[github:reds-heig/logisim-evolution|Logisim-evolution]]'' — Унапређена верзија ''Logisim''
* [https://mega.nz/folder/As1A1TZY#z-SnQ4VsucNAwTLQgZjFug Рокови и решења (РТИ)]

== Пројекат ==
Пројекат се од 2020/21. године ради на ''Logisim'' симулатору дигиталне логике. У одељку [[#Корисне везе|Корисне везе]] изнад доступне су везе за преузимање ''Logisim'' и ''Logisim-evolution'' симулатора, а потребне су и ЕТФ библиотеке са компонентама које су доступне за:
* Стари ''Logisim'', на страници предмета под одељком "Пројекат"
* [[Медиј:ORT2 ETF-evolution.circ|''Logisim-evolution'']] - препоручује се именовање преузете датотеке као <code>ETF-evolution.circ</code>
Ове библиотеке је најбоље поставити у исти директоријум као шеме које преузимате са викија, али ће вас ''Logisim'' свакако питати да изаберете путању до ових библиотека уколико то не урадите.

== Испитни рокови ==
=== Колоквијум 1 ===
{{#dpl:
| titleregexp = ОРТ2/К1
| noresultsheader = Тренутно нема решених рокова.
| format = ,* [[%PAGE%|²{#invoke:String¦sub¦%PAGE%¦6¦-1}²]]\n,,
}}
=== Колоквијум 2 ===
{{#dpl:
| titleregexp = ОРТ2/К2
| noresultsheader = Тренутно нема решених рокова.
| format = ,* [[%PAGE%|²{#invoke:String¦sub¦%PAGE%¦6¦-1}²]]\n,,
}}
=== Колоквијум 3 ===
{{#dpl:
| titleregexp = ОРТ2/К3
| noresultsheader = Тренутно нема решених рокова.
| format = ,* [[%PAGE%|²{#invoke:String¦sub¦%PAGE%¦6¦-1}²]]\n,,
}}

== Лаб вежбе ==
На предмету се одржавају две лабораторијске вежбе од којих свака носи по 5 бодова. Лабораторијска вежба почиње улазним тестом од 10 минута и 3 питања, за који се примери могу наћи на страници предмета у одељку "Лабораторијске вежбе" (питалице су истог облика као на лабораторијској вежби). После улазног теста се прелази на рад у симулатору и за тај део се пишу одговори на задата питања у вези са задатим програмом у документу који се на крају вежбе предаје на мрежни диск. Током лабораторијске вежбе демонстратор такође испитује студента за 3 бода. Уколико је студент на улазном тесту освојио 2 бода, на бодове демонстратора се додаје 1 бод, а уколико је освојио 3 бода, на бодове демонстратора се додају 2 бода. Ако је студент освојио 0 или 1 бод на улазном тесту, не наставља с радом лабораторијске вежбе и добија 0 бодова. Збир бодова са улазног теста и од демонстратора се скалира са процентом урађености дела лабораторијске вежбе са симулатором, и тако се израчунавају коначни бодови на тој лабораторијској вежби.

Укратко:
* <math>T</math> — Бодови освојени на улазном тесту (од 0 до 3)
* <math>D</math> — Бодови освојени од демонстратора (од 0 до 3)
* <math>S</math> — Проценат урађености дела лабораторијске вежбе са симулатором (од 0 до 1)
* Коначна оцена: <math>\left\{\begin{array}{ll} 0 & T < 2 \\ (T - 1 + D) \cdot S & T \geq 2 \end{array}\right.</math>

== Начин оцењивања ==
* '''K1''', '''K2''' — Бодови са првог и другог колоквијума, носе по 20 бодова.
* '''L1''', '''L2''' — Бодови са лабораторијских вежби, носе по 5 бодова.
* '''I''' - Испитни део, носи 20 бодова.
* '''Пројекат''' — Носи 30 бодова.
* '''P''' — Коначан број бодова: <math>P = K_1 + K_2 + I + L_1 + L_2 + Пројекат</math>.
{| class="wikitable"
! Бодови
| <math>P \leq 50</math> || <math>50 < P \leq 60</math> || <math>60 < P \leq 70</math> || <math>70 < P \leq 80</math> || <math>80 < P \leq 90</math> || <math>90 < P</math>
|-
! Оцена
| 5 || 6 || 7 || 8 || 9 || 10
|}

[[Категорија:Трећи семестар]]
[[Категорија:Обавезни предмети]]
[[Категорија:ОРТ2]]

Корисник:Mladen Žurkić

2020-12-08T21:32:05Z

Mladen Žurkić:

Kontakt:
* [https://discordapp.com Discord:] <code>Mostone#8424</code>

Pozdrav!

ПМТ/К2 2019

2020-12-08T21:30:16Z

Mladen Žurkić: /* Задатак 1 t_0 = */

{{tocright}}

== Питање 1 ==
<div class="abc-list">
# '''(3п)''' Које особине има идеалан систем за пренос? Описати идеални систем за пренос у временском и спектралном домену.
# '''(2п)''' Одредити минималан проток сигнала добијеног применом временског мултиплексирања <math>N = 12</math> сигнала и ИКМ, ако је максимална учестаност у спектру сваког од сигнала <math>f_m = 10kHz</math>, а примењена је равномерна квантизација са <math>q = 512</math> нивоа.
</div>

== Питање 2 ==
<div class="abc-list">
# '''(2п)''' Нацртати двострани и једнострани амплитудски спектар сигнала <math>x(t)=U_1 \cos(2\pi f_1 t)</math>, <math>U_1=6V</math>, <math>f_1=400Hz</math>. Нацртати спектар снаге сигнала <math>x(t)</math>.
# '''(3п)''' Сигнал <math>y(t)</math> добијен је идеалним одабирањем сигнала <math>x(t)</math>, при чему је учестаност одабирања једнака <math>f_1=1000Hz</math>. Нацртати амплитудски спектар сигнала <math>y(t)</math> у опсегу од 0Hz до 3000Hz. Детаљно објаснити на који начин се на основу дискретизованог сигнала <math>y(t)</math> може извршити реконструкција сигнала <math>x(t)</math>.
</div>

== Задатак 1 ==
Дат је сигнал <math>x(t)</math> кога чини периодична униполарна поворка правоугаоних импулса периоде <math>T=0.5ms</math>, времена трајања импулса <math>r=0.1ms</math> и амплитуде <math>E=1V</math>. Време почетка импулса је <math>t_0 = -\tau/2</math>. Познато да је двострани спектар поворке правоугаоних импулса описан изразом

<math>X_n = \frac{E\tau}{T}\frac{\sin(\pi n\tau / T)}{(\pi n\tau / T)}.</math>
<div class="abc-list">
# '''(3п)''' Нацртати облик амплитудског спектра сигнала <math>x(t)</math> у опсегу учестаности до 10kHz. Колико се спектралних компоненти налази у опсегу од 3.4kHz до 8.9kHz (навести учестаност сваке компоненте)? Написати израз за укупну снагу компонената које се налазе у овом опсегу.
# '''(2п)''' Одредити средњу снагу сигнала <math>x(t)</math>, као и средњу снагу сигнала <math>y(t)</math> који се добија пропуштањем <math>x(t)</math> кроз филтар пропусних ниских учестаности (NF), чија је амплитудска карактеристика описана са
#: <math>\left|H_{NF}(jf)\right| = \left\{\begin{array}{ll}
1, & f_z \leq 3800 Hz, \\
0, & ostalo.
\end{array}
\right.
</math>
</div>

== Задатак 2 ==
Сигнал <math>p(t)</math> чија максимална учестаност у спектру износи 20kHz преноси се поступком импулсне кодне модулације (ИКМ). Сигнал <math>p(t)</math> се одабире учестаношћу која је 10% већа од минималне учестаности, одређене теоремом одабирања. Расподела амплитуда одбирака сигнала је униформна у интервалу <math>[-4V, +4V]</math>. Квантизација одбирака сигнала је униформна са <math>q=16</math> квантизационих нивоа. Кодирање сигнала врши се простим бинарним кодом почевши од најниже квантизационе вредности.
<div class="abc-list">
# '''(1п)''' Одредити учестаност одабирања сигнала <math>p(t)</math> и проток <math>V_b</math> добијеног ИКМ сигнала.
# '''(2п)''' Одредити вредност три најнижа и три највиша квантизациона нивоа, као и одговарајуће кодне речи на излазу кодера.
# '''(1п)''' Израчунати однос сигнал/шум квантизације (у dB).
# '''(1п)''' Одредити проток <math>V_{b,m}</math> ИКМ сигнала, ако се врши неравномерна квантизација са <math>q_n=32</math>, а учестаност одабирања није промењена.
</div>

[[Категорија:Рокови]]
[[Категорија:ПМТ]]

Корисник:Mladen Žurkić

2020-12-08T12:28:30Z

Mladen Žurkić: Нова страница: Mladen Žurkić Kontakt: * [https://discordapp.com Discord:] <code>Mostone#8424</code> Pozdrav!

Mladen Žurkić

Kontakt:
* [https://discordapp.com Discord:] <code>Mostone#8424</code>

Pozdrav!

Датотека:PMT 1. domaći 2020.pdf

2020-11-15T18:34:09Z

Mladen Žurkić: Нова страница: {{file | description = }}

АСП2/К1 2017

2020-11-03T13:39:36Z

Mladen Žurkić: /* Zapis while uslova, kao što je kod svage bin pr.*/

{{tocright}}
[https://rti.etf.bg.ac.rs/rti/ri3sp/rokovi/13S112ASP2_K1_1718.pdf Zadaci sa stranice predmeta.]

== 1. zadatak ==
=== Postavka ===
Uporediti metode binarne i višestruke sekvencijalne pretrage nad uređenim nizom celih brojeva 3, 7, 10, 11, 18, 22, 25, 27, 39, 41, 45, 48, 56, 64, 65, 78, 86. Odrediti broj poređenja pri pretrazi ključeva 25 i 44 za obe tehnike.
{| class="wikitable"
|+ Tabela iz postavke zadatka.
! 0 !! 1 !! 2 !! 3 !! 4 !! 5 !! 6 !! 7 !! 8 !! 9 !! 10 !! 11 !! 12 !! 13 !! 14 !! 15 !! 16
|-
| 3 || 7 || 10 || 11 || 18 || 22 || 25 || 27 || 39 || 41 || 45 || 48 || 56 || 64 || 65 || 78 || 86
|}

=== Rešenje ===
Višestrukom sekvencijalnom pretragom prvo idemo od ključa 3 do ključa 25, čime radimo 7 poređenja na nejednakost i jedno poređenje na jednakost, a zatim idemo od ključa 25 do ključa 45 čime radimo 5 poređenja na nejednakost i jedno poređenje na jednakost, što ukupno daje 14 poređenja na vrednost ključa.

Binarnom pretragom prvo gađamo ključ 39 (2), pa 11 (2), pa 22 (2) i na kraju 25 (1), a zatim u drugoj pretrazi 39 (2), pa 56 (2), pa 45 (2), pa 41 (2) i tu se pretraga završava neuspešno, čime vršimo 15 poređenja na vrednost ključa.

== 2. zadatak ==
=== Postavka ===
Funkciji FIND_BST prosleđen je pokazivač root na koren jednog kompletnog binarnog stabla. Struktura čvora ovog stabla osim ključa, pokazivača na levo i desno podstablo, sadrži i pokazivač na oca. Implementirati iterativnu funkciju FIND_BST čija povratna vrednost treba da bude pokazivač na koren onog podstabla koje predstavlja stablo binarne pretrage. Ukoliko postoji više ovakvih podstabala, treba vratiti pokazivač na koren onog podstabla sa maksimalnim brojem čvorova. Proveru da li je neko podstablo stablo binarne pretrage izdvojiti u posebnu funkciju. Obavezno kratko prokomentarisati rešenje.

=== Rešenje ===
Ovde nam je najpogodnije da ''postorder'' obilaskom određujemo da li su čvorovi binarna stabla pretraživanja, jer tako kad stignemo do viših čvorova već znamo da li su im deca ispravna binarna stabla pretraživanja. S tim u vidu, implementacija tražene funkcije za proveru izgleda ovako:
<syntaxhighlight lang="milo">
IS BST(node, left_max, right_min)
if left_max < key(node) < right_min then
return true
end_if
return false
</syntaxhighlight>
Kao pozivne argumente ove funkcije primamo najveći ključ iz levog podstabla i najmanji ključ iz desnog podstabla, što znači da bi trebalo da te podatke čuvamo u nekom redu kako bismo iz roditelja mogli da tim informacijama pristupimo. Obilazak kreće od reda listova i kreće se tako što svaki list gura svog roditelja u red, a duplikati roditelja se izbacuju iz reda prilikom njihovog obilaska.
<syntaxhighlight lang="milo">
FIND BST(root)
if root = nil then
return nil
end_if
last_bst = nil
QUEUE_INIT(Q_valid_bst)
QUEUE_INIT(Q_nodes)
QUEUE_INIT(Q_inv_nodes)
QUEUE_INIT(Q_max)
QUEUE_INIT(Q_min)
INSERT(Q_nodes, root)
while (not QUEUE_EMPTY(Q_nodes)) do
node = DELETE(Q_nodes)
if left(node) ≠ nil then
INSERT(Q_nodes, left(node))
INSERT(Q_nodes, right(node))
else
INSERT(Q_inv_nodes, node)
end_if
end_while
while (not QUEUE_EMPTY(Q_inv_nodes)) do
node = DELETE(Q_inv_nodes)
if left(node) = nil then
valid_bst = true
curr_max = key(node)
curr_min = key(node)
else
DELETE(Q_inv_nodes)
left_valid = DELETE(Q_valid_bst)
right_valid = DELETE(Q_valid_bst)
left_min = DELETE(Q_min)
right_min = DELETE(Q_min)
left_max = DELETE(Q_max)
right_max = DELETE(Q_max)
if left_valid and right_valid and IS_BST(node, left_max, right_min) then
valid_bst = true
else
valid_bst = false
end_if
curr_max = max(key(node), left_max, right_max)
curr_min = min(key(node), left_min, right_min)
end_if
if valid_bst then
last_bst = node
end_if
INSERT(Q_valid_bst, valid_bst)
INSERT(Q_inv_nodes, parent(node))
INSERT(Q_min, curr_min)
INSERT(Q_max, curr_max)
end_while
return last_bst
</syntaxhighlight>

== 3. zadatak ==
=== Postavka ===
[[Датотека:ASP2 K1 2018 zadatak 3 stablo.png|thumb|Crveno-crno stablo iz postavke zadatka.]]
Neka se posmatra crveno-crno stablo sa slike. Prikazati izgled stabla po koracima nakon umetanja ključeva 7 i 10.

=== Rešenje ===

== 4. zadatak ==
=== Postavka ===
Koristeći modifikovanu binarnu pretragu, napisati u pseudukodu iterativnu funkciju koja vraća poziciju prethodnika i sledbenika zadate vrednosti ''k'' u zadatom uređenom nizu ''arr''. Vrednost k ne mora postojati u nizu.

=== Rešenje ===
Ovde se pretpostavlja da se ključevi u nizu ne mogu ponavljati.
<syntaxhighlight lang="milo">
ARR PRED SUCC(arr, k)
while (low ≤ high) do
mid = (high + low) / 2
if arr[mid] = k then
return mid-1, mid+1
else if arr[mid] < k then
low = mid + 1
else
high = mid - 1
end_if
end_while
if arr[mid] < k then
return mid, mid+1
else
return mid-1, mid
end_if
</syntaxhighlight>

== 5. zadatak ==
=== Postavka ===
Neka se u prazno AVL stablo redom ubacuju ključevi 12, 43, 23, 55, 72, 2, 60, 57, 89, a zatim se brišu ključevi 12, 23 i 57. Prilikom brisanja koristiti '''prethodnika'''. Prikazati izgled stabla nakon svakog izvršenog koraka pri umetanju i brisanju

=== Rešenje ===
Konačno stablo je:
60
/ \
43 72
/ \ \
2 55 89
Postupak možete simulirati u nekom od [https://www.cs.usfca.edu/~galles/visualization/AVLtree.html simulatora] za AVL stabla.

== 6. zadatak ==
=== Postavka ===
Napisati u pseudokodu funkciju koja efikasno proverava da li je dato binarno stablo pretrage ''bst'' balansirano po AVL kriterijumu. Pored pokazivača na oca i levog i desnog sina, čvor stabla sadrži i podatke o visini levog i desnog podstabla.

=== Rešenje ===
Pošto ne moramo da izračunavamo visine podstabla, ovaj zadatak se svodi na posećivanje svih čvorova kako bismo uporedili sve visine levih i desnih podstabala u jednom čvoru. Ukoliko se u nekom razlikuju za više od 1, stablo nije balansirano po AVL kriterijumu.
<syntaxhighlight lang="milo">
CHECK AVL BALANCED(bst)
INIT_STACK(S)
PUSH(S, bst)
while (not STACK_EMPTY(S)) do
node = POP(S)
if abs(height_l(node) - height_r(node)) > 1 then
return false
end_if
if height_l(node) > 2 then
PUSH(S, left(node))
end_if
if height_r(node) > 2 then
PUSH(S, right(node))
end_if
end_while
return true
</syntaxhighlight>

== 7. zadatak ==
=== Postavka ===
Suboptimalno stablo binarnog pretraživanja
<div class="abc-list">
# Objasniti algoritam za određivanje suboptimalnog stabla binarnog pretraživanja koji je zasnovan na težinama podstabala.
# Ako su za ''n'' ključeva date verovatnoće uspešnog pretraživanja u nizu ''P'', a neuspešnog u nizu ''Q'', napisati efikasnu implementaciju funkcije koja nalazi samo koren tog stabla.
</div>

=== Rešenje ===
Određivanje suboptimalnog stabla binarnog pretraživanja zasnovanog na težinama podstabala, gde je težina podstabla koje uključuje čvorove na pozicijama od <math>i+1</math> do <math>j</math> u tabeli definisana kao <math>w_{ij} = q_i + p_{i+1} + q_{i+1} + ... + p_j + q_j</math>, se vrši tako što se prvo odredi ključ koji, kad postavljen za koren, daje najmanju razliku težina levog i desnog podstabla, a zatim se taj proces primeni rekurzivno na levo i desno podstablo (podniz) kako bi se i njihovi koreni odredili.
<syntaxhighlight lang="milo">
FIND ROOT(P, Q, n)
min_key = 1
left = Q[1]
right = 1 - left - P[1]
min_diff = abs(right - left)
for i = 2 to n do
left = left + Q[i] + P[i-1]
right = 1 - left - P[i]
diff = abs(right - left)
if diff < min_diff then
min_diff = diff
min_key = i
end_if
end_for
return min_key
end_for
</syntaxhighlight>

== 8. zadatak ==
=== Postavka ===
Neka se u samopodešavajuće stablo umeću redom ključevi 50, 70, 30, 60, 40, zatim se pretražuje na 70, pa se umeće 45 i, na kraju, pretražuje na 30. Prikazati izgled stabla nakon svake operacije.

=== Rešenje ===
Konačno stablo je:
30
\
40
\
45
\
60
/ \
50 70
Postupak možete simulirati u nekom od [https://www.cs.usfca.edu/~galles/visualization/SplayTree.html simulatora] za samopodešavajuća stabla.

[[Категорија:АСП2]]
[[Категорија:Рокови]]

АСП2/К1 2016

2020-11-02T10:42:44Z

Mladen Žurkić: /* Kosta Mladenovic izmena */

{{tocright}}
[https://rti.etf.bg.ac.rs/rti/ri3sp/rokovi/13S112ASP2_K1_1617.pdf Zadaci na stranici predmeta.]

== 1. zadatak ==
=== Postavka ===
Ako je ''inorder'' obilaskom nekog stabla binarnog pretraživanja dobijen niz ključeva 1 5 8 9 11 14 prikazati tri moguća izgleda ovog stabla sa: (a) najmanjom visinom, (b) najvećom visinom i (c) visinom između najmanje i najveće. Obeležiti stablo sa najboljim i najlošijim performansama operacija.

=== Rešenje ===
Stablo A ima najbolje performanse operacija:
9
/ \
5 11
/ \ \
1 8 14
Stablo B ima najlošije performanse operacija:
1
\
5
\
8
\
9
\
11
\
14
Stablo C nema ni najbolje ni najlošije performanse operacija:
11
/ \
9 14
/
8
/
5
/
1

== 2. zadatak ==
=== Postavka ===
Dat je niz celih brojeva. Koristeći stablo binarnog pretraživanja, napisati funkciju koja menja svaki element njegovim sledbenikom. U slučaju da element nema sledbenika, zadržati originalnu vrednost. Rezultat funkcije je niz preuredjen na opisani način.

=== Rešenje ===
Ovde prvo prebacujemo zadati niz u binarno stablo pretraživanja koristeći funkciju za umetanje čvora a zatim za svaki element niza pronalazimo sledbenika slično kao u [[АСП2/К1 2018#2. zadatak|drugom zadatku sa prvog kolokvijuma 2018]].
<syntaxhighlight lang="milo">
ARR TRANSFORM(arr, n)
bst = nil
for i = 1 to n do
BST-INSERT(bst, arr[i])
end_for
for i = 1 to n do
key = arr[i]
p = bst
prev = nil
while (p ≠ nil) and (key(p) ≠ key) do
if key(p) > key then
prev = p
p = left(p)
else
p = right(p)
end_if
end_while
p = right(p)
while p ≠ nil do
prev = p
p = left(p)
end_while
if prev ≠ nil then
arr[i] = key(prev)
end_if
end_for
</syntaxhighlight>
<syntaxhighlight lang="milo">
BST-INSERT(bst, key)
node = GETNODE
key(node) = key
if bst = nil then
bst = node
else
p = bst
while true do
if key(p) > key then
if left(p) = nil then
left(p) = node
break
else
p = left(p)
end_if
else
if right(p) = nil then
right(p) = node
break
else
p = right(p)
end_if
end_if
end_while
end_if
</syntaxhighlight>

== 3. zadatak ==
=== Postavka ===
Neka je dat rastuće uređeni niz celih brojeva (npr., 1 2 3 5 7 9) ili neka njegova rotacija (npr., 5 7 9 1 2 3). Vrednosti se ne ponavljaju u nizu. Napisati u pseudokodu iterativnu funkciju koja na efikasan način pronalazi minimalnu vrednost u nizu.

=== Rešenje ===
Ovaj problem se svodi na binarnu pretragu sa izmenjenim uslovima: sada detektujemo da li se nalazimo levo ili desno od tražene vrednosti poredeći se sa prvim elementom (ukoliko je trenutni element veći od prvog, levo smo od tražene vrednosti) a detekciju tražene vrednosti tako što proverimo da li je element levo od trenutnog veći od njega (to znači da smo došli na početak nerotiranog niza).
<syntaxhighlight lang="milo">
FIND MIN(arr, n)
low = 1
high = n
if arr[1] ≤ arr[n] then
return 1
end_if
while low ≤ high do
mid = (high + low) / 2
if arr[mid] < arr[mid-1] then
return mid
else if arr[mid] < arr[1] then
high = mid - 1
else
low = mid + 1
end_if
end_while
</syntaxhighlight>

== 4. zadatak ==
=== Postavka ===
Binarno pretraživanje u povećanoj tabeli
<div class="abc-list">
# Objasniti na koji način se vrši umetanje i brisanje u povećanoj tabeli.
# Data je povećana tabela uređena neopadajuće i odgovarajući vektor sa bitovima validnosti. Na slici je prikazano trenutno stanje. Prikazati izgled povećane tabele i vektora validnosti nakon umetanja svakog od kljuceva: 6, 29 i 35, a zatim ukloniti ključeve : 18 i 23 i prikazati finalno stanje.
</div>
{| class="wikitable"
|+ Početno stanje povećane tabele
| 5 || 5 || 9 || 18 || 22 || 22 || 23 || 25 || 28 || 38 || 40
|-
| 1 || 0 || 0 || 1 || 0 || 0 || 0 || 1 || 0 || 1 || 0
|}

=== Rešenje ===
Umetanje se vrši tako što prvo uradimo (binarnu) pretragu za neki ključ i ako utvrdimo da postoji (da postoji ključ sa traženom vrednošću u tabeli i da mu je bit validnosti postavljen na 1) bacamo grešku, u suprotnom proveravamo bit validnosti na polju do kojeg smo došli: ako je 1, moramo pomeriti sve validne ključeve koji slede nakon tog polja za jedno mesto unapred kako bismo mogli da ubacimo ključ na to polje. Pri ubacivanju se bit validnosti tog ključa postavi na 1, svi sledeći nevalidni ključevi se postave na tu vrednost a svi prethodni na vrednost prethodnog validnog ključa.

Pri brisanju se nakon pretrage za dati ključ, bit validnosti ključa samo postavi na 0 ukoliko postoji ili baci greška ukoliko ne postoji.

{| class="wikitable"
|+ Stanje povećane tabele nakon unosa ključa 6
| 5 || 6 || 9 || 18 || 22 || 22 || 23 || 25 || 28 || 38 || 40
|-
| 1 || 1 || 0 || 1 || 0 || 0 || 0 || 1 || 0 || 1 || 0
|}
{| class="wikitable"
|+ Stanje povećane tabele nakon unosa ključa 29
| 5 || 6 || 9 || 18 || 22 || 22 || 23 || 25 || 29 || 38 || 40
|-
| 1 || 1 || 0 || 1 || 0 || 0 || 0 || 1 || 1 || 1 || 0
|}
{| class="wikitable"
|+ Stanje povećane tabele nakon unosa ključa 35
| 5 || 6 || 9 || 18 || 22 || 22 || 23 || 25 || 29 || 35 || 38
|-
| 1 || 1 || 0 || 1 || 0 || 0 || 0 || 1 || 1 || 1 || 1
|}
{| class="wikitable"
|+ Stanje povećane tabele nakon uklanjanja ključa 18
| 5 || 6 || 9 || 18 || 22 || 22 || 23 || 25 || 29 || 35 || 38
|-
| 1 || 1 || 0 || 0 || 0 || 0 || 0 || 1 || 1 || 1 || 1
|}
Brisanjem ključa 23 dešava se greška jer taj ključ ne postoji.

== 5. zadatak ==
=== Postavka ===
Dato je stablo binarnog pretraživanja. Da li stablo zadato na slici zadovoljava kriterijum AVL stabla? Ukoliko ne, izvršiti balansiranje stabla po AVL kriterijumu, a zatim iz dobijenog stabla obrisati ključeve 55 i 20, pa u stablo umetnuti ključ 30. Prilikom brisanja, koristiti sledbenika. Prikazati izgled stabla nakon svake izvršene izmene.
20
/ \
17 32
/ / \
10 25 33
/ / \ \
5 22 27 57
/ \
55 71

=== Rešenje ===
Vidimo da su kritični čvorovi ovde 17, 32 i 33. Prvo radimo desnu rotaciju oko čvora 17:
20
/ \
10 32
/ \ / \
5 17 25 33
/ \ \
22 27 57
/ \
55 71
čime taj čvor više nije kritičan, ali zbog skraćivanja dužine levog podstabla čvor 20 postaje kritičan. Zatim radimo levu rotaciju oko čvora 33:
20
/ \
10 32
/ \ / \
5 17 25 57
/ \ / \
22 27 33 71
\
55
čime čvorovi 32 i 33 više nisu kritični. Na kraju, radimo levu rotaciju oko čvora 20:
32
/ \
20 57
/ \ / \
10 25 33 71
/ \ / \ \
5 17 22 27 55

== 6. zadatak ==
=== Postavka ===
[[Датотека:ASP2 K1 2016 zadatak 6 stablo.png|thumb|Crveno-crno stablo iz postavke zadatka.]]
U crveno-crnom stablu sa slike se najpre izvrši brisanje ključa 35, a zatim umetanje ključeva 9, 43, 10. Prikazati izgled stabla nakon svake od navedenih promena.

=== Rešenje ===

== 7. zadatak ==
=== Postavka ===
<div class="abc-list">
# U pseudokodu napisati funkciju koja za AVL stablo zadate visine ''h'' izračunava najmanji broj čvorova koje stablo može da sadrži.
# Na kojoj visini može da se nalazi list najbliži korenu?
# Kako se nazivaju ovakva stabla i po čemu su dobila ime?
</div>

=== Rešenje ===
<div class="abc-list">
# Pseudokod je dat ispod.
# ''ceil(h / 2)''
# Ovakva stabla, koja su najgori slučajevi AVL stabala, dobila su ime po Fibonačijevim brojevima  čija se rekurzivna definicija veoma malo razlikuje sa rekurzivnom definicijom broja čvorova ovakvih stabala u zavisnosti od njihove visine.
</div>
<syntaxhighlight lang="milo">
AVL MIN NODES(h)
if h = 0 then
return 1
else if h = 1 then
return 2
else
return AVL_MIN_NODES(h - 1) + AVL_MIN_NODES(h - 2) + 1
end_if
</syntaxhighlight>

== 8. zadatak ==
=== Postavka ===
Za stablo binarnog pretraživanja koje sadrži ključeve K1 < K2 < ... < Kn i čiji je koren ključ Kr izvesti vezu cene stabla i cena podstabla. Obavezno objasniti postupak.

=== Rešenje ===
Cena podstabla koje sadrži ključeve <math>K_{i+1}, K_{i+2}, ..., K_j</math> označava se sa <math>T_{ij}</math> i ima vrednost <math>q_i + p_{i+1} + q_{i+1} + ... + p_j + q_j</math>, što je zapravo zbir verovatnoća pretraživanja svih internih i eksternih čvorova tog podstabla. Pošto jedan čvor ima svoju verovatnoću pretraživanja kao i dva podstabla, dobijamo da je cena celog stabla čiji je koren <math>K_r</math> rekurzivno definisana sa <math>T = T_{1,r} + p_r + T_{r+1,n}</math>.

[[Категорија:АСП2]]
[[Категорија:Рокови]]

АСП2/К1 2015

2020-11-02T10:29:47Z

Mladen Žurkić: /* Promena broja 38 u 35 */

{{tocright}}
[https://rti.etf.bg.ac.rs/rti/ri3sp/rokovi/13S112ASP2_K1_1516.pdf Zadaci na stranici predmeta.]

== 1. zadatak ==
=== Postavka ===
Skup ključeva smešten je u stablo binarnog pretraživanja. Nakon brisanja ključa 12, dobijen je izgled stabla prikazan na slici. Pod pretpostavkom da je ključ 9 umetnut u stablo nakon ključa 12, da nije bilo prethodnih brisanja ključeva i da se prilikom brisanja koristi sledbenik, prikazati izgled stabla neposredno pre brisanja ključa 12.
6
/ \
5 15
/ / \
3 7 18
\ \ /
4 9 16
/ \
8 17

=== Rešenje ===
6
/ \
5 15
/ / \
3 12 18
\ / /
4 7 16
\ \
9 17
/
8

6
/ \
5 12
/ / \
3 7 15
\ \ \
4 9 18
/ /
8 16
\
17

6
/ \
5 12
/ / \
3 7 18
\ \ /
4 9 16
/ / \
8 15 17

== 2. zadatak ==
=== Postavka ===
Dat je krug K, sa centrom u tački C, poluprečnika r. Data je duž D čije je teme T1 unutar K, a teme T2 izvan K. Koristeći metodu binarne pretrage kao ideju, napisati u pseudokodu funkciju koja približno određuje tačku preseka K i D. Preciznost aproksimacije kontrolisati posebnim parametrom funkcije.

=== Rešenje ===
Ovde je ideja da nagađamo na kom se delu duži, u procentima, nalazi presek s kružnicom. Za svako nagađanje računamo razdaljinu od centra i ako je veća od poluprečnika to znači da smo van kruga, odnosno da treba da idemo bliže tački T1, u suprotnom treba da idemo bliže tački T2. Parametar <code>p</code> nam ovde označava preciznost aproksimacije u procentima dužine duži.
<syntaxhighlight lang="milo">
INTERSECT(K, D)
p = 0.05
low = 0
high = 1
mid_x = 0
mid_y = 0
while high - low ≥ p do
mid = (high + low) / 2
mid_x = (x(T2) - x(T1)) * mid + x(T1)
mid_y = (y(T2) - y(T1)) * mid + y(T1)
diff = sqrt((mid_x - x(C)) * (mid_x - x(C)) + (mid_y - y(C)) * (mid_y - y(C)))
if diff = r then
return mid_x, mid_y
else if diff < r then
low = mid
else
high = mid
end_if
end_while
return mid_x, mid_y
</syntaxhighlight>

== 3. zadatak ==
=== Postavka ===
Stabla binarnog pretraživanja
<div class="abc-list">
# Na koji način se u stablo binarnog pretraživanja može dozvoliti umetanje ključeva sa istom vrednošću?
# Napisati u pseudokodu iterativnu implementaciju funkcije koja umeće vrednost ''x'' u stablo binarnog pretraživanja na koje pokazuje pokazivač ''root''. U stablo je dozvoljeno umetati ključeve sa istom vrednošću.
</div>

=== Rešenje ===
Postoje dva načina na koje se može dozvoliti umetanje ključeva sa istom vrednošću u binarno stablo pretraživanja:
# U svakom čvoru stabla se čuva niz čvorova koje imaju istu vrednost ključa - ovim se postiže da se struktura stabla ne povećava.
# Čvorovi sa istom vrednošću se tretiraju kao veći, odnosno čuvaju u desnom podstablu - ovim se postiže veća pogodnost kod korišćenja za realizaciju struktura poput prioritetnog reda.
<syntaxhighlight lang="milo">
BST INSERT MOD(root, x)
node = GETNODE
value(node) = x
if root = nil then
root = node
return
end_if
p = root
while true do
if key(p) = x then
right(node) = right(p)
right(p) = node
break
else if key(p) < x then
if right(p) = nil then
right(p) = node
break
else
p = right(p)
end_if
else
if left(p) = nil then
left(p) = node
break
else
p = left(p)
end_if
end_if
end_while
</syntaxhighlight>

== 4. zadatak ==
=== Postavka ===
Crveno-crna stabla
<div class="abc-list">
# Definisati pojam crne visine (eng. ''black height'') nekog čvora crveno-crnog stabla.
# Napisati u pseudokodu funkciju koja u zadatom crveno-crnom stablu određuje crnu visinu zadatog čvora X.
</div>

=== Rešenje ===

== 5. zadatak ==
=== Postavka ===
Neka se u prazno AVL stablo redom umeću ključevi 35, 75, 51, 61, 65, 80, 44, 48, 39, 77, a zatim brišu ključevi 65, 44, 80. Prilikom brisanja, koristiti sledbenika. Prikazati izgled stabla nakon svakog izvršenog umetanja i brisanja.

=== Rešenje ===
Postupak umetanja možete simulirati u nekom od [https://www.cs.usfca.edu/~galles/visualization/AVLtree.html simulatora] za AVL stabla. Nakon umetanja dobije se sledeće stablo:
65
/ \
44 77
/ \ / \
35 51 75 80
\ / \
39 48 60
Po brisanju čvora 65, njegov sledbenik čvor 75 dolazi na njegovo mesto:
75
/ \
44 77
/ \ \
35 51 80
\ / \
39 48 60
Zatim se briše čvor 44 i njegov sledbenik čvor 48 dolazi na njegovo mesto:
75
/ \
48 77
/ \ \
35 51 80
\ \
39 60
Na kraju, briše se čvor 80 čime čvor 75 postaje kritičan čvor pa radimo rotaciju ulevo oko njega:
48
/ \
35 75
\ / \
39 51 77
\
61

== 6. zadatak ==
=== Postavka ===
[[Датотека:ASP2 K1 2015 zadatak 6 stablo.png|thumb|Crveno-crno stablo iz postavke zadatka.]]
U crveno-crno stablo sa slike se najpre vrši umetanje ključa 50, a zatim vrši brisanje ključa 13. Prikazati izgled stabla nakon svake od navedenih promena.

=== Rešenje ===

== 7. zadatak ==
=== Postavka ===
Dati pseudokod i objasniti algoritam određivanja prethodnika čvora sa zadatom adresom ''x'' u stablu binarnog pretraživanja. '''Napomena:''' Prilikom kretanja uz stablo ne koristiti proveru na pripadnost podstablu, već na vrednosti ključeva.

=== Rešenje ===
Prvo proveravamo da li čvor ima levo podstablo. Ukoliko ima, vraćamo najdesniji čvor u levom podstablu kao prethodnika čvora. Ukoliko nema, penjemo se uz stablo poredeći ključ čvora ''x'' sa ključevima njegovih roditelja i ako nađemo čvor sa manjim ključem vratimo ga.
<syntaxhighlight lang="milo">
PRED NODE(x)
if left(x) = nil then
p = parent(x)
while p ≠ nil do
if key(p) < key(x) then
return p
end_if
p = parent(p)
end_while
return nil
else
p = left(x)
while right(p) ≠ nil do
p = right(p)
end_while
return p
end_if
</syntaxhighlight>

== 8. zadatak ==
=== Postavka ===
a) Objasniti jednu strategiju za dobijanje suboptimalnog stabla binarnog pretraživanja koja uključuje i uspešna i neuspešna pretraživanja. b) Postupak ilustrovati po koracima ako su dati ključevi <math>K_i, i = 1..6</math>, sa verovatnoćama uspešnog pretraživanja <math>p_i, i = 1..6</math>, (0.1, 0.05, 0.05, 0.1, 0.05, 0.1, respektivno) i verovatnoćama neuspešnog pretraživanja <math>q_i, i = 0..6</math> (0.2, 0.05, 0.05, 0.0, 0.0, 0.05, 0.2, respektivno).

=== Rešenje ===
<div class="abc-list">
# Možemo formirati suboptimalno binarno stablo pretraživanja odabiranjem korena sa najmanjom razlikom težina između podstabala i rekurzivno ponavljati proces za oba podstabla.
#
## Kandidati za koren su nam K3 i K4. K3 nam daje razliku 0.1 između težina podstabla, a K4 0.05, pa zato biramo K4 i proces nastavljamo za [1, 2, 3] i [5, 6].
## Jedini kandidat za koren levog podstabla nam je K2, i zato njega postavljamo kao koren, K1 njegovo levo dete a K3 njegovo desno.
## Kandidat K6 je bolji od K5 jer omogućava razliku od 0.05 između težina podstabala za razliku od 0.1, pa njega postavljamo kao koren a K5 kao njegovo levo dete i dobijamo konačno stablo:
</div>
4
/ \
2 6
/ \ /
1 3 5

[[Категорија:АСП2]]
[[Категорија:Рокови]]

Датотека:PMT K1P 2020.pdf

2020-11-01T19:47:04Z

Mladen Žurkić: Нова страница: {{file | description = Поправка првог колоквијума 2019. године. | author = Катедра за телекомуникације, Ел…

{{file
| description = Поправка првог колоквијума 2019. године.
| author = Катедра за телекомуникације, Електротехнички факултет у Београду
| source = Са канала предмета на платформи "Teams"
}}

Датотека:PMT K1 2019.pdf

2020-11-01T19:36:00Z

Mladen Žurkić: Нова страница: {{file | description = Први колоквијум 2019. године. | author = Катедра за телекомуникације, Електротехни…

{{file
| description = Први колоквијум 2019. године.
| author = Катедра за телекомуникације, Електротехнички факултет у Београду
| source = Са канала предмета на платформи "Teams"
}}

АСП2/К1 2017

2020-11-01T19:11:24Z

Mladen Žurkić: /* - -> +*/

{{tocright}}
[https://rti.etf.bg.ac.rs/rti/ri3sp/rokovi/13S112ASP2_K1_1718.pdf Zadaci sa stranice predmeta.]

== 1. zadatak ==
=== Postavka ===
Uporediti metode binarne i višestruke sekvencijalne pretrage nad uređenim nizom celih brojeva 3, 7, 10, 11, 18, 22, 25, 27, 39, 41, 45, 48, 56, 64, 65, 78, 86. Odrediti broj poređenja pri pretrazi ključeva 25 i 44 za obe tehnike.
{| class="wikitable"
|+ Tabela iz postavke zadatka.
! 0 !! 1 !! 2 !! 3 !! 4 !! 5 !! 6 !! 7 !! 8 !! 9 !! 10 !! 11 !! 12 !! 13 !! 14 !! 15 !! 16
|-
| 3 || 7 || 10 || 11 || 18 || 22 || 25 || 27 || 39 || 41 || 45 || 48 || 56 || 64 || 65 || 78 || 86
|}

=== Rešenje ===
Višestrukom sekvencijalnom pretragom idemo od ključa 3 do ključa 45, čime posećujemo 11 ključeva. Binarnom pretragom prvo gađamo ključ 39, pa 11, pa 22 i na kraju 25, a zatim u drugoj pretrazi 39, pa 56, pa 45, pa 41 i tu se pretraga završava neuspešno, čime posećujemo 8 ključeva.

== 2. zadatak ==
=== Postavka ===
Funkciji FIND_BST prosleđen je pokazivač root na koren jednog kompletnog binarnog stabla. Struktura čvora ovog stabla osim ključa, pokazivača na levo i desno podstablo, sadrži i pokazivač na oca. Implementirati iterativnu funkciju FIND_BST čija povratna vrednost treba da bude pokazivač na koren onog podstabla koje predstavlja stablo binarne pretrage. Ukoliko postoji više ovakvih podstabala, treba vratiti pokazivač na koren onog podstabla sa maksimalnim brojem čvorova. Proveru da li je neko podstablo stablo binarne pretrage izdvojiti u posebnu funkciju. Obavezno kratko prokomentarisati rešenje.

=== Rešenje ===
Ovde nam je najpogodnije da ''postorder'' obilaskom određujemo da li su čvorovi binarna stabla pretraživanja, jer tako kad stignemo do viših čvorova već znamo da li su im deca ispravna binarna stabla pretraživanja. S tim u vidu, implementacija tražene funkcije za proveru izgleda ovako:
<syntaxhighlight lang="milo">
IS BST(node, left_child_valid_bst, right_child_valid_bst)
if (not left_child_valid_bst) or (not right_child_valid_bst) or (node = nil) then
return false
end_if
if key(left(node)) < key(node) < key(right(node)) then
return true
end_if
return false
</syntaxhighlight>
Kao pozivne argumente ove funkcije primamo da li su nam levo i desno dete čvora validni BST, što bi značilo da treba da te podatke čuvamo u nekom redu kako bismo iz roditelja mogli da tim informacijama pristupimo. Obilazak kreće od reda listova i kreće se tako što svaki list gura svog roditelja u red, a duplikati roditelja se izbacuju iz reda prilikom njihovog obilaska.
<syntaxhighlight lang="milo">
FIND BST(root)
if root = nil then
return nil
end_if
last_bst = nil
QUEUE_INIT(Q_valid_bst)
QUEUE_INIT(Q_nodes)
QUEUE_INIT(Q_inv_nodes)
INSERT(Q_nodes, root)
while (not QUEUE_EMPTY(Q_nodes)) do
node = DELETE(Q_nodes)
if left(node) ≠ nil then
INSERT(Q_nodes, left(node))
INSERT(Q_nodes, right(node))
else
INSERT(Q_inv_nodes, node)
end_if
end_while
while (not QUEUE_EMPTY(Q_inv_nodes)) do
node = DELETE(Q_inv_nodes)
if left(node) = nil then
left_valid = true
right_valid = true
else
DELETE(Q_inv_nodes)
left_valid = DELETE(Q_valid_bst)
right_valid = DELETE(Q_valid_bst)
end_if
valid_bst = IS_BST(node, left_valid, right_valid)
if valid_bst then
last_bst = node
end_if
INSERT(Q_valid_bst, valid_bst)
INSERT(Q_inv_nodes, parent(node))
end_while
return last_bst
</syntaxhighlight>

== 3. zadatak ==
=== Postavka ===
[[Датотека:ASP2 K1 2018 zadatak 3 stablo.png|thumb|Crveno-crno stablo iz postavke zadatka.]]
Neka se posmatra crveno-crno stablo sa slike. Prikazati izgled stabla po koracima nakon umetanja ključeva 7 i 10.

=== Rešenje ===

== 4. zadatak ==
=== Postavka ===
Koristeći modifikovanu binarnu pretragu, napisati u pseudukodu iterativnu funkciju koja vraća poziciju prethodnika i sledbenika zadate vrednosti ''k'' u zadatom uređenom nizu ''arr''. Vrednost k ne mora postojati u nizu.

=== Rešenje ===
Ovde se pretpostavlja da se ključevi u nizu ne mogu ponavljati.
<syntaxhighlight lang="milo">
ARR PRED SUCC(arr, k)
while high - low > 1 do
mid = (high + low) / 2
if arr[mid] = k then
return mid - 1, mid + 1
else if arr[mid] < k then
low = mid + 1
else
high = mid - 1
end_if
end_while
if high = low then
if arr[high] = k then
return high - 1, high + 1
else if arr[high] < k then
return high, high + 1
else
return high - 1, high
end_if
else
return low, high
end_if
</syntaxhighlight>

== 5. zadatak ==
=== Postavka ===
Neka se u prazno AVL stablo redom ubacuju ključevi 12, 43, 23, 55, 72, 2, 60, 57, 89, a zatim se brišu ključevi 12, 23 i 57. Prilikom brisanja koristiti '''prethodnika'''. Prikazati izgled stabla nakon svakog izvršenog koraka pri umetanju i brisanju

=== Rešenje ===
Konačno stablo je:
60
/ \
49 72
/ \ \
2 55 89
Postupak možete simulirati u nekom od [https://www.cs.usfca.edu/~galles/visualization/AVLtree.html simulatora] za AVL stabla.

== 6. zadatak ==
=== Postavka ===
Napisati u pseudokodu funkciju koja efikasno proverava da li je dato binarno stablo pretrage ''bst'' balansirano po AVL kriterijumu. Pored pokazivača na oca i levog i desnog sina, čvor stabla sadrži i podatke o visini levog i desnog podstabla.

=== Rešenje ===
Pošto ne moramo da izračunavamo visine podstabla, ovaj zadatak se svodi na posećivanje svih čvorova kako bismo uporedili sve visine levih i desnih podstabala u jednom čvoru. Ukoliko se u nekom razlikuju za više od 1, stablo nije balansirano po AVL kriterijumu.
<syntaxhighlight lang="milo">
CHECK AVL BALANCED(bst)
INIT_STACK(S)
PUSH(S, bst)
while (not STACK_EMPTY(S)) do
node = POP(S)
if abs(height_l(node) - height_r(node)) > 1 then
return false
end_if
if height_l(node) > 2 then
PUSH(S, left(node))
end_if
if height_r(node) > 2 then
PUSH(S, right(node))
end_if
end_while
return true
</syntaxhighlight>

== 7. zadatak ==
=== Postavka ===
Suboptimalno stablo binarnog pretraživanja
<div class="abc-list">
# Objasniti algoritam za određivanje suboptimalnog stabla binarnog pretraživanja koji je zasnovan na težinama podstabala.
# Ako su za ''n'' ključeva date verovatnoće uspešnog pretraživanja u nizu ''P'', a neuspešnog u nizu ''Q'', napisati efikasnu implementaciju funkcije koja nalazi samo koren tog stabla.
</div>

=== Rešenje ===
Određivanje suboptimalnog stabla binarnog pretraživanja zasnovanog na težinama podstabala, gde je težina podstabla koje uključuje čvorove na pozicijama od <math>i+1</math> do <math>j</math> u tabeli definisana kao <math>w_{ij} = q_i + p_{i+1} + q_{i+1} + ... + p_j + q_j</math>, se vrši tako što se prvo odredi ključ koji, kad postavljen za koren, daje najmanju razliku težina levog i desnog podstabla, a zatim se taj proces primeni rekurzivno na levo i desno podstablo (podniz) kako bi se i njihovi koreni odredili.
<syntaxhighlight lang="milo">
FIND ROOT(P, Q, n)
min_key = 1
left = Q[1]
min_diff = abs(1 - 2 * left - P[1])
for i = 2 to n do
left = left + Q[i] + P[i-1]
diff = abs(1 - 2 * left - P[i])
if diff < min_diff then
min_diff = diff
min_key = i
else
break
end_if
end_for
return min_key
end_for
</syntaxhighlight>

== 8. zadatak ==
=== Postavka ===
Neka se u samopodešavajuće stablo umeću redom ključevi 50, 70, 30, 60, 40, zatim se pretražuje na 70, pa se umeće 45 i, na kraju, pretražuje na 30. Prikazati izgled stabla nakon svake operacije.

=== Rešenje ===
Konačno stablo je:
30
\
40
\
45
\
60
/ \
50 70
Postupak možete simulirati u nekom od [https://www.cs.usfca.edu/~galles/visualization/SplayTree.html simulatora] za samopodešavajuća stabla.

[[Категорија:АСП2]]
[[Категорија:Рокови]]

АСП2/К1 2018

2020-11-01T17:49:45Z

Mladen Žurkić: /* 168 -> 160 */

{{tocright}}
[https://rti.etf.bg.ac.rs/rti/ri3sp/rokovi/13S112ASP2_K1_1819.pdf Zadaci na stranici predmeta.]

== 1. zadatak ==
=== Postavka ===
Optimalno stablo binarnog pretraživanja
<div class="abc-list">
# Navesti formulu za izračunavanje cene optimalnog stabla binarnog pretraživanja i objasniti je.
# Ukoliko se posmatraju tri ključa <math>K_1 < K_2 < K_3</math> sa poznatim verovatnoćama uspešnog pretraživanja p1 = 0.2, p2 = 0.05, p3 = 0.1 i neuspešnog pretraživanja q0 = 0.15, q1 = 0.2, q2 = 0.1 i q3 = 0.2, odrediti i nacrtati optimalno stablo binarnog pretraživanja.
</div>

=== Rešenje ===

== 2. zadatak ==
=== Postavka ===
Napisati u pseudokodu efikasnu iterativnu implementaciju funkcije koja u stablu binarnog pretraživanja na čiji koren ukazuje pokazivač ''root'' pronalazi sledbenika čvora koji sadrži ključ ''key''. U okviru čvora stabla ne postoji pokazivač na oca.

=== Rešenje ===
Ideja je da umesto ''inorder'' obilaska iskoristimo činjenicu da se sledbenik čvora sa ključem ''key'' može pronaći jednim spuštanjem niz stablo u pretrazi za ključem ''key''. Postoje dva slučaja:
# kada čvor sa ključem ''key'' ima desno podstablo, znamo da se u njemu sigurno nalazi njegov sledbenik kao najlevlje dete desnog podstabla, i
# kada taj čvor nema desno podstablo, uzimamo poslednji čvor kod koga smo utvrdili da mu je ključ veći od ključa koji tražimo (poslednji čvor kod koga smo "otišli levo").
<syntaxhighlight lang="milo">
FIND BST SUCC(root, key)
p = root
succ = nil
while (key(p) ≠ key) do
if (key(p) < key) then
p = right(p)
else if (key(p) > key) then
succ = p
p = left(p)
end_if
end_while
if (right(p) ≠ nil) then
p = right(p)
while (p ≠ nil) do
succ = p
p = left(p)
end_while
end_if
return succ
</syntaxhighlight>

== 3. zadatak ==
=== Postavka ===
[[Датотека:ASP2 K1 2018 zadatak 3 stablo.png|thumb|Crveno-crno stablo iz postavke zadatka.]]
Neka se posmatra crveno-crno stablo sa slike. Prikazati izgled stabla po koracima nakon umetanja ključeva 81 i 79 i uklanjanja ključa 23.

=== Rešenje ===

== 4. zadatak ==
=== Postavka ===
U stablu binarne pretrage greškom su dva čvora zamenila svoje pozicije. Implementirati funkciju CORRECT_BST koja ispravlja grešku i vraća ova dva čvora na svoje prave pozicije. Svaki čvor osim celobrojnog ključa i pokazivača na levo i desno podstablo sadrži i pokazivač na oca.

=== Rešenje ===
Ovde se pretpostavlja da se pod zamenom čvorova ne misli samo na zamenu ključeva u tim čvorovima već na zamenu zajedno da podstablima, tako da jedna zamena ne može imati kaskadne posledice već će samo dva čvora ostati nekonzistentna.

Ideja je na stek guramo decu čvorova za koje odredimo da upadaju u granice pretrage po stablu binarnog pretraživanja, a ako ne upadaju smestimo ih u jednu od dve promenljive i nakon toga zamenimo, pazeći da zamenimo i pokazivače na roditelje i roditeljske pokazivače.
<syntaxhighlight lang="milo">
CORRECT BST(root)
STACK_INIT(S_nodes)
STACK_INIT(S_low)
STACK_INIT(S_high)
PUSH(S_nodes, root)
PUSH(S_low, -∞)
PUSH(S_high, +∞)
while not STACK_EMPTY(S_nodes) do
node = POP(S_nodes)
low = POP(S_low)
high = POP(S_high)
if low < key(node) < high then
if left(node) ≠ nil then
PUSH(S_nodes, left(node))
PUSH(S_low, low)
PUSH(S_high, key(node))
end_if
if right(node) ≠ node then
PUSH(S_nodes, right(node))
PUSH(S_low, key(node))
PUSH(S_high, high)
end_if
else
if first = nil then
first = node
else
second = node
break
end_if
end_if
end_while
tmp = parent(first)
parent(first) = parent(second)
parent(second) = tmp
if left(parent(first)) = second then
left(parent(first)) = first
else
right(parent(first)) = first
end_if
if left(parent(second)) = first then
left(parent(second)) = second
else
right(parent(second)) = second
end_if
</syntaxhighlight>

== 5. zadatak ==
=== Postavka ===
Neka se u prazno AVL stablo redom ubacuju ključevi 27, 12, 7, 34, 31, 5, 6, a zatim se brišu ključevi 31, 34, 12. Prilikom brisanja koristiti '''prethodnika'''. Prikazati izgled stabla nakon svakog izvršenog koraka pri umetanju i brisanju.

=== Rešenje ===
Konačno stablo je:
7
/ \
6 27
/
5
Postupak možete simulirati u nekom od [https://www.cs.usfca.edu/~galles/visualization/AVLtree.html simulatora] za AVL stabla.

== 6. zadatak ==
=== Postavka ===
Koristeći metodu binarne pretrage kao ideju, napisati u pseudokodu funkciju koja efikasno proverava da li je tačka T teme ''n''-tougla M. Mnogougao M se zadaje pomoću niza tačaka – temena. Tačke su određene koordinatama ''x'' i ''y''. Niz temena mnogougla je uređen rastuće po vrednosti koordinate ''x'', pri čemu za istu vrednost koordinate ''x'' važi rastuća uređenost po vrednosti koordinate ''y''.

=== Rešenje ===
Ovde se radi obična binarna pretraga s tim što se uslovi za odlazak ulevo ili udesno menjaju: ukoliko je x koordinata trenutne tačke veća od tražene, ili ukoliko su iste ali je y koordinata veća od tražene, ide se ulevo, a ukoliko je x koordinata trenutne tačke manja od tražene, ili ukoliko su iste ali je y koordinata manja od tražene, ide se udesno.
<syntaxhighlight lang="milo">
CHECK VERTEX(M, n, T)
low = 1
high = n
while low ≤ high do
mid = (high + low) / 2
if (x(M[mid]) = x(T)) and (y(M[mid]) = y(T)) then
return true
else if (x(M[mid]) < x(T)) or ((x(M[mid]) = x(T)) and (y(M[mid]) < y(T))) then
low = mid + 1
else
high = mid - 1
end_if
end_while
return false
</syntaxhighlight>

== 7. zadatak ==
=== Postavka ===
Dat je neuređeni niz ''A'' dužine ''n'' celobrojnih ključeva u opsegu vrednosti 1..100 koji se pretražuje i neuređeni niz ključeva ''K'' mnogo veće dužine ''m'' na koje se vrši pretraga. U nizu ''K'' ima veliki broj ponovljenih ključeva. Zbog neravnomerne verovatnoće pretrage ključeva, koristi se sledeća tehnika optimizacije. Nakon svakog uspešnog pretraživanja, vrši se prebacivanje za ''p'' pozicija unapred, gde je ''p'' broj uspešnih nalaženja tog ključa. Napisati u pseudokodu funkciju koja redom pretražuje niz ''A'' na ključeve iz niza ''K'' i vraća prosečan broj poređenja po nađenom ključu.

=== Rešenje ===
<syntaxhighlight lang="milo">
SEARCH(A, K, n, m)
for i = 1 to 100 do
P[i] = 0
end_for
sum = 0
num = 0
for i = 1 to m do
key = K[i]
found = 0
for j = 1 to n do
if A[j] = key then
found = j
break
end_if
end_for
if found ≠ 0 then
sum = sum + j
num = num + 1
P[key] = P[key] + 1
for k = found downto found - P[key] + 1 do
A[k] = A[k-1]
end_for
A[found - P[key]] = key
end_if
end_for
if num = 0 then
return 0
else
return sum/num
end_if
</syntaxhighlight>

== 8. zadatak ==
=== Postavka ===
Obrazložiti da li je sledeća sekvenca ključeva validna u stablu binarnog pretraživanja:
<div class="abc-list">
# Ako se prilikom uspešnog pretraživanja u jednom stablu redom proveravaju ključevi 23, 87, 158, 348, 160, 200, 150, 158.
# Ako se prilikom neuspešnog pretraživanja u drugom stablu redom proveravaju ključevi 546, 453, 427, 68, 415, 231, 247, 417, 300.
</div>

=== Rešenje ===
Ovde gledamo naš silazak niz potencijalni BST i na osnovu prethodno pogledanih čvorova određujemo granice ''high'' i ''low'' u kojima se moraju nalaziti naredni ključevi kako bi stablo bilo validan BST. Dobijamo da oba slučaja nisu moguća u binarnom stablu pretraživanja.
<div class="abc-list">
#
## 23 → 87, low = 23, high = +∞
## 87 → 158, low = 87, high = +∞
## 158 → 348, low = 158, high = +∞
## 348 → 160, low = 158, high = 348
## 160 → 200, low = 160, high = 348
## 200 → 150, 150 < low => ⚡
#
## 546 → 453, low = -∞, high = 546
## 453 → 427, low = -∞, high = 453
## 427 → 68, low = -∞, high = 427
## 68 → 415, low = 68, high = 427
## 415 → 231, low = 68, high = 415
## 231 → 247, low = 231, high = 415
## 247 → 417, 417 > high => ⚡
</div>

[[Категорија:АСП2]]
[[Категорија:Рокови]]

Математика 2/Јул 2020

2020-07-06T10:46:00Z

Mladen Žurkić: /* Други део задаци */

== Други део ==

=== Задаци ===
=== 2. задатак ===
а) Колико има функција које сликају скуп M = {1, 2} у скуп P = {1, 2, 3, 4, 5}?

б) Коликоа има функција које сликају скуп {a, b, c} у скуп цифара?

== Домаћи задатак ==
=== 1. задатак ===
Решити интеграле:
{| class="wikitable"
|-
| <math>\int \frac{dx}{x^2 + 4x + 4} </math>
|-
| <math>\int \frac{x+2}{x^2 + 4x + 4}dx </math>
|}
=== 2. задатак ===
Одредити екстреме функције <math> z(x,y) = (x-y)^2 + (x-1)^2 </math>
=== 3. задатак ===
Одредити <math> c,d \in \mathbb{R} </math> тако да <math> y = csinx + dcosx </math> буде решење <math> y' + 2y = cosx </math>
=== 4. задатак ===
Одредити параметар а тако да матрица има сопствену вредност 5. ''(Фали матрица)''
=== 5. задатак ===
Колико има осмоцифрених бројева таквих да се цифра 9 појављује три пута, цифре 7 и 8 два пута и цифра 6 једанпут?

[[Категорија:Рокови]]
[[Категорија:Математика 2]]