Izpitno vprašanje RAČ2PRA 15900

Iz MaFiRaWiki

GFDL Avtor tega članka je študent/ka AleksandraVujasin.

Pripravil/a ga je pri predmetu Računalništvo 2 (FMF PRA).


Kljub temu ste vsi vabljeni k urejanju in popravkom, saj je bistvo wikija ravno v sodelovalnem delu.

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