Wyniki wyszukiwania - BazTech

1

Fluid motion modelling using vortex particle method on GPU

Rogulski Ł., Deorowicz S.

Studia Informatica

|

2013

|

Vol. 34, nr 1

31--48

EN

In this paper we present the vortex-in-cell method aimed at graphic processor units. Inviscid fluid model is examined in domain with periodic boundary conditions. The leap-frogging vortex rings simulation results are presented with sample vortex rings collision visualization. At the end the GPU solver performance advantage over CPU solver is presented.

PL

W pracy prezentujemy metodę obliczeniową wir-w-komórce zaimplementowaną na układach graficznych. Za model ośrodka został przyjęty płyn nielepki wraz z periodycznymi warunkami brzegowymi. W pracy przedstawiono wyniki symulacji dla gry wirów oraz przykładowe wizualizacje z wykorzystaniem cząsteczek markerów. Pod koniec została przedstawiona analiza uzyskanego przyspieszenia algorytmu na GPU względem wersji na CPU.

2

Sekwencyjne i równolegle algorytmy znajdowania podciągów

Deorowicz S.

Studia Informatica

|

2010

|

Vol. 31, nr 4B

239-239

PL

Pierwsza cześć niniejszej pracy poświęcona jest problemowi najdłuższego podciągu rosnącego (LIS) oraz jego wariantom (podciąg otrzymuje sie z ciągu przez usuniecie zera bądź większej liczby symboli). Problem ten znajduje zastosowania m.in. w bioinformatyce do uliniawiania genomów, wyszukiwania nowych genów. Pierwszym z wariantów problemu LIS rozważanym w niniejszej pracy jest problem podciągów rosnących, które są pod pewnymi względami ekstremalne. Kolejnym wariantem jest problem podciągu rosnącego o zadanym pochyleniu. Dalsze dwa warianty to problemy cyklicznych podciągów rosnących oraz podciągów rosnących w oknie ustalonego rozmiaru ciągu wejściowego. Dla tych ostatnich wariantów zaproponowano w pracy wykorzystanie reprezentacji ciągu za pomocą pokrycia zachłannego oraz opracowano wydajne algorytmy łączenia takich pokryć. Algorytmy te są kluczowe do efektywnego rozwiązywania wspomnianych problemów. Druga cześć pracy dotyczy problemu najdłuższego wspólnego podciągu i jego wariantów. Zastosowania tych problemów są bardzo liczne i dotyczą przede wszystkim porównywania ciągów w celu oceny ich podobieństwa. Dla problemu LCS niezmienniczego względem transpozycji LCTS) zaproponowano kilka algorytmów sekwencyjnych, które, jak wynika z eksperymentów praktycznych, okazały sie znacznie szybsze od algorytmów istniejących. Dla problemu ukierunkowanego LCS (CLCS) zaproponowano algorytmy sekwencyjne, również szybsze od dotychczas istniejących. Ponadto, zaproponowano dla tego problemu pierwszy algorytm równoległości bitowej. Dla problemu scalonego LCS (MerLCS) zaproponowano pierwszy algorytm równoległości bitowej, który w eksperymentach praktycznych okazał sie kilkudziesięciokrotnie szybszy od znanych algorytmów. Dla problemów LCS, LCTS, CLCS zaproponowano także algorytmy równoległe przeznaczone do wykonywania w procesorach graficznych. Dla wszystkich algorytmów proponowanych w niniejszej pracy przeprowadzono analizę złożoności czasowej i pamięciowej w przypadku pesymistycznym(dla niektórych także w przypadku średnim). Dzięki temu często można było wykazać, ze proponowane algorytmy są także najszybsze w sensie asymptotycznym.

EN

The first part of this work is on the longest increasing subsequence problem (LIS) and its variants (a subsequence can be obtained from a sequence by removing zero or more symbols). The problem has applications in bioinformatics, e.g., in sequence alignment, searching new genes. The first variant of the LIS problem, which is considered in this work, is a problem of longest increasing subsequences that are extremal from some point of view. Next variant is a slope-constrained longest increasing subsequence problem. The last two discussed variants of the LIS problem are a longest increasing cyclic subsequence problem (LICS) and a longest increasing subsequence in a sliding window problem (LISW). The algorithms for the recent two problems use cover representation of a sequence. Original algorithms for cover merging are crucial to the proposed algorithms for the LICS and LISW problems. The second part of this work is on the longest common subsequence problem (LCS) and its variants. The applications of these problems are numerous and concentrate mainly on the sequence comparison. For the transposition-invariant LCS problem (LCTS), a few sequential algorithms were proposed. Experiments show that they are much faster than the existing algorithms. For the constrained LCS problem (CLCS), a few sequential algorithms were also proposed. They are faster than the known algorithms. Moreover, for the CLCS problem, the first bit-parallel algorithm was invented. For the merged LCS problem (MerLCS), a bit parallel algorithm, tens times faster than the existing algorithms was proposed. For the LCS, LCTS, CLCS problems also algorithms for graphical processors were invented. All the proposed algorithms were analysed and their time and space complexities in the worst case were determined. For some algorithms the average case was also analysed. Obtained time complexities allow to show that the proposed algorithms are usually faster than the existing algorithms also in an asymptotic sense.

3

Bit-Parallel Algorithm for the Constrained Longest Common Subsequence Problem

Deorowicz S.

Fundamenta Informaticae

|

2010

|

Vol. 99, nr 4

409-433

EN

The problem of finding a constrained longest common subsequence (CLCS) for the sequences A and B with respect to the sequence P was introduced recently. Its goal is to find a longest subsequence C of A and B such that P is a subsequence of C. Most of the algorithms solving the CLCS problem are based on dynamic programming. Bit-parallelism is a technique of using single bits in a machine word for concurrent computation. We propose the first bit-parallel algorithm computing a CLCS and/or its length which outperforms the other known algorithms in terms of speed.

4

On Some Variants of the Longest Increasing Subsequence Problem

Deorowicz S.

Theoretical and Applied Informatics

|

2009

|

Vol. 21, No. 3-4

135-148

EN

The problem of finding a longest increasing subsequence (LIS) is a well known task in sequence processing. There are many variants of the basic task. We discuss a recently introduced variant of LIS, a minimal height longest increasing subsequence problem and propose a new algorithm for it, which improves its time complexity. Moreover, we define a family of similar problems and introduce algorithms solving them.

PL

Problem wyznaczania najdłuższego rosnącego podciągu (ang. longest increasing subsequence, LIS) jest jednym z problemów w przetwarzaniu ciągów. W artykule dyskutowany jest jeden z jego wariantów, a mianowicie problem wyznaczania najdłuższego rosnącego podciągu o minimalnej wysokości. Zaprezentowany algorytm dla tego problemu oferuje złożoność czasową lepsza niż najszybszy opisany do tej pory w literaturze algorytm. Ponadto w pracy zdefiniowano rodzinę podobnych problemów, dla których zaproponowano optymalne algorytmy ich rozwiazywania.

5

Fast algorithm for the constrained longest common subsequence problem

Deorowicz S.

Theoretical and Applied Informatics

|

2007

|

Vol. 19, No. 2

91-102

EN

The problem of finding the constrained longest common subsequence (CLCS) for the sequences A and B with respect to the sequence P was introduced recently. Its goal is to find the longest subsequence of A and B such that P is a subsequence of it. The best known algorithms for its solving require time of order of a product of the sequence lengths. We introduce a novel approach in which time and space complexities depend also on the number of matches between A, B, and P. The time complexity is better for typical parameter settings and never worse.

PL

Problem wyznaczania najdłuższego wspólnego podciągu ciągów A i B, którego podciągiem jest podciąg P (CLCS) pojawił się˛ literaturze stosunkowo niedawno. Złożoności obliczeniowe najlepszych znanych algorytmów są˛ iloczynem długości wszystkich ciągów. W niniejszej pracy przedstawione jest nowy algorytm rozwiązywania tego problemu, dla którego złożoność´ obliczeniowa zależy od liczby dopasować pomiędzy ciągami A, B i P. Złożoność´ ta jest zwykle lepsza (a nigdy gorsza) niż najlepszych znanych do tej pory algorytmów.

6

Web log compression

Grabowski S., Deorowicz S.

Automatyka / Akademia Górniczo-Hutnicza im. Stanisława Staszica w Krakowie

|

2007

|

T. 11, z. 3

417-424

EN

Web log data store client activity on a particular server, usually in form of one-line "hits" with information like the client's IP, date/ time, requested file or query, download size in bytes etc. Web logs of popular sites may grow at the pace of hundreds of megabytes a day, or even more. It makes sense to archive old logs, to analyze them further, e.g. for detecting attacks or other server abuse patterns. In this work we present a specialized lossless Apache web log preprocessor and test it with combination of several popular general-purpose compressors. The test results show the proposed transform improves the compression efficiency of general-purpose compressors on average by 65% in case of gzip and 52% in case of bzip2.

PL

Pliki z logami webowymi przechowują zapis aktywności klientów na danym serwerze, zwykle w formie jednolinijkowych wpisów zawierających informacje typu: numer IP maszyny klienta, data/czas dostępu do danego zasobu, rozmiar ściągniętego pliku w bajtach etc. Dane te, na popularnych serwerach www, mogą przyrastać w tempie setek megabajtów na dzień lub nawet wyższym. Archiwizacja "starych" logów jest jednak zalecana, głównie w celu ich analizy, np. mającej na celu wykrywanie ataków sieciowych i nietypowych (niepożądanych) wzorców zachowań. W niniejszej pracy przedstawiamy specjalizowany, zorientowany na kompresję, preprocesor dla logów serwera Apache i testujemy jego efektywność w połączeniu z kilkoma popularnymi kompresorami ogólnego przeznaczenia. Wyniki eksperymentów pokazują, że zaproponowana transformata poprawia efektywność kompresji o 65% (tj. 3-krotnie) w przypadku gzipa oraz o 52% w przypadku kompresora bzip2.

7

Correcting Spelling Errors by Modelling Their Causes

Deorowicz S., Ciura M. G.

International Journal of Applied Mathematics and Computer Science

|

2005

|

Vol. 15, no 2

275-285

EN

This paper accounts for a new technique of correcting isolated words in typed texts. A language-dependent set of string substitutions reflects the surface form of errors that result from vocabulary incompetence, misspellings, or mistypings. Candidate corrections are formed by applying the substitutions to text words absent from the computer lexicon. A minimal acyclic deterministic finite automaton storing the lexicon allows quick rejection of nonsense corrections, while costs associated with the substitutions serve to rank the remaining ones. A comparison of the correction lists generated by several spellcheckers for two corpora of English spelling errors shows that our technique suggests the right words more accurately than the others.