Azərbaycanca AzərbaycancaБеларускі БеларускіDansk DanskDeutsch DeutschEspañola EspañolaFrançais FrançaisIndonesia IndonesiaItaliana Italiana日本語 日本語Қазақ ҚазақLietuvos LietuvosNederlands NederlandsPortuguês PortuguêsРусский Русскийසිංහල සිංහලแบบไทย แบบไทยTürkçe TürkçeУкраїнська Українська中國人 中國人United State United StateAfrikaans Afrikaans
Підтримка
www.wikidata.uk-ua.nina.az

В інформатиці задача про найдовшу зростаючу підпослідовність полягає у пошуку підпослідовності даної послідовності в які

Задача про найдовшу зростаючу підпослідовність

Задача про найдовшу зростаючу підпослідовність

В інформатиці задача про найдовшу зростаючу підпослідовність полягає у пошуку підпослідовності даної послідовності, в якій елементи підпослідовності розташовані в порядку зростання, тобто, кожен наступний елемент підпослідовності більше попереднього, також, підпослідовність є якомога довшою. Шукана послідовність не обов'язково є неперервною або єдиною. Найбільш довгі зростаючи підпослідовності вивчаються у різних дисциплінах, пов'язаних з математикою, включаючи алгоритміку, теорію випадкових матриць, теорію представлень та фізику. Задача про найдовшу зростаючу підпослідовність розв'язується за час O (n log n), де n — довжина вхідної послідовності.

Приклад

У перших 16 членах двійкової [en]

0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15

найдовша зростаюча підпослідовність

0, 2, 6, 9, 11, 15.

Ця підпослідовність має довжину шість, що є максимальним значенням, бо вхідна послідовність не має зростаючих підпослідовностей із семи елементів. Найдовша зростаюча підпослідовність у цьому прикладі має декілька розв'язків. Наприклад,

0, 4, 6, 9, 11, 15
0, 2, 6, 9, 13, 15
0, 4, 6, 9, 13, 15.

Це різні зростаючі підпослідовності однакової довжини в одній і тій же вхідній послідовності.

Зв'язок з іншими алгоритмічними задачами

Задача найдовшої зростаючого підпослідовності тісно пов'язана з найдовшою спільною підпослідовністю, яка розв'язується за допомогою динамічного програмування за квадратичний час: найдовша зростаюча підпослідовність послідовності S є найдовшою загальною підпослідовністю S і T, де T — результат [en]S . Однак для окремого випадку, коли вхідними даними є перестановка цілих чисел 1, 2, …, n, цей підхід можна зробити набагато ефективнішим, так, щоб він виконувався за час O(n log log n).

Найбільша кліка в графі перестановки відповідає найдовшій спадній підпослідовності перестановки, яка визначає граф (припускаючи, що вихідна послідовність без перестановок сортується від найменшого значення до найбільшого). Подібним чином, максимальна [en] в графі перестановок відповідає найдовшій неспадній підпослідовності. Тому найефективніші алгоритми пошуку зростаючої підпослідовності можуть бути використані для ефективного вирішення задачі про кліку в графах перестановки.

У [en] між перестановками і таблицями Юнга довжина першого рядка таблиці, що відповідає перестановці, дорівнює довжині найбільшої зростаючої підпослідовності перестановки, а довжина першого стовпця дорівнює довжині найдовшої спадної підпослідовністі.

Ефективні алгоритми

Викладений нижче алгоритм ефективно вирішує задачу про найдовшу зростаючу підпослідовність за допомогою масивів та двійкового пошуку. Він обробляє елементи послідовності один за одним, відповідно до їх порядку, при цьому підтримується найдовша зростаюча підпослідовність, знайдена на цей момент. Позначимо значення вхідної послідовності як X[0], X[1], тощо. Потім, після обробки чергового X[i], алгоритм буде зберігати значення у двох масивах:

M[j] — зберігає індекс k найменшого значення X[k], яке є останнім у зростаючий підпослідовністі довжини j, що закінчується значенням X[k] (k ≤ i, рівність можлива тільки коли входовий масив до індексу i є зростаючим). Зверніть увагу, що j ≤ (i + 1), оскільки j ≥ 1 є довжиною зростаючої підпослідовності, а k ≥ 0 — це індекс в масиві X її останнього елементу.
P[k] — зберігає індекс в масиві X, який йде перед останнім елементом X[k] у найдовшій зростаючій послідовності, що закінчується на X[k].

Крім того, алгоритм зберігає змінну L, яка представляє довжину найдовшої зростаючої підпослідовності, знайденого на поточний момент. Оскільки наведений нижче алгоритм використовує нумерацію від нуля, для ясності M доповнюється елементом M[0], який не використовується, тим самим M[j] відповідає послідовності довжини j. Конкретна реалізація може не залучати M[0] і відповідно індекси буде скорегувано.

Зверніть увагу, що в будь-який момент виконання алгоритму послідовність: X[M[1]], X[M[2]], …, X[M[L]]

є зростаючою. Бо, якщо існує зростаюча підпослідовність довжини j ≥ 2, що закінчується в X[M[j]], то існує також підпослідовність довжини j-1, що закінчується на меншому значенні: а саме та, яка закінчується в X[P[M[j]]]. Таким чином, ми можемо виконувати двійковий пошук в цій послідовності за логарифмічний час.

Тоді алгоритм працює наступним чином:

image
Демо-версія коду.
P = масив довжини N M = масив довжини N + 1 L = 0 L = 0 for i in range 0 to N-1: // Двійковий пошук найбільшого додатного j ≤ L // такого, що X[M[j]] < X[i] lo = 1 hi = L while lo ≤ hi: mid = ceil((lo+hi)/2) if X[M[mid]] < X[i]: lo = mid+1 else: hi = mid-1 // Після пошуку, lo на 1 більше, ніж // довжина найдовшого префіксу X[i] newL = lo // Попередник X[i] є останнім індексом // підпослідовності довжини newL-1 // The predecessor of X[i] is the last index of // the subsequence of length newL-1 P[i] = M[newL-1] M[newL] = i if newL > L: // Якщо ми знайшли підпослідовність довшу // за будь-яку зі знайдених, то оновимо L L = newL // Реконструюємо найдовшу зростаючу підпослідовність S = масив довжини L k = M[L] for i in range L-1 to 0: S[i] = X[k] k = P[k] return S

Оскільки алгоритм виконує один двійковий пошук на кожен елемент послідовності, його загальний час виконання можна виразити позначенням Big O, як O (n log n). Fredman, (1975) обговорює варіант цього алгоритму, який він приписує Дональду Кнуту. У варіанті, який він досліджував, алгоритм перевіряє, чи кожне значення X[i] може бути використано для продовження поточної найдовшої послідовності, що збільшується, за сталий час, перед виконанням двійкового пошуку. За допомогою цієї модифікації алгоритм використовує щонайбільше n log2n − n log2log2n + O(n) порівнянь в найгіршому випадку, що є оптимальним для алгоритму, заснованого на порівнянні, з точністю до сталого коефіцієнта в O(n).

Межі довжини

Відповідно до теореми Ердеша — Секереша, будь-яка послідовність n2+1 різних цілих чисел має зростаючу або спадну підпослідовність довжини n + 1. Для входів, в яких кожна перестановка очікується з однаковою ймовірністю, очікувана довжина найдовшої зростаючої підпослідовності становить приблизно 2√n. Коли n наближається до нескінченності, тоді граничне значення довжини найбільшої зростаючої підпослідовності випадково переставленої послідовності з n елементів має розподіл, що наближається до [en], розподілу найбільшого власного значення випадкової матриці в (універсальному гауссовому ансамблі).

Онлайн-алгоритми

Найдовша зростальна підпослідовність також досліджувалась з використанням онлайн-алгоритмів, в яких елементи послідовності незалежних випадкових величин із неперервним розподілом F, або, як варіант, елементи випадкової перестановки — подаються по одному елементу до алгоритму, який повинен вирішити, включити чи виключити кожен елемент, не маючи інформації про елементи, які надійдуть згодом. У цьому варіанті задачі, який передбачає цікаве застосування у декількох контекстах, можна розробити оптимальну процедуру відбору, яка, беручи до уваги випадкову вибірку розміром n, буде генерувати зростальну послідовність із максимально очікуваною довжиною розміру приблизно √2n. Довжина зростальної підпослідовності, відібрана за цією оптимальною процедурою, має дисперсію, приблизно рівну √2n/3, і її граничний розподіл асимптотично нормальний після звичайного центрування та масштабування. Ті самі асимптотичні результати мають більш точні межі для відповідної задачі в умовах Пуассонівського процесу. Подальше уточнення у випадку Пуассонівського процесу, відбувається через доведення центральної граничної теореми для оптимального процесу вибору з відповідною нормалізацією у більш повному сенсі, ніж можна було б очікувати. Доведення дає не тільки «правильну» функціональну граничну теорему, але також (сингулярну) матрицю коваріації тривимірного процесу, що узагальнює всі взаємодійні процеси.

Застосування

  • Частина системи [en] (Maximum Unique Match finder) для вирівнювання цілих геномів.
  • Використовується в системах контролю версій, таких як Git тощо.
  • Використовується в Patience Diff, алгоритмі різниці (обчислює та відображає різницю між вмістом файлів), який використовується у «Bazaar» (Bazaar — це система контролю версій, яка допомагає вам відстежувати історію проекту з часом та легко співпрацювати з іншими)

Див. також

  • [en], ефективний метод визначення довжини найбільшої зростаючої підпослідовності
  • [en], алгебраїчна система, що визначається перетвореннями, які зберігають довжину найдовшої зростаючої підпослідовності
  • Анатолій Вершик, російський математик, який вивчав застосування теорії груп до найдовших зростаючих підпослідовностей
  • Найдовша спільна підпослідовність
  • [en]

Примітки

  1. ; (1999), Longest increasing subsequences: from patience sorting to the Baik–Deift–Johansson theorem, Bulletin of the American Mathematical Society, 36 (04): 413—432, doi:10.1090/S0273-0979-99-00796-X
  2. (1961), Longest increasing and decreasing subsequences, , 13: 179—191, doi:10.4153/CJM-1961-015-3, MR 0121305
  3. Hunt, J.; Szymanski, T. (1977), A fast algorithm for computing longest common subsequences, Communications of the ACM, 20 (5): 350—353, doi:10.1145/359581.359603
  4. (1980), Algorithmic Graph Theory and Perfect Graphs, Computer Science and Applied Mathematics, Academic Press, с. 159
  5. (1975), On computing the length of longest increasing subsequences, Discrete Mathematics, 11 (1): 29—35, doi:10.1016/0012-365X(75)90103-X
  6. Erdős, Paul; Szekeres, George (1935), , Compositio Mathematica, 2: 463—470, архів оригіналу за 19 лютого 2019, процитовано 21 липня 2021
  7. (1995), Variations on the monotone subsequence theme of Erdős and Szekeres, у ; ; та ін. (ред.), (PDF), IMA Volumes in Mathematics and its Applications, т. 72, Springer-Verlag, с. 111—131, архів оригіналу (PDF) за 11 червня 2019, процитовано 21 липня 2021
  8. Vershik, A. M.; Kerov, C. V. (1977), Asymptotics of the Plancheral measure of the symmetric group and a limiting form for Young tableaux, Dokl. Akad. Nauk SSSR, 233: 1024—1027
  9. Baik, Jinho; Deift, Percy; Johansson, Kurt (1999), On the distribution of the length of the longest increasing subsequence of random permutations, Journal of the American Mathematical Society, 12 (4): 1119—1178, arXiv:math/9810105, doi:10.1090/S0894-0347-99-00307-0.
  10. Samuels, Stephen. M.; (1981), Optimal Sequential Selection of a Monotone Sequence From a Random Sample (PDF), Annals of Probability, 9 (6): 937—947, doi:10.1214/aop/1176994265{{}}: Обслуговування CS1: Сторінки з параметром url-status, але без параметра archive-url ()
  11. Arlotto, Alessandro; Nguyen, Vinh V.; (2015), Optimal online selection of a monotone subsequence: a central limit theorem, Stochastic Processes and their Applications, 125 (9): 3596—3622, arXiv:1408.6750, doi:10.1016/j.spa.2015.03.009
  12. ; Delbaen, Freddy (2001), Optimal rules for the sequential selection of monotone subsequences of maximum expected length, Stochastic Processes and their Applications, 96 (2): 313—342
  13. ; Delbaen, Freddy (2004), A central limit theorem for the optimal selection process for monotone subsequences of maximum expected length, Stochastic Processes and their Applications, 114 (2): 287—311, doi:10.1016/j.spa.2004.09.002

Посилання

  • Найдовша зростаюча підпослідовність на сайті Algorithmist [ 30 квітня 2010 у Wayback Machine.] (англ.)
  • Спрощена найдовша зростаюча підпослідовність [ 1 жовтня 2017 у Wayback Machine.] (англ.)
  • Обчислення кількості найдовших зростаючих підпослідовностей [ 21 липня 2021 у Wayback Machine.] (англ.)
  • Poldo's diet [ 1 жовтня 2017 у Wayback Machine.] (італ.)

Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри, мобільний, телефон, android, ios, apple, мобільний телефон, samsung, iphone, xiomi, xiaomi, redmi, honor, oppo, nokia, sonya, mi, ПК, web, Інтернет

V informatici zadacha pro najdovshu zrostayuchu pidposlidovnist polyagaye u poshuku pidposlidovnosti danoyi poslidovnosti v yakij elementi pidposlidovnosti roztashovani v poryadku zrostannya tobto kozhen nastupnij element pidposlidovnosti bilshe poperednogo takozh pidposlidovnist ye yakomoga dovshoyu Shukana poslidovnist ne obov yazkovo ye neperervnoyu abo yedinoyu Najbilsh dovgi zrostayuchi pidposlidovnosti vivchayutsya u riznih disciplinah pov yazanih z matematikoyu vklyuchayuchi algoritmiku teoriyu vipadkovih matric teoriyu predstavlen ta fiziku Zadacha pro najdovshu zrostayuchu pidposlidovnist rozv yazuyetsya za chas O n log n de n dovzhina vhidnoyi poslidovnosti PrikladU pershih 16 chlenah dvijkovoyi en 0 8 4 12 2 10 6 14 1 9 5 13 3 11 7 15 najdovsha zrostayucha pidposlidovnist 0 2 6 9 11 15 Cya pidposlidovnist maye dovzhinu shist sho ye maksimalnim znachennyam bo vhidna poslidovnist ne maye zrostayuchih pidposlidovnostej iz semi elementiv Najdovsha zrostayucha pidposlidovnist u comu prikladi maye dekilka rozv yazkiv Napriklad 0 4 6 9 11 15 0 2 6 9 13 15 0 4 6 9 13 15 Ce rizni zrostayuchi pidposlidovnosti odnakovoyi dovzhini v odnij i tij zhe vhidnij poslidovnosti Zv yazok z inshimi algoritmichnimi zadachamiZadacha najdovshoyi zrostayuchogo pidposlidovnosti tisno pov yazana z najdovshoyu spilnoyu pidposlidovnistyu yaka rozv yazuyetsya za dopomogoyu dinamichnogo programuvannya za kvadratichnij chas najdovsha zrostayucha pidposlidovnist poslidovnosti S ye najdovshoyu zagalnoyu pidposlidovnistyu S i T de T rezultat en S Odnak dlya okremogo vipadku koli vhidnimi danimi ye perestanovka cilih chisel 1 2 n cej pidhid mozhna zrobiti nabagato efektivnishim tak shob vin vikonuvavsya za chas O n log log n Najbilsha klika v grafi perestanovki vidpovidaye najdovshij spadnij pidposlidovnosti perestanovki yaka viznachaye graf pripuskayuchi sho vihidna poslidovnist bez perestanovok sortuyetsya vid najmenshogo znachennya do najbilshogo Podibnim chinom maksimalna en v grafi perestanovok vidpovidaye najdovshij nespadnij pidposlidovnosti Tomu najefektivnishi algoritmi poshuku zrostayuchoyi pidposlidovnosti mozhut buti vikoristani dlya efektivnogo virishennya zadachi pro kliku v grafah perestanovki U en mizh perestanovkami i tablicyami Yunga dovzhina pershogo ryadka tablici sho vidpovidaye perestanovci dorivnyuye dovzhini najbilshoyi zrostayuchoyi pidposlidovnosti perestanovki a dovzhina pershogo stovpcya dorivnyuye dovzhini najdovshoyi spadnoyi pidposlidovnisti Efektivni algoritmiVikladenij nizhche algoritm efektivno virishuye zadachu pro najdovshu zrostayuchu pidposlidovnist za dopomogoyu masiviv ta dvijkovogo poshuku Vin obroblyaye elementi poslidovnosti odin za odnim vidpovidno do yih poryadku pri comu pidtrimuyetsya najdovsha zrostayucha pidposlidovnist znajdena na cej moment Poznachimo znachennya vhidnoyi poslidovnosti yak X 0 X 1 tosho Potim pislya obrobki chergovogo X i algoritm bude zberigati znachennya u dvoh masivah M j zberigaye indeks k najmenshogo znachennya X k yake ye ostannim u zrostayuchij pidposlidovnisti dovzhini j sho zakinchuyetsya znachennyam X k k i rivnist mozhliva tilki koli vhodovij masiv do indeksu i ye zrostayuchim Zvernit uvagu sho j i 1 oskilki j 1 ye dovzhinoyu zrostayuchoyi pidposlidovnosti a k 0 ce indeks v masivi X yiyi ostannogo elementu P k zberigaye indeks v masivi X yakij jde pered ostannim elementom X k u najdovshij zrostayuchij poslidovnosti sho zakinchuyetsya na X k Krim togo algoritm zberigaye zminnu L yaka predstavlyaye dovzhinu najdovshoyi zrostayuchoyi pidposlidovnosti znajdenogo na potochnij moment Oskilki navedenij nizhche algoritm vikoristovuye numeraciyu vid nulya dlya yasnosti M dopovnyuyetsya elementom M 0 yakij ne vikoristovuyetsya tim samim M j vidpovidaye poslidovnosti dovzhini j Konkretna realizaciya mozhe ne zaluchati M 0 i vidpovidno indeksi bude skoreguvano Zvernit uvagu sho v bud yakij moment vikonannya algoritmu poslidovnist X M 1 X M 2 X M L ye zrostayuchoyu Bo yaksho isnuye zrostayucha pidposlidovnist dovzhini j 2 sho zakinchuyetsya v X M j to isnuye takozh pidposlidovnist dovzhini j 1 sho zakinchuyetsya na menshomu znachenni a same ta yaka zakinchuyetsya v X P M j Takim chinom mi mozhemo vikonuvati dvijkovij poshuk v cij poslidovnosti za logarifmichnij chas Todi algoritm pracyuye nastupnim chinom Demo versiya kodu P masiv dovzhini N M masiv dovzhini N 1 L 0 L 0 for i in range 0 to N 1 Dvijkovij poshuk najbilshogo dodatnogo j L takogo sho X M j lt X i lo 1 hi L while lo hi mid ceil lo hi 2 if X M mid lt X i lo mid 1 else hi mid 1 Pislya poshuku lo na 1 bilshe nizh dovzhina najdovshogo prefiksu X i newL lo Poperednik X i ye ostannim indeksom pidposlidovnosti dovzhini newL 1 The predecessor of X i is the last index of the subsequence of length newL 1 P i M newL 1 M newL i if newL gt L Yaksho mi znajshli pidposlidovnist dovshu za bud yaku zi znajdenih to onovimo L L newL Rekonstruyuyemo najdovshu zrostayuchu pidposlidovnist S masiv dovzhini L k M L for i in range L 1 to 0 S i X k k P k return S Oskilki algoritm vikonuye odin dvijkovij poshuk na kozhen element poslidovnosti jogo zagalnij chas vikonannya mozhna viraziti poznachennyam Big O yak O n log n Fredman 1975 obgovoryuye variant cogo algoritmu yakij vin pripisuye Donaldu Knutu U varianti yakij vin doslidzhuvav algoritm pereviryaye chi kozhne znachennya X i mozhe buti vikoristano dlya prodovzhennya potochnoyi najdovshoyi poslidovnosti sho zbilshuyetsya za stalij chas pered vikonannyam dvijkovogo poshuku Za dopomogoyu ciyeyi modifikaciyi algoritm vikoristovuye shonajbilshe n log2n n log2log2n O n porivnyan v najgirshomu vipadku sho ye optimalnim dlya algoritmu zasnovanogo na porivnyanni z tochnistyu do stalogo koeficiyenta v O n Mezhi dovzhiniVidpovidno do teoremi Erdesha Sekeresha bud yaka poslidovnist n2 1 riznih cilih chisel maye zrostayuchu abo spadnu pidposlidovnist dovzhini n 1 Dlya vhodiv v yakih kozhna perestanovka ochikuyetsya z odnakovoyu jmovirnistyu ochikuvana dovzhina najdovshoyi zrostayuchoyi pidposlidovnosti stanovit priblizno 2 n Koli n nablizhayetsya do neskinchennosti todi granichne znachennya dovzhini najbilshoyi zrostayuchoyi pidposlidovnosti vipadkovo perestavlenoyi poslidovnosti z n elementiv maye rozpodil sho nablizhayetsya do en rozpodilu najbilshogo vlasnogo znachennya vipadkovoyi matrici v universalnomu gaussovomu ansambli Onlajn algoritmiNajdovsha zrostalna pidposlidovnist takozh doslidzhuvalas z vikoristannyam onlajn algoritmiv v yakih elementi poslidovnosti nezalezhnih vipadkovih velichin iz neperervnim rozpodilom F abo yak variant elementi vipadkovoyi perestanovki podayutsya po odnomu elementu do algoritmu yakij povinen virishiti vklyuchiti chi viklyuchiti kozhen element ne mayuchi informaciyi pro elementi yaki nadijdut zgodom U comu varianti zadachi yakij peredbachaye cikave zastosuvannya u dekilkoh kontekstah mozhna rozrobiti optimalnu proceduru vidboru yaka beruchi do uvagi vipadkovu vibirku rozmirom n bude generuvati zrostalnu poslidovnist iz maksimalno ochikuvanoyu dovzhinoyu rozmiru priblizno 2n Dovzhina zrostalnoyi pidposlidovnosti vidibrana za ciyeyu optimalnoyu proceduroyu maye dispersiyu priblizno rivnu 2n 3 i yiyi granichnij rozpodil asimptotichno normalnij pislya zvichajnogo centruvannya ta masshtabuvannya Ti sami asimptotichni rezultati mayut bilsh tochni mezhi dlya vidpovidnoyi zadachi v umovah Puassonivskogo procesu Podalshe utochnennya u vipadku Puassonivskogo procesu vidbuvayetsya cherez dovedennya centralnoyi granichnoyi teoremi dlya optimalnogo procesu viboru z vidpovidnoyu normalizaciyeyu u bilsh povnomu sensi nizh mozhna bulo b ochikuvati Dovedennya daye ne tilki pravilnu funkcionalnu granichnu teoremu ale takozh singulyarnu matricyu kovariaciyi trivimirnogo procesu sho uzagalnyuye vsi vzayemodijni procesi ZastosuvannyaChastina sistemi en Maximum Unique Match finder dlya virivnyuvannya cilih genomiv Vikoristovuyetsya v sistemah kontrolyu versij takih yak Git tosho Vikoristovuyetsya v Patience Diff algoritmi riznici obchislyuye ta vidobrazhaye riznicyu mizh vmistom fajliv yakij vikoristovuyetsya u Bazaar Bazaar ce sistema kontrolyu versij yaka dopomagaye vam vidstezhuvati istoriyu proektu z chasom ta legko spivpracyuvati z inshimi Div takozh en efektivnij metod viznachennya dovzhini najbilshoyi zrostayuchoyi pidposlidovnosti en algebrayichna sistema sho viznachayetsya peretvorennyami yaki zberigayut dovzhinu najdovshoyi zrostayuchoyi pidposlidovnosti Anatolij Vershik rosijskij matematik yakij vivchav zastosuvannya teoriyi grup do najdovshih zrostayuchih pidposlidovnostej Najdovsha spilna pidposlidovnist en Primitki 1999 Longest increasing subsequences from patience sorting to the Baik Deift Johansson theorem Bulletin of the American Mathematical Society 36 04 413 432 doi 10 1090 S0273 0979 99 00796 X 1961 Longest increasing and decreasing subsequences 13 179 191 doi 10 4153 CJM 1961 015 3 MR 0121305 Hunt J Szymanski T 1977 A fast algorithm for computing longest common subsequences Communications of the ACM 20 5 350 353 doi 10 1145 359581 359603 1980 Algorithmic Graph Theory and Perfect Graphs Computer Science and Applied Mathematics Academic Press s 159 1975 On computing the length of longest increasing subsequences Discrete Mathematics 11 1 29 35 doi 10 1016 0012 365X 75 90103 X Erdos Paul Szekeres George 1935 Compositio Mathematica 2 463 470 arhiv originalu za 19 lyutogo 2019 procitovano 21 lipnya 2021 1995 Variations on the monotone subsequence theme of Erdos and Szekeres u ta in red PDF IMA Volumes in Mathematics and its Applications t 72 Springer Verlag s 111 131 arhiv originalu PDF za 11 chervnya 2019 procitovano 21 lipnya 2021 Vershik A M Kerov C V 1977 Asymptotics of the Plancheral measure of the symmetric group and a limiting form for Young tableaux Dokl Akad Nauk SSSR 233 1024 1027 Baik Jinho Deift Percy Johansson Kurt 1999 On the distribution of the length of the longest increasing subsequence of random permutations Journal of the American Mathematical Society 12 4 1119 1178 arXiv math 9810105 doi 10 1090 S0894 0347 99 00307 0 Samuels Stephen M 1981 Optimal Sequential Selection of a Monotone Sequence From a Random Sample PDF Annals of Probability 9 6 937 947 doi 10 1214 aop 1176994265 a href wiki D0 A8 D0 B0 D0 B1 D0 BB D0 BE D0 BD Citation title Shablon Citation citation a Obslugovuvannya CS1 Storinki z parametrom url status ale bez parametra archive url posilannya Arlotto Alessandro Nguyen Vinh V 2015 Optimal online selection of a monotone subsequence a central limit theorem Stochastic Processes and their Applications 125 9 3596 3622 arXiv 1408 6750 doi 10 1016 j spa 2015 03 009 Delbaen Freddy 2001 Optimal rules for the sequential selection of monotone subsequences of maximum expected length Stochastic Processes and their Applications 96 2 313 342 Delbaen Freddy 2004 A central limit theorem for the optimal selection process for monotone subsequences of maximum expected length Stochastic Processes and their Applications 114 2 287 311 doi 10 1016 j spa 2004 09 002PosilannyaNajdovsha zrostayucha pidposlidovnist na sajti Algorithmist 30 kvitnya 2010 u Wayback Machine angl Sproshena najdovsha zrostayucha pidposlidovnist 1 zhovtnya 2017 u Wayback Machine angl Obchislennya kilkosti najdovshih zrostayuchih pidposlidovnostej 21 lipnya 2021 u Wayback Machine angl Poldo s diet 1 zhovtnya 2017 u Wayback Machine ital

Дата публікації:
Топ