Wyniki wyszukiwania - BazTech

Ograniczanie wyników

Powiadomienia systemowe

Sesja wygasła!

Znaleziono wyników: 2

Liczba wyników na stronie

Wyniki wyszukiwania

Wyszukiwano:
w słowach kluczowych: longest increasing subsequence

Sortuj według:

Ogranicz wyniki do:

On Some Variants of the Longest Increasing Subsequence Problem

Deorowicz S.

Theoretical and Applied Informatics

2009

Vol. 21, No. 3-4

135-148

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.

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.

Layering of the Poisson process in the quadrant

Levikson B., Rolski T., Weiss G.

Probability and Mathematical Statistics

2001

Vol. 21, Fasc. 2

417--440

We consider the increasing sequence of non-intersecting monotone decreasing step processes Y*n(t), n = 1, 2,...(t > 0), whose jump points cover all the points of the homogeneous rate 1 Poisson process on the quadrant R2+. We deriveproperties of these processes, in particular the marginal distributions P(Y*n(t) > x), in terms of a Toeplitz determinant of some modified Bessel functions. Our system provides a new view of the Hammersley interacting particle system discussed by Aldousand Diaconis, and the distributions we derive are related tothe distribution of the length of the longest ascending sequence in a random permutation.