АСП1/К3 Јул 2021 — разлика између измена
< АСП1
Пређи на навигацију
Пређи на претрагу
м (Замена начина истицања милокода.) |
м (Hmm) |
||
| Ред 37: | Ред 37: | ||
Data je mreža puteva između gradova predstavljena matričnom reprezentacijom grafa. Putarina između bilo koja dva povezana grada iznosi 1. Međutim pri ulasku u svaki grad, postoji određena taksa koju je potrebno platiti. Cena takse se definiše na nivou grada. | Data je mreža puteva između gradova predstavljena matričnom reprezentacijom grafa. Putarina između bilo koja dva povezana grada iznosi 1. Međutim pri ulasku u svaki grad, postoji određena taksa koju je potrebno platiti. Cena takse se definiše na nivou grada. | ||
<div class="abc-list"> | <div class="abc-list"> | ||
# Mika voli da putuje i nalazi se u gradu X. Izračunati za svaki grad koliko je novca Miki potrebno da ga obiđe ukoliko uvek kreće iz mesta X. Implementirati funkciju koja efikasno računa minimalnu potrebnu količinu novca za posetu svakom gradu. Funkciji su prosleđeni broj gradova, graf, cene taksi za svaki grad (niz prirodnih brojeva) i indeks početnog grada. | # Mika voli da putuje i nalazi se u gradu X. Izračunati za svaki grad koliko je novca Miki potrebno da ga obiđe ukoliko uvek kreće iz mesta X. Implementirati funkciju koja efikasno računa minimalnu potrebnu količinu novca za posetu svakom gradu. Funkciji su prosleđeni broj gradova, graf, cene taksi za svaki grad (niz prirodnih brojeva) i indeks početnog grada. | ||
# Jedan od gradova je zbog nedostatka turista uveo da turisti pri ulasku ne plaćaju taksu, već da dobiju beneficiju u vidu novca. Ukratko prokomentarisati kako ova modifikacija utiče na predloženi algoritam pod a). Da li bi se u tom slučaju koristio isti algoritam ili bi bio pogodniji neki drugi (ako da, koji)? | # Jedan od gradova je zbog nedostatka turista uveo da turisti pri ulasku ne plaćaju taksu, već da dobiju beneficiju u vidu novca. Ukratko prokomentarisati kako ova modifikacija utiče na predloženi algoritam pod a). Da li bi se u tom slučaju koristio isti algoritam ili bi bio pogodniji neki drugi (ako da, koji)? | ||
</div> | </div> | ||
=== Rešenje === | === Rešenje === | ||
{{Милокод|<nowiki>CALC EXPENSES(N, G, taxes, X)</nowiki>}} | |||
== 3. zadatak == | == 3. zadatak == | ||
| Ред 61: | Ред 62: | ||
# Definisati početno i završno vreme prilikom obilaska grafa po dubini. Koja je njegova uloga? | # Definisati početno i završno vreme prilikom obilaska grafa po dubini. Koja je njegova uloga? | ||
# Napisati u pseudokodu implementaciju funkcije koja na osnovu zapisanih početnih i završnih vremena obilaska svakog čvora obilaskom po dubini određuje da li se čvor X nalazi u podstablu čvora Y u stablu obilaska. | # Napisati u pseudokodu implementaciju funkcije koja na osnovu zapisanih početnih i završnih vremena obilaska svakog čvora obilaskom po dubini određuje da li se čvor X nalazi u podstablu čvora Y u stablu obilaska. | ||
</div> | </div> | ||
{{Милокод|<nowiki>IS SUCCESSOR(start_time, finish_time, x, y)</nowiki>}} | |||
=== Rešenje === | === Rešenje === | ||
Тренутна верзија на датум 13. септембар 2024. у 01:03
- Овај рок није решен. Помозите SI Wiki тако што ћете га решити.
Jul 2021. godine nema postavku dostupnu sa stranice predmeta.
1. zadatak
Postavka
Posmatra se plan za realizaciju jednog softverskog projekta dat tabelom. Faza S je početna.
| A | S – 7 dana |
| B | G – 6 dana, R – 2 dana |
| F | L – 11 dana |
| L | S – 7 dana |
| G | L – 3 dana, A – 4 dana |
| M | F – 5 dana, B – 3 dana |
| R | A – 5 dana |
| T | B – 7 dana, M – 2 dana |
- (5p) Predstaviti projekat grafom.
- (10p) Ako faza B predstavlja beta fazu projekta i želimo da znamo da ni ona neće kasniti naći kritični put (ili puteve) i kritične aktivnosti za beta fazu.
- (10p) Naći kritični put (ili puteve) za uspešnu realizaciju ovog projekta kao i kritične aktivnosti.
Rešenje
2. zadatak
Postavka
Data je mreža puteva između gradova predstavljena matričnom reprezentacijom grafa. Putarina između bilo koja dva povezana grada iznosi 1. Međutim pri ulasku u svaki grad, postoji određena taksa koju je potrebno platiti. Cena takse se definiše na nivou grada.
- Mika voli da putuje i nalazi se u gradu X. Izračunati za svaki grad koliko je novca Miki potrebno da ga obiđe ukoliko uvek kreće iz mesta X. Implementirati funkciju koja efikasno računa minimalnu potrebnu količinu novca za posetu svakom gradu. Funkciji su prosleđeni broj gradova, graf, cene taksi za svaki grad (niz prirodnih brojeva) i indeks početnog grada.
- Jedan od gradova je zbog nedostatka turista uveo da turisti pri ulasku ne plaćaju taksu, već da dobiju beneficiju u vidu novca. Ukratko prokomentarisati kako ova modifikacija utiče na predloženi algoritam pod a). Da li bi se u tom slučaju koristio isti algoritam ili bi bio pogodniji neki drugi (ako da, koji)?
Rešenje
CALC EXPENSES(N, G, taxes, X)
3. zadatak
Postavka
Slika iz trećeg zadatka.
Uparivanje neusmerenog netežinskog grafa.
- Predložiti i ukratko opisati način na koji se vrši pronalaženje maksimalnog uparenog skupa grafa.
- Za graf sa slike prikazati pronalaženje maksimalnog uparenog skupa po koracima.
Rešenje
4. zadatak
Postavka
Obilazak po dubini
- Definisati stablo obilaska.
- Definisati početno i završno vreme prilikom obilaska grafa po dubini. Koja je njegova uloga?
- Napisati u pseudokodu implementaciju funkcije koja na osnovu zapisanih početnih i završnih vremena obilaska svakog čvora obilaskom po dubini određuje da li se čvor X nalazi u podstablu čvora Y u stablu obilaska.
IS SUCCESSOR(start_time, finish_time, x, y)