أطول متتالية جزئية متزايدة
أطول متتالية جزئية متزايدة في علم الحاسوب، تعالج مسألةُ إيجاد البحث عن متتالية جزئية من متتالية معطاة بحيث تكون عناصر هذه المتتالية الجزئية مرتبة، تصاعديّاً أو تنازليًّا، وبحيث تكون أطول ما يمكن .وهذه المتتالية الجزئية ليست بالضرورة ناتجة عن عناصر متجاورة كما أنها يمكن ألا تكون وحيدة ضمن المتتالية الأصلية.
تمت دراسة مسألة إيجاد أطول متتالية جزئية متزايدة في سياق دراسة عدة فروع متعلقة بالرياضيات، متضمنة الخوارزميات ، تجمع مصفوفة غاوسية،نظرية تمثيل الزمر، والفيزياء. يمكن حل مسألة إيجاد أطول متتالية جزئية متزايدة في زمن( O(n log n، حيث n هو طول متتالية الدخل .

مثال 
في متتالية ڤان دير كورپت الثنائية
0، 8، 4، 12، 2، 10، 6، 14، 1، 9، 5، 13، 3، 11، 7، 15، …
إحدى المتتاليات الجزئية الأطول المتزايدة هي
0، 2، 6، 9، 13، 15.
طول هذه المتتالية الجزئية هو 6; أي أن المتتالية الأصلية لا تحوي متتالية جزئية من 7 عناصر يمكنها تشكيل متتالية جزئية متزايدة.كما أن المتتالية الجزئية المتزايدة الأطول ليست وحيدة فمثلاً لدينا 
0، 4، 6، 9، 11، 15 أو 0، 4، 6، 9، 13، 15
هما متتاليتان جزئيتان متزايدتان من نفس طول المتتالية الجزئية المتزايدة الأطول .

علاقتها بمسائل خوارزمية أخرى 
مسألة إيجاد المتتالية الجزئية المتزايدة الأطول لها تعلق وطيد بمسألة إيجاد أطول متتالية جزئية مشتركة، والتي تحتاج زمناً من الدرجة الثالثة لحلها باستخدام البرمجة الديناميكية : إن أطول متتالية جزئية متزايدة في متتالية ما S هي أطول متتالية جزئية مشتركة بين المتتاليتين S و T، حيث T هي نتيجة ترتيب المتتالية S.

من أجل الحالة الخاصة التي يكون فيها الدخل عبارة عن تبديل للأعداد الصحيحة 1، 2، ...، n، يمكن لهذا الحل أن يكون فعالاً، ليعطينا حلاً بحدود( O(n log log n.

خوارزمية فعالة للحل 
الخوارزمية التالية تحلّ مسألة إيجاد أطول متتالية جزئية متزايدة باستخدام المصفوفات والبحث الثنائي. 
فهي تقوم بمعالجة عناصر المتتالية تباعاً، وتقوم بحفظ أطول متتالية جزئية تم العثور عليها حتى الآن. إذا رمزنا إلى عناصر المتتالية بـ [X[1]، X[0، الخ. فبعد معالجة العنصر [X[i، تكون الخوارزمية قد حفظت قيماً في مصفوفتين:
[M[j — تحفظ قيمة الفهرس k لأصغر عنصر [X[k حيث توجد متتالية جزئية متزايدة طولها j وتنتهي بالعنصر [X[kفي المجال k ≤ i (لاحظ أن لدينا هنا j ≤ k ≤ i ، لأن j يمثل طول المتتالية الجزئية المتزايدة، وk يمثل رقم فهرس انتهاء المتتالية الجزئية.فمن الواضح أنه لا يمكننا الحصول على متتالية جزئية متزايدة طولها 13 عندما نكون لانزال عند العناصر رقم 11 ، . k ≤ i بالتعريف).

[P[k — تحفظ رقم الفهرس للعنصر الذي يسبق [X[k في أطول متتالية جزئية متزايدة تنتهي عند [X[k.

إضافة لما سبق فإن الخوارزمية تحفظ عدداً L يمثل طول أطول متتالية جزئية متزايدة تم العثور عليها حتى الآن.

في الخوارزمية أدناه سنزيح المصفوفة M بالعنصر [M[0 الذي لن يستخدم للتسهيل (فالمصفوفة تستخدم الترقيم بدءاً من الصفر ).

لاحظ أن المتتالية [[X[M[1]]، X[M[2]]، ...، X[M[L تكون غير متناقصة عند أي نقطة من الخوارزمية، لذلك إذا كان هناك متتالية جزئية طولها i تنتهي عند [[X[M[i
فهناك أيضاً متتالية جزئية طولها i-1 تنتهي عند قيمة أصغر : وهي القيمة [[[X[P[M[i. لذلك نقوم بعمل بحث ثنائي في المتتالية في زمن لوغاريتمي .

سنكتب الخوارزمية بالعربية لتقريبها إلى الفهم أكثر بحيث توضح المسميات وظيفة كل متحول ومصفوفة وذلك كما يلي :
 سنرمز بالكلمة أمجد لــأطول متتالية جزئية متزايدة .
 [M[j تكافئها : رقم_أصغر_نهاية_لأمجد_بطول_ما[ج]
 [P[k تكافئها : رقم_السابق_في_أمجد_لعنصر_ما[ك]
 [X[k تكافئها : الدخل[ك]
 عدد العناصر N يقابله الحجم
 طول أمجد تم العثور عليها L يقابله الطول
نص الخوارزمية بطريقة شبه الكود كما يلي :

 رقم_السابق_في_أمجد_لعنصر_ما = مصفوفة طولها الحجم
 رقم_أصغر_نهاية_لأمجد_بطول_ما = مصفوفة طولها الحجم+1
 الطول = 0
 
 من أجل المتحول س ضمن المجال من 0 إلى الحجم-1 :
  \\ بحث ثنائي للعثور على أكبر قيمة تحقق العلاقتين ج ≤ الطول
  \\ و الدخل[ رقم_أصغر_نهاية_لأمجد_بطول_ما[ج] ] <الدخل[س]
  رقم_القيمة_الأدنى = 1
  رقم_القيمة_الأعلى = الطول
  طالما رقم_القيمة_الأدنى ≤ رقم_القيمة_الأعلى :
   رقم_القيمة_الوسطى = (رقم_القيمة_الأدنى+رقم_القيمة_الأعلى)\2
   إذا كان الدخل[ رقم_أصغر_نهاية_لأمجد_بطول_ما[رقم_القيمة_الوسطى] ] <الدخل[س]:
    رقم_القيمة_الأدنى = رقم_القيمة_الوسطى +1
   وإلا :
    رقم_القيمة_الأعلى = رقم_القيمة_الوسطى -1
   نهاية جملة الشرط
  نهاية حلقة التكرار
    
  \\ بعد انتهاء البحث،رقم_القيمة_الأدنى أكبر بمقدار 1 من
  \\ طول أمجد التي تسبق الدخل[س]
  الطول_الجديد = رقم_القيمة_الأدنى
  \\ العنصر الذي يسبق الدخل[س] في أمجد المنتهية بالدخل[س]
  \\ هو آخر عنصر من أمجد ذات الطول الطول_الجديد -1 
  السابق_في_أمجد_لعنصر_ما[س] = رقم_أصغر_نهاية_لأمجد_بطول_ما[الطول_الجديد -1 ]
    
  إذا كان الطول_الجديد> الطول :
   \\ أي أننا وجدنا أمجد جديدة أطول من السابقة
   \\ لذلك علينا تحديث قيمة الطول و رقم_أصغر_نهاية_لأمجد_بطول_ما
   رقم_أصغر_نهاية_لأمجد_بطول_ما[الطول_الجديد] = س
   الطول = الطول_الجديد
  وإلا إذا كان الدخل[س] <الدخل[رقم_أصغر_نهاية_لأمجد_بطول_ما[الطول_الجديد]]:
   \\ أي أننا عثرنا على قيمة أصغر لنهاية أمجد بطول الطول_الجديد
   \\ فعلينا تغيير هذه القيمة
    رقم_أصغر_نهاية_لأمجد_بطول_ما[الطول_الجديد] = س
  نهاية جملة الشرط 
 نهاية حلقة التكرار
 
 \\إعادة بناء أمجد
 عناصر_أمجد = مصفوفة طولها الطول
 ك = رقم_أصغر_نهاية_لأمجد_بطول_ما[الطول]
 من أجل المتحول س في المجال من الطول-1 إلى 0 :
   عناصر_أمجد[س] = الدخل [ك]
   ك = رقم_السابق_في_أمجد_لعنصر_ما[ك]
 نهاية حلقة التكرار 
 قم بإعادة عناصر_أمجد
 نهاية الخوارزمية''
الزمن الكلي الذي تستغرقه الخوارزمية باستخدام رمز O الكبير هو (O(n log n وذلك لأن الخوارزمية تقوم بعملية بحث ثنائي من أجل كل عنصر .ناقش العالم فريدمان(1975) تعديلات على الخوارزمية نسبها إلى دونالد كنوث ، تختبر خوارزميته المعدلة فيما إذا كان من الممكن استخدام العنصر [X[i لتمديد المتتالية الجزئية الحالية الأطول، وذلك خلال زمن ثابت، وذلك قبل القيام بالبحث الثنائي .

تستخدم الخوارزمية وفق هذا التعديل عدداً أقصى من عمليات المقارنة هو (n log2 n − n log2log2 n + O(n في الحالة الأسوأ، وهو زمن مثالي لخوارزمية تعتمد المقارنة وذلك حتى الوصول إلى الثابت في عبارة (O(n .

حدود الطول 
حسب مبرهنة إيردوس-سيكريس، فإن أي متتالية من n2+1 عدد صحيح مختلف إما أن يكون لها متتالية جزئية متزايدة أو متناقصة طولها n+1.

في القوائم التي تكون فيها كل تبديلات القائمة متماثلة تقريباً، يكون الطول المتوقع لأطول متتالية جزئية متزايدة هو تقريباً2√n.
عندما تسعى n إلى اللانهاية، يكون طول أطول متتالية جزئية متزايدة في متتالية مبدّلة عشوائياً من n عنصر ذا توزّع يقترب من توزّع Tracy–Widom ، أي توزع أكبر قيمة ذاتية لمصفوفة عشوائية ضمن تجمع الغاوسي المتكامل .

خوارزميات متصلة على الخط

انظر أيضًا 

 خوارزمية

مراجع 

برمجة ديناميكية
توافقيات
خوارزميات
رياضيات
لغات شكلية
أطول متتالية جزئية متزايدة في علم الحاسوب ، تعالج مسألةُ إيجاد البحث عن متتالية جزئية من متتالية معطاة ب حيث تكون عناصر هذه المتتالية الجزئية مرتبة ، تصاعديّاً أو تنازليًّا ، وب حيث تكون أطول ما يمكن \ . و هٰذه المتتالية الجزئية ليست ب الضرورة ناتجة عن عناصر متجاورة كما أن ها يمكن أن لا تكون وحيدة ضمن المتتالية الأصلية . تمت دراسة مسألة إيجاد أطول متتالية جزئية متزايدة في سياق دراسة عدة فروع متعلقة بالرياضيات ، متضمنة الخوارزميات ، تجمع مصفوفة غاوسية ، نظرية تمثيل الزمر ، والفيزياء . يمكن حل مسألة إيجاد أطول متتالية جزئية متزايدة في زمن ( O ( n log n ، حيث n هو طول متتالية الدخل \ . مثال في متتالية ڤان دير كورپت الثنائية 0 ، … إحدى المتتاليات الجزئية الأطول المتزايدة هي 0 ، طول هذه المتتالية الجزئية هو أي أن المتتالية الأصلية لا تحوي متتالية جزئية منعناصر يمكن ها تشكيل متتالية جزئية متزايدة . كما أن المتتالية الجزئية المتزايدة الأطول ليست وحيدة فمثلاً لدي نا 0، أو هما متتاليتان جزئيتان متزايدتان من نفس طول المتتالية الجزئية المتزايدة الأطول \ . علاقة ها بمسائل خوارزمية أخرى مسألة إيجاد المتتالية الجزئية المتزايدة الأطول ل ها تعلق وطيد بمسألة إيجاد أطول متتالية جزئية مشتركة ، و التي تحتاج زمناً من الدرجة الثالثة ل حل ها ب استخدام البرمجة الديناميكية \ : إن أطول متتالية جزئية متزايدة في متتالية ما S هي أطول متتالية جزئية مشتركة بين المتتاليتين S و T ، حيث T هي نتيجة ترتيب المتتالية S . من أجل الحالة الخاصة التي يكون في ها الدخل عبارة عن تبديل للأعداد الصحيحة \ . . . ، n ، يمكن ل هٰذا الحل أن يكون فعالاً ، ل يعطي نا حلاً بحدود ( O ( n log log n . خوارزمية فعالة ل الحل الخوارزمية التالية تحلّ مسألة إيجاد أطول متتالية جزئية متزايدة ب استخدام المصفوفات و البحث الثنائي . ف هي تقوم ب معالجة عناصر المتتالية تباعاً ، و تقوم بحفظ أطول متتالية جزئية تم العثور علي ها حتى الآن . إذا رمز نا إلى عناصر المتتالية بـ [ X [ 1 ] ، X [ 0 ، الخ . ف بعد معالجة العنصر [ X [ i ، تكون الخوارزمية قد حفظت قيماً في مصفوفتين : [ M [ j — تحفظ قيمة الفهرس k لأصغر عنصر [ X [ k حيث توجد متتالية جزئية متزايدة طول ها j و تنتهي بالعنصر [ X [ kفي المجال k ≤ i ( لاحظ أن لدي نا هنا j ≤ k ≤ i ، لأن j يمثل طول المتتالية الجزئية المتزايدة ، وk يمثل رقم فهرس انتهاء المتتالية الجزئية . ف من الواضح أن ه لا يمكن نا الحصول على متتالية جزئية متزايدة طولها عندما نكون ل إنزال عند العناصر رقم ،\ . k ≤ i بالتعريف ) . [ P [ k — تحفظ رقم الفهرس للعنصر الذي يسبق [ X [ k في أطول متتالية جزئية متزايدة تنتهي عند [ X [ k . إضافة ل ما سبق ف إن الخوارزمية تحفظ عدداً L يمثل طول أطول متتالية جزئية متزايدة تم العثور علي ها حتى الآن . في الخوارزمية أدنا ه سنزيح المصفوفة M بالعنصر [ M [ 0 الذي لن يستخدم ل التسهيل ( فالمصفوفة تستخدم الترقيم بدءاً من الصفر ) . لاحظ أن المتتالية [ [ X [ M [ 1 ] ] ، X [ M [ 2 ] ] ،\ . . . ، X [ M [ L تكون غير متناقصة عند أي نقطة من الخوارزمية ، ل ذٰلك إذا كان هناك متتالية جزئية طول ها i تنتهي عند [ [ X [ M [ i ف هناك أيضاً متتالية جزئية طول ها i - 1 تنتهي عند قيمة أصغر \ : و هي القيمة [ [ [ X [ P [ M [ i . ل ذٰلك نقوم بعمل بحث ثنائي في المتتالية في زمن لوغاريتمي \ . سنكتب الخوارزمية ب العربية لتقريب ها إلى الفهم أكثر ب حيث توضح المسميات وظيفة كل متحول ومصفوفة و ذٰلك كما يلي \ : سنرمز بالكلمة أمجد لــأطول متتالية جزئية متزايدة \ . [ M [ j تكافئ ها \ : رقم_أصغر_نهاية _لأمجد_بطول _ما [ ج ] [ P [ k تكافئ ها \ : رقم_السابق_في_أمجد_لعنصر _ما [ ك ] [ X [ k تكافئ ها \ : الدخل [ ك ] عدد العناصر N يقابل ه الحجم طول أمجد تم العثور علي ها L يقابل ه الطول نص الخوارزمية ب طريقة شبه الكود كما يلي \ : رقم_السابق_في_أمجد_لعنصر_ما = مصفوفة طول ها الحجم رقم_أصغر_نهاية _لأمجد_بطول_ما = مصفوفة طول ها الحجم + 1 الطول = 0 من أجل المتحول س ضمن المجال من إلى الحجم - 1\ : \\ بحث ثنائي للعثور على أكبر قيمة تحقق العلاقتين ج ≤ الطول \\ و الدخل [ رقم_أصغر_نهاية _لأمجد_بطول _ما [ ج ] ] <الدخل [ س ] رقم_القيمة _الأدنى = 1 رقم_القيمة _الأعلى = الطول طالما رقم_القيمة _الأدنى ≤ رقم_القيمة _الأعلى \ : رقم_القيمة _ الوسطى = ( رقم_القيمة _الأدنى + رقم_القيمة _الأعلى ) \2 إذا كان الدخل [ رقم_أصغر_نهاية _لأمجد_بطول_ما [ رقم_القيمة _ الوسطى ] ] <الدخل [ س ] : رقم_القيمة _الأدنى = رقم_القيمة _ الوسطى + 1 وإلا\ : رقم_القيمة _الأعلى = رقم_القيمة _ الوسطى - 1 نهاية جملة الشرط نهاية حلقة ال تكرار \\ بعد انتهاء البحث ، رقم_القيمة _الأدنى أكبر بمقدارمن \\ طول أمجد التي تسبق الدخل [ س ] الطول_ الجديد = رقم_القيمة _الأدنى \\ العنصر الذي يسبق الدخل [ س ] في أمجد المنتهية بالدخل [ س ] \\ هو آخر عنصر من أمجد ذات الطول الطول_ الجديد السابق_في_أمجد_لعنصر _ما [ س ] = رقم_أصغر_نهاية _لأمجد_بطول_ما [ الطول_ الجديد ] إذا كان الطول_ الجديد > الطول \ : \\ أي أن نا وجد نا أمجد جديدة أطول من السابقة \\ ل ذٰلك علي نا تحديث قيمة الطول و رقم_أصغر_نهاية _لأمجد_بطول_ما رقم_أصغر_نهاية _لأمجد_بطول_ما [ الطول_ الجديد ] = س الطول = الطول_ الجديد و إلا إذا كان الدخل [ س ] <الدخل [ رقم_أصغر_نهاية _لأمجد_بطول_ما [ الطول_ الجديد ] ] : \\ أي أن نا عثرنا على قيمة أصغر لنهاية أمجد ب طول الطول_ الجديد \\ ف علي نا تغيير هذه القيمة رقم_أصغر_نهاية _لأمجد_بطول_ما [ الطول_ الجديد ] = س نهاية جملة الشرط نهاية حلقة ال تكرار \\ إعادة بناء أمجد عناصر_أمجد = مصفوفة طول ها الطول ك = رقم_أصغر_نهاية _لأمجد_بطول_ما [ الطول ] من أجل المتحول س في المجال من الطول - 1 إلى : عناصر_أمجد [ س ] = الدخل [ ك ] ك = رقم_السابق_في_أمجد_لعنصر _ما [ ك ] نهاية حلقة ال تكرار قم ب إعادة عناصر_أمجد نهاية الخوارزمية ' ' الزمن الكلي الذي تستغرق ه الخوارزمية ب استخدام رمز O الكبير هو ( O ( n log n و ذٰلك لأن الخوارزمية تقوم ب عملية بحث ثنائي من أجل كل عنصر \ . ناقش العالم فريدمان ( 1975 ) تعديلات على الخوارزمية نسب ها إلى دونالد كنوث ، تختبر خوارزمية ه المعدلة فيما إذا كان من الممكن استخدام العنصر [ X [ i ل تمديد المتتالية الجزئية الحالية الأطول ، و ذٰلك خلال زمن ثابت ، و ذٰلك قبل القيام ب البحث الثنائي \ . تستخدم الخوارزمية وفق هذا التعديل عدداً أقصى من عمليات المقارنة هو ( n log 2 n − n log2lo g 2 n + O ( n في الحالة الأسوأ ، و هو زمن مثالي لخوارزمية تعتمد المقارنة و ذٰلك حتى الوصول إلى الثابت في عبارة ( O ( n\ . حدود الطول حسب مبرهنة إيردوس - سيكريس ، ف إن أي متتالية من n2 + 1 عدد صحيح مختلف إما أن يكون ل ها متتالية جزئية متزايدة أو متناقصة طول ها n + 1 . في القوائم التي تكون في ها كل تبديلات القائمة متماثلة تقريباً ، يكون الطول المتوقع لأطول متتالية جزئية متزايدة هو تقريباً 2 √ n . عندما تسعى n إلى اللانهاية ، يكون طول أطول متتالية جزئية متزايدة في متتالية مبدّلة عشوائياً من n عنصر ذا توزّع يقترب من توزّع Tracy – Widom ، أي توزع أكبر قيمة ذاتية لمصفوفة عشوائية ضمن تجمع الغاوسي المتكامل \ . خوارزميات متصلة على الخط انظر أيضًا خوارزمية مراجع برمجة ديناميكية توافقيات خوارزميات رياضيات لغات ش كلية