[an error occurred while processing this directive]

IN210 - læremidler og pensum

Kompendium 51

NY UTGAVE AUGUST 1999. Kan kjøpes i Akademika (del A og del B) eller leses på nettet: pdf-versjon av kompendium 51 (395 sider, 2,3Mb):
  • Kap. 1 og 2: Bakgrunnsstoff.
  • Kap. 3: Alt er pensum.
  • Kap. 4: Oppgaver gitt på gruppene.
  • Kap. 5: Oppsummeringer og noen steder utdypninger av deler av pensum. Det gis ingen garanti for at det stemmer helt med årets pensum.

Garey and Johnson: Computers and Intractability

  • Kap. 1: Alt er pensum.
  • Kap. 2: Alt er pensum, med følgende modifikasjoner:
    • Stoffet om deterministiske turingmaskiner i kap. 2.2 og om ikkedeterministiske turingmaskiner i kap. 2.3 og kap. 2.5 er ikke pensum i alle detaljer, men man må ha forståelse for hva stoffet og setningene innbærer på det plan resten av boka arbeider. (Se bl.a. kommentarer til disse avsnitt, i kompendiet side 58).
    • I kap. 2.6 er ikke detaljene i beviset for Cook's teorem pensum.
  • Kap. 3: Alt er pensum, med følgende modifikasjoner:
    • I kap 3.2 er de tre metodene pensum, men teoremene 3.6 - 3.10 er ikke pensum.
  • Kap. 4: Alt er pensum, med følgende modifikasjoner:
    • Fra og med MAX CUT på side 87 og resten av kap 4.1 utgår.
    • Av kap. 4.2.2 tar vi bare med de første avsnittene fram til "In contrast, ...", på side 96. Man skal imidlertid også vite at MULTIPROCESSOR SCHEDULING og 3-PARTISJON er NP-komplette i sterk forstand.
  • Kap. 5: Alt er pensum, med følgende modifikasjoner:
    • Av 5.1 utgår følgende:
      • Fra "The formal counterpart" side 110 til "The generalization" side 111.
      • Fra "This notion" side 111 til "We are now prepared" side 113.
      • Fra "Kth LARGEST SUBSET" side 114 til "On the basis of" side 115.
    • 5.2 er ikke pensum (men er meget interessant bakgrunnsstoff).
  • Kap. 6: Alt er pensum, med følgende modifikasjoner:
    • Fra "The idea behind ...", side 131 til "These results ... " side 132 utgår.
    • Av kapittel 6.2 tar vi (bare) med:
      • Fra starten og fram til "Let us begin with ...", side 138.
      • Teorem 6.8 og 6.9 med bevis: Fra "Recall that we ..." (side 140) til "Let us now return ..." (side 142).
      • Teorem 6.13 med bevis: Fra "Theorem 6.13" (side 147) og ut kapittel 6.2.
    • Kapittel 6.3 er ikke pensum
  • Kap. 7: Er ikke pensum.

David Harel: Algorithmics

Annen utgave.
  • Kap. 8 (hele)
  • Kap. 9: side 223-238
  • Kap. 10: side 265-281
  • Kap. 11: side 309-334
  • Kap. 12: side 347-353

Artikkel om kvantekomputere

Artikkelen Quantum Computing, av Lov K. Grover (The Sciences, July/August 1999).

Sist oppdatert 22.08.2001.