Vybrané partie z dátových štruktúr
2-INF-237, LS 2016/17
Prezentácia: Rozdiel medzi revíziami
Z VPDS
(→Rady k prezentácii) |
|||
| Riadok 1: | Riadok 1: | ||
| − | Cieľom prezentácie je precvičiť si prácu s odbornou literatúrou a oboznámiť sa s ďalšími výsledkami v oblasti | + | Cieľom prezentácie je precvičiť si prácu s odbornou literatúrou a oboznámiť sa s ďalšími výsledkami v oblasti dátových štruktúr. Každý študent si zvolí a podrobne naštuduje jeden odborný článok (z odbornej konferencie alebo časopisu) z tejto oblasti a ten odprezentuje spolužiakom na prednáške koncom semestra. Každý študent si musí zvoliť iný článok. |
==Termíny== | ==Termíny== | ||
| − | * Výber článku na prezentáciu do | + | * Výber článku na prezentáciu do pondelka 20.4. v systéme Moodle. Každý článok môže prezentovať iba jeden študent, takže odovzdajte svoj výber radšej skôr. Kto si článok do uvedeného termínu nevyberie, bude mu nejaký priradený vyučujúcou. |
| − | * Prezentácie na prednáškach v posledných týždňoch semestra | + | * Prezentácie na prednáškach v posledných týždňoch semestra |
* Prezentáciu vo formáte pdf odovzdať prostredníctvom Moodlu najneskôr 1 hodinu pred prednáškou, na ktorej máte prezentovať. | * Prezentáciu vo formáte pdf odovzdať prostredníctvom Moodlu najneskôr 1 hodinu pred prednáškou, na ktorej máte prezentovať. | ||
| Riadok 17: | Riadok 17: | ||
Typická osnova prezentácie (podľa potreby ju však možete meniť): | Typická osnova prezentácie (podľa potreby ju však možete meniť): | ||
| − | * Úvod: aký problém autori študujú, prečo je dôležitý alebo zaujímavý | + | * Úvod: aký problém autori študujú, prečo je dôležitý alebo zaujímavý? Má nejaký vzťah k učivu z prednášok, prípradne k iným predmetom? |
* Prehľad výsledkov: V čom je presne prínos autorov oproti predchádzajúcim prácam? Nemusíte robiť rozsiahly prehľad predchádzajúcich prác, len uveďte, čo je v článku nové. Malo by to byť jasné najmä z úvodu a záveru článku. | * Prehľad výsledkov: V čom je presne prínos autorov oproti predchádzajúcim prácam? Nemusíte robiť rozsiahly prehľad predchádzajúcich prác, len uveďte, čo je v článku nové. Malo by to byť jasné najmä z úvodu a záveru článku. | ||
| − | * Jadro: Vysvetlite nejaký kúsok zo samotného obsahu článku (časť algoritmu alebo dôkazu, niektoré výsledky | + | * Jadro: Vysvetlite nejaký kúsok zo samotného obsahu článku (časť algoritmu alebo dôkazu, niektoré výsledky z testovania na dátach a pod.) |
* Záver: zhrnutie prezentácie, váš názor (čo sa Vám na článku páčilo alebo nepáčilo) | * Záver: zhrnutie prezentácie, váš názor (čo sa Vám na článku páčilo alebo nepáčilo) | ||
| Riadok 41: | Riadok 41: | ||
* L. Heng, R. Durbin (2009): Fast and accurate short read alignment with Burrows-Wheeler transform. Bioinformatics 25(14): 1754-1760 [http://bioinformatics.oxfordjournals.org/cgi/reprint/25/14/1754 pdf] <i>Aplikácia BWT v bioinformatike.</i> | * L. Heng, R. Durbin (2009): Fast and accurate short read alignment with Burrows-Wheeler transform. Bioinformatics 25(14): 1754-1760 [http://bioinformatics.oxfordjournals.org/cgi/reprint/25/14/1754 pdf] <i>Aplikácia BWT v bioinformatike.</i> | ||
| − | * Orlin, James B., et al. "A faster algorithm for the single source shortest path problem with few distinct positive lengths." Journal of Discrete Algorithms 8.2 (2010): 189-198. [http://dspace.mit.edu/openaccess-disseminate/1721.1/67886] | + | * Orlin, James B., et al. "A faster algorithm for the single source shortest path problem with few distinct positive lengths." Journal of Discrete Algorithms 8.2 (2010): 189-198. [http://dspace.mit.edu/openaccess-disseminate/1721.1/67886] |
* Gonzalo Navarro, Yakov Nekrich: Optimal Dynamic Sequence Representations. SODA 2013: 865-876 [http://arxiv.org/pdf/1206.6982] | * Gonzalo Navarro, Yakov Nekrich: Optimal Dynamic Sequence Representations. SODA 2013: 865-876 [http://arxiv.org/pdf/1206.6982] | ||
| − | * Holm, Jacob, Kristian De Lichtenberg, and Mikkel Thorup. "Poly-logarithmic deterministic fully-dynamic algorithms for connectivity, minimum spanning tree, 2-edge, and biconnectivity." Journal of the ACM (JACM) 48, no. 4 (2001): 723-760. [http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.89.919&rep=rep1&type=pdf pdf] <i>Ako udržiavať súvislé komponenty v dynamickom grafe. Dlhší článok, stačí naštudovať a prezentovať časť.</i | + | * Holm, Jacob, Kristian De Lichtenberg, and Mikkel Thorup. "Poly-logarithmic deterministic fully-dynamic algorithms for connectivity, minimum spanning tree, 2-edge, and biconnectivity." Journal of the ACM (JACM) 48, no. 4 (2001): 723-760. [http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.89.919&rep=rep1&type=pdf pdf] <i>Ako udržiavať súvislé komponenty v dynamickom grafe. Dlhší článok, stačí naštudovať a prezentovať časť o súvislosti.</i> |
| − | * Burcsi, Peter, Ferdinando Cicalese, Gabriele Fici, and Zsuzsanna Lipták. "Algorithms for jumbled pattern matching in strings." International Journal of Foundations of Computer Science 23, no. 02 (2012): 357-374. [http://arxiv.org/pdf/1102.1746.pdf] <i>Indexovanie textu aby sa dala vyhľadávať vzorka s permutovanými znakmi.</i | + | * Burcsi, Peter, Ferdinando Cicalese, Gabriele Fici, and Zsuzsanna Lipták. "Algorithms for jumbled pattern matching in strings." International Journal of Foundations of Computer Science 23, no. 02 (2012): 357-374. [http://arxiv.org/pdf/1102.1746.pdf] <i>Indexovanie textu aby sa dala vyhľadávať vzorka s permutovanými znakmi.</i> |
| − | * Wild, Sebastian, and Markus E. Nebel. "Average case analysis of Java 7’s dual pivot quicksort." In Algorithms–ESA 2012, pp. 825-836. Springer Berlin Heidelberg, 2012. [http://arxiv.org/pdf/1310.7409] <i>Síce ide o triedenie a nie dátové štruktúry, ale tieto dve oblasti spolu úzko súvisia.</i | + | * Wild, Sebastian, and Markus E. Nebel. "Average case analysis of Java 7’s dual pivot quicksort." In Algorithms–ESA 2012, pp. 825-836. Springer Berlin Heidelberg, 2012. [http://arxiv.org/pdf/1310.7409] <i>Síce ide o triedenie a nie dátové štruktúry, ale tieto dve oblasti spolu úzko súvisia.</i> |
| − | * Goel, Ashish, Sanjeev Khanna, Daniel H. Larkin, and Robert E. Tarjan. "Disjoint Set Union with Randomized Linking." SODA 2014 [http://www.cs.princeton.edu/~dhlarkin/papers/soda14-disjoint-set-union-with-randomized-linking.pdf] | + | * Goel, Ashish, Sanjeev Khanna, Daniel H. Larkin, and Robert E. Tarjan. "Disjoint Set Union with Randomized Linking." SODA 2014 [http://www.cs.princeton.edu/~dhlarkin/papers/soda14-disjoint-set-union-with-randomized-linking.pdf] |
* Bender, Michael A., Roozbeh Ebrahimi, Jeremy T. Fineman, Golnaz Ghasemiesfeh, Rob Johnson, and Samuel McCauley. "Cache-Adaptive Algorithms." [http://www.cs.sunysb.edu/~rob/papers/cache-adaptive.pdf] <i>Zovšeboecnenie modelu cache-oblivious algoritmov.</i> | * Bender, Michael A., Roozbeh Ebrahimi, Jeremy T. Fineman, Golnaz Ghasemiesfeh, Rob Johnson, and Samuel McCauley. "Cache-Adaptive Algorithms." [http://www.cs.sunysb.edu/~rob/papers/cache-adaptive.pdf] <i>Zovšeboecnenie modelu cache-oblivious algoritmov.</i> | ||
| − | * Larkin, Daniel H., Siddhartha Sen, and Robert E. Tarjan. "A back–to–basics empirical study of priority queues." ALENEX 2014 [http://arxiv.org/pdf/1403.0252v1] | + | * Larkin, Daniel H., Siddhartha Sen, and Robert E. Tarjan. "A back–to–basics empirical study of priority queues." ALENEX 2014 [http://arxiv.org/pdf/1403.0252v1] |
==Rady k hľadaniu článkov== | ==Rady k hľadaniu článkov== | ||
| Riadok 67: | Riadok 67: | ||
* Konferencie CPM a SPIRE sú dobrým zdrojom článkov o vyhľadávaní v texte, iné dátové štuktúry nájdete na všeobecných konferenciách pre teoretickú informatiku, napr STOC, FOCS, SODA. ESA. WADS, MFCS, ISAAC. Praktické implementácie sú námetom konferencií WAE a ALENEX. | * Konferencie CPM a SPIRE sú dobrým zdrojom článkov o vyhľadávaní v texte, iné dátové štuktúry nájdete na všeobecných konferenciách pre teoretickú informatiku, napr STOC, FOCS, SODA. ESA. WADS, MFCS, ISAAC. Praktické implementácie sú námetom konferencií WAE a ALENEX. | ||
| − | Väčšina databáz má linky na elektronické verzie článkov u vydavateľa. Tam väčšinou uvidíte aspoň | + | Väčšina databáz má linky na elektronické verzie článkov u vydavateľa. Tam väčšinou uvidíte aspoň voľne prístupný abstrakt, ktorý vám pomôže rozhodnúť, či Vás článok zaujíma. Pre niektoré zdroje (napr. ACM, IEEE a [http://www.uniba.sk/?id=1867 ďalšie]) je plný text článku prístupný z fakultnej siete. Z domu sa môžete prihlásiť cez univerzitný proxy (v prehliadači nastavte automatický konfiguračný skript http://www.uniba.sk/proxy.pac ). Celý text článku (pdf) sa v mnohých prípadoch dá nájsť na webe (napr. na webstránke autora). V najhoršom prípade, ak neviete zohnať článok, ktorý k projektu alebo prezentácii veľmi potrebujete, kontaktujte ma e-mailom a môžem sa pokúsiť ho zohnať. |
Verzia zo dňa a času 10:51, 17. január 2015
Cieľom prezentácie je precvičiť si prácu s odbornou literatúrou a oboznámiť sa s ďalšími výsledkami v oblasti dátových štruktúr. Každý študent si zvolí a podrobne naštuduje jeden odborný článok (z odbornej konferencie alebo časopisu) z tejto oblasti a ten odprezentuje spolužiakom na prednáške koncom semestra. Každý študent si musí zvoliť iný článok.
Obsah
Termíny
- Výber článku na prezentáciu do pondelka 20.4. v systéme Moodle. Každý článok môže prezentovať iba jeden študent, takže odovzdajte svoj výber radšej skôr. Kto si článok do uvedeného termínu nevyberie, bude mu nejaký priradený vyučujúcou.
- Prezentácie na prednáškach v posledných týždňoch semestra
- Prezentáciu vo formáte pdf odovzdať prostredníctvom Moodlu najneskôr 1 hodinu pred prednáškou, na ktorej máte prezentovať.
Rady k prezentácii
- Na prezentáciu budete mať 15 minút (plus diskusia), pričom tento limit bude striktne dodržiavaný. Nechystajte si teda priveľa materiálu, rátajte aspoň 1,5 minúty na slajd.
- K dispozícii bude dátový projektor a notebook, na ktorom bude nahraná vaša odovzdaná prezentácia. Môžete si priniesť aj vlastný počítač. Môžete použiť tabuľu, ale s mierou, lebo vysvetľovanie pri tabuli ide pomalšie.
- Hlavným cieľom je porozprávať niečo zaujímavé z vášho článku vo forme prístupnej vašim spolužiakom (ktorí chodili na tento predmet, nepamätajú si však každý detail z každej prednášky). Nemusíte pokryť celý obsah článku a nemusíte použiť rovnaké poradie, označenie alebo príklady, ako autori článku.
- Nedávajte do prezentácie veľa textu, použite dostatočne veľký font a dobre viditeľné farby (podobné farby, napr. žltá na bielej, nemusia byť na projektore vôbec viditeľné).
- Použite čo najmenej definícií a označenia. Pojmy, algoritmy a dôkazy radšej ilustrujte na obrázku alebo príklade, než zložitým textom.
Typická osnova prezentácie (podľa potreby ju však možete meniť):
- Úvod: aký problém autori študujú, prečo je dôležitý alebo zaujímavý? Má nejaký vzťah k učivu z prednášok, prípradne k iným predmetom?
- Prehľad výsledkov: V čom je presne prínos autorov oproti predchádzajúcim prácam? Nemusíte robiť rozsiahly prehľad predchádzajúcich prác, len uveďte, čo je v článku nové. Malo by to byť jasné najmä z úvodu a záveru článku.
- Jadro: Vysvetlite nejaký kúsok zo samotného obsahu článku (časť algoritmu alebo dôkazu, niektoré výsledky z testovania na dátach a pod.)
- Záver: zhrnutie prezentácie, váš názor (čo sa Vám na článku páčilo alebo nepáčilo)
Typy vhodných článkov
- Články o dátových štruktúrach alebo ich variantoch, ktoré neboli/nebudú pokryté na prednáške
- Články empiricky porovnávajúce dátové štruktúry na reálnych dátach alebo popisujúce použitie týchto algoritmov v reálnych aplikáciach.
- Články o podrobnejšej analýze dátových štruktúr: dolné a horné odhady, analýza v priemernom prípade a pod.
Príklady článkov
Zopár ukážok článkov, nemusíte si však vybrať z tohto zoznamu.
- J. Fischer, V. Heun (2006) Theoretical and Practical Improvements on the RMQ-Problem, with Applications to LCA and LCE. CPM 2006. Novší algoritmus na hľadanie najnižšieho spoločného predka, experimentálne porovnanie. pdf
- Alstrup, Stephen, Cyril Gavoille, Haim Kaplan, and Theis Rauhe. "Nearest common ancestors: A survey and a new algorithm for a distributed environment." Theory of Computing Systems 37, no. 3 (2004): 441-456. [1]
- Y. Xu, Y. Papakonstantinou (2007) Efficient LCA based keyword search in XML data. CIKM 2007: 1007-1010 pdf Vyhľadávanie v XML pomocou LCA.
- Hagai Cohen and Ely Porat (2010) Fast Set Intersection and Two-Patterns Matching. LATIN 2010. Pdf od vydavateľa Štruktúra na rýchlejšie hľadanie prienikov utriedených množín
- L. Heng, R. Durbin (2009): Fast and accurate short read alignment with Burrows-Wheeler transform. Bioinformatics 25(14): 1754-1760 pdf Aplikácia BWT v bioinformatike.
- Orlin, James B., et al. "A faster algorithm for the single source shortest path problem with few distinct positive lengths." Journal of Discrete Algorithms 8.2 (2010): 189-198. [2]
- Gonzalo Navarro, Yakov Nekrich: Optimal Dynamic Sequence Representations. SODA 2013: 865-876 [3]
- Holm, Jacob, Kristian De Lichtenberg, and Mikkel Thorup. "Poly-logarithmic deterministic fully-dynamic algorithms for connectivity, minimum spanning tree, 2-edge, and biconnectivity." Journal of the ACM (JACM) 48, no. 4 (2001): 723-760. pdf Ako udržiavať súvislé komponenty v dynamickom grafe. Dlhší článok, stačí naštudovať a prezentovať časť o súvislosti.
- Burcsi, Peter, Ferdinando Cicalese, Gabriele Fici, and Zsuzsanna Lipták. "Algorithms for jumbled pattern matching in strings." International Journal of Foundations of Computer Science 23, no. 02 (2012): 357-374. [4] Indexovanie textu aby sa dala vyhľadávať vzorka s permutovanými znakmi.
- Wild, Sebastian, and Markus E. Nebel. "Average case analysis of Java 7’s dual pivot quicksort." In Algorithms–ESA 2012, pp. 825-836. Springer Berlin Heidelberg, 2012. [5] Síce ide o triedenie a nie dátové štruktúry, ale tieto dve oblasti spolu úzko súvisia.
- Goel, Ashish, Sanjeev Khanna, Daniel H. Larkin, and Robert E. Tarjan. "Disjoint Set Union with Randomized Linking." SODA 2014 [6]
- Bender, Michael A., Roozbeh Ebrahimi, Jeremy T. Fineman, Golnaz Ghasemiesfeh, Rob Johnson, and Samuel McCauley. "Cache-Adaptive Algorithms." [7] Zovšeboecnenie modelu cache-oblivious algoritmov.
- Larkin, Daniel H., Siddhartha Sen, and Robert E. Tarjan. "A back–to–basics empirical study of priority queues." ALENEX 2014 [8]
Rady k hľadaniu článkov
- Podľa kľúčových slov sa články dobre hľadajú na Google Scholar. Tam okrem iného nájdete aj linky na iné články, ktoré daný článok citujú, čo môže byť dobrý zdroj ďalších informácií.
- The DBLP Computer Science Bibliography je dobrý zdroj bibtexových záznamov, ak píšete projekt alebo inú prácu v Latexu a tiež sa dá použiť na nájdenie zoznamu článkov od jedného autora alebo z jednej konferencie a podobne.
- ISI Web of Knowledge je oficiálna databáza hlavne časopiseckých článkov a citácií, prístupná z fakultnej siete. Menej pohodlná na použitie ako Google Scholar.
- Konferencie CPM a SPIRE sú dobrým zdrojom článkov o vyhľadávaní v texte, iné dátové štuktúry nájdete na všeobecných konferenciách pre teoretickú informatiku, napr STOC, FOCS, SODA. ESA. WADS, MFCS, ISAAC. Praktické implementácie sú námetom konferencií WAE a ALENEX.
Väčšina databáz má linky na elektronické verzie článkov u vydavateľa. Tam väčšinou uvidíte aspoň voľne prístupný abstrakt, ktorý vám pomôže rozhodnúť, či Vás článok zaujíma. Pre niektoré zdroje (napr. ACM, IEEE a ďalšie) je plný text článku prístupný z fakultnej siete. Z domu sa môžete prihlásiť cez univerzitný proxy (v prehliadači nastavte automatický konfiguračný skript http://www.uniba.sk/proxy.pac ). Celý text článku (pdf) sa v mnohých prípadoch dá nájsť na webe (napr. na webstránke autora). V najhoršom prípade, ak neviete zohnať článok, ktorý k projektu alebo prezentácii veľmi potrebujete, kontaktujte ma e-mailom a môžem sa pokúsiť ho zohnať.
