Longest increasing subsequence (original) (raw)
أطول متتالية جزئية متزايدة في علم الحاسوب، تعالج مسألةُ إيجاد البحث عن متتالية جزئية من متتالية معطاة بحيث تكون عناصر هذه المتتالية الجزئية مرتبة، تصاعديّاً أو تنازليًّا، وبحيث تكون أطول ما يمكن .وهذه المتتالية الجزئية ليست بالضرورة ناتجة عن عناصر متجاورة كما أنها يمكن ألا تكون وحيدة ضمن المتتالية الأصلية.تمت دراسة مسألة إيجاد أطول متتالية جزئية متزايدة في سياق دراسة عدة فروع متعلقة بالرياضيات، متضمنة الخوارزميات ، تجمع مصفوفة غاوسية،نظرية تمثيل الزمر، والفيزياء. يمكن حل مسألة إيجاد أطول متتالية جزئية متزايدة في زمن( O(n log n، حيث n هو طول متتالية الدخل .
| Property | Value |
|---|---|
| dbo:abstract | أطول متتالية جزئية متزايدة في علم الحاسوب، تعالج مسألةُ إيجاد البحث عن متتالية جزئية من متتالية معطاة بحيث تكون عناصر هذه المتتالية الجزئية مرتبة، تصاعديّاً أو تنازليًّا، وبحيث تكون أطول ما يمكن .وهذه المتتالية الجزئية ليست بالضرورة ناتجة عن عناصر متجاورة كما أنها يمكن ألا تكون وحيدة ضمن المتتالية الأصلية.تمت دراسة مسألة إيجاد أطول متتالية جزئية متزايدة في سياق دراسة عدة فروع متعلقة بالرياضيات، متضمنة الخوارزميات ، تجمع مصفوفة غاوسية،نظرية تمثيل الزمر، والفيزياء. يمكن حل مسألة إيجاد أطول متتالية جزئية متزايدة في زمن( O(n log n، حيث n هو طول متتالية الدخل . (ar) En Ciencias de la Computación, el problema de la subsecuencia creciente máxima consiste en encontrar una subsecuencia de una secuencia dada donde los elementos de la subsecuencia están ordenados, de menor a mayor, y la subsecuencia sea tan larga como sea posible. Esta subsecuencia no es necesariamente continua, o única.La subsecuencias crecientes máximas son estudiadas por varias disciplinas relacionadas con las matemáticas, incluyendo algoritmos, física y teorías de matriz aleatoria. El problema de la subsecuencia creciente máxima es soluble en O(n log n), donde n denota el tamaño de la secuencia de entrada. (es) In computer science, the longest increasing subsequence problem is to find a subsequence of a given sequence in which the subsequence's elements are in sorted order, lowest to highest, and in which the subsequence is as long as possible. This subsequence is not necessarily contiguous, or unique.Longest increasing subsequences are studied in the context of various disciplines related to mathematics, including algorithmics, random matrix theory, representation theory, and physics. The longest increasing subsequence problem is solvable in time where denotes the length of the input sequence. (en) La recherche d'une plus longue sous-suite strictement croissante dans une suite finie est un problème classique en algorithmique. Ce problème peut être résolu en temps O(n log n) en la longueur de la suite. (fr) 컴퓨터 공학에서 최장 증가 부분 수열(Longest Increasing Subsequence) 문제는, 주어진 수열에서 오름차순으로 정렬된 가장 긴 부분수열을 찾는 문제이다. 여기서의 부분 수열은 연속적이거나 유일할 필요는 없다. 최장 증가 부분 수열은 알고리즘을 포함한 수학, , 표현론, 그리고 물리학과 관련된 다양한 분야에서 연구되었다.최장 증가 부분 수열 문제는, 입력 수열의 길이가 n일 때 O(nlogn)의 시간에 풀이가 가능하다. (ko) In informatica, il problema della massima sottosequenza crescente consiste nel trovare una sottosequenza di una sequenza data in cui gli elementi della sottosequenza siano ordinati dal minore al maggiore e la cui lunghezza sia la massima possibile. La sottosequenza non deve essere necessariamente contigua, o univoca.Il problema della massima sottosequenza crescente è risolvibile in tempo O(n log n), dove n rappresenta la lunghezza della sequenza originale. (it) Задача поиска наибольшей увеличивающейся подпоследовательности состоит в нахождении наиболее длинной возрастающей подпоследовательности в данной последовательности элементов. (ru) Em ciência da computação, o problema da maior subsequência crescente, ou máxima subsequência crescente consiste em encontrar um subsequência de números, dada um sequência, na qual seus elementos estão ordenados do menor para o maior, e a sequência é a mais longa possível. Este subsequência não é necessariamente contígua, ou o única.Este problema é estudado no contexto das várias disciplinas relacionadas com a matemática, incluindo algoritmo, teoria da matriz aleatória, teoria de representação e física. O problema pode ser resolvido em tempo O(n log n), onde n denota o comprimento da seqüência de entrada. (pt) В інформатиці задача про найдовшу зростаючу підпослідовність полягає у пошуку підпослідовності даної послідовності, в якій елементи підпослідовності розташовані в порядку зростання, тобто, кожен наступний елемент підпослідовності більше попереднього, також, підпослідовність є якомога довшою. Шукана послідовність не обов'язково є неперервною або єдиною. Найбільш довгі зростаючи підпослідовності вивчаються у різних дисциплінах, пов'язаних з математикою, включаючи алгоритміку, теорію випадкових матриць, теорію представлень та фізику. Задача про найдовшу зростаючу підпослідовність розв'язується за час O (n log n), де n — довжина вхідної послідовності. (uk) 在计算机科学中，最长递增子序列（longest increasing subsequence）问题是指，在一个给定的数值序列中，找到一个子序列，使得这个子序列元素的数值依次递增，并且这个子序列的长度尽可能地大。最长递增子序列中的元素在原序列中不一定是连续的。许多与数学、算法、、表示论相关的研究都会涉及最长递增子序列。解决最长递增子序列问题的算法最低要求O(n log n)的時間複雜度，这里n表示输入序列的规模。 (zh) |
| dbo:thumbnail | wiki-commons:Special:FilePath/LISDemo.gif?width=300 |
| dbo:wikiPageExternalLink | https://cms.di.unipi.it/%23/task/poldo/statement https://kuuatt.blogspot.com/2017/06/longest-increasing-sub-sequence-longest.html https://stackoverflow.com/questions/22923646/number-of-all-longest-increasing-subsequences/22945390%2322945390 http://www.algorithmist.com/index.php/Longest_Increasing_Subsequence |
| dbo:wikiPageID | 4587078 (xsd:integer) |
| dbo:wikiPageLength | 20440 (xsd:nonNegativeInteger) |
| dbo:wikiPageRevisionID | 1094466780 (xsd:integer) |
| dbo:wikiPageWikiLink | dbr:Robinson–Schensted_correspondence dbr:Representation_theory dbr:Algorithmics dbc:Dynamic_programming dbr:Permutation dbr:Independent_set_(graph_theory) dbr:Mathematics dbr:Online_algorithm dbr:Clique_problem dbr:Erdős–Szekeres_theorem dbr:Clique_(graph_theory) dbr:Computer_science dbr:Zero-based_numbering dbr:Physics dbr:Van_der_Corput_sequence dbr:Central_limit_theorem dbc:Combinatorics dbr:Dynamic_programming dbr:Normal_distribution dbc:Problems_on_strings dbr:Gaussian_unitary_ensemble dbr:Covariance_matrix dbc:Formal_languages dbr:Big_O_notation dbr:Tracy–Widom_distribution dbr:Donald_Knuth dbr:Sequence dbr:Young_tableau dbr:Longest_common_subsequence_problem dbr:Sorting dbr:Random_permutation dbr:Permutation_graph dbr:Random_matrix_theory dbr:Binary_search dbr:File:LISDemo.gif |
| dbp:wikiPageUsesTemplate | dbt:Annotated_link dbt:Harvtxt dbt:Reflist |
| dct:subject | dbc:Dynamic_programming dbc:Combinatorics dbc:Problems_on_strings dbc:Formal_languages |
| rdf:type | yago:WikicatNP-completeProblems yago:Abstraction100002137 yago:Act100030358 yago:Activity100407535 yago:Algorithm105847438 yago:Attribute100024264 yago:Communication100033020 yago:Condition113920835 yago:Difficulty114408086 yago:Event100029378 yago:Language106282651 yago:Problem114410605 yago:Procedure101023820 yago:PsychologicalFeature100023100 yago:YagoPermanentlyLocatedEntity yago:Rule105846932 yago:State100024720 yago:WikicatAlgorithms yago:WikicatFormalLanguages yago:WikicatPolynomial-timeProblems yago:WikicatProblemsOnStrings |
| rdfs:comment | أطول متتالية جزئية متزايدة في علم الحاسوب، تعالج مسألةُ إيجاد البحث عن متتالية جزئية من متتالية معطاة بحيث تكون عناصر هذه المتتالية الجزئية مرتبة، تصاعديّاً أو تنازليًّا، وبحيث تكون أطول ما يمكن .وهذه المتتالية الجزئية ليست بالضرورة ناتجة عن عناصر متجاورة كما أنها يمكن ألا تكون وحيدة ضمن المتتالية الأصلية.تمت دراسة مسألة إيجاد أطول متتالية جزئية متزايدة في سياق دراسة عدة فروع متعلقة بالرياضيات، متضمنة الخوارزميات ، تجمع مصفوفة غاوسية،نظرية تمثيل الزمر، والفيزياء. يمكن حل مسألة إيجاد أطول متتالية جزئية متزايدة في زمن( O(n log n، حيث n هو طول متتالية الدخل . (ar) En Ciencias de la Computación, el problema de la subsecuencia creciente máxima consiste en encontrar una subsecuencia de una secuencia dada donde los elementos de la subsecuencia están ordenados, de menor a mayor, y la subsecuencia sea tan larga como sea posible. Esta subsecuencia no es necesariamente continua, o única.La subsecuencias crecientes máximas son estudiadas por varias disciplinas relacionadas con las matemáticas, incluyendo algoritmos, física y teorías de matriz aleatoria. El problema de la subsecuencia creciente máxima es soluble en O(n log n), donde n denota el tamaño de la secuencia de entrada. (es) In computer science, the longest increasing subsequence problem is to find a subsequence of a given sequence in which the subsequence's elements are in sorted order, lowest to highest, and in which the subsequence is as long as possible. This subsequence is not necessarily contiguous, or unique.Longest increasing subsequences are studied in the context of various disciplines related to mathematics, including algorithmics, random matrix theory, representation theory, and physics. The longest increasing subsequence problem is solvable in time where denotes the length of the input sequence. (en) La recherche d'une plus longue sous-suite strictement croissante dans une suite finie est un problème classique en algorithmique. Ce problème peut être résolu en temps O(n log n) en la longueur de la suite. (fr) 컴퓨터 공학에서 최장 증가 부분 수열(Longest Increasing Subsequence) 문제는, 주어진 수열에서 오름차순으로 정렬된 가장 긴 부분수열을 찾는 문제이다. 여기서의 부분 수열은 연속적이거나 유일할 필요는 없다. 최장 증가 부분 수열은 알고리즘을 포함한 수학, , 표현론, 그리고 물리학과 관련된 다양한 분야에서 연구되었다.최장 증가 부분 수열 문제는, 입력 수열의 길이가 n일 때 O(nlogn)의 시간에 풀이가 가능하다. (ko) In informatica, il problema della massima sottosequenza crescente consiste nel trovare una sottosequenza di una sequenza data in cui gli elementi della sottosequenza siano ordinati dal minore al maggiore e la cui lunghezza sia la massima possibile. La sottosequenza non deve essere necessariamente contigua, o univoca.Il problema della massima sottosequenza crescente è risolvibile in tempo O(n log n), dove n rappresenta la lunghezza della sequenza originale. (it) Задача поиска наибольшей увеличивающейся подпоследовательности состоит в нахождении наиболее длинной возрастающей подпоследовательности в данной последовательности элементов. (ru) Em ciência da computação, o problema da maior subsequência crescente, ou máxima subsequência crescente consiste em encontrar um subsequência de números, dada um sequência, na qual seus elementos estão ordenados do menor para o maior, e a sequência é a mais longa possível. Este subsequência não é necessariamente contígua, ou o única.Este problema é estudado no contexto das várias disciplinas relacionadas com a matemática, incluindo algoritmo, teoria da matriz aleatória, teoria de representação e física. O problema pode ser resolvido em tempo O(n log n), onde n denota o comprimento da seqüência de entrada. (pt) В інформатиці задача про найдовшу зростаючу підпослідовність полягає у пошуку підпослідовності даної послідовності, в якій елементи підпослідовності розташовані в порядку зростання, тобто, кожен наступний елемент підпослідовності більше попереднього, також, підпослідовність є якомога довшою. Шукана послідовність не обов'язково є неперервною або єдиною. Найбільш довгі зростаючи підпослідовності вивчаються у різних дисциплінах, пов'язаних з математикою, включаючи алгоритміку, теорію випадкових матриць, теорію представлень та фізику. Задача про найдовшу зростаючу підпослідовність розв'язується за час O (n log n), де n — довжина вхідної послідовності. (uk) 在计算机科学中，最长递增子序列（longest increasing subsequence）问题是指，在一个给定的数值序列中，找到一个子序列，使得这个子序列元素的数值依次递增，并且这个子序列的长度尽可能地大。最长递增子序列中的元素在原序列中不一定是连续的。许多与数学、算法、、表示论相关的研究都会涉及最长递增子序列。解决最长递增子序列问题的算法最低要求O(n log n)的時間複雜度，这里n表示输入序列的规模。 (zh) |
| rdfs:label | أطول متتالية جزئية متزايدة (ar) Problema de la subsecuencia más larga (es) Plus longue sous-suite strictement croissante (fr) Massima sottosequenza crescente (it) Longest increasing subsequence (en) 최장 증가 부분 수열 (ko) Máxima subsequência crescente (pt) Задача поиска наибольшей увеличивающейся подпоследовательности (ru) Задача про найдовшу зростаючу підпослідовність (uk) 最长递增子序列 (zh) |
| owl:sameAs | freebase:Longest increasing subsequence yago-res:Longest increasing subsequence wikidata:Longest increasing subsequence dbpedia-ar:Longest increasing subsequence dbpedia-es:Longest increasing subsequence dbpedia-fa:Longest increasing subsequence dbpedia-fr:Longest increasing subsequence dbpedia-it:Longest increasing subsequence dbpedia-ka:Longest increasing subsequence dbpedia-ko:Longest increasing subsequence dbpedia-pt:Longest increasing subsequence dbpedia-ru:Longest increasing subsequence dbpedia-sr:Longest increasing subsequence dbpedia-th:Longest increasing subsequence dbpedia-uk:Longest increasing subsequence dbpedia-zh:Longest increasing subsequence https://global.dbpedia.org/id/3sEyw |
| prov:wasDerivedFrom | wikipedia-en:Longest_increasing_subsequence?oldid=1094466780&ns=0 |
| foaf:depiction | wiki-commons:Special:FilePath/LISDemo.gif |
| foaf:isPrimaryTopicOf | wikipedia-en:Longest_increasing_subsequence |
| is dbo:wikiPageDisambiguates of | dbr:LIS |
| is dbo:wikiPageRedirects of | dbr:Nondecreasing_subsequence dbr:Longest_increasing_subsequence_problem dbr:Longest_nondecreasing_subsequence |
| is dbo:wikiPageWikiLink of | dbr:Robinson–Schensted_correspondence dbr:MUMmer dbr:Plancherel_measure dbr:Nondecreasing_subsequence dbr:Binary_logarithm dbr:Patience_sorting dbr:Determinantal_point_process dbr:Anatoly_Vershik dbr:Clique_problem dbr:Optimal_substructure dbr:Perfect_graph dbr:Stack-sortable_permutation dbr:238_(number) dbr:File_comparison dbr:Hook_length_formula dbr:Tracy–Widom_distribution dbr:Sorting_algorithm dbr:Longest_alternating_subsequence dbr:Longest_common_subsequence_problem dbr:LIS dbr:Plactic_monoid dbr:Permutation_graph dbr:Superpattern dbr:Longest_increasing_subsequence_problem dbr:Longest_nondecreasing_subsequence |
| is foaf:primaryTopic of | wikipedia-en:Longest_increasing_subsequence |
