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

Заштита података/Јул 2021

2023-05-04T20:18:21Z

Lukahrvacevic: /* 2. zadatak */

{{tocright}}
'''Julski rok 2021. godine''' održan je 29. juna. Postavka ovog roka nije javno dostupna.
{{rešenja}}

== 1. zadatak ==
Ana i Branko razmenjuju ključ Diffie-Hellman algoritmom. Za tu svrhu koriste prost broj 10007 i njegov primitivni koren 3073. Ana je za svoj privatni broj odredila 3072, a Branko 520. Odrediti:
<div class="abc-list">
# Javni broj koji je izračunala Ana <span class="spoiler" data-solution="text">3374</span>
# Javni broj koji je izračunao Branko <span class="spoiler" data-solution="text">5388</span>
# Ključ koji je razmenjen <span class="spoiler" data-solution="text">1876</span>
</div>

== 2. zadatak ==

Marko treba da plati uslugu n bitkoina u blokčejnu koji koristi SHA-256 heš funkciju i stoga formira transakciju t<sub>1</sub> sa iznosom n kojim se plaća usluga. Kako bi smanjio svoju obavezu i prevario prodavca usluge Marko želi da napravi drugu transakciju t<sub>2</sub> čija je vrednost manja od n i da je podmetne umesto t<sub>1</sub>. Koliko če različitih transakcija Marko morati da napravi da bi sa verovatnoćom 0.5 uspeo da napravi zadovoljavajuću transakciju t<sub>2</sub>?

Podrazumeva se da zamena transakcije treba da bude takva da nema novog rudarenja. Odgovor upisati u polje, operacija stepenovanja treba da se
označi simbolom ^.

Odgovor: <span class="spoiler" data-solution="text">2^255</span>

Ako se zna da blokčejn ima u svakom bloku 2048 transakcija, koliko je heš operacija potrebno da se izvrši da bi se izračunao "Transaction hash" ?

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

== 3. zadatak ==
{{delimično rešeno}}
Na slici je dat prvi deo Kerberos v4 autentikacije:

<math> (1) \quad \mathbf{C \rightarrow AS} \quad ID_c \parallel ID_{tgs} \parallel TS_1 </math>

<math> (2) \quad \mathbf{AS \rightarrow C} \quad E\left( K_c, \left[ \qquad \parallel TS_2 \parallel Lifetime_2 \parallel Ticket_{tgs} \right] \right) </math>

<math> \qquad Ticket_{tgs} = E\left( K_{tgs}, \left[ \qquad \parallel TS_2 \parallel Lifetime_2 \right] \right) </math>

Elementi koji nedostaju u poruci (2) (ne i u Ticket<sub>tgs</sub>) su:
<div class="abc-list" data-solution="multiple">
# identifikator servera AS
# identifikator TGS
# identifikator klijenta C
# IP adresa servera V
# IP adresa klijenta C
# IP adresa servera AS
# ključ kojim komuniciraju klijent i autentikacioni server AS
# ključ kojim komuniciraju klijent i server V
# identifikator servera V
# ključ kojim komuniciraju klijent i TGS
</div>

== 4. zadatak ==
: ''Isti zadatak kao sa [[Заштита података/К 2022#5. zadatak|kolokvijuma za RTI 2022. godine]].''

== 5. zadatak ==
MAC algoritam koji daje MAC kod veličine 32 bita ima ključ veličine 100 bita. Ako je raspodela MAC kodova koji daje algoritam uniformna i sve vrednosti su jednako verovatne, da bi otkrio ključ koji se koristi za generisanje MAC kodova napadaču će trebati:
<div class="abc-list">
# <span class="spoiler" data-solution="text">4</span> različita para/različitih parova (poruka, MAC(poruka)).
# Da izvrši <span class="spoiler" data-solution="text">2^100+2^68+2^36+2^4</span> MAC operacija (za prikaz operacije stepenovanja koristiti simbol ^).
</div>

== 6. zadatak ==
{{delimično rešeno}}
Firma F ima centralu koja se nalazi u Helsinkiju. Na centralnoj lokaciji se nalazi 5 web aplikacija kojima se pružaju interne poslovne usluge. Sve aplikacije koriste HTTPS. F ima 10 zaposlenih u svojoj ispostavi u Pragu. Ako se zna da svi zaposleni u ispostavi svakog radnog dana koriste svih 5 aplikacija na centralnoj lokaciji i da se povezuju na svaku od aplikacija dva puta: jednom na početku radnog dana i jednom nakon pauze, tokom svakog
radnog dana će se:
<div class="abc-list">
# generisati ukupno <span class="spoiler" data-solution="text">nerešeno</span> različitih kriptografskih ključeva potrebnih za zaštitu web saobraćaja TLS-om svih web sesija (uneti broj)
# izvršiti <span class="spoiler" data-solution="text">nerešeno</span> razmena ključeva (uneti broj)
# Ako se između lokacija firme u Helsinkiju i Pragu za zaštitu podataka između radnika i web aplikacija koristi site-to-site IPsec sa main modom razmene koji se vrši svake prve nedelje u mesecu u 23:00 i quick modom koji se vrši svaki dan u ponoć i ne koristi se TLS na web aplikacijama, onda če se svaki dan izvršiti <span class="spoiler" data-solution="text">nerešeno</span> razmena ključeva. (uneti broj)
</div>

== 7. zadatak ==
Kod kojih od navedenih kriptografskih algoritama učestanost pojavljivanja simbola/slova u šifrovanom tekstu ima istu raspodelu kao učestanost
pojavljivanja slova u originalnom tekstu?
<div class="abc-list" data-solution="multiple">
# RSA algoritam
# <span class="solution">''Row transposition'' algoritam</span>
# ''Vigenere'' algoritam sa autokey poboljšanjem
# Rotor mašina/Enigma
# Monoalfabetska šifra sa Gausovim poboljšanjem
# <span class="solution">Monoalfabetska šifra</span>
# ''Playfair'' algoritam
# <span class="solution">''Rail-fence'' algoritam</span>
# ''Vigenere'' algoritam
# ''One-time pad''
# ''Hill''-ov algoritam
# <span class="solution">Cezarov algoritam</span>
</div>

== 8. zadatak ==
Data je šema El Gamalovog algoritma za digitalno potpisivanje (<math>m</math> je hash poruke M):
* <math> S_1 = \alpha^K mod q </math>
* <math> S_2 = K^{-1}\left( m - X_AS_1 \right) mod (q-1) </math>
Za ovako formiran digitalni potpis važi sledeće:
<div class="abc-list" data-solution="multiple">
# Vrednosti koje su potrebne prijemnoj strani za proveru digitalnog potpisa su: <math>K</math>, <math>\alpha</math> i <math>q</math>
# <span class="solution">Za jednu poruku M može da postoji više različitih ispravnih vrednosti digitalnog potpisa <math>(S_1, S_2)</math></span>
# <span class="solution">Vrednosti koje su potrebne prijemnoj strani za proveru digitalnog potpisa su: <math>\alpha</math>, <math>q</math> i <math>Y_A</math></span>
# Ukoliko se promeni poruka M, promeniće se vrednost celog digitalnog potpisa i <math>S_1</math> i <math>S_2</math>
# Potpis je ispravan ukoliko je <math>S1 = S2</math>
# <span class="solution">Ukoliko se promeni poruka M, promeniće se vrednost <math>S_2</math></span>
# Za jednu poruku M postoji tačno jedna ispravna vrednost digitalnog potpisa <math>(S_1, S_2)</math>
# Vrednosti koje su potrebne prijemnoj strani za proveru digitalnog potpisa su: <math>K</math>, <math>\alpha</math>, <math>q</math> i <math>Y_A</math></span>
# Ukoliko se promeni poruka M, promeniće se vrednost <math>S_1</math>
# Vrednosti koje su potrebne prijemnoj strani za proveru digitalnog potpisa su: <math>\alpha</math> i <math>q</math>
</div>

== 9. zadatak ==
Originalnu poruku 00111100b propustiti kroz SDES algoritam korišćenjem ključa 0011001100b. Detalji algoritma dati su u nastavku.
{| class="wikitable"
|+ PC1:
| 3 || 5 || 2 || 7 || 4 || 10 || 1 || 9 || 8 || 6
|}
Rotacija: 1. iteracija za 1, 2. iteracija za 2
{| class="wikitable"
|+ PC2:
| 6 || 3 || 7 || 4 || 8 || 5 || 10 || 9
|}
{| class="wikitable"
|+ IP:
| 2 || 6 || 3 || 1 || 4 || 8 || 5 || 7
|}
{| class="wikitable"
|+ IP<sup>-1</sup>:
| 4 || 1 || 3 || 5 || 7 || 2 || 8 || 6
|}
{| class="wikitable"
|+ E:
| 4 || 1 || 2 || 3 || 2 || 3 || 4 || 1
|}
{| class="wikitable"
|+ S1:
| 1 || 0 || 3 || 2
|-
| 3 || 2 || 1 || 0
|-
| 0 || 2 || 1 || 3
|-
| 3 || 1 || 0 || 2
|}
{| class="wikitable"
|+ S2:
| 0 || 1 || 2 || 3
|-
| 2 || 0 || 1 || 3
|-
| 3 || 0 || 1 || 2
|-
| 2 || 1 || 0 || 3
|}
{| class="wikitable"
|+ P:
| 2 || 4 || 3 || 1
|}
Napomena: Sve vrednosti pisati u binarnom obliku bez sufiksa "b".
<div class="abc-list">
# Koja je vrednost ključa prve iteracije <span class="spoiler" data-solution="text">01011100</span>
# Koja je vrednost ključa druge iteracije <span class="spoiler" data-solution="text">11000000</span>
# Koja je vrednost poruke nakon inicijalne permutacije <span class="spoiler" data-solution="text">01101010</span>
# Koja je vrednost poruke nakon prolaska kroz funkciju iteracije za prvu iteraciju <span class="spoiler" data-solution="text">11001010</span>
# Koja je vrednost poruke nakon prve iteracije <span class="spoiler" data-solution="text">10101100</span>
# Koja je vrednost šifrovane poruke <span class="spoiler" data-solution="text">11010001</span>
</div>
Objašnjenje: <span class="spoiler" data-solution="explanation">Pretpostavlja se da se u stavci pod d mislilo na izlaz <math>f_K</math> bloka, a u stavci pod e na izlaz <math>SW</math> bloka.</span>

== 10. zadatak ==
Na slici je dat deo PGP šeme na strani slanja za obezbeđivanje <span class="spoiler" data-solution="text">tajnosti</span> poruke.

Z predstavlja operaciju kompresije, a operacije EC i EP su operacije šifrovanja.
[[Датотека:ZP jul 2021 zadatak 10.svg|center|frame|PGP šema u desetom zadatku.]]
Ako stranu slanja označimo sa X, a stranu prijema sa Y onda:
<div class="abc-list" data-solution="select" data-options="Ks,PUx,PUy,PRx,PRy">
# na mestu označenom brojem 1 se koristi ključ <span class="spoiler">Ks</span>
# na mestu označenom brojem 2 se koristi ključ <span class="spoiler">PUy</span>
</div>
Ukoliko se šemom obezbeđuje i kompresija tada se poruka propušta kroz ZIP algoritam na poziciji <span class="spoiler" data-solution="text">A</span>

== 11. zadatak ==

== 12. zadatak ==
{{delimično rešeno}}
Za svaki od sledećih scenarija, odrediti o kom malicioznom softveru je reč.
<div class="abc-list" data-solution="select" data-options="logička bomba,zadnja vrata,zombi,keylogger,flooder,downloader,adware,ransomware">
# Dati maliciozni kod se propagira na druge mašine korišćenjem crva. Nakon propagacije, cilj datog softvera je da koristi zaraženu mašinu za napade na druge mašine. Maliciozni softver koji je opisan je <span class="spoiler">nerešeno</span>.
# Nikoli, studentu Elektrotehničkog fakulteta, poslat je mejl sa linkom ka sajtu preko kojeg može da preuzme desktop verziju eStudent aplikacije. Kada je Nikola preuzeo i pokrenuo aplikaciju, svi podaci sa Nikolinog računara su postali ograničeni samo na napadače, koji poseduju odgovarajući ključ. Maliciozni softver koji je Nikola iskoristio je <span class="spoiler">ransomware</span>.
# Marina je preko USBa postavila maliciozni softver na nastavnički računar u sale 309 u toku pauze između časova. Dok je trajao čas, nastavnik se prijavio na Moodle sistem kako bi studentima pokazao rešenja zadataka sa kolokvijuma. Maliciozni softver je zapamtio podatke koje je uneo nastavnik i omogućio Marini da vidi pitanja za popravni kolokvijum. Maliciozni softver koji je Marina iskoristila je <span class="spoiler">keylogger</span>. Koji tip napadača je Marina? <span class="spoiler" data-solution="text">nerešeno</span>
</div>

== 13. zadatak ==

[[Категорија:Рокови]]
[[Категорија:Заштита података]]

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

2023-02-13T11:22:07Z

Lukahrvacevic: /* Resen barrel shifter */

{{tocright}}
'''Питања''' на теоријском делу испита се, слично као на [[Рачунарске мреже 1/Питања|РМ1]], дохватају из корпуса питања и нису свим студентима иста, али долазе из сличних области. Испод су излистани неки задаци по категоријама питања.

== SystemVerilog ограничења ==
У оваквим задацима, једноставно, је дат SystemVerilog код са ограничењима на неке променљиве, и пита се нешто у вези са вредностима које та променљива може да има и њиховим вероватноћама појављивања.

=== 1. задатак ===
Које вредности може имати променљива <code>variable</code> из приказане класе <code>Constraints</code>:
<syntaxhighlight lang="systemverilog">
class Constraints;
rand bit [3:0] variable;

constraint c1 { variable <= 4'd9; }
constraint c2 { variable inside {[4:14]}; }
constraint c3 { ! (variable inside {4'h0, 4'h5}); }
endclass
</syntaxhighlight>
Могуће вредности, сортиране од најмање ка највећој, у децималном бројном систему, раздвојене запетом без пратећег размака, навести као одговор.

Напомена: Приказ очекиваног формата одговора за следеће произвољно одабране вредности 15, 2, 7 и 10 јесте:
2,7,10,15
'''Одговор:''' <span class="spoiler" data-solution="text">4,6,7,8,9</span>

=== 2. задатак ===
{{делимично решено}}
Дата је класа <code>Constraints</code>:
<syntaxhighlight lang="systemverilog">
class Constraints;
rand bit [2:0] variable;

constraint distribution { variable dist { 0:/20, 1:/30, [2:6]:/40, 7:/10 }; }
endclass
</syntaxhighlight>
Која је вероватноћа да променљива <code>variable</code> приликом генерисања псеудослучајне вредности добије вредност '''4'''? Вероватноћу представити као разломак у којем су бројилац и именилац узајамно прости бројеви.
<div data-solution="select" data-options="14,10,5,3,11,27,4,12,26,28,1,29,13">
* Бројилац: <span class="spoiler">нерешено</span>
* Именилац: <span class="spoiler">нерешено</span>
</div>

=== 3. задатак ===
Које вредности може имати променљива <code>v2</code> из приказане класе <code>Constraints</code>:
<syntaxhighlight lang="systemverilog">
class Constraints;
randc bit [3:0] v1;
randc bit [3:0] v2;

constraint c1 { v1 > 4'b0100; }
constraint c2 { ! (v1 inside {[4'h8:4'hF]}); }
constraint c3 { v2 == v1 * 2 + 1; }
endclass
</syntaxhighlight>
Могуће вредности, сортиране од најмање ка највећој, у децималном бројном систему, раздвојене запетом без пратећег размака, навести као одговор.

Напомена: Приказ очекиваног формата одговора за следеће произвољно одабране вредности 15, 2, 7 и 10 јесте:
2,7,10,15
'''Одговор:''' <span class="spoiler" data-solution="text">11,13,15</span>

=== 4. задатак ===
{{делимично решено}}
Дата је класа <code>Constraints</code>:
<syntaxhighlight lang="systemverilog">
class Constraints;
rand bit [2:0] variable;

constraint distribution { variable dist { 0:/20, 1:/30, [2:6]:/20, 7:/30 }; }
endclass
</syntaxhighlight>
Која је вероватноћа да променљива <code>variable</code> приликом генерисања псеудослучајне вредности добије вредност '''4'''? Вероватноћу представити као разломак у којем су бројилац и именилац узајамно прости бројеви.
<div data-solution="select" data-options="14,10,5,3,11,27,4,12,26,28,1,29,13">
* Бројилац: <span class="spoiler">нерешено</span>
* Именилац: <span class="spoiler">нерешено</span>
</div>

=== 5. задатак ===
{{делимично решено}}
Дата је класа <code>Constraints</code>:
<syntaxhighlight lang="systemverilog">
class Constraints;
rand bit [2:0] variable;

constraint distribution { variable dist { 0:/20, 1:/30, [2:6]:=20, 7:/30 }; }
endclass
</syntaxhighlight>
Која је вероватноћа да променљива <code>variable</code> приликом генерисања псеудослучајне вредности добије вредност '''4'''? Вероватноћу представити као разломак у којем су бројилац и именилац узајамно прости бројеви.
<div data-solution="select" data-options="14,10,5,3,11,27,4,12,26,28,1,29,13">
* Бројилац: <span class="spoiler">нерешено</span>
* Именилац: <span class="spoiler">нерешено</span>
</div>

== Сабирачи ==
У оваквим задацима обично је дат Verilog код одређеног сабирача (једног од типова као што су рађени на предавањима) и питају се ствари у вези са функционисањем тог сабирача.

=== 1. задатак ===
У наставку је дата имплементација једног осморазредног сабирача. О ком сабирачу се ради, ако се зна да модул <code>ripple_carry_adder_n</code> представља ''N''-разредни сабирач са серијским преносом, а да модул <code>multiplexer_2_1</code> представља двоулазни мултиплексер ширине ''N'' информационих улаза?
<syntaxhighlight lang="verilog">
module adder_8 (
input [7:0] a, b,
input carry_in,
output [7:0] sum,
output carry_out
);

wire carry_3_0, carry_3_1, carry_3;
wire [3:0] sum_low_0, sum_low_1, sum_low;

ripple_carry_adder_n #(4) rca_1 (a[3:0], b[3:0], 1'b0, sum_low_0, carry_3_0);
ripple_carry_adder_n #(4) rca_2 (a[3:0], b[3:0], 1'b1, sum_low_1, carry_3_1);

multiplexer_2_1 #(4) mpx_1 (sum_low_0, sum_low_1, carry_in, sum_low);

assign carry_3 = (carry_in & carry_3_1) | carry_3_0;

wire carry_7_0, carry_7_1, carry_7;
wire [3:0] sum_high_0, sum_high_1, sum_high;

ripple_carry_adder_n #(4) rca_3 (a[7:4], b[7:4], 1'b0, sum_high_0, carry_7_0);
ripple_carry_adder_n #(4) rca_4 (a[7:4], b[7:4], 1'b1, sum_high_1, carry_7_1);

multiplexer_2_1 #(4) mpx_2 (sum_high_0, sum_high_1, carry_3, sum_high);

assign carry_7 = carry_7_0 | (carry_3_0 & carry_7_1) | (carry_in & carry_3_1 & carry_7_1);

assign sum = {sum_high, sum_low};
assign carry_out = carry_7;

endmodule
</syntaxhighlight>
<div class="abc-list" data-solution="single">
# Условни сабирач (''Conditional Sum Adder'')
# Сабирач са серијским преносом (''Ripple Carry Adder'')
# Сабирач са чувањем преноса (''Carry Save Adder'')
# <span class="solution">Сабирач на основу бита преноса (''Carry Select Adder'')</span>
# Сабирач са паралелним преносом (''Carry Lookahead Adder'')
# Потпуни сабирач (''Full Adder'')
</div>
'''Објашњење:''' <span class="spoiler" data-solution="explanation">У коду се види карактеристични "осакаћени мултиплексер" код генерисања преноса <code>carry_3</code> и <code>carry_7</code>.</span>

=== 2. задатак ===
У наставку је дата непотпуна имплементација четвороразредног сабирача на основу бита преноса (''Carry Select Adder''). Допунити имплементацију, ако се зна да модул <code>ripple_carry_adder_n</code> представља ''N''-разредни сабирач са серијским преносом, а да модул <code>multiplexer_2_1</code> представља двоулазни мултиплексер ширине ''N'' информационих улаза?<sup>[sic]</sup>
<syntaxhighlight lang="verilog">
module carry_select_adder_4 (
input [3:0] a, b,
input carry_in,
output [3:0] sum,
output carry_out
);

wire carry_3_0, carry_3_1;
wire [3:0] sum_0, sum_1;

ripple_carry_adder_n #(4) rca_1 (a[3:0], b[3:0], БЕЛИНА_1, sum_0, БЕЛИНА_2);
ripple_carry_adder_n #(4) rca_2 (a[3:0], b[3:0], БЕЛИНА_3, sum_1, БЕЛИНА_4);

multiplexer_2_1 #(4) mpx_1 (sum_0, sum_1, carry_in, sum);

assign carry_out = (carry_in & carry_3_1) | carry_3_0;

endmodule
</syntaxhighlight>
<div class="abc-list" data-solution="select" data-options="carry_3_1,1'b1,sum,1'b0,carry_out,carry_in,carry_3_0,sum_0,sum_1">
# Белина 1: <span class="spoiler">1'b0</span>
# Белина 2: <span class="spoiler">carry_3_0</span>
# Белина 3: <span class="spoiler">1'b1</span>
# Белина 4: <span class="spoiler">carry_3_1</span>
</div>
'''Објашњење:''' <span class="spoiler" data-solution="explanation">Ово је само друга варијанта задатка изнад. Једном сабирачу се даје да рачуна као да је улазни пренос 0, а другом да је улазни пренос 1, па се њихови резултати смештају у одговарајуће сигнале.</span>

== Временски облици ==
У оваквим задацима дат је Verilog код са кашњењима и временски облици излазних сигнала у ''ModelSim'', па се студенти питају да препознају одговарајући временски облик.

=== 1. задатак ===
{{делимично решено}}
Који временски облик одговара следећем изворном коду:
<syntaxhighlight lang="verilog">
module delay_module_3 (
out1, out2, a, b, c, x, y, z
);

output reg out1, out2;
input a, b, c, x, y, z;
wire e, f, g;

always @(posedge a) out1 = #1 b & c;
always @(negedge a) out1 = #1 b | ~c;

always @(posedge x) out2 = #1 y ^ z;
always @(negedge x) out2 = #1 ~y;

endmodule

module top_display;

reg a, b, c, x, y, z;
wire o1, o2;
delay_module_3 d3(o1, o2, a, b, c, x, y, z);

initial begin
a = 1'b0; b = 1'b0; c = 1'b0; x = 1'b0; y = 1'b0; z = 1'b0;
#1 b = 1'b1;
#2 a = 1'b1; y = 1'b1;
#0 c = 1'b1;
#2 x = 1'b1;
#2 a = 1'b0;
#1 b = 1'b0;
#3 x = 1'b0;
#0 y = 1'b0;
#0 $finish;
end

endmodule
</syntaxhighlight>
<div class="abc-list" data-solution="single">
# [[Датотека:VLSI zadaci vremenski oblik 9.jpg|link=]]
# [[Датотека:VLSI zadaci vremenski oblik 10.jpg|link=]]
# [[Датотека:VLSI zadaci vremenski oblik 11.jpg|link=]]
# [[Датотека:VLSI zadaci vremenski oblik 12.jpg|link=]]
# Ниједан од понуђених временских облика.
</div>

== Померачи ==
У оваквим задацима дат је Фанел или Барел померач са одређеним карактеристикама, и траже се сви његови међурезултати.

=== 1. задатак ===
Дат је Фанел померач (''Funnel Shifter'') са дванаестобитним улазом и петобитним излазом. Допунити вредности добијене у сваком од корака овог померача као и вредност излзаног податка за следеће улазне вредности:
<div data-solution="select" data-options="29,16,1A,27,7,14,5A,13,D,B,A7,9">
* Улазни податак: 5A7
* Контролни сигнал (број померања удесно): 4
* Први корак: <span class="spoiler">5A</span>
* Други корак: <span class="spoiler">1A</span>
* Трећи корак: <span class="spoiler">1A</span>
* Излазни податак: <span class="spoiler">1A</span>
</div>
Све вредности су написане у хексадецималном бројном систему.

=== 2. задатак ===
{{делимично решено}}
Дат је Барел померач (''Barrel Shifter'') са осмобитним улазом и осмобитним излазом. Допунити вредности добијене у сваком од корака овог померача као и вредност излзаног податка за следеће улазне вредности:
<div data-solution="select" data-options="5E,F2,97,79,CB,E5,2F">
* Улазни податак: 79
* Контролни сигнал (број померања удесно): 7
* Први корак: <span class="spoiler">97</span>
* Други корак: <span class="spoiler">E5</span>
* Трећи корак: <span class="spoiler">F2</span>
* Излазни податак: <span class="spoiler">F2</span>
</div>
Све вредности су написане у хексадецималном бројном систему.

== Верификација без UVM ==
У оваквим задацима дат је код из примера верификације без коришћења UVM стандарда са вежби и пита се шта се тачно дешава у коду и зашто.

=== 1. задатак ===
У наставку је дат део кода ''Driver''-a.
<syntaxhighlight lang="systemverilog">
class Driver;

virtual reg8_if vif;
mailbox mbx;
event done;

task run();
@(posedge vif.clk);
forever begin
dut_item item;
mbx.get(item);
// ...
@(posedge vif.clk);
->done;
end
endtask

endclass
</syntaxhighlight>
Koja класа чека на догађај <code>done</code> који се овде окида?

Напомена: Сматрати да се процес верификације врши без коришћења UVM стандарда.
<div class="abc-list" data-solution="single">
# ''Driver''
# <span class="solution">''Generator''</span>
# ''Monitor''
# ''Scoreboard''
</div>
'''Објашњење:''' <span class="spoiler" data-solution="explanation">Први пример са вежби. Генератор чека на овај догађај како не би генерисао више предмета него што драјвер може да конзумира.</span>

=== 2. задатак ===
У наставку је дат део кода ''Driver''-a.
<syntaxhighlight lang="systemverilog">
class Driver;

virtual reg8_if vif;
mailbox mbx;
event done;

task run();
@(posedge vif.clk);
forever begin
dut_item item;
mbx.get(item);
// ...
@(posedge vif.clk);
->done;
end
endtask

endclass
</syntaxhighlight>
Koja класа поставља <code>item</code> у ''mailbox'' који се овде дохвата?

Напомена: Сматрати да се процес верификације врши без коришћења UVM стандарда.
<div class="abc-list" data-solution="single">
# ''Driver''
# <span class="solution">''Generator''</span>
# ''Monitor''
# ''Scoreboard''
</div>

== UVM ==
Ова питања се обично односе на било шта из UVM стандарда.

=== 1. задатак ===
Које класе наслеђују класу <code>uvm_transaction</code>?
<div class="abc-list" data-solution="multiple">
# <span class="solution"><code>uvm_sequence_item</code></span>
# <code>uvm_driver</code>
# <code>uvm_monitor</code>
# <code>uvm_sequencer</code>
# <code>uvm_test</code>
# <span class="solution"><code>uvm_sequence</code></span>
</div>

=== 2. задатак ===
Које фазе кроз које пролазе UVM компоненте се реализују као ''task'' уместо као функције?
<div class="abc-list" data-solution="multiple">
# build
# connect
# end of elaboration
# start of simulation
# <span class="solution">run</span>
# extract
# check
# report
</div>

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

Системски софтвер/Септембар 2022

2022-09-27T14:56:32Z

Lukahrvacevic: Pogresan addend

{{tocright}}
'''Испит из септембарског рока 2022.''' одржан је 14.09.
== 1. задатак ==
: Исти задатак се нашао на [[Системски софтвер/Јун 2022#1. задатак|јунском року 2022. године]]
=== Поставка ===
Посматра се процес асемблирања датог ивзорног асемблерског кода за ''amd64'' архитектуру. Резултат асемблирања је предметни програм по ''ELF'' формату. Приказати садржај (1) табеле симбола и (2) релокационих записа <u>строго поштујући школски формат и обавезно у складу са задатом нумерацијом симбола</u>.
<syntaxhighlight lang="asm">
.intel_syntax noprefix
.section .text
.global min, la1
min: enter 0, 0 # 0x00
mov rbx, la1 # 0x04
cmp rbx, [rbp]+0x12 # 0x0c
call var[rip] # 0x10
jle la1 # 0x16
mov rax, [rbp]+0x12 # 0x18
jmp la2 # 0x1c
la1: mov rax, rbx # 0x1e
la2: leave # 0x21
ret # 0x22

.data
.global var
.type var, @object
var:
.quad la1, la2-4
.end
</syntaxhighlight>

Напомена: хексадецимални бројеви наведени у коментару изворног асемблерског кода представљају померај до почетка инструкције у том реду гледано од почетка секције којој инструкција припада. Такође, усвојити претпоставку да је величина операционог кода:
* 2B за инструкцију <code>call</code> за ''PC'' релативно адресирање,
* 4B за инструкцију <code>mov</code> за апсолутно адресирање и
* 1B за инструкције <code>jle</code> и <code>jmp</code> за ''PC'' релативно адресирање.
=== Решење ===
Видети [[Системски софтвер/Јун 2022#1. задатак|овде]].
== 2. задатак ==
=== Поставка ===
Посматра се макро процесор са угњежденим макро дефиницијама, без угњеждених макро експанзија.
<div class="abc-list">
# Шта је резултат макро експанзије задатог текста?
# Приказати операције над стеком параматера према редоследу њиховог извођења користећи нотације ''PUSH(...)'' и ''POP(...)'' при чему уместо три тачкице треба навести листу вредности које се смештају или скидају са стека.
# Приказати операције над стеком аргумената према редоследу њиховог извођења користећи нотације ''PUSH(...)'' и ''POP(...)'' при чему уместо три тачкице треба навести листу вредности које се смештају или скидају са стека.
</div>
MCDEFN
M1 A, B, C D
M2 A, B, C
MCDEFN
M2 C, D, F
A, B, C, D, E
MCEND
M2 C, D, F
MCEND
M2 1, 2, 3
M1 4, 5, 6, 7
M1 4, 5, 6, 7
M2 1, 2, 3
=== Решење ===
a)

M2 1, 2, 3
M2 4, 5, 6
M2 6, 7, F
M2 4, 5, 6
M2 6, 7, F
4, 5, 1, 2, E

b)

PUSH(((1,0),A), ((1,1),B), ((1,2),C), ((1,3),D))
PUSH(((2,0),C), ((2,1),D), ((2,2),F))
POP(((2,0),C), ((2,1),D), ((2,2),F))
POP(((1,0),A), ((1,1),B), ((1,2),C), ((1,3),D))

c)

PUSH((0,4), (1,5), (2,6), (3,7))
POP((0,4), (1,5), (2,6), (3,7))
PUSH((0,4), (1,5), (2,6), (3,7))
POP((0,4), (1,5), (2,6), (3,7))
PUSH((0,1), (1,2), (2,3))
POP((0,1), (1,2), (2,3))

== 3. задатак ==
=== Поставка ===
Посматрају се два објектна програма <code>levi.o</code> и <code>desni.o</code> добијена помоћу ''GNU'' асемблера.
{| class="wikitable"
|
#shdr
Num Address Size Type Flags Name
1: 0000000 0052 PROGBITS AX .text
3: 0000000 0000 PROGBITS WA .data
4: 0000000 0012 NOBITS WA .bss
#.symtab
Num Value Size Type Bind Ndx Name
0: 0000000 0000 NOTYP LOC UND
1: 0000000 0000 SCTN LOC 1 .text
2: 0000000 0000 SCTN LOC 3 .data
3: 0000000 0000 SCTN LOC 4 .bss
4: 0000013 0000 FUNC GLOB 1 a
5: 0000010 0000 NOTYP GLOB 4 d
6: 0000000 0000 NOTYP GLOB UND c
#.rela.text
Offset Type Symbol Addend
0000004 R_X86_64_32S 4 (a) 0
000000b R_X86_64_PC32 6 (c) -4
||
#shdr
Num Address Size Type Flags Name
1: 0000000 000a PROGBITS AX .text
3: 0000000 0008 PROGBITS WA .data
5: 0000000 0016 NOBITS WA .bss
#.symtab
Num Value Size Type Bind Ndx Name
0: 0000000 0000 NOTYP LOC UND
1: 0000000 0000 SCTN LOC 1 .text
2: 0000000 0000 SCTN LOC 3 .data
3: 0000000 0000 SCTN LOC 5 .bss
4: 0000004 0000 NOTYP LOC 3 b
5: 0000008 0000 OBJCT GLOB 5 c
6: 0000000 0000 NOTYP GLOB UND a
#.rela.text
Offset Type Symbol Addend
0000003 R_X86_64_PC32 6 (a) -4
#.rela.data
Offset Type Symbol Addend
0000002 R_X86_64_32 3 (.bss) 0
|}

Приказати излаз линкера <code>izlaz.o</code> тако да буде испоштовано све што је наведено у наставку:
* <u>строго поштујући школски формат и обавезно са нумерацијом у табели симбола према следећем редоследу</u>: <code>UND, .text, .data, .bss, b, c, d, a </code>
* повезивање се иницира следећом командом <code>ld --relocatable -o izlaz.o -T script.ld levi.o desni.o</code>
* линкерска скрипта <code>script.ld</code> има следећи садржај:
SECTIONS
{
.text : { *(.text) }
.data : { *(.data) }
.bss : { *.(bss) }
}
=== Решење ===

#shdr
Num Address Size Type Flags Name
1: 0000000 005c PROGBITS AX .text
3: 0000000 0008 PROGBITS WA .data
4: 0000000 0028 NOBITS WA .bss
#.symtab
Num Value Size Type Bind Ndx Name
0: 0000000 0000 NOTYP LOC UND
1: 0000000 0000 SCTN LOC 1 .text
2: 0000000 0000 SCTN LOC 3 .data
3: 0000000 0000 SCTN LOC 4 .bss
4: 0000004 0000 NOTYP LOC 3 b
5: 000001a 0000 OBJCT GLOB 5 c
6: 0000000 0000 NOTYP GLOB 4 d
7: 0000000 0000 FUNC GLOB 1 a
#.rela.text
Offset Type Symbol Addend
0000004 R_X86_64_32S 7 (a) 0
000000b R_X86_64_PC32 5 (c) -4
0000055 R_X86_64_PC32 7 (a) -4
#.rela.data
Offset Type Symbol Addend
0000002 R_X86_64_32 3 (.bss) 0

== 4. задатак ==
: Исти задатак се нашао на [[Системски софтвер/Јун 2022#4. задатак|јунском року 2022. године]]
=== Поставка ===
Посматра се ''JIT'' емулатор и емулирање следећег програма.
<div class="abc-list">
# Означити све блокове који ће у току рада емулатора бити преведени. За сваки преведени блок навести јединствену идентификацију у облику <code>'''B'''''<n>(<x>-<y>)</code> (<code><n></code> је <u>редни број блока у погледу тренутка његовог превођења при чему нумерација почиње од броја један</u>, <x> је редни број прве а <y> редни број последње линије изворног кода блока).
# Навести секвенцу извршавања. У секвенци извршавања могу се нађи само <code>GP</code> (сваки пут када се емулатор врати у главну петљу), <code>BH</code> (сваки пут када се позове функција која помаже у разрешавању скокова) и <code>'''B'''''<n></code> (сваки пут када се изврши дати блок у складу са ознакама из претходне тачке).
</div>

<syntaxhighlight lang="asm">
BEG ; line 1
LDI 2 ; line 2 ( PZ) A <= <V>
L1 SUB B ; line 3 (CPZ) A <= A - mem[<V>]
L2 ADD C ; line 4 (CPZ) A <= A + mem[<V>]
BNG L2 ; line 5 if (!flags[P]) PC <= <V>
BZE L3 ; line 6 if ( flags[Z]) PC <= <V>
SBI 2 ; line 7 (CPZ) A <= A - <V>
BNZ L1 ; line 8 if (!flags[Z]) PC <= <V>
L3 HLT ; line 9 stop execution
B DC 9 ; line 10
C DC 2 ; line 11
END ; line 12
</syntaxhighlight>
=== Решење ===
Видети [[Системски софтвер/Јун 2022#4. задатак|овде]].

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

Системски софтвер/Септембар 2022

2022-09-21T20:53:39Z

Lukahrvacevic: /* Решење */

{{tocright}}
'''Испит из септембарског рока 2022.''' одржан је 14.09.
== 1. задатак ==
=== Поставка ===
Посматра се процес асемблирања датог ивзорног асемблерског кода за ''amd64'' архитектуру. Резултат асемблирања је предметни програм по ''ELF'' формату. Приказати садржај (1) табеле симбола и (2) релокационих записа <u>строго поштујући школски формат и обавезно у складу са задатом нумерацијом симбола</u>.
<syntaxhighlight lang="asm">
.intel_syntax noprefix
.section .text
.global min, la1
min: enter 0, 0 # 0x00
mov rbx, la1 # 0x04
cmp rbx, [rbp]+0x12 # 0x0c
call var[rip] # 0x10
jle la1 # 0x16
mov rax, [rbp]+0x12 # 0x18
jmp la2 # 0x1c
la1: mov rax, rbx # 0x1e
la2: leave # 0x21
ret # 0x22

.data
.global var
.type var, @object
var:
.quad la1, la2-4
.end
</syntaxhighlight>

Напомена: хексадецимални бројеви наведени у коментару изворног асемблерског кода представљају померај до почетка инструкције у том реду гледано од почетка секције којој инструкција припада. Такође, усвојити претпоставку да је величина операционог кода:
* 2B за инструкцију <code>call</code> за ''PC'' релативно адресирање,
* 4B за инструкцију <code>mov</code> за апсолутно адресирање и
* 1B за инструкције <code>jle</code> и <code>jmp</code> за ''PC'' релативно адресирање.
=== Решење ===
Видети [[Системски софтвер/Јун 2022#1. задатак|овде]].
== 2. задатак ==
=== Поставка ===
Посматра се макро процесор са угњежденим макро дефиницијама, без угњеждених макро експанзија.
<div class="abc-list">
# Шта је резултат макро експанзије задатог текста?
# Приказати операције над стеком параматера према редоследу њиховог извођења користећи нотације ''PUSH(...)'' и ''POP(...)'' при чему уместо три тачкице треба навести листу вредности које се смештају или скидају са стека.
# Приказати операције над стеком аргумената према редоследу њиховог извођења користећи нотације ''PUSH(...)'' и ''POP(...)'' при чему уместо три тачкице треба навести листу вредности које се смештају или скидају са стека.
</div>
MCDEFN
M1 A, B, C D
M2 A, B, C
MCDEFN
M2 C, D, F
A, B, C, D, E
MCEND
M2 C, D, F
MCEND
M2 1, 2, 3
M1 4, 5, 6, 7
M1 4, 5, 6, 7
M2 1, 2, 3
=== Решење ===

a)

M2 1, 2, 3
M2 4, 5, 6
M2 6, 7, F
M2 4, 5, 6
M2 6, 7, F
4, 5, 1, 2, E

b)

PUSH(((1,0),A), ((1,1),B), ((1,2),C), ((1,3),D))
PUSH(((2,0),C), ((2,1),D), ((2,2),F))
POP(((2,0),C), ((2,1),D), ((2,2),F))
POP(((1,0),A), ((1,1),B), ((1,2),C), ((1,3),D))

c)

PUSH((0,4), (1,5), (2,6), (3,7))
POP((0,4), (1,5), (2,6), (3,7))
PUSH((0,4), (1,5), (2,6), (3,7))
POP((0,4), (1,5), (2,6), (3,7))
PUSH((0,1), (1,2), (2,3))
POP((0,1), (1,2), (2,3))

== 3. задатак ==
=== Поставка ===
Посматрају се два објектна програма <code>levi.o</code> и <code>desni.o</code> добијена помоћу ''GNU'' асемблера.
{| class="wikitable"
|
#shdr
Num Address Size Type Flags Name
1: 0000000 0052 PROGBITS AX .text
3: 0000000 0000 PROGBITS WA .data
4: 0000000 0012 NOBITS WA .bss
#.symtab
Num Value Size Type Bind Ndx Name
0: 0000000 0000 NOTYP LOC UND
1: 0000000 0000 SCTN LOC 1 .text
2: 0000000 0000 SCTN LOC 3 .data
3: 0000000 0000 SCTN LOC 4 .bss
4: 0000013 0000 FUNC GLOB 1 a
5: 0000010 0000 NOTYP GLOB 4 d
6: 0000000 0000 NOTYP GLOB UND c
#.rela.text
Offset Type Symbol Addend
0000004 R_X86_64_32S 4 (a) 0
000000b R_X86_64_PC32 6 (c) -4
||
#shdr
Num Address Size Type Flags Name
1: 0000000 000a PROGBITS AX .text
3: 0000000 0008 PROGBITS WA .data
5: 0000000 0016 NOBITS WA .bss
#.symtab
Num Value Size Type Bind Ndx Name
0: 0000000 0000 NOTYP LOC UND
1: 0000000 0000 SCTN LOC 1 .text
2: 0000000 0000 SCTN LOC 3 .data
3: 0000000 0000 SCTN LOC 5 .bss
4: 0000004 0000 NOTYP LOC 3 b
5: 0000008 0000 OBJCT GLOB 5 c
6: 0000000 0000 NOTYP GLOB UND a
#.rela.text
Offset Type Symbol Addend
0000003 R_X86_64_PC32 6 (a) -4
#.rela.data
Offset Type Symbol Addend
0000002 R_X86_64_32 3 (.bss) 0
|}

Приказати излаз линкера <code>izlaz.o</code> тако да буде испоштовано све што је наведено у наставку:
* <u>строго поштујући школски формат и обавезно са нумерацијом у табели симбола према следећем редоследу</u>: <code>UND, .text, .data, .bss, b, c, d, a </code>
* повезивање се иницира следећом командом <code>ld --relocatable -o izlaz.o -T script.ld levi.o desni.o</code>
* линкерска скрипта <code>script.ld</code> има следећи садржај:
SECTIONS
{
.text : { *(.text) }
.data : { *(.data) }
.bss : { *.(bss) }
}
=== Решење ===

{| class="wikitable"
|
#shdr
Num Address Size Type Flags Name
1: 0000000 005c PROGBITS AX .text
3: 0000000 0008 PROGBITS WA .data
4: 0000000 0028 NOBITS WA .bss
#.symtab
Num Value Size Type Bind Ndx Name
0: 0000000 0000 NOTYP LOC UND
1: 0000000 0000 SCTN LOC 1 .text
2: 0000000 0000 SCTN LOC 3 .data
3: 0000000 0000 SCTN LOC 4 .bss
4: 0000004 0000 NOTYP LOC 3 b
5: 000001a 0000 OBJCT GLOB 5 c
6: 0000000 0000 NOTYP GLOB 4 d
7: 0000000 0000 FUNC GLOB 1 a
#.rela.text
Offset Type Symbol Addend
0000004 R_X86_64_32S 7 (a) -4
000000b R_X86_64_PC32 5 (c) -4
0000055 R_X86_64_PC32 7 (a) -4
#.rela.data
Offset Type Symbol Addend
0000002 R_X86_64_32 3 (.bss) 0
|}

== 4. задатак ==
: Исти задатак се нашао на [[Системски софтвер/Јун 2022#4. задатак|јунском року 2022. године]]
=== Поставка ===
Посматра се ''JIT'' емулатор и емулирање следећег програма.
<div class="abc-list">
# Означити све блокове који ће у току рада емулатора бити преведени. За сваки преведени блок навести јединствену идентификацију у облику <code>'''B'''''<n>(<x>-<y>)</code> (<code><n></code> је <u>редни број блока у погледу тренутка његовог превођења при чему нумерација почиње од броја један</u>, <x> је редни број прве а <y> редни број последње линије изворног кода блока).
# Навести секвенцу извршавања. У секвенци извршавања могу се нађи само <code>GP</code> (сваки пут када се емулатор врати у главну петљу), <code>BH</code> (сваки пут када се позове функција која помаже у разрешавању скокова) и <code>'''B'''''<n></code> (сваки пут када се изврши дати блок у складу са ознакама из претходне тачке).
</div>

<syntaxhighlight lang="asm">
BEG ; line 1
LDI 2 ; line 2 ( PZ) A <= <V>
L1 SUB B ; line 3 (CPZ) A <= A - mem[<V>]
L2 ADD C ; line 4 (CPZ) A <= A + mem[<V>]
BNG L2 ; line 5 if (!flags[P]) PC <= <V>
BZE L3 ; line 6 if ( flags[Z]) PC <= <V>
SBI 2 ; line 7 (CPZ) A <= A - <V>
BNZ L1 ; line 8 if (!flags[Z]) PC <= <V>
L3 HLT ; line 9 stop execution
B DC 9 ; line 10
C DC 2 ; line 11
END ; line 12
</syntaxhighlight>
=== Решење ===
Видети [[Системски софтвер/Јун 2022#4. задатак|овде]].

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

Системски софтвер/Септембар 2022

2022-09-21T20:52:27Z

Lukahrvacevic: /* Greska u trecem zadatku */

{{tocright}}
'''Испит из септембарског рока 2022.''' одржан је 14.09.
== 1. задатак ==
=== Поставка ===
Посматра се процес асемблирања датог ивзорног асемблерског кода за ''amd64'' архитектуру. Резултат асемблирања је предметни програм по ''ELF'' формату. Приказати садржај (1) табеле симбола и (2) релокационих записа <u>строго поштујући школски формат и обавезно у складу са задатом нумерацијом симбола</u>.
<syntaxhighlight lang="asm">
.intel_syntax noprefix
.section .text
.global min, la1
min: enter 0, 0 # 0x00
mov rbx, la1 # 0x04
cmp rbx, [rbp]+0x12 # 0x0c
call var[rip] # 0x10
jle la1 # 0x16
mov rax, [rbp]+0x12 # 0x18
jmp la2 # 0x1c
la1: mov rax, rbx # 0x1e
la2: leave # 0x21
ret # 0x22

.data
.global var
.type var, @object
var:
.quad la1, la2-4
.end
</syntaxhighlight>

Напомена: хексадецимални бројеви наведени у коментару изворног асемблерског кода представљају померај до почетка инструкције у том реду гледано од почетка секције којој инструкција припада. Такође, усвојити претпоставку да је величина операционог кода:
* 2B за инструкцију <code>call</code> за ''PC'' релативно адресирање,
* 4B за инструкцију <code>mov</code> за апсолутно адресирање и
* 1B за инструкције <code>jle</code> и <code>jmp</code> за ''PC'' релативно адресирање.
=== Решење ===
Видети [[Системски софтвер/Јун 2022#1. задатак|овде]].
== 2. задатак ==
=== Поставка ===
Посматра се макро процесор са угњежденим макро дефиницијама, без угњеждених макро експанзија.
<div class="abc-list">
# Шта је резултат макро експанзије задатог текста?
# Приказати операције над стеком параматера према редоследу њиховог извођења користећи нотације ''PUSH(...)'' и ''POP(...)'' при чему уместо три тачкице треба навести листу вредности које се смештају или скидају са стека.
# Приказати операције над стеком аргумената према редоследу њиховог извођења користећи нотације ''PUSH(...)'' и ''POP(...)'' при чему уместо три тачкице треба навести листу вредности које се смештају или скидају са стека.
</div>
MCDEFN
M1 A, B, C D
M2 A, B, C
MCDEFN
M2 C, D, F
A, B, C, D, E
MCEND
M2 C, D, F
MCEND
M2 1, 2, 3
M1 4, 5, 6, 7
M1 4, 5, 6, 7
M2 1, 2, 3
=== Решење ===

a)

M2 1, 2, 3
M2 4, 5, 6
M2 6, 7, F
M2 4, 5, 6
M2 6, 7, F
4, 5, 1, 2, E

b)

PUSH(((1,0),A), ((1,1),B), ((1,2),C), ((1,3),D))
PUSH(((2,0),C), ((2,1),D), ((2,2),F))
POP(((2,0),C), ((2,1),D), ((2,2),F))
POP(((1,0),A), ((1,1),B), ((1,2),C), ((1,3),D))

c)

PUSH((0,4), (1,5), (2,6), (3,7))
POP((0,4), (1,5), (2,6), (3,7))
PUSH((0,4), (1,5), (2,6), (3,7))
POP((0,4), (1,5), (2,6), (3,7))
PUSH((0,1), (1,2), (2,3))
POP((0,1), (1,2), (2,3))

== 3. задатак ==
=== Поставка ===
Посматрају се два објектна програма <code>levi.o</code> и <code>desni.o</code> добијена помоћу ''GNU'' асемблера.
{| class="wikitable"
|
#shdr
Num Address Size Type Flags Name
1: 0000000 0052 PROGBITS AX .text
3: 0000000 0000 PROGBITS WA .data
4: 0000000 0012 NOBITS WA .bss
#.symtab
Num Value Size Type Bind Ndx Name
0: 0000000 0000 NOTYP LOC UND
1: 0000000 0000 SCTN LOC 1 .text
2: 0000000 0000 SCTN LOC 3 .data
3: 0000000 0000 SCTN LOC 4 .bss
4: 0000013 0000 FUNC GLOB 1 a
5: 0000010 0000 NOTYP GLOB 4 d
6: 0000000 0000 NOTYP GLOB UND c
#.rela.text
Offset Type Symbol Addend
0000004 R_X86_64_32S 4 (a) 0
000000b R_X86_64_PC32 6 (c) -4
||
#shdr
Num Address Size Type Flags Name
1: 0000000 000a PROGBITS AX .text
3: 0000000 0008 PROGBITS WA .data
5: 0000000 0016 NOBITS WA .bss
#.symtab
Num Value Size Type Bind Ndx Name
0: 0000000 0000 NOTYP LOC UND
1: 0000000 0000 SCTN LOC 1 .text
2: 0000000 0000 SCTN LOC 3 .data
3: 0000000 0000 SCTN LOC 5 .bss
4: 0000004 0000 NOTYP LOC 3 b
5: 0000008 0000 OBJCT GLOB 5 c
6: 0000000 0000 NOTYP GLOB UND a
#.rela.text
Offset Type Symbol Addend
0000003 R_X86_64_PC32 6 (a) -4
#.rela.data
Offset Type Symbol Addend
0000002 R_X86_64_32 3 (.bss) 0
|}

Приказати излаз линкера <code>izlaz.o</code> тако да буде испоштовано све што је наведено у наставку:
* <u>строго поштујући школски формат и обавезно са нумерацијом у табели симбола према следећем редоследу</u>: <code>UND, .text, .data, .bss, b, c, d, a </code>
* повезивање се иницира следећом командом <code>ld --relocatable -o izlaz.o -T script.ld levi.o desni.o</code>
* линкерска скрипта <code>script.ld</code> има следећи садржај:
SECTIONS
{
.text : { *(.text) }
.data : { *(.data) }
.bss : { *.(bss) }
}
=== Решење ===

{| class="wikitable"
|
#shdr
Num Address Size Type Flags Name
1: 0000000 005c PROGBITS AX .text
3: 0000000 0008 PROGBITS WA .data
4: 0000000 0028 NOBITS WA .bss
#.symtab
Num Value Size Type Bind Ndx Name
0: 0000000 0000 NOTYP LOC UND
1: 0000000 0000 SCTN LOC 1 .text
2: 0000000 0000 SCTN LOC 3 .data
3: 0000000 0000 SCTN LOC 4 .bss
4: 0000004 0000 NOTYP LOC 3 b
5: 000001a 0000 OBJCT GLOB 5 c
6: 0000000 0000 NOTYP GLOB 4 d
7: 0000000 0000 NOTYP FUNC 1 a
#.rela.text
Offset Type Symbol Addend
0000004 R_X86_64_32S 7 (a) -4
000000b R_X86_64_PC32 5 (c) -4
0000055 R_X86_64_PC32 7 (a) -4
#.rela.data
Offset Type Symbol Addend
0000002 R_X86_64_32 3 (.bss) 0
|}

== 4. задатак ==
: Исти задатак се нашао на [[Системски софтвер/Јун 2022#4. задатак|јунском року 2022. године]]
=== Поставка ===
Посматра се ''JIT'' емулатор и емулирање следећег програма.
<div class="abc-list">
# Означити све блокове који ће у току рада емулатора бити преведени. За сваки преведени блок навести јединствену идентификацију у облику <code>'''B'''''<n>(<x>-<y>)</code> (<code><n></code> је <u>редни број блока у погледу тренутка његовог превођења при чему нумерација почиње од броја један</u>, <x> је редни број прве а <y> редни број последње линије изворног кода блока).
# Навести секвенцу извршавања. У секвенци извршавања могу се нађи само <code>GP</code> (сваки пут када се емулатор врати у главну петљу), <code>BH</code> (сваки пут када се позове функција која помаже у разрешавању скокова) и <code>'''B'''''<n></code> (сваки пут када се изврши дати блок у складу са ознакама из претходне тачке).
</div>

<syntaxhighlight lang="asm">
BEG ; line 1
LDI 2 ; line 2 ( PZ) A <= <V>
L1 SUB B ; line 3 (CPZ) A <= A - mem[<V>]
L2 ADD C ; line 4 (CPZ) A <= A + mem[<V>]
BNG L2 ; line 5 if (!flags[P]) PC <= <V>
BZE L3 ; line 6 if ( flags[Z]) PC <= <V>
SBI 2 ; line 7 (CPZ) A <= A - <V>
BNZ L1 ; line 8 if (!flags[Z]) PC <= <V>
L3 HLT ; line 9 stop execution
B DC 9 ; line 10
C DC 2 ; line 11
END ; line 12
</syntaxhighlight>
=== Решење ===
Видети [[Системски софтвер/Јун 2022#4. задатак|овде]].

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

Системски софтвер/Септембар 2022

2022-09-21T19:33:26Z

Lukahrvacevic: Resen septembarski rok

{{tocright}}
'''Испит из септембарског рока 2022.''' одржан је 14.09.
== 1. задатак ==
=== Поставка ===
Посматра се процес асемблирања датог ивзорног асемблерског кода за ''amd64'' архитектуру. Резултат асемблирања је предметни програм по ''ELF'' формату. Приказати садржај (1) табеле симбола и (2) релокационих записа <u>строго поштујући школски формат и обавезно у складу са задатом нумерацијом симбола</u>.
<syntaxhighlight lang="asm">
.intel_syntax noprefix
.section .text
.global min, la1
min: enter 0, 0 # 0x00
mov rbx, la1 # 0x04
cmp rbx, [rbp]+0x12 # 0x0c
call var[rip] # 0x10
jle la1 # 0x16
mov rax, [rbp]+0x12 # 0x18
jmp la2 # 0x1c
la1: mov rax, rbx # 0x1e
la2: leave # 0x21
ret # 0x22

.data
.global var
.type var, @object
var:
.quad la1, la2-4
.end
</syntaxhighlight>

Напомена: хексадецимални бројеви наведени у коментару изворног асемблерског кода представљају померај до почетка инструкције у том реду гледано од почетка секције којој инструкција припада. Такође, усвојити претпоставку да је величина операционог кода:
* 2B за инструкцију <code>call</code> за ''PC'' релативно адресирање,
* 4B за инструкцију <code>mov</code> за апсолутно адресирање и
* 1B за инструкције <code>jle</code> и <code>jmp</code> за ''PC'' релативно адресирање.
=== Решење ===
Видети [[Системски софтвер/Јун 2022#1. задатак|овде]].
== 2. задатак ==
=== Поставка ===
Посматра се макро процесор са угњежденим макро дефиницијама, без угњеждених макро експанзија.
<div class="abc-list">
# Шта је резултат макро експанзије задатог текста?
# Приказати операције над стеком параматера према редоследу њиховог извођења користећи нотације ''PUSH(...)'' и ''POP(...)'' при чему уместо три тачкице треба навести листу вредности које се смештају или скидају са стека.
# Приказати операције над стеком аргумената према редоследу њиховог извођења користећи нотације ''PUSH(...)'' и ''POP(...)'' при чему уместо три тачкице треба навести листу вредности које се смештају или скидају са стека.
</div>
MCDEFN
M1 A, B, C D
M2 A, B, C
MCDEFN
M2 C, D, F
A, B, C, D, E
MCEND
M2 C, D, F
MCEND
M2 1, 2, 3
M1 4, 5, 6, 7
M1 4, 5, 6, 7
M2 1, 2, 3
=== Решење ===

a)

M2 1, 2, 3
M2 4, 5, 6
M2 6, 7, F
M2 4, 5, 6
M2 6, 7, F
4, 5, 1, 2, E

b)

PUSH(((1,0),A), ((1,1),B), ((1,2),C), ((1,3),D))
PUSH(((2,0),C), ((2,1),D), ((2,2),F))
POP(((2,0),C), ((2,1),D), ((2,2),F))
POP(((1,0),A), ((1,1),B), ((1,2),C), ((1,3),D))

c)

PUSH((0,4), (1,5), (2,6), (3,7))
POP((0,4), (1,5), (2,6), (3,7))
PUSH((0,4), (1,5), (2,6), (3,7))
POP((0,4), (1,5), (2,6), (3,7))
PUSH((0,1), (1,2), (2,3))
POP((0,1), (1,2), (2,3))

== 3. задатак ==
=== Поставка ===
Посматрају се два објектна програма <code>levi.o</code> и <code>desni.o</code> добијена помоћу ''GNU'' асемблера.
{| class="wikitable"
|
#shdr
Num Address Size Type Flags Name
1: 0000000 0052 PROGBITS AX .text
3: 0000000 0000 PROGBITS WA .data
4: 0000000 0012 NOBITS WA .bss
#.symtab
Num Value Size Type Bind Ndx Name
0: 0000000 0000 NOTYP LOC UND
1: 0000000 0000 SCTN LOC 1 .text
2: 0000000 0000 SCTN LOC 3 .data
3: 0000000 0000 SCTN LOC 4 .bss
4: 0000013 0000 FUNC GLOB 1 a
5: 0000010 0000 NOTYP GLOB 4 d
6: 0000000 0000 NOTYP GLOB UND c
#.rela.text
Offset Type Symbol Addend
0000004 R_X86_64_32S 4 (a) 0
000000b R_X86_64_PC32 6 (c) -4
||
#shdr
Num Address Size Type Flags Name
1: 0000000 000a PROGBITS AX .text
3: 0000000 0008 PROGBITS WA .data
5: 0000000 0016 NOBITS WA .bss
#.symtab
Num Value Size Type Bind Ndx Name
0: 0000000 0000 NOTYP LOC UND
1: 0000000 0000 SCTN LOC 1 .text
2: 0000000 0000 SCTN LOC 3 .data
3: 0000000 0000 SCTN LOC 5 .bss
4: 0000004 0000 NOTYP LOC 3 b
5: 0000008 0000 OBJCT GLOB 5 c
6: 0000000 0000 NOTYP GLOB UND a
#.rela.text
Offset Type Symbol Addend
0000003 R_X86_64_PC32 6 (a) -4
#.rela.data
Offset Type Symbol Addend
0000002 R_X86_64_32 3 (.bss) 0
|}

Приказати излаз линкера <code>izlaz.o</code> тако да буде испоштовано све што је наведено у наставку:
* <u>строго поштујући школски формат и обавезно са нумерацијом у табели симбола према следећем редоследу</u>: <code>UND, .text, .data, .bss, b, c, d, a </code>
* повезивање се иницира следећом командом <code>ld --relocatable -o izlaz.o -T script.ld levi.o desni.o</code>
* линкерска скрипта <code>script.ld</code> има следећи садржај:
SECTIONS
{
.text : { *(.text) }
.data : { *(.data) }
.bss : { *.(bss) }
}
=== Решење ===

{| class="wikitable"
|
#shdr
Num Address Size Type Flags Name
1: 0000000 005c PROGBITS AX .text
3: 0000000 0008 PROGBITS WA .data
4: 0000000 0028 NOBITS WA .bss
#.symtab
Num Value Size Type Bind Ndx Name
0: 0000000 0000 NOTYP LOC UND
1: 0000000 0000 SCTN LOC 1 .text
2: 0000000 0000 SCTN LOC 3 .data
3: 0000000 0000 SCTN LOC 4 .bss
4: 0000004 0000 NOTYP LOC 3 b
5: 000001a 0000 OBJCT GLOB 5 c
6: 0000000 0000 NOTYP GLOB 4 d
7: 0000000 0000 NOTYP GLOB 1 a
#.rela.text
Offset Type Symbol Addend
0000004 R_X86_64_32S 7 (a) -4
000000b R_X86_64_PC32 5 (c) -4
0000055 R_X86_64_PC32 7 (a) -4
#.rela.data
Offset Type Symbol Addend
0000002 R_X86_64_32 3 (.bss) 0
|}

== 4. задатак ==
: Исти задатак се нашао на [[Системски софтвер/Јун 2022#4. задатак|јунском року 2022. године]]
=== Поставка ===
Посматра се ''JIT'' емулатор и емулирање следећег програма.
<div class="abc-list">
# Означити све блокове који ће у току рада емулатора бити преведени. За сваки преведени блок навести јединствену идентификацију у облику <code>'''B'''''<n>(<x>-<y>)</code> (<code><n></code> је <u>редни број блока у погледу тренутка његовог превођења при чему нумерација почиње од броја један</u>, <x> је редни број прве а <y> редни број последње линије изворног кода блока).
# Навести секвенцу извршавања. У секвенци извршавања могу се нађи само <code>GP</code> (сваки пут када се емулатор врати у главну петљу), <code>BH</code> (сваки пут када се позове функција која помаже у разрешавању скокова) и <code>'''B'''''<n></code> (сваки пут када се изврши дати блок у складу са ознакама из претходне тачке).
</div>

<syntaxhighlight lang="asm">
BEG ; line 1
LDI 2 ; line 2 ( PZ) A <= <V>
L1 SUB B ; line 3 (CPZ) A <= A - mem[<V>]
L2 ADD C ; line 4 (CPZ) A <= A + mem[<V>]
BNG L2 ; line 5 if (!flags[P]) PC <= <V>
BZE L3 ; line 6 if ( flags[Z]) PC <= <V>
SBI 2 ; line 7 (CPZ) A <= A - <V>
BNZ L1 ; line 8 if (!flags[Z]) PC <= <V>
L3 HLT ; line 9 stop execution
B DC 9 ; line 10
C DC 2 ; line 11
END ; line 12
</syntaxhighlight>
=== Решење ===
Видети [[Системски софтвер/Јун 2022#4. задатак|овде]].

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

КДП/Јун 2020

2022-07-16T16:56:38Z

Lukahrvacevic: Skidanje taga delimicno reseno

{{tocright}}
Поставка овог рока може се наћи са [https://rti.etf.bg.ac.rs/rti/ir3kdp/rokovi/kdp20.zip странице предмета] (зипована).

== 1. задатак ==
=== Поставка ===
Андерсенов алгоритам за N процеса реализован помоћу ''addAndGet'' операције. Уколико би ''addAndGet'' операција имала следећи ефекат: <code>addAndGet(var, incr) : < var = var + incr; return(var); ></code>, да ли је могуће направити ''Fine grain'' решење, полазећи од ''Coarse grain'' решења (написати га), и ако је могуће – направите га.

=== Решење ===
''Coarse-grain'' решење:
<syntaxhighlight lang="cpp">
const int N = 100;
bool flag[N];
int tail = 0;

void worker() {
while (true) {
< int index = tail; tail = (tail + 1) % N; >
< await(flag[index]); >
/* критична секција */
flag[index] = false;
flag[(index + 1) % N] = true;
/* некритична секција */
}
}
</syntaxhighlight>
''Fine-grain'' решење:
<syntaxhighlight lang="cpp">
const int N = 100;
bool flag[N];
int tail = 0;

void worker() {
while (true) {
int index = (addAndGet(tail, 1) - 1) % N;
while (!flag[index]) skip();
/* критична секција */
flag[index] = false;
flag[(index + 1) % N] = true;
/* некритична секција */
}
}
</syntaxhighlight>

== 2. задатак ==
=== Поставка ===
Посматра се острво на коме људи могу да разгледају музеј о диносаурусима и парк за живим примерцима (''The Jurassic Park Problem''). У парку постоји N безбедних возила која могу да приме по једног путника. У парк може долазити произвољан број посетилаца. На почетку посетилац слободно разгледа музеј са експонатима. Када заврши разгледање, прелази на део са живим диносаурусима, тако што сачека да се појави прво сигурно возило које ће га провести кроз парк. Када наиђе слободно возило, посетилац прелази на вожњу по парку која траје неко време. На крају вожње посетилац напушта парк (може некад да се врати), а возило се враћа да прими следећег посетиоца. Уколико су сва возила заузета, посетилац који жели да иде у обилазак чека слободно возило. Уколико постоји слободно возило, али не и посетилац који тренутно чека да уђе, онда возило чека. Користећи семафоре написати програме за посетиоце и возила, као и код за иницијализацију.

=== Решење ===
<syntaxhighlight lang="cpp">
const int N = 100;

sem carCount = N;
list<pair<sem*, sem*>> freeCars;
sem carMutex = 1;

void car() {
sem carSem = 0;
sem visitorSem = 0;
while (true) {
// Враћамо се назад на место (први пут, ово служи за иницијализацију)
carMutex.wait();
freeCars.push_back({&carSem, &visitorSem});
carMutex.signal();
carCount.signal();
carSem.wait();
// Посетилац се вози по парку
visitorSem.signal();
// Готова вожња по парку
carSem.wait();
}
}

void visitor() {
while (true) {
// Обилазак музеја
carCount.wait();
carMutex.wait();
sem* carSem = freeCars.front().first;
sem* visitorSem = freeCars.front().second;
freeCars.pop_front();
carSem->signal();
carMutex.signal();
// Вожња по парку
visitorSem->wait();
// Готова вожња по парку
carSem->signal();
// Посетилац је напустио парк и можда се некад врати
}
}
</syntaxhighlight>

== 3. задатак ==
{{делимично решено}}
=== Поставка ===
Објасните како се реализује монитор са ''Signal and Continue'' дисциплином, код кога је дозвољено да се из једне мониторске методе позива друга мониторска метода користећи семафоре. За сваку каракеристичну<sup>[sic]</sup> ситуацију (5 ситуацијa) дати основне компоненте кôда (као са предавања) и објасните функцију делова тог кôда. За сваку ситуацију посебно навести који семафори се користе, и од чега зависи број тих семафора.

=== Решење ===

== 4. задатак ==
{{делимично решено}}
=== Поставка ===
У неком обданишту постоји правило које каже да се на свака три детета мора наћи барем једна васпитачица (''The Child Care Problem''). Родитељ доводи једно или више деце у обданиште и чека све док се не појави место, како би оставио сву децу одједном и отишао. Родитељ такође може да одведе једно или више деце, такође одједном. Васпитачица долази на посао и сме да напусти обданиште само уколико то не нарушава правило. Мора се поштовати редослед доласка родитеља који остављају децу и васпитачица које одлазе са посла. Користећи условне критичне регионе, написати процедуре за родитеље који доводе децу, родитеље који одводе децу, васпитачице које долазе на посао и васпитачице које одлазе са посла. Иницијализовати почетне услове.

=== Решење ===

== 5. задатак ==
=== Поставка ===
Реализовати прстен од n процеса, који комуницирају асинхроним прослеђивањем порука коришћењем комуникационих канала и ''send'' и ''receive'' исказа, а код кога процес 0 генерише случајан низ од m природних бројева у интервалу од 1 до 20.000 завршен са ''sentinel'' вредношћу ''EONAT'' (нпр 20.001). Преосталих n-1 процеса одстрањују из низа све појаве првих n-1 простих бројева. Сваки процес има по један различит прост број за који је задужен. Након одстрањивања простих бројева, модификован низ се дистрибуира свим процесима. Обезбедити максималну конкурентност.

=== Решење ===

<syntaxhighlight lang="cpp">
const int N = ...;
const int m = ...;
const int EONAT = 20001;
chan values[N](int);

void proccess0(){
int array[m];

for(int i=0; i<m; i++) array[i] = rand(1,20000);

for(int i=0; i<m; i++) send values[1](array[i]);
send values[1](EONAT);

bool end = false;
int temp,index = 0;
while(!end){
receive values[0](temp);
if(temp == EONAT) end = true;
else array[index++] = temp;
}

for(int i=0; i<index; i++) send values[1](array[i]);
send values[1](EONAT);
}

void proccess(int id, int myNumber){
int array[m];

bool end = false;
int temp;
while(!end){
receive values[id](temp);
if(temp == EONAT) end = true;
else if(temp != myNumber) send values[(id+1)%N](temp);
}

end = false;
int index = 0;
while(!end){
receive values[id](temp);
if(temp == EONAT) end = true;
else{
array[index++] = temp;
if(id != N-1) send values[(id+1)%N](temp);
}
}
}

</syntaxhighlight>

== 6. задатак ==
{{делимично решено}}
=== Поставка ===
Посматра се скуп чворова у графу који могу да комуницирају само са својим суседима (''Distributed Pairing Problem''). Сваки чвор треба да нађе чвор са којим ће се упарити. На крају поступка упаривања сваки чвор ће или имати свог пара, или остати неупарен, али тако да ни једна два суседна чвора не остану неупарена. Написати програм за чвор користећи библиотеку C-Linda.

=== Решење ===

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

КДП/Јун 2020

2022-07-16T16:56:23Z

Lukahrvacevic: /* 5. задатак */

{{tocright}}
Поставка овог рока може се наћи са [https://rti.etf.bg.ac.rs/rti/ir3kdp/rokovi/kdp20.zip странице предмета] (зипована).

== 1. задатак ==
=== Поставка ===
Андерсенов алгоритам за N процеса реализован помоћу ''addAndGet'' операције. Уколико би ''addAndGet'' операција имала следећи ефекат: <code>addAndGet(var, incr) : < var = var + incr; return(var); ></code>, да ли је могуће направити ''Fine grain'' решење, полазећи од ''Coarse grain'' решења (написати га), и ако је могуће – направите га.

=== Решење ===
''Coarse-grain'' решење:
<syntaxhighlight lang="cpp">
const int N = 100;
bool flag[N];
int tail = 0;

void worker() {
while (true) {
< int index = tail; tail = (tail + 1) % N; >
< await(flag[index]); >
/* критична секција */
flag[index] = false;
flag[(index + 1) % N] = true;
/* некритична секција */
}
}
</syntaxhighlight>
''Fine-grain'' решење:
<syntaxhighlight lang="cpp">
const int N = 100;
bool flag[N];
int tail = 0;

void worker() {
while (true) {
int index = (addAndGet(tail, 1) - 1) % N;
while (!flag[index]) skip();
/* критична секција */
flag[index] = false;
flag[(index + 1) % N] = true;
/* некритична секција */
}
}
</syntaxhighlight>

== 2. задатак ==
=== Поставка ===
Посматра се острво на коме људи могу да разгледају музеј о диносаурусима и парк за живим примерцима (''The Jurassic Park Problem''). У парку постоји N безбедних возила која могу да приме по једног путника. У парк може долазити произвољан број посетилаца. На почетку посетилац слободно разгледа музеј са експонатима. Када заврши разгледање, прелази на део са живим диносаурусима, тако што сачека да се појави прво сигурно возило које ће га провести кроз парк. Када наиђе слободно возило, посетилац прелази на вожњу по парку која траје неко време. На крају вожње посетилац напушта парк (може некад да се врати), а возило се враћа да прими следећег посетиоца. Уколико су сва возила заузета, посетилац који жели да иде у обилазак чека слободно возило. Уколико постоји слободно возило, али не и посетилац који тренутно чека да уђе, онда возило чека. Користећи семафоре написати програме за посетиоце и возила, као и код за иницијализацију.

=== Решење ===
<syntaxhighlight lang="cpp">
const int N = 100;

sem carCount = N;
list<pair<sem*, sem*>> freeCars;
sem carMutex = 1;

void car() {
sem carSem = 0;
sem visitorSem = 0;
while (true) {
// Враћамо се назад на место (први пут, ово служи за иницијализацију)
carMutex.wait();
freeCars.push_back({&carSem, &visitorSem});
carMutex.signal();
carCount.signal();
carSem.wait();
// Посетилац се вози по парку
visitorSem.signal();
// Готова вожња по парку
carSem.wait();
}
}

void visitor() {
while (true) {
// Обилазак музеја
carCount.wait();
carMutex.wait();
sem* carSem = freeCars.front().first;
sem* visitorSem = freeCars.front().second;
freeCars.pop_front();
carSem->signal();
carMutex.signal();
// Вожња по парку
visitorSem->wait();
// Готова вожња по парку
carSem->signal();
// Посетилац је напустио парк и можда се некад врати
}
}
</syntaxhighlight>

== 3. задатак ==
{{делимично решено}}
=== Поставка ===
Објасните како се реализује монитор са ''Signal and Continue'' дисциплином, код кога је дозвољено да се из једне мониторске методе позива друга мониторска метода користећи семафоре. За сваку каракеристичну<sup>[sic]</sup> ситуацију (5 ситуацијa) дати основне компоненте кôда (као са предавања) и објасните функцију делова тог кôда. За сваку ситуацију посебно навести који семафори се користе, и од чега зависи број тих семафора.

=== Решење ===

== 4. задатак ==
{{делимично решено}}
=== Поставка ===
У неком обданишту постоји правило које каже да се на свака три детета мора наћи барем једна васпитачица (''The Child Care Problem''). Родитељ доводи једно или више деце у обданиште и чека све док се не појави место, како би оставио сву децу одједном и отишао. Родитељ такође може да одведе једно или више деце, такође одједном. Васпитачица долази на посао и сме да напусти обданиште само уколико то не нарушава правило. Мора се поштовати редослед доласка родитеља који остављају децу и васпитачица које одлазе са посла. Користећи условне критичне регионе, написати процедуре за родитеље који доводе децу, родитеље који одводе децу, васпитачице које долазе на посао и васпитачице које одлазе са посла. Иницијализовати почетне услове.

=== Решење ===

== 5. задатак ==
{{делимично решено}}
=== Поставка ===
Реализовати прстен од n процеса, који комуницирају асинхроним прослеђивањем порука коришћењем комуникационих канала и ''send'' и ''receive'' исказа, а код кога процес 0 генерише случајан низ од m природних бројева у интервалу од 1 до 20.000 завршен са ''sentinel'' вредношћу ''EONAT'' (нпр 20.001). Преосталих n-1 процеса одстрањују из низа све појаве првих n-1 простих бројева. Сваки процес има по један различит прост број за који је задужен. Након одстрањивања простих бројева, модификован низ се дистрибуира свим процесима. Обезбедити максималну конкурентност.

=== Решење ===

<syntaxhighlight lang="cpp">
const int N = ...;
const int m = ...;
const int EONAT = 20001;
chan values[N](int);

void proccess0(){
int array[m];

for(int i=0; i<m; i++) array[i] = rand(1,20000);

for(int i=0; i<m; i++) send values[1](array[i]);
send values[1](EONAT);

bool end = false;
int temp,index = 0;
while(!end){
receive values[0](temp);
if(temp == EONAT) end = true;
else array[index++] = temp;
}

for(int i=0; i<index; i++) send values[1](array[i]);
send values[1](EONAT);
}

void proccess(int id, int myNumber){
int array[m];

bool end = false;
int temp;
while(!end){
receive values[id](temp);
if(temp == EONAT) end = true;
else if(temp != myNumber) send values[(id+1)%N](temp);
}

end = false;
int index = 0;
while(!end){
receive values[id](temp);
if(temp == EONAT) end = true;
else{
array[index++] = temp;
if(id != N-1) send values[(id+1)%N](temp);
}
}
}

</syntaxhighlight>

== 6. задатак ==
{{делимично решено}}
=== Поставка ===
Посматра се скуп чворова у графу који могу да комуницирају само са својим суседима (''Distributed Pairing Problem''). Сваки чвор треба да нађе чвор са којим ће се упарити. На крају поступка упаривања сваки чвор ће или имати свог пара, или остати неупарен, али тако да ни једна два суседна чвора не остану неупарена. Написати програм за чвор користећи библиотеку C-Linda.

=== Решење ===

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

КДП/Јул 2020

2022-07-16T16:33:32Z

Lukahrvacevic: /* 3. задатак */

{{tocright}}
Поставка овог рока може се наћи са [https://rti.etf.bg.ac.rs/rti/ir3kdp/rokovi/2122/KDP_2022_feb.pdf странице предмета.]

== 1. задатак ==
{{делимично решено}}
=== Поставка ===
Користећи расподељене бинарне семафоре и технику предаје штафетне палице решити проблем читалаца и писаца (''Readers - Writers Problem'').

=== Решење ===

== 2. задатак ==
=== Поставка ===
Проблем изградње молекула воде (''The H2O Problem''). Написати монитор са ''signal and continue'' дисциплином за решавање овог проблема, под следећим условима. Атоми водоника, када желе да направе молекул воде, позивају мониторску процедуру <code>hReady()</code>, атоми кисеоника позивају мониторску процедуру <code>oReady()</code>. Последњи пристигли атом треба да позове мониторску процедуру <code>makeWater()</code>, након чијег завршетка сва три атома треба да заврше своје одговарајуће <code>hReady()</code> и <code>oReady()</code> процедуре. Не сме бити изгладњивања.

=== Решење ===
<syntaxhighlight lang="java">
class TheH2OProblem {
private Condition hQueue = new Condition();
private Condition oQueue = new Condition();
private int hCount = 0;
private int oCount = 0;
private int hTicket = 1;
private int oTicket = 1;
public synchronized void hReady() {
++hCount;
if (hCount >= 2 && oCount >= 1) {
makeWater();
hCount -= 2;
oCount -= 1;
hQueue.signal();
oQueue.signal();
} else {
hQueue.wait(hTicket++);
}
}
public synchronized void oReady() {
++oCount;
if (hCount >= 2 && oCount >= 1) {
makeWater();
hCount -= 2;
oCount -= 1;
hQueue.signal();
hQueue.signal();
} else {
oQueue.wait(oTicket++);
}
}
private void makeWater() {
// ...
}
}
</syntaxhighlight>

== 3. задатак ==
=== Поставка ===
Користећи активне мониторе решити проблем филозофа који ручавају (''The Dining Philosophers''). Филозофи могу да комуницирају искључиво са процесом координатором (централизовано решење). Обезбедити да филозоф који је пре затражио да једе пре и започиње са јелом. Написати код за филозофе и за процес координатор

=== Решење ===
Напомена: Због захтева да филозоф који је пре затражио да једе пре и започне са јелом иде се по строго ФИФО редоследу, и филозофи који су се заблокирали на чекању виљушке неће је добити све док сви филозофи који су затражили виљушку пре њих не добију своју, и из тог разлога је потребна while петља код отпуштања виљушке.
<syntaxhighlight lang="cpp">
const int N = ...;
enum op_kind{REQUEST,RELEASE};
chan request(int, op_kind kind, bool); //Poslednji parametar ukazuje na to da li filozof trazi levu ili desnu viljusku
chan reply[N](bool);

class Coordinator{
public:

void run(){
int philosopher;
op_kind kind;
bool left;
queue<pair<int,int>> waiting;
int forks[N] = {};
while(true){
receive request(philosopher, kind, left);
int fork = left ? philosopher : (philosopher+1)%N;
if(kind == REQUEST){
if(forks[fork] == 0){
forks[fork] = 1;
send reply[philosopher](true);
}
else{
waiting.push(make_pair(philosopher, fork));
}
}
else if(kind == RELEASE){
forks[fork] = 0;
while(!waiting.empty() && forks[waiting.front().second] == 0){
send reply[waiting.front().first](true);
waiting.pop();
}
}
}
}
}

void philosopher(int id){
bool status;

while(true){

//Think

send request(id, REQUEST, id!=0);
receive reply[id](status);
send request(id, REQUEST, id==0);
receive reply[id](status);

//Eat

send request(id, RELEASE, id!=0);
send request(id, RELEASE, id==0);

}
}
</syntaxhighlight>

== 4. задатак ==
{{делимично решено}}
=== Поставка ===
Посматра се семафор за регулацију саобраћаја на улици са једним пешачким прелазом. Када пешак стигне до пешачког прелаза, уколико је светло за пешаке зелено, он прелази улицу. Уколико је у моменту његовог доласка светло за пешаке црвено, он чека да се укључи зелено светло. Зелено светло за пешаке се укључује или након К секунди од појаве првог пешака који је затекао црвено светло, или након проласка C аутомобила од последњег активног зеленог светла за пешаке. Зелено светло за пешаке трајања G секунди се пали само уколико је испуњен неки од наведених услова и барем један пешак чека. Потребно је у језику CSP написати процесе пешака, аутомобила и семафора, уколико је познато да у систему постоји N аутомобила и T пешака. Доступна је функција <code>system_current_time</code> која враћа тренутно време система.

=== Решење ===

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

КДП/Јануар 2020

2022-07-16T16:09:57Z

Lukahrvacevic: /* Ne treba da stoje imena argumenata kod kanala */

{{tocright}}
'''Јануарски испит 2020. године''' одржан је 18. јануара. Поставка овог рока може се наћи са [https://rti.etf.bg.ac.rs/rti/ir3kdp/rokovi/kdp20.zip странице предмета] (зипована).

== 1. задатак ==
: ''Сличан задатак дошао је у [[КДП/Август 2021#1. zadatak|августу 2021. године]] са ''Signal and Continue'' дисциплином.''
=== Поставка ===
Потребно је реализовати семафор који поред стандардних атомских операција ''signal()'' и ''wait()'' има и атомске операције ''signal(n)'' и ''wait(n)'' која интерну семафорску променљиву атомски увећава односно умањује за ''n'' уколико је то могуће, уколико није чека док не буде били могуће. Потребно је решити проблем користећи мониторе који имају ''Signal and Wait'' дисциплину. Процес који је раније упутио захтев треба раније да обави своју операцију. Број процеса и максимална вредност ''n'' нису унапред познати. Условне променљиве су ''FIFO'' према тренутку доласка и немају приоритетну методу ''wait''.

=== Решење ===
<syntaxhighlight lang="java">
class Semaphore {
private int value;
private Queue<Integer> requests = new Queue<>();
private Condition queue = new Condition();
public Semaphore(int value) {
this.value = value;
}
public synchronized void wait(int num) {
if (value >= num) {
value -= num;
} else {
requests.insert(num);
queue.wait();
internalSignal();
}
}
public synchronized void signal(int num) {
value += num;
internalSignal();
}
public synchronized void wait() {
wait(1);
}
public synchronized void signal() {
signal(1);
}
private void internalSignal() {
if (requests.size() > 0 && value >= requests.top()) {
value -= requests.pop();
queue.signal();
}
}
}
</syntaxhighlight>

== 2. задатак ==
=== Поставка ===
Користећи семафоре написати програм који решава проблем путовања лифтом. Путник позива лифт са произвољног спрата. Када лифт стигне на неки спрат сви путници који су изразили жељу да сиђу на том спрату обавезно изађу. Након изласка путника сви путници који су чекали на улазак уђу у лифт и кажу на који спрат желе да пређу. Тек када се сви изјасне лифт прелази даље. Лифт редом обилази спратове и стаје само на оне где има путника који улазе или излазе. Може се претпоставити да постоји N спратова.

=== Решење ===
<syntaxhighlight lang="cpp">
struct Floor {
list<sem*> peopleEntering;
sem mutexEntering = 1;
list<sem*> peopleExiting;
sem mutexExiting = 1;
};

const int N = 10;
Floor floors[N];
sem liftSem = 0;

void person() {
sem personSem = 0;
int currentFloorIndex = rand() % N;
while (true) {
// Особа може да каже да хоће да изађе на истом спрату као тренутном
// Претпоставка: особа није глупа
int nextFloorIndex = rand() % N;
Floor& currentFloor = floors[currentFloorIndex];
Floor& nextFloor = floors[nextFloorIndex];
currentFloor.mutexEntering.wait();
currentFloor.peopleEntering.push_back(&personSem);
currentFloor.mutexEntering.signal();
// Чекамо да дође лифт
personSem.wait();
// Улазимо у лифт и бирамо на којем спрату стајемо
nextFloor.mutexExiting.wait();
nextFloor.peopleExiting.push_back(&personSem);
nextFloor.mutexExiting.signal();
liftSem.signal();
// Чекамо да лифт стигне на наш спрат
personSem.wait();
// Излазимо из лифта
liftSem.signal();
}
}

void lift() {
int currentFloorIndex = 0;
bool goingUp = true;
while (true) {
// Одређивање следећег спрата
// Претпоставка: лифт све време иде горе-доле, без обзира да ли га је неко звао
if (goingUp) {
if (++currentFloorIndex == N-1) {
goingUp = false;
}
} else {
if (--currentFloorIndex == 0) {
goingUp = true;
}
}
Floor& floor = floors[currentFloorIndex];
// Не морамо да чекамо на mutexExiting, јер се он заузима само када путници улазе
// што тренутно није случај
int countPeopleExiting = floor.peopleExiting.size();
// Задржавамо mutexEntering док не испразнимо листу, како нам не би ушао неочекивани путник
floor.mutexEntering.wait();
int countPeopleEntering = floor.peopleEntering.size();
if (countPeopleExiting == 0 && countPeopleEntering == 0) {
// Не стајемо на овом спрату
floor.mutexEntering.signal();
continue;
}
// Стајемо на овом спрату
// Пуштамо људе да изађу
for (int i = 0; i < countPeopleExiting; ++i) {
sem* personSem = floor.peopleExiting.front();
personSem->signal();
floor.peopleExiting.pop_front();
}
for (int i = 0; i < countPeopleExiting; ++i) {
liftSem.wait();
}
// Пуштамо људе да уђу
for (int i = 0; i < countPeopleEntering; ++i) {
sem* personSem = floor.peopleEntering.front();
personSem->signal();
floor.peopleEntering.pop_front();
}
for (int i = 0; i < countPeopleEntering; ++i) {
liftSem.wait();
}
floor.mutexEntering.signal();
// Настављамо на следећи спрат
}
}
</syntaxhighlight>

== 3. задатак ==
=== Поставка ===
Користећи технику активних монитора потребно је реализовати семафор који поред стандардних атомских операција ''signal()'' и ''wait()'' има и атомске операције ''signal(n)'' и ''wait(n)'' која интерну семафорску променљиву атомски увећава односно умањује за ''n'' уколико је то могуће, уколико није чека док не буде били могуће. Процес који је раније упутио захтев треба раније да обави своју операцију.

=== Решење ===
<syntaxhighlight lang="cpp">
enum op_kind{WAIT,SIGNAL,WAITN,SIGNALN};
chan request(int, op_kind, int);
chan reply[n](bool);

class Semaphore{
public:

void run(){
int clientID;
op_kind kind;
int n;
int tokens = 0;
queue<pair<int,int>> pending;
while(true){
receive request(clientID, kind, n);
if(kind == WAIT){
if(tokens<=0){
pending.push(make_pair(clientID, 1));
}
else{
tokens--;
send reply[clientID](true);
}
}
else if(kind == WAITN){
if(tokens<=n-1){
pending.push(make_pair(clientID, n));
}
else{
tokens = tokens-n;
send reply[clientID](true);
}
}
else if(kind == SIGNAL){
tokens++;
if(!pending.empty() && pending.front().second == tokens){
tokens = 0;
send reply[pending.front().first](true);
pending.pop();
}
}
else if(kind == SIGNALN){
tokens += n;
while(!pending.empty() && pending.front().second <= tokens){
tokens -= pending.front().second;
send reply[pending.front().first](true);
pending.pop();
}
}
}
}
}
</syntaxhighlight>

== 4. задатак ==
{{делимично решено}}
=== Поставка ===
У свемиру постоји N небеских тела која међусобно интерагују (''N Body Gravitational Problem''), по Њутновом закону гравитације. Свако тело интерагује са сваким, при чему размењују информације о позицији, брзини и вектору силе. Користећи CSP потребно је решити овај проблем користећи торбу послова за дохватање посла и синхронизацију на баријери у свакој итерацији. Потребно је реализовати следеће процесе: ''Worker'' (обавља израчунавање), ''Bag'' (обавља поделу посла) и ''Collector'' (обавља прикупљање резултата). Број процеса ''Worker'' није познат, али је познато да их има мање од N. Постоји тачно један процес ''Bag'' и тачно један процес ''Collector''.

=== Решење ===

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

КДП/Јануар 2020

2022-07-16T16:06:41Z

Lukahrvacevic: /* Решење */

{{tocright}}
'''Јануарски испит 2020. године''' одржан је 18. јануара. Поставка овог рока може се наћи са [https://rti.etf.bg.ac.rs/rti/ir3kdp/rokovi/kdp20.zip странице предмета] (зипована).

== 1. задатак ==
: ''Сличан задатак дошао је у [[КДП/Август 2021#1. zadatak|августу 2021. године]] са ''Signal and Continue'' дисциплином.''
=== Поставка ===
Потребно је реализовати семафор који поред стандардних атомских операција ''signal()'' и ''wait()'' има и атомске операције ''signal(n)'' и ''wait(n)'' која интерну семафорску променљиву атомски увећава односно умањује за ''n'' уколико је то могуће, уколико није чека док не буде били могуће. Потребно је решити проблем користећи мониторе који имају ''Signal and Wait'' дисциплину. Процес који је раније упутио захтев треба раније да обави своју операцију. Број процеса и максимална вредност ''n'' нису унапред познати. Условне променљиве су ''FIFO'' према тренутку доласка и немају приоритетну методу ''wait''.

=== Решење ===
<syntaxhighlight lang="java">
class Semaphore {
private int value;
private Queue<Integer> requests = new Queue<>();
private Condition queue = new Condition();
public Semaphore(int value) {
this.value = value;
}
public synchronized void wait(int num) {
if (value >= num) {
value -= num;
} else {
requests.insert(num);
queue.wait();
internalSignal();
}
}
public synchronized void signal(int num) {
value += num;
internalSignal();
}
public synchronized void wait() {
wait(1);
}
public synchronized void signal() {
signal(1);
}
private void internalSignal() {
if (requests.size() > 0 && value >= requests.top()) {
value -= requests.pop();
queue.signal();
}
}
}
</syntaxhighlight>

== 2. задатак ==
=== Поставка ===
Користећи семафоре написати програм који решава проблем путовања лифтом. Путник позива лифт са произвољног спрата. Када лифт стигне на неки спрат сви путници који су изразили жељу да сиђу на том спрату обавезно изађу. Након изласка путника сви путници који су чекали на улазак уђу у лифт и кажу на који спрат желе да пређу. Тек када се сви изјасне лифт прелази даље. Лифт редом обилази спратове и стаје само на оне где има путника који улазе или излазе. Може се претпоставити да постоји N спратова.

=== Решење ===
<syntaxhighlight lang="cpp">
struct Floor {
list<sem*> peopleEntering;
sem mutexEntering = 1;
list<sem*> peopleExiting;
sem mutexExiting = 1;
};

const int N = 10;
Floor floors[N];
sem liftSem = 0;

void person() {
sem personSem = 0;
int currentFloorIndex = rand() % N;
while (true) {
// Особа може да каже да хоће да изађе на истом спрату као тренутном
// Претпоставка: особа није глупа
int nextFloorIndex = rand() % N;
Floor& currentFloor = floors[currentFloorIndex];
Floor& nextFloor = floors[nextFloorIndex];
currentFloor.mutexEntering.wait();
currentFloor.peopleEntering.push_back(&personSem);
currentFloor.mutexEntering.signal();
// Чекамо да дође лифт
personSem.wait();
// Улазимо у лифт и бирамо на којем спрату стајемо
nextFloor.mutexExiting.wait();
nextFloor.peopleExiting.push_back(&personSem);
nextFloor.mutexExiting.signal();
liftSem.signal();
// Чекамо да лифт стигне на наш спрат
personSem.wait();
// Излазимо из лифта
liftSem.signal();
}
}

void lift() {
int currentFloorIndex = 0;
bool goingUp = true;
while (true) {
// Одређивање следећег спрата
// Претпоставка: лифт све време иде горе-доле, без обзира да ли га је неко звао
if (goingUp) {
if (++currentFloorIndex == N-1) {
goingUp = false;
}
} else {
if (--currentFloorIndex == 0) {
goingUp = true;
}
}
Floor& floor = floors[currentFloorIndex];
// Не морамо да чекамо на mutexExiting, јер се он заузима само када путници улазе
// што тренутно није случај
int countPeopleExiting = floor.peopleExiting.size();
// Задржавамо mutexEntering док не испразнимо листу, како нам не би ушао неочекивани путник
floor.mutexEntering.wait();
int countPeopleEntering = floor.peopleEntering.size();
if (countPeopleExiting == 0 && countPeopleEntering == 0) {
// Не стајемо на овом спрату
floor.mutexEntering.signal();
continue;
}
// Стајемо на овом спрату
// Пуштамо људе да изађу
for (int i = 0; i < countPeopleExiting; ++i) {
sem* personSem = floor.peopleExiting.front();
personSem->signal();
floor.peopleExiting.pop_front();
}
for (int i = 0; i < countPeopleExiting; ++i) {
liftSem.wait();
}
// Пуштамо људе да уђу
for (int i = 0; i < countPeopleEntering; ++i) {
sem* personSem = floor.peopleEntering.front();
personSem->signal();
floor.peopleEntering.pop_front();
}
for (int i = 0; i < countPeopleEntering; ++i) {
liftSem.wait();
}
floor.mutexEntering.signal();
// Настављамо на следећи спрат
}
}
</syntaxhighlight>

== 3. задатак ==
{{делимично решено}}
=== Поставка ===
Користећи технику активних монитора потребно је реализовати семафор који поред стандардних атомских операција ''signal()'' и ''wait()'' има и атомске операције ''signal(n)'' и ''wait(n)'' која интерну семафорску променљиву атомски увећава односно умањује за ''n'' уколико је то могуће, уколико није чека док не буде били могуће. Процес који је раније упутио захтев треба раније да обави своју операцију.

=== Решење ===
<syntaxhighlight lang="cpp">
enum op_kind{WAIT,SIGNAL,WAITN,SIGNALN};
chan request(int clientID, op_kind kind, int n);
chan reply[n](bool);

class Semaphore{
public:

void run(){
int clientID;
op_kind kind;
int n;
int tokens = 0;
queue<pair<int,int>> pending;
while(true){
receive request(clientID, kind, n);
if(kind == WAIT){
if(tokens<=0){
pending.push(make_pair(clientID, 1));
}
else{
tokens--;
send reply[clientID](true);
}
}
else if(kind == WAITN){
if(tokens<=n-1){
pending.push(make_pair(clientID, n));
}
else{
tokens = tokens-n;
send reply[clientID](true);
}
}
else if(kind == SIGNAL){
tokens++;
if(!pending.empty() && pending.front().second == tokens){
tokens = 0;
send reply[pending.front().first](true);
pending.pop();
}
}
else if(kind == SIGNALN){
tokens += n;
while(!pending.empty() && pending.front().second <= tokens){
tokens -= pending.front().second;
send reply[pending.front().first](true);
pending.pop();
}
}
}
}
}
</syntaxhighlight>

== 4. задатак ==
{{делимично решено}}
=== Поставка ===
У свемиру постоји N небеских тела која међусобно интерагују (''N Body Gravitational Problem''), по Њутновом закону гравитације. Свако тело интерагује са сваким, при чему размењују информације о позицији, брзини и вектору силе. Користећи CSP потребно је решити овај проблем користећи торбу послова за дохватање посла и синхронизацију на баријери у свакој итерацији. Потребно је реализовати следеће процесе: ''Worker'' (обавља израчунавање), ''Bag'' (обавља поделу посла) и ''Collector'' (обавља прикупљање резултата). Број процеса ''Worker'' није познат, али је познато да их има мање од N. Постоји тачно један процес ''Bag'' и тачно један процес ''Collector''.

=== Решење ===

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

КДП/К1 2018

2022-04-01T15:14:12Z

Lukahrvacevic: /* Komentari */

{{tocright}}
Поставка овог рока може се наћи са [https://rti.etf.bg.ac.rs/rti/ir3kdp/rokovi/kdp18.zip странице предмета] (зипована).

== 1. задатак ==
=== Поставка ===
Потребно је урадити синхронизацију на баријери која функционише на следећи начин: постоје два процеса координатора за по половину радних процеса (претпоставити паран број радних процеса) који треба да се синхронизују на баријери. Притом, та два процеса координатора прво закључују када су сви њихови процеси стигли до њихових интерних подбаријера и кроз поступак међусобне комуникације координатора утврђују када су сви радни процеси стигли до еквивалентне јединствене баријере. Након тога оба процеса координатора треба да дозволе радним процесима да прођу баријеру. Написати кôд радних процеса и оба процеса координатора.

=== Решење ===

<syntaxhighlight lang="cpp">
const int N=...;
sem arrive[N]={0};
sem pass[N]={0};
bool coordinator=false;
sem coordinatorSem=0;
sem mutex=0;

void coordinator1(){
for(int i=0; i<N/2; i++) arrive[i].wait();
mutex.wait();
if(coordinator){
coordinator=false;
mutex.signal();
coordinatorSem.signal();
}
else{
coordinator=true;
mutex.signal();
coordinatorSem.wait();
}
for(int i=0; i<N/2; i++) pass[i].signal();
}

void coordinator2(){
for(int i=N/2; i<N; i++) arrive[i].wait();
mutex.wait();
if(coordinator){
coordinator=false;
mutex.signal();
coordinatorSem.signal();
}
else{
coordinator=true;
mutex.signal();
coordinatorSem.wait();
}
for(int i=N/2; i<N; i++) pass[i].signal();
}

void process(int i){
while(true){
work();
arrive[i].signal();
pass[i].wait();
}
}
</syntaxhighlight>

== 2. задатак ==
=== Поставка ===
Негде у Африци постоји дубок кањон на чијим литицама живе бабуни (<i>The Baboons Crossing Problem</i>). Између две литице кањона постоји лијана преко које бабуни прелазе реку. Да би се избегао сукоб између бабуна у једном тренутку на лијани смеју да се нађу само бабуни који припадају једној страни кањона. Такође, лијана може да издржи највише 5 бабуна, иначе пуца. Користећи семафоре написати програм за бабуне са обе стране кањона.

=== Решење ===
<syntaxhighlight lang="cpp">
const int N=5;
int baboons=0;
int currentSide=0;
sem waiting[2]={0};
List<int> list;
sem mutex=0;

//side je 0 ili 1, u zavisnosti sa koje strane kanjona se nalazi
void baboon(int side){
mutex.wait();
if(baboons==0 || (currentSide==side && baboons<N && list.size()==0)){ //Uslov list.size()==0 da ne bi doslo do izgladnjivanja
currentSide=side;
baboons++;
mutex.signal();
}
else{
list.add(side);
mutex.signal();
waiting[side].wait();
}

cross();

mutex.wait();
baboons--;
if(list.size()>0){
if(list.get(0)==side){ //Ako je sledeci zablokiran kretao sa iste strane, moze da krene kada jedan babun predje na drugu stranu
list.pop(0);
baboons++;
waiting[side].signal();
}
else if(baboons==0){ //Ako je sledeci zablokiran kretao sa suprotne strane, moze da krene samo kada svi babuni sa prvobitne strane predju lijanu, i sa njim mozemo pustiti jos
currentSide=!side; // maksimalno 4(N-1) babuna sa iste strane ako su se svi zablokirali za redom
while(list.get(0)==(!side) && baboons<N){
list.pop(0);
baboons++;
waiting[!side].signal();
}
}
}
mutex.signal();
}
</syntaxhighlight>

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

КДП/К1 2018

2022-04-01T15:04:11Z

Lukahrvacevic: Dodata oba zadatka sa K1 2018

{{tocright}}
Поставка овог рока може се наћи са [https://rti.etf.bg.ac.rs/rti/ir3kdp/rokovi/kdp18.zip странице предмета] (зипована).

== 1. задатак ==
=== Поставка ===
Потребно је урадити синхронизацију на баријери која функционише на следећи начин: постоје два процеса координатора за по половину радних процеса (претпоставити паран број радних процеса) који треба да се синхронизују на баријери. Притом, та два процеса координатора прво закључују када су сви њихови процеси стигли до њихових интерних подбаријера и кроз поступак међусобне комуникације координатора утврђују када су сви радни процеси стигли до еквивалентне јединствене баријере. Након тога оба процеса координатора треба да дозволе радним процесима да прођу баријеру. Написати кôд радних процеса и оба процеса координатора.

=== Решење ===

<syntaxhighlight lang="cpp">
const int N=...;
sem arrive[N]={0};
sem pass[N]={0};
bool coordinator=false;
sem coordinatorSem=0;
sem mutex=0;

void coordinator1(){
for(int i=0; i<N/2; i++) arrive[i].wait();
mutex.wait();
if(coordinator){
coordinator=false;
mutex.signal();
coordinatorSem.signal();
}
else{
coordinator=true;
mutex.signal();
coordinatorSem.wait();
}
for(int i=0; i<N/2; i++) pass[i].signal();
}

void coordinator2(){
for(int i=N/2; i<N; i++) arrive[i].wait();
mutex.wait();
if(coordinator){
coordinator=false;
mutex.signal();
coordinatorSem.signal();
}
else{
coordinator=true;
mutex.signal();
coordinatorSem.wait();
}
for(int i=N/2; i<N; i++) pass[i].signal();
}

void process(int i){
while(true){
work();
arrive[i].signal();
pass[i].wait();
}
}
</syntaxhighlight>

== 2. задатак ==
=== Поставка ===
Негде у Африци постоји дубок кањон на чијим литицама живе бабуни (<i>The Baboons Crossing Problem</i>). Између две литице кањона постоји лијана преко које бабуни прелазе реку. Да би се избегао сукоб између бабуна у једном тренутку на лијани смеју да се нађу само бабуни који припадају једној страни кањона. Такође, лијана може да издржи највише 5 бабуна, иначе пуца. Користећи семафоре написати програм за бабуне са обе стране кањона.

=== Решење ===
<syntaxhighlight lang="cpp">
const int N=5;
int baboons=0;
int currentSide=0;
sem waiting[2]={0};
List<int> list;
sem mutex=0;

//side je 0 ili 1, u zavisnosti sa koje strane kanjona se nalazi
void baboon(int side){
mutex.wait();
if(baboons==0 || (currentSide==side && baboons<N && list.size()==0)){
currentSide=side;
baboons++;
mutex.signal();
}
else{
list.add(side);
mutex.signal();
waiting[side].wait();
}

cross();

mutex.wait();
baboons--;
if(list.size()>0){
if(list.get(0)==side){
list.pop(0);
baboons++;
waiting[side].signal();
}
else if(baboons==0){
currentSide=!side;
while(list.get(0)==(!side) && baboons<N){
list.pop(0);
baboons++;
waiting[!side].signal();
}
}
}
mutex.signal();
}
</syntaxhighlight>

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

КДП/К1 2020

2022-04-01T11:54:38Z

Lukahrvacevic: /* Prepravka indeksa semafora u signal() */

{{tocright}}
Поставка овог рока може се наћи са [https://rti.etf.bg.ac.rs/rti/ir3kdp/rokovi/kdp20.zip странице предмета] (зипована).

== 1. задатак ==
=== Поставка ===
Написати и објасните<sup>[sic]</sup> ''CLH'' алгоритам за критичну секцију (''coarse grain''). Реализовати (''fine grain'') верзију алгоритма уколико би на датом процесору постојала операција SWAP која би недељиво обављала замену вредности два операнда (<code>SWAP(var1, var2): < temp = var1; var1 = var2; var2 = temp; ></code>). Објаснити зашто је то правична (''fair'') критична секција.

=== Решење ===
''CLH'' алгоритам уланчава процесе који желе да уђу у критичну секцију у неку врсту уланчане листе, тако да сваки проверава да ли је онај пре њега и даље закључан и у тренутку када више не буде закључан улази у критичну секцију.
<syntaxhighlight lang="cpp">
Node* tail = nullptr;

void worker() {
while (true) {
Node* node = new Node();
node->locked = true;
< prev = tail; tail = node; >
< await (prev == nullptr || !prev->locked); >
// Критична секција
node->locked = false;
// Некритична секција
}
}
</syntaxhighlight>
Пошто је <code>prev</code> овде локална променљива и ту нема критичне референце, <code>await</code> се може заменити обичном петљом. Са друге стране, за атомску акцију <code>prev = tail; tail = node;</code> потребна нам је поменута SWAP инструкција:
<syntaxhighlight lang="cpp">
Node* tail = nullptr;

void worker() {
while (true) {
Node* node = new Node();
node->locked = true;
Node* prev = node;
SWAP(prev, tail);
while (prev != nullptr && prev->locked) skip();
// Критична секција
node->locked = false;
// Некритична секција
}
}
</syntaxhighlight>
Ова критична секција је правична јер ће први процес који уради замену (изврши SWAP инструкцију) бити први који ће ући у критичну секцију.

== 2. задатак ==
=== Поставка ===
Посматра се један паркинг. Постоји само једна рампа која служи и за улаз на паркинг, и за излаз са паркинга, кроз коју може пролазити само један аутомобил у једном тренутку. На паркингу има N места за паркирање. Аутомобили који улазе, могу да уђу, један по један, уколико има слободних места. Уколико нема слободног места, проверава се да ли има аутомобила који хоће да изађу. Ако након изласка свих аутомобила који желе да изађу и уласка аутомобила који су дошли пре њега за аутомобил неће бити места, он одлази у потрагу за другим паркингом. Аутомобили при изласку плаћају услуге паркинга и излазе један по један. На почетку предност на рампи имају аутомобили који излазе са паркинга. Након што кроз рампу изађе K узастопних аутомобила, приоритет се мења (додељује се већи приоритет онима који улазе). Након проласка K узастопних аутомобила који улазе, приоритет се поново мења. Ако нема аутомобила из смера који има приоритет, аутомобили који немају приоритетни смер смеју да пролазе кроз рампу. Коришћењем једног низа од 2N + 1 семафора направити методе за тражење дозвола за улаз и излаз и обавештавање о уласку и изласку аутомобила са паркинга. Није дозвољено користити помоћне структуре података ни додатне елементе за синхронизацију процеса. Аутомобили не смеју да се претичу.

=== Решење ===
<syntaxhighlight lang="cpp">
const int N = 100;
const int K = 50;

sem sems[2 * N + 1];
// Број слободних места на паркингу (аутомобили који чекају излаз су ослободили своје место)
int capacity = N;
// Број аутомобила који чекају на улазу
int entering = 0;
// Број аутомобила који чекају на излазу
int exiting = 0;
int enterTail = 0;
int enterHead = 0;
int exitTail = 0;
int exitHead = 0;
// true - излаз, false - улаз
bool priority = true;
int passed = 0;
sem& mutex = sems[2 * N];
bool requestEntrance() {
mutex.wait();
if (capacity - entering <= 0) {
mutex.signal();
return false;
}
++entering;
if (entering == 1 && exiting == 0) {
// Слободан пролаз
mutex.signal();
return true;
}
int semIndex = enterTail;
enterTail = (enterTail + 1) % N;
mutex.signal();
sems[semIndex].wait();
return true;
}
void requestExit() {
mutex.wait();
++capacity;
++exiting;
if (entering == 0 && exiting == 1) {
// Слободан пролаз
mutex.signal();
return;
}
int semIndex = exitTail + N;
exitTail = (exitTail + 1) % N;
mutex.signal();
sems[semIndex].wait();
}
void entered() {
mutex.wait();
--entering;
--capacity;
signal();
mutex.signal();
}
void exited() {
mutex.wait();
--exiting;
signal();
mutex.signal();
}
void signal() {
int semIndex = -1;
bool hasCapacity = (capacity - exiting) < N;
bool signalExit = (exiting > 0) && (priority || !hasCapacity || entering == 0);
bool signalEnter = (entering > 0 && hasCapacity) && (!priority || exiting == 0);
if (signalExit) {
semIndex = exitHead + N;
exitHead = (exitHead + 1) % N;
} else if (signalEnter) {
semIndex = enterHead;
enterHead = (enterHead + 1) % N;
}
if (semIndex >= 0) {
if (priority != signalExit) {
// Ако сада није изашао аутомобил из реда који је имао приоритет,
// ресетује се бројач узастопних аутомобила
passed = 0;
} else {
++passed;
}
if (passed == K) {
passed = 0;
priority = !priority;
}
sems[semIndex].signal();
}
}
void car() {
while (true) {
if (requestEntrance()) {
entered();
// ...
requestExit();
// pay();
exited();
}
}
}
</syntaxhighlight>

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

Неуралне мреже/Јануар 2019

2022-02-20T23:17:29Z

Lukahrvacevic: /* 1. zadatak */ Dodatno objasnjenje za poslednja dva

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

== 1. zadatak ==
Zaokružiti tačna tvrđenja (svaki tačan odgovor: +1 poen, svaki netačan odgovor: -0.5 poena, bez zaokruživanja: 0 poena):

=== Stavka a ===
''Stepen pripadanja'' konkretne vrednosti lingvističke varijable ''diskretnom'' fuzzy skupu je:
<div class="abc-list" data-solution="single">
# kontinualan fuzzy skup
# diskretan klasičan skup
# kontinualan klasičan skup
# <span class="solution">realna vrednost</span>
# kontinualna realna funkcija
# nijedno od ponuđenog
</div>

=== Stavka b ===
''Funkcija pripadanja'' lingvističke varijable ''kontinualnom'' fuzzy skupu je:
<div class="abc-list" data-solution="single">
# kontinualan fuzzy skup
# diskretan klasičan skup
# kontinualan klasičan skup
# realna vrednost
# <span class="solution">kontinualna realna funkcija</span>
# nijedno od ponuđenog
</div>

=== Stavka c ===
''Funkcija pripadanja'' lingvističke varijable ''diskretnom'' fuzzy skupu je:
<div class="abc-list" data-solution="single">
# kontinualan fuzzy skup
# diskretan klasičan skup
# kontinualan klasičan skup
# realna vrednost
# kontinualna realna funkcija
# <span class="solution">nijedno od ponuđenog</span>
</div>
Objašnjenje: <span class="spoiler" data-solution="explanation">Ovde bi kao odgovor moglo da dođe u obzir diskretna funkcija.</span>

=== Stavka d ===
''Podrška (support) kontinualnog'' fuzzy skupa je:
<div class="abc-list" data-solution="single">
# kontinualan fuzzy skup
# diskretan klasičan skup
# <span class="solution">kontinualan klasičan skup</span>
# realna vrednost
# kontinualna realna funkcija
# nijedno od ponuđenog
</div>

=== Stavka e ===
''<math>\alpha</math>-presek (<math>\alpha</math>-cut) diskretnog'' fuzzy skupa
<div class="abc-list" data-solution="single">
# kontinualan fuzzy skup
# <span class="solution">diskretan klasičan skup</span>
# kontinualan klasičan skup
# realna vrednost
# kontinualna realna funkcija
# nijedno od ponuđenog
</div>

=== Stavka f ===
Za ''kontinualan'' fuzzy skup <math>A</math>, <math>A^2</math> ("A na kvadrat") je:
<div class="abc-list" data-solution="single">
# <span class="solution">kontinualan fuzzy skup</span>
# diskretan klasičan skup
# kontinualan klasičan skup
# realna vrednost
# kontinualna realna funkcija
# nijedno od ponuđenog
</div>

=== Stavka g ===
Za ''diskretan'' fuzzy skup <math>A</math>, <math>A^2</math> ("A na kvadrat"):
<div class="abc-list" data-solution="single">
# kontinualan fuzzy skup
# diskretan klasičan skup
# kontinualan klasičan skup
# realna vrednost
# kontinualna realna funkcija
# <span class="solution">nijedno od ponuđenog</span>
</div>
Objašnjenje: <span class="spoiler" data-solution="explanation">Odgovor je diskretan fuzzy skup.</span>

=== Stavka h ===
U pravilu "if ''time'' is ''short'' then ''risk'' is ''high''" ''Sugenove'' mašine, ''short'' je:
<div class="abc-list" data-solution="single">
# diskretan fuzzy skup
# <span class="solution">kontinualan fuzzy skup</span>
# klasičan skup
# lingvistička varijabla
# nijedno od ponuđenog
</div>

=== Stavka i ===
U pravilu "if ''time'' is ''short'' then ''risk'' is ''high''" ''Mamdanijeve'' mašine, ''short'' je:
<div class="abc-list" data-solution="single">
# diskretan fuzzy skup
# <span class="solution">kontinualan fuzzy skup</span>
# klasičan skup
# lingvistička varijabla
# nijedno od ponuđenog
</div>
Objašnjenje: <span class="spoiler" data-solution="explanation">I kod Mamdanijeve i kod Sugenove mašine ulazni skupovi moraju biti kontinualni.</span>

=== Stavka j ===
Ako je rezultat izvršenja svih pravila ''Mamdanijeve'' mašine prazan skup, rezultat (maksimum) agregacije je:
<div class="abc-list" data-solution="single">
# prazan diskretan fuzzy skup
# <span class="solution">prazan kontinualan fuzzy skup</span>
# prazan klasičan skup
# realna vrednost 0
# nijedno od ponuđenog
</div>

=== Stavka k ===
Ako je rezultat izvršenja svih pravila ''Sugenove'' mašine prazan skup, rezultat (maksimum) agregacije je:
<div class="abc-list" data-solution="single">
# <span class="solution">prazan diskretan fuzzy skup</span>
# prazan kontinualan fuzzy skup
# prazan klasičan skup
# realna vrednost 0
# nijedno od ponuđenog
</div>

=== Stavka l ===
Rezultat Center of Gravity defazifikacije praznog fuzzy skupa je:
<div class="abc-list" data-solution="single">
# prazan diskretan fuzzy skup
# prazan kontinualan fuzzy skup
# prazan klasičan skup
# realna vrednost 0
# <span class="solution">nijedno od ponuđenog</span>
</div>
Objašnjenje: <span class="spoiler" data-solution="explanation">Defazifikacija praznog fuzzy skupa proizvodi nedefinisano ponašanje(zbog deljenja sa nulom).</span>

=== Stavka m ===
Rezultat Weighted Average defazifikacije praznog fuzzy skupa je:
<div class="abc-list" data-solution="single">
# prazan diskretan fuzzy skup
# prazan kontinualan fuzzy skup
# prazan klasičan skup
# realna vrednost 0
# <span class="solution">nijedno od ponuđenog</span>
</div>
Objašnjenje: <span class="spoiler" data-solution="explanation">Defazifikacija praznog fuzzy skupa proizvodi nedefinisano ponašanje(zbog deljenja sa nulom).</span>

== 2. zadatak ==
Za kontinualne fuzzy skupove <math>A</math>, <math>B</math> i <math>C</math> definisane su funkcije pripadanja:
* <math>\mu_A(x) = \left\{\begin{array}{ll}
1 + \frac{x}{4}, & -4 \leq x \leq 0 \\
1 - \frac{x}{4}, & 0 < x \leq 4
\end{array}\right.</math>
* <math>\mu_B(x) = \left\{\begin{array}{ll}
2 + \frac{x}{2}, & -4 \leq x < -2 \\
1, & -2 \leq x < 0 \\
1 - \frac{x}{2}, & 0 \leq x < 2 \\
0 & 2 \leq x \leq 4
\end{array}\right.</math>
* <math>\mu_C(x) = \left\{\begin{array}{ll}
y + 1, & -1 \leq y < 0 \\
1, & 0 \leq y \leq 1 \\
\frac{3-y}{2}, & 1 < y \leq 3
\end{array}\right.</math>
<div class="abc-list">
# Skicirati funkcije pripadanja za fuzzy skupove: (standardna) unija <math>A \cup B</math>, (standardni) komplement <math>\neg B</math> i (standardni) komplement <math>\neg C</math>.
# Ako se primenjuje '''scaling implikacija''', a konkretno je <math>x = 1</math>, skicirati rezultat izvršavanja pravila <math>\text{R1: if}\ x\ \text{is}\ \neg B\ \text{then}\ y\ \text{is}\ C</math>.
# Ako se primenjuje '''scaling implikacija''', rezultat izvršavanja pravila <math>\text{R1: if}\ x\ \text{is}\ \neg B\ \text{then}\ y\ \text{is}\ C</math> biće ''prazan skup'' za opseg konkretnih vrednosti ulazne varijable: <span class="spoiler" data-solution="plain">Sa grafika za <math>\neg B</math> vidimo da će biti prazan skup za opseg <math>x \in [-2,0]</math></span>
# Ako se primenjuje '''clipping implikacija''', a konkretno je <math>x = -1</math>, skicirati rezultat izvršavanja pravila <math>\text{R1: if}\ x\ \text{is}\ A\ \text{then}\ y\ \text{is}\ \neg C</math>.
</div>
<gallery class="spoiler" data-solution="plain">
NM januar 2019 zadatak 2 mua.svg | <math>\mu_A(x)</math>
NM januar 2019 zadatak 2 mub.svg | <math>\mu_B(x)</math>
NM januar 2019 zadatak 2 muc.svg | <math>\mu_C(x)</math>
NM januar 2019 zadatak 2a A unija B.svg | Zadatak 2a, <math>A \cup B</math>
NM januar 2019 zadatak 2a komplement B.svg | Zadatak 2a, <math>\neg B</math>
NM januar 2019 zadatak 2a komplement C.svg | Zadatak 2a, <math>\neg C</math>
NM januar 2019 zadatak 2b.svg | Zadatak 2b
NM januar 2019 zadatak 2d.svg | Zadatak 2d
</gallery>

== 3. zadatak ==
Za diskretne fuzzy skupove <math>A</math>, <math>B</math> i <math>C</math> definisane su funkcije pripadanja:
* <math>\mu_A(z) = 0.1|50 + 0.3|-30 + 0.1|-10 + 0.1|10 + 0.0|30</math>
* <math>\mu_B(z) = 0.0|50 + 0.4|-30 + 0.6|-10 + 0.7|10 + 0.5|30</math>
* <math>\mu_C(z) = 0.5|50 + 1.0|-30 + 0.8|-10 + 0.5|10 + 0.1|30</math>
<div class="abc-list">
# Ako je presek skupova definisan kao ''proizvod'' pripadnosti, tada je za <math>D = A \cap B \cap C</math>:
#: <math>\mu_D(z) = </math> <span class="spoiler" data-solution="plain"><math> \frac{0}{50} + \frac{0.12}{-30} + \frac{0.048}{-10} + \frac{0.035}{10} + \frac{0}{30}</math></span>
# Rezultat standardne (weighted average) defazifikacije, primenjene nad skupom <math>D = A \cap B \cap C</math> je:
#: <math>z_{WA} =</math> <span class="spoiler" data-solution="text">-18.37</span>
Objašnjenje: <span class="spoiler" data-solution="explanation"><math>z_{WA} =\frac{0 \cdot 50 + 0.12 \cdot (-30) + 0.048 \cdot (-10) + 0.035 \cdot 10 + 0 \cdot 30}{0+0.12+0.048+0.035+0}</math></span>
</div>

[[Категорија:Неуралне мреже]]
[[Категорија:Рокови]]

Неуралне мреже/Јануар 2019

2022-02-20T23:09:11Z

Lukahrvacevic: /* 2. zadatak */

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

== 1. zadatak ==
Zaokružiti tačna tvrđenja (svaki tačan odgovor: +1 poen, svaki netačan odgovor: -0.5 poena, bez zaokruživanja: 0 poena):

=== Stavka a ===
''Stepen pripadanja'' konkretne vrednosti lingvističke varijable ''diskretnom'' fuzzy skupu je:
<div class="abc-list" data-solution="single">
# kontinualan fuzzy skup
# diskretan klasičan skup
# kontinualan klasičan skup
# <span class="solution">realna vrednost</span>
# kontinualna realna funkcija
# nijedno od ponuđenog
</div>

=== Stavka b ===
''Funkcija pripadanja'' lingvističke varijable ''kontinualnom'' fuzzy skupu je:
<div class="abc-list" data-solution="single">
# kontinualan fuzzy skup
# diskretan klasičan skup
# kontinualan klasičan skup
# realna vrednost
# <span class="solution">kontinualna realna funkcija</span>
# nijedno od ponuđenog
</div>

=== Stavka c ===
''Funkcija pripadanja'' lingvističke varijable ''diskretnom'' fuzzy skupu je:
<div class="abc-list" data-solution="single">
# kontinualan fuzzy skup
# diskretan klasičan skup
# kontinualan klasičan skup
# realna vrednost
# kontinualna realna funkcija
# <span class="solution">nijedno od ponuđenog</span>
</div>
Objašnjenje: <span class="spoiler" data-solution="explanation">Ovde bi kao odgovor moglo da dođe u obzir diskretna funkcija.</span>

=== Stavka d ===
''Podrška (support) kontinualnog'' fuzzy skupa je:
<div class="abc-list" data-solution="single">
# kontinualan fuzzy skup
# diskretan klasičan skup
# <span class="solution">kontinualan klasičan skup</span>
# realna vrednost
# kontinualna realna funkcija
# nijedno od ponuđenog
</div>

=== Stavka e ===
''<math>\alpha</math>-presek (<math>\alpha</math>-cut) diskretnog'' fuzzy skupa
<div class="abc-list" data-solution="single">
# kontinualan fuzzy skup
# <span class="solution">diskretan klasičan skup</span>
# kontinualan klasičan skup
# realna vrednost
# kontinualna realna funkcija
# nijedno od ponuđenog
</div>

=== Stavka f ===
Za ''kontinualan'' fuzzy skup <math>A</math>, <math>A^2</math> ("A na kvadrat") je:
<div class="abc-list" data-solution="single">
# <span class="solution">kontinualan fuzzy skup</span>
# diskretan klasičan skup
# kontinualan klasičan skup
# realna vrednost
# kontinualna realna funkcija
# nijedno od ponuđenog
</div>

=== Stavka g ===
Za ''diskretan'' fuzzy skup <math>A</math>, <math>A^2</math> ("A na kvadrat"):
<div class="abc-list" data-solution="single">
# kontinualan fuzzy skup
# diskretan klasičan skup
# kontinualan klasičan skup
# realna vrednost
# kontinualna realna funkcija
# <span class="solution">nijedno od ponuđenog</span>
</div>
Objašnjenje: <span class="spoiler" data-solution="explanation">Odgovor je diskretan fuzzy skup.</span>

=== Stavka h ===
U pravilu "if ''time'' is ''short'' then ''risk'' is ''high''" ''Sugenove'' mašine, ''short'' je:
<div class="abc-list" data-solution="single">
# diskretan fuzzy skup
# <span class="solution">kontinualan fuzzy skup</span>
# klasičan skup
# lingvistička varijabla
# nijedno od ponuđenog
</div>

=== Stavka i ===
U pravilu "if ''time'' is ''short'' then ''risk'' is ''high''" ''Mamdanijeve'' mašine, ''short'' je:
<div class="abc-list" data-solution="single">
# diskretan fuzzy skup
# <span class="solution">kontinualan fuzzy skup</span>
# klasičan skup
# lingvistička varijabla
# nijedno od ponuđenog
</div>
Objašnjenje: <span class="spoiler" data-solution="explanation">I kod Mamdanijeve i kod Sugenove mašine ulazni skupovi moraju biti kontinualni.</span>

=== Stavka j ===
Ako je rezultat izvršenja svih pravila ''Mamdanijeve'' mašine prazan skup, rezultat (maksimum) agregacije je:
<div class="abc-list" data-solution="single">
# prazan diskretan fuzzy skup
# <span class="solution">prazan kontinualan fuzzy skup</span>
# prazan klasičan skup
# realna vrednost 0
# nijedno od ponuđenog
</div>

=== Stavka k ===
Ako je rezultat izvršenja svih pravila ''Sugenove'' mašine prazan skup, rezultat (maksimum) agregacije je:
<div class="abc-list" data-solution="single">
# <span class="solution">prazan diskretan fuzzy skup</span>
# prazan kontinualan fuzzy skup
# prazan klasičan skup
# realna vrednost 0
# nijedno od ponuđenog
</div>

=== Stavka l ===
Rezultat Center of Gravity defazifikacije praznog fuzzy skupa je:
<div class="abc-list" data-solution="single">
# prazan diskretan fuzzy skup
# prazan kontinualan fuzzy skup
# prazan klasičan skup
# realna vrednost 0
# <span class="solution">nijedno od ponuđenog</span>
</div>
Objašnjenje: <span class="spoiler" data-solution="explanation">Defazifikacija praznog fuzzy skupa proizvodi nedefinisano ponašanje.</span>

=== Stavka m ===
Rezultat Weighted Average defazifikacije praznog fuzzy skupa je:
<div class="abc-list" data-solution="single">
# prazan diskretan fuzzy skup
# prazan kontinualan fuzzy skup
# prazan klasičan skup
# realna vrednost 0
# <span class="solution">nijedno od ponuđenog</span>
</div>
Objašnjenje: <span class="spoiler" data-solution="explanation">Defazifikacija praznog fuzzy skupa proizvodi nedefinisano ponašanje.</span>

== 2. zadatak ==
Za kontinualne fuzzy skupove <math>A</math>, <math>B</math> i <math>C</math> definisane su funkcije pripadanja:
* <math>\mu_A(x) = \left\{\begin{array}{ll}
1 + \frac{x}{4}, & -4 \leq x \leq 0 \\
1 - \frac{x}{4}, & 0 < x \leq 4
\end{array}\right.</math>
* <math>\mu_B(x) = \left\{\begin{array}{ll}
2 + \frac{x}{2}, & -4 \leq x < -2 \\
1, & -2 \leq x < 0 \\
1 - \frac{x}{2}, & 0 \leq x < 2 \\
0 & 2 \leq x \leq 4
\end{array}\right.</math>
* <math>\mu_C(x) = \left\{\begin{array}{ll}
y + 1, & -1 \leq y < 0 \\
1, & 0 \leq y \leq 1 \\
\frac{3-y}{2}, & 1 < y \leq 3
\end{array}\right.</math>
<div class="abc-list">
# Skicirati funkcije pripadanja za fuzzy skupove: (standardna) unija <math>A \cup B</math>, (standardni) komplement <math>\neg B</math> i (standardni) komplement <math>\neg C</math>.
# Ako se primenjuje '''scaling implikacija''', a konkretno je <math>x = 1</math>, skicirati rezultat izvršavanja pravila <math>\text{R1: if}\ x\ \text{is}\ \neg B\ \text{then}\ y\ \text{is}\ C</math>.
# Ako se primenjuje '''scaling implikacija''', rezultat izvršavanja pravila <math>\text{R1: if}\ x\ \text{is}\ \neg B\ \text{then}\ y\ \text{is}\ C</math> biće ''prazan skup'' za opseg konkretnih vrednosti ulazne varijable: <span class="spoiler" data-solution="plain">Sa grafika za <math>\neg B</math> vidimo da će biti prazan skup za opseg <math>x \in [-2,0]</math></span>
# Ako se primenjuje '''clipping implikacija''', a konkretno je <math>x = -1</math>, skicirati rezultat izvršavanja pravila <math>\text{R1: if}\ x\ \text{is}\ A\ \text{then}\ y\ \text{is}\ \neg C</math>.
</div>
<gallery class="spoiler" data-solution="plain">
NM januar 2019 zadatak 2 mua.svg | <math>\mu_A(x)</math>
NM januar 2019 zadatak 2 mub.svg | <math>\mu_B(x)</math>
NM januar 2019 zadatak 2 muc.svg | <math>\mu_C(x)</math>
NM januar 2019 zadatak 2a A unija B.svg | Zadatak 2a, <math>A \cup B</math>
NM januar 2019 zadatak 2a komplement B.svg | Zadatak 2a, <math>\neg B</math>
NM januar 2019 zadatak 2a komplement C.svg | Zadatak 2a, <math>\neg C</math>
NM januar 2019 zadatak 2b.svg | Zadatak 2b
NM januar 2019 zadatak 2d.svg | Zadatak 2d
</gallery>

== 3. zadatak ==
Za diskretne fuzzy skupove <math>A</math>, <math>B</math> i <math>C</math> definisane su funkcije pripadanja:
* <math>\mu_A(z) = 0.1|50 + 0.3|-30 + 0.1|-10 + 0.1|10 + 0.0|30</math>
* <math>\mu_B(z) = 0.0|50 + 0.4|-30 + 0.6|-10 + 0.7|10 + 0.5|30</math>
* <math>\mu_C(z) = 0.5|50 + 1.0|-30 + 0.8|-10 + 0.5|10 + 0.1|30</math>
<div class="abc-list">
# Ako je presek skupova definisan kao ''proizvod'' pripadnosti, tada je za <math>D = A \cap B \cap C</math>:
#: <math>\mu_D(z) = </math> <span class="spoiler" data-solution="plain"><math> \frac{0}{50} + \frac{0.12}{-30} + \frac{0.048}{-10} + \frac{0.035}{10} + \frac{0}{30}</math></span>
# Rezultat standardne (weighted average) defazifikacije, primenjene nad skupom <math>D = A \cap B \cap C</math> je:
#: <math>z_{WA} =</math> <span class="spoiler" data-solution="text">-18.37</span>
Objašnjenje: <span class="spoiler" data-solution="explanation"><math>z_{WA} =\frac{0 \cdot 50 + 0.12 \cdot (-30) + 0.048 \cdot (-10) + 0.035 \cdot 10 + 0 \cdot 30}{0+0.12+0.048+0.035+0}</math></span>
</div>

[[Категорија:Неуралне мреже]]
[[Категорија:Рокови]]

Неуралне мреже/Јануар 2019

2022-02-20T21:36:22Z

Lukahrvacevic: /* 3. zadatak */

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

== 1. zadatak ==
Zaokružiti tačna tvrđenja (svaki tačan odgovor: +1 poen, svaki netačan odgovor: -0.5 poena, bez zaokruživanja: 0 poena):

=== Stavka a ===
''Stepen pripadanja'' konkretne vrednosti lingvističke varijable ''diskretnom'' fuzzy skupu je:
<div class="abc-list" data-solution="single">
# kontinualan fuzzy skup
# diskretan klasičan skup
# kontinualan klasičan skup
# <span class="solution">realna vrednost</span>
# kontinualna realna funkcija
# nijedno od ponuđenog
</div>

=== Stavka b ===
''Funkcija pripadanja'' lingvističke varijable ''kontinualnom'' fuzzy skupu je:
<div class="abc-list" data-solution="single">
# kontinualan fuzzy skup
# diskretan klasičan skup
# kontinualan klasičan skup
# realna vrednost
# <span class="solution">kontinualna realna funkcija</span>
# nijedno od ponuđenog
</div>

=== Stavka c ===
''Funkcija pripadanja'' lingvističke varijable ''diskretnom'' fuzzy skupu je:
<div class="abc-list" data-solution="single">
# kontinualan fuzzy skup
# diskretan klasičan skup
# kontinualan klasičan skup
# realna vrednost
# kontinualna realna funkcija
# <span class="solution">nijedno od ponuđenog</span>
</div>
Objašnjenje: <span class="spoiler" data-solution="explanation">Ovde bi kao odgovor moglo da dođe u obzir diskretna funkcija.</span>

=== Stavka d ===
''Podrška (support) kontinualnog'' fuzzy skupa je:
<div class="abc-list" data-solution="single">
# kontinualan fuzzy skup
# diskretan klasičan skup
# <span class="solution">kontinualan klasičan skup</span>
# realna vrednost
# kontinualna realna funkcija
# nijedno od ponuđenog
</div>

=== Stavka e ===
''<math>\alpha</math>-presek (<math>\alpha</math>-cut) diskretnog'' fuzzy skupa
<div class="abc-list" data-solution="single">
# kontinualan fuzzy skup
# <span class="solution">diskretan klasičan skup</span>
# kontinualan klasičan skup
# realna vrednost
# kontinualna realna funkcija
# nijedno od ponuđenog
</div>

=== Stavka f ===
Za ''kontinualan'' fuzzy skup <math>A</math>, <math>A^2</math> ("A na kvadrat") je:
<div class="abc-list" data-solution="single">
# <span class="solution">kontinualan fuzzy skup</span>
# diskretan klasičan skup
# kontinualan klasičan skup
# realna vrednost
# kontinualna realna funkcija
# nijedno od ponuđenog
</div>

=== Stavka g ===
Za ''diskretan'' fuzzy skup <math>A</math>, <math>A^2</math> ("A na kvadrat"):
<div class="abc-list" data-solution="single">
# kontinualan fuzzy skup
# diskretan klasičan skup
# kontinualan klasičan skup
# realna vrednost
# kontinualna realna funkcija
# <span class="solution">nijedno od ponuđenog</span>
</div>
Objašnjenje: <span class="spoiler" data-solution="explanation">Odgovor je diskretan fuzzy skup.</span>

=== Stavka h ===
U pravilu "if ''time'' is ''short'' then ''risk'' is ''high''" ''Sugenove'' mašine, ''short'' je:
<div class="abc-list" data-solution="single">
# diskretan fuzzy skup
# <span class="solution">kontinualan fuzzy skup</span>
# klasičan skup
# lingvistička varijabla
# nijedno od ponuđenog
</div>

=== Stavka i ===
U pravilu "if ''time'' is ''short'' then ''risk'' is ''high''" ''Mamdanijeve'' mašine, ''short'' je:
<div class="abc-list" data-solution="single">
# diskretan fuzzy skup
# <span class="solution">kontinualan fuzzy skup</span>
# klasičan skup
# lingvistička varijabla
# nijedno od ponuđenog
</div>
Objašnjenje: <span class="spoiler" data-solution="explanation">I kod Mamdanijeve i kod Sugenove mašine ulazni skupovi moraju biti kontinualni.</span>

=== Stavka j ===
Ako je rezultat izvršenja svih pravila ''Mamdanijeve'' mašine prazan skup, rezultat (maksimum) agregacije je:
<div class="abc-list" data-solution="single">
# prazan diskretan fuzzy skup
# <span class="solution">prazan kontinualan fuzzy skup</span>
# prazan klasičan skup
# realna vrednost 0
# nijedno od ponuđenog
</div>

=== Stavka k ===
Ako je rezultat izvršenja svih pravila ''Sugenove'' mašine prazan skup, rezultat (maksimum) agregacije je:
<div class="abc-list" data-solution="single">
# <span class="solution">prazan diskretan fuzzy skup</span>
# prazan kontinualan fuzzy skup
# prazan klasičan skup
# realna vrednost 0
# nijedno od ponuđenog
</div>

=== Stavka l ===
Rezultat Center of Gravity defazifikacije praznog fuzzy skupa je:
<div class="abc-list" data-solution="single">
# prazan diskretan fuzzy skup
# prazan kontinualan fuzzy skup
# prazan klasičan skup
# realna vrednost 0
# <span class="solution">nijedno od ponuđenog</span>
</div>
Objašnjenje: <span class="spoiler" data-solution="explanation">Defazifikacija praznog fuzzy skupa proizvodi nedefinisano ponašanje.</span>

=== Stavka m ===
Rezultat Weighted Average defazifikacije praznog fuzzy skupa je:
<div class="abc-list" data-solution="single">
# prazan diskretan fuzzy skup
# prazan kontinualan fuzzy skup
# prazan klasičan skup
# realna vrednost 0
# <span class="solution">nijedno od ponuđenog</span>
</div>
Objašnjenje: <span class="spoiler" data-solution="explanation">Defazifikacija praznog fuzzy skupa proizvodi nedefinisano ponašanje.</span>

== 2. zadatak ==
{{delimično rešeno}}
Za kontinualne fuzzy skupove <math>A</math>, <math>B</math> i <math>C</math> definisane su funkcije pripadanja:
* <math>\mu_A(x) = \left\{\begin{array}{ll}
1 + \frac{x}{4}, & -4 \leq x \leq 0 \\
1 - \frac{x}{4}, & 0 < x \leq 4
\end{array}\right.</math>
* <math>\mu_B(x) = \left\{\begin{array}{ll}
2 + \frac{x}{2}, & -4 \leq x < -2 \\
1, & -2 \leq x < 0 \\
1 - \frac{x}{2}, & 0 \leq x < 2 \\
0 & 2 \leq x \leq 4
\end{array}\right.</math>
* <math>\mu_C(x) = \left\{\begin{array}{ll}
y + 1, & -1 \leq y < 0 \\
1, & 0 \leq y \leq 1 \\
\frac{3-y}{2}, & 1 < y \leq 3
\end{array}\right.</math>
<div class="abc-list">
# Skicirati funkcije pripadanja za fuzzy skupove: (standardna) unija <math>A \cup B</math>, (standardni) komplement <math>\neg B</math> i (standardni) komplement <math>\neg C</math>.
# Ako se primenjuje '''scaling implikacija''', a konkretno je <math>x = 1</math>, skicirati rezultat izvršavanja pravila <math>\text{R1: if}\ x\ \text{is}\ \neg B\ \text{then}\ y\ \text{is}\ C</math>.
# Ako se primenjuje '''scaling implikacija''', rezultat izvršavanja pravila <math>\text{R1: if}\ x\ \text{is}\ \neg B\ \text{then}\ y\ \text{is}\ C</math> biće ''prazan skup'' za opseg konkretnih vrednosti ulazne varijable: _______________
# Ako se primenjuje '''clipping implikacija''', a konkretno je <math>x = -1</math>, skicirati rezultat izvršavanja pravila <math>\text{R1: if}\ x\ \text{is}\ A\ \text{then}\ y\ \text{is}\ \neg C</math>.
</div>
== 3. zadatak ==
Za diskretne fuzzy skupove <math>A</math>, <math>B</math> i <math>C</math> definisane su funkcije pripadanja:
* <math>\mu_A(z) = 0.1|50 + 0.3|-30 + 0.1|-10 + 0.1|10 + 0.0|30</math>
* <math>\mu_B(z) = 0.0|50 + 0.4|-30 + 0.6|-10 + 0.7|10 + 0.5|30</math>
* <math>\mu_C(z) = 0.5|50 + 1.0|-30 + 0.8|-10 + 0.5|10 + 0.1|30</math>
<div class="abc-list">
# Ako je presek skupova definisan kao ''proizvod'' pripadnosti, tada je za <math>D = A \cap B \cap C</math>:
#: <math>\mu_D(z) = </math> <span class="spoiler" data-solution="plain"><math> \frac{0}{50} + \frac{0.12}{-30} + \frac{0.048}{-10} + \frac{0.035}{10} + \frac{0}{30}</math></span>
# Rezultat standardne (weighted average) defazifikacije, primenjene nad skupom <math>D = A \cap B \cap C</math> je:
#: <math>z_{WA} =</math> <span class="spoiler" data-solution="text">-18.37</span>
Objašnjenje: <span class="spoiler" data-solution="explanation"><math>z_{WA} =\frac{0 \cdot 50 + 0.12 \cdot (-30) + 0.048 \cdot (-10) + 0.035 \cdot 10 + 0 \cdot 30}{0+0.12+0.048+0.035+0}</math></span>
</div>

[[Категорија:Неуралне мреже]]
[[Категорија:Рокови]]

Неуралне мреже/Јануар 2019

2022-02-20T21:15:55Z

Lukahrvacevic:

{{rešenja}}

== 1. zadatak ==
Zaokružiti tačna tvrđenja (svaki tačan odgovor: +1 poen, svaki netačan odgovor: -0.5 poena, bez zaokruživanja: 0 poena):
<div class="abc-list" data-solution="single">
''Stepen pripadanja'' konkretne vrednosti lingvističke varijable ''diskretnom'' fuzzy skupu je:
# kontinualan fuzzy skup
# diskretan klasičan skup
# kontinualan klasičan skup
# <span class="solution">realna vrednost</span>
# kontinualna realna funkcija
# nijedno od ponuđenog
</div>
<div class="abc-list" data-solution="single">
''Funkcija pripadanja'' lingvističke varijable ''kontinualnom'' fuzzy skupu je:
# kontinualan fuzzy skup
# diskretan klasičan skup
# kontinualan klasičan skup
# realna vrednost
# <span class="solution">kontinualna realna funkcija</span>
# nijedno od ponuđenog
</div>
<div class="abc-list" data-solution="single">
''Funkcija pripadanja'' lingvističke varijable ''diskretnom'' fuzzy skupu je:
# kontinualan fuzzy skup
# diskretan klasičan skup
# kontinualan klasičan skup
# realna vrednost
# kontinualna realna funkcija
# <span class="solution">nijedno od ponuđenog</span>
</div>
Objašnjenje: <span class="spoiler" data-solution="explanation">Ovde bi kao odgovor moglo da dođe u obzir diskretna funkcija.</span>
<div class="abc-list" data-solution="single">
''Podrška (support) kontinualnog'' fuzzy skupa je:
# kontinualan fuzzy skup
# diskretan klasičan skup
# <span class="solution">kontinualan klasičan skup</span>
# realna vrednost
# kontinualna realna funkcija
# nijedno od ponuđenog
</div>
<div class="abc-list" data-solution="single">
''<math>\alpha</math>-presek (<math>\alpha</math>-cut) diskretnog'' fuzzy skupa
# kontinualan fuzzy skup
# <span class="solution">diskretan klasičan skup</span>
# kontinualan klasičan skup
# realna vrednost
# kontinualna realna funkcija
# nijedno od ponuđenog
</div>
<div class="abc-list" data-solution="single">
Za ''kontinualan'' fuzzy skup <math>A</math>, <math>A^2</math> ("A na kvadrat") je:
# <span class="solution">kontinualan fuzzy skup</span>
# diskretan klasičan skup
# kontinualan klasičan skup
# realna vrednost
# kontinualna realna funkcija
# nijedno od ponuđenog
</div>
<div class="abc-list" data-solution="single">
Za ''diskretan'' fuzzy skup <math>A</math>, <math>A^2</math> ("A na kvadrat"):
# kontinualan fuzzy skup
# diskretan klasičan skup
# kontinualan klasičan skup
# realna vrednost
# kontinualna realna funkcija
# <span class="solution">nijedno od ponuđenog</span>
</div>
Objašnjenje: <span class="spoiler" data-solution="explanation">Odgovor je diskretan fuzzy skup.</span>
<div class="abc-list" data-solution="single">
U pravilu "if ''time'' is ''short'' then ''risk'' is ''high''" ''Sugenove'' mašine, ''short'' je:
# diskretan fuzzy skup
# <span class="solution">kontinualan fuzzy skup</span>
# klasičan skup
# lingvistička varijabla
# nijedno od ponuđenog
</div>
<div class="abc-list" data-solution="single">
U pravilu "if ''time'' is ''short'' then ''risk'' is ''high''" ''Mamdanijeve'' mašine, ''short'' je:
# diskretan fuzzy skup
# <span class="solution">kontinualan fuzzy skup</span>
# klasičan skup
# lingvistička varijabla
# nijedno od ponuđenog
</div>
Objašnjenje: <span class="spoiler" data-solution="explanation">I kod Mamdanijeve i kod Sugenove mašine ulazni skupovi moraju biti kontinualni.</span>
<div class="abc-list" data-solution="single">
Ako je rezultat izvršenja svih pravila ''Mamdanijeve'' mašine prazan skup, rezultat (maksimum) agregacije je:
# prazan diskretan fuzzy skup
# <span class="solution">prazan kontinualan fuzzy skup</span>
# prazan klasičan skup
# realna vrednost 0
# nijedno od ponuđenog
</div>
<div class="abc-list" data-solution="single">
Ako je rezultat izvršenja svih pravila ''Sugenove'' mašine prazan skup, rezultat (maksimum) agregacije je:
# <span class="solution">prazan diskretan fuzzy skup</span>
# prazan kontinualan fuzzy skup
# prazan klasičan skup
# realna vrednost 0
# nijedno od ponuđenog
</div>
<div class="abc-list" data-solution="single">
Rezultat Center of Gravity defazifikacije praznog fuzzy skupa je:
# prazan diskretan fuzzy skup
# prazan kontinualan fuzzy skup
# prazan klasičan skup
# realna vrednost 0
# <span class="solution">nijedno od ponuđenog</span>
</div>
Objašnjenje: <span class="spoiler" data-solution="explanation">Defazifikacija praznog fuzzy skupa proizvodi nedefinisano ponašanje.</span>
<div class="abc-list" data-solution="single">
Rezultat Weighted Average defazifikacije praznog fuzzy skupa je:
# prazan diskretan fuzzy skup
# prazan kontinualan fuzzy skup
# prazan klasičan skup
# realna vrednost 0
# <span class="solution">nijedno od ponuđenog</span>
</div>
Objašnjenje: <span class="spoiler" data-solution="explanation">Defazifikacija praznog fuzzy skupa proizvodi nedefinisano ponašanje.</span>
== 2. zadatak ==
{{delimično rešeno}}
Za kontinualne fuzzy skupove <math>A</math>, <math>B</math> i <math>C</math> definisane su funkcije pripadanja:
* <math>\mu_A(x) = \left\{\begin{array}{ll}
1 + \frac{x}{4}, & -4 \leq x \leq 0 \\
1 - \frac{x}{4}, & 0 < x \leq 4
\end{array}\right.</math>
* <math>\mu_B(x) = \left\{\begin{array}{ll}
2 + \frac{x}{2}, & -4 \leq x < -2 \\
1, & -2 \leq x < 0 \\
1 - \frac{x}{2}, & 0 \leq x < 2 \\
0 & 2 \leq x \leq 4
\end{array}\right.</math>
* <math>\mu_C(x) = \left\{\begin{array}{ll}
y + 1, & -1 \leq y < 0 \\
1, & 0 \leq y \leq 1 \\
\frac{3-y}{2}, & 1 < y \leq 3
\end{array}\right.</math>
<div class="abc-list">
# Skicirati funkcije pripadanja za fuzzy skupove: (standardna) unija <math>A \cup B</math>, (standardni) komplement <math>\neg B</math> i (standardni) komplement <math>\neg C</math>.
# Ako se primenjuje '''scaling implikacija''', a konkretno je <math>x = 1</math>, skicirati rezultat izvršavanja pravila <math>\text{R1: if}\ x\ \text{is}\ \neg B\ \text{then}\ y\ \text{is}\ C</math>.
# Ako se primenjuje '''scaling implikacija''', rezultat izvršavanja pravila <math>\text{R1: if}\ x\ \text{is}\ \neg B\ \text{then}\ y\ \text{is}\ C</math> biće ''prazan skup'' za opseg konkretnih vrednosti ulazne varijable: _______________
# Ako se primenjuje '''clipping implikacija''', a konkretno je <math>x = -1</math>, skicirati rezultat izvršavanja pravila <math>\text{R1: if}\ x\ \text{is}\ A\ \text{then}\ y\ \text{is}\ \neg C</math>.
</div>
== 3. zadatak ==
{{delimično rešeno}}
Za diskretne fuzzy skupove <math>A</math>, <math>B</math> i <math>C</math> definisane su funkcije pripadanja:
* <math>\mu_A(z) = 0.1|50 + 0.3|-30 + 0.1|-10 + 0.1|10 + 0.0|30</math>
* <math>\mu_B(z) = 0.0|50 + 0.4|-30 + 0.6|-10 + 0.7|10 + 0.5|30</math>
* <math>\mu_C(z) = 0.5|50 + 1.0|-30 + 0.8|-10 + 0.5|10 + 0.1|30</math>
<div class="abc-list">
# Ako je presek skupova definisan kao ''proizvod'' pripadnosti, tada je za <math>D = A \cap B \cap C</math>:
#: <math>\mu_D(z) =</math>
# Rezultat standardne (weighted average) defazifikacije, primenjene nad skupom <math>D = A \cap B \cap C</math> je:
#: <math>z_{WA} =</math>
</div>

[[Категорија:Неуралне мреже]]
[[Категорија:Рокови]]

Неуралне мреже/Јануар 2019

2022-02-20T21:14:46Z

Lukahrvacevic:

{{rešenja}}

== 1. zadatak ==
Zaokružiti tačna tvrđenja (svaki tačan odgovor: +1 poen, svaki netačan odgovor: -0.5 poena, bez zaokruživanja: 0 poena):
<div class="abc-list" data-solution="single">
''Stepen pripadanja'' konkretne vrednosti lingvističke varijable ''diskretnom'' fuzzy skupu je:
# kontinualan fuzzy skup
# diskretan klasičan skup
# kontinualan klasičan skup
# <span class="solution">realna vrednost</span>
# kontinualna realna funkcija
# nijedno od ponuđenog
</div>
<div class="abc-list" data-solution="single">
''Funkcija pripadanja'' lingvističke varijable ''kontinualnom'' fuzzy skupu je:
# kontinualan fuzzy skup
# diskretan klasičan skup
# kontinualan klasičan skup
# realna vrednost
# <span class="solution">kontinualna realna funkcija</span>
# nijedno od ponuđenog
</div>
<div class="abc-list" data-solution="single">
''Funkcija pripadanja'' lingvističke varijable ''diskretnom'' fuzzy skupu je:
# kontinualan fuzzy skup
# diskretan klasičan skup
# kontinualan klasičan skup
# realna vrednost
# kontinualna realna funkcija
# <span class="solution">nijedno od ponuđenog</span>
</div>
Objašnjenje: <span class="spoiler" data-solution="explanation">Ovde bi kao odgovor moglo da dođe u obzir diskretna funkcija.</span>
<div class="abc-list" data-solution="single">
''Podrška (support) kontinualnog'' fuzzy skupa je:
# kontinualan fuzzy skup
# diskretan klasičan skup
# <span class="solution">kontinualan klasičan skup</span>
# realna vrednost
# kontinualna realna funkcija
# nijedno od ponuđenog
</div>
<div class="abc-list" data-solution="single">
''<math>\alpha</math>-presek (<math>\alpha</math>-cut) diskretnog'' fuzzy skupa
# kontinualan fuzzy skup
# <span class="solution">diskretan klasičan skup</span>
# kontinualan klasičan skup
# realna vrednost
# kontinualna realna funkcija
# nijedno od ponuđenog
</div>
<div class="abc-list" data-solution="single">
Za ''kontinualan'' fuzzy skup <math>A</math>, <math>A^2</math> ("A na kvadrat") je:
# <span class="solution">kontinualan fuzzy skup</span>
# diskretan klasičan skup
# kontinualan klasičan skup
# realna vrednost
# kontinualna realna funkcija
# nijedno od ponuđenog
</div>
<div class="abc-list" data-solution="single">
Za ''diskretan'' fuzzy skup <math>A</math>, <math>A^2</math> ("A na kvadrat"):
# kontinualan fuzzy skup
# diskretan klasičan skup
# kontinualan klasičan skup
# realna vrednost
# kontinualna realna funkcija
# <span class="solution">nijedno od ponuđenog</span>
</div>
Objašnjenje: <span class="spoiler" data-solution="explanation">Odgovor je diskretan fuzzy skup.</span>
<div class="abc-list" data-solution="single">
U pravilu "if ''time'' is ''short'' then ''risk'' is ''high''" ''Sugenove'' mašine, ''short'' je:
# diskretan fuzzy skup
# <span class="solution">kontinualan fuzzy skup</span>
# klasičan skup
# lingvistička varijabla
# nijedno od ponuđenog
</div>
<div class="abc-list" data-solution="single">
U pravilu "if ''time'' is ''short'' then ''risk'' is ''high''" ''Mamdanijeve'' mašine, ''short'' je:
# diskretan fuzzy skup
# <span class="solution">kontinualan fuzzy skup</span>
# klasičan skup
# lingvistička varijabla
# nijedno od ponuđenog
</div>
Objašnjenje: <span class="spoiler" data-solution="explanation">I kod Mamdanijeve i kod Sugenove mašine ulazni skupovi moraju biti kontinualni.</span>
<div class="abc-list" data-solution="single">
Ako je rezultat izvršenja svih pravila ''Mamdanijeve'' mašine prazan skup, rezultat (maksimum) agregacije je:
# prazan diskretan fuzzy skup
# <span class="solution">prazan kontinualan fuzzy skup</span>
# prazan klasičan skup
# realna vrednost 0
# nijedno od ponuđenog
</div>
<div class="abc-list" data-solution="single">
Ako je rezultat izvršenja svih pravila ''Sugenove'' mašine prazan skup, rezultat (maksimum) agregacije je:
# <span class="solution">prazan diskretan fuzzy skup</span>
# prazan kontinualan fuzzy skup
# prazan klasičan skup
# realna vrednost 0
# nijedno od ponuđenog
</div>
<div class="abc-list" data-solution="single">
Rezultat Center of Gravity defazifikacije praznog fuzzy skupa je:
# prazan diskretan fuzzy skup
# prazan kontinualan fuzzy skup
# prazan klasičan skup
# realna vrednost 0
# <span class="solution">nijedno od ponuđenog</span>
</div>
Objašnjenje: <span class="spoiler" data-solution="explanation">Defazifikacija praznog fuzzy skupa proizvodi nedefinisano ponašanje.</span>
<div class="abc-list" data-solution="single">
Rezultat Weighted Average defazifikacije praznog fuzzy skupa je:
# prazan diskretan fuzzy skup
# prazan kontinualan fuzzy skup
# prazan klasičan skup
# realna vrednost 0
# <span class="solution">nijedno od ponuđenog</span>
</div>
Objašnjenje: <span class="spoiler" data-solution="explanation">Defazifikacija praznog fuzzy skupa proizvodi nedefinisano ponašanje.</span>
{{delimično rešeno}}
== 2. zadatak ==
Za kontinualne fuzzy skupove <math>A</math>, <math>B</math> i <math>C</math> definisane su funkcije pripadanja:
* <math>\mu_A(x) = \left\{\begin{array}{ll}
1 + \frac{x}{4}, & -4 \leq x \leq 0 \\
1 - \frac{x}{4}, & 0 < x \leq 4
\end{array}\right.</math>
* <math>\mu_B(x) = \left\{\begin{array}{ll}
2 + \frac{x}{2}, & -4 \leq x < -2 \\
1, & -2 \leq x < 0 \\
1 - \frac{x}{2}, & 0 \leq x < 2 \\
0 & 2 \leq x \leq 4
\end{array}\right.</math>
* <math>\mu_C(x) = \left\{\begin{array}{ll}
y + 1, & -1 \leq y < 0 \\
1, & 0 \leq y \leq 1 \\
\frac{3-y}{2}, & 1 < y \leq 3
\end{array}\right.</math>
<div class="abc-list">
# Skicirati funkcije pripadanja za fuzzy skupove: (standardna) unija <math>A \cup B</math>, (standardni) komplement <math>\neg B</math> i (standardni) komplement <math>\neg C</math>.
# Ako se primenjuje '''scaling implikacija''', a konkretno je <math>x = 1</math>, skicirati rezultat izvršavanja pravila <math>\text{R1: if}\ x\ \text{is}\ \neg B\ \text{then}\ y\ \text{is}\ C</math>.
# Ako se primenjuje '''scaling implikacija''', rezultat izvršavanja pravila <math>\text{R1: if}\ x\ \text{is}\ \neg B\ \text{then}\ y\ \text{is}\ C</math> biće ''prazan skup'' za opseg konkretnih vrednosti ulazne varijable: _______________
# Ako se primenjuje '''clipping implikacija''', a konkretno je <math>x = -1</math>, skicirati rezultat izvršavanja pravila <math>\text{R1: if}\ x\ \text{is}\ A\ \text{then}\ y\ \text{is}\ \neg C</math>.
</div>
{{delimično rešeno}}
== 3. zadatak ==
Za diskretne fuzzy skupove <math>A</math>, <math>B</math> i <math>C</math> definisane su funkcije pripadanja:
* <math>\mu_A(z) = 0.1|50 + 0.3|-30 + 0.1|-10 + 0.1|10 + 0.0|30</math>
* <math>\mu_B(z) = 0.0|50 + 0.4|-30 + 0.6|-10 + 0.7|10 + 0.5|30</math>
* <math>\mu_C(z) = 0.5|50 + 1.0|-30 + 0.8|-10 + 0.5|10 + 0.1|30</math>
<div class="abc-list">
# Ako je presek skupova definisan kao ''proizvod'' pripadnosti, tada je za <math>D = A \cap B \cap C</math>:
#: <math>\mu_D(z) =</math>
# Rezultat standardne (weighted average) defazifikacije, primenjene nad skupom <math>D = A \cap B \cap C</math> je:
#: <math>z_{WA} =</math>
</div>

[[Категорија:Неуралне мреже]]
[[Категорија:Рокови]]

Неуралне мреже/Јануар 2019

2022-02-20T21:14:09Z

Lukahrvacevic: Kategorizacija u delimicno reseno - resicu do kraja ili posle ili sutra

{{delimično rešeno}}
{{rešenja}}

== 1. zadatak ==
Zaokružiti tačna tvrđenja (svaki tačan odgovor: +1 poen, svaki netačan odgovor: -0.5 poena, bez zaokruživanja: 0 poena):
<div class="abc-list" data-solution="single">
''Stepen pripadanja'' konkretne vrednosti lingvističke varijable ''diskretnom'' fuzzy skupu je:
# kontinualan fuzzy skup
# diskretan klasičan skup
# kontinualan klasičan skup
# <span class="solution">realna vrednost</span>
# kontinualna realna funkcija
# nijedno od ponuđenog
</div>
<div class="abc-list" data-solution="single">
''Funkcija pripadanja'' lingvističke varijable ''kontinualnom'' fuzzy skupu je:
# kontinualan fuzzy skup
# diskretan klasičan skup
# kontinualan klasičan skup
# realna vrednost
# <span class="solution">kontinualna realna funkcija</span>
# nijedno od ponuđenog
</div>
<div class="abc-list" data-solution="single">
''Funkcija pripadanja'' lingvističke varijable ''diskretnom'' fuzzy skupu je:
# kontinualan fuzzy skup
# diskretan klasičan skup
# kontinualan klasičan skup
# realna vrednost
# kontinualna realna funkcija
# <span class="solution">nijedno od ponuđenog</span>
</div>
Objašnjenje: <span class="spoiler" data-solution="explanation">Ovde bi kao odgovor moglo da dođe u obzir diskretna funkcija.</span>
<div class="abc-list" data-solution="single">
''Podrška (support) kontinualnog'' fuzzy skupa je:
# kontinualan fuzzy skup
# diskretan klasičan skup
# <span class="solution">kontinualan klasičan skup</span>
# realna vrednost
# kontinualna realna funkcija
# nijedno od ponuđenog
</div>
<div class="abc-list" data-solution="single">
''<math>\alpha</math>-presek (<math>\alpha</math>-cut) diskretnog'' fuzzy skupa
# kontinualan fuzzy skup
# <span class="solution">diskretan klasičan skup</span>
# kontinualan klasičan skup
# realna vrednost
# kontinualna realna funkcija
# nijedno od ponuđenog
</div>
<div class="abc-list" data-solution="single">
Za ''kontinualan'' fuzzy skup <math>A</math>, <math>A^2</math> ("A na kvadrat") je:
# <span class="solution">kontinualan fuzzy skup</span>
# diskretan klasičan skup
# kontinualan klasičan skup
# realna vrednost
# kontinualna realna funkcija
# nijedno od ponuđenog
</div>
<div class="abc-list" data-solution="single">
Za ''diskretan'' fuzzy skup <math>A</math>, <math>A^2</math> ("A na kvadrat"):
# kontinualan fuzzy skup
# diskretan klasičan skup
# kontinualan klasičan skup
# realna vrednost
# kontinualna realna funkcija
# <span class="solution">nijedno od ponuđenog</span>
</div>
Objašnjenje: <span class="spoiler" data-solution="explanation">Odgovor je diskretan fuzzy skup.</span>
<div class="abc-list" data-solution="single">
U pravilu "if ''time'' is ''short'' then ''risk'' is ''high''" ''Sugenove'' mašine, ''short'' je:
# diskretan fuzzy skup
# <span class="solution">kontinualan fuzzy skup</span>
# klasičan skup
# lingvistička varijabla
# nijedno od ponuđenog
</div>
<div class="abc-list" data-solution="single">
U pravilu "if ''time'' is ''short'' then ''risk'' is ''high''" ''Mamdanijeve'' mašine, ''short'' je:
# diskretan fuzzy skup
# <span class="solution">kontinualan fuzzy skup</span>
# klasičan skup
# lingvistička varijabla
# nijedno od ponuđenog
</div>
Objašnjenje: <span class="spoiler" data-solution="explanation">I kod Mamdanijeve i kod Sugenove mašine ulazni skupovi moraju biti kontinualni.</span>
<div class="abc-list" data-solution="single">
Ako je rezultat izvršenja svih pravila ''Mamdanijeve'' mašine prazan skup, rezultat (maksimum) agregacije je:
# prazan diskretan fuzzy skup
# <span class="solution">prazan kontinualan fuzzy skup</span>
# prazan klasičan skup
# realna vrednost 0
# nijedno od ponuđenog
</div>
<div class="abc-list" data-solution="single">
Ako je rezultat izvršenja svih pravila ''Sugenove'' mašine prazan skup, rezultat (maksimum) agregacije je:
# <span class="solution">prazan diskretan fuzzy skup</span>
# prazan kontinualan fuzzy skup
# prazan klasičan skup
# realna vrednost 0
# nijedno od ponuđenog
</div>
<div class="abc-list" data-solution="single">
Rezultat Center of Gravity defazifikacije praznog fuzzy skupa je:
# prazan diskretan fuzzy skup
# prazan kontinualan fuzzy skup
# prazan klasičan skup
# realna vrednost 0
# <span class="solution">nijedno od ponuđenog</span>
</div>
Objašnjenje: <span class="spoiler" data-solution="explanation">Defazifikacija praznog fuzzy skupa proizvodi nedefinisano ponašanje.</span>
<div class="abc-list" data-solution="single">
Rezultat Weighted Average defazifikacije praznog fuzzy skupa je:
# prazan diskretan fuzzy skup
# prazan kontinualan fuzzy skup
# prazan klasičan skup
# realna vrednost 0
# <span class="solution">nijedno od ponuđenog</span>
</div>
Objašnjenje: <span class="spoiler" data-solution="explanation">Defazifikacija praznog fuzzy skupa proizvodi nedefinisano ponašanje.</span>

== 2. zadatak ==
Za kontinualne fuzzy skupove <math>A</math>, <math>B</math> i <math>C</math> definisane su funkcije pripadanja:
* <math>\mu_A(x) = \left\{\begin{array}{ll}
1 + \frac{x}{4}, & -4 \leq x \leq 0 \\
1 - \frac{x}{4}, & 0 < x \leq 4
\end{array}\right.</math>
* <math>\mu_B(x) = \left\{\begin{array}{ll}
2 + \frac{x}{2}, & -4 \leq x < -2 \\
1, & -2 \leq x < 0 \\
1 - \frac{x}{2}, & 0 \leq x < 2 \\
0 & 2 \leq x \leq 4
\end{array}\right.</math>
* <math>\mu_C(x) = \left\{\begin{array}{ll}
y + 1, & -1 \leq y < 0 \\
1, & 0 \leq y \leq 1 \\
\frac{3-y}{2}, & 1 < y \leq 3
\end{array}\right.</math>
<div class="abc-list">
# Skicirati funkcije pripadanja za fuzzy skupove: (standardna) unija <math>A \cup B</math>, (standardni) komplement <math>\neg B</math> i (standardni) komplement <math>\neg C</math>.
# Ako se primenjuje '''scaling implikacija''', a konkretno je <math>x = 1</math>, skicirati rezultat izvršavanja pravila <math>\text{R1: if}\ x\ \text{is}\ \neg B\ \text{then}\ y\ \text{is}\ C</math>.
# Ako se primenjuje '''scaling implikacija''', rezultat izvršavanja pravila <math>\text{R1: if}\ x\ \text{is}\ \neg B\ \text{then}\ y\ \text{is}\ C</math> biće ''prazan skup'' za opseg konkretnih vrednosti ulazne varijable: _______________
# Ako se primenjuje '''clipping implikacija''', a konkretno je <math>x = -1</math>, skicirati rezultat izvršavanja pravila <math>\text{R1: if}\ x\ \text{is}\ A\ \text{then}\ y\ \text{is}\ \neg C</math>.
</div>

== 3. zadatak ==
Za diskretne fuzzy skupove <math>A</math>, <math>B</math> i <math>C</math> definisane su funkcije pripadanja:
* <math>\mu_A(z) = 0.1|50 + 0.3|-30 + 0.1|-10 + 0.1|10 + 0.0|30</math>
* <math>\mu_B(z) = 0.0|50 + 0.4|-30 + 0.6|-10 + 0.7|10 + 0.5|30</math>
* <math>\mu_C(z) = 0.5|50 + 1.0|-30 + 0.8|-10 + 0.5|10 + 0.1|30</math>
<div class="abc-list">
# Ako je presek skupova definisan kao ''proizvod'' pripadnosti, tada je za <math>D = A \cap B \cap C</math>:
#: <math>\mu_D(z) =</math>
# Rezultat standardne (weighted average) defazifikacije, primenjene nad skupom <math>D = A \cap B \cap C</math> je:
#: <math>z_{WA} =</math>
</div>

[[Категорија:Неуралне мреже]]
[[Категорија:Рокови]]

Неуралне мреже/Јануар 2019

2022-02-20T21:12:56Z

Lukahrvacevic:

{{nerešeno}}
{{rešenja}}

== 1. zadatak ==
Zaokružiti tačna tvrđenja (svaki tačan odgovor: +1 poen, svaki netačan odgovor: -0.5 poena, bez zaokruživanja: 0 poena):
<div class="abc-list" data-solution="single">
''Stepen pripadanja'' konkretne vrednosti lingvističke varijable ''diskretnom'' fuzzy skupu je:
# kontinualan fuzzy skup
# diskretan klasičan skup
# kontinualan klasičan skup
# <span class="solution">realna vrednost</span>
# kontinualna realna funkcija
# nijedno od ponuđenog
</div>
<div class="abc-list" data-solution="single">
''Funkcija pripadanja'' lingvističke varijable ''kontinualnom'' fuzzy skupu je:
# kontinualan fuzzy skup
# diskretan klasičan skup
# kontinualan klasičan skup
# realna vrednost
# <span class="solution">kontinualna realna funkcija</span>
# nijedno od ponuđenog
</div>
<div class="abc-list" data-solution="single">
''Funkcija pripadanja'' lingvističke varijable ''diskretnom'' fuzzy skupu je:
# kontinualan fuzzy skup
# diskretan klasičan skup
# kontinualan klasičan skup
# realna vrednost
# kontinualna realna funkcija
# <span class="solution">nijedno od ponuđenog</span>
</div>
Objašnjenje: <span class="spoiler" data-solution="explanation">Ovde bi kao odgovor moglo da dođe u obzir diskretna funkcija.</span>
<div class="abc-list" data-solution="single">
''Podrška (support) kontinualnog'' fuzzy skupa je:
# kontinualan fuzzy skup
# diskretan klasičan skup
# <span class="solution">kontinualan klasičan skup</span>
# realna vrednost
# kontinualna realna funkcija
# nijedno od ponuđenog
</div>
<div class="abc-list" data-solution="single">
''<math>\alpha</math>-presek (<math>\alpha</math>-cut) diskretnog'' fuzzy skupa
# kontinualan fuzzy skup
# <span class="solution">diskretan klasičan skup</span>
# kontinualan klasičan skup
# realna vrednost
# kontinualna realna funkcija
# nijedno od ponuđenog
</div>
<div class="abc-list" data-solution="single">
Za ''kontinualan'' fuzzy skup <math>A</math>, <math>A^2</math> ("A na kvadrat") je:
# <span class="solution">kontinualan fuzzy skup</span>
# diskretan klasičan skup
# kontinualan klasičan skup
# realna vrednost
# kontinualna realna funkcija
# nijedno od ponuđenog
</div>
<div class="abc-list" data-solution="single">
Za ''diskretan'' fuzzy skup <math>A</math>, <math>A^2</math> ("A na kvadrat"):
# kontinualan fuzzy skup
# diskretan klasičan skup
# kontinualan klasičan skup
# realna vrednost
# kontinualna realna funkcija
# <span class="solution">nijedno od ponuđenog</span>
</div>
Objašnjenje: <span class="spoiler" data-solution="explanation">Odgovor je diskretan fuzzy skup.</span>
<div class="abc-list" data-solution="single">
U pravilu "if ''time'' is ''short'' then ''risk'' is ''high''" ''Sugenove'' mašine, ''short'' je:
# diskretan fuzzy skup
# <span class="solution">kontinualan fuzzy skup</span>
# klasičan skup
# lingvistička varijabla
# nijedno od ponuđenog
</div>
<div class="abc-list" data-solution="single">
U pravilu "if ''time'' is ''short'' then ''risk'' is ''high''" ''Mamdanijeve'' mašine, ''short'' je:
# diskretan fuzzy skup
# <span class="solution">kontinualan fuzzy skup</span>
# klasičan skup
# lingvistička varijabla
# nijedno od ponuđenog
</div>
Objašnjenje: <span class="spoiler" data-solution="explanation">I kod Mamdanijeve i kod Sugenove mašine ulazni skupovi moraju biti kontinualni.</span>
<div class="abc-list" data-solution="single">
Ako je rezultat izvršenja svih pravila ''Mamdanijeve'' mašine prazan skup, rezultat (maksimum) agregacije je:
# prazan diskretan fuzzy skup
# <span class="solution">prazan kontinualan fuzzy skup</span>
# prazan klasičan skup
# realna vrednost 0
# nijedno od ponuđenog
</div>
<div class="abc-list" data-solution="single">
Ako je rezultat izvršenja svih pravila ''Sugenove'' mašine prazan skup, rezultat (maksimum) agregacije je:
# <span class="solution">prazan diskretan fuzzy skup</span>
# prazan kontinualan fuzzy skup
# prazan klasičan skup
# realna vrednost 0
# nijedno od ponuđenog
</div>
<div class="abc-list" data-solution="single">
Rezultat Center of Gravity defazifikacije praznog fuzzy skupa je:
# prazan diskretan fuzzy skup
# prazan kontinualan fuzzy skup
# prazan klasičan skup
# realna vrednost 0
# <span class="solution">nijedno od ponuđenog</span>
</div>
Objašnjenje: <span class="spoiler" data-solution="explanation">Defazifikacija praznog fuzzy skupa proizvodi nedefinisano ponašanje.</span>
<div class="abc-list" data-solution="single">
Rezultat Weighted Average defazifikacije praznog fuzzy skupa je:
# prazan diskretan fuzzy skup
# prazan kontinualan fuzzy skup
# prazan klasičan skup
# realna vrednost 0
# <span class="solution">nijedno od ponuđenog</span>
</div>
Objašnjenje: <span class="spoiler" data-solution="explanation">Defazifikacija praznog fuzzy skupa proizvodi nedefinisano ponašanje.</span>

== 2. zadatak ==
Za kontinualne fuzzy skupove <math>A</math>, <math>B</math> i <math>C</math> definisane su funkcije pripadanja:
* <math>\mu_A(x) = \left\{\begin{array}{ll}
1 + \frac{x}{4}, & -4 \leq x \leq 0 \\
1 - \frac{x}{4}, & 0 < x \leq 4
\end{array}\right.</math>
* <math>\mu_B(x) = \left\{\begin{array}{ll}
2 + \frac{x}{2}, & -4 \leq x < -2 \\
1, & -2 \leq x < 0 \\
1 - \frac{x}{2}, & 0 \leq x < 2 \\
0 & 2 \leq x \leq 4
\end{array}\right.</math>
* <math>\mu_C(x) = \left\{\begin{array}{ll}
y + 1, & -1 \leq y < 0 \\
1, & 0 \leq y \leq 1 \\
\frac{3-y}{2}, & 1 < y \leq 3
\end{array}\right.</math>
<div class="abc-list">
# Skicirati funkcije pripadanja za fuzzy skupove: (standardna) unija <math>A \cup B</math>, (standardni) komplement <math>\neg B</math> i (standardni) komplement <math>\neg C</math>.
# Ako se primenjuje '''scaling implikacija''', a konkretno je <math>x = 1</math>, skicirati rezultat izvršavanja pravila <math>\text{R1: if}\ x\ \text{is}\ \neg B\ \text{then}\ y\ \text{is}\ C</math>.
# Ako se primenjuje '''scaling implikacija''', rezultat izvršavanja pravila <math>\text{R1: if}\ x\ \text{is}\ \neg B\ \text{then}\ y\ \text{is}\ C</math> biće ''prazan skup'' za opseg konkretnih vrednosti ulazne varijable: _______________
# Ako se primenjuje '''clipping implikacija''', a konkretno je <math>x = -1</math>, skicirati rezultat izvršavanja pravila <math>\text{R1: if}\ x\ \text{is}\ A\ \text{then}\ y\ \text{is}\ \neg C</math>.
</div>

== 3. zadatak ==
Za diskretne fuzzy skupove <math>A</math>, <math>B</math> i <math>C</math> definisane su funkcije pripadanja:
* <math>\mu_A(z) = 0.1|50 + 0.3|-30 + 0.1|-10 + 0.1|10 + 0.0|30</math>
* <math>\mu_B(z) = 0.0|50 + 0.4|-30 + 0.6|-10 + 0.7|10 + 0.5|30</math>
* <math>\mu_C(z) = 0.5|50 + 1.0|-30 + 0.8|-10 + 0.5|10 + 0.1|30</math>
<div class="abc-list">
# Ako je presek skupova definisan kao ''proizvod'' pripadnosti, tada je za <math>D = A \cap B \cap C</math>:
#: <math>\mu_D(z) =</math>
# Rezultat standardne (weighted average) defazifikacije, primenjene nad skupom <math>D = A \cap B \cap C</math> je:
#: <math>z_{WA} =</math>
</div>

[[Категорија:Неуралне мреже]]
[[Категорија:Рокови]]

Неуралне мреже/Јануар 2019

2022-02-20T21:11:49Z

Lukahrvacevic: /* Interaktivni rezim i odgovori za prvi zadatak */

{{nerešeno}}

== 1. zadatak ==
Zaokružiti tačna tvrđenja (svaki tačan odgovor: +1 poen, svaki netačan odgovor: -0.5 poena, bez zaokruživanja: 0 poena):
<div class="abc-list" data-solution="single">
''Stepen pripadanja'' konkretne vrednosti lingvističke varijable ''diskretnom'' fuzzy skupu je:
# kontinualan fuzzy skup
# diskretan klasičan skup
# kontinualan klasičan skup
# <span class="solution">realna vrednost</span>
# kontinualna realna funkcija
# nijedno od ponuđenog
</div>
<div class="abc-list" data-solution="single">
''Funkcija pripadanja'' lingvističke varijable ''kontinualnom'' fuzzy skupu je:
# kontinualan fuzzy skup
# diskretan klasičan skup
# kontinualan klasičan skup
# realna vrednost
# <span class="solution">kontinualna realna funkcija</span>
# nijedno od ponuđenog
</div>
<div class="abc-list" data-solution="single">
''Funkcija pripadanja'' lingvističke varijable ''diskretnom'' fuzzy skupu je:
# kontinualan fuzzy skup
# diskretan klasičan skup
# kontinualan klasičan skup
# realna vrednost
# kontinualna realna funkcija
# <span class="solution">nijedno od ponuđenog</span>
</div>
Objašnjenje: <span class="spoiler" data-solution="explanation">Ovde bi kao odgovor moglo da dođe u obzir diskretna funkcija.</span>
<div class="abc-list" data-solution="single">
''Podrška (support) kontinualnog'' fuzzy skupa je:
# kontinualan fuzzy skup
# diskretan klasičan skup
# <span class="solution">kontinualan klasičan skup</span>
# realna vrednost
# kontinualna realna funkcija
# nijedno od ponuđenog
</div>
<div class="abc-list" data-solution="single">
''<math>\alpha</math>-presek (<math>\alpha</math>-cut) diskretnog'' fuzzy skupa
# kontinualan fuzzy skup
# <span class="solution">diskretan klasičan skup</span>
# kontinualan klasičan skup
# realna vrednost
# kontinualna realna funkcija
# nijedno od ponuđenog
</div>
<div class="abc-list" data-solution="single">
Za ''kontinualan'' fuzzy skup <math>A</math>, <math>A^2</math> ("A na kvadrat") je:
# <span class="solution">kontinualan fuzzy skup</span>
# diskretan klasičan skup
# kontinualan klasičan skup
# realna vrednost
# kontinualna realna funkcija
# nijedno od ponuđenog
</div>
<div class="abc-list" data-solution="single">
Za ''diskretan'' fuzzy skup <math>A</math>, <math>A^2</math> ("A na kvadrat"):
# kontinualan fuzzy skup
# diskretan klasičan skup
# kontinualan klasičan skup
# realna vrednost
# kontinualna realna funkcija
# <span class="solution">nijedno od ponuđenog</span>
</div>
Objašnjenje: <span class="spoiler" data-solution="explanation">Odgovor je diskretan fuzzy skup.</span>
<div class="abc-list" data-solution="single">
U pravilu "if ''time'' is ''short'' then ''risk'' is ''high''" ''Sugenove'' mašine, ''short'' je:
# diskretan fuzzy skup
# <span class="solution">kontinualan fuzzy skup</span>
# klasičan skup
# lingvistička varijabla
# nijedno od ponuđenog
</div>
<div class="abc-list" data-solution="single">
U pravilu "if ''time'' is ''short'' then ''risk'' is ''high''" ''Mamdanijeve'' mašine, ''short'' je:
# diskretan fuzzy skup
# <span class="solution">kontinualan fuzzy skup</span>
# klasičan skup
# lingvistička varijabla
# nijedno od ponuđenog
</div>
Objašnjenje: <span class="spoiler" data-solution="explanation">I kod Mamdanijeve i kod Sugenove mašine ulazni skupovi moraju biti kontinualni.</span>
<div class="abc-list" data-solution="single">
Ako je rezultat izvršenja svih pravila ''Mamdanijeve'' mašine prazan skup, rezultat (maksimum) agregacije je:
# prazan diskretan fuzzy skup
# <span class="solution">prazan kontinualan fuzzy skup</span>
# prazan klasičan skup
# realna vrednost 0
# nijedno od ponuđenog
</div>
<div class="abc-list" data-solution="single">
Ako je rezultat izvršenja svih pravila ''Sugenove'' mašine prazan skup, rezultat (maksimum) agregacije je:
# <span class="solution">prazan diskretan fuzzy skup</span>
# prazan kontinualan fuzzy skup
# prazan klasičan skup
# realna vrednost 0
# nijedno od ponuđenog
</div>
<div class="abc-list" data-solution="single">
Rezultat Center of Gravity defazifikacije praznog fuzzy skupa je:
# prazan diskretan fuzzy skup
# prazan kontinualan fuzzy skup
# prazan klasičan skup
# realna vrednost 0
# <span class="solution">nijedno od ponuđenog</span>
</div>
Objašnjenje: <span class="spoiler" data-solution="explanation">Defazifikacija praznog fuzzy skupa proizvodi nedefinisano ponašanje.</span>
<div class="abc-list" data-solution="single">
Rezultat Weighted Average defazifikacije praznog fuzzy skupa je:
# prazan diskretan fuzzy skup
# prazan kontinualan fuzzy skup
# prazan klasičan skup
# realna vrednost 0
# <span class="solution">nijedno od ponuđenog</span>
</div>
Objašnjenje: <span class="spoiler" data-solution="explanation">Defazifikacija praznog fuzzy skupa proizvodi nedefinisano ponašanje.</span>

== 2. zadatak ==
Za kontinualne fuzzy skupove <math>A</math>, <math>B</math> i <math>C</math> definisane su funkcije pripadanja:
* <math>\mu_A(x) = \left\{\begin{array}{ll}
1 + \frac{x}{4}, & -4 \leq x \leq 0 \\
1 - \frac{x}{4}, & 0 < x \leq 4
\end{array}\right.</math>
* <math>\mu_B(x) = \left\{\begin{array}{ll}
2 + \frac{x}{2}, & -4 \leq x < -2 \\
1, & -2 \leq x < 0 \\
1 - \frac{x}{2}, & 0 \leq x < 2 \\
0 & 2 \leq x \leq 4
\end{array}\right.</math>
* <math>\mu_C(x) = \left\{\begin{array}{ll}
y + 1, & -1 \leq y < 0 \\
1, & 0 \leq y \leq 1 \\
\frac{3-y}{2}, & 1 < y \leq 3
\end{array}\right.</math>
<div class="abc-list">
# Skicirati funkcije pripadanja za fuzzy skupove: (standardna) unija <math>A \cup B</math>, (standardni) komplement <math>\neg B</math> i (standardni) komplement <math>\neg C</math>.
# Ako se primenjuje '''scaling implikacija''', a konkretno je <math>x = 1</math>, skicirati rezultat izvršavanja pravila <math>\text{R1: if}\ x\ \text{is}\ \neg B\ \text{then}\ y\ \text{is}\ C</math>.
# Ako se primenjuje '''scaling implikacija''', rezultat izvršavanja pravila <math>\text{R1: if}\ x\ \text{is}\ \neg B\ \text{then}\ y\ \text{is}\ C</math> biće ''prazan skup'' za opseg konkretnih vrednosti ulazne varijable: _______________
# Ako se primenjuje '''clipping implikacija''', a konkretno je <math>x = -1</math>, skicirati rezultat izvršavanja pravila <math>\text{R1: if}\ x\ \text{is}\ A\ \text{then}\ y\ \text{is}\ \neg C</math>.
</div>

== 3. zadatak ==
Za diskretne fuzzy skupove <math>A</math>, <math>B</math> i <math>C</math> definisane su funkcije pripadanja:
* <math>\mu_A(z) = 0.1|50 + 0.3|-30 + 0.1|-10 + 0.1|10 + 0.0|30</math>
* <math>\mu_B(z) = 0.0|50 + 0.4|-30 + 0.6|-10 + 0.7|10 + 0.5|30</math>
* <math>\mu_C(z) = 0.5|50 + 1.0|-30 + 0.8|-10 + 0.5|10 + 0.1|30</math>
<div class="abc-list">
# Ako je presek skupova definisan kao ''proizvod'' pripadnosti, tada je za <math>D = A \cap B \cap C</math>:
#: <math>\mu_D(z) =</math>
# Rezultat standardne (weighted average) defazifikacije, primenjene nad skupom <math>D = A \cap B \cap C</math> je:
#: <math>z_{WA} =</math>
</div>

[[Категорија:Неуралне мреже]]
[[Категорија:Рокови]]

АСП1/К1 2020

2022-02-20T15:48:04Z

Lukahrvacevic: /* 8. zadatak */

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

== 1. zadatak ==
=== Postavka ===
Neka je data funkcija ''random()'' koja vraća broj 0 ili 1 sa podjednakom verovatnoćom. Objasniti i ilustrovati primerom kako bi se korišćenjem zadate funkcije implementirala funkcija koja vraća vrednost 0 sa verovatnoćom 25%, a sa 1 verovatnoćom od 75%.

=== Rešenje ===
U okviru naše nove funkcije pozivamo funkciju random dva puta, i samo u jednom od četiri slučaja, na primer kada oba puta funkcija vrati nulu (00), naša nova funkcija vraća nulu, a za sve ostale slučajeve (01, 10, 11) vraća jedan. Na taj način je obezbeđeno da funkcija vraća 0 sa verovatnoćom 25%, a 1 sa verovatnoćom 75%.
<syntaxhighlight lang="milo">
NEW RANDOM()
if (random() = 0) and (random() = 0) then
return 0
else
return 1
end_if
</syntaxhighlight>

== 2. zadatak ==
=== Postavka ===
Neka je dat stek ''s1'' na kome se nalaze celi brojevi. Korišćenjem dodatnog steka ''s2'', transformisati sadržaj steka ''s1'' tako da on postane neopadajuće uređen niz. Smatrati da su operacije za rad sa stekom već implementirane.

=== Rešenje ===
Ideja jeste da na steku ''s1'' imamo sortirani i nesortirani deo. Na početku svi elementi su u nesortiranom delu i određujemo dubinu steka i trenutni maksimum na njemu. Svakom narednom iteracijom sve elemente koji su manji od maksimuma prebacujemo na stek ''s2'', dok sve maksimume izbacujemo sa steka, a zatim naknadno ubacujemo onoliko puta koliko su se pojavili. Na kraju, vraćamo sve ne-maksimalne elemente sa steka ''s2'' nazad u nesortirani deo steka ''s1'', pritom ponovo određujući maksimalni element u nesortiranom delu. Proces se ponavlja dok ima elemenata u maksimalnom delu.
<syntaxhighlight lang="milo">
SORT STACK(s1)
max = TOP(s1)
cnt = 0
while (not STACK_IS_EMPTY(s1)) do
x = POP(s1)
if (x > max) then
max = x
end_if
PUSH(s2, x)
cnt = cnt + 1
end_while
while (not STACK_IS_EMPTY(s2)) do
x = POP(s2)
PUSH(s1, x)
end_while
while (cnt > 0) do
num = cnt
tmp = 0
while (num > 0) do
x = POP(s1)
if (x < max) then
PUSH(s2, x)
else
cnt = cnt - 1
tmp = tmp + 1
end_if
num = num - 1
end_while
for i = 1 to tmp do
PUSH(s1, max)
i = i + 1
end_for
if (cnt > 0) then
max = TOP(s2)
while (not STACK_IS_EMPTY(s2)) do
x = POP(s2)
if (x > max) then
max = x
end_if
PUSH(s1, x)
end_while
end_if
end_while
</syntaxhighlight>

== 3. zadatak ==
=== Postavka ===
Posmatra se retka matrica A veličine NxM. Matrica je data u vidu kružnih ulančanih listi sa zaglavljima R<sub>A</sub> i C<sub>A</sub>. Napisati efikasnu iterativnu funkciju u pseudokodu koja datu matricu pretvara u vektorski format sa tri posebna vektora R, C i V. Funkcija takođe treba da vrati broj nenultih elemenata u matrici. Smatrati da je za sve vektore inicijalno rezervisano dovoljno prostora.

=== Rešenje ===
<syntaxhighlight lang="milo">
REFORMAT SPARSE MAT(A, N, M, Ra, Ca, R, C, V)
cnt = 1
for i = 1 to N do
curr = next(Ra[i])
R[i] = cnt
while (curr ≠ Ra[i]) do
C[cnt] = col(curr)
V[cnt] = val(curr)
cnt = cnt + 1
curr = next(curr)
end_while
end_for
R[N + 1] = cnt + 1
return cnt
</syntaxhighlight>

== 4. zadatak ==
=== Postavka ===
Transformisati izraz u infiksnom obliku
: A+C^(D-E!)!^F*B-C+G*H
u ekvivalentni izraz u postfiksnoj formi. Tabelu prioriteta operatora dopuniti odgovarajućim vrednostima, pri čemu je operacija faktorijel ! unarna operacija koja se grupiše sleva na desno i ima najveći prioritet od svih aritmetičkih operacija, a operacija ^ je operacija stepenovanja i grupiše se sdesna na levo. Transformaciju izraza prikazati po koracima.

=== Rešenje ===
{| class="wikitable"
! operator
! ul. pr !! stek pr. !! R
|-
! +, -
| 2 || 2 || -1
|-
! *, /
| 3 || 3 || -1
|-
! ^
| 5 || 4 || -1
|-
! !
| 6 || 6 || 0
|-
! (
| 7 || 0 || -
|-
! )
| 1 || - || -
|}
Postfiksna forma datog infiksnog izraza koji se dobije primenom algoritma za konverziju iz infiksa u postfiks je:
: ACDE!-!F^^B*+C-GH*+

== 5. zadatak ==
=== Postavka ===
Data je retko popunjena kvadratna matrica 2N x 2N. Nepodrazumevani elementi matrice smeštaju se u memoriji po vrstama. Indeksiranje kreće od 1, a svaki element matrice zauzima po 2 reči.
<div class="abc-list">
# Izvesti adresnu funkciju za pristup proizvoljnom elementu matrice.
# Implementirati funkciju GET koja vraća vrednost traženog elementa koji odgovara indeksima ''i'' i ''j'' matrice ''A''.
</div>

=== Rešenje ===
<div class="abc-list">
# <math>A_{ij} = \left\{
\begin{array}{ll}
A_{11} + ((i-1) \cdot 2+\left\lfloor{(j-1)/N)}\right\rfloor) \cdot 2 & i=j \lor i+j=2N+1 \\
0 & i \neq j \land i+j \neq 2N+1
\end{array}\right.</math>
# <syntaxhighlight lang="milo">
GET(A, i, j, N)
if (i = j or i + j = 2 * N + 1) then
return A[i, j]
else
return 0
end_if
</syntaxhighlight>
</div>

== 6. zadatak ==
=== Postavka ===
U nekom azilu za životinje su zbrinuti psi, mačke i kanarinci. Kada neko želi da usvoji životinju, on se može izjasniti da li želi psa, mačku, kanarinca ili mu je svejedno. Nije moguće uputiti zahtev za određenom (pojedinačnom) životinjom već u skladu sa odabirom vrste, biće dodeljena ili životinja tražene vrste koja je najduže u azilu, ako takva postoji, ili životinja koja je tu duže od svih drugih. Takođe, azil prihvata nove životinje dok se ne popuni kapacitet.
<div class="abc-list">
# Ukratko objasniti koja struktura se koristi za modelovanje azila i kako se ona održava sa dolaskom i usvajanjem životinja.
# Prikazati kako će struktura usvojena pod a) izgledati nakon usvajanja jednog psa, ako je prikazano trenutno stanje životinja u azilu po boksovima u kojima su smešteni. Pored vrste životinje, radi ilustracije, u zagradi se nalazi i trenutno vreme boravka životinje u azilu.
#: M(2) K(1) P(6) P(3) M(6) M(7) K(5) P(3)
</div>

=== Rešenje ===
{{delimično rešeno}}

== 7. zadatak ==
=== Postavka ===
U nekom programu je potrebno prestaviti skup celih brojeva u opsegu od 0 do 999. Neka su u programskom jeziku koji se koristi na raspolaganju celobrojni tipovi na 4 bajta širine, a pokazivači zauzimaju 4 bajta. Objasniti na koje načine se ovakav skup može predstaviti sekvencijalnom i ulančanom reprezantacijom, a zatim odrediti prosečno zauzeće prostora u oba slučaja pod pretpostavkom da se u skupu u proseku nalazi 10 elemenata.

=== Rešenje ===
{{delimično rešeno}}

== 8. zadatak ==
=== Postavka ===
Napisati u pseudokodu implementaciju funkcije koja u dvostruko ulančanu listu celih brojeva na koju ukazuje pokazivač ''list'' ubacuje vrednost ''x'' ispred elementa na koji ukazuje pokazivač ''node''. Voditi računa da lista ostane u potpuno konzistentnom stanju.

=== Rešenje ===
Pretpostavljamo da je ''node'' validan pokazivač na element koji se nalazi u listi ''list''.
<syntaxhighlight lang="milo">
INSERT BEFORE D(list, node, x)
new_node = Node(x)
new_node.prev = node.prev
new_node.next = node
if node.prev == null
list = new_node
else
node.prev.next = new_node
node.prev = new_node
</syntaxhighlight>

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

АСП1/Август 2021

2022-02-20T15:35:52Z

Lukahrvacevic: /* 9. zadatak */

{{tocright}}
Ovaj članak je rekreacija avgustovskog roka koji nije objavljen.

== 1. zadatak ==
{{delimično rešeno}}
=== Postavka ===
Data je retka matrica koja je prikazana na slici. (Data je matrica npr. 5*6 sa 5 ili 6 random nenultih elemenata).
<div class="abc-list">
# Nacrtati izgled delova memorije u kojima se čuva ova retka matrica, ako se primenjuje ''Compressed Sparse Row'' način čuvanja.
# Napisati funkciju u pseudokodu koja na osnovu sačuvane ''Compressed Sparse Row'' reprezentacije matrice M i unetog broja ''i'' štampa sve nenulte elemente ''i''-te vrste.
</div>
=== Rešenje ===
== 2. zadatak ==
=== Postavka ===
Navedite načine reprezentacije grafova i njihove prednosti i mane.
=== Rešenje ===
Potrebno je samo napisati i prokomentarisati tabelu 7.1 sa strane 161 iz udžbenika.
== 3. zadatak ==
=== Postavka ===
Zadato je binarno stablo S i date su adrese dva čvora ''x'' i ''y''. Napisati funkciju u pseudokodu koja pronalazi najnižeg zajedničkog pretka zadata dva čvora.
=== Rešenje ===
<syntaxhighlight lang="milo">
LOWEST_COMMON_ANCESTOR(S,x,y)
return FIND(S,x,y)
</syntaxhighlight>
<syntaxhighlight lang="milo">
FIND(S,x,y)
if S == null
return null
end_if
if S == x || S == y
return S
end_if
left = FIND(S.left,x,y)
right = FIND(S.right,x,y)
if left ≠ null && right ≠ null
return S
else if left ≠ null
return left
else if right ≠ null
return right
else
return null
end_if
</syntaxhighlight>

== 4. zadatak ==
=== Postavka ===
Potpuno formalno izvesti međusobnu zavisnost interne i eksterne dužine puta u binarnom stablu i kratko obrazložiti.
=== Rešenje ===
<math> PE = PI + 2n </math>, gde je <math>n</math> broj čvorova u stablu
izvođenje indukcijom, kao u knjizi/na predavanju.
== 5. zadatak ==
=== Postavka ===
Potrebno je realizovati aplikaciju za obradu slika. Korisniku je potrebno da za uneti set slika i unet set operacija omogućiti da se sve operacije izvrše nad svim unetim slikama. Navesti koje strukture je pogodno koristiti za čuvanje seta slika i seta operacija i objasniti zašto. Napisati funkciju u pseudokodu koja obrađuje uneti set slika unetim setom operacija, u skladu sa odabranim strukturama podataka.
=== Rešenje ===
''Rešenje je krajnje trivijalno i ovde je navedeno jedno koje je bodovano maksimalnim brojem poena.''
Za oba se može koristiti jednostruko ulančana lista (jer nije bitan redosled kojim će se operacije izvršavati jer će se svakako sve izvršiti na svim slikama), a ulančane liste su pogodno za lako dodavanje i brisanje elemenata.
<syntaxhighlight lang="milo">
PROCESS_IMAGES(images, operations)
S = head(images)
O = head(operations)
while s ≠ NIL do
while o ≠ NIL do
data(S) = (operation(O))(data(S))
end_while
end_while
</syntaxhighlight>
== 6. zadatak ==
=== Postavka ===
'''Huffman-ov algoritam''': Dat јe tekst sa 6 slova dužine 21 slovo. Odrediti izgled stabla dobijenog statičkim Huffman-om za ovaj tekst i uporediti prosečan broj bitova za čuvanje ovog teksta, kao i jednog slova u slučaju da se čuva podrazumevano i na osnovu ovog Huffman stabla. Frekvenciju slova zaključiti iz teksta.
=== Rešenje ===
Najobičniji statički Huffman za zadatim frekvencijama.

== 7. zadatak ==
=== Postavka ===
Dat je grad koji je modelovan usmerenim grafom, tako što su čvorovi lokacije u gradu (pekara, apoteka, biblioteka itd), a težine grana između čvorova vreme u minutima koje je potrebno da se peške dođe od izvorišne do odredišne lokacije. Dete želi da stigne od škole (čvor ''X'') do kuće (čvor ''Y'') najbrže moguće. Međutim, postoji opasan deo grada (čvor Z), koji nije bezbedan za decu i koji ona treba da izbegavaju. Napisati funkciju u pseudokodu koja na osnovu zadatog grafa ''G'' (nije data reprezentacija, rešenje treba da bude konceptualno), zadatih lokacija kuće i škole, ''Y'' i ''X'', i opasnog dela grada ''Z'', pronalazi najkraće vreme koje je detetu potrebno od škole do kuće.
=== Rešenje ===
Zadatak se rešava implementacijom Dijkstrinog algortima, tako što kada se u uzimanju čvorova redom po težinskoj udaljenosti od početnog dođe do "opasnog" čvora ''Z'', za njega se upiše težina beskonačno i ta petlja preskoči sa '''continue'''. Na kraju se samo proveri dostižnost ciljnog čvora.
== 8. zadatak ==
=== Postavka ===
Dat je graf na slici (ima nekih 7-8 čvorova). Za dati graf uraditi topološko sortiranje i prikazati graf dobijen tako.
=== Rešenje ===
{{delimično rešeno}}
== 9. zadatak==
=== Postavka ===
<div class="abc-list">
# Detaljno opisati postupak za pronalaženje jako povezanih komponenti u grafu.
# Za graf sa slike (nekih 7-8 čvorova) po koracima primeniti algoritam za pronalaženje jako povezanih komponenti i rezultujući graf.
</div>
=== Rešenje ===
Videti zadatak iz [[АСП1/Јул 2020#Treći kolokvijum|julskog roka 2020.]]

== 10. zadatak ==
=== Postavka ===
Potrebno je čuvati neki skup brojeva koji će biti u opsegu između 1 i 100.
<div class="abc-list">
# Uporediti sekvencijalnu i ulančanu reprezentaciju skupa i uporediti složenost operacija dodavanja elementa, brisanja elementa i provere pripadnosti elementa skupu za ove dve reprezentacije.
# Neka je dat skup (npr. 5, 14, 44, 45, 78, 98) prikazati jednu i drugu reprezenatciju nakon operacija (npr. dodavanje 7, dodavanje 46, dodavanje 97, brisanje 78).
</div>
=== Rešenje ===
Kod sekvencijalne se alocira vektor S[1:100] i ukoliko je element ''X'' u skupu, u polje ''S''[''X''] se upisuje 1, inače 0. Kod ulančane reprezentacije je najefikasnije čuvati ulančanu listu u rastućem ili opadajućem poretku. Dodavanje/brisanje u sekvencijalnoj se radi u O(1) tako što se samo proveri ili izmeni indeks u nizu. Kod ulančane reprezentacije je potrebno proći kroz listu do lokacije na koju treba umetnuti/obrisati element (po rastućem ili opadajućem poretku).

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

АСП1/Август 2021

2022-02-20T15:23:01Z

Lukahrvacevic: /* 3. zadatak */

{{tocright}}
Ovaj članak je rekreacija avgustovskog roka koji nije objavljen.

== 1. zadatak ==
{{delimično rešeno}}
=== Postavka ===
Data je retka matrica koja je prikazana na slici. (Data je matrica npr. 5*6 sa 5 ili 6 random nenultih elemenata).
<div class="abc-list">
# Nacrtati izgled delova memorije u kojima se čuva ova retka matrica, ako se primenjuje ''Compressed Sparse Row'' način čuvanja.
# Napisati funkciju u pseudokodu koja na osnovu sačuvane ''Compressed Sparse Row'' reprezentacije matrice M i unetog broja ''i'' štampa sve nenulte elemente ''i''-te vrste.
</div>
=== Rešenje ===
== 2. zadatak ==
=== Postavka ===
Navedite načine reprezentacije grafova i njihove prednosti i mane.
=== Rešenje ===
Potrebno je samo napisati i prokomentarisati tabelu 7.1 sa strane 161 iz udžbenika.
== 3. zadatak ==
=== Postavka ===
Zadato je binarno stablo S i date su adrese dva čvora ''x'' i ''y''. Napisati funkciju u pseudokodu koja pronalazi najnižeg zajedničkog pretka zadata dva čvora.
=== Rešenje ===
<syntaxhighlight lang="milo">
LOWEST_COMMON_ANCESTOR(S,x,y)
return FIND(S,x,y)
</syntaxhighlight>
<syntaxhighlight lang="milo">
FIND(S,x,y)
if S == null
return null
end_if
if S == x || S == y
return S
end_if
left = FIND(S.left,x,y)
right = FIND(S.right,x,y)
if left ≠ null && right ≠ null
return S
else if left ≠ null
return left
else if right ≠ null
return right
else
return null
end_if
</syntaxhighlight>

== 4. zadatak ==
=== Postavka ===
Potpuno formalno izvesti međusobnu zavisnost interne i eksterne dužine puta u binarnom stablu i kratko obrazložiti.
=== Rešenje ===
<math> PE = PI + 2n </math>, gde je <math>n</math> broj čvorova u stablu
izvođenje indukcijom, kao u knjizi/na predavanju.
== 5. zadatak ==
=== Postavka ===
Potrebno je realizovati aplikaciju za obradu slika. Korisniku je potrebno da za uneti set slika i unet set operacija omogućiti da se sve operacije izvrše nad svim unetim slikama. Navesti koje strukture je pogodno koristiti za čuvanje seta slika i seta operacija i objasniti zašto. Napisati funkciju u pseudokodu koja obrađuje uneti set slika unetim setom operacija, u skladu sa odabranim strukturama podataka.
=== Rešenje ===
''Rešenje je krajnje trivijalno i ovde je navedeno jedno koje je bodovano maksimalnim brojem poena.''
Za oba se može koristiti jednostruko ulančana lista (jer nije bitan redosled kojim će se operacije izvršavati jer će se svakako sve izvršiti na svim slikama), a ulančane liste su pogodno za lako dodavanje i brisanje elemenata.
<syntaxhighlight lang="milo">
PROCESS_IMAGES(images, operations)
S = head(images)
O = head(operations)
while s ≠ NIL do
while o ≠ NIL do
data(S) = (operation(O))(data(S))
end_while
end_while
</syntaxhighlight>
== 6. zadatak ==
=== Postavka ===
'''Huffman-ov algoritam''': Dat јe tekst sa 6 slova dužine 21 slovo. Odrediti izgled stabla dobijenog statičkim Huffman-om za ovaj tekst i uporediti prosečan broj bitova za čuvanje ovog teksta, kao i jednog slova u slučaju da se čuva podrazumevano i na osnovu ovog Huffman stabla. Frekvenciju slova zaključiti iz teksta.
=== Rešenje ===
Najobičniji statički Huffman za zadatim frekvencijama.

== 7. zadatak ==
=== Postavka ===
Dat je grad koji je modelovan usmerenim grafom, tako što su čvorovi lokacije u gradu (pekara, apoteka, biblioteka itd), a težine grana između čvorova vreme u minutima koje je potrebno da se peške dođe od izvorišne do odredišne lokacije. Dete želi da stigne od škole (čvor ''X'') do kuće (čvor ''Y'') najbrže moguće. Međutim, postoji opasan deo grada (čvor Z), koji nije bezbedan za decu i koji ona treba da izbegavaju. Napisati funkciju u pseudokodu koja na osnovu zadatog grafa ''G'' (nije data reprezentacija, rešenje treba da bude konceptualno), zadatih lokacija kuće i škole, ''Y'' i ''X'', i opasnog dela grada ''Z'', pronalazi najkraće vreme koje je detetu potrebno od škole do kuće.
=== Rešenje ===
Zadatak se rešava implementacijom Dijkstrinog algortima, tako što kada se u uzimanju čvorova redom po težinskoj udaljenosti od početnog dođe do "opasnog" čvora ''Z'', za njega se upiše težina beskonačno i ta petlja preskoči sa '''continue'''. Na kraju se samo proveri dostižnost ciljnog čvora.
== 8. zadatak ==
=== Postavka ===
Dat je graf na slici (ima nekih 7-8 čvorova). Za dati graf uraditi topološko sortiranje i prikazati graf dobijen tako.
=== Rešenje ===
{{delimično rešeno}}
== 9. zadatak==
=== Postavka ===
<div class="abc-list">
# Detaljno opisati postupak za pronalaženje jako povezanih komponenti u grafu.
# Za graf sa slike (nekih 7-8 čvorova) po koracima primeniti algoritam za pronalaženje jako povezanih komponenti i rezultujući graf.
</div>
=== Rešenje ===
{{delimično rešeno}}
== 10. zadatak ==
=== Postavka ===
Potrebno je čuvati neki skup brojeva koji će biti u opsegu između 1 i 100.
<div class="abc-list">
# Uporediti sekvencijalnu i ulančanu reprezentaciju skupa i uporediti složenost operacija dodavanja elementa, brisanja elementa i provere pripadnosti elementa skupu za ove dve reprezentacije.
# Neka je dat skup (npr. 5, 14, 44, 45, 78, 98) prikazati jednu i drugu reprezenatciju nakon operacija (npr. dodavanje 7, dodavanje 46, dodavanje 97, brisanje 78).
</div>
=== Rešenje ===
Kod sekvencijalne se alocira vektor S[1:100] i ukoliko je element ''X'' u skupu, u polje ''S''[''X''] se upisuje 1, inače 0. Kod ulančane reprezentacije je najefikasnije čuvati ulančanu listu u rastućem ili opadajućem poretku. Dodavanje/brisanje u sekvencijalnoj se radi u O(1) tako što se samo proveri ili izmeni indeks u nizu. Kod ulančane reprezentacije je potrebno proći kroz listu do lokacije na koju treba umetnuti/obrisati element (po rastućem ili opadajućem poretku).

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

АСП1/Август 2021

2022-02-20T15:17:27Z

Lukahrvacevic: /* 3. zadatak */

{{tocright}}
Ovaj članak je rekreacija avgustovskog roka koji nije objavljen.

== 1. zadatak ==
{{delimično rešeno}}
=== Postavka ===
Data je retka matrica koja je prikazana na slici. (Data je matrica npr. 5*6 sa 5 ili 6 random nenultih elemenata).
<div class="abc-list">
# Nacrtati izgled delova memorije u kojima se čuva ova retka matrica, ako se primenjuje ''Compressed Sparse Row'' način čuvanja.
# Napisati funkciju u pseudokodu koja na osnovu sačuvane ''Compressed Sparse Row'' reprezentacije matrice M i unetog broja ''i'' štampa sve nenulte elemente ''i''-te vrste.
</div>
=== Rešenje ===
== 2. zadatak ==
=== Postavka ===
Navedite načine reprezentacije grafova i njihove prednosti i mane.
=== Rešenje ===
Potrebno je samo napisati i prokomentarisati tabelu 7.1 sa strane 161 iz udžbenika.
== 3. zadatak ==
=== Postavka ===
Zadato je binarno stablo S i date su adrese dva čvora ''x'' i ''y''. Napisati funkciju u pseudokodu koja pronalazi najnižeg zajedničkog pretka zadata dva čvora.
=== Rešenje ===
<syntaxhighlight lang="milo">
LOWEST_COMMON_ANCESTOR(S,x,y)
return FIND(S,x,y)
</syntaxhighlight>
<syntaxhighlight lang="milo">
FIND(S,x,y)
if S==null
return null
end_if
if S == x || S == y
return S
end_if
left = FIND(S.left,x,y)
right = FIND(S.right,x,y)
if left ≠ null && right ≠ null
return S
else if left ≠ null
return left
else if right ≠ null
return right
else
return null
end_if
</syntaxhighlight>

== 4. zadatak ==
=== Postavka ===
Potpuno formalno izvesti međusobnu zavisnost interne i eksterne dužine puta u binarnom stablu i kratko obrazložiti.
=== Rešenje ===
<math> PE = PI + 2n </math>, gde je <math>n</math> broj čvorova u stablu
izvođenje indukcijom, kao u knjizi/na predavanju.
== 5. zadatak ==
=== Postavka ===
Potrebno je realizovati aplikaciju za obradu slika. Korisniku je potrebno da za uneti set slika i unet set operacija omogućiti da se sve operacije izvrše nad svim unetim slikama. Navesti koje strukture je pogodno koristiti za čuvanje seta slika i seta operacija i objasniti zašto. Napisati funkciju u pseudokodu koja obrađuje uneti set slika unetim setom operacija, u skladu sa odabranim strukturama podataka.
=== Rešenje ===
''Rešenje je krajnje trivijalno i ovde je navedeno jedno koje je bodovano maksimalnim brojem poena.''
Za oba se može koristiti jednostruko ulančana lista (jer nije bitan redosled kojim će se operacije izvršavati jer će se svakako sve izvršiti na svim slikama), a ulančane liste su pogodno za lako dodavanje i brisanje elemenata.
<syntaxhighlight lang="milo">
PROCESS_IMAGES(images, operations)
S = head(images)
O = head(operations)
while s ≠ NIL do
while o ≠ NIL do
data(S) = (operation(O))(data(S))
end_while
end_while
</syntaxhighlight>
== 6. zadatak ==
=== Postavka ===
'''Huffman-ov algoritam''': Dat јe tekst sa 6 slova dužine 21 slovo. Odrediti izgled stabla dobijenog statičkim Huffman-om za ovaj tekst i uporediti prosečan broj bitova za čuvanje ovog teksta, kao i jednog slova u slučaju da se čuva podrazumevano i na osnovu ovog Huffman stabla. Frekvenciju slova zaključiti iz teksta.
=== Rešenje ===
Najobičniji statički Huffman za zadatim frekvencijama.

== 7. zadatak ==
=== Postavka ===
Dat je grad koji je modelovan usmerenim grafom, tako što su čvorovi lokacije u gradu (pekara, apoteka, biblioteka itd), a težine grana između čvorova vreme u minutima koje je potrebno da se peške dođe od izvorišne do odredišne lokacije. Dete želi da stigne od škole (čvor ''X'') do kuće (čvor ''Y'') najbrže moguće. Međutim, postoji opasan deo grada (čvor Z), koji nije bezbedan za decu i koji ona treba da izbegavaju. Napisati funkciju u pseudokodu koja na osnovu zadatog grafa ''G'' (nije data reprezentacija, rešenje treba da bude konceptualno), zadatih lokacija kuće i škole, ''Y'' i ''X'', i opasnog dela grada ''Z'', pronalazi najkraće vreme koje je detetu potrebno od škole do kuće.
=== Rešenje ===
Zadatak se rešava implementacijom Dijkstrinog algortima, tako što kada se u uzimanju čvorova redom po težinskoj udaljenosti od početnog dođe do "opasnog" čvora ''Z'', za njega se upiše težina beskonačno i ta petlja preskoči sa '''continue'''. Na kraju se samo proveri dostižnost ciljnog čvora.
== 8. zadatak ==
=== Postavka ===
Dat je graf na slici (ima nekih 7-8 čvorova). Za dati graf uraditi topološko sortiranje i prikazati graf dobijen tako.
=== Rešenje ===
{{delimično rešeno}}
== 9. zadatak==
=== Postavka ===
<div class="abc-list">
# Detaljno opisati postupak za pronalaženje jako povezanih komponenti u grafu.
# Za graf sa slike (nekih 7-8 čvorova) po koracima primeniti algoritam za pronalaženje jako povezanih komponenti i rezultujući graf.
</div>
=== Rešenje ===
{{delimično rešeno}}
== 10. zadatak ==
=== Postavka ===
Potrebno je čuvati neki skup brojeva koji će biti u opsegu između 1 i 100.
<div class="abc-list">
# Uporediti sekvencijalnu i ulančanu reprezentaciju skupa i uporediti složenost operacija dodavanja elementa, brisanja elementa i provere pripadnosti elementa skupu za ove dve reprezentacije.
# Neka je dat skup (npr. 5, 14, 44, 45, 78, 98) prikazati jednu i drugu reprezenatciju nakon operacija (npr. dodavanje 7, dodavanje 46, dodavanje 97, brisanje 78).
</div>
=== Rešenje ===
Kod sekvencijalne se alocira vektor S[1:100] i ukoliko je element ''X'' u skupu, u polje ''S''[''X''] se upisuje 1, inače 0. Kod ulančane reprezentacije je najefikasnije čuvati ulančanu listu u rastućem ili opadajućem poretku. Dodavanje/brisanje u sekvencijalnoj se radi u O(1) tako što se samo proveri ili izmeni indeks u nizu. Kod ulančane reprezentacije je potrebno proći kroz listu do lokacije na koju treba umetnuti/obrisati element (po rastućem ili opadajućem poretku).

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

ОС1/Октобар 2013

2022-02-20T14:28:06Z

Lukahrvacevic: /* 10. zadatak */

{{tocright}}
[http://os.etf.bg.ac.rs/OS1/rokovi/2013/okt/OS1%20Okt%202013.pdf Zadaci na stranici predmeta.]

== 1. zadatak ==
=== Postavka ===
Koja je razlika između multiprocesorskih i distribuiranih računarskih sistema?

=== Rešenje ===
Kod multiprocesorskih sistema skup procesora ima deljenu operativnu memoriju, dok kod distribuiranog sistema nema zajedničke operativne memorije, već postoji mrežna komunikacija između procesora.

== 2. zadatak ==
=== Postavka ===
Korišćenjem operacije <code>yield(jmp_buf old, jmp_buf new)</code> koja čuva kontekst niti čiji je <code>jmp_buf</code> dat kao prvi argument, oduzima joj procesor i restaurira kontekst niti čiji je <code>jmp_buf</code> dat kao drugi argument, kojoj predaje procesor, realizovati operaciju <code>Semaphore::wait()</code> u školskom jezgru.

=== Rešenje ===
<syntaxhighlight lang="c">
Semaphore::wait() {
lock();
if(--val < 0) {
jmp_buf old = Thread::running->context;
blocked.put(Thread::running);
Thread::running = Scheduler::get();
jmp_buf new = Thread::running->context;
yield(old, new);
}
unlock();
}
</syntaxhighlight>

== 3. zadatak ==
=== Postavka ===
Koja je razlika između (teškog) procesa i niti (''thread'')?

=== Rešenje ===
Teški proces je izvršavanje jednog programa sa sopstvenim adresnim prostorom dok se nitima, tj. lakim procesima zove svaki tok kontrole koji koristi taj adresni prostor.

== 4. zadatak ==
=== Postavka ===
Korišćenjem standardnih brojačkih semafora, napisati kod za inicijalizaciju i potrebnu sinhronizaciju kritične sekcije u koju može ući najviše ''N'' uporednih procesa.

=== Rešenje ===
<syntaxhighlight lang="ada">
var mutex : Semaphore := N;

process P:
begin
loop
wait(mutex);
<critical>
signal(mutex);
<non-critical>
end
end P;
</syntaxhighlight>

== 5. zadatak ==
=== Postavka ===
Ako tokom svog prvog prolaza linker u svojoj tabeli ne pronađe simbol koji je definisan u tekućem fajlu (izvozi se), da li će prijaviti grešku? Obrazložiti.

=== Rešenje ===
Ne jer ako se ne nalazi u tabeli simbola znači da simbol nije definisan i ne dolazi do konflikta imena.

== 6. zadatak ==
=== Postavka ===
Koja je razlika između ''best fit'' i ''worst fit'' algoritma kontinualne alokacije memorije?

=== Rešenje ===
Best fit algoritam ima cilj da nakon alokacije ostane što manji slobodan fragment kako bi se smanjila eksterna fragmentacija.
Worst fit algoritam ima cilja da preostali slobodan fragment bude što upotrebljiviji, odnosno takav da se poveća šansa da se može upotrebiti za dalju alokaciju, tj. ostavlja najveći slobodan fragment nakon alokacije.

== 7. zadatak ==
=== Postavka ===
U nekom sistemu sa virtuelnom memorijom broj stranice u virtuelnoj adresi je veličine 48 bita. Da bi čuvanje PMT učinio izvodljivim, sistem koristi ''hash'' tabelu sa 64K ulaza za smešanje PMT svakog procesa. ''Hash'' funkcija je prosta modulo funkcija: ulaz u tabelu određuje se pomoću 16 najnižih bita broja stranice. U svakom ulazu ''hash'' tabele nalazi se 64-bitna glava ulančane liste zapisa za alocirane stranice koje se preslikavaju u taj ulaz. Svaki zapis sadrži viših 32 bita broja stranice, broj okvira u koji je ta stranica preslikana (32 bita, vrednost 0 označava da stranica ne može da se preslika) i pokazivač na sledeći zapis (64 bita, vrednost 0 označava kraj liste). Neki proces je alocirao 256 najnižih i 256 najviših stranica svog virtuelnog adresnog prostora. Koliko prostora (u bajtovima) ukupno zauzima PMT ovog procesa?

=== Rešenje ===
{{delimično rešeno}}

== 8. zadatak ==
=== Postavka ===
U nekom sistemu podržan je samo asinhroni izlaz na izlazni uređaj pomoću sledeće funkcije

<code>IOReqID output (IODevID deviceID, IOReq* request);</code>

koja zadaje (asinhrono) izlaznu operaciju specifikovanu drugim argumentom na uređaju identifikovanom prvim argumentom. Ova funkcija odmah vraća kontrolu pozivaocu, uz identifikaciju zadate operacije (rezultat tipa <code>IOReqID</code> je veći od 0 u slučaju ispravno zadatog zahteva).
Funkcija

<code>void ioWait (IOReqID);</code>

blokira pozivajući proces sve dok operacija identifikovana argumentom nije završena u potpunosti. Pomoću ovih funkcija realizovati funkciju koja, u odnosu na jedan argument, može zadati operaciju sinhrono ili asinhrono, prema želji pozivaoca.

=== Rešenje ===
<syntaxhighlight lang="c">
IOReqID output_user(IODevID deviceID, IOReq* request, bool synchronous) {
IOReqID id = output(deviceID, request);
if(synchronous && id > 0) wait(id);
return id;
}
</syntaxhighlight>

== 9. zadatak ==
=== Postavka ===
Šta označava skraćenica FTP? Ukratko objasniti čemu služi ovaj protokol.

=== Rešenje ===
File Transfer Protocol - u razmeni fajlova učestvuju 2 računara. Jedan igra ulogu servera a drugi ulogu klijenta. Na oba računara se izvršavaju programi koji implementiraju ovaj protokol.

== 10. zadatak ==
=== Postavka ===
Koja metoda alokacije fajlova je efikasnija za direktni pristup, ulančana ili indeksirana i zašto?
=== Rešenje ===
Efikasnija je indeksirana; kod ulančane alokacije je efikasan sekvencijalan pristup, ali direktni pristup nekom bloku <b>n</b> podrazumeva pristup svim blokovima počev od prvog pa do njega. Jedna od najvecih pogodnosti indeksne alokacije je upravo direktni pristup, jer indeksna alokacija podrazumeva postojanje indeksnog bloka u kome se nalazi spisak brojeva blokova sa sadržajem fajla redom, koji omogućava vrlo efikasan direktan pristup.

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

ОС1/Јун 2016

2022-02-19T23:12:48Z

Lukahrvacevic: /* 10. zadatak */

{{tocright}}
[http://os.etf.bg.ac.rs/OS1/rokovi/2016/jun/Jun%202016.pdf Zadaci na stranici predmeta.]

== 1. zadatak ==
=== Postavka ===
Šta se smatralo najvećim nedostatkom prvobitnih paketnih (''batch'') sistema i kako je taj nedostatak rešen?

=== Rešenje ===
Prvobitni batch sistemi su efikasno delili resurse ali nisu interaktivni. Osnovni nedostatak bio je slabo iskorišćenje glavnog resursa računara - procesora. Nedostatak je rešen uvođenjem time sharing-a

== 2. zadatak ==
=== Postavka ===
Korišćenjem funkcije <code>yield(jmp_buf old, jmp_buf new)</code> koja čuva kontekst jedne niti i predaje procesor drugoj niti, realizovati operaciju <code>wait</code> na brojačkom semaforu u školskom jezgru

=== Rešenje ===
Videti zadatak iz [[ОС1/Октобар 2013#2. zadatak|oktobarskog roka 2013]].

== 3. zadatak ==
=== Postavka ===
Za sledeće slučajeve navesti u koje stanje prelazi tekući (''running'') proces i naznačiti da li se to dešava kao posledica sistemskog poziva od strane tog tekućeg procesa ili spoljašnjeg prekida.

=== Rešenje ===


== 4. zadatak ==
=== Postavka ===
Napisati kod koji realizuje Petersonov algoritam međusobnog isključenja dva uporedna procesa pomoću uposlenog čekanja.

=== Rešenje ===
<syntaxhighlight lang="ada">
shared var turn : integer := 1, flag1, flag2 : boolean := false;

process P1
begin
loop
flag1 := true; turn := 2;
while flag2 and turn = 2 do null;
<critical section>
flag1 := false;
<non-critical section>
end
end P1;

process P2
begin
loop
flag2 := true; turn := 1;
while flag1 and turn = 1 do null;
<critical section>
flag2 := false;
<non-critical section>
end
end P2;
</syntaxhighlight>

== 5. zadatak ==
=== Postavka ===
Precizno objasniti zašto klasičan linker svoj posao obavlja u dva prolaza (a ne može samo u jednom). Obrazloženje ilustrovati primerom.

=== Rešenje ===
U prvom prolazu linker pravi globalnu mapu .obj fajlova i globalno definisanih izvezenih simbola i njihovih adresa relativno u odnosu na početak .obj fajla. U drugom prolazu razrešava nerazrešena adresna polja koristeći definisane simbole u tabeli simbola.

== 6. zadatak ==
=== Postavka ===
Virtuelni adresni prostor sistema je 8GB, adresibilna jedinica je 16-bitna reč, a virtuelni adresni prostor je organizovan stranično sa stranicom veličine 32KB. Fizički adresni prostor je veličine 2GB. Tabele preslikavanja stranica su organizovane u dva nivoa, s tim da tabela prvog nivoa ima 2K ulaza. Svaki ulaz u PMT oba nivoa zauzima samo onoliko koliko je potrebno da se smesti broj okvira (PMT drugog nivoa je poravnata na okvir). Koliko memorije zauzimaju ukupno PMT procesa koji je alocirao svojih prvih 128 stranica?

=== Rešenje ===
VAS: 2^33B -> VA: 32b, page size 32KB = 2^15B -> page 14b, AU = 2B

PAS: 2GB = 2^31B -> PA: 30b

PMT1: 2K = 2^11 -> 11b

VA: page1(11) : page2(7) : offset(14)

128 stranica -> PMT1 i 1 PMT2 = 2^11 * 2^2 + 2^7 * 2^2 = 8.5KB

== 7. zadatak ==
=== Postavka ===
Neki sistem sa straničnom organizacijom memorije koristi tehniku ''copy on write''. Jedan proces je tek kreirao drugi proces pozivom <code>fork()</code>. Ako novokreirani proces odmah po pokretanju izvrši operaciju upisa u memoriju, koji izuzetak će generisati procesor, ''page fault'' ili neki drugi i koji? Precizno objasniti zašto i kako.

=== Rešenje ===
Procesor će generisati izuzetak ''write prohibited'', jer je u desktriptoru ove stranice označeno da ona nije dozvoljena za upis zbog tek kreiranog procesa deteta.

== 8. zadatak ==
=== Postavka ===
Na asembleru nekog zamišljenog RISC procesora sa LOAD/STORE arhitekturom napisati program koji prenosi blok podataka zadate dužine sa zadate adrese na izlazni uređaj korišćenjem programiranog ulaza/izlaza sa prozivanjem (polling).

=== Rešenje ===
<syntaxhighlight lang="ada">
LD R1, blockAddr
LD R2, cnt
ST [ctrl], #0..1
wait: LD R0, [status]
AND R0, #1..0
JZ wait
LD R0, [R1]
ST [data], R0
INC R1
DEC R2
JNZ wait
ST [ctrl], R0
</syntaxhighlight>

== 9. zadatak ==
=== Postavka ===
Ako fajl sistem koristi dve vrste ključeva, deljeni (''shared'') i ekskluzivni (''exclusive''), sa implicitnim zaključavanjem prilikom otvaranja fajla, koji ključ će biti zahtevan od strane procesa koji otvara fajl sa najavom samo operacije čitanja?

=== Rešenje ===
Deljeni (shared) ključ.

== 10. zadatak ==
=== Postavka ===
Neki sistem evidentira slobodne blokove fajl sistema tako što u jedan slobodan blok smešta spisak (indeks) do ''n'' narednih slobodnih blokova (najmanje 0, najviše ''n''), kao i broj sledećeg takvog indeksnog bloka. Koliki je broj blokova kojima sistem treba da pristupi (na čitanje ili upis) u najgorem slučaju prilikom alokacije jednog slobodnog bloka za sadržaj fajla? Broj prvog takvog bloka u lancu je globalni podatak koji se nalazi u memoriji i njegova eventualna izmena se ne broji.

=== Rešenje ===
Broj blokova kojima sistem treba da pristupi je u svakom slučaju 1. Kada se na spisku nalazi bar jedan slobodan blok, on se alocira i briše sa spiska. Kada se na spisku ne nalazi nijedan slobodan blok, blok u kome se nalazi spisak se alocira kao slobodan blok i u memoriji se menja pokazivač sa njega na sledeći blok sa spiskom.

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