Når man søger på Google, bliver de fundne links returneret i en rækkefølge der (nogenlunde) svarer til relevansen af disse links. Relevansen måles med en størrelse som kaldes Page rank. Hvorledes defineres denne størrelse og hvorledes beregnes den?
Svarene på disse spørgsmål involverer opstilling og løsning af verdens største egenværdi-problem. Man opstiller en matrix hvis orden er lig med antallet af hjemmesider på nettet og som beskriver alle links mellem hjemmesiderne, og beregner den største egenværdi og tilhørende egenvektor for denne matrix. Elementerne i egenvektoren er de søgte Page-ranks.
I dette projekt skal vi se på formuleringen af det underliggende problem og den tilhørende matematik, bl.a. hvorledes det omtalte egenværdi-problem opstår. Denne del indeholder primært stof fra lineær algebra. Endvidere skal vi se på algoritmer fra numerisk analyse til beregning af egenværdier, og vi skal se hvorledes man bliver nødt til at tage hensyn til problemets struktur og enorme dimension ved beregningerne. Som litteratur bruger vi dels beskrivelser fra internettet (fx "Page Rank Explained") og dels uddrag af lærebøger.
OPGAVEKRAV:
Lektor
Hans Bruun Nielsen
IMM, 4525 3077.
Email: hbn@imm.dtu.dk