АСП1/Јул 2018 - Историја измена

KockaAdmiralac: Hmm

2024-09-13T00:15:30Z

Hmm

← Старија измена		Верзија на датум 13. септембар 2024. у 02:15
Ред 86:		Ред 86:
	return path		return path
	</nowiki>}}		</nowiki>}}

	{{Милокод\|<nowiki>		{{Милокод\|<nowiki>
	CHILD NODES(V, n, k)		CHILD NODES(V, n, k)
Ред 238:		Ред 239:
	return node		return node
	</nowiki>}}		</nowiki>}}

	{{Милокод\|<nowiki>		{{Милокод\|<nowiki>
	LIST INSERT(before, node)		LIST INSERT(before, node)
Ред 247:		Ред 249:
	return node		return node
	</nowiki>}}		</nowiki>}}

	{{Милокод\|<nowiki>		{{Милокод\|<nowiki>
	REARRANGE LIST(head)		REARRANGE LIST(head)
Ред 302:		Ред 305:
	return node		return node
	</nowiki>}}		</nowiki>}}

	{{Милокод\|<nowiki>		{{Милокод\|<nowiki>
	GASOLINE TRAVEL(G, src, dst)		GASOLINE TRAVEL(G, src, dst)

KockaBot: Замена начина истицања милокода.

2024-09-13T00:08:24Z

Замена начина истицања милокода.

← Старија измена		Верзија на датум 13. септембар 2024. у 02:08
Ред 68:		Ред 68:

	U pseudokodu ispod pretpostavlja se da nam put od čvora ka korenu kao i deca trenutnog čvora trebaju vraćeni kao ulančane liste.		U pseudokodu ispod pretpostavlja se da nam put od čvora ka korenu kao i deca trenutnog čvora trebaju vraćeni kao ulančane liste.
	<~~syntaxhighlight lang="milo"~~>		{{Милокод\|<nowiki>
	NODE TO ROOT(V, n, k)		NODE TO ROOT(V, n, k)
	t = 0		t = 0
Ред 85:		Ред 85:
	end_while		end_while
	return path		return path
	</~~syntaxhighlight~~>		</nowiki>}}
	<~~syntaxhighlight lang="milo"~~>		{{Милокод\|<nowiki>
	CHILD NODES(V, n, k)		CHILD NODES(V, n, k)
	children = nil		children = nil
Ред 99:		Ред 99:
	end_if		end_if
	return children		return children
	</~~syntaxhighlight~~>		</nowiki>}}

	== 4. zadatak ==		== 4. zadatak ==
Ред 121:		Ред 121:
	=== Rešenje ===		=== Rešenje ===
	Ovaj skup stranica se može modelovati netežinskim usmerenim grafom gde čvorovi predstavljaju stranice a grana od strane A do strane B znači da postoji veza na strani A do strane B.		Ovaj skup stranica se može modelovati netežinskim usmerenim grafom gde čvorovi predstavljaju stranice a grana od strane A do strane B znači da postoji veza na strani A do strane B.
	<~~syntaxhighlight lang="milo"~~>		{{Милокод\|<nowiki>
	AVG CLICKS NUM(G)		AVG CLICKS NUM(G)
	for i = 1 to n do		for i = 1 to n do
Ред 149:		Ред 149:
	end_for		end_for
	return sum / (n * (n - 1))		return sum / (n * (n - 1))
	</~~syntaxhighlight~~>		</nowiki>}}

	== 6. zadatak ==		== 6. zadatak ==
Ред 232:		Ред 232:

	=== Rešenje ===		=== Rešenje ===
	<~~syntaxhighlight lang="milo"~~>		{{Милокод\|<nowiki>
	LIST REMOVE(node)		LIST REMOVE(node)
	next(prev(node)) = next(node)		next(prev(node)) = next(node)
	prev(next(node)) = prev(node)		prev(next(node)) = prev(node)
	return node		return node
	</~~syntaxhighlight~~>		</nowiki>}}
	<~~syntaxhighlight lang="milo"~~>		{{Милокод\|<nowiki>
	LIST INSERT(before, node)		LIST INSERT(before, node)
	t = prev(before)		t = prev(before)
Ред 246:		Ред 246:
	next(node) = before		next(node) = before
	return node		return node
	</~~syntaxhighlight~~>		</nowiki>}}
	<~~syntaxhighlight lang="milo"~~>		{{Милокод\|<nowiki>
	REARRANGE LIST(head)		REARRANGE LIST(head)
	if head = nil then		if head = nil then
Ред 269:		Ред 269:
	i = i + 1		i = i + 1
	end_loop		end_loop
	</~~syntaxhighlight~~>		</nowiki>}}

	== 8. zadatak ==		== 8. zadatak ==
Ред 294:		Ред 294:

	=== Rešenje ===		=== Rešenje ===
	<~~syntaxhighlight lang="milo"~~>		{{Милокод\|<nowiki>
	GETNODE(i, j)		GETNODE(i, j)
	ALLOCATE(node)		ALLOCATE(node)
Ред 301:		Ред 301:
	next(node) = nil		next(node) = nil
	return node		return node
	</~~syntaxhighlight~~>		</nowiki>}}
	<~~syntaxhighlight lang="milo"~~>		{{Милокод\|<nowiki>
	GASOLINE TRAVEL(G, src, dst)		GASOLINE TRAVEL(G, src, dst)
	branches = nil		branches = nil
Ред 336:		Ред 336:
	S = S + {to(min_branch)}		S = S + {to(min_branch)}
	end_loop		end_loop
	</~~syntaxhighlight~~>		</nowiki>}}

	== 10. zadatak ==		== 10. zadatak ==

KockaAdmiralac: PNG u SVG

2022-02-13T21:18:59Z

PNG u SVG

← Старија измена		Верзија на датум 13. фебруар 2022. у 23:18
Ред 153:		Ред 153:
	== 6. zadatak ==		== 6. zadatak ==
	=== Postavka ===		=== Postavka ===
	[[{{ns:6}}:ASP1 jul 2018 zadatak 6 graf.~~png~~\|thumb\|Graf iz postavke zadatka.]]		[[{{ns:6}}:ASP1 jul 2018 zadatak 6 graf.svg\|thumb\|Graf iz postavke zadatka.]]
	Primenom algoritma za određivanje kritičnih puteva u grafu odrediti kritične puteve u grafu sa slike kao i dozvoljena kašnjenja svih aktivnosti u grafu.		Primenom algoritma za određivanje kritičnih puteva u grafu odrediti kritične puteve u grafu sa slike kao i dozvoljena kašnjenja svih aktivnosti u grafu.

KockaAdmiralac: Prebacivanje na jednostavno isticanje sintakse

2020-08-28T09:41:11Z

Prebacivanje na jednostavno isticanje sintakse

Прикажи измене

KockaAdmiralac: Kategorizacija

2020-07-27T09:58:24Z

Kategorizacija

← Старија измена		Верзија на датум 27. јул 2020. у 11:58
Ред 369:		Ред 369:

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

KockaAdmiralac: Ispravka

2020-06-11T21:59:31Z

Ispravka

← Старија измена		Верзија на датум 11. јун 2020. у 23:59
Ред 186:		Ред 186:
	\|-		\|-
	\| A-B		\| A-B
	\| 2		\| 3
	\|-		\|-
	\| A-E		\| A-E
Ред 195:		Ред 195:
	\|-		\|-
	\| D-B		\| D-B
	\| 0		\| 1
	\|-		\|-
	\| D-C		\| D-C
Ред 216:		Ред 216:
	\|-		\|-
	\| E-K		\| E-K
	\| 0		\| 2
	\|-		\|-
	\| K-V		\| K-V

KockaAdmiralac: Da

2020-04-12T01:54:32Z

Нова страница

{{tocright}}
[https://rti.etf.bg.ac.rs/rti/ri3sp/rokovi/13S111ASP1_jul_2018.pdf Zadaci]

== 1. zadatak ==
=== Postavka ===
Odrediti binarno stablo čijim eksternim čvorovima su pridružene težine: 3, 6, 3, 1, za koje je težinska eksterna dužina puta najmanja i izračunati tu dužinu.

=== Rešenje ===
13
/ \
6 7
/ \
3 4
/ \
3 1
Eksterna dužina puta: <math>1 \cdot 6 + 2 \cdot 3 + 3 \cdot 1 + 3 \cdot 3 = 6 + 6 + 3 + 9 = 24</math>

== 2. zadatak ==
=== Postavka ===
Dat je aritmetički izraz u infiksnoj notaciji: 3+7+4*(2+1). Pretvoriti dati izraz u postfiksni izraz, a zatim prikazati stanje steka po koracima tokom izračunavanja vrednosti dobijenog postfiksnog izraza. Smatrati da pokazivač vrha steka pokazuje na poslednju zauzetu lokaciju i obeležiti ga na slici.

=== Rešenje ===
Postfiksni izraz: '''3 7 + 4 2 1 + * +'''
{| class="wikitable"
! colspan="2" | 3
! colspan="2" | 7
! colspan="2" | +
! colspan="2" | 4
! colspan="2" | 2
! colspan="2" | 1
! colspan="2" | +
! colspan="2" | *
! colspan="2" | +
|-
| || -- || || -- || || -- || || -- || || -- || || -- || || -- || || -- || || --
|-
| || -- || || -- || || -- || || -- || || -- || || -- || || -- || || -- || || --
|-
| || -- || || -- || || -- || || -- || || -- || || -- || || -- || || -- || || --
|-
| || -- || || -- || || -- || || -- || || -- || → || 1 || || -- || || -- || || --
|-
| || -- || || -- || || -- || || -- || → || 2 || || 2 || → || 3 || || -- || || --
|-
| || -- || → || 7 || || -- || → || 4 || || 4 || || 4 || || 4 || → || 12 || || --
|-
| → || 3 || || 3 || → || 10 || || 10 || || 10 || || 10 || || 10 || || 10 || → || 22
|}

== 3. zadatak ==
=== Postavka ===
Posmatra se vektorska implementacija kompletnog ili skoro kompletnog stabla reda 3 u vidu vektora ''V[1:n]''.
<div class="abc-list">
# Prikazati stablo čija je vektorska reprezentacija data na slici.
# Napisati u pseudokodu funkciju koja nalazi put od čvora sa indeksom ''k'' ka korenu i funkciju koja nalazi sve sinove čvora sa indeksom ''k''.
</div>
{| class="wikitable"
|+ Slika uz deo pod a.
| 1 || 2 || 3 || 4 || 5 || 6 || 7 || 8 || 9 || 10 || 11 || 12 || 13
|}

=== Rešenje ===
1
/ | \
2 3 4
/ | \ / | \ / | \
5 6 7 8 9 10 11 12 13

U pseudokodu ispod pretpostavlja se da nam put od čvora ka korenu kao i deca trenutnog čvora trebaju vraćeni kao ulančane liste.
<u>NODE TO ROOT(''V'', ''n'', ''k'')</u>
''t'' = 0
''path'' = nil
''p'' = ''k''
'''while''' ''p'' ≠ 0 '''do'''
LIST_INSERT(''path'', ''v''[''p''])
''t'' = ''p'' mod 3
'''if''' t = 0 '''then'''
''p'' = ''p'' / 3
'''else if''' ''t'' = 1 '''then'''
''p'' = (''p'' - 1) / 3
'''else'''
''p'' = (''p'' + 1) / 3
'''end_if'''
'''end_while'''
'''return''' ''path''

<u>CHILD NODES(''V'', ''n'', ''k'')</u>
''children'' = nil
'''if''' 3 * ''k'' - 1 ≤ ''n'' '''then'''
LIST_INSERT(''children'', ''v''[3 * ''k'' - 1])
'''end_if'''
'''if''' 3 * ''k'' ≤ ''n'' '''then'''
LIST_INSERT(''children'', ''v''[3 * ''k''])
'''end_if'''
'''if''' 3 * ''k'' + 1 ≤ ''n'' '''then'''
LIST_INSERT(''children'', ''v''[3 * ''k'' + 1])
'''end_if'''
'''return''' ''children''

== 4. zadatak ==
=== Postavka ===
Neka je data opšta kvadratna matrica A[''l:u'', ''l:u''] koja sadrži elemente samo ispod glavne dijagonale, uključujući i tu dijagonalu. Formalno definisati i kratko objasniti adresnu funkciju za pristup proizvoljnom elementu A[''i'', ''j''], ukoliko se matrica linearizuje po vrstama.

=== Rešenje ===
<math>A_{ij} = A_{ll} + \left(\frac{(i-l)(i-l+1)}{2} + j - l\right) \cdot S</math>
* <math>A_{ll}</math> je adresa početnog elementa matrice.
* <math>\frac{(i-l)(i-l+1)}{2}</math> je broj elemenata u redovima iznad elementa kojeg tražimo. <math>i-l</math> je broj redova iznad trenutnog reda i stoga broj elemenata u redu iznad našeg, a pošto broj elemenata opada sa brojem reda ovaj zbir dobijamo kao Gausov zbir.
* <math>j-l</math> je broj elemenata levo od našeg trenutnog elementa.

== 5. zadatak ==
=== Postavka ===
Neka se posmatra jedan skup veb stranica u okviru lokalnog intraneta jedne kompanije. Svaka stranica sadrži određeni broj hiperlinkova koji vode ka drugim stranicama u okviru intraneta.
<div class="abc-list">
# Opisati na koji način se ovaj skup stranica može modelovati grafom. Komentarisati tip i usmerenost grafa.
# Napisati u pseudokodu iterativnu funkciju koja određuje prosečan broj klikova potreban da se sa neke veb stranice stigne do neke druge veb stranice u okviru kompanijskog intraneta. Prosek računati na nivou svih mogućih parova stranica.
</div>

=== Rešenje ===
Ovaj skup stranica se može modelovati netežinskim usmerenim grafom gde čvorovi predstavljaju stranice a grana od strane A do strane B znači da postoji veza na strani A do strane B.
<u>AVG CLICKS NUM(''G'')</u>
'''for''' ''i'' = 1 '''to''' ''n'' '''do'''
'''for''' ''i'' = 1 '''to''' ''n'' '''do'''
'''if''' (''i'', ''j'') ∈ ''E'' '''then'''
''d''[''i'', ''j''] = 1
'''else'''
''d''[''i'', ''j''] = ∞
'''end_if'''
'''end_for'''
'''end_for'''
'''for''' ''k'' = 1 '''to''' ''n'' '''do'''
'''for''' ''i'' = 1 '''to''' ''n'' '''do'''
'''for''' ''j'' = 1 '''to''' ''n'' '''do'''
'''if''' ''d''[''i'', ''k''] + ''d''[''k'', ''j''] < ''d''[''i'', ''j''] '''then'''
''d''[''i'', ''j''] = ''d''[''i'', ''k''] + ''d''[''k'', ''j'']
'''end_if'''
'''end_for'''
'''end_for'''
'''end_for'''
'''for''' ''i'' = 1 '''to''' ''n'' '''do'''
'''for''' ''j'' = 1 '''to''' ''n'' '''do'''
'''if''' ''i'' ≠ ''j'' '''then'''
''sum'' = ''sum'' + ''d''[''i'', ''j'']
'''end_if'''
'''end_for'''
'''end_for'''
'''return''' ''sum'' / (''n'' * (''n'' - 1))

== 6. zadatak ==
=== Postavka ===
[[{{ns:6}}:ASP1 jul 2018 zadatak 6 graf.png|thumb|Graf iz postavke zadatka.]]
Primenom algoritma za određivanje kritičnih puteva u grafu odrediti kritične puteve u grafu sa slike kao i dozvoljena kašnjenja svih aktivnosti u grafu.

=== Rešenje ===
Kritični putevi: '''AEDCM''' i '''AEDVM'''.
{| class="wikitable"
! Čvor
! EST
|-
| A
| 0
|-
| B
| 6
|-
| C
| 10
|-
| D
| 5
|-
| E
| 2
|-
| K
| 6
|-
| M
| 13
|-
| V
| 11
|}
{| class="wikitable"
! Aktivnost
! I
|-
| A-B
| 2
|-
| A-E
| 0
|-
| E-D
| 0
|-
| D-B
| 0
|-
| D-C
| 0
|-
| B-C
| 1
|-
| C-M
| 0
|-
| D-V
| 0
|-
| V-M
| 0
|-
| E-V
| 2
|-
| E-K
| 0
|-
| K-V
| 2
|}

== 7. zadatak ==
=== Postavka ===
Data je dvostruko ulančana lista. Implementirati funkciju REARRANGE_LIST koja prosleđenu listu preuređuje tako da se svi elementi sa neparnih pozicija u originalnom poretku nađu pre svih elemenata sa parnih pozicija u originalnom poretku.

=== Rešenje ===
<u>LIST REMOVE(''node'')</u>
''next''(''prev''(''node'')) = ''next''(''node'')
''prev''(''next''(''node'')) = ''prev''(''node'')
'''return''' ''node''

<u>LIST INSERT(''before'', ''node'')</u>
''t'' = ''prev''(''before'')
''prev''(''before'') = ''node''
''next''(''t'') = ''node''
''prev''(''node'') = ''t''
''next''(''node'') = ''before''
'''return''' ''node''

<u>REARRANGE LIST(''head'')</u>
'''if''' ''head'' = nil '''then'''
'''return'''
'''end_if'''
''p'' = ''head''
''n'' = nil
'''loop'''
'''for''' ''k'' = 1 '''to''' ''i'' + 1 '''do'''
''p'' = ''next''(''p'')
'''if''' ''p'' = nil '''then'''
'''return'''
'''end_if'''
'''end_for'''
''n'' = LIST_REMOVE(''p'')
'''for''' ''k'' = 1 '''to''' ''i'' '''do'''
''p'' = ''prev''(''p'')
'''end_for'''
LIST_INSERT(''p'', ''n'')
''p'' = ''n''
''i'' = ''i'' + 1
'''end_loop'''

== 8. zadatak ==
=== Postavka ===
Prikazati postupak kodiranja poruke ADBECDAADBE primenom dinamičkog ''Huffman'' algoritma.

=== Rešenje ===
Krajnje ''Huffman''-ovo stablo:
11
/ \
5 6
/ \ / \
B 3 D A
2 / \ 3 3
1 E
/ \ 2
NYT C
0 1
Krajnja poruka: '''A 0D 00B 100E 000C 00 00 01 10 00 011'''

== 9. zadatak ==
=== Postavka ===
Posmatra se neusmeren težinski graf predstavljen matricom susednosti, čiji čvorovi predstavljaju gradove u kojima se nalaze benzinske pumpe na kojima se može dopuniti rezervoar, a težine grana predstavljaju koliko litara goriva se potroši u putu između povezanih gradova. Perica kreće iz grada src i želi da stigne u grad dst. Na efikasan način odrediti minimalni kapacitet rezervoara Peričinog automobila da bi on mogao da uspešno da završi svoj put.

=== Rešenje ===
<u>GETNODE(''i'', ''j'')</u>
ALLOCATE(''node'')
''from''(''node'') = ''i''
''to''(''node'') = ''j''
''next''(''node'') = nil
'''return''' ''node''

<u>GASOLINE TRAVEL(''G'', ''src'', ''dst'')</u>
''branches'' = nil
''t'' = nil
'''for''' ''i'' = 1 '''to''' ''n'' '''do'''
'''for''' ''j'' = 1 '''to''' ''n'' '''do'''
'''if''' ''e''[''i'', ''j''] = 1 '''then'''
'''if''' ''branches'' = nil '''then'''
''branches'' = GETNODE(''i'', ''j'')
'''else'''
''t'' = ''next''(''branches'')
''next''(''branches'') = GETNODE(''i'', ''j'')
''next''(''next''(''branches'')) = ''t''
'''end_if'''
'''end_if'''
'''end_for'''
'''end_for'''
''S'' = {''src''}
'''loop'''
''t'' = ''branches''
''min_branch'' = nil
'''while''' ''t'' ≠ nil '''do'''
'''if''' (''from''(''t'') ∈ ''S'') and (''to''(''t'') ∈ (''V'' - ''S'') '''then'''
'''if''' (''min_branch'' = nil) or (''w''(''from''(''t''), ''to''(''t'')) < ''w''(''from''(''min_branch''), ''to''(''min_branch''))) '''then'''
''min_branch'' = ''t''
'''end_if'''
'''end_if'''
''t'' = ''next''(''t'')
'''end_while'''
'''if''' ''to''(''min_branch'') = ''dst'' '''then'''
'''return''' ''last_min''
'''end_if'''
''S'' = ''S'' + {''to''(''min_branch'')}
'''end_loop'''

== 10. zadatak ==
=== Postavka ===
Prilikom obilaska nekog grafa može se dobiti '''stablo obilaska'''.
<div class="abc-list">
# Definisati ovo stablo.
# Prilikom obilaska usmerenog grafa po dubini dobijena su početna (''t1'') i završna vremena (''t2'') čvorova kao u priloženoj tabeli. Rekonstruisati stablo obilaska i precizno objasniti postupak rekonstrukcije.
</div>
{| class="wikitable"
!
! ''t1''
! ''t2''
|-
| A || 3 || 4
|-
| B || 5 || 10
|-
| C || 11 || 12
|-
| D || 14 || 15
|-
| E || 8 || 9
|-
| F || 2 || 13
|-
| G || 1 || 16
|-
| H || 6 || 7
|}

=== Rešenje ===
<div class="abc-list">
# Stablo obilaska je aciklični neusmereni netežinski graf čije grane označavaju iz kog je čvora posećen koji čvor prilikom obilaska grafa, a čvorovi su isti kao u grafu koji se obilazi.
# Postupak ide tako što udemo predom kroz brojeve <math>t = 1 ... 2n</math> i čuvamo jedan imaginarni pokazivač koji je u <math>t = 1</math> postavljam na koren. Ako <math>t</math> označava početno vreme nekog čvora, na trenutni pokazivač dodajemo dete sa vrednošću tog čvora i prebacujemo pokazivač na to dete. Ako <math>t</math> označava krajnje vreme nekog čvora, prebacujemo pokazivač na njegovog roditelja (ako je pokazivač na korenu, završavamo).
</div>
G
/ \
F D
/ | \
A B C
/ \
H E

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