Informatika1-2013/Gyakorlat8
A MathWikiből
(Változatok közti eltérés)
(Új oldal, tartalma: „== Feladatok == === 1. feladat === Implementáld a szélességi keresést (BFS) === 2. feladat === === 3. Feladat ===”) |
|||
(egy szerkesztő 10 közbeeső változata nincs mutatva) | |||
1. sor: | 1. sor: | ||
== Feladatok == | == Feladatok == | ||
+ | * A [https://docs.google.com/document/d/1DNdim5h2yj3XL07e-2z_YR2XtFLA9np_hd44rNeH9M0/edit?usp=sharing felhőelefánt másolatát] nézzétek, ha egy megoldást mutatok be. | ||
+ | === 1. feladat - Szélességi bejárás=== | ||
+ | * A szélességi bejárásról bővebben [http://en.wikipedia.org/wiki/Breadth-first_search itt] olvashattok. | ||
+ | * Írj függvényt Sage-ben, mely megvalósítja a szélességi bejárást egy paraméterként kapott G gráfon. | ||
+ | * Írd meg a függvényt úgy, hogy a bejárás alapja egy rekurzív algoritmus legyen. | ||
+ | === 2. feladat - Jaccard hasonlóság=== | ||
+ | Gyakori feladat, hogy két halmazról kell eldöntenünk, mennyire "hasonlóak". Például | ||
− | + | * meg kell mondanunk, hogy két vásárló mennyire vett azonos termékeket | |
− | + | * két ember mennyire olvas hasonló könyvket, hallgat azonos zenét, ... | |
− | + | Az alapfeladat, hogy eldöntsük Sage-ben két listáról, hogy "mennyire tartalmaznak azonos elemeket". (A listák egy-egy matematikai értelemben vett halmaznak felelnek meg.) | |
+ | * Multiplicitás nélküli halmazok összehasonlításának egyik módja a Jaccard index kiszámítása. Ez egyszerűen két halmaz metszetének és uniójának hányadosa: [http://en.wikipedia.org/wiki/Jaccard_index Jaccard index] | ||
+ | * Írj sage függvényt, mely | ||
+ | * bemenetként megkap két listát, | ||
+ | * kiszámolja a két lista Jaccard-indexét, | ||
+ | * nem dolgozik multiplicitással, tehát például a ['ferrari','mercedes','ferrari', 'mercedes'] és ['mercedes','williams','mercedes'] listák hasonlósága 1/3. | ||
− | === 3. Feladat === | + | === 3. Feladat - PageRank=== |
+ | |||
+ | * A PageRank algorimtusról bővebben [http://en.wikipedia.org/wiki/PageRank itt] olvashattok. | ||
+ | * Implementáljátok a PageRank algoritmust. Írjatok függvényt, mely bemenetként egy gráfot kap, kimenetként pedig a PageRank vektort adja vissza. |
A lap jelenlegi, 2013. november 7., 08:46-kori változata
Tartalomjegyzék |
Feladatok
- A felhőelefánt másolatát nézzétek, ha egy megoldást mutatok be.
1. feladat - Szélességi bejárás
- A szélességi bejárásról bővebben itt olvashattok.
- Írj függvényt Sage-ben, mely megvalósítja a szélességi bejárást egy paraméterként kapott G gráfon.
- Írd meg a függvényt úgy, hogy a bejárás alapja egy rekurzív algoritmus legyen.
2. feladat - Jaccard hasonlóság
Gyakori feladat, hogy két halmazról kell eldöntenünk, mennyire "hasonlóak". Például
- meg kell mondanunk, hogy két vásárló mennyire vett azonos termékeket
- két ember mennyire olvas hasonló könyvket, hallgat azonos zenét, ...
Az alapfeladat, hogy eldöntsük Sage-ben két listáról, hogy "mennyire tartalmaznak azonos elemeket". (A listák egy-egy matematikai értelemben vett halmaznak felelnek meg.)
- Multiplicitás nélküli halmazok összehasonlításának egyik módja a Jaccard index kiszámítása. Ez egyszerűen két halmaz metszetének és uniójának hányadosa: Jaccard index
- Írj sage függvényt, mely
- bemenetként megkap két listát,
- kiszámolja a két lista Jaccard-indexét,
- nem dolgozik multiplicitással, tehát például a ['ferrari','mercedes','ferrari', 'mercedes'] és ['mercedes','williams','mercedes'] listák hasonlósága 1/3.
3. Feladat - PageRank
- A PageRank algorimtusról bővebben itt olvashattok.
- Implementáljátok a PageRank algoritmust. Írjatok függvényt, mely bemenetként egy gráfot kap, kimenetként pedig a PageRank vektort adja vissza.