Proseminár z informatiky  2-INF-169

Predmet je určený pre študentov, ktorí majú záujem o prehĺbenie si vedomostí z (prevažne teoretickej) informatiky formou samoštúdia a prezentácií.

Vyžaduje sa, aby účastníci počas semestra naštudovali niekoľko (1-2) tém a následne ich odprezentovali kolegom. Jedna prezentácia zvyčajne pokrýva výsledky z odborného článku, doplnené o vysvetlenie potrebných referencovaných výsledkov.

V zimnom semestri 2014 sa semináre konajú v pondelok o 11:30 v akváriu VI.

Ak máte ( k predmetu ) akékoľvek otázky neváhajte nás kontaktovať (najlepšie mailom).

18. 11. 2015

Dynamic graph connectivity in polylogarithmic worst case time

Ladislav Papay
Bruce M. Kapron, Valerie King, Ben Mountjoy: Dynamic graph connectivity in polylogarithmic worst case time. SODA 2013
materiály
  kapron_dynamicGraphConnectivity.pdf
04. 05. 2015

Introduction to the Burrows-Wheeler Transform and FM Index

Ján Hozza
Podľa článku: Ben Langmead: Introduction to the Burrows-Wheeler Transform and FM Index
materiály
  bwt_fm.pdf
06. 04. 2015

Minimum and maximum against k lies

Ján Hozza
podľa článku: Michael Hoffmann, Jiří Matoušek, Yoshio Okamoto, Philipp Zumstein: Minimum and maximum against k lies. arXiv:1002.0562
materiály
  minMaxAgainsLies.pdf
01. 12. 2014

Smoothed complexity

Rasťo Královič
- krátka rekapitulácia lineárneho programovania a simplexového algoritmu
- simplexový algoritmus je exponenciálny v najhoršom prípade
- polynomial smoothed analysis (výsledok Speilman, Teng)
materiály
  Spielman, Teng: Smoothed Analysis (tech report)
  Desphande, Spielman: Improved proof (FOCS 06)
10. 11. 2014

testovnie prvočíslenosti - krátky ceftifikát(a nedeterminizmus), malý alternujúci priestor pri unárnom vstupe

Dana Pardubská
Podľa článkov:

Vaughan R. Pratt: Every prime has a succinct certificate. SIAM J. Comp. Vol.4, No.3, 1975

Viliam Geffert, Dana Pardubska: Factoring and testing primes in small space. RAIRO-Theor. Inf. Appl. 47 (2013)

materiály
  primesCertificatePratt.pdf
  primesGefPard.pdf
03. 11. 2014

O násobení matíc

Dana Pardubská
Podľa článkov

I.Korec a J.Wiedermann: Deterministic Verification of Integer Matrix Multiplication in Quadratic Time (SOFSEM 2014, LNCS 8327, pp. 375-382)

J.Wiedermann: Fast Nondeterministic Matrix Multiplication via Derandomization of Freivalds' Algorithm (TCS 2014, LNCS 8705, pp. 123-135)

materiály
  I.Korec a J.Wiedermann
  J.Wiedermann
28. 10. 2014

L(2,1) labelling

Anna Dresslerová
13. 10. 2014

Hashovanie a spol.

Ján Hozza
Ako konštruovať hashovacie funkcie, ako riešiť kolízie a pod.
29. 09. 2014

Space-Efficient Randomized Algorithms for K-SUM

Michal Anderle
Prezentácia podľa článku z ESA 2014.
materiály
  J. R. Wang: Space-Efficient Randomized Algorithms for K-SUM, ESA 2014