Izpitno vprašanje RAČ2PRA 15900

Iz MaFiRaWiki

(Razlika med različicami)
Različica od 20:01, 6 maj 2006
AleksandraVujasin (Pogovor | prispevki)

← Prejšnja različica
Različica od 20:55, 6 maj 2006
AleksandraVujasin (Pogovor | prispevki)
Odgovor
Naslednja različica →
Vrstica 4: Vrstica 4:
=Odgovor= =Odgovor=
 +
 +* n enot z dolžinami l<sub>i</sub> moramo shraniti na magnetni trak, tako da bo povprečni čas klica najmanjši
 +* pred vsakim branjem trak previjemo na začetek
 +* enako pogosto kličemo enote
 +* čas branja premo sorazmeren z dolžino
 +<br/>
 +*Primer:
 +** Dopustna podmnožica
 +** Optimalna podmnožica
 +<br/>
 +*OZNAČIMO:
 +** i<sub>k</sub> - številka programa, ki je na k-tem mestu
 +** t<sub>k</sub> - čas, ki ga potrebujemo za branje i<sub>k</sub>-tega programa
 +
 +:::::<math>\sum_{r=1}^k l_{i_r}</math>
 +
 +** povprečni čas klica
 +
 +:::::<math>\frac{1}{n}\sum_{k=1}^n t_k</math>
 +
 +* na r tem koraku - katero enoto bomo izbrali
 +* dodajamo v nepadajočem vrstnem redu
 +
 +*DOKAZ: požrešna metoda deluje optimalno
 +** naj bodo označene l<sub>1</sub> ≤ l<sub>2</sub> ≤ … ≤ l<sub>n</sub>
 +** povprečen čas branja:
 +
 +:::::<math>\frac{1}{n}\sum_{j=1}^n t_j = \frac{1}{n}\sum_{j=1}^n \sum_{r=1}^j l_r = \frac{1}{n}\sum_{r=1}^n \sum_{j=r}^n l_r = \frac{1}{n}\sum_{r=1}^n (n - r +1)l_r</math>
 +
 +** zamenjajmo vrstni red i-te in j-te enote
 +** i-to enoto torej preberemo (n - j + 1)krat
 +**Kaj se spremeni v času:
 + - ((n - i + 1)l<sub>i</sub> + (n - j + 1)l<sub>j</sub>) + ((n - i + 1)l<sub>j</sub> + (n - j + 1)l<sub>i</sub>) = (n - j)(l<sub>i</sub> - l<sub>j</sub>) >= 0

Različica od 20:55, 6 maj 2006

Vprašanje

Razporejanje programskih enot na trak - opis algoritma.

Odgovor

  • n enot z dolžinami li moramo shraniti na magnetni trak, tako da bo povprečni čas klica najmanjši
  • pred vsakim branjem trak previjemo na začetek
  • enako pogosto kličemo enote
  • čas branja premo sorazmeren z dolžino


  • Primer:
    • Dopustna podmnožica
    • Optimalna podmnožica


  • OZNAČIMO:
    • ik - številka programa, ki je na k-tem mestu
    • tk - čas, ki ga potrebujemo za branje ik-tega programa
\sum_{r=1}^k l_{i_r}
    • povprečni čas klica
\frac{1}{n}\sum_{k=1}^n t_k
  • na r tem koraku - katero enoto bomo izbrali
  • dodajamo v nepadajočem vrstnem redu
  • DOKAZ: požrešna metoda deluje optimalno
    • naj bodo označene l1 ≤ l2 ≤ … ≤ ln
    • povprečen čas branja:
\frac{1}{n}\sum_{j=1}^n t_j = \frac{1}{n}\sum_{j=1}^n \sum_{r=1}^j l_r = \frac{1}{n}\sum_{r=1}^n \sum_{j=r}^n l_r = \frac{1}{n}\sum_{r=1}^n (n - r +1)l_r
    • zamenjajmo vrstni red i-te in j-te enote
    • i-to enoto torej preberemo (n - j + 1)krat
    • Kaj se spremeni v času:
- ((n - i + 1)li + (n - j + 1)lj) + ((n - i + 1)lj + (n - j + 1)li) = (n - j)(li - lj) >= 0
Osebna orodja