Algoritmien kilpailukykyanalyysi

pvm: 16.5.2000

Luennoitsija: Tomi Pasanen

  1. Analysoi MTF (move-to-front) menetelmä listan organisoinnissa
  2. Satunnaistaminen ja kilpailukykyanalyysi
  3. Analysoi MARK algoritmin toiminta sivutusongelmassa.

    Algorithm MARK: Initially, all pages are unmarked. When requesting a page p that is in cache but unmarked, p is made marked. If p is not in cache, then it is marked and brought into cache replacing a randomly and uniformly chosen page from the set of all unmarked pages. If all pages in cache are marked when p is about to be brought in, then all pages are unmarked first.
  4. Mitä seuraavat termit tarkoittavat
  • Absoluuttinen approksimointialgoritmi
    (absolute approximation algorithm)

    Absoluuttinen suoritussuhde
    (absolute performance ratio)

    Asymptoottinen suoritussuhde
    (asymptotic performance ratio)

    Approksimaatiosysteemi
    (approximation scheme)

    Polynominen approksimointisysteemi
    (polynomial approximation scheme (PAS))

    Täysin polynominen approksimointisysteemi
    (fully polynomial approximation scheme (FPAS))

    Pseudo-polynomiaikainen algoritmi
    (pseudo-polynomial time algorithm)

    Vahvasti NP-täydellinen
    (strongly NP-complete)

    •