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

Програмски преводиоци 1

2026-03-14T23:15:11Z

Andrija: лабела "Табела симбола"

{{Предмет
| шифра = 13С114ПП1, 13Е114ПП1
| семестар = 7
| статус = обавезни
| страница = [http://ir4pp1.etf.bg.ac.rs/ ir4pp1.etf.rs]
| одсек = СИ, РТИ
}}
Значи '''Програмски преводиоци 1''' је значи обавезни предмет значи у седмом семестру на СИ и РТИ. Ја уопште нисам одговоран за ово манијакално име пакета.

== Корисне везе ==
* [https://drive.google.com/open?id=107YMW0yq1ShVDAIyVtzLGwJ_H8Sm13D1 ETF SI] (модификације)
* [https://app.box.com/s/0r50je333z1qyypz0h3rm0iqb9s0d64f/folder/38797850748 ETF Materijali (Box)] (решења старијих рокова)
* [https://www.youtube.com/playlist?list=PLd4LFMwqLLCfy8fxg6cR6YAEC1jkaDWRt Студентски видео снимци решења задатака са вежби и рокова] (обрађено градиво закључно са „парсирањем од врха ка дну“)
* [https://drive.google.com/open?id=1ZZ8p48rhYnjIxiJaGCFzyRoQv7tc-Czx Слике презентација Кристијана Жиже] (снимљене вежбе 2020)
* [[github:ksendzo/PP1-Projekat|Неки савети за израду пројекта]] (основа за водич за пројекат који је на викију)
* [https://docs.google.com/spreadsheets/d/1FhDa3-M4vlaFJOpblQJ_wJOiWLhIX1H6NKMOhdXCqE4/edit?gid=0#gid=0 Google tabela] листинг свих пронађених питања с рокова (последње ажурирано јануара 2024.) уз лабелирање по областима

== Настава ==
Области се на следећи начин обрађују по блоковима:
* '''Први блок:'''
** лексичка анализа (коначни аутомати, минимизација аутомата, конверзија из недетерминистичког у детерминистички, конверзија регуларног израза у ДКА, лексички процесори),
** генератори лексичких анализатора (''JFlex''),
** синтаксна анализа (увод у граматике и језике),
** потисни аутомати
* '''Други блок:'''
** парсирање од дна ка врху (LR(0) парсери, SLR(1) парсери, LALR(1) парсери, опоравак од грешака),
** генератори парсера (''CUP''),
** парсирање од врха ка дну (LL(1) граматике, трансформација у LL(1), конструкција парсера по принципу рекурзивног спуста),
** атрибутивно-транслационе граматике (S-атрибутивне и L-атрибутивне граматике)
** апстрактна синтаксна стабла (''AST-CUP'')
* '''Трећи блок:'''
** табела симбола (конкретна реализација на пројекту, различите могуће организације, случај вишеструког наслеђивања),
** Микројава виртуелна машина (меморијски сегменти, инструкције, превођење израза, превођење контролних структура, превођење позива метода, наслеђивање и виртуелни механизам),
** генерисање међукода (четворке, тројке, граф тока контроле, SSA форма),
** извршно окружење (контролне и приступне везе, дисплеји, стабла активације),
** генерисање x86 кода (животни век променљивих, ''getreg'' алгоритам)
Градиво које се обрађује искључиво на предавањима укључује моделовање коначних аутомата у коду, S-атрибутивне и L-атрибутивне граматике, укључивање акција и атрибута у парсер конструисан по принципу рекурзивног спуста, апстрактна синтаксна стабла и вишеструко наслеђивање. Градиво из ''JFlex'', ''CUP'' и апстрактних синтаксних стабала, иако теоретски може да дође на колоквијумима, се јако ретко појављује. Градиво S-атрибутивних и L-атрибутивних граматика се чешће појављује на испиту него на колоквијуму.

Сви материјали са вежби и предавања могу се пронаћи на страници предмета, у несрећној комбинацији различитих формата (ZIP, RAR, DOC, PDF и PPT). Презентације Кристијана Жиже, чије су снимљене вежбе из 2020. године, нису доступне (обрисао их је када је одлазио са предмета), али су доступне слике тих презентација из одељка са [[#Корисне везе|корисним везама]]. На вежбама и предавањима се такође могу помињати збирка или уџбеник, оне су доступне са странице предмета (додуше тешко видљиве) и из одељка [[#Литература|са литературом]].

== Пројекат ==
Пројекат на предмету носи 40 бодова и обавезан је. Услов за излазак на испит је барем 20 бодова освојених на одбрани пројекта. Предаје се до дан или два пред одбрану, са мало ранијом иницијалном предајом ради формирања распореда (као на [[ОО1]] и [[ОО2]]). Пројекат је подељен на 3 нивоа, где ниво А носи 20, ниво Б 30 и ниво Ц 40 бодова (могуће је освојити и број бодова између уколико пројекат испуњава део захтева за виши ниво, или уколико модификација на одбрани само делимично ради). Обично за сваки ниво буде по један захтев специфичан за ту школску годину, али се ниво Б генерално разликује од нивоа А по томе што захтева имплементацију функција, а ниво Ц од нивоа Б по томе што захтева имплементацију класа. На крају израде пројекта тражи се и документ са извештајем о пројекту.

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

Од материјала за пројекат релевантне су вежбе из ''JFlex'', ''CUP'', табеле симбола и Микројава виртуелне машине. Поред тога, на страници предмета постоје снимци и изворни код једног студента који ради један мини-пројекат по фазама, који могу бити корисни као увод у алате за израду пројекта и примере имплементације одређених захтева. Већи део кода са тих снимака може се искористити ради имплементације захтева за ниво А на пројекту. На снимцима се као окружење за израду користи ''Eclipse'', али било које окружење инсталирано у рачунарским лабораторијама на факултету је прихватљиво. Такође је доступан '''[[Програмски преводиоци 1/Пројекат|водич за израду пројекта]].'''

Одбрана пројекта се организује неколико дана пре испита. На одбрани се прво раде модификације, затим асистенту или демонстратору покаже да модификација ради и потом брани основни пројекат. Одбрана основног пројекта обично није много детаљна, већ се покрену јавни тестови и види да ли раде (дају добар испис), евентуално откоментаришу неке линије које треба да изазову грешке. Том приликом се ретко тестира опоравак од синтаксних грешки и разне спецификације исписа прописане поставком. У извештај са пројекта се не улази. Структура пројекта која у поставци пише да је неопходна није заправо неопходна. Неке од модификација претходних година доступне су из одељка са [[#Корисне везе|корисним везама]].

Стари пројекти доступни су са странице предмета (године 2021/2022 су доступни на http://ir4pp1.etf.rs/Domaci/2021-2022, претходне године на http://ir4pp1.etf.rs/Domaci/2020-2021 и тако даље, али не постоји лако доступна листа домаћих на једном месту).

== Испитни рокови ==
Испитни рокови се понекад објављују [http://ir4pp1.etf.bg.ac.rs/Rokovi.html на страници предмета,] и понекад имају решења у виду сликаних вежбанки студената који су освојили максималан број бодова.

Рокови који су решени на викију су:
{{#dpl:
| category = Програмски преводиоци 1
| category = Рокови
| format = ,\n* [[%PAGE%|²{#invoke:String¦sub¦%PAGE%¦25¦-1}²]],
| ordermethod = title
| include = {nerešeno}.dpl, {delimično rešeno}.dpl, {нерешено}.dpl, {делимично решено}.dpl
}}

Уколико желите да додате рок, посетите '''[[Project:Направи#Стандард (латиница)|страницу за прављење рока]]'''.

=== По категоријама ===
Овде су задаци груписани по лабелама које ознаћавају тип или област задатка. Одласком на страницу лабеле можете видети све задатке тог типа који су решени (или барем преписани) на викију. Уколико желите да уређујете решења, то је потребно радити преко страница рокова излистаних изнад.

* [[Програмски преводиоци 1/Табела симбола|Табела симбола]]

== Литература ==
Постоји једна збирка задатака и један уџбеник из предмета, доступни са странице предмета:
* '''[http://ir4pp1.etf.rs/zbirka/ppzbirka.pdf "Збирка задатака из Програмских преводилаца 1"]''', Д.Велашевић, Д.Бојић, 2000 издавач: ''Електротехнички факултет Универзитета у Београду''
* '''[http://ir4pp1.etf.rs/Predavanja/pp1_udzbenik.pdf "Програмски преводиоци 1"]''', Д.Бојић, М.Вукасовић, 2022 (верзија 0.9)
На збирку се обично позива из материјала са вежби. Уџбеник опширно покрива градиво са предавања, али како још увек није дошао до стабилне верзије уме имати чудне језичке конструкте (налик онима из првог пасуса овог чланка) који га чине неоптималним за спремање испита.

== Начин оцењивања ==
=== СИ ===
* <math>K_1</math>, <math>K_2</math> — бодови са првог и другог колоквијума који се одржавају у првој и другој колоквијумској недељи и надокнађују се преко бодова са испита (0-20)
* <math>D</math> — бодови са пројекта (0-40)
* <math>I</math> — бодови са испита (0-60)
* Бодови са испита/колоквијума: <math>P_1 = max\left(\frac{1}{3} I + K_1 + K_2, \frac{2}{3} I + K_1, \frac{2}{3} I + K_2, I\right)</math>
* Бодови: <math>P = P_1 + D</math>
* Услов: <math>D \geq 20</math>, <math>P_1 \geq 31</math>


{| class="wikitable"
! Бодови
| <math>P \leq 51</math> || <math>50 || <math>60 || <math>70 || <math>80 || <math>91 < P</math>
|-
! Оцена
| 5 || 6 || 7 || 8 || 9 || 10
|}

=== РТИ ===
Како на РТИ има само један колоквијум од 30 бодова, коначни бодови се рачунају по формули: <math>P = D + max\left(\frac{1}{2} I + K, I\right)</math>.

== Потребна помоћ ==
* {{задаци|postavke}}
* {{задаци|rešenja}}
*: Рокови који су преписани а нису решени су: {{рокови|нерешени}}
*: Рокови којима недостаје понеко решење су: {{рокови|делимично решени}}

Програмски преводиоци 1/Табела симбола

2026-03-14T23:09:06Z

Andrija: Нова страница: {{tocright}} '''Табела симбола'''. {{Ознака задатка|Табела симбола}} Категорија:Програмски преводиоци 1

{{tocright}}
'''Табела симбола'''.
{{Ознака задатка|Табела симбола}}
[[Категорија:Програмски преводиоци 1]]

Програмски преводиоци 1/Јануар 2022

2026-03-14T23:07:00Z

Andrija: dodat tag

{{tocright}}
'''Ispit u januarskom roku 2022. godine''' održan je 28. januara. Postavka roka je dostupna [http://ir4pp1.etf.rs/Rokovi/2021-2022/pp1-januar-2021-22.pdf sa stranice predmeta.]

== 1. zadatak ==
{{delimično rešeno}}
=== Postavka ===
Odrediti minimalni konačni deterministički automat koji prihvata one i samo one ulazne sekvence koje NE prihvata konačni automat sa slike ali kada se čitaju sa desna u levo. Na primer, dati automat ne prihvata sekvencu ab, to znači da traženi automat treba da prihvati sekvencu ba. Postupak izložiti po koracima, na generalan način koji bi se mogao primeniti i na svaki drugi automat.
{| class="wikitable"
! Stanje !! a !! b !! Prihvata
|-
| → A || B || || 0
|-
| B || C || D || 0
|-
| C || || || 1
|-
| D || || F || 0
|-
| F || F || F || 1
|}

=== Rešenje ===
Prvi korak je da dodamo eksplictno stanje greške i da ga dodamo u prazna polja. 
Drugi korak je da izračunamo skup prethodnika za sva stanja (na grafu bi to bilo obrtanje strellica). 
Treći korak je konstruišemo DKA sa ovim novim funkcijama prelaza, gde će nam početno stanje biti stanja prihvatanja originalnog automata,
a stanje prihvatanja početno stanje originalnog automata.

S0 = {B, F} 
δ(S0, a) = {B}∪{F} = S1 = {B,F} 
δ(S0, a) = ∅ ∪ {D,F} = S2={D,F} 
Analogno ćemo ovo uraditi za svako stanje. 
Svako stanje koje u sebi sadrži u sebi početno stanje originalnog automata je stanje prihvatanja.
I na kraju da bi dobili odgovarajući automat radimo komplement tj. obrnemo stanja prihvatanja.

Traženi automat:

{| class="wikitable"
! Stanje !! a !! b !! Prihvata
|-
| → S0={C,F} || S1 || S2 || 1
|-
| S1={B,F} || S5 || S2 || 1
|-
| S2={D,F} || S3 || S4 || 1
|-
| S3={F} || S3 || S2 || 1
|-
| S4={B,D,F} || S5 || S4 || 1
|-
| S5={A,F} || S3 || S2 || 0
|}

== 2. zadatak ==
=== Postavka ===
<div class="abc-list">
# Za smene 1 i 2 date gramatike navesti koje atribute treba računati i od kojih drugih atributa oni mogu da zavise da bi cela gramatika bila L-atributivna. Pravila navoditi u obliku aa = f(bb, cc, dd,..) gde je aa atribut koji mora da se računa, dok su bb, cc, dd, itd svi drugi atributi od kojih posmatrani može da zavisi. Neterminal <S> ima sintetizovan atribut.
# Navesti pseudokod za proceduru A u parseru na bazi rekurzivnog spusta. Ostale delove parsera ne navoditi. Preimenovati promenljive da se minimizuje broj pravila kopiranja vrednosti atributa.
</div>
# <S>x → ay <A>z,v,w <S>p {bq}
# <S>x1 → dy1 {cz1} <A>v1, w1, p1
# <A>x,y,z1 → aq {cv} <A>x1,z,u <A>u,t,y1
## <math>v \larr x - q</math>
## <math>x_1 \larr x</math>
## <math>y \larr y_1</math>
## <math>z_1 \larr z</math>
# <A>t,s,s1 → dq {bt1} as2
## <math>t_1 \larr t</math>
## <math>(s,s_1) \larr s_2</math>

=== Rešenje ===
Iz date gramatike možemo zaključiti sledeće o tipovima atributa:
* Akcije <code>b</code> i <code>c</code> sadrže nasleđene atribute.
* Neterminal <code><A></code> sadrži tri atributa, od kojih je prvi nasleđen a druga dva sintetizovana.
Na osnovu toga, u prvoj smeni vidimo da atributi mogu imati sledeće vrednosti:
* <math>x = f(y, z, v, w, p, q)</math>
* <math>z = f(y)</math>
* <math>q = f(y, z, v, w, p)</math>
a u drugoj smeni sledeće:
* <math>x1 = f(y_1, z_1, v_1, w_1, p_1)</math>
* <math>z1 = f(y_1)</math>
* <math>v1 = f(y_1, z_1)</math>
Kod parsera sa adekvatno preimenovanim atributima dat je ispod:
<syntaxhighlight lang="cpp">
void A(int x, int& y, int& z) {
switch (input) {
case 'a':
input = advance();
int q = getInputValue();
out('c', x - q);
int u;
A(x, z, u);
int t;
A(u, t, y);
break;
case 'd':
input = advance();
out('b', x);
input = advance();
y = z = getInputValue();
break;
}
}
</syntaxhighlight>

== 3. zadatak ==
=== Postavka ===
Zadata je gramatika
# <S> → <S> b <A>
# <S> → <A> a b
# <A> → c d
# <A> → ε
# → ε
<div class="abc-list">
# Konstruisati karaketristični[sic] automat LR(0) parsera kao i odgovarajuću kontrolnu tabelu. Da li ima konflikata?
# Konstruisati kontrolnu tabelu SLR(1) parsera. Da li ima konflikata?
</div>

=== Rešenje ===
[[Датотека:PPR januar 2022 zadatak 3 automat.svg|thumb|Karakteristični LR(0) automat u trećem zadatku.]]
{| class="wikitable"
|+ Kontrolna tabela LR(0) parsera
! Stanje !! Akcija
|-
| <S'>0 || '''R/R konflikt'''
|-
| <A>2 || SHIFT
|-
| 31 || SHIFT
|-
| <S>x || SHIFT
|-
| c3 || REDUCE(5)
|-
| 32 || SHIFT
|-
| d3 || REDUCE(3)
|-
| a2 || REDUCE(5)
|-
| 2 || SHIFT
|-
| b2 || REDUCE(2)
|-
| ─┤0 || ACCEPT
|-
| b1 || '''R/R konflikt'''
|-
| <A>1 || REDUCE(1)
|}
FOLLOW skupovi su sledeći:
* FOLLOW(<S>) = {─┤, b}
* FOLLOW() = {b, c, d}
* FOLLOW(<A>) = {a} ∪ FOLLOW(<S>) = {─┤, a, b}
{| class="wikitable"
|+ Kontrolna tabela SLR(0) parsera
! Stanje !! a !! b !! c !! d !! ─┤
|-
| <S'>0 || REDUCE(4) || '''R/R konflikt''' || REDUCE(5) || REDUCE(5) || REDUCE(4)
|-
| <A>2 || SHIFT || || || ||
|-
| 31 || || || SHIFT || ||
|-
| <S>x || || SHIFT || || || SHIFT
|-
| c3 || || REDUCE(5) || REDUCE(5) || REDUCE(5) ||
|-
| 32 || || || || SHIFT ||
|-
| d3 || REDUCE(3) || REDUCE(3) || || || REDUCE(3)
|-
| a2 || || REDUCE(5) || REDUCE(5) || REDUCE(5) ||
|-
| 2 || || SHIFT || || ||
|-
| b2 || || REDUCE(2) || || || REDUCE(2)
|-
| ─┤0 || || || || || ACCEPT
|-
| b1 || REDUCE(4) || '''R/R konflikt''' || REDUCE(5) || REDUCE(5) || REDUCE(4)
|-
| <A>1 || || REDUCE(1) || || || REDUCE(1)
|}

== 4. zadatak ==
=== Postavka ===
Dat je listing programa Januar2022, napisan na programskom jeziku Mikrojava. Sve metode unutrašnjih klasa su virtuelne. Globalne metode se pozivaju statički. Napisati kompletan Mikrojava bajtkod prevoda funkcije <code>f</code> za dati program
<syntaxhighlight lang="java">
program Januar2022
const int K = 2;
int add;
class A {
int fld;
{
int m(int a)
{ return fld * 2; }
void met()
{ fld = fld + 3; }
} }
class B extends A {
{
int m(int b)
{ /*T1*/
return fld + b;
}
}
}
A arr[];
{
int f(int index){
add = arr[index].m(K);
arr[index].met();
return add + K;
}
void main()
B b;
int ret;
{
/*T2*/
arr = new A[2];
arr[0] = new B;
arr[1] = new A;
ret = f(0) + f(1);
print(arr[0].m(ret));
}
}
</syntaxhighlight>

=== Rešenje ===
<pre>
enter 1, 1
getstatic 1
load_0
aload
const_2
getstatic 1
load_0
aload
getfield 0
invokevirtual 'm' -1
putstatic 0
getstatic 1
load_0
aload
dup
getfield 0
invokevirtual 'm' 'e' 't' -1
getstatic 0
const_2
add
exit
return
</pre>

== 5. zadatak ==
{{ознака|5. zadatak|Табела симбола}}
=== Postavka ===
Prikazati izgled tabele simbola u trenucima T1 i T2 na osnovu izvornog koda iz zadatka 4 prema formatu čvorova tabele simbola iz priloga. Universe opseg ne treba crtati. Za T2 dovoljno je naznačiti izmene u odnosu na prethodno stanje tabele.

=== Rešenje ===
<gallery widths="500" heights="500" class="transparent-svg">
PPR januar 2022 zadatak 5 T1.svg | Tabela simbola u stanju T1.
PPR januar 2022 zadatak 5 T2.svg | Tabela simbola u stanju T2.
</gallery>

== 6. zadatak ==
=== Postavka ===
Za dati programski fragment napisati odgovarajući međukod u SSA formi i nacrtati graf toka kontrole na nivou osnovnih blokova.
<syntaxhighlight lang="c">
a = 1;
b = 2;
c = 3;
for (a = 4; b < c || a < 10; a++) {
if (a > b + c) {
c++;
break;
} else if (a > b * c) {
b--;
continue;
}
else return a;
}
a = b * c;
return a;
</syntaxhighlight>

=== Rešenje ===
[[Датотека:PPR januar 2022 zadatak 6 graf.svg|thumb|Karakteristični LR(0) automat u trećem zadatku.]]
# a1 := 1
# b1 := 2
# c1 := 3
# a2 := 4
# t1 := Ф(b1, b2)
# if t1 < c1 goto 8
# if a2 >= 10 goto 17
# t2 := t1 + c1
# if a <= t2 goto 12
# c2 := c1 + 1
# goto 17
# t3 := t1 * c1
# if a <= t3 goto 16
# b2 := t1 - 1
# goto 5
# return a2
# t4 := Ф(b1, b2)
# t5 := Ф(c1, c2)
# t6 := t1 * t2
# a3 := t6
# return a3

[[Категорија:Рокови]]
[[Категорија:Програмски преводиоци 1]]

Шаблон:Ознака задатка

2026-03-14T23:00:44Z

Andrija:

<includeonly>{{#dpl:
| uses = Шаблон:Ознака
| category = {{ROOTPAGENAME}}
| category = Рокови
| include = {ознака}.dpl
| format = ,²{#ifeq:{{{1|{{SUBPAGENAME}}}}}¦,}²\n,
| secseparators = ,\n}²²{#ifeq:{{{1|{{SUBPAGENAME}}}}}¦,}²\n²{#ifeq:{{{1|{{SUBPAGENAME}}}}}¦,}²\n²{#ifeq:{{{1|{{SUBPAGENAME}}}}}¦,}²\n²{#ifeq:{{{1|{{SUBPAGENAME}}}}}¦,}²\n²{#ifeq:{{{1|{{SUBPAGENAME}}}}}¦,}²\n²{#ifeq:{{{1|{{SUBPAGENAME}}}}}¦,}²\n²{#ifeq:{{{1|{{SUBPAGENAME}}}}}¦,}²\n²{#ifeq:{{{1|{{SUBPAGENAME}}}}}¦,\n}²\n²{#ifeq:{{{1|{{SUBPAGENAME}}}}}¦
| ordermethod = title
}}</includeonly><noinclude><templatedata>
{
"params": {
"1": {
"description": "Назив ознаке чији задаци се приказују.",
"type": "string",
"label": "Ознака",
"example": "C-Linda",
"default": "Исто као назив подстранице на којој се шаблон позива.",
"autovalue": "{{SUBPAGENAME}}",
"suggested": true
}
},
"description": "Шаблон за исписивање задатака који садрже неку ознаку.",
"paramOrder": [
"1"
],
"format": "inline"
}
</templatedata>[[Категорија:Шаблони]]</noinclude>

Шаблон:Ознака.dpl

2026-03-14T22:59:09Z

Andrija:

<includeonly>{{{2}}}|
== {{#invoke:String|replace|{{{%TITLE%}}}|^[^/]+/(.*)|%1|1|false}}, {{{1}}} ==
<div style="display: none;">Debug: {{{%TITLE%}}} {{{1}}}</div>
{{#dpl:|title = {{{%TITLE%}}}|include = ##.*{{{1}}}.*|format = ,²{#dplreplace:,¦/\[\[Категорија:.*?\x5d\x5d/¦}²,}}
</includeonly><noinclude>
<templatedata>
{
"params": {
"1": {
"label": "Одељак",
"description": "Наслов одељка са задатком.",
"example": "3. задатак",
"type": "string",
"required": true
},
"2": {
"label": "Ознака",
"description": "Назив ознаке задатка.",
"example": "Семафори",
"type": "string",
"required": true
},
"%TITLE%": {
"label": "Наслов странице",
"description": "Наслов странице на којој се налази задатак. Овај параметар се прослеђује аутоматски од стране DPL.",
"example": "КДП/Јун 2020",
"type": "wiki-page-name",
"required": true
}
},
"description": "Верзија [[Шаблон:Ознака]] за приказивање преко DPL.",
"paramOrder": [
"1",
"2",
"%TITLE%"
]
}
</templatedata>[[Категорија:Шаблони]]</noinclude>

Шаблон:Ознака

2026-03-14T22:57:35Z

Andrija:

<includeonly></includeonly><noinclude><templatedata>
{
"params": {
"1": {
"description": "Назив одељка на страници на којој се задатак налази.",
"type": "string",
"required": true,
"label": "Одељак",
"example": "3. задатак"
},
"2": {
"description": "Назив ознаке која се додељује задатку.",
"type": "string",
"required": true,
"label": "Ознака",
"example": "C-Linda"
}
},
"description": "Шаблон за категорисање задатка. За верзију која се приказује ради укључивања преко DPL, видети [[Шаблон:Ознака.dpl]].",
"paramOrder": [
"1",
"2"
],
"format": "inline"
}
</templatedata>[[Категорија:Шаблони]]</noinclude>

Шаблон:Ознака задатка

2026-03-14T21:12:39Z

Andrija: Направљена празна страница

Шаблон:Ознака.dpl

2026-03-14T21:12:31Z

Andrija: Направљена празна страница

Шаблон:Ознака

2026-03-14T21:11:42Z

Andrija: Направљена празна страница

Микропроцесорски системи/Јул 2022

2025-10-25T17:09:15Z

Andrija: Dopuna postavci zadatka

{{tocright}}
'''Јулски испит 2022. године''' одржан је 10. јула и на њему је била доступна сва потребна документација и презентације са предавања. Поставка рока није доступна са странице предмета.
{{решења}}

== Теорија ==
=== 1. задатак ===
На којој адреси се налази машинска инструкција коју микропроцесор ''Cortex-M3'' прву извршава након ресета?
<div class="abc-list" data-solution="single">
# 0x00000004
# mem[0x00000004]
# Ниједна од понуђених
# mem[0x08000004]
# 0x08000004
</div>
'''Објашњење:''' У ''Cortex-M3 Programming Manual'' пише на страни 15 како се у програмски бројач уписује вредност са адресе 0x00000004, тако да се прва инструкција извршава са адресе која пише на тој локацији у меморији.

=== 2. задатак ===
Која вредност се налази у регистру ''R1'' након извршавања дате секвенце асемблерских инструкција? Одговор унети према формату неозначених хексадецималних литерала у ''C'' програмском језику ширине 32 бита.
<syntaxhighlight lang="asm">
mov r0, 3
mov r1, 8
cmp r1, r0
itttt gt
subgt r1, r1, r0
subgt r1, r1, 8
subsgt r1, r1, r0
subsgt r1, r1, 5
</syntaxhighlight>
Приказ очекиваног формата одговора за произвољно одабрану вредност 1 јесте:
0x00000001
'''Одговор:''' 0xFFFFFFFA

'''Објашњење:''' На почетку програма регистру ''R0'' додељује се вредност 3, а регистру ''R1'' вредност 8. Затим се та два регистра упоређују, па се прелази на извршавање инструкција које зависе од тога да ли је један број био већи од другог. Пошто јесте, прва инструкција <code>subgt</code> мења ''R1'' на 5, а друга на -3. Пошто друга инструкција није имала суфикс <code>s</code>, програмски статусни регистар се није ажурирао, па се наставља на извршавање инструкције <code>subsgt</code>, након које ''R1'' има вредност -6, а програмска статусна реч се ажурира тако да се последња инструкција не извршава. Релевантна страница у ''Cortex-M3 Programming Manual'' је 56 (3.3.7 ''Conditional execution'').

=== 3. задатак ===
Колика је максимална радна фреквенција (''HCLK'') микроконтролера ''STM32F103R6'' уколико се користи ''HSE'' осцилатор који на свом излазу производи сигнал такта фреквенције 2MHz? Одговор унети у мегахерцима без навођења ознаке јединице.

'''Одговор:''' 32

'''Објашњење:''' На слици са стране 93 од ''STM32F103 Reference Manual'' може се видети како ''HSE'' такт може проћи кроз PLL који може да његову фреквенцију помножи до 16 пута.

=== 4. задатак ===
: ''Исти задатак као са [[Микропроцесорски системи/К2 2022#3. задатак|другог колоквијума 2022. године]].''

=== 5. задатак ===
Периферија ''USART'' микроконтролера ''STM32F103R6'' конфигурисана је тако да преноси осам (8) битова, користи парну парност и поставља један стоп бит. Са линије за пренос узорковани су следећи битови (сваки бит је добијен на основу одговарајућег броја узорака стања на линији):
...111111011011010000011111111...
Које грешке постоје приликом пријема?
<div class="abc-list" data-solution="single">
# Нема грешака
# Само ''Framing error''
# ''Framing error'' и ''Parity error''
# Само ''Parity error''
</div>
'''Објашњење:''' Док на жици нема пакета, стоји вредност 1. Наилазимо на почетни бит 0, а након њега долази осам битова од којих осми представља бит парности. Сабирањем тих осам битова добијамо број 5, што је непаран број а парност је парна, па се дешава ''Parity error''. Након тих осам битова наилази бит са вредношћу 0, а очекује се завршни бит са вредношћу 1, тако да се такође дешава и ''Framing error''.

== Задатак ==
=== Поставка ===
[[Датотека:MIPS jul 2022 referentna šema.jpeg|thumb|Референтна шема у задатку.]]
# <del>У систему постоји један микроконтролер који контролише вентилатор у складу са тренутном вредношћу температуре. У симулатору ''Proteus'' направити пројекат и инстанцирати микроконтролер ''STM32F103R6 (CM3_STM32)''. Направити пројекат у алату ''CubeMX'' који ће служити за конфигурисање микроконтролера.</del>
# <del>У симулатору ''Proteus'' додати следеће компоненте</del> строго према датој референтној шеми:
#* <del>електромотор ''MOTOR (MOTORS)'' који представља вентилатор и чија ће брзина рада бити контролисана</del> ''PWM'' сигналом канала 4 тајмера 1 <del>микроконтролера</del>,
#* аналогни мултиплексер ''74HC4051 (74HC)'', који један од аналогних сигнала са улаза пропушта непромењен на излаз, чији је излазни пин повезан на канал 7 аналогно-дигиталног конвертора микроконтролера; селекција излаза мултиплексера се врши преко његових пинова ''CBA'' где пин ''A'' има најмању тежину,
#* <del>температурни сензор ''LM35 (NATDAC)'' чији је излазни пин повезан</del> на нулти улаз (''X0'') мултиплексера <del>(аналогна вредност напона на излазном пину сензора је линеарно пропорционална вредности температуре)</del>,
#* анемометар ''ANEMOMETER (ACTIVE)'' повезан у складу са референтном шемом на канале 1 и 2 тајмера 1; излазни сигнал анемометра је периодична правоугаона поворка чија се фреквенција линеарно повећава са повећањем брзине ветра (брзина ветра једнака је производу фреквенције излазног сигнала анемометра и реалне константе 2.4),
#* ветроказ ''WINDVANE (ACTIVE)'' чији је излазни пин повезан у складу са референтном шемом (обратити пажњу на постојање отпорника) на први улаз (X1) мултиплексера; аналогна вредност напона на излазном пину ветроказа представља азимут односно правац ветра (функција за пресликавање вредности напона у азимут дата је у прилогу),
#* кишомер ''RAINGAUGE (ACTIVE)'' повезан у складу са референтном шемом на моностабилни мултивибратор ''74HC221 (74HC)''; кишомер ради по принципу кофе са превртањем (кофа се пуни кишницом све док се не препуни, затим долази до њеног превртања и потпуног пражњења уз генерисање електричног импулса); моностабилни мултивибратор обезбеђује униформно трајање генерисаног електричног импулса; подесити на кишомеру ниво превртања кофе (''Trigger Level'') на вредност 0.01 милиметара услед чега ће кофа слати електрични импулс на сваких 1200 милисекунди при константном интензитету падавине од 30.0 милиметара по сат (за већи интензитет падавине импулс ће стизати брже и обрнуто); подесити на моностабилном мултивибратору временску константу (''Monostable Time Constant'') на једну милисекунду (1mS) услед чега ће сигнал на његовом излазу увек трајати тачно једну милисекунду,
#* <del>виртуелни терминал повезан на периферију ''USART1'' микроконтролера</del> преко пинова ''PB6'' и ''PB7'' <del>и,</del>
#* ''LCD'' дисплеј ''LM041L (DISPLAY)'' са четири линије, којима редом одговарају почетне адресе <code>0x80</code>, <code>0xC0</code>, <code>0x90</code> и <code>0xD0</code> у ''DDRAM'' меморији контролера ''HD44780'', <del>повезан на пинове ''PC0''-''PC6'' микроконтролера</del>.
# [6 поена] Обезбедити могућност рада са LCD дисплејом и формирати карактере за LCD дисплеј који представљају стрелицу на горе (↑) и стрелицу на доле (↓) у складу са референтним снимком. Ови карактери користиће се као индикатори да ли се нека вредност повећала или смањила приликом њене последње промене.
# <del>Обезбедити приказ поруке '''''<nowiki>/A=<a>/B=/T=<t>/K=<k></nowiki>''''' на виртуелном терминалу, где је ''<nowiki><a></nowiki>'' тренутна вредност азимута ветра, ''<nowiki></nowiki>'' тренутна вредност брзине ветра, ''<nowiki><t></nowiki>'' тренутна вредност температуре изражено у степенима Целзијуса у опсегу [0, 60] и ''<nowiki><k></nowiki>'' тренутна вредност интезитета падавине.</del> Овај испис је предвиђен само ради могућности остваривања парцијалних поена за студенте који успешно очитају вредност са компоненте али не могу да је прикажу на ''LCD'' дисплеју као што је тражено у наредним ставкама. <del>За величине чије вредности нису успешно израчунате исписати ? (знак питања). Освежавање описане поруке вршити периодично на сваких 200 милисекунди уколико је дошло до промене вредности. Приликом освежавања поруке променити тренутне вредности у постојећој поруци уместо додавања нове поруке на виртуелном терминалу.</del>
# <del>Обезбедити приказ поруке '''''<nowiki> Tem: <t></nowiki>''''' у трећем реду ''LCD'' дисплеја, где ''<nowiki><t></nowiki>'' представља тренутну вредност температуре изражено у степенима Целзијуса у опсегу [0, 60] очитану са температурног сензора, а ''<nowiki></nowiki>'' индикатор смера последње промене вредности у виду стрелице. Освежавање поруке вршити периодично на сваких 200 милисекунди уколико је дошло до промене вредности.</del> Овај испис је предвиђен ради остваривања поена за студенте који успешно обезбеде могућност рада са ''LCD'' дисплејом.
# [6 поена] Обезбедити приказ поруке '''''<nowiki> Brz: </nowiki>''''' у другом реду ''LCD'' дисплеја, где ''<nowiki></nowiki>'' представља тренутну вредност брзине ветра очитану са анемометра, а ''<nowiki></nowiki>'' индикатор смера последње промене вредности у виду стрелице. Освежавање поруке вршити периодично на сваких 200 милисекунди уколико је дошло до промене вредности.
# [6 поена] Обезбедити приказ поруке '''''<nowiki> Azi: <a></nowiki>''''' у првом реду ''LCD'' дисплеја, где ''<nowiki><a></nowiki>'' представља тренутну вредност азимута ветра очитану са ветроказа, а ''<nowiki></nowiki>'' индикатор смера последње промене вредности у виду стрелице. Освежавање поруке вршити периодично на сваких 200 милисекунди уколико је дошло до промене вредности.
# [6 поена] Обезбедити приказ поруке '''''<nowiki> Kis: <k></nowiki>''''' у четвртом реду ''LCD'' дисплеја, где ''<nowiki><k></nowiki>'' представља тренутну вредност интензитета падавине изражено у милиметрима по сату очитану са кишомера, а ''<nowiki></nowiki>'' индикатор смера последње промене вредности у виду стрелице. Освежавање поруке вршити периодично на сваких 200 милисекунди уколико је дошло до промене вредности.
# [6 поена] Обезбедити контролу вентилатора на начин описан у наставку. Зависно од тренутне вредности температуре вентилатор се врти одговарајућом брзином. Уколико тренутна вредност температуре припада опсегу:
#* [0, 30) вентилатор се не врти,
#* [30, 35) вентилатор се врти брзином једнаком 50% максималне брзине и
#* [35, 60] вентилатор се врти максималном брзином.
#:Ажурирање брзине вентилатора вршити периодично на 200 милисекунди.

На року је поред текста задатка и референтне шеме био доступан и референтни снимак (изглед симулације урађеног задатка), као и фајл <code>voltage2WindBearing.c</code> у коме је дефинисана помоћна функција <syntaxhighlight lang="c" inline>static float voltage2WindBearing(float voltage)</syntaxhighlight>. Целокупна поставка задатка може се преузети [[Медиј:MIPS jul 2022 postavka.zip|овде]].

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

Датотека:MIPS jul 2022 postavka.zip

2025-10-25T17:03:07Z

Andrija: Нова страница: {{file | description = }}

Микропроцесорски системи/Јул 2022

2025-10-25T16:41:56Z

Andrija: Dodata postavka prakticnog dela (zadatka)

{{tocright}}
'''Јулски испит 2022. године''' одржан је 10. јула и на њему је била доступна сва потребна документација и презентације са предавања. Поставка рока није доступна са странице предмета.
{{решења}}

== Теорија ==
=== 1. задатак ===
На којој адреси се налази машинска инструкција коју микропроцесор ''Cortex-M3'' прву извршава након ресета?
<div class="abc-list" data-solution="single">
# 0x00000004
# mem[0x00000004]
# Ниједна од понуђених
# mem[0x08000004]
# 0x08000004
</div>
'''Објашњење:''' У ''Cortex-M3 Programming Manual'' пише на страни 15 како се у програмски бројач уписује вредност са адресе 0x00000004, тако да се прва инструкција извршава са адресе која пише на тој локацији у меморији.

=== 2. задатак ===
Која вредност се налази у регистру ''R1'' након извршавања дате секвенце асемблерских инструкција? Одговор унети према формату неозначених хексадецималних литерала у ''C'' програмском језику ширине 32 бита.
<syntaxhighlight lang="asm">
mov r0, 3
mov r1, 8
cmp r1, r0
itttt gt
subgt r1, r1, r0
subgt r1, r1, 8
subsgt r1, r1, r0
subsgt r1, r1, 5
</syntaxhighlight>
Приказ очекиваног формата одговора за произвољно одабрану вредност 1 јесте:
0x00000001
'''Одговор:''' 0xFFFFFFFA

'''Објашњење:''' На почетку програма регистру ''R0'' додељује се вредност 3, а регистру ''R1'' вредност 8. Затим се та два регистра упоређују, па се прелази на извршавање инструкција које зависе од тога да ли је један број био већи од другог. Пошто јесте, прва инструкција <code>subgt</code> мења ''R1'' на 5, а друга на -3. Пошто друга инструкција није имала суфикс <code>s</code>, програмски статусни регистар се није ажурирао, па се наставља на извршавање инструкције <code>subsgt</code>, након које ''R1'' има вредност -6, а програмска статусна реч се ажурира тако да се последња инструкција не извршава. Релевантна страница у ''Cortex-M3 Programming Manual'' је 56 (3.3.7 ''Conditional execution'').

=== 3. задатак ===
Колика је максимална радна фреквенција (''HCLK'') микроконтролера ''STM32F103R6'' уколико се користи ''HSE'' осцилатор који на свом излазу производи сигнал такта фреквенције 2MHz? Одговор унети у мегахерцима без навођења ознаке јединице.

'''Одговор:''' 32

'''Објашњење:''' На слици са стране 93 од ''STM32F103 Reference Manual'' може се видети како ''HSE'' такт може проћи кроз PLL који може да његову фреквенцију помножи до 16 пута.

=== 4. задатак ===
: ''Исти задатак као са [[Микропроцесорски системи/К2 2022#3. задатак|другог колоквијума 2022. године]].''

=== 5. задатак ===
Периферија ''USART'' микроконтролера ''STM32F103R6'' конфигурисана је тако да преноси осам (8) битова, користи парну парност и поставља један стоп бит. Са линије за пренос узорковани су следећи битови (сваки бит је добијен на основу одговарајућег броја узорака стања на линији):
...111111011011010000011111111...
Које грешке постоје приликом пријема?
<div class="abc-list" data-solution="single">
# Нема грешака
# Само ''Framing error''
# ''Framing error'' и ''Parity error''
# Само ''Parity error''
</div>
'''Објашњење:''' Док на жици нема пакета, стоји вредност 1. Наилазимо на почетни бит 0, а након њега долази осам битова од којих осми представља бит парности. Сабирањем тих осам битова добијамо број 5, што је непаран број а парност је парна, па се дешава ''Parity error''. Након тих осам битова наилази бит са вредношћу 0, а очекује се завршни бит са вредношћу 1, тако да се такође дешава и ''Framing error''.

== Задатак ==
=== Поставка ===
[[Датотека:MIPS jul 2022 referentna šema.jpeg|thumb|Референтна шема у задатку.]]
# <del>У систему постоји један микроконтролер који контролише вентилатор у складу са тренутном вредношћу температуре. У симулатору ''Proteus'' направити пројекат и инстанцирати микроконтролер ''STM32F103R6 (CM3_STM32)''. Направити пројекат у алату ''CubeMX'' који ће служити за конфигурисање микроконтролера.</del>
# <del>У симулатору ''Proteus'' додати следеће компоненте</del> строго према датој референтној шеми:
#* <del>електромотор ''MOTOR (MOTORS)'' који представља вентилатор и чија ће брзина рада бити контролисана</del> ''PWM'' сигналом канала 4 тајмера 1 <del>микроконтролера</del>,
#* аналогни мултиплексер ''74HC4051 (74HC)'', који један од аналогних сигнала са улаза пропушта непромењен на излаз, чији је излазни пин повезан на канал 7 аналогно-дигиталног конвертора микроконтролера; селекција излаза мултиплексера се врши преко његових пинова ''CBA'' где пин ''A'' има најмању тежину,
#* <del>температурни сензор ''LM35 (NATDAC)'' чији је излазни пин повезан</del> на нулти улаз (''X0'') мултиплексера <del>(аналогна вредност напона на излазном пину сензора је линеарно пропорционална вредности температуре)</del>,
#* анемометар ''ANEMOMETER (ACTIVE)'' повезан у складу са референтном шемом на канале 1 и 2 тајмера 1; излазни сигнал анемометра је периодична правоугаона поворка чија се фреквенција линеарно повећава са повећањем брзине ветра (брзина ветра једнака је производу фреквенције излазног сигнала анемометра и реалне константе 2.4),
#* ветроказ ''WINDVANE (ACTIVE)'' чији је излазни пин повезан у складу са референтном шемом (обратити пажњу на постојање отпорника) на први улаз (X1) мултиплексера; аналогна вредност напона на излазном пину ветроказа представља азимут односно правац ветра (функција за пресликавање вредности напона у азимут дата је у прилогу),
#* кишомер ''RAINGAUGE (ACTIVE)'' повезан у складу са референтном шемом на моностабилни мултивибратор ''74HC221 (74HC)''; кишомер ради по принципу кофе са превртањем (кофа се пуни кишницом све док се не препуни, затим долази до њеног превртања и потпуног пражњења уз генерисање електричног импулса); моностабилни мултивибратор обезбеђује униформно трајање генерисаног електричног импулса; подесити на кишомеру ниво превртања кофе (''Trigger Level'') на вредност 0.01 милиметара услед чега ће кофа слати електрични импулс на сваких 1200 милисекунди при константном интензитету падавине од 30.0 милиметара по сат (за већи интензитет падавине импулс ће стизати брже и обрнуто); подесити на моностабилном мултивибратору временску константу (''Monostable Time Constant'') на једну милисекунду (1mS) услед чега ће сигнал на његовом излазу увек трајати тачно једну милисекунду,
#* <del>виртуелни терминал повезан на периферију ''USART1'' микроконтролера</del> преко пинова ''PB6'' и ''PB7'' <del>и,</del>
#* ''LCD'' дисплеј ''LM041L (DISPLAY)'' са четири линије, којима редом одговарају почетне адресе <code>0x80</code>, <code>0xC0</code>, <code>0x90</code> и <code>0xD0</code> у ''DDRAM'' меморији контролера ''HD44780'', <del>повезан на пинове ''PC0''-''PC6'' микроконтролера</del>.
# [6 поена] Обезбедити могућност рада са LCD дисплејом и формирати карактере за LCD дисплеј који представљају стрелицу на горе (↑) и стрелицу на доле (↓) у складу са референтним снимком. Ови карактери користиће се као индикатори да ли се нека вредност повећала или смањила приликом њене последње промене.
# <del>Обезбедити приказ поруке '''''<nowiki>/A=<a>/B=/T=<t>/K=<k></nowiki>''''' на виртуелном терминалу, где је ''<nowiki><a></nowiki>'' тренутна вредност азимута ветра, ''<nowiki></nowiki>'' тренутна вредност брзине ветра, ''<nowiki><t></nowiki>'' тренутна вредност температуре изражено у степенима Целзијуса у опсегу [0, 60] и ''<nowiki><k></nowiki>'' тренутна вредност интезитета падавине.</del> Овај испис је предвиђен само ради могућности остваривања парцијалних поена за студенте који успешно очитају вредност са компоненте али не могу да је прикажу на ''LCD'' дисплеју као што је тражено у наредним ставкама. <del>За величине чије вредности нису успешно израчунате исписати ? (знак питања). Освежавање описане поруке вршити периодично на сваких 200 милисекунди уколико је дошло до промене вредности. Приликом освежавања поруке променити тренутне вредности у постојећој поруци уместо додавања нове поруке на виртуелном терминалу.</del>
# <del>Обезбедити приказ поруке '''''<nowiki> Tem: <t></nowiki>''''' у трећем реду ''LCD'' дисплеја, где ''<nowiki><t></nowiki>'' представља тренутну вредност температуре изражено у степенима Целзијуса у опсегу [0, 60] очитану са температурног сензора, а ''<nowiki></nowiki>'' индикатор смера последње промене вредности у виду стрелице. Освежавање поруке вршити периодично на сваких 200 милисекунди уколико је дошло до промене вредности.</del> Овај испис је предвиђен ради остваривања поена за студенте који успешно обезбеде могућност рада са ''LCD'' дисплејом.
# [6 поена] Обезбедити приказ поруке '''''<nowiki> Brz: </nowiki>''''' у другом реду ''LCD'' дисплеја, где ''<nowiki></nowiki>'' представља тренутну вредност брзине ветра очитану са анемометра, а ''<nowiki></nowiki>'' индикатор смера последње промене вредности у виду стрелице. Освежавање поруке вршити периодично на сваких 200 милисекунди уколико је дошло до промене вредности.
# [6 поена] Обезбедити приказ поруке '''''<nowiki> Azi: <a></nowiki>''''' у првом реду ''LCD'' дисплеја, где ''<nowiki><a></nowiki>'' представља тренутну вредност азимута ветра очитану са ветроказа, а ''<nowiki></nowiki>'' индикатор смера последње промене вредности у виду стрелице. Освежавање поруке вршити периодично на сваких 200 милисекунди уколико је дошло до промене вредности.
# [6 поена] Обезбедити приказ поруке '''''<nowiki> Kis: <k></nowiki>''''' у четвртом реду ''LCD'' дисплеја, где ''<nowiki><k></nowiki>'' представља тренутну вредност интензитета падавине изражено у милиметрима по сату очитану са кишомера, а ''<nowiki></nowiki>'' индикатор смера последње промене вредности у виду стрелице. Освежавање поруке вршити периодично на сваких 200 милисекунди уколико је дошло до промене вредности.
# [6 поена] Обезбедити контролу вентилатора на начин описан у наставку. Зависно од тренутне вредности температуре вентилатор се врти одговарајућом брзином. Уколико тренутна вредност температуре припада опсегу:
#* [0, 30) вентилатор се не врти,
#* [30, 35) вентилатор се врти брзином једнаком 50% максималне брзине и
#* [35, 60] вентилатор се врти максималном брзином.
#:Ажурирање брзине вентилатора вршити периодично на 200 милисекунди.

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

Датотека:MIPS jul 2022 referentna šema.jpeg

2025-10-25T16:36:39Z

Andrija: Нова страница: {{file | description = }}

Општи водичи

2025-10-23T07:26:07Z

Andrija: Napomena oko naknadne prijave ispita

{{tocright}}
Овде се налазе '''водичи''' који нису у вези ни са једним [[:Категорија:Предмети|предметом]].

== Поништавање испита ==
Испити се могу поништити најкасније дан пред испит, ако сте га пријавили за тај рок. Ако нисте, можете да поништите кад год. Испите које сте пали не поништавате. У најбољем случају можете питати професора да вам упише 5 како не бисте поништавали испит, али ово не функционише код свих професора (поготово оних са РТИ катедре).
# Пре поништавања испита потребно је да имате:
## Потврду о уплати накнаде за поништавање испита
## Молбу за поништавање испита (купује се у скриптарници, кошта 25 РСД)
## Закључану оцену (налази се у секцији ''Положени испити'') из предмета који хоћете да поништите на студентским сервисима.
# Потврда о уплати изгледа овако:
#* '''Сврха:''' Поништавање испита
#* '''Износ:''' 2.000,00 РСД
#* '''Рачун:''' 840-0000001438666-48 (СОП. ПРИ. ЕТФ Београд)
#* '''Модел и позив на број:''' 97 89100 (ЕР) или 97 77201 (СИ)
# Молбу попуњавате са именом и презименом, бројем индекса, одсеком, предметом и оценом коју поништавате, и испитним роком у којем сте добили оцену. Уз њу прилажете индекс и уплатницу (спадају под "остала документа").
# Молбу подносите у [https://www.etf.bg.ac.rs/sr/sluzbe/studentski-odsek студентској служби,] од 11 до 13 сати радним данима.

== Накнадна пријава испита ==
Испити се могу накнадно пријавити '''пре рока у којем се одржава тај испит'''. Процес:
# У случају да немате новац (3.000,00 РСД) на студентском рачуну, морате га уплатити. На е-студенту, у одсеку "Школарине и уплате" постоји пример уплатнице (износ мора бити 3.000,00 РСД или више а сврху уплате можете променити у "Накнадна пријава испита").
#* '''Препоручено је да се на рачун уплате паре најкасније два радна дана пред почетак рока (уколико рок почиње у понедељак, то је 4 дана пре почетка рока), јер је углавном потребан један дан да легну.''' У случају да вам је остао само један радни дан до почетка рока, '''морате однети доказ о уплати у студентску службу јер се новац неће прокњижити на време'''.
#* Имајте на уму да ако је у питању плаћена пријава испита (пријављиван више од три пута), треба уплатити '''и пријаву и накнадну пријаву''', тј. треба имати 5.000,00 РСД на рачуну.
# Ако имате новац на рачуну, пошаљите мејл на [mailto:stud_sluzba@etf.rs stud_sluzba@etf.rs] са захтевом да пријавите одређен испит. Испуниће вам молбу током радног времена, од 11-13.
# '''НЕ ПРЕПОРУЧУЈЕ СЕ''' да одете у [https://www.etf.bg.ac.rs/sr/sluzbe/studentski-odsek студентску службу] од 11-13 и ''лично'' питате, јер одлазак до студентске службе често може да буде непријатно искуство.

== Излазак из тима ==
''Microsoft Teams'' платформа прави излазак из тимова безразложно тешком операцијом. Уколико желите да напустите неки тим, потребно је следеће:
# Да имате ''Android'' уређај
# Деинсталирате ''Microsoft Teams'' апликацију уколико је имате инсталирану
# Инсталирате [https://studentetfbgacrs-my.sharepoint.com/:u:/g/personal/sa190595d_student_etf_bg_ac_rs/ET1FuXmFjjRDkeUwCu4qzmoB1k4Lrw3hnZYam3iJgHnC9g старију верзију апликације за ''Android''] (могуће је да ћете морати да у својим сигурносним подешавањима дозволите инсталацију апликација из непознатих извора)
# Пријавите се са студентским налогом
# На дну листе тимова изаберете опцију за преглед свих тимова
# На том екрану ћете у менију са десне стране сваког тима моћи да изаберете опцију за излазак из тима
# Можда ћете морати мало да сачекате да ''Teams'' региструје излазак из тима, а уколико ни након пола минута не уклони тим можете пробати опет

== Одјављивање са листе предмета ==
Након што завршите са неким предметом, можда вас више не занимају обавештења о њему. Бићете аутоматски одјављени са листе тог предмета кад се поново формирају листе тог истог предмета, али можете и се унапред одјавити са листа:
# Посетите [https://lists.etf.bg.ac.rs/ страницу за ЕТФ мејлинг листе]
# Уколико нисте раније правили налог на тој страници, [https://lists.etf.bg.ac.rs/wws/sendpasswd/ направите га.] Лозинка ће вам бити послата на мејл адресу
# Пријавите се са вашом студентском адресом е-поште и добијеном лозинком
# Изаберите у левој траци листу предмета са које хоћете да се одјавите
# Изаберите у левој траци "Unsubscribe"

[[Категорија:Водичи]]

Општи водичи

2025-10-21T00:18:58Z

Andrija: Korekcija cene za naknadnu prijavu ispita

{{tocright}}
Овде се налазе '''водичи''' који нису у вези ни са једним [[:Категорија:Предмети|предметом]].

== Поништавање испита ==
Испити се могу поништити најкасније дан пред испит, ако сте га пријавили за тај рок. Ако нисте, можете да поништите кад год. Испите које сте пали не поништавате. У најбољем случају можете питати професора да вам упише 5 како не бисте поништавали испит, али ово не функционише код свих професора (поготово оних са РТИ катедре).
# Пре поништавања испита потребно је да имате:
## Потврду о уплати накнаде за поништавање испита
## Молбу за поништавање испита (купује се у скриптарници, кошта 25 РСД)
## Закључану оцену (налази се у секцији ''Положени испити'') из предмета који хоћете да поништите на студентским сервисима.
# Потврда о уплати изгледа овако:
#* '''Сврха:''' Поништавање испита
#* '''Износ:''' 2.000,00 РСД
#* '''Рачун:''' 840-0000001438666-48 (СОП. ПРИ. ЕТФ Београд)
#* '''Модел и позив на број:''' 97 89100 (ЕР) или 97 77201 (СИ)
# Молбу попуњавате са именом и презименом, бројем индекса, одсеком, предметом и оценом коју поништавате, и испитним роком у којем сте добили оцену. Уз њу прилажете индекс и уплатницу (спадају под "остала документа").
# Молбу подносите у [https://www.etf.bg.ac.rs/sr/sluzbe/studentski-odsek студентској служби,] од 11 до 13 сати радним данима.

== Накнадна пријава испита ==
Испити се могу накнадно пријавити '''пре рока у којем се одржава тај испит'''. Процес:
# У случају да немате новац (3.000,00 РСД) на студентском рачуну, морате га уплатити. На е-студенту, у одсеку "Школарине и уплате" постоји пример уплатнице (износ мора бити 3.000,00 РСД или више а сврху уплате можете променити у "Накнадна пријава испита"). '''Препоручено је да се на рачун уплате паре најкасније два радна дана пред почетак рока (уколико рок почиње у понедељак, то је 4 дана пре почетка рока), јер је углавном потребан један дан да легну.''' У случају да вам је остао само један радни дан до почетка рока, '''морате однети доказ о уплати у студентску службу јер се новац неће прокњижити на време'''.
# Ако имате новац на рачуну, пошаљите мејл на [mailto:stud_sluzba@etf.rs stud_sluzba@etf.rs] са захтевом да пријавите одређен испит. Испуниће вам молбу током радног времена, од 11-13.
# '''НЕ ПРЕПОРУЧУЈЕ СЕ''' да одете у [https://www.etf.bg.ac.rs/sr/sluzbe/studentski-odsek студентску службу] од 11-13 и ''лично'' питате, јер одлазак до студентске службе често може да буде непријатно искуство.

== Излазак из тима ==
''Microsoft Teams'' платформа прави излазак из тимова безразложно тешком операцијом. Уколико желите да напустите неки тим, потребно је следеће:
# Да имате ''Android'' уређај
# Деинсталирате ''Microsoft Teams'' апликацију уколико је имате инсталирану
# Инсталирате [https://studentetfbgacrs-my.sharepoint.com/:u:/g/personal/sa190595d_student_etf_bg_ac_rs/ET1FuXmFjjRDkeUwCu4qzmoB1k4Lrw3hnZYam3iJgHnC9g старију верзију апликације за ''Android''] (могуће је да ћете морати да у својим сигурносним подешавањима дозволите инсталацију апликација из непознатих извора)
# Пријавите се са студентским налогом
# На дну листе тимова изаберете опцију за преглед свих тимова
# На том екрану ћете у менију са десне стране сваког тима моћи да изаберете опцију за излазак из тима
# Можда ћете морати мало да сачекате да ''Teams'' региструје излазак из тима, а уколико ни након пола минута не уклони тим можете пробати опет

== Одјављивање са листе предмета ==
Након што завршите са неким предметом, можда вас више не занимају обавештења о њему. Бићете аутоматски одјављени са листе тог предмета кад се поново формирају листе тог истог предмета, али можете и се унапред одјавити са листа:
# Посетите [https://lists.etf.bg.ac.rs/ страницу за ЕТФ мејлинг листе]
# Уколико нисте раније правили налог на тој страници, [https://lists.etf.bg.ac.rs/wws/sendpasswd/ направите га.] Лозинка ће вам бити послата на мејл адресу
# Пријавите се са вашом студентском адресом е-поште и добијеном лозинком
# Изаберите у левој траци листу предмета са које хоћете да се одјавите
# Изаберите у левој траци "Unsubscribe"

[[Категорија:Водичи]]

Програмски преводиоци 1/Септембар 2023

2025-10-13T23:47:32Z

Andrija: Link ka roku na stranici predmeta

{{tocright}}
'''Ispit u septembarskom roku 2023. godine''' održan je 16. Septembra. Postavka roka je dostupna sa [http://ir4pp1.etf.rs/Rokovi/2022-2023/pp1-2223-septembar.pdf stranice predmeta].

== 1. zadatak ==
=== Postavka ===
'''(10p)''' Dat je deo implementacije klase ''Node'' u programskom jeziku ''Java'', koja predstavlja čvor u sintaksnom stablu izgenerisanom za konstrukciju DKA korišćenjem metoda pozicije, gde su objašnjenja polja i metoda data u komentarima iznad njih (sva polja su inicijalizovana konstruktorom):
<syntaxhighlight lang="cpp">
public class Node {
private enum Type {
ASTERISK, // *
PLUS, // +
PERIOD, // .
OR, // |
SYMBOL, // s
EPSILON // ε
}
// left subtree of position node, null if leaf (symbol) node
private Node left;

// right subtree of position node, null if unary operation or leaf (symbol) node
private Node right;

// type of position node
private Type type;

// position of symbol in regex, only valid for leaf (symbol) nodes, otherwise set to -1
private int symbolPos;

// check whether the subsequence with the given node as root of the subtree can be empty
public boolean isNullable();

// find sert of leaf (symbol) node positions which could be at the beginning of
// subsequence with the given node as root of the subtree
public Set<Integer> firstPos();

// find set of leaf (symbol) node positions which could be at the end of
// subsequence with the given node as root of the subtree
public Set<Integer> lastPos();

// returns a union of the two parameters
public static Set<Integer> union(Set<Integer> first, Set<Integer> second);
}
</syntaxhighlight>
Potrebno je napisati implementaciju metoda <code>firstPos()</code> i <code>lastPos()</code>

=== 1a. zadatak ===
Identičan ovakav zadatak (za isti broj poena) se pojavio u Avgustu 2023, samo se tražila implementacija <code>isNullable()</code>.

=== Rešenje ===
<syntaxhighlight lang="java">
public Set<Integer> firstPos() {
Set<Integer> ret = new HashSet<Integer>();

switch (this.type) {
case 'SYMBOL':
ret.add(this.symbolPos);
break;

case 'ASTERISK':
return this.left.firstPos();

case 'OR':
for (Integer pos : this.left.firstPos()) {
ret.add(pos);
}
for (Integer pos : this.right.firstPos()) {
ret.add(pos);
}
break;

case 'PERIOD':
for (Integer pos : this.left.firstPos()) {
ret.add(pos);
}
if (this.left.isNullable()) {
for (Integer pos : this.right.firstPos()) {
ret.add(pos);
}
}
break;

default:
break;
}

return ret;
}

public Set<Integer> lastPos() {
Set<Integer> ret = new HashSet<Integer>();

switch (this.type) {
case 'SYMBOL':
ret.add(this.symbolPos);
break;

case 'ASTERISK':
return this.left.lastPos();

case 'OR':
for (Integer pos : this.left.lastPos()) {
ret.add(pos);
}
for (Integer pos : this.right.lastPos()) {
ret.add(pos);
}
break;

case 'PERIOD':
for (Integer pos : this.right.lastPos()) {
ret.add(pos);
}
if (this.right.isNullable()) {
for (Integer pos : this.left.lastPos()) {
ret.add(pos);
}
}
break;

default:
break;
}

return ret;
}

public boolean isNullable(){
switch(this.type){
case 'SYMBOL':
return false;

case 'EPSILON':
case 'ASTERISK':
return true;

case 'PERIOD':
return this.left.isNullable() && this.right.isNullable();

case 'OR':
return this.left.isNullable() || this.right.isNullable();

default: return false;
}

}
</syntaxhighlight>

== 2. zadatak ==
{{delimično rešeno}}
=== Postavka ===
'''(10p)''' Za rekurzivni spust koji opisuje navedenu gramatiku, koji su opisani ispod:
<div class="abc-list">
# Dopuniti delove rekurzivnog spusta obeleženih sa labelama PN (N označava labelu koja se može popuniti i može predstavljati jednu ili više linija koda), ukoliko je poznato da se sekvence ''aadddbb'', ''dd'' i ''ab'' prihvataju.
# Napisati LL(1) gramatiku opisanu rekurzivnim spustom.
</div>

<pre>
Glavni program:
IN = NEXTCHAR();
call PROCS;
if (INP<> '˧')
then REJECT;
else ACCEPT;
end if;
end;

procedure PROCS:
case IN of
'a': goto P1;
'd', 'b', '˧': goto P2;
default: REJECT;
end case;
P1: /* ... */
P2: /* ... */
end procedure;

procedure PROCA:
case IN of
'b', '˧': goto P3;
'd': goto P4;
default: REJECT;
end case;
P3: /* ... */
P4: /* ... */
end procedure;
</pre>

== 3. zadatak ==
{{delimično rešeno}}
=== Postavka ===
'''(10p)''' Za dati Mikrojava bajtkod:
<div class="abc-list">
# Navesti izlaz programa.
# Rekonstruisati izvorni Mikrojava kod na osnovu datog bajtkoda.
</div>
<pre>
0: enter 2 2
3: load_0
4: load_1
5: mul
6: jmp 3 (=9)
9: exit
10: return
11: enter 2 3
14: const_0
15: store_2
16: load_2
17: load_1
18: jge 21 (=39)
21: load_0
22: load_2
23: aload
24: const_0
25: print
26: const 32
31: const_0
32: bprint
33: inc 2,1
36: jmp -20 (=16)
39: const 10
44: const_0
45: bprint
46: exit
47: return
48: enter 0 5
51: const_0
52: store_0
53: const 10
58: newarray 1
60: store_1
61: const 10
66: newarray 1
68: store_2
69: load_0
70: const 10
75: jge 74 (=149)
78: load_1
79: load_0
80: load_0
81: const 10
86: mul
87: load_0
88: const_3
89: rem
90: add
91: astore
92: load_0
93: const_2
94: rem
95: const_1
96: jne 12 (=108)
99: load_1
100: load_0
101: const_1
102: neg
103: load_1
104: load_0
105: aload
106: mul
107: astore
108: load_1
109: load_0
110: aload
111: const_2
112: call -112 (=0)
115: store_3
116: load_1
117: load_0
118: aload
119: const_3
120: call -120 (=0)
123: store 4
125: load_3
126: load 4
128: jle 10 (=138)
131: load_2
132: load_0
133: load_3
134: astore
135: jmp 8 (=143)
138: load_2
139: load_0
140: load 4
142: astore
143: inc 0,1
146: jmp -77 (=69)
149: load_1
150: const 10
155: call -144 (=11)
158: load_2
159: const 10
164: call -153 (=11)
167: exit
168: return
</pre>

== 4. zadatak ==
{{delimično rešeno}}
=== Postavka ===
'''(10p)''' Za datu gramatiku konstruisati:
<div class="abc-list">
# LR(0) karakteristični automat
# LALR(1) karakteristični automat
# Za oba slučaja LR(0) i LALR(1) navesti stanja sa po jednim konfliktom i objasniti o kom se konfliktu radi, u slučaju da konflikt postoji. Nije potrebno konstruisati tabele parsera.
</div>
Oba automata prikazati u vidu grafa prelaza, unutar stanja napisati konfiguracije.

<div>
# <code><S> → ( <X> )</code>
# <code><S> → [ <X> ]</code>
# <code><S> → ( <Y> ]</code>
# <code><S> → [ <Y> )</code>
# <code><X> → a</code>
# <code><Y> → a</code>
</div>

== 5. zadatak ==
{{delimično rešeno}}
=== Postavka ===
'''(10p)''' Nacrtati graf memorijske predstave objekata c, d1 i d2:
<syntaxhighlight lang="java">
class A { int x; }
class B { int y; }
class C extends A, B { int z; }
class D extends B, C { int v; }
C c; D d1, d2;
</syntaxhighlight>

<div class="abc-list">
# Ako je dozvoljen neiskorišćen prostor na nivou objekata.
# Ako neiskorišćen prostor može da postoji samo na nivou klase, a ne i objekata
</div>

== 6. zadatak ==
{{delimično rešeno}}
=== Postavka ===
'''(10p)''' Dat je sledeći program na jeziku sličnom Pascalu. Statičko okruženje za nelokalne promenljive je realizovano pomoću pristupnih veza. Glavni program poseduje sopstveni akcioni zapis na steku.

<div class="abc-list">
# Prikazati jasno i precizno izgled steka poziva neposredno pre povratka iz procedure c. Voditi računa o formatu aktivacionih zapisa
# Napisati kompletan 80x86 asemblerski kod koji bi kompajler izgenerisao za procedure c i d (enter i leave instrukcije ne postoje)
</div>

<syntaxhighlight lang="pascal">
program Sep23 (output);
var g, t: integer

procedure b(p: integer)
var m: integer;

procedure c ()
begin
g := m+t;
end; {c}
procedure d (p: integer)
t := p+2;
c();
end {d}
begin
m := p+1;
d(m);
end; {b}

begin
g := 1
b(g);
end. {Sep23}
</syntaxhighlight>

[[Категорија:Рокови]]
[[Категорија:Програмски преводиоци 1]]

Програмски преводиоци 1/Јануар 2023

2025-10-13T23:45:15Z

Andrija: Postavka je dostupna na stranici predmeta

{{tocright}}
'''Januarski ispit 2023. godine''' održan je 19. januara. Postavka roka je dostupna sa [http://ir4pp1.etf.rs/Rokovi/2022-2023/pp1-2223-januar.pdf stranice predmeta].

== 1. zadatak ==
=== Postavka ===
Dat je sledeći program:
<syntaxhighlight lang="cpp">
int main() {
int count;
void procX() {
void report() {
writeln("count = " + count);
}
void proxY() {
int count;
count = 200;
report();
}
count = 100;
report();
procY();
}
count = 300;
procX();
}
</syntaxhighlight>
<div class="abc-list">
# Ukoliko se koristi statičko razrešavanje dosega, šta će ispisati dati program?
# Ukoliko se koristi dinamičko razrešavanje dosega, šta će ispisati dati program?
# Ukoliko se za nelokalne promenljive koriste displeji, nacrtati poslednje stanje steka i displeja nakon što je <code>report</code> funkcija pozvana poslednji put.
</div>

=== Rešenje ===
a) Ispis: 
count = 100 
count = 100 
Objasnjenje: Statičko razrešavanje znači da veza između imena promenljive i deklaracije se pravi u vreme prevođenja (kompajliranja).
Dakle, kada se report kompajlira, kompajler već odluči: "ovo count u report se odnosi na count iz procX", jer je to najbliži leksički obuhvatajući opseg.
 
b) Ispis: 
count = 100 
count = 200 
Objasnjenje: Kod dinamičkog razrešavanja, nelokalna promenljiva se traži preko lanca aktivacionih zapisa na steku, počev od najbližeg pozivaoca.
c)

== 2. zadatak ==
=== Postavka ===
Dat je isečak koda klase <code>Struct</code>. Dopuniti metodu <code>AssignableTo</code> kodom koji fali.
<syntaxhighlight lang="java">
public class Struct {
private int kind;
private Struct elemType;
public boolean Equals(Struct other) {
return (this == other) || (kind == Kinds.Array && other.kind == Kinds.Array && elemType.Equals(other.ElemType));
}
public boolean IsRefType() {
return kind == Kinds.Class || kind == Kinds.Array;
}
public boolean AssignableTo(Struct dest) {
if (this.Equals(dest) ||
|| (kind == Kinds.Array && dest.kind == Kinds.Array && dest.elemType == Tab.noType)) {
return true;
}
return false;
}
}
</syntaxhighlight>

=== Rešenje ===
Preuzeto iz [http://ir4pp1.etf.rs/Predavanja/pp1_udzbenik.pdf udžbenika Programski prevodioci 1] (Dragan Bojić, Maja Vukasović) sa strane 209.
<syntaxhighlight lang="java">
class Struct {
...
// checks, if this can be assigned to dest (explicit. assignment, parameters)
public bool AssignableTo (Struct dest) {
if ( this.Equals(dest) || this == Tab.nullType && dest.IsRefType() ||
kind == Kinds.Arr && dest.kind == Kinds.Arr && // for len()
dest.elemType == Tab.noType) return true;
for (Struct s = elemType; s != null; s = s.elemType) {
if (s.equals(dest)) return true;
}
return false;
}
}
</syntaxhighlight>

== 3. zadatak ==
{{delimično rešeno}}
=== Postavka ===
Za dati blok koda napisati međukod a zatim nacrtati graf toka kontrole sa međukodom u SSA formi.
<syntaxhighlight lang="cpp">
int res = 10;
for (int i = 0; i < 10; i++) {
int n = res;
for (int j = i + 1; j < n; j++) {
if ((i + j) % 2 == 0) {
res++;
}
}
}
</syntaxhighlight>

=== Rešenje ===

== 4. zadatak ==
=== Postavka ===
Za datu gramatiku konstruisati karakteristički LR(0) automat i kontrolnu tabelu, a zatim dodati LALR(1) predikcione skupove.
# <S> → <S> <A>
# <A> → <A> a <A> b
# <A> → <S> a
# <A> → c

=== Rešenje ===
Ova postavka zadatka je gotovo sigurno pogrešna, jer se u stanju praznog steka kod LR(0) parsera ne može preći ni u jedno drugo stanje, a ne može ni da se uradi Reduce. Takođe, nejasno je kakve ulazne sekvence prihvata/odbija ovakva gramatika jer se one ne mogu ni generisati zbog toga što jedina smena za startni neterminal < S > sadrži levu rekurziju, pa je tako jedina moguća sekvenca ona u kojoj se < S > neprestano dodaje na početak.

== 5. zadatak ==
=== Postavka ===
U datoj gramatici neterminalu <code><list></code> dodati sintetizovani atribut koji naizmenično sadrži cifre najvećih i najmanjih brojeva iz niza. Na primer, ukoliko je sekvenca koja se prepoznaje [1, 2, 3] [4, 5, 6] [7, 8, 9], taj atribut bi imao vrednost 349. Smatrati da terminal <code>INT</code> ima sintetizovani simbol sa svojom vrednošću.
# <list> → <list> <item>
# <list> → <item>
# <item> → [ <num_arr> ]
# <num_arr> → <num_arr>, INT
# <num_arr> → INT

=== Rešenje ===
Uvodimo sledeće sintetizovane atribute:
* INTdigit - digit predstavlja cifru opisanu terminalom INT
* <num_arr>minDigit, maxDigit - minDigit predstavlja minimalnu cifru sadržanu u nizu cifara <num_arr>, a maxDigit maksimalnu cifru sadržanu u nizu cifara <num_arr>
* <item>minDigit, maxDigit - minDigit predstavlja minimalnu cifru sadržanu u nizu cifara koji se nalazi u neterminalu <item>, a maxDigit maksimalnu cifru sadržanu u nizu cifara koji se nalazi u neterminalu <item>
* <list>value, takeMinDigit - value predstavlja vrednost koju treba izračunati po postavci zadatka, a takeMinDigit da li u sledećem koraku treba uzeti minimalnu ili maksimalnu cifru (ovo posmatramo kao neki flag kome u svakom koraku invertujemo vrednost, a čija je početna vrednost 1 jer u prvom koraku uzimamo maksimalnu, a u drugom minimalnu cifru)

Atributivno translaciona gramatika izgleda ovako (stvari koje su dodate u odnosu na gramatiku iz postavke su prikazane '''podebljanim slovima'''):

# <list>'''value, takeMinDigit''' -> <list>'''valueRHS, takeMinDigitRHS''' <item>'''minDigit, maxDigit''' '''{ value = valueRHS * 10 + (takeMinDigitRHS == 1) ? minDigit : maxDigit; takeMinDigit = 1 - takeMinDigitRHS; }'''
# <list>'''value, takeMinDigit''' -> <item>'''minDigit, maxDigit''' '''{ value = maxDigit; takeMinDigit = 1; }'''
# <item>'''minDigit, maxDigit''' -> [ <num_arr>'''minDigitRHS, maxDigitRHS''' ] '''{ minDigit = minDigitRHS; maxDigit = maxDigitRHS; }'''
# <num_arr>'''minDigit, maxDigit''' -> <num_arr>'''minDigitRHS, maxDigitRHS''' , INT'''digit''' '''{ minDigit = min(minDigitRHS, digit); maxDigit = max(maxDigitRHS, digit); }'''
# <num_arr>'''minDigit, maxDigit''' -> INT'''digit''' '''{ minDigit = digit; maxDigit = digit; }'''

== 6. zadatak ==
=== Postavka ===
Napisati kompletan prevod funkcija <code>f1</code>, <code>f2</code> i <code>main</code> na Mikrojava bajtkod. Smatrati da prevod <code>f1</code> kreće od adrese 0. Sekciju označenu sa <code>// ...</code> nije potrebno prevoditi i smatrati da je njena dužina jedna instrukcija.
<syntaxhighlight lang="cpp">
program Januar2023
int b;
class A {
int fun1(int p) {...}
}
class B {
A[] arr;
}
B bObj;
int f1() {
return 1;
}
int f2() {
return 2;
}
void main() int x; {
bObj = new B;
// ...
b = bObj.arr[1].fun1(3);
if (b < x) {
b = f1();
}
else b = f2();
}
</syntaxhighlight>

=== Rešenje ===
<syntaxhighlight lang="asm">
00: enter 0 0
03: const_1
04: exit
05: return
06: enter 0 0
09: const_2
10: exit
11: return
12: enter 0 1
15: new 4
18: dup
19: const_2
20: putfield 0
23: putstatic 1
26: ...
27: getstatic 1
30: getfield 1
33: const_1
34: aload
35: const_3
36: getstatic 1
39: getfield 1
42: const_1
43: aload
44: getfield 0
47: invokevirtual 'f' 'u' 'n' '1' -1
68: putstatic 0
71: getstatic 0
74: load_0
75: jge 12
78: call -78
81: putstatic 0
84: jmp 9
87: call -81
90: putstatic 0
93: exit
94: return
95: ...
</syntaxhighlight>

[[Категорија:Рокови]]
[[Категорија:Програмски преводиоци 1]]

Програмски преводиоци 1/Септембар 2023

2025-10-13T23:36:02Z

Andrija: Rok je delimicno resen

{{tocright}}
'''Ispit u septembarskom roku 2023. godine''' održan je 16. Septembra.

== 1. zadatak ==
=== Postavka ===
'''(10p)''' Dat je deo implementacije klase ''Node'' u programskom jeziku ''Java'', koja predstavlja čvor u sintaksnom stablu izgenerisanom za konstrukciju DKA korišćenjem metoda pozicije, gde su objašnjenja polja i metoda data u komentarima iznad njih (sva polja su inicijalizovana konstruktorom):
<syntaxhighlight lang="cpp">
public class Node {
private enum Type {
ASTERISK, // *
PLUS, // +
PERIOD, // .
OR, // |
SYMBOL, // s
EPSILON // ε
}
// left subtree of position node, null if leaf (symbol) node
private Node left;

// right subtree of position node, null if unary operation or leaf (symbol) node
private Node right;

// type of position node
private Type type;

// position of symbol in regex, only valid for leaf (symbol) nodes, otherwise set to -1
private int symbolPos;

// check whether the subsequence with the given node as root of the subtree can be empty
public boolean isNullable();

// find sert of leaf (symbol) node positions which could be at the beginning of
// subsequence with the given node as root of the subtree
public Set<Integer> firstPos();

// find set of leaf (symbol) node positions which could be at the end of
// subsequence with the given node as root of the subtree
public Set<Integer> lastPos();

// returns a union of the two parameters
public static Set<Integer> union(Set<Integer> first, Set<Integer> second);
}
</syntaxhighlight>
Potrebno je napisati implementaciju metoda <code>firstPos()</code> i <code>lastPos()</code>

=== 1a. zadatak ===
Identičan ovakav zadatak (za isti broj poena) se pojavio u Avgustu 2023, samo se tražila implementacija <code>isNullable()</code>.

=== Rešenje ===
<syntaxhighlight lang="java">
public Set<Integer> firstPos() {
Set<Integer> ret = new HashSet<Integer>();

switch (this.type) {
case 'SYMBOL':
ret.add(this.symbolPos);
break;

case 'ASTERISK':
return this.left.firstPos();

case 'OR':
for (Integer pos : this.left.firstPos()) {
ret.add(pos);
}
for (Integer pos : this.right.firstPos()) {
ret.add(pos);
}
break;

case 'PERIOD':
for (Integer pos : this.left.firstPos()) {
ret.add(pos);
}
if (this.left.isNullable()) {
for (Integer pos : this.right.firstPos()) {
ret.add(pos);
}
}
break;

default:
break;
}

return ret;
}

public Set<Integer> lastPos() {
Set<Integer> ret = new HashSet<Integer>();

switch (this.type) {
case 'SYMBOL':
ret.add(this.symbolPos);
break;

case 'ASTERISK':
return this.left.lastPos();

case 'OR':
for (Integer pos : this.left.lastPos()) {
ret.add(pos);
}
for (Integer pos : this.right.lastPos()) {
ret.add(pos);
}
break;

case 'PERIOD':
for (Integer pos : this.right.lastPos()) {
ret.add(pos);
}
if (this.right.isNullable()) {
for (Integer pos : this.left.lastPos()) {
ret.add(pos);
}
}
break;

default:
break;
}

return ret;
}

public boolean isNullable(){
switch(this.type){
case 'SYMBOL':
return false;

case 'EPSILON':
case 'ASTERISK':
return true;

case 'PERIOD':
return this.left.isNullable() && this.right.isNullable();

case 'OR':
return this.left.isNullable() || this.right.isNullable();

default: return false;
}

}
</syntaxhighlight>

== 2. zadatak ==
{{delimično rešeno}}
=== Postavka ===
'''(10p)''' Za rekurzivni spust koji opisuje navedenu gramatiku, koji su opisani ispod:
<div class="abc-list">
# Dopuniti delove rekurzivnog spusta obeleženih sa labelama PN (N označava labelu koja se može popuniti i može predstavljati jednu ili više linija koda), ukoliko je poznato da se sekvence ''aadddbb'', ''dd'' i ''ab'' prihvataju.
# Napisati LL(1) gramatiku opisanu rekurzivnim spustom.
</div>

<pre>
Glavni program:
IN = NEXTCHAR();
call PROCS;
if (INP<> '˧')
then REJECT;
else ACCEPT;
end if;
end;

procedure PROCS:
case IN of
'a': goto P1;
'd', 'b', '˧': goto P2;
default: REJECT;
end case;
P1: /* ... */
P2: /* ... */
end procedure;

procedure PROCA:
case IN of
'b', '˧': goto P3;
'd': goto P4;
default: REJECT;
end case;
P3: /* ... */
P4: /* ... */
end procedure;
</pre>

== 3. zadatak ==
{{delimično rešeno}}
=== Postavka ===
'''(10p)''' Za dati Mikrojava bajtkod:
<div class="abc-list">
# Navesti izlaz programa.
# Rekonstruisati izvorni Mikrojava kod na osnovu datog bajtkoda.
</div>
<pre>
0: enter 2 2
3: load_0
4: load_1
5: mul
6: jmp 3 (=9)
9: exit
10: return
11: enter 2 3
14: const_0
15: store_2
16: load_2
17: load_1
18: jge 21 (=39)
21: load_0
22: load_2
23: aload
24: const_0
25: print
26: const 32
31: const_0
32: bprint
33: inc 2,1
36: jmp -20 (=16)
39: const 10
44: const_0
45: bprint
46: exit
47: return
48: enter 0 5
51: const_0
52: store_0
53: const 10
58: newarray 1
60: store_1
61: const 10
66: newarray 1
68: store_2
69: load_0
70: const 10
75: jge 74 (=149)
78: load_1
79: load_0
80: load_0
81: const 10
86: mul
87: load_0
88: const_3
89: rem
90: add
91: astore
92: load_0
93: const_2
94: rem
95: const_1
96: jne 12 (=108)
99: load_1
100: load_0
101: const_1
102: neg
103: load_1
104: load_0
105: aload
106: mul
107: astore
108: load_1
109: load_0
110: aload
111: const_2
112: call -112 (=0)
115: store_3
116: load_1
117: load_0
118: aload
119: const_3
120: call -120 (=0)
123: store 4
125: load_3
126: load 4
128: jle 10 (=138)
131: load_2
132: load_0
133: load_3
134: astore
135: jmp 8 (=143)
138: load_2
139: load_0
140: load 4
142: astore
143: inc 0,1
146: jmp -77 (=69)
149: load_1
150: const 10
155: call -144 (=11)
158: load_2
159: const 10
164: call -153 (=11)
167: exit
168: return
</pre>

== 4. zadatak ==
{{delimično rešeno}}
=== Postavka ===
'''(10p)''' Za datu gramatiku konstruisati:
<div class="abc-list">
# LR(0) karakteristični automat
# LALR(1) karakteristični automat
# Za oba slučaja LR(0) i LALR(1) navesti stanja sa po jednim konfliktom i objasniti o kom se konfliktu radi, u slučaju da konflikt postoji. Nije potrebno konstruisati tabele parsera.
</div>
Oba automata prikazati u vidu grafa prelaza, unutar stanja napisati konfiguracije.

<div>
# <code><S> → ( <X> )</code>
# <code><S> → [ <X> ]</code>
# <code><S> → ( <Y> ]</code>
# <code><S> → [ <Y> )</code>
# <code><X> → a</code>
# <code><Y> → a</code>
</div>

== 5. zadatak ==
{{delimično rešeno}}
=== Postavka ===
'''(10p)''' Nacrtati graf memorijske predstave objekata c, d1 i d2:
<syntaxhighlight lang="java">
class A { int x; }
class B { int y; }
class C extends A, B { int z; }
class D extends B, C { int v; }
C c; D d1, d2;
</syntaxhighlight>

<div class="abc-list">
# Ako je dozvoljen neiskorišćen prostor na nivou objekata.
# Ako neiskorišćen prostor može da postoji samo na nivou klase, a ne i objekata
</div>

== 6. zadatak ==
{{delimično rešeno}}
=== Postavka ===
'''(10p)''' Dat je sledeći program na jeziku sličnom Pascalu. Statičko okruženje za nelokalne promenljive je realizovano pomoću pristupnih veza. Glavni program poseduje sopstveni akcioni zapis na steku.

<div class="abc-list">
# Prikazati jasno i precizno izgled steka poziva neposredno pre povratka iz procedure c. Voditi računa o formatu aktivacionih zapisa
# Napisati kompletan 80x86 asemblerski kod koji bi kompajler izgenerisao za procedure c i d (enter i leave instrukcije ne postoje)
</div>

<syntaxhighlight lang="pascal">
program Sep23 (output);
var g, t: integer

procedure b(p: integer)
var m: integer;

procedure c ()
begin
g := m+t;
end; {c}
procedure d (p: integer)
t := p+2;
c();
end {d}
begin
m := p+1;
d(m);
end; {b}

begin
g := 1
b(g);
end. {Sep23}
</syntaxhighlight>

[[Категорија:Рокови]]
[[Категорија:Програмски преводиоци 1]]

Програмски преводиоци 1/Јануар 2024

2025-10-13T23:33:14Z

Andrija: Rok je delimicno resen

{{tocright}}
'''Januarski ispit 2024. godine''' održan je 18. januara i trajao je 150 minuta. Postavka roka nije dostupna sa stranice predmeta.

== 1. zadatak ==
{{delimično rešeno}}
=== Postavka ===
Dat je sledeći kod na programskom jeziku C.
<syntaxhighlight lang="c">
int f1(int a) {
int b = a;
b = b + 1;
return b;
}

int f2(int a) {
int b = a;
b = b + f1(1);
return b;
}

int m(int a, int n, int (*m1)(int), int(*m2)(int)) {
int tmp1, int tmp2;
tmp1 = f1(a);
tmp2 = f2(a);

if (n == 0) {
return 1;
} else {
return tmp2 * m(tmp1, n - 1, m1, m2);
}
}

int main() {
printf("%d", m(1, 3, &f1, &f2));
return 0;
}
</syntaxhighlight>

* Dati ispis programa;
* Dati izgled steka nakon poslednjeg poziva funkcije <code>f2</code>;
* Dati x86 kod za funkciju <code>f2</code>.

=== Rešenje ===

== 2. zadatak ==
{{delimično rešeno}}
=== Postavka ===
Data je sledeća gramatika:
* <S> -> <S>a
* <S> -> <S><A>b
* <S> -> eps
* <A> -> a
* <A> -> b

# Konstruisati automat i kontrolnu tabelu SLR(1) automata
# Ispraviti gramatiku tako da se ukloni konflikt ali semantika ostane ista.

=== Rešenje ===

== 3. zadatak ==
=== Postavka ===
Date su sledeće gramatike:

Gramatika A:
# -> o 
# -> v

Gramatika B:
# -> o 
# -> v

Gramatika C:
# -> o
# -> v

Gramatika D:
# -> v <Q>
# <Q> -> o <Q>
# <Q> -> eps

Gramatika E
# -> v o
# -> v

* Koje su dve gramatike iste?
* Dokazati na primeru neke sekvence da se ostale 3 gramatike razlikuju.

=== Rešenje ===
a) Gramatika A jedina može počinjati sa O, pa ona sigurno nije ista kao neka druga. Gramatika B može prihvatiti sekvencu VOV, dok gramatika C ne može, pa ni one nisu iste. Gramatika C mora početi sa VV, što važi i za gramatiku E, pa su te dve gramatike iste.

b) Ukoliko uzmemo sekvencu OVV, takva sekvenca je validna za gramatiku A, ali nije za gramatike B i D. U gramatici B vidimo da ukoliko je ulazna sekvenca duža od 1, posle V mora da sledi O, dok u gramatici D to nije slučaj. Na primer, za sekvencu VVO se vidi da se B i D razlikuju jer gramatika D prihvata takvu sekvencu dok je gramatika B odbija.

== 4. zadatak ==
=== Postavka ===
Napisati funkciju <code>static Obj find(String name, boolean isGlobal)</code> za mikrojavu, koja se ponaša kao operator <code>::</code> ako je <code>isGlobal=true</code>. Traženu funkciju pisati od nule.

<syntaxhighlight lang="java">
public class Tab {
public static final Struct
noType = new Struct(Struct.None),
intType = new Struct(Struct.Int),
charType = new Struct(Struct.Char),
nullType = new Struct(Struct.Class);
public static final Obj noObj = new Obj(Obj.Var, "noObj", noType);
public static Obj chrObj, ordObj, lenObj;
public static Scope currentScope;
private static int currentLevel; //universe == -1

public static Obj find(String name, boolean isGlobal);
}
</syntaxhighlight>

=== Rešenje ===
<syntaxhighlight lang="java">
public static Obj find(String name, boolean isGlobal) {
Obj result = null;

if (isGlobal == true) {
Scope s = currentScope;

while (s.getOuter() != null) {
s = s.getOuter();
}

if (s.getLocals() != null) {
result = s.getLocals().searchKey(name);
}

} else {
for (Scope s = currentScope; s != null; s = s.getOuter()) {
if (s.getLocals() != null) {
result = s.getLocals().searchKey(name);
if (result != null) break;
}
}
}

return (result != null) ? result : noObj;
}
</syntaxhighlight>
Operator :: preskače sve opsege i traži ime direktno u universe opsegu. Pošto u fragmentu koda koji je dat nije navedeno da postoji pokazivač na universe opseg, onda se u if grani ide na gore sve dok se ne dođe do njega i zatim se u njemu pretražuje. Else grana je standardna implementacija koja je data u projektu.

== 5. zadatak ==
{{delimično rešeno}}
=== Postavka ===
Za dati regularni izraz <code>(a | (bc)*)+ d (c | ε)+</code> konstruisati DKA.

=== Rešenje ===

== 6. zadatak ==
{{delimično rešeno}}
=== Postavka ===
Za sledeći kod napisati Mikrojava bajtkod.
<syntaxhighlight lang="java">
int b;
const int one = 1;

class A {
int[] niz;
int calc(int a) {
...nebitno
}
}

class B extends A {
int calc(int a) {
...isto nebitno
}
}

int f(int c)
{
if (c > 10) return c;
else return c + 1;
}

void main()
int x, y; A c;
{
read(b);
b = f(b);
c = new B;
x = 0;

do {
if (x % 2 == 0) y = c.calc(b);
else y = y + (b + one);

x++;
} while (x < 5);
}
</syntaxhighlight>

=== Rešenje ===

[[Категорија:Рокови]]
[[Категорија:Програмски преводиоци 1]]

Програмски преводиоци 1/Јануар 2023

2025-10-13T23:31:40Z

Andrija: Rok je delimicno resen

{{tocright}}
'''Januarski ispit 2023. godine''' održan je 19. januara. Postavka roka nije dostupna sa stranice predmeta.

== 1. zadatak ==
=== Postavka ===
Dat je sledeći program:
<syntaxhighlight lang="cpp">
int main() {
int count;
void procX() {
void report() {
writeln("count = " + count);
}
void proxY() {
int count;
count = 200;
report();
}
count = 100;
report();
procY();
}
count = 300;
procX();
}
</syntaxhighlight>
<div class="abc-list">
# Ukoliko se koristi statičko razrešavanje dosega, šta će ispisati dati program?
# Ukoliko se koristi dinamičko razrešavanje dosega, šta će ispisati dati program?
# Ukoliko se za nelokalne promenljive koriste displeji, nacrtati poslednje stanje steka i displeja nakon što je <code>report</code> funkcija pozvana poslednji put.
</div>

=== Rešenje ===
a) Ispis: 
count = 100 
count = 100 
Objasnjenje: Statičko razrešavanje znači da veza između imena promenljive i deklaracije se pravi u vreme prevođenja (kompajliranja).
Dakle, kada se report kompajlira, kompajler već odluči: "ovo count u report se odnosi na count iz procX", jer je to najbliži leksički obuhvatajući opseg.
 
b) Ispis: 
count = 100 
count = 200 
Objasnjenje: Kod dinamičkog razrešavanja, nelokalna promenljiva se traži preko lanca aktivacionih zapisa na steku, počev od najbližeg pozivaoca.
c)

== 2. zadatak ==
=== Postavka ===
Dat je isečak koda klase <code>Struct</code>. Dopuniti metodu <code>AssignableTo</code> kodom koji fali.
<syntaxhighlight lang="java">
public class Struct {
private int kind;
private Struct elemType;
public boolean Equals(Struct other) {
return (this == other) || (kind == Kinds.Array && other.kind == Kinds.Array && elemType.Equals(other.ElemType));
}
public boolean IsRefType() {
return kind == Kinds.Class || kind == Kinds.Array;
}
public boolean AssignableTo(Struct dest) {
if (this.Equals(dest) ||
|| (kind == Kinds.Array && dest.kind == Kinds.Array && dest.elemType == Tab.noType)) {
return true;
}
return false;
}
}
</syntaxhighlight>

=== Rešenje ===
Preuzeto iz [http://ir4pp1.etf.rs/Predavanja/pp1_udzbenik.pdf udžbenika Programski prevodioci 1] (Dragan Bojić, Maja Vukasović) sa strane 209.
<syntaxhighlight lang="java">
class Struct {
...
// checks, if this can be assigned to dest (explicit. assignment, parameters)
public bool AssignableTo (Struct dest) {
if ( this.Equals(dest) || this == Tab.nullType && dest.IsRefType() ||
kind == Kinds.Arr && dest.kind == Kinds.Arr && // for len()
dest.elemType == Tab.noType) return true;
for (Struct s = elemType; s != null; s = s.elemType) {
if (s.equals(dest)) return true;
}
return false;
}
}
</syntaxhighlight>

== 3. zadatak ==
{{delimično rešeno}}
=== Postavka ===
Za dati blok koda napisati međukod a zatim nacrtati graf toka kontrole sa međukodom u SSA formi.
<syntaxhighlight lang="cpp">
int res = 10;
for (int i = 0; i < 10; i++) {
int n = res;
for (int j = i + 1; j < n; j++) {
if ((i + j) % 2 == 0) {
res++;
}
}
}
</syntaxhighlight>

=== Rešenje ===

== 4. zadatak ==
=== Postavka ===
Za datu gramatiku konstruisati karakteristički LR(0) automat i kontrolnu tabelu, a zatim dodati LALR(1) predikcione skupove.
# <S> → <S> <A>
# <A> → <A> a <A> b
# <A> → <S> a
# <A> → c

=== Rešenje ===
Ova postavka zadatka je gotovo sigurno pogrešna, jer se u stanju praznog steka kod LR(0) parsera ne može preći ni u jedno drugo stanje, a ne može ni da se uradi Reduce. Takođe, nejasno je kakve ulazne sekvence prihvata/odbija ovakva gramatika jer se one ne mogu ni generisati zbog toga što jedina smena za startni neterminal < S > sadrži levu rekurziju, pa je tako jedina moguća sekvenca ona u kojoj se < S > neprestano dodaje na početak.

== 5. zadatak ==
=== Postavka ===
U datoj gramatici neterminalu <code><list></code> dodati sintetizovani atribut koji naizmenično sadrži cifre najvećih i najmanjih brojeva iz niza. Na primer, ukoliko je sekvenca koja se prepoznaje [1, 2, 3] [4, 5, 6] [7, 8, 9], taj atribut bi imao vrednost 349. Smatrati da terminal <code>INT</code> ima sintetizovani simbol sa svojom vrednošću.
# <list> → <list> <item>
# <list> → <item>
# <item> → [ <num_arr> ]
# <num_arr> → <num_arr>, INT
# <num_arr> → INT

=== Rešenje ===
Uvodimo sledeće sintetizovane atribute:
* INTdigit - digit predstavlja cifru opisanu terminalom INT
* <num_arr>minDigit, maxDigit - minDigit predstavlja minimalnu cifru sadržanu u nizu cifara <num_arr>, a maxDigit maksimalnu cifru sadržanu u nizu cifara <num_arr>
* <item>minDigit, maxDigit - minDigit predstavlja minimalnu cifru sadržanu u nizu cifara koji se nalazi u neterminalu <item>, a maxDigit maksimalnu cifru sadržanu u nizu cifara koji se nalazi u neterminalu <item>
* <list>value, takeMinDigit - value predstavlja vrednost koju treba izračunati po postavci zadatka, a takeMinDigit da li u sledećem koraku treba uzeti minimalnu ili maksimalnu cifru (ovo posmatramo kao neki flag kome u svakom koraku invertujemo vrednost, a čija je početna vrednost 1 jer u prvom koraku uzimamo maksimalnu, a u drugom minimalnu cifru)

Atributivno translaciona gramatika izgleda ovako (stvari koje su dodate u odnosu na gramatiku iz postavke su prikazane '''podebljanim slovima'''):

# <list>'''value, takeMinDigit''' -> <list>'''valueRHS, takeMinDigitRHS''' <item>'''minDigit, maxDigit''' '''{ value = valueRHS * 10 + (takeMinDigitRHS == 1) ? minDigit : maxDigit; takeMinDigit = 1 - takeMinDigitRHS; }'''
# <list>'''value, takeMinDigit''' -> <item>'''minDigit, maxDigit''' '''{ value = maxDigit; takeMinDigit = 1; }'''
# <item>'''minDigit, maxDigit''' -> [ <num_arr>'''minDigitRHS, maxDigitRHS''' ] '''{ minDigit = minDigitRHS; maxDigit = maxDigitRHS; }'''
# <num_arr>'''minDigit, maxDigit''' -> <num_arr>'''minDigitRHS, maxDigitRHS''' , INT'''digit''' '''{ minDigit = min(minDigitRHS, digit); maxDigit = max(maxDigitRHS, digit); }'''
# <num_arr>'''minDigit, maxDigit''' -> INT'''digit''' '''{ minDigit = digit; maxDigit = digit; }'''

== 6. zadatak ==
=== Postavka ===
Napisati kompletan prevod funkcija <code>f1</code>, <code>f2</code> i <code>main</code> na Mikrojava bajtkod. Smatrati da prevod <code>f1</code> kreće od adrese 0. Sekciju označenu sa <code>// ...</code> nije potrebno prevoditi i smatrati da je njena dužina jedna instrukcija.
<syntaxhighlight lang="cpp">
int b;
class A {
int fun1(int p) {...}
}
class B {
A[] arr;
}
B bObj;
int f1() {
return 1;
}
int f2() {
return 2;
}
void main() int x; {
bObj = new B;
// ...
b = bObj.arr[1].fun1(3);
if (b < x) {
b = f1();
}
else b = f2();
}
</syntaxhighlight>

=== Rešenje ===
<syntaxhighlight lang="asm">
00: enter 0 0
03: const_1
04: exit
05: return
06: enter 0 0
09: const_2
10: exit
11: return
12: enter 0 1
15: new 4
18: dup
19: const_2
20: putfield 0
23: putstatic 1
26: ...
27: getstatic 1
30: getfield 1
33: const_1
34: aload
35: const_3
36: getstatic 1
39: getfield 1
42: const_1
43: aload
44: getfield 0
47: invokevirtual 'f' 'u' 'n' '1' -1
68: putstatic 0
71: getstatic 0
74: load_0
75: jge 12
78: call -78
81: putstatic 0
84: jmp 9
87: call -81
90: putstatic 0
93: exit
94: return
95: ...
</syntaxhighlight>

[[Категорија:Рокови]]
[[Категорија:Програмски преводиоци 1]]

КДП/Септембар 2023

2025-09-15T15:28:07Z

Andrija: Tekst zadatka ispravka

{{tocright}}


== {{категорија|1. задатак|Синхронизациони_алгоритми}} ==
=== Поставка ===
Написати и објаснити CLH алгоритам за критичну секцију (coarse grain). Реализовати (fine grain) верзију алгоритма уколико би на датом процесору постојала операција SWAP која би недељиво обављала замену вердности два операнда (SWAP(var1, var2): <temp=var1; var1=var2; var2=temp;>). Објаснити зашто је то правична критична секција.
=== Решење ===
CLH алгоритам процесе уланчава у уланчану листу по редоследу којим долазе. Самим тим та листа се понаша као ред и тиме је овај алгоритам правичан јер користи FIFO принцип.
''Coarse-grain'' решење:
<syntaxhighlight lang="cpp">
struct Node {
bool locked;
Node() {
locked = true;
}
};

Node* tail = nullptr;

void process() {
while (true) {
Node* new_node = new Node();
Node* prev;
< prev = tail; tail = new_node; >
< await(tail == nullptr || !prev->locked); >
/* критична секција */
new_node->locked=false;
/* некритична секција */
}
}
</syntaxhighlight>
''Fine-grain'' решење:
Пошто су prev и new_node локални показивачи, можемо да их усмеримо на новокреирани чвор. Затим се недељиво позива функција SWAP која ће недељиво заменити вредност prev и tail показивача.
<syntaxhighlight lang="cpp">
struct Node {
bool locked;
Node() {
locked = true;
}
};

Node* tail = nullptr;

void process() {
while (true) {
Node* new_node = new Node();
Node* prev = new_node;
SWAP(prev, tail);
while(prev!= nullptr && prev->locked) skip();
/* критична секција */
new_node->locked=false;
/* некритична секција */
}
}
</syntaxhighlight>

== {{категорија|2. задатак|Монитори}} ==
=== Поставка ===
Трајект за превоз аутомобила, камиона и аутобуса превози возила са обале на обалу. Трајект поседује N позиција које су линеарлно постављене једна иза друге. Камиона заузима три, аутовус две а аутомобил једну позицију. Возила чекају на трајект у реду и на њега улазе једно по једно по редоследу у ком чекају у реду, док на трајекту има места. Када нема места да се наредно возило у реду укрца и трајект није у потпуности попуњен, преко реда се укрцавају мања возила док се трајект не попуни у потпуности. Када је комплетно пун, трајект започиње превоз возила на другу обалу. На другој обали возила се искрцавају у редоследу супротном од оног у којем су се укрцала. Када се сва возила искрцају, празан трајект се враћа на почетну обалу. Написати монитор са ''signal and wait'' дисциплином који решава дати проблем.
=== Решење ===
{{делимично решено}}
== {{категорија|3. задатак|Филтерски_процеси}} ==
=== Поставка ===
Филтерски процеси имају један улаз и један излаз и раде следеће: примају позитивне вредности на улазу и прослеђују их на излаз ако су веће од запамћеног минимума процеса. Процеси имају само две локације, за сачувани минимум и за последњу примљену вредност. Када на улаз стигне EOS, избацују минималну вредност на излаз а затим EOS. Направите проточну обраду (''pipeline'') од n процеса који опадајуће соритају до n улазних позитивних вредности које се убацују на почетак проточне обраде а завршавају се са EOS.
=== Решење ===
<syntaxhighlight lang="cpp">
void process() {
chan<int> in;
chan<int> out;
int input;
int min;
while ((input = in.receive()) != EOS) {
if (input < min) {
out.send(min);
min = input;
} else out.send(input);
}
out.send(min);
out.send(EOS);
}
</syntaxhighlight>

== {{категорија|4. задатак|CSP}} ==
=== Поставка ===
Постоји N пчела и један гладан медвед (''The bear and honeybees''). Они користе заједничку кошницу. Кошница је иницијално празна, a може да прими H напрстака меда. Медвед спава док се кошница не напуни медом, када се напуни медом меда поједе сав мед након чега се враћа на спавање. Пчелице непрестано лете од света до света и сакупљају мед. Када прикупе један напрстак долазе и стављају га у кошницу. Она пчела која је попунила кошницу буди медведа. Решити проблем користећи CSP.

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


<syntaxhighlight lang="pascal">
[Bee(i:1..N)::BEE || Bear::BEAR || BeeHive::BEEHIVE]

BEE :: [
full: boolean
*[
flyAndCollect()
BeeHive!honneyCollected
BeeHive?isFull(full)
full == true -> Bear!hiveFull
]
]

BEAR :: *[
sleep()
[
(i:0..N) Bee(i)?hiveFull
]
eat()
BeeHive!honeyEaten
]

BEEHIVE :: [
H: integer
size: integer := 0

*[
size < H, (i:0..N) Bee(i)?honneyCollected -> [
size := size + 1
Bee(i)!isFull(size == H)
]
□
size == H; Bear?honeyEaten -> [
size := 0
]
]
]
</syntaxhighlight>

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

КДП/Септембар 2023

2025-09-15T15:25:55Z

Andrija: Poboljsanje resenja

{{tocright}}


== {{категорија|1. задатак|Синхронизациони_алгоритми}} ==
=== Поставка ===
Написати и објаснити CLH алгоритам за критичну секцију (coarse grain). Реализовати (fine grain) верзију алгоритма уколико би на датом процесору постојала операција SWAP која би недељиво обављала замену вердности два операнда (SWAP(var1, var2): <temp=var1; var1=var2; var2=temp;>). Објаснити зашто је то правична критична секција.
=== Решење ===
CLH алгоритам процесе уланчава у уланчану листу по редоследу којим долазе. Самим тим та листа се понаша као ред и тиме је овај алгоритам правичан јер користи FIFO принцип.
''Coarse-grain'' решење:
<syntaxhighlight lang="cpp">
struct Node {
bool locked;
Node() {
locked = true;
}
};

Node* tail = nullptr;

void process() {
while (true) {
Node* new_node = new Node();
Node* prev;
< prev = tail; tail = new_node; >
< await(tail == nullptr || !prev->locked); >
/* критична секција */
new_node->locked=false;
/* некритична секција */
}
}
</syntaxhighlight>
''Fine-grain'' решење:
Пошто су prev и new_node локални показивачи, можемо да их усмеримо на новокреирани чвор. Затим се недељиво позива функција SWAP која ће недељиво заменити вредност prev и tail показивача.
<syntaxhighlight lang="cpp">
struct Node {
bool locked;
Node() {
locked = true;
}
};

Node* tail = nullptr;

void process() {
while (true) {
Node* new_node = new Node();
Node* prev = new_node;
SWAP(prev, tail);
while(prev!= nullptr && prev->locked) skip();
/* критична секција */
new_node->locked=false;
/* некритична секција */
}
}
</syntaxhighlight>

== {{категорија|2. задатак|Монитори}} ==
=== Поставка ===
Трајект за превоз аутомобила, камиона и аутобуса превози возила са обале на обалу. Трајект поседује N позиција које су линеарлно постављене једна иза друге. Камиона заузима три, аутовус две а аутомобил једну позицију. Возила чекају на трајект у реду и на њега улазе једно по једно по редоследу у ком чекају у реду, док на трајекту има места. Када нема места да се наредно возило у реду укрца и трајект није у потпуности попуњен, преко реда се укрцавају мања возила док се трајект не попуни у потпуности. Када је комплетно пун, трајект започиње превоз возила на другу обалу. На другој обали возила се искрцавају у редоследу супротном од оног у којем су се укрцала. Када се сва возила искрцају, празан трајект се враћа на почетну обалу. Написати монитор са ''signal and wait'' дисциплином који решава дати проблем.
=== Решење ===
{{делимично решено}}
== {{категорија|3. задатак|Филтерски_процеси}} ==
=== Поставка ===
Филтерски процеси имају један улаз и један излаз и раде следеће: примају позитивне вредности на улазу и прослеђују их на излаз ако су веће од запамћеног минимума процеса. Процеси имају само две локације, за сачувани минимум и за последњу примљену вредност. Када на улаз стигне EOS, избацују минималну вредност на излаз а затим EOS. Направите проточну обраду (''pipeline'') од n процеса који опадајуће соритају до n улазних позитивних вредности које се убацују на почетак проточне обраде а завршавају се са EOS.
=== Решење ===
<syntaxhighlight lang="cpp">
void process() {
chan<int> in;
chan<int> out;
int input;
int min;
while ((input = in.receive()) != EOS) {
if (input < min) {
out.send(min);
min = input;
} else out.send(input);
}
out.send(min);
out.send(EOS);
}
</syntaxhighlight>

== {{категорија|4. задатак|CSP}} ==
=== Поставка ===
Постоји N пчела и један гладан медвед (''The bear and honeybees''). Они користе заједничку кошницу. Кошница је иницијално празна и може да прими до N напрстака меда. Медвед спава док се кошница не напуни медом, када се напуни медом меда поједе сав мед након чега се враћа на спавање. Пчелице непрестано лете од света до света и сакупљају мед. Она пчела која је попунила кошницу буди медведа. Решити проблем користећи CSP.
=== Решење ===


<syntaxhighlight lang="pascal">
[Bee(i:1..N)::BEE || Bear::BEAR || BeeHive::BEEHIVE]

BEE :: [
full: boolean
*[
flyAndCollect()
BeeHive!honneyCollected
BeeHive?isFull(full)
full == true -> Bear!hiveFull
]
]

BEAR :: *[
sleep()
[
(i:0..N) Bee(i)?hiveFull
]
eat()
BeeHive!honeyEaten
]

BEEHIVE :: [
H: integer
size: integer := 0

*[
size < H, (i:0..N) Bee(i)?honneyCollected -> [
size := size + 1
Bee(i)!isFull(size == H)
]
□
size == H; Bear?honeyEaten -> [
size := 0
]
]
]
</syntaxhighlight>

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

КДП/Јул-1 2025

2025-09-14T18:50:59Z

Andrija: Ispravka resenja

{{tocright}}
Испит из КДП-а у року '''Јул-1 2025. године''' одржан је 20. августа. Поставка рока тренутно није доступна онлајн.

== {{категорија|1. задатак|Штафетна_палица}} ==
{{делимично решено}}
=== Поставка ===
Потребно је реализовати семафор који поред стандардних атомских операција <code>signal()</code> и <code>wait()</code> има и атомске операције <code>signal(n)</code> и <code>wait(n)</code> које интерну семафорску променљиву атомски увећава односно умањује за n уколико је то могуће, уколико није чека док не буде било могуће. Потребно је решити проблем користећи расподељене бинарне семафоре и технику предаје штафетне палице. Процес који је раније упутио <code>wait</code> захтев треба раније да обави своју операцију. Претпоставити да у било ком тренутку максимално N процеса може упутити захтев за приступ семафору.

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

== {{категорија|2. задатак|Монитори}} ==
{{делимично решено}}
=== Поставка ===
Аутомобили који долазе са севера и југа морају да пређу реку преко моста (''One lane bridge problem''). На мосту постоји само једна возна трака. Значи, у било ком тренутку мостом може да прође један или више аутомобила који долазе из истог смера (али не и из супротног смера). Обезбедити да се смер саобраћаја мења сваки пут након што га пређе 10 аутомобила из истог смера, ако су за то време један или више аутомобила чекали да га пређу из супротног смера. Написати монитор са signal and wait дисциплином који решава дати проблем.

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

== {{категорија|3. задатак|Филтерски_процеси}} ==
{{делимично решено}}
=== Поставка ===
Филтерска мрежа за тражење минимума низа. Елемент мреже на своје улазе прима две[sic] низа целих бројева која се завршавају са вредношћу ''EOS''. Елемент на једном излазу треба да генерише вредност која одговара минималној вредности из примљених низова, и након тога вредност ''EOS''. Приказати филтерску мрежу која најбрже налази минимум 11 вредности.

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

== {{категорија|4. задатак|C-Linda}} ==
=== Поставка ===
Претпоставити да постоји <math>N</math> путника и једно возило на тобогану (''The roller coaster problem''). Путници се наизменично шетају по луна парку и возе на тобогану. Тобоган може да прими највише <math>K</math> путника при чему је <math>K < N</math>. Вожња тобоганом може да почне само уколико се сакупило тачно <math>K</math> путника. Користећи ''C-Lindu'' написати програм који решава овај проблем.

=== Решење ===
<syntaxhighlight lang="c">
const int N, K; // K < N

void putnik(int i) {
while (true) {
// setnja
in("onboard");
out("onboarded");
// voznja
in("disembark");
out("disembarked");
}
}

void tobogan() {
while (true) {
for (int i = 0; i < K; i++) out("onboard");
for (int i = 0; i < K; i++) in("onboarded");
// voznja
for (int i = 0; i < K; i++) out("disembark");
for (int i = 0; i < K; i++) in("disembarked");
}
}

void init() {
eval(tobogan);
for (int i = 0; i < N; i++) {
eval(putnik, i);
}
}
</syntaxhighlight>

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

КДП/Јул-1 2025

2025-09-14T17:40:16Z

Andrija: Решење 4. задатка

{{tocright}}
Испит из КДП-а у року '''Јул-1 2025. године''' одржан је 20. августа. Поставка рока тренутно није доступна онлајн.

== {{категорија|1. задатак|Штафетна_палица}} ==
{{делимично решено}}
=== Поставка ===
Потребно је реализовати семафор који поред стандардних атомских операција <code>signal()</code> и <code>wait()</code> има и атомске операције <code>signal(n)</code> и <code>wait(n)</code> које интерну семафорску променљиву атомски увећава односно умањује за n уколико је то могуће, уколико није чека док не буде било могуће. Потребно је решити проблем користећи расподељене бинарне семафоре и технику предаје штафетне палице. Процес који је раније упутио <code>wait</code> захтев треба раније да обави своју операцију. Претпоставити да у било ком тренутку максимално N процеса може упутити захтев за приступ семафору.

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

== {{категорија|2. задатак|Монитори}} ==
{{делимично решено}}
=== Поставка ===
Аутомобили који долазе са севера и југа морају да пређу реку преко моста (''One lane bridge problem''). На мосту постоји само једна возна трака. Значи, у било ком тренутку мостом може да прође један или више аутомобила који долазе из истог смера (али не и из супротног смера). Обезбедити да се смер саобраћаја мења сваки пут након што га пређе 10 аутомобила из истог смера, ако су за то време један или више аутомобила чекали да га пређу из супротног смера. Написати монитор са signal and wait дисциплином који решава дати проблем.

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

== {{категорија|3. задатак|Филтерски_процеси}} ==
{{делимично решено}}
=== Поставка ===
Филтерска мрежа за тражење минимума низа. Елемент мреже на своје улазе прима две[sic] низа целих бројева која се завршавају са вредношћу ''EOS''. Елемент на једном излазу треба да генерише вредност која одговара минималној вредности из примљених низова, и након тога вредност ''EOS''. Приказати филтерску мрежу која најбрже налази минимум 11 вредности.

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

== {{категорија|4. задатак|C-Linda}} ==
=== Поставка ===
Претпоставити да постоји <math>N</math> путника и једно возило на тобогану (''The roller coaster problem''). Путници се наизменично шетају по луна парку и возе на тобогану. Тобоган може да прими највише <math>K</math> путника при чему је <math>K < N</math>. Вожња тобоганом може да почне само уколико се сакупило тачно <math>K</math> путника. Користећи ''C-Lindu'' написати програм који решава овај проблем.

=== Решење ===
<syntaxhighlight lang="c">
const int N, K; // K < N

void putnik(int i) {
while (true) {
// setnja
in("ticket");
out("ready");
in("start_ride");
// voznja
in("end_ride");
}
}

void tobogan() {
while (true) {
for (int i = 0; i < K; i++) out("ticket");
for (int i = 0; i < K; i++) in("ready");
for (int i = 0; i < K; i++) out("start_ride");
// voznja
for (int i = 0; i < K; i++) out("end_ride");
}
}

void init() {
eval(tobogan);
for (int i = 0; i < N; i++) {
eval(putnik, i);
}
}
</syntaxhighlight>

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

КДП/Јул-1 2025

2025-09-14T14:31:38Z

Andrija: Ispravka kategorija

{{tocright}}

Испит из КДП-а у року '''Јул-1 2025. године''' одржан је 20. августа. Поставка рока није доступна онлајн.

== {{категорија|1. задатак|Штафетна_палица}} ==
{{нерешено}}
=== Поставка ===
Потребно је реализовати семафор који поред стандардних атомских операција <code>signal()</code> и <code>wait()</code> има и атомске операције <code>signal(n)</code> и <code>wait(n)</code> које интерну семафорску променљиву атомски увећава односно умањује за n уколико је то могуће, уколико није чека док не буде било могуће. Потребно је решити проблем користећи расподељене бинарне семафоре и технику предаје штафетне палице. Процес који је раније упутио <code>wait</code> захтев треба раније да обави своју операцију. Претпоставити да у било ком тренутку максимално N процеса може упутити захтев за приступ семафору.

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

== {{категорија|2. задатак|Монитори}} ==
{{нерешено}}
=== Поставка ===
Аутомобили који долазе са севера и југа морају да пређу реку преко моста (''One lane bridge problem''). На мосту постоји само једна возна трака. Значи, у било ком тренутку мостом може да прође један или више аутомобила који долазе из истог смера (али не и из супротног смера). Обезбедити да се смер саобраћаја мења сваки пут након што га пређе 10 аутомобила из истог смера, ако су за то време један или више аутомобила чекали да га пређу из супротног смера. Написати монитор са signal and wait дисциплином који решава дати проблем.

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

== {{категорија|3. задатак|Филтерски_процеси}} ==
{{нерешено}}
=== Поставка ===
Филтерска мрежа за тражење минимума низа. Елемент мреже на своје улазе прима две[sic] низа целих бројева која се завршавају са вредношћу ''EOS''. Елемент на једном излазу треба да генерише вредност која одговара минималној вредности из примљених низова, и након тога вредност ''EOS''. Приказати филтерску мрежу која најбрже налази минимум 11 вредности.

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

== {{категорија|4. задатак|C-Linda}} ==
{{нерешено}}
=== Поставка ===
Претпоставити да постоји <math>N</math> путника и једно возило на тобогану (''The roller coaster problem''). Путници се наизменично шетају по луна парку и возе на тобогану. Тобоган може да прими највише <math>K</math> путника при чему је <math>K < N</math>. Вожња тобоганом може да почне само уколико се сакупило тачно <math>K</math> путника. Користећи ''C-Lindu'' написати програм који решава овај проблем.

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

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

КДП/Јул-1 2025

2025-09-14T14:24:58Z

Andrija: Math tagovi

{{tocright}}

Испит из КДП-а у року '''Јул-1 2025. године''' одржан је 20. августа. Поставка рока није доступна онлајн.

== {{категорија|1. задатак|Штафетна палица}} ==
{{нерешено}}
=== Поставка ===
Потребно је реализовати семафор који поред стандардних атомских операција <code>signal()</code> и <code>wait()</code> има и атомске операције <code>signal(n)</code> и <code>wait(n)</code> које интерну семафорску променљиву атомски увећава односно умањује за n уколико је то могуће, уколико није чека док не буде било могуће. Потребно је решити проблем користећи расподељене бинарне семафоре и технику предаје штафетне палице. Процес који је раније упутио <code>wait</code> захтев треба раније да обави своју операцију. Претпоставити да у било ком тренутку максимално N процеса може упутити захтев за приступ семафору.

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

== {{категорија|2. задатак|Монитори}} ==
{{нерешено}}
=== Поставка ===
Аутомобили који долазе са севера и југа морају да пређу реку преко моста (''One lane bridge problem''). На мосту постоји само једна возна трака. Значи, у било ком тренутку мостом може да прође један или више аутомобила који долазе из истог смера (али не и из супротног смера). Обезбедити да се смер саобраћаја мења сваки пут након што га пређе 10 аутомобила из истог смера, ако су за то време један или више аутомобила чекали да га пређу из супротног смера. Написати монитор са signal and wait дисциплином који решава дати проблем.

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

== {{категорија|3. задатак|Филтерски процеси}} ==
{{нерешено}}
=== Поставка ===
Филтерска мрежа за тражење минимума низа. Елемент мреже на своје улазе прима две[sic] низа целих бројева која се завршавају са вредношћу ''EOS''. Елемент на једном излазу треба да генерише вредност која одговара минималној вредности из примљених низова, и након тога вредност ''EOS''. Приказати филтерску мрежу која најбрже налази минимум 11 вредности.

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

== {{категорија|4. задатак|C-Linda}} ==
{{нерешено}}
=== Поставка ===
Претпоставити да постоји <math>N</math> путника и једно возило на тобогану (''The roller coaster problem''). Путници се наизменично шетају по луна парку и возе на тобогану. Тобоган може да прими највише <math>K</math> путника при чему је <math>K < N</math>. Вожња тобоганом може да почне само уколико се сакупило тачно <math>K</math> путника. Користећи ''C-Lindu'' написати програм који решава овај проблем.

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

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

КДП/Јул-1 2025

2025-09-14T14:21:54Z

Andrija: Dodat rok Jul-1 2025

{{tocright}}

Испит из КДП-а у року '''Јул-1 2025. године''' одржан је 20. августа. Поставка рока није доступна онлајн.

== {{категорија|1. задатак|Штафетна палица}} ==
{{нерешено}}
=== Поставка ===
Потребно је реализовати семафор који поред стандардних атомских операција <code>signal()</code> и <code>wait()</code> има и атомске операције <code>signal(n)</code> и <code>wait(n)</code> које интерну семафорску променљиву атомски увећава односно умањује за n уколико је то могуће, уколико није чека док не буде било могуће. Потребно је решити проблем користећи расподељене бинарне семафоре и технику предаје штафетне палице. Процес који је раније упутио <code>wait</code> захтев треба раније да обави своју операцију. Претпоставити да у било ком тренутку максимално N процеса може упутити захтев за приступ семафору.

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

== {{категорија|2. задатак|Монитори}} ==
{{нерешено}}
=== Поставка ===
Аутомобили који долазе са севера и југа морају да пређу реку преко моста (''One lane bridge problem''). На мосту постоји само једна возна трака. Значи, у било ком тренутку мостом може да прође један или више аутомобила који долазе из истог смера (али не и из супротног смера). Обезбедити да се смер саобраћаја мења сваки пут након што га пређе 10 аутомобила из истог смера, ако су за то време један или више аутомобила чекали да га пређу из супротног смера. Написати монитор са signal and wait дисциплином који решава дати проблем.

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

== {{категорија|3. задатак|Филтерски процеси}} ==
{{нерешено}}
=== Поставка ===
Филтерска мрежа за тражење минимума низа. Елемент мреже на своје улазе прима две[sic] низа целих бројева која се завршавају са вредношћу ''EOS''. Елемент на једном излазу треба да генерише вредност која одговара минималној вредности из примљених низова, и након тога вредност ''EOS''. Приказати филтерску мрежу која најбрже налази минимум 11 вредности.

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

== {{категорија|4. задатак|C-Linda}} ==
{{нерешено}}
=== Поставка ===
Претпоставити да постоји N путника и једно возило на тобогану (''The roller coaster problem''). Путници се наизменично шетају по луна парку и возе на тобогану. Тобоган може да прими највише K путника при чему је K < N. Вожња тобоганом може да почне само уколико се сакупило тачно K путника. Користећи ''C-Lindu'' написати програм који решава овај проблем.

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

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

КДП/Фебруар 2024

2025-09-14T13:35:54Z

Andrija: Tagovi za delimicno reseno

{{tocright}}

== {{категорија|1. задатак|Синхронизациони_алгоритми}} ==
{{делимично решено}}
=== Поставка ===
Написати и објаснити ''Test and set'' решење за критичну секцију (''coarse grain'' и ''fine grain''). Дати решење за смањење инвалидације кеш меморија у том случају.
=== Решење ===

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

== {{категорија|3. задатак|Активни_монитори}} ==
=== Поставка ===
Решити проблем читалаца и писаца (''Readers-Writers problem'') користећи активне мониторе. Обезбедити да процес који је пре упутио захтев за приступ ресурсу пре треба да буде опслужен.

=== Решење ===
<syntaxhighlight lang="cpp">
const int N; // broj citalaca + broj pisaca
enum op_kind { START_READ, END_READ, START_WRITE, END_WRITE };
chan request(int id, op_kind op);
chan reply[N](bool);

void reader(int id) {
bool status;
while (true) {
send request(id, START_READ);
receive reply[id](status);
// read
send request(id, END_READ);
}
}

void writer(int id) {
bool status;
while (true) {
send request(id, START_WRITE);
receive reply[id](status);
// write
send request(id, END_WRITE);
}
}

void monitor() {
int numR = 0, numW = 0;
queue buffer(int, int);

while (true) {
int id, op;
receive s(id, op);

if (op == START_READ || op == START_WRITE) {
buffer.push(id, op);
}
if (op == END_READ) numR--;
if (op == END_WRITE) numW--;

if (numW == 0 && numR == 0 && !buffer.empty()) {
id, op = buffer.pop();
if (op == START_READ) numR++;
if (op == START_WRITE) numW++;
send reply[id](true);
}
while (numW == 0 && !buffer.empty() && buffer.front().op == START_READ) {
id, op = buffer.pop();
numR++;
send reply[id](true);
}
}
}
</syntaxhighlight>

== {{категорија|4. задатак|CSP}} ==
{{делимично решено}}
=== Поставка ===
Посматра се шпил од 24 карте, подељене у 4 боје, са по 6 различитих бројева. Игру играју 4 играча, која седе за округлим столом и сваки од њих иницијално држи по 4 карте. Између сва суседна играча се налази гомила са картама, која може у неком тренутку бити празна, а иницијално садржи 2 карте. Игра се завршава када бар један играч објави да има све 4 карте истог броја, у различитим бојама, о тада сви играчи прекидају игру. Сваки играч, док год нема 4 карте исте и нико није објавио да је победник, избацује једну карту из своје руке и ставља је на гомилу са своје леве стране, потом узима једну карту са врха из гомиле са своје десне стране. Претпоставити да су играчима иницијално подељене карте на случајан начин. Користећи CSP написати програме за играче и гомиле са картама.
=== Решење ===

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

КДП/Фебруар 2024

2025-09-13T23:09:01Z

Andrija: Ispravka resenja

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

== {{категорија|1. задатак|Синхронизациони_алгоритми}} ==
=== Поставка ===
Написати и објаснити ''Test and set'' решење за критичну секцију (''coarse grain'' и ''fine grain''). Дати решење за смањење инвалидације кеш меморија у том случају.
=== Решење ===

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

== {{категорија|3. задатак|Активни_монитори}} ==
=== Поставка ===
Решити проблем читалаца и писаца (''Readers-Writers problem'') користећи активне мониторе. Обезбедити да процес који је пре упутио захтев за приступ ресурсу пре треба да буде опслужен.

=== Решење ===
<syntaxhighlight lang="cpp">
const int N; // broj citalaca + broj pisaca
enum op_kind { START_READ, END_READ, START_WRITE, END_WRITE };
chan request(int id, op_kind op);
chan reply[N](bool);

void reader(int id) {
bool status;
while (true) {
send request(id, START_READ);
receive reply[id](status);
// read
send request(id, END_READ);
}
}

void writer(int id) {
bool status;
while (true) {
send request(id, START_WRITE);
receive reply[id](status);
// write
send request(id, END_WRITE);
}
}

void monitor() {
int numR = 0, numW = 0;
queue buffer(int, int);

while (true) {
int id, op;
receive s(id, op);

if (op == START_READ || op == START_WRITE) {
buffer.push(id, op);
}
if (op == END_READ) numR--;
if (op == END_WRITE) numW--;

if (numW == 0 && numR == 0 && !buffer.empty()) {
id, op = buffer.pop();
if (op == START_READ) numR++;
if (op == START_WRITE) numW++;
send reply[id](true);
}
while (numW == 0 && !buffer.empty() && buffer.front().op == START_READ) {
id, op = buffer.pop();
numR++;
send reply[id](true);
}
}
}
</syntaxhighlight>

== {{категорија|4. задатак|CSP}} ==
=== Поставка ===
Посматра се шпил од 24 карте, подељене у 4 боје, са по 6 различитих бројева. Игру играју 4 играча, која седе за округлим столом и сваки од њих иницијално држи по 4 карте. Између сва суседна играча се налази гомила са картама, која може у неком тренутку бити празна, а иницијално садржи 2 карте. Игра се завршава када бар један играч објави да има све 4 карте истог броја, у различитим бојама, о тада сви играчи прекидају игру. Сваки играч, док год нема 4 карте исте и нико није објавио да је победник, избацује једну карту из своје руке и ставља је на гомилу са своје леве стране, потом узима једну карту са врха из гомиле са своје десне стране. Претпоставити да су играчима иницијално подељене карте на случајан начин. Користећи CSP написати програме за играче и гомиле са картама.
=== Решење ===



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

КДП/Јул 2020

2025-09-12T17:13:03Z

Andrija: Mala poboljsanja radi citljivosti

{{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{ACQUIRE,RELEASE};
// Poslednji parametar ukazuje na to da li filozof trazi levu (true) ili desnu (false) viljusku
chan request(int, op_kind, bool);
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 == ACQUIRE) {
if (forks[fork] == 0) {
forks[fork] = 1;
send reply[philosopher](true);
} else {
waiting.push({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, ACQUIRE, id != 0);
receive reply[id](status);
send request(id, ACQUIRE, id == 0);
receive reply[id](status);
// Eat
send request(id, RELEASE, id != 0);
send request(id, RELEASE, id == 0);
}
}
</syntaxhighlight>

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

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

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

КДП/Јануар 2023

2025-08-20T02:57:32Z

Andrija: Избачено "задатак није решен"

{{tocright}}
'''Испит у јануарском испитном року 2023. године''' одржан је 18. јанаура. Поставка је доступна на [https://rti.etf.bg.ac.rs/rti/ir3kdp/rokovi/2223/IR3KDP_2023_jan.pdf страници предмета].

== {{категорија|1. задатак|Семафори}} ==
{{делимично решено}}
=== Поставка ===
Имплементирати и објасните основну разлику и разлоге за постојање те разлике између имплементација бафера коначног капацитета (<code>bounded buffer</code>) за случајеве 1 произвођач и 1 потрошач, као и M произвођача и N потрошача помоћу семафора. У складу са објашњењем, прикажите разлике и за случајеве M произвођача и 1 потрошач, као и 1 произвођач и N потрошача.
=== Решење ===

== {{категорија|2. задатак|Монитори}} ==
{{делимично решено}}
=== Поставка ===
Аутомобили који долазе са севера и југа морају да пређу реку преко неког старог моста (<code>Old Bridge problem</code>). На мосту постоји само једна возна трака, па сви аутомобили на мосту морају да се крећу у истом смеру. Због оптерећења моста које мост може да поднесе, број аутомобила који се налазе на мосту не сме да пређе K (K > 0). Написати монитор са <code>signal and continue</code> дисциплином који решава дати проблем.

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

== {{категорија|3. задатак|CSP}} ==
=== Поставка ===
Решити проблем читалаца и писаца користећи ''CSP''. Решење треба да обезбеди да када стигне захтев од писца за тражење дозволе за започињање писања не треба прихватати захтеве за започињање било од читалаца било од писаца док тај писац не заврши са писањем.

=== Решење ===
<syntaxhighlight lang="pascal">
[reader(i:1..N)::READER || writer(i:1..M)::WRITER || conductor::CONDUCTOR]

READER :: *[
conductor!request
conductor!pass
// reading
conductor!done
]

WRITER :: *[
conductor!request
conductor!pass
// writing
conductor!done
]

CONDUCTOR :: [
read_count: integer = 0
write_count: integer = 0
queue: (0..C) integer
who: (0..C) char
head: integer = 0
tail: integer = 0
*[
head == tail, write_count == 0, (i:1..N) reader(i)?request ->
reader(i)!pass
read_count++
□
head == tail, write_count == 0, read_count == 0, (i:1..M) writer(i)?request ->
writer(i)!pass
write_count++
□
(head + 1) % N != tail, write_count + read_count != 0, (i:1..N) reader(i)?request ->
queue(head) = i
who(head) = 'r'
head = (head + 1) % N
□
(head + 1) % N != tail, write_count + read_count != 0, (i:1..M) writer(i)?request ->
queue(head) = i
who(head) = 'w'
head = (head + 1) % N
□
read_count == 1, (i:1..N) reader(i)?done ->
read_count--
*[
head != tail, write_count == 0, who[tail] == 'r' ->
reader(queue(tail))!pass
tail = (tail + 1) % N
read_count++
□
head != tail, write_count == 0, read_count == 0, who[tail] == 'w' ->
writer(queue(tail))!pass
tail = (tail + 1) % N
write_count++
]
□
read_count != 1, (i:1..N) reader(i)?done ->
read_count--
□
(i:1..M) writer(i)?done ->
write_count--
*[
head != tail, write_count == 0, who[tail] == 'r' ->
reader(queue(tail))!pass
tail = (tail + 1) % N
read_count++
□
head != tail, write_count == 0, read_count == 0, who[tail] == 'w' ->
writer(queue(tail))!pass
tail = (tail + 1) % N
write_count++
]
]
]
</syntaxhighlight>

== {{категорија|4. задатак|C-Linda}} ==
=== Поставка ===
Трајект за превоз возила превози возила са обале на обалу. Трајект поседује M трака од којих свака има N позиција које су линеарно постављене једна иза друге. Возило заузима једну позицију. Возило приликом доласка стаје у ред за случајно изабрану траку и чека на укрцавање. Нема могућности за престројавањем. Возила улазе у своју траку једно по једно по редоследу у којем чекају у траци, док на трајекту има места. Када је пун, трајект започиње превоз возила на другу обалу. На другој обали возила се искрцавају из своје траке у редоследу супротном од редоследа у којем су се укрцала у своју траку. Када се сва возила искрцају, празан трајект се враћа на почетну обалу. Користећи ''C-Linda'' написати програм који решава овај проблем.

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

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

КДП/Јануар 2023

2025-08-20T02:56:09Z

Andrija: Решење 3. задатка

{{tocright}}
'''Испит у јануарском испитном року 2023. године''' одржан је 18. јанаура. Поставка је доступна на [https://rti.etf.bg.ac.rs/rti/ir3kdp/rokovi/2223/IR3KDP_2023_jan.pdf страници предмета].

== {{категорија|1. задатак|Семафори}} ==
{{делимично решено}}
=== Поставка ===
Имплементирати и објасните основну разлику и разлоге за постојање те разлике између имплементација бафера коначног капацитета (<code>bounded buffer</code>) за случајеве 1 произвођач и 1 потрошач, као и M произвођача и N потрошача помоћу семафора. У складу са објашњењем, прикажите разлике и за случајеве M произвођача и 1 потрошач, као и 1 произвођач и N потрошача.
=== Решење ===

== {{категорија|2. задатак|Монитори}} ==
{{делимично решено}}
=== Поставка ===
Аутомобили који долазе са севера и југа морају да пређу реку преко неког старог моста (<code>Old Bridge problem</code>). На мосту постоји само једна возна трака, па сви аутомобили на мосту морају да се крећу у истом смеру. Због оптерећења моста које мост може да поднесе, број аутомобила који се налазе на мосту не сме да пређе K (K > 0). Написати монитор са <code>signal and continue</code> дисциплином који решава дати проблем.

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

== {{категорија|3. задатак|CSP}} ==
{{делимично решено}}
=== Поставка ===
Решити проблем читалаца и писаца користећи ''CSP''. Решење треба да обезбеди да када стигне захтев од писца за тражење дозволе за започињање писања не треба прихватати захтеве за започињање било од читалаца било од писаца док тај писац не заврши са писањем.

=== Решење ===
<syntaxhighlight lang="pascal">
[reader(i:1..N)::READER || writer(i:1..M)::WRITER || conductor::CONDUCTOR]

READER :: *[
conductor!request
conductor!pass
// reading
conductor!done
]

WRITER :: *[
conductor!request
conductor!pass
// writing
conductor!done
]

CONDUCTOR :: [
read_count: integer = 0
write_count: integer = 0
queue: (0..C) integer
who: (0..C) char
head: integer = 0
tail: integer = 0
*[
head == tail, write_count == 0, (i:1..N) reader(i)?request ->
reader(i)!pass
read_count++
□
head == tail, write_count == 0, read_count == 0, (i:1..M) writer(i)?request ->
writer(i)!pass
write_count++
□
(head + 1) % N != tail, write_count + read_count != 0, (i:1..N) reader(i)?request ->
queue(head) = i
who(head) = 'r'
head = (head + 1) % N
□
(head + 1) % N != tail, write_count + read_count != 0, (i:1..M) writer(i)?request ->
queue(head) = i
who(head) = 'w'
head = (head + 1) % N
□
read_count == 1, (i:1..N) reader(i)?done ->
read_count--
*[
head != tail, write_count == 0, who[tail] == 'r' ->
reader(queue(tail))!pass
tail = (tail + 1) % N
read_count++
□
head != tail, write_count == 0, read_count == 0, who[tail] == 'w' ->
writer(queue(tail))!pass
tail = (tail + 1) % N
write_count++
]
□
read_count != 1, (i:1..N) reader(i)?done ->
read_count--
□
(i:1..M) writer(i)?done ->
write_count--
*[
head != tail, write_count == 0, who[tail] == 'r' ->
reader(queue(tail))!pass
tail = (tail + 1) % N
read_count++
□
head != tail, write_count == 0, read_count == 0, who[tail] == 'w' ->
writer(queue(tail))!pass
tail = (tail + 1) % N
write_count++
]
]
]
</syntaxhighlight>

== {{категорија|4. задатак|C-Linda}} ==
=== Поставка ===
Трајект за превоз возила превози возила са обале на обалу. Трајект поседује M трака од којих свака има N позиција које су линеарно постављене једна иза друге. Возило заузима једну позицију. Возило приликом доласка стаје у ред за случајно изабрану траку и чека на укрцавање. Нема могућности за престројавањем. Возила улазе у своју траку једно по једно по редоследу у којем чекају у траци, док на трајекту има места. Када је пун, трајект започиње превоз возила на другу обалу. На другој обали возила се искрцавају из своје траке у редоследу супротном од редоследа у којем су се укрцала у своју траку. Када се сва возила искрцају, празан трајект се враћа на почетну обалу. Користећи ''C-Linda'' написати програм који решава овај проблем.

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

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

КДП/Фебруар 2020

2025-08-18T20:19:57Z

Andrija: Табулација

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

== {{категорија|1. задатак|Семафори}} ==
=== Поставка ===
Користећи расподељене бинарне семафоре решити проблем произвођача и потрошача (''Producer – Consumer Problem'').

=== Решење ===
Решење са бафером за M произвођача и N потрошача
<syntaxhighlight lang="cpp">
#include <semaphore>

class ProducerConsumer {

private:

const int CAPACITY=...;
int writeCursor=0;
int readCursor = 0;

int data[CAPACITY]; //Примера ради је узето да произвођач прави податке типа int

std::binary_semaphore space_available(CAPACITY);
std::binary_semaphore item_available(0);
std::binary_semaphore mutexProducer(1);
std::binary_semaphore mutexConsumer(1);

public:

void producer() {

spaceAvailable.acquire(); //у std::binary_semaphore ово је еквивалент операцији wait
mutexProducer.acquire();

data[writeCursor] = this.produce(); //Нека метода која би враћала неки број

writeCursor = (writeCursor + 1) % CAPACITY;

mutexProducer.release();
item_available.release(); //у std::binary_semaphore ово је еквивалент операцији signal

}

int consumer() {
item_available.acquire();
mutexConsumer.acquire()

int i = data[readCursor];

readCursor = (readCursor + 1) % CAPACITY;

item_available.release();
mutexConsumer.release()

return i;

}

}
</syntaxhighlight>

== {{категорија|2. задатак|Региони}} ==
=== Поставка ===
Постоји група од N филозофа који проводи свој живот тако што наизменично филозофирају, чекају на пиће, и пију (''The Drinking Philosophers Problem''). Филозофи су тако распоређени да је по једна флаша са пићем постављенa између суседних филозофа. У неком тренутку филозоф може да постане жедан. Жедном филозофу је потребно неколико суседних флаша да би направио коктел и почео да га пије. Избор пића зависи од тренутног расположења и може се разликовати од прилике до прилике. Када прикупи сва потребна пића филозоф започиње са њиховим испијањем које траје извесно време. Када се напије, филозоф враћа флаше да и други уживају, а он прелази на филозофирање. Написати програм који симулира понашање филозофа користећи условне критичне регионе.

=== Решење ===
<syntaxhighlight lang="cpp">
#include <queue>
#include <vector>

using namespace std;

const int N = 100;

struct Table {
int drinks[N] = {-1};
queue<int> drinkQueues[N];
};
Table table;

void philosophizing();
void drinking();
vector<int> getDrinkRound();

void philosopher(int id) {
while (true) {
vector<int> drinks = getDrinkRound();
region (table) {
for (int drink : drinks) {
if (table.drinks[drink] == -1) {
table.drinks[drink] = id;
} else {
table.drinkQueues[drink].push(id);
await (table.drinks[drink] == id);
}
}
}
drinking();
region (table) {
for (int drink : drinks) {
if (table.drinkQueues[drink].empty()) {
table.drinks[drink] = -1;
} else {
table.drinks[drink] = table.drinkQueues[drink].front();
table.drinkQueues[drink].pop();
}
}
}
philosophizing();
}
}
</syntaxhighlight>

== {{категорија|3. задатак|Филтерски_процеси}} ==
=== Поставка ===
Филтерски процеси имају један улаз и један излаз. Процеси имају само три локације. Направите проточну обраду (pipeline) од n ових филтерских процеса који проналазе медијану: до n улазних позитивних вредности (непарно) које се убацују на почетак проточне обраде, а завршавају се са EOS. На излаз проточне обраде се шаље медијана па EOS.

=== Решење ===
Пошто је у задатку речено да је дозвољено користити само три локације у процесу, једна ће бити одвојена за број који пристиже а друге две за локалне минимуме и максимуме. Памтиће се минимуми и максимуми јер је медијана непарног броја елемената управо она вредност која је тачно на средини листе у сортираном поретку. За разлику од других решења оваквог типа задатка на викију, ништа се не шаље на излаз осим EOS кад се исти прими јер је сва обрада за медијану већ разрешена унутар петље.
<syntaxhighlight lang="cpp">
void process() {

chan<int> in;
chan<int> out;
int input;
int mem[2];
while ((input = in.receive()) != EOS) {
if (mem[0] <= input && input <= mem[1]) {
out.send(input);
} else if (input < mem[0]) {
out.send(mem[0]);
mem[0] = input;
} else if (input > mem[1]) {
out.send(mem[1]);
mem[1] = input;
}
}
out.send(EOS);
}
</syntaxhighlight>

== {{категорија|4. задатак|C-Linda}} ==
{{делимично решено}}
=== Поставка ===
Посматра се берберница у којој за три различите столице раде три берберина (''The Hilzer's Barbershop problem''). Поред ове три столице у берберници се налази и чекаоница која прима 10 муштерија које могу да седе и 10 које могу да стоје, укупно 20. Када муштерија дође до бербернице уколико на шишање чека више од 20 муштерија онда одлази, а уколико берберница није пуна онда остаје. Уколико барем један берберин спава муштерија која дође на ред за шишање буди оног берберина који је најдуже спавао и седа у његову столицу. На место те муштерије која је устала седа муштерија која је најдуже стајала. Уколико су сви бербери заузети онда муштерија чека, и то ако има места за седење седа, а ако не онда стоји. Муштерије се опслужују у редоследу по коме су приспеле, и седају у истом том редоследу. Када берберин заврши са шишањем муштерија му плаћа и излази из бербернице. Берберин све време или спава или шиша или наплаћује. Користећи C-Linda написати процесе берберина и муштерија.

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

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

КДП/Септембар 2023

2025-08-18T20:17:24Z

Andrija: Недостајућа заграда

{{tocright}}


== {{категорија|1. задатак|Синхронизациони_алгоритми}} ==
=== Поставка ===
Написати и објаснити CLH алгоритам за критичну секцију (coarse grain). Реализовати (fine grain) верзију алгоритма уколико би на датом процесору постојала операција SWAP која би недељиво обављала замену вердности два операнда (SWAP(var1, var2): <temp=var1; var1=var2; var2=temp;>). Објаснити зашто је то правична критична секција.
=== Решење ===
CLH алгоритам процесе уланчава у уланчану листу по редоследу којим долазе. Самим тим та листа се понаша као ред и тиме је овај алгоритам правичан јер користи FIFO принцип.
''Coarse-grain'' решење:
<syntaxhighlight lang="cpp">
struct Node {
bool locked;
Node() {
locked = true;
}
};

Node* tail = nullptr;

void process() {
while (true) {
Node* new_node = new Node();
Node* prev;
< prev = tail; tail = new_node; >
< await(tail == nullptr || !prev->locked); >
/* критична секција */
new_node->locked=false;
/* некритична секција */
}
}
</syntaxhighlight>
''Fine-grain'' решење:
Пошто су prev и new_node локални показивачи, можемо да их усмеримо на новокреирани чвор. Затим се недељиво позива функција SWAP која ће недељиво заменити вредност prev и tail показивача.
<syntaxhighlight lang="cpp">
struct Node {
bool locked;
Node() {
locked = true;
}
};

Node* tail = nullptr;

void process() {
while (true) {
Node* new_node = new Node();
Node* prev = new_node;
SWAP(prev, tail);
while(prev!= nullptr && prev->locked) skip();
/* критична секција */
new_node->locked=false;
/* некритична секција */
}
}
</syntaxhighlight>

== {{категорија|2. задатак|Монитори}} ==
=== Поставка ===
Трајект за превоз аутомобила, камиона и аутобуса превози возила са обале на обалу. Трајект поседује N позиција које су линеарлно постављене једна иза друге. Камиона заузима три, аутовус две а аутомобил једну позицију. Возила чекају на трајект у реду и на њега улазе једно по једно по редоследу у ком чекају у реду, док на трајекту има места. Када нема места да се наредно возило у реду укрца и трајект није у потпуности попуњен, преко реда се укрцавају мања возила док се трајект не попуни у потпуности. Када је комплетно пун, трајект започиње превоз возила на другу обалу. На другој обали возила се искрцавају у редоследу супротном од оног у којем су се укрцала. Када се сва возила искрцају, празан трајект се враћа на почетну обалу. Написати монитор са ''signal and wait'' дисциплином који решава дати проблем.
=== Решење ===
{{делимично решено}}
== {{категорија|3. задатак|Филтерски_процеси}} ==
=== Поставка ===
Филтерски процеси имају један улаз и један излаз и раде следеће: примају позитивне вредности на улазу и прослеђују их на излаз ако су веће од запамћеног минимума процеса. Процеси имају само две локације, за сачувани минимум и за последњу примљену вредност. Када на улаз стигне EOS, избацују минималну вредност на излаз а затим EOS. Направите проточну обраду (''pipeline'') од n процеса који опадајуће соритају до n улазних позитивних вредности које се убацују на почетак проточне обраде а завршавају се са EOS.
=== Решење ===
<syntaxhighlight lang="cpp">
void process() {
chan<int> in;
chan<int> out;
int input;
int min;
while ((input = in.receive()) != EOS) {
if (input < min) {
out.send(min);
min = input;
} else out.send(input);
}
out.send(min);
out.send(EOS);
}
</syntaxhighlight>

== {{категорија|4. задатак|CSP}} ==
=== Поставка ===
Постоји N пчела и један гладан медвед (''The bear and honeybees''). Они користе заједничку кошницу. Кошница је иницијално празна и може да прими до N напрстака меда. Медвед спава док се кошница не напуни медом, када се напуни медом меда поједе сав мед након чега се враћа на спавање. Пчелице непрестано лете од света до света и сакупљају мед. Она пчела која је попунила кошницу буди медведа. Решити проблем користећи CSP.
=== Решење ===


<syntaxhighlight lang="pascal">
[Bee(i:1..N)::BEE || Bear::Bear || BeeHive::BeeHive]

BEE:: *[

flyAndCollect();
BeeHive!honneyCollected();
BeeHive?goBackToCollecting();
]

Bear:: * [

sleep();
BeeHive?bearEat();
BeeHive!allIsEaten();
BeeHive?okToSleep();

]

BeeHive:: [
size:integer; size:=0;
N:integer; N:=...;

*[
size < N; Bees(i)?honneyCollected() -> [
size := size + 1;

size==N -> [BeeHive!bearEat();]
[]
size < N -> [Bees(i)!goBackToCollecting();]

]

[]

size == N; BeeHive?allIsEaten() - > [
size = 0;
BeeHive!okToSleep();
]

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

КДП/Јун 2022

2024-08-28T00:44:33Z

Andrija: исправка грешке

{{tocright}}
'''Испит у јунском испитном року 2022. године''' одржан је 14. јуна. Поставка овог рока још увек није доступна са странице предмета.

== {{категорија|1. задатак|Синхронизациони_алгоритми}} ==
{{делимично решено}}
=== Поставка ===
Објасните шта је ''At-Most-Once-Property''. Објасните зашто, када је испуњена та особина, критична референца има особине атомске акције. Дати два примера у којима су по два процеса.

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

== {{категорија|2. задатак|Семафори}} ==
{{делимично решено}}
=== Поставка ===
Постоје три особе међу којима треба изабрати једну (''The Odd Person Wins Game''). Свака од тих особа поседује новчић који има две стране. Избор особе се одиграва тако што свака особа независно баца свој новчић. Уколико постоји особа којој је новчић пао на другу страну у односу на преостале особе, онда се та особа изабира. Уколико све особе имају исто постављен новчић, поступак се понавља све док се не изабере једна. Особе након сваког бацања морају да знају да ли су изабране или не или се поступак понавља. Користећи семафоре написати програм који описује понашање особе. Ниједној особи не треба давати предност на основу њиховог идентификатора.

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

== {{категорија|3. задатак|Монитори}} ==
=== Поставка ===
Монитор треба да регулише распоред уласка пацијената на преглед код једног лекара. Сваки регуларно заказани пацијент је пре приступања том монитору добио један од 12 хронолошки поређаних полусатних интервала за тај дан (прављење распореда није део задатка). Пацијент када дође на преглед (не мора да буде тачан) позива мониторску процедуру <code>želim_da_se_pregledam</code> и том приликом доставља ID и почетак полусатног интервала у коме је њему заказан преглед. Ако је лекар заузет, пацијенти на чекању ће се поређати на основу хронолошког редоследа у распореду за тај дан. Лекар позива мониторску процедуру <code>sledeći</code>, која враћа идентификатор следећег пацијента, када жели да прегледа следећег пацијента. Ако нема пацијената у том случају, лекар се поствља у стање чекања из кога излази када наиђе први пацијент. Написати овакав монитор користећи дисциплину ''Signal and Wait'' и условне променљиве код којих нема приоритетних редова чекања. Монитор не треба да садржи синхронизацију везану за крај прегледа.

=== Решење ===
<syntaxhighlight lang="java">
// pretpostavka da je ID 0-11
class Monitor {
private Condition[] awaitPatient[12], awaitDoctor;
private boolean[] patientChecked[12]; // da li je pacijent pregledan, potreban zbog signal&wait
private PriorityQueue<<int,int>> pq; // prioritetni red slot, ID, sortiran po slotu

public synchronized void zelim_da_se_pregledam(int ID, int slot) {
pq.add(slot,ID);
awaitDoctor.signal();
// potrebno jer signal&wait predaje kontrolu pa je pacijent u medjuvremenu mozda pregledan
if (patientChecked[ID] == false) awaitPatient[ID].wait();
}

public synchronized int sledeci() {
if (pq.size() == 0) awaitDoctor.wait();
int id = pq.pop().first;
pq.remove();
patientChecked[id] = true;
awaitPatient[id].signal();
return id;
}
}
</syntaxhighlight>

== {{категорија|4. задатак|Региони}} ==
=== Поставка ===
Трајект за превоз аутомобила, камиона и аутобуса превози возила са обале на обалу. Трајект поседује N позиција које су линеарно постављене једна иза друге. Камион заузима три, аутобус две, а аутомобил једну позицију. Возила чекају на трајект у реду и на њега улазе једно по једно по редоследу у којем чекају у реду, док на трајекту има места. Када наредно возило у реду за трајект нема места да се укрца или када је трајект пун, трајект започиње превоз возила на другу обалу. На другој обали возила се искрцавају у редоследу супротном од редоследа у којем су се укрцала. Када се сва возила искрцају, празан трајект се враћа на почетну обалу. Користећи регионе написати програм који решава овај проблем.

=== Решење ===
<syntaxhighlight lang="cpp">
struct Trajekt {
int cap = N;
int curr = 0, next = 0, ticketIn = 0, ticketOut = 0;
bool ukrcavanje = false, iskrcavanje = false
}

Trajekt t;

void vozilo(int space) {
int myTicketIn, myTicketOut;
region(t) {
myTicketIn = t.ticketIn++;
await (t.ukrcavanje && t.ticketIn == myTicketIn);
if (t.cap - t.curr < space) {
// ukoliko nema mesta za mene, posalji trajekt pa sacekaj da se vrati
t.ukrcavanje = false;
await (t.ukrcavanje);
}
t.curr += space;
myTicketOut = ++t.ticketOut;
t.next++;
if (t.curr == t.cap)
t.ukrcavanje = false;
}
// prevozimo se
region(t) {
await (t.iskrcavanje && myTicketOut == t.ticketOut);
if (--t.ticketOut == 0)
// ukoliko sam poslednji, posalji trajekt nazad
t.iskrcavanje = false
}
}

void trajekt() {
while (1) {
region(t) {
t.ukrcavanje = true
await (!t.ukrcavanje);
}
preveziVozila();
region(t) {
t.iskrcavanje = true;
await (!t.iskrcavanje);
}
vratiSeNazad();
}
}
</syntaxhighlight>

== {{категорија|5. задатак|Размена_порука}} ==
=== Поставка ===
Користећи синхрону размену порука написати дистрибуирано решење за проблем филозофа који ручавају (''The Dining Philosophers Problem''). Код дистрибуираног решења процеси филозофи комуницирају само са процесима виљушкама и процеси виљушке комуницирају само са процесима филозофима.

=== Решење ===
<syntaxhighlight lang="cpp">
void philosopher(int ID, chan<string> release, chan<char> forkL, chan<char> forkR) {
while (true) {
// Филозофирамо
if (ID % 2 == 0) {
forkL.send('R');
forkR.send('L');
} else {
forkR.send('L');
forkL.send('R');
}
// Једемо
release.receive();
release.receive();
}
}

void fork(chan<char> acquire, chan<string> philL, chan<string> philR) {
while (true) {
char dir = acquire.receive();
if (dir == 'L') {
philL.send("release");
} else {
philR.send("release");
}
}
}
</syntaxhighlight>

== {{категорија|6. задатак|C-Linda}} ==
=== Поставка ===
Постоји P произвођача и C потрошача који деле заједнички бафер капацитета B (''Atomic broadcast problem''). Произвођачи генеришу производ по производ на које чекају свих C потрошача. Сваки потрошач мора да прими производе у тачно оном редоследу у коме су произведени, мада различити потрошачи могу у исто време да узимају различите производе. Решити проблем користећи ''C-Linda'', тако да се ни у ком тренутку у заједничком простору не нађе више од B производа.

=== Решење ===
Тагови коришћени у овој имплементацији су:
* <code>buffer empty</code>: постоји места да произвођач убацује у бафер
* <code>buffer full</code>: постоје производи у баферу које потрошачи могу да читају
* <code>product</code>: производ са одређеним индексом у низу
* <code>size</code>: величина бафера
* <code>producer index</code>: индекс у баферу до ког су произвођачи стигли са попуњавањем
* <code>consumer count</code>: број потрошача који је преостао да прочита производ на одређеном индексу
<syntaxhighlight lang="cpp">
const int P = 100;
const int C = 100;
const int B = 100;

struct Product {};
Product produce();
void consume(Product p);

int producer() {
while (true) {
Product p = produce();
in("buffer empty");
int index;
in("producer index", &index);
out("product", index, p);
out("consumer count", index, C);
out("producer index", (index + 1) % B);
int size;
in("size", &size);
if (size == 0) {
out("buffer full");
}
out("size", ++size);
if (size < B) {
out("buffer empty");
}
}
}

void consumer() {
int index = 0;
while (true) {
in("buffer full");
Product p;
int count;
in("consumer count", index, &count);
if (count == 1) {
in("product", index, &p);
int size;
in("size", &size);
if (size == B) {
out("buffer empty");
}
out("size", --size);
if (size > 0) {
out("buffer full");
}
} else {
rd("product", index, &p);
out("consumer count", index, count-1);
out("buffer full");
}
index = (index + 1) % B;
consume(p);
}
}

void initialize() {
out("buffer empty");
out("size", 0);
out("producer index", 0);
}
</syntaxhighlight>

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