Ponedeljkov seminar računalništva in informatike - Arhiv

petek, 29. junij 2012 Seminar MARA

V ponedeljek, 2. julija 2012, 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

16.00 - predavatelj: Staš Bevc

Naslov: ESPResSo++: program za simulacije sistemov mehke snovi

Povzetek:
Prenovljeni Extensible simulation package for research on soft matter systems (ESPResSo++) je sodoben programski paket za izvajanje simulacij molekularne dinamike mehke snovi. Eden od glavnih ciljev pri razvoju programa je razširljivost, zaradi česar je jedro programa napisano modularno z uporabo objektno usmerjenega programiranja. Raziskovalci lahko ESPResSo++ uporabljajo kot raziskovalno okolje za razvoj in preizkušanje lastnih metodoloških pristopov.
Na predavanju bom predstavil program ESPResSo++, potek razvoja, organizacijo kode, način
paralelizacije ter nekaj preprostih primerov simulacij.

16.30 - predavatelj: Kati Rozman

Naslov: PARALLEL-PROBIS: Hitri vzporedni algoritem za lokalno strukturno primerjavo proteinskih struktur in vezavnih mest

Povzetek:
Predstavili bomo nov vzporedni algoritem ProBiS za iskanje podobnih vezavnih mest na proteinih. S tem algoritmom računamo lokalne podobnosti med proteinskimi strukturami na gruči večprocesorskih računalnikov. Največje izboljšanje algoritma opazimo pri proteinih z okoli 600 aminokislinami. V tem primeru je pohitritev računanja za 180. Računanje porazdelimo med dve med seboj povezani gruči računalnikov skupaj z 248 računalniškimi jedri. Računalniški program Parallel ProBiS je za akademsko uporabo prosto dostopen na naslovu  http://probis.cmm.ki.si/download.

17.00 - predavatelj: Marko Grgurovič

Naslov: Parallel Ant System

Povzetek:
We study the parallel case of the ant system algorithm solving the traveling salesman problem. Following series of recent results for the graphics processing unit model, we show that they translate to the parallel random access machine model. In addition, we introduce a novel method for updating the pheromone matrix without atomic instructions, which is an improvement over the currently best known non-atomic update method. As an immediate consequence, we give new asymptotic bounds for the parallel ant system. We also present an empirical comparison with the currently known approaches to pheromone matrix update. For the empirical study we implement our results on the graphics processing unit.

17.30 - predavatelj: Marko Grgurovič

Naslov: Speeding up shortest path algorithms

Povzetek:
Given an arbitrary non-negatively weighted graph $G=(V,E)$ we present an algorithm that computes all pairs shortest paths in time $\mathcal{O}(m^* n + m \lg n + nT_\psi(m^*, n))$, where $m^*$ is the number of different edges contained in shortest paths and $T_\psi(m^*, n)$ is a running time of an algorithm to solve a single-source shortest path problem (SSSP). This is a substantial improvement over a trivial $n$ times application of $\psi$ that runs in $\mathcal{O}(nT_\psi(m,n))$. In our algorithm we use $\psi$ as a black box and hence any improvement on $\psi$ results also in improvement of our
algorithm.
Furthermore, a combination of our method, Johnson's reweighting technique, breadth-first search and topological sorting results in an $\mathcal{O}(m^*n + m \lg n)$ all-pairs shortest path algorithm for arbitrarily-weighted directed acyclic graphs.
In addition, we also point out a connection between the complexity of a certain sorting problem defined on shortest paths and SSSP.

Vabljeni!