دالة التعقيد

في علم الحاسوب ، تُعرَّف دالة التعقيد لكلمة أو سلسلة نصية ( متسلسلة محدودة أو غير محدودة من الرموز من أبجدية معينة ) بأنها الدالة التي تحسب عدد العوامل المختلفة (السلاسل الفرعية من الرموز المتتالية) لتلك السلسلة. وبشكل أعم، فإن دالة التعقيد للغة رسمية (مجموعة من السلاسل النصية المحدودة) تحسب عدد الكلمات المختلفة ذات طول محدد.

ليكن u سلسلة (قد تكون لانهائية) من الرموز من أبجدية ما. عرّف الدالة p _u ( n ) لعدد صحيح موجب n بأنها عدد العوامل المختلفة (السلاسل الفرعية المتتالية) التي طولها n من السلسلة u . ^{[ 1 ] [ 2 ] [ 3 ] [ 4 ] [ 5 ]} 

بالنسبة لسلسلة u طولها n على الأقل على أبجدية حجمها k، من الواضح أن لدينا

${\displaystyle 1\leq p_{u}(n)\leq k^{n}\ ,}$

تُحقق الحدود بواسطة الكلمة الثابتة والكلمة المنفصلة ، ^{​​[ 6 ]} على سبيل المثال، كلمة Champernowne على التوالي. ^{[ 7 ]} بالنسبة للكلمات اللانهائية u ، يكون لدينا p _u ( n ) محدودًا إذا كانت u دورية في النهاية (متتالية منتهية، وربما فارغة، متبوعة بدورة منتهية). على العكس من ذلك، إذا كان p _u ( n ) ≤ n لبعض n ، فإن u تكون دورية في النهاية. ^{[ 3 ] [ 8 ]}

المتتالية غير الدورية هي متتالية لا تكون دورية في نهاية المطاف. تتميز المتتالية غير الدورية بدالة تعقيد متزايدة تمامًا (وهذا ما تنص عليه نظرية مورس-هيدلوند )، ^{[ 9 ] [ 10 ]} لذا فإن p ( n ) تساوي على الأقل n + 1. ^{[ 11 ]}

تُعتبر مجموعة S من الكلمات الثنائية المحدودة متوازنة إذا كانت المجموعة الجزئية S _n من الكلمات ذات الطول n، _لكل n ، تتمتع بخاصية أن وزن هامينغ للكلمات في S_{_n} يأخذ قيمتين مختلفتين على الأكثر. المتتالية المتوازنة هي تلك التي تكون فيها مجموعة عواملها متوازنة. ^{[ 12 ]} تتميز المتتالية المتوازنة بدالة تعقيد لا تتجاوز n + 1. ^{[ 13 ]}

الكلمة الستورمية على أبجدية ثنائية هي كلمة ذات دالة تعقيد n  +  1. ^{[ 14 ]} تكون المتتالية ستورمية إذا وفقط إذا كانت متوازنة وغير دورية. ^{[ 2 ] [ 15 ]} مثال على ذلك كلمة فيبوناتشي . ^{[ 14 ] [ 16 ]} بشكل عام، الكلمة الستورمية على أبجدية حجمها k هي كلمة ذات تعقيد n + k − 1. أما كلمة أرنو-راوزي على أبجدية ثلاثية فلها تعقيد 2n +  1  : ^{[ 14 ]} مثال على ذلك كلمة تريبوناتشي . ^{[ 17 ]}

بالنسبة للكلمات المتكررة ، أي تلك التي يظهر فيها كل عامل بشكل لانهائي، فإن دالة التعقيد تكاد تميز مجموعة العوامل: إذا كانت s كلمة متكررة لها نفس دالة التعقيد مثل t ، فإن s لها نفس مجموعة العوامل مثل t أو δ t حيث δ تشير إلى تشاكل مضاعفة الحروف a → aa . ^{[ 18 ]}

لنفترض أن L هي لغة على أبجدية ونعرف الدالة p _L ( n ) لعدد صحيح موجب n على أنها عدد الكلمات المختلفة ذات الطول n في L ^{[ 9 ]} وبالتالي فإن دالة تعقيد الكلمة هي دالة تعقيد اللغة التي تتكون من عوامل تلك الكلمة.

تكون دالة تعقيد اللغة أقل تقييدًا من دالة تعقيد الكلمة. على سبيل المثال، قد تكون محدودة ولكنها ليست ثابتة في النهاية: دالة تعقيد اللغة المنتظمة${\displaystyle a(bb)^{*}a}$_{تأخذ القيمتين 3 و4 على التوالي عندما يكون} n فرديًا أو زوجيًا (n ≥ 2). يوجد نظير لنظرية مورس-هيدلوند: إذا كان تعقيد اللغة L يحقق الشرط pL ( n ) ≤ n لبعض قيم n ، فإن pL يكون محدودًا _، وتوجد لغة منتهية F تحقق الشرط ^{[ 9 ].}

${\displaystyle L\subseteq \{xy^{k}z:x,y,z\in F,\ k\in \mathbb {N} \}\ .}$

اللغة متعددة الحدود أو اللغة المتفرقة هي اللغة التي تكون دالة تعقيدها p ( n ) محدودة بقوة ثابتة لـ n . أما اللغة المنتظمة التي ليست متعددة الحدود فهي اللغة الأسية : يوجد عدد لا نهائي من قيم n التي تكون فيها p ( n ) أكبر من ^kn لبعض قيم k الثابتة > 1. ^{[ 19 ]}

يُعرَّف الإنتروبيا الطوبولوجية لمتتالية لانهائية u بالصيغة التالية:

${\displaystyle H_{\mathrm {top} }(u)=\lim _{n\rightarrow \infty }{\frac {\log p_{u}(n)}{n\log k}}\ .}$

توجد النهاية لأن لوغاريتم دالة التعقيد شبه جمعي . ^{[ 20 ] [ 21 ]} كل عدد حقيقي بين 0 و1 يظهر لأن الإنتروبيا الطوبولوجية لبعض المتتاليات قابلة للتطبيق، ^{[ 22 ]} والتي يمكن اعتبارها متكررة بانتظام ^{[ 23 ]} أو حتى إرجودية بشكل فريد. ^{[ 24 ]}

إذا كان x عددًا حقيقيًا و b عددًا صحيحًا ≥ 2، فإن دالة التعقيد لـ x في النظام ذي الأساس b هي دالة التعقيد p ( x , b , n ) لتسلسل أرقام x المكتوبة في النظام ذي الأساس b . إذا كان x عددًا غير نسبي، فإن p ( x , b , n ) ≥ n + 1؛ وإذا كان x عددًا نسبيًا، فإن p ( x , b , n ) ≤ C ، حيث C ثابت يعتمد على x و b . ^{[ 6 ]} يُفترض أن التعقيد بالنسبة للعدد غير النسبي الجبري x هو bⁿ ⁽ وهو ما سيتحقق إذا كانت جميع هذه الأعداد أعدادًا طبيعية )، ولكن كل ما هو معروف في هذه الحالة هو أن p ينمو أسرع من أي دالة خطية لـ n . ^{[ 25 ]}

تحسب دالة التعقيد الأبلي p  ab ( n ) عدد مرات ظهور العوامل المختلفة ذات الطول n ، حيث نحدد الآن العوامل التي تختلف فقط بتبديل المواضع. من الواضح أن p ab ( n ) ≤ p ( n ). يحقق التعقيد الأبلي لمتتالية ستورميان الشرط p ab ( n ) = 2. [ 26 ]

• ألوش، جان بول؛ شاليت، جيفري (2003). المتتاليات التلقائية: النظرية، التطبيقات، التعميمات . مطبعة جامعة كامبريدج . ISBN 978-0-521-82332-6. Zbl 1086.11015 . 
• بيرستل، جان؛ لوف، آرون؛ رويتناور، كريستوف؛ ساليولا، فرانكو ف. (2009). التوافقية على الكلمات. كلمات كريستوفيل والتكرارات في الكلمات . سلسلة دراسات CRM. المجلد  27. بروفيدنس، رود آيلاند: الجمعية الرياضية الأمريكية . ISBN 978-0-8218-4480-9. Zbl 1161.68043 . 
• بيرثي، فاليري ؛ ريغو، ميشيل، محرران. (2010). التوافقية، والأتمتة، ونظرية الأعداد . موسوعة الرياضيات وتطبيقاتها. المجلد  135. كامبريدج: مطبعة جامعة كامبريدج . ISBN 978-0-521-51597-9. Zbl 1197.68006 . 
• بوجو، يان (2012). التوزيع بتردد واحد والتقريب الديوفانتي . سلسلة كامبريدج في الرياضيات. المجلد  193. كامبريدج: مطبعة جامعة كامبريدج . ISBN 978-0-521-11169-0. Zbl 1260.11001 . 
• كاسين، جوليان؛ نيكولا، فرانسوا (2010). "تعقيد العوامل". في بيرثي، فاليري ؛ ريغو، ميشيل (محرران). التوافقية، والأتمتة، ونظرية الأعداد . موسوعة الرياضيات وتطبيقاتها. المجلد  135. كامبريدج: مطبعة جامعة كامبريدج . الصفحات 163-247 . ISBN  978-0-521-51597-9. Zbl 1216.68204 . 
• لوثير، م. (2011). التوافقية الجبرية على الكلمات . موسوعة الرياضيات وتطبيقاتها. المجلد  90. مع مقدمة بقلم جان بيرستيل ودومينيك بيرين (إعادة طبع للطبعة ذات الغلاف المقوى لعام 2002  ). مطبعة جامعة كامبريدج. ISBN 978-0-521-18071-9. Zbl 1221.68183 . 
• بيثياس فوج، ن. (2002). Berthé, فاليري ; فيرينزي، سيباستيان؛ مودويت، كريستيان؛ سيجل، أ. (محرران). البدائل في الديناميكيات والحساب والتوافقيات . ملاحظات محاضرة في الرياضيات. المجلد.  1794. برلين: سبرينغر-فيرلاغ . رقم ISBN 3-540-44141-7. Zbl 1014.11015 .