CN - curs 01 - 2012immobilier-montreal.net/upload/documents/292859.pdf · Săptămânânile 1-7 şi...
Transcript of CN - curs 01 - 2012immobilier-montreal.net/upload/documents/292859.pdf · Săptămânânile 1-7 şi...
1
[email protected] , [email protected]
[email protected] – pentru temele de laborator
http://www.infoiasi.ro/~ancai/CN/
Consultaţii:
prin e-mail la adresa de mai sus sau
la cabinet (C-307), joi, 16-18
2
Regulament - 2011-2012
Laborator
8 teme
cei care prezintă temele până la termenul limită precizat la
fiecare temă, punctajul maxim ce poate fi obţinut este
punctajul afişat pentru fiecare temă
cei care prezintă temele după termenul limită precizat
punctarea se va face din 50% din punctajul temei prezentate
3
Examen
teză scrisă de 1 oră, cu 3 sau 4 exerciţii din materia predată,
˝cu cursurile pe masa˝ - exclusă documentaţia pe suport
electronic
teza scrisă este notată între 1 şi 10
prezenţa la examen este obligatorie chiar dacă s-a obţinut
punctaj de promovare doar din punctajul de la laborator
4
Calculul punctajului / notei final(e)
Punctaj final = punctaj laborator + 29*nota examen
Promovează disciplina acei studenţi care au:
nota la examen ≥ 3
şi
punctaj final ≥ 260 pt
Nota finală se calculează din punctajul final aplicând ”curba lui Gauss”.
5
Desfăşurarea semestrului
Săptămânânile 1-7 şi 9-15 – şcoală conform orarului
Prima săptămâna de evaluare – liber
Săptămâna 15
- prezentare teme de laborator restante
Săptămâna 15 sau 16 - examen
6
Bibliografie 1. Elemente de informatică şi calcul numeric, vol. 1 - C.Ignat,
C.Ilioi, T.Jucan - Ed. Univ. ‘Al. I. Cuza’ Iaşi, 1987 2. Calcul numeric în C - T. A. Beu - Ed. Albastră, Cluj, 2004 3. Metode numerice - V.Iorga, B.Jora - Ed. Albastră, Cluj, 2004 4. Numerical Recipes in C/C++ (www.nr.com) 5. Matrix Computations - G.H. Golub, C.F. van Loan - John
Hopkins Univ. Press, 1996 6. Numerical Analysis – R.L. Burden, J.D. Faires – Brooks/Cole,
Thomson Learning, 2001 7. Computing for numerical methods using Visual C++ - S. Salleh,
A.Y. Zomaya, S. Abu Baka – John Wiley & Sons, 2008 8. Numerical Optimization – J. Nocedal, S.J. Wright – Springer,
1999
7
Capitolele cursului
1. Rezolvarea sistemelor liniare (Ax=b)
2. Optimizare numerică ( min { F(x) ; x Œ Rn } )
3. Valori şi vectori proprii (Au = λu)
4. Ecuaţii neliniare (f(x)=0)
5. Interpolare numerică
8
Exemple
Web search – Google’s PageRank
- informaţii nestructurate, ‘self-organized’
- fără standarde, recenzenţi, ‘paznici’ ai conţinutului
- informaţie volatilă, eterogenă şi foarte diversă (conţinut,
structură, format, limbi, alfabete, scop)
- 1013 – pagini web (probabil mai multe) ???
9
Căutarea
roboţi web – parcurg permanent graful Web pentru informaţii
depozitul de pagini - memorează temporar paginile web
(paginile foarte populare sunt stocate perioade mai lungi)
modulul de indexare – se extrage din paginile depozitate
informaţia esenţială (cuvinte-cheie, fraze-cheie, descriptori) →
se obţine o versiune comprimată a paginii; în funcţie de
popularitatea paginii aceasta este fie ştearsă, fie păstrată în
depozitul de pagini
10
informaţiile esenţiale memorate despre orice pagină Web
index de conţinut - cuvinte sau fraze cheie, titlu (se
construieşte inverted file - similar indexului unei cărţi) index de structură hyperlink index de informaţii speciale – imagini, pdf
11
modul de interogare – transformă cererea din limbaj natural
într-un limbaj pentru motorul de căutare (de obicei numere); se
consultă informaţiile esenţiale memorate; se obţin paginile
relevante cererii (care conţin termeni din interogare). modulul de ‘ranking’(evaluare a relevanţei) – prelucrează
paginile relevante furnizate de modulul de interogare şi le
ordonează după anumite criterii (funcţie de motorul de
căutare); acest modul trebuie să discearnă care pagină Web
răspunde cel mai bine interogaţiei şi le ordonează;
12
PageRank este sistemul de evaluare a paginilor web din punctul
de vedere al importanţei, folosit de motorul de căutare Google.
Nota furnizată de PageRank este unul din factorii folosiţi
pentru a ordona paginile web atunci cand se face o căutare.
“PageRank is an important factor. It is one out of 200 signals
but still it is an important one for a large number of queries.”
(Matt Cutts – head of Google’s Webspam team)
13
Google dă cel puţin 2 ‘note’/’scoruri’ fiecărei pagini Web:
a. popularitate
b. conţinut – modul de calcul este secret – termenii din
interogare sunt în titlu sau în interiorul paginii, de câte
ori termenii apar în pagină, cât de aproape unii de alţii
sunt termenii din interogaţiile cu cuvinte multiple, cum
apar termenii de interogare (bold, subtitluri…),
conţinutul paginilor vecine
Nota/scorul finală cu care se face ordonarea este o medie ponderată
între notele de mai sus, componenta principală fiind popularitatea.
14
PageRank (Google) – S. Brin, L. Page (popularitate) Sergey Brin, Lawrence Page, R. Motwami, Terry Winograd – ‘The
PageRank citation ranking: bringing order to the Web’ –
Technical Report 1999-0120, Computer Science Department,
Stanford University, 1999
Ideea: O pagină este importantă dacă este referită (citată) de alte
pagini importante.
15
Importanţa unei pagini (PageRank-ul ei) este calculată sumând
PageRank-urile tuturor paginilor care citează pagina respectivă.
Dacă o pagină importantă citează mai multe pagini, atunci
importanţa ei se împarte egal paginilor pe care le citează.
Graful Web – cu n noduri.
daca pagina citeaza pagina altfel
10ij
j iI
cj = numarul de citari ale paginii j (outlink-urile paginii j)
ri = PageRank-ul paginii i
16
?1
(1 ) , 0 , 0.85n
iji j
j j
Ir d d r d d
c
(1)
Constanta d asigură faptul că fiecare pagina Web are un Pagerank
de cel puţin (1-d).
Relaţia (1) poate fi scrisă matricial astfel:
1(1 ) Tr d e d e I C r (2)
17
diag 1 2
11
, , , , ,
1
n n n n nij ne I I C c c c
Deoarece suma tututror Pagerank-urilor este 1 putem scrie:
11
nT
ii
r e r
.
11 T n ndA ee d I Cn
18
Relaţia (2) se poate scrie:
r Ar
Această relaţie ne spune că matricea A (matrice de dimensiuni
foarte mari şi rară) are valoarea proprie 1 iar vectorul de Pagerank-
uri este vectorul propriu asociat. Se poate folosi metoda puterii
pentru determinarea lui r.
19
Alte tehnici de CN folosite pentru PageRank: rezolvarea sistemelor
liniare, SVD (Singular Value Decomposition)
An Arnoldi-type Algortihm for Computing Page Rank, G.H. Golub, C.
Greif, BIT Numerical Mathematics, Springer, 2006
Fast Parallel PageRank: A Linear System Approach, D. Gleich, L.
Zhukov, P. Berkhin, WWW2005, May 10–14, 2005, Chiba, Japan
The Use of the Linear Algebra by Web Search Engines, A.N.Langville,
C.D. Meyer, 2004
(http://www.infoiasi.ro/~ancai/CN/bibliografie/)
20
Compresia imaginilor digitale si descompunerea după valori singulare
o imagine digitală ↔ matrice de pixeli A cu m linii şi n coloane
sau 31,...,1,...,
,ij iji mj n
A a a
( sau 30,1, ...,255 0,1, ...,255ij ija a )
Pentru memorarea lui A e nevoie de m·n·mem(int) = 2 m n bytes
Descompunerea dupa valori singulare (SVD) a unei matrici
, , ,T m m m n n nA U SV U S V
matrici ortogonale1 2 1 2, , ..., , , , ...,m nU u u u V v v v
21
daca daca
1, , , ,
0m ni j ij i j ij
i ju u v v i j
i j
1
2
0 0 00 0 0
0 0 0
0 0 0 0
m n
r
S
- valorile singulare ale matricii 1 2 0 , min{ , }r r m n A
22
1 1 1 2 2 2T T T
r r rA u v u v u v
1 1 1 2 2 2T T T
k k k kA A u v u v u v
memorarea lui Ak necesită k(m+n+1)·mem(double)
m=2448 , n=3264 , ( 1)c
mnrk m n
, r=2448
k=50 rc= 27.9722 ; k=100 rc= 13.9861 ; k=150 rc= 9.3241
k=200 rc= 6.9931 ; k=250 rc=5.5944 ; k=300 rc= 4.662
23
Vectori şi matrici
Fie xi , yi , . Se definesc vectorii , nx y şi operaţiile
de adunare şi înmulţire cu scalari astfel:
1 1 1 1 1
2 2 2 2 2, , ,
n n n n n
x y x y xx y x y x
x y x y x
x y x y x
.
24
Fie vectorul nz :
cu
1
21 2, , ..., .n
n
zz
z z z z
z
Pentru z utilizăm notaţiile:
z = a + ib , Re z = a, Im z = b , 2 2,z a ib z a b
25
Notăm cu m n / m n spaţiul matricilor cu elemente reale / complexe cu m linii şi n coloane
,11 1
1
, / 1,2, ..., , 1,2, ...,n
ij
m mn
a aA a i m j n
a a
26
Definiţie
X se numeşte spaţiu vectorial (spaţiu liniar)
+ : X X Æ X şi : K X Æ X,
astfel încât ( X , + ) este un grup comutativ :
a + b = b + a , a,b X – comutativitate,
(a + b) + c = a + (b + c) , a,b,c X – asociativitate ,
0 X a. î. a + 0 = 0 + a = a , a X - element neutru ,
a X, -a X a.î. a + (-a) = (-a) + a = 0 – element opus.
27
iar pentru operaţia de înmulţire cu scalari au loc relaţiile:
(a+b) = a + b , K , a,b X ,
( + ) a = a + a , , K , a X,
( a ) = ( )a , , K , a X,
1 K astfel încât 1 a = a , a X.
28
Definiţie Fie X un spaţiu liniar. Spunem că vectorii x1 , x2 , …, xp X
sunt liniar independenţi dacă:
1 1 2 2 1 2.. 0 ... 0p p p ix x x K
Spaţiul vectorial X este finit dimensional dacă există p
vectori liniar independenţi în X, x1 , x2 , …,xp X, şi orice
mulţime de q elemente din X cu q > p este liniar dependentă.
În acest caz dimensiunea spaţiului X este p (dim X = p).
29
Fie spaţiul vectorial X finit dimensional cu dim X = p. Orice
sistem de p vectori liniar independenţi din X se numeşte bază
a spaţiului X.
Fie x1 , x2 , …,xp X o bază pentru spaţiul X . Atunci pentru
x X , unice constantele 1, 2,…, p K astfel încât
1 1 2 21
..p
p p i ii
x x x x x
n este un spaţiu vectorial finit dimensional, dim n = n cu
baza canonică:
31
Calcul matricial Fie matricea m nA :
11 1
1 , 1
1
,n
ij i m j n
m mn
a aA A a
a a
Se defineşte matricea transpusă:
11 1
1 , 1
1
,m
T T n mji i m j n
n mn
a aA A a
a a
32
Pentru matricea: 1
1,m n
i mijj n
A A a
se defineşte matricea adjunctă AH:
11
11 1 11 1
1 1
,
H Tj njii m
n mH
m mn n mn
A A a
a a a aA A
a a a a
33
Pentru m nA matricea adjunctă coincide cu transpusa,
AH = AT.
Fie vectorul nx , acesta este considerat vector coloană, 1nx :
1
21 2
Tn
n
xx
x x x x x
x