četrtek, 26. september 2013 Seminar MARA

V ponedeljek, 30. septembra 2013, bodo ob 16.00  uri v prostorih Fakultete za matematiko, naravoslovje in informacijske tehnologije Univerze na Primorskem, Glagoljaška 8, Koper predavanja v okviru skupnega SEMINARJA ZA MATEMATIČNE IN RAČUNALNIŠKE ZNANOSTI Oddelka za matematiko in Oddelka za Informacijske znanosti in tehnologije UP FAMNIT, Oddelka za matematiko in Oddelka za Informacijske znanosti in tehnologije UP IAM, Oddelka za matematiko in računalništvo UP PEF ter Oddelkov za matematiko in teoretično računalništvo IMFM.

RAČUNALNIŠKI SEMINAR

Prostor: FAMNIT-1-RU1 ob 16:00

Predavatelj: Jasna Lenar

Naslov: Pregled paralelizacije statističnih metod

Povzetek:
Statistične metode so splošno uporabne na številnih znanstvenih področjih, med drugim v podatkovnem rudarjenju, strojnem učenju in razpoznavanju vzorcev. Vsa področja, kjer uporabljamo statistične metode so praviloma računsko in podatkovno zahtevna, zato se znanstveniki in razvijalci programske opreme intenzivno ukvarjajo z razvojem novih vzporednih programskih rešitev. Razvoj gre tako v smeri iskanja splošnih rešitev za večje število problemov, kot tudi specializiranih rešitev za posamezna področja izvajanja, ki imajo svoje značilnosti in omejitve.
Predstavili bomo osnovne značilnosti statističnih algoritmov. Razvrstili jih bomo glede na to, kako učinkovito jih lahko paraleliziramo. Opisali bomo, katere so tiste skupne značilnosti, ki nam omogočajo razvoj splošnih rešitev za večje število problemov.
Predstavili bomo tudi najnovejše znanstvene prispevke na tem področju in najbolj pogosto uporabljene programske rešitve.

Predavatelj: Marko Grgurovič

Naslov: Using trees to speed up the Floyd-Warshall algorithm

Povzetek:
We present a combination of the Floyd-Warshall algorithm with a  hourglass-like tree structure, which reduces the number of path  combinations that have to be examined. Only those path combinations that provably cannot change the values in the shortest path matrix are omitted.  The resulting algorithm is simple to implement, uses no fancy data  structures and, in our tests, is faster than the Floyd-Warshall algorithm  for random complete graphs on 256-4096 nodes by factors ranging from  2.5-8.5x. When we inspect the number of path combinations examined  however, our modification reduces the amount by a staggering factor of  12-90x.

Naslov: Adaptive Algorithms for Dynamic Programming with Applications to Bioinformatics

Povzetek:
In the talk we consider a simple computation that lies at the core  of many dynamic programming algorithms, perhaps most notably those for  computing the edit distance between two strings. Past solutions have  assumed properties of the input function such as convexity and concavity and would not work on general inputs. We present an algorithm that  combines the previous algorithms in a way that makes no assumptions on the  input, yet its running time depends on a measure of ``sortedness'' present  in the input. This measure turns out to be very natural, and if the input  comes from a function, it corresponds to the number of inflection points  of the input function. An immediate consequence of the result is that if  the input comes from a polynomial of degree d, then the running time of  the algorithm can be upper bounded by a function of d. The new algorithm  extends the previous results to a wider family of functions and is never  worse than either special cases.

Vabljeni!