أقل نقطة ثابتة

📅 آخر تحديث: ٤ أغسطس ٢٠٢٦
✍️ نُشر في: ٤ أغسطس ٢٠٢٦
📷 يحتوي على 39 صور
الموسوعة الحرة
الدالة f ( x )  = x 2 − 4 لها نقطتان ثابتتان، موضحتان كنقطة تقاطع مع الخط الأزرق؛ أصغر نقطة لها هي عند 1/2 − √ 17 /2.     

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

أمثلة

وفقًا للترتيب المعتاد للأعداد الحقيقية ، فإن أصغر نقطة ثابتة للدالة الحقيقية f ( x ) = x² هي x = 0 (لأن النقطة الثابتة الأخرى الوحيدة هي 1 و 0 < 1). في المقابل، لا تمتلك الدالة f ( x ) = x + 1 أي نقاط ثابتة على الإطلاق، وبالتالي ليس لها نقطة ثابتة صغرى، بينما تمتلك الدالة f ( x ) = x عددًا لا نهائيًا من النقاط الثابتة، ولكن ليس لها نقطة ثابتة صغرى.         

يتركجي=(V،أ){\displaystyle G=(V,A)}ليكن رسمًا بيانيًا موجهًا وv{\displaystyle v}ليكن رأسًا. مجموعة الرؤوس التي يمكن الوصول إليها منv{\displaystyle v}يمكن تعريفها بأنها أصغر نقطة ثابتة للدالةو:℘(V)→℘(V){\displaystyle f:\wp (V)\to \wp (V)}، كما هو مُعرَّفو(X)={v}∪{x∈V: بالنسبة للبعض w∈X هناك حافة من w ل x}.{\displaystyle f(X)=\{v\}\cup \{x\in V:{\text{ لبعض }}w\in X{\text{ يوجد ضلع من }}w{\text{ إلى }}x\}.}مجموعة الرؤوس التي يمكن الوصول إليها بشكل مشترك منv{\displaystyle v}يتم تعريفها بواسطة نقطة ثابتة دنيا مماثلة. المكون المتصل بقوة منv{\displaystyle v}هي نقطة تقاطع هاتين النقطتين الثابتتين الأصغر.

يتركجي=(V،Σ،R،S0){\displaystyle G=(V,\Sigma ,R,S_{0})}أن تكون قواعد نحوية خالية من السياق . المجموعةهـ{\displaystyle E}من الرموز التي تنتج سلسلة فارغةε{\displaystyle \varepsilon }يمكن الحصول عليها كأصغر نقطة ثابتة للدالةو:℘(V)→℘(V){\displaystyle f:\wp (V)\to \wp (V)}، كما هو مُعرَّفو(X)={S∈V:S∈X أو (S→ε)∈R أو (S→S1...Sن)∈R و Sأنا∈Xللجميع أنا}{\displaystyle f(X)=\{S\in V:\;S\in X{\text{ or }}(S\to \varepsilon )\in R{\text{ or }}(S\to S^{1}\dots S^{n})\in R{\text{ and }}S^{i}\in X{\text{, for all }}i\}}، أين℘(V){\displaystyle \wp (V)}يشير إلى مجموعة القوى لـV{\displaystyle V}.

التطبيقات

تُنتج العديد من نظريات النقطة الثابتة خوارزميات لتحديد أصغر نقطة ثابتة. غالبًا ما تتمتع أصغر النقاط الثابتة بخصائص مرغوبة لا تتمتع بها النقاط الثابتة العادية.

الدلالات الدلالية

طلب جزئي بشأنZ⊥{\displaystyle \mathbb {Z} _{\bot }}

في علم الحاسوب ، يستخدم منهج الدلالات الدلالية أقل النقاط الثابتة لاستخلاص دالة رياضية مقابلة من نص برنامج معين، تُسمى دلالاته. ولتحقيق هذه الغاية، يتم إنشاء كائن رياضي اصطناعي.⊥{\displaystyle \bot }يتم إدخال ، للدلالة على القيمة الاستثنائية "غير مُعرَّفة". وبالنظر إلى نوع بيانات البرنامج int، على سبيل المثال، يتم تعريف نظيره الرياضي على النحو التالي:Z⊥=Z∪{⊥}؛{\displaystyle \mathbb {Z} _{\bot }=\mathbb {Z} \cup \{\bot \};} يتم تحويلها إلى مجموعة مرتبة جزئياً عن طريق تعريف⊥⊏ن{\displaystyle \bot \sqsubset n}لكلن∈Z{\displaystyle n\in \mathbb {Z} }والسماح لأي عضوين مختلفينن،م∈Z{\displaystyle n,m\in \mathbb {Z} }كن لا مثيل له فيما يتعلق⊏{\displaystyle \sqsubset }انظر الصورة.

إن دلالات تعريف البرنامج int f(int n){...}هي دالة رياضية ماو:Z⊥→Z⊥.{\displaystyle f:\mathbb {Z} _{\bot }\to \mathbb {Z} _{\bot }.}fإذا لم يتوقف تعريف البرنامج عند إدخال بيانات معينة n، فيمكن التعبير عن ذلك رياضياً على النحو التالي:و(ن)=⊥.{\displaystyle f(n)=\bot .}يتم ترتيب مجموعة جميع الدوال الرياضية جزئيًا عن طريق تعريفو⊑ز{\displaystyle f\sqsubseteq g}إذا، لكلن،{\displaystyle n,}العلاقةو(ن)⊑ز(ن){\displaystyle f(n)\sqsubseteq g(n)}يثبت ذلك، أي إذاو(ن){\displaystyle f(n)}أقل تحديدًا أو يساويز(ن).{\displaystyle g(n).}فعلى سبيل المثال، دلالات التعبير x+x/xأقل تحديدًا من دلالات التعبير x+1، لأن الأول، وليس الثاني، يُشير إلى0{\displaystyle 0}ل⊥،{\displaystyle \bot ,}ويتفقون على خلاف ذلك.

بفرض وجود نص برمجي معين f، يتم الحصول على نظيره الرياضي كأصغر نقطة ثابتة لبعض عمليات الربط بين الدوال التي يمكن الحصول عليها عن طريق "الترجمة" f. على سبيل المثال، تعريف C

دالة ` act` تأخذ عددًا صحيحًا ` n` كمدخل ، وتعيد ` 1` إذا كان ` n` يساوي صفرًا ، وإلا تعيد `n * fact ( n - 1 ) `.

يتم تحويلها إلى خريطة

F:(Z⊥→Z⊥)→(Z⊥→Z⊥)،{\displaystyle F:(\mathbb {Z} _{\bot }\to \mathbb {Z} _{\bot })\to (\mathbb {Z} _{\bot }\to \mathbb {Z} _{\bot }),}يُعرَّف بأنه(F(و))(ن)={1لو ن=0،ن⋅و(ن-1)لو ن≠⊥ و ن≠0،⊥لو ن=⊥.{\displaystyle (F(f))(n)={\begin{cases}1&{\text{إذا كان }}n=0,\\n\cdot f(n-1)&{\text{إذا كان }}n\neq \bot {\text{ و }}n\neq 0,\\\bot &{\text{إذا كان }}n=\bot .\\\end{cases}}}

رسم الخرائطF{\displaystyle F}يُعرَّف بطريقة غير تكرارية، على الرغم من factأنه عُرِّف بشكل تكراري. في ظل قيود معينة (انظر نظرية كلين للنقطة الثابتة )، والتي تتحقق في المثال،F{\displaystyle F}بالضرورة أن يكون لها نقطة ثابتة دنيا،حقيقة{\displaystyle \operatorname {fact} }، إنه(F(حقيقة))(ن)=حقيقة⁡(ن){\displaystyle (F(\operatorname {fact} ))(n)=\operatorname {fact} (n)}للجميعن∈Z⊥{\displaystyle n\in \mathbb {Z} _{\bot }}[ 1 ] من الممكن إثبات ذلك

حقيقة⁡(ن)={ن!لو ن≥0،⊥لو ن<0 أو ن=⊥.{\displaystyle \operatorname {fact} (n)={\begin{cases}n!&{\text{if }}n\geq 0,\\\bot &{\text{if }}n<0{\text{ or }}n=\bot .\end{cases}}}

نقطة ثابتة أكبر منF{\displaystyle F}على سبيل المثال، الدالةحقيقة0،{\displaystyle \operatorname {fact} _{0},}محدد بواسطة

حقيقة0⁡(ن)={ن!لو ن≥0،0لو ن<0،⊥لو ن=⊥،{\displaystyle \operatorname {fact} _{0}(n)={\begin{cases}n!&{\text{if }}n\geq 0,\\0&{\text{if }}n<0,\\\bot &{\text{if }}n=\bot ,\end{cases}}}

ومع ذلك، فإن هذه الوظيفة لا تعكس بشكل صحيح سلوك نص البرنامج المذكور أعلاه بالنسبة للقيم السالبة.ن؛{\displaystyle n;}fact(-1)على سبيل المثال ، لن تنتهي المكالمة على الإطلاق، ناهيك عن أن تعود 0. فقط أقل نقطة ثابتة،حقيقة،{\displaystyle \operatorname {fact} ,}يمكن استخدامها بشكل معقول كدلالة لبرنامج رياضي.

التعقيد الوصفي

أظهر كلٌّ من إيمرمان [ 2 ] [ 3 ] وفاردي [ 4 ] بشكلٍ مستقلٍّ نتيجة التعقيد الوصفي التي تُفيد بأنّ خصائص البنى المرتبة خطيًا والقابلة للحساب في زمنٍ متعدد الحدود قابلةٌ للتعريف في منطق الرتبة الأولى مع عامل النقطة الثابتة الصغرى (FO(LFP)) . مع ذلك، فإنّ منطق الرتبة الأولى مع عامل النقطة الثابتة الصغرى (FO(LFP)) ضعيفٌ جدًّا بحيث لا يُمكنه التعبير عن جميع خصائص البنى غير المرتبة في زمنٍ متعدد الحدود (على سبيل المثال، كون البنية ذات حجمٍ زوجي ).

أفضل نقاط ثابتة

يمكن تعريف أعظم نقطة ثابتة لدالة ما بشكل مشابه لأصغر نقطة ثابتة، أي أنها النقطة الثابتة التي تتجاوز أي نقطة ثابتة أخرى، وفقًا لترتيب المجموعة المرتبة جزئيًا. في علوم الحاسوب ، يُستخدم مصطلح أعظم نقطة ثابتة بشكل أقل شيوعًا من مصطلح أصغر نقطة ثابتة. تحديدًا، لا تحتوي المجموعات المرتبة جزئيًا الموجودة في نظرية المجال عادةً على عنصر أعظم، وبالتالي، بالنسبة لدالة معينة، قد توجد نقاط ثابتة قصوى متعددة وغير قابلة للمقارنة ، وقد لا توجد أعظم نقطة ثابتة لتلك الدالة. لمعالجة هذه المشكلة، تم تعريف النقطة الثابتة المثلى بأنها النقطة الثابتة الأكثر تحديدًا والمتوافقة مع جميع النقاط الثابتة الأخرى. توجد النقطة الثابتة المثلى دائمًا، وهي أعظم نقطة ثابتة إذا كانت أعظم نقطة ثابتة موجودة. تسمح النقطة الثابتة المثلى بالدراسة الرسمية للدوال التكرارية والدوال التكرارية المشتركة التي لا تتقارب مع أصغر نقطة ثابتة. [ 5 ] لسوء الحظ، في حين تُظهر نظرية كلين للتكرار أن أصغر نقطة ثابتة قابلة للحساب فعليًا، فإن النقطة الثابتة المثلى لدالة قابلة للحساب قد تكون دالة غير قابلة للحساب. [ 6 ]

انظر أيضاً

ملحوظات

  1. ↑ سي. أ. غونتر؛ دي. إس. سكوت (1990). "المجالات الدلالية". في جان فان ليوين (محرر). النماذج الرسمية والدلالات . دليل علوم الحاسوب النظرية. المجلد  ب. إلسيفير. الصفحات 633-674 . ISBN  0-444-88074-7.هنا: الصفحات  636-638
  2. ↑ N. Immerman, Relational queries computable in polynomial time, Information and Control 68 (1–3) (1986) 86–104.
  3. ↑ إيمرمان، نيل (1982). "الاستعلامات العلائقية القابلة للحساب في وقت متعدد الحدود". STOC '82: وقائع الندوة السنوية الرابعة عشرة لجمعية ACM حول نظرية الحوسبة . الصفحات 147-152 . doi : 10.1145/800070.802187 .  النسخة المنقحة في المعلومات والتحكم ، 68 (1986)، 86-104.
  4. ↑ فاردي، موشيه ي. (1982). "تعقيد لغات الاستعلام العلائقية". STOC '82: وقائع الندوة السنوية الرابعة عشرة لجمعية ACM حول نظرية الحوسبة . الصفحات 137-146 . doi : 10.1145/800070.802186 . 
  5. ↑ شارغيراود، آرثر (2010). "المُركِّب الأمثل للنقطة الثابتة" (ملف PDF) . إثبات النظريات التفاعلي . سلسلة محاضرات في علوم الحاسوب. المجلد 6172. الصفحات 195-210 . doi : 10.1007/978-3-642-14052-5_15 . ISBN   978-3-642-14051-8تم الاطلاع عليه بتاريخ 30 أكتوبر 2021 .
  6. ↑ شامير، عدي (أكتوبر 1976). النقاط الثابتة للتعريفات الاسترجاعية (أطروحة دكتوراه). معهد وايزمان للعلوم. OCLC 884951223 . هنا: المثال 12.1، الصفحات 12.2-12.3

مراجع