Detaljerte l?ringskrav (forel?pig)
----------------------------------


Kurset kan i hovedsak sees p? som best?ende av fem bolker:

1) Kompendiet
2) Stokastiske grafer (Random graphs)
3) Sorteringsnettverk
4) Probabilistiske algoritmer og Gjennomsnittsanalyse/-kompleksitet
5) Egen artikkel


1) Kompendiet er i hovedsak bakgrunnsstoff. Enkelte, enkle, bevis kan
   man dog m?tte presentere i detalj.

2) Man m? ha forst?ese av hva stokastiske grafer er, hva de brukes
   til, hvilke modeller som finnes, evolusjon, terskler, etc. I
   tillegg m? man i detalj kunne bevise ulike terskelfunksjoner. (Vi
   har sett p? etpar bevis (sykler, klikker).)

3) Men m? ha forst?else for hva et sorteringsnettverk er, og detaljert
   kunne redgj?re for Batchers odd-even-nettverk (oppbygging, kj?retid
   og korrekthet). I tillegg m? man kunne forklare hovedtrekkene i
   Patersons sorteringsnettverk, og kunne redgj?re for den teroretisk
   betydningen av Ajtaj, Komlos og Szemeredis arbeid (som Paterson
   bygger p?).

4) Man m? kunne redgj?re for Angluin og Valiants tre algoritmer, og
   grovt skissere hvordan de beviser sine resultater, Det sentrale
   punktet, Coupon Collector-beviset, skal dog kunne presenteres i
   detalj. N?r det gjelder Average case NP-completeness m? man kunne
   skissere Levins teori (Klassen Dist-NP, reduksjonstypen som brukes,
   kompletthet for Dist-NP (herunder Coding Lemma)). I tillegg m? man
   kunne forklare hovedtrekkene i Gurevich og Shelas arbeid (men ingen
   beviser).

5) Hovedresultatet/fremgangsm?ten i den presenterte artikkel m? kunne
   presenteres.