Wyniki wyszukiwania - BazTech

1

A parallel algorithm for the decomposition of finite languages

Jastrząb T., Czech Z. J.

Studia Informatica

|

2014

|

Vol. 35, nr 4

5--16

PL

Język skończony jest dekomponowalny, jeżeli może zostać zapisany jako złożenie dwóch niepustych języków. W niniejszym artykule zaproponowany został równoległy algorytm dekompozycji języków skończonych. Efektywność przedstawionego algorytmu została oceniona na podstawie eksperymentów przeprowadzonych dla wybranych języków.

EN

A finite language is said to be decomposable, if it can be written as a catenation of two non-empty languages. In this paper a parallel algorithm for finding the decomposition of finite languages is proposed. The effectiveness of the algorithm is assessed based on the experimental results provided for selected languages.

2

Adaptive threads co-operation schemes in a parallel heuristic algorithm for the vehicle routing problem with time windows

Nalepa J., Czech Z. J.

Theoretical and Applied Informatics

|

2012

|

Vol. 24, No. 3

191-203

EN

The influence of the co-operation frequency of threads in a parallel heuristic algorithm to solve the vehicle routing problem with time windows on the accuracy of solutions is investigated. The accuracy of solutions is defined as their proximity to the best known solutions of Gehring and Homberger's benchmarking tests. Two adaptive co-operation schemes are proposed and experimentally evaluated.

PL

Wyznaczanie tras dla pojazdów z oknami czasowymi (ang. vehicle routing problem with time windows) jest problemem optymalizacji dyskretnej należącym do klasy problemów NP-trudnych. Istnieją metody heurystyczne rozwiązywania problemu, pozwalające wyznaczyć w rozsądnym czasie rozwiązania nieoptymalne o koszcie bliskim kosztowi rozwiązania optymalnego, takie jak symulowane wyżarzanie, przeszukiwanie tabu, algorytmy genetyczne czy algorytmy memetyczne. Wprzypadku algorytmów dwustopniowych, w pierwszej fazie minimalizowana jest liczba tras, a w fazie drugiej całkowita przebyta odległość. Flota składa się z pojazdów o jednakowej, zdefiniowanej pojemności, która nie może zostać przekroczona, a obsługa klientów musi rozpocząć się w czasie trwania ich okien czasowych.

3

Randomized PRAM simulation

Czech Z.J., Mikanik W.

Fundamenta Informaticae

|

1998

|

Vol. 36, nr 4

317-336

EN

The parallel random access machine (PRAM) is the most commonly used general-purpose machine model for describing parallel computations. Unfortunately the PRAM model is not physically realizable, since on large machines a parallel shared memory access can only be accomplished at the cost of a significant time delay. A number of PRAM simulation algorithms are known. The algorithms allow execution of PRAM programs on more realistic parallel machines. We study the randomized simulation of an exclusive read, exclusive write (EREW) PRAM on a module parallel computer (MPC). The simulation is based on utilizing universal hashing. The optimally efficient simulation involving parallel slackness is also investigated. The results of our experiments performed on the MPC built upon IMS T9000 transputers throw some light on the question whether using the PRAM model in parallel computations is practically viable given the present state of transputer technology.