فرایندهای متناوب: چرخه‌ها، بازتاب و شمارش رویدادها

حالت، مبدأ و قاعدهٔ به‌روزرسانی

فرایند متناوب (Periodic process)، حالت مشخصی را پس از دوره‌ای ثابت تکرار می‌کند. مبدأ زمان، مکان یا عدد نمایشگر، جهت حرکت و پیوسته یا گسسته‌بودن تغییرها را تعیین کنید. تکرار مقدار الزاماً تکرار حالت کامل نیست؛ جهت می‌تواند وضعیت بعدی را تعیین کند. آرایش آغازین، نخستین بازگشت نیست.

روش کار: یک چرخهٔ کامل را مشخص کنید؛ شماره یا زمان را به چرخه‌های کامل و باقی‌مانده تقسیم کنید؛ باقی‌مانده را با قرارداد دو سر مسیر محاسبه کنید؛ رویدادها را در بازه‌ای صریح بشمارید.

شمارش رفت‌وبرگشتی و حرکت بازتابی

برای $n\ge2$ نفر در یک صف، اگر هنگام برگشت هیچ انتهایی تکرار نشود، چرخهٔ گوینده‌ها $1,2,\ldots,n,n-1,\ldots,2$ است. طول آن $P=2(n-1)$ است. برای گویندهٔ عدد $k\ge1$، فازِ با مبدأ صفر را $r=(k-1)\bmod P$ بگیرید:

مثال کوتاه: برای شش نفر، چرخه $1,2,3,4,5,6,5,4,3,2$ است. برای عدد ۳۸، $r=37\bmod10=7$ و گوینده نفر چهارم است. نفر اول عدد ۳۱ را می‌گوید و هفت گام در چرخه نیز به نفر چهارم می‌رسد. اگر انتها تکرار می‌شود، چرخهٔ واقعی را دوباره بنویسید؛ این دوره خودبه‌خود معتبر نیست.

نقطه‌ای که با سرعت واحد بین صفر و $L$ بازتاب می‌کند، دورهٔ فاز $2L$ دارد. برای تعریف تابع فاز تاشده، $r=u\bmod(2L)$ را در $[0,2L)$ بگیرید و بگذارید:

مسیر بازتابی به‌شکل $x(t)=f_L(\phi+vt)$ نوشته می‌شود؛ سرعت فازِ علامت‌دار و فاز اولیه، جهت آغازین را مشخص می‌کنند. با اندازهٔ سرعت $s$، رفت‌وبرگشت کامل $2L/s$ زمان می‌برد. دو مقدار تاشده دقیقاً وقتی برابرند که فازهایشان به پیمانهٔ $2L$ برابر یا قرینه باشند:

هر دو شاخه را برای هر زوج حل کنید، زمان‌های مجاز را نگه دارید و اجتماع زمان رویدادها را بسازید. برخورد سه‌تایی یک نوبت است، هرچند در سه فهرست زوجی دیده شود.

مثال کوتاه: بگذارید $L=10$ و نمایشگرها $A=f_{10}(t)$، $B=f_{10}(4+t)$ و $C=f_{10}(10-t)$ باشند. در $0<t\le20$، الف و ب در $8,18$، الف و ج در $5,15$ و ب و ج در $3,13$ برابر می‌شوند. این شش زمان متمایزند. الف فقط در مضرب‌های ۲۰ به صفر بازمی‌گردد و همهٔ نمایشگرها در زمان ۲۰ به آرایش آغازین برمی‌گردند. بازگشت دوم در ۴۰ است و دوازده نوبت برابری داریم. جای‌گذاری زمان‌های زوجی در تابع تاشده، کامل‌بودن فهرست و نبود شمارش تکراریِ سه‌تایی را کنترل می‌کند.

برابری گسسته، زمان صحیح می‌خواهد

برای دو نمایشگر که فقط پس از هر ثانیهٔ کامل تغییر می‌کنند، مقدارها را در زمان صحیح $t\ge0$ بنویسید. اگر $A=a+pt$ و $B=b-qt$ باشد، شرط برابری چنین است:

مثلاً $A=5+2t$ و $B=20-3t$ در $t=3$ عدد ۱۱ را نشان می‌دهند. اگر شروع نمایشگر دوم ۲۱ باشد، $t=16/5$ می‌شود؛ نمایشگرهای گسسته هرگز برابر نمی‌شوند، هرچند خط‌های پیوسته همدیگر را قطع کنند. اگر توقف به حداقل یک به‌روزرسانی نیاز دارد، $t\ge1$ بگذارید. بخش‌پذیری و زوجیت می‌توانند زمان ناممکن را فوراً حذف کنند.

هم‌زمانی‌ها، «فقط» و رویداد توقف

اگر نخستین رویداد پس از یک دورهٔ کامل $p$ رخ دهد و منظم تکرار شود، تعداد آن در $(0,T]$ برابر $\lfloor T/p\rfloor$ است. در $(a,b]$، دو تعدادِ کف را از هم کم کنید. زمان صفر را فقط وقتی جداگانه بشمارید که قاعده آن را رویداد بداند. برای رویداد دارای تأخیر اولیه، مبدأ را جابه‌جا کنید؛ دوره‌ها به‌تنهایی فازهای متفاوت را هم‌زمان نمی‌کنند.

برای رویدادهای هم‌فاز در زمان‌های مثبت با دوره‌های $p,q,r$، هم‌زمانی هر زوج با کوچک‌ترین مضرب مشترک تکرار می‌شود. اصل شمول و عدم شمول می‌دهد:

تعداد هم‌زمانی $q,r$ بدون $p$ برابر است با:

ابتدا رویداد توقف خواسته‌شده را از این دنبالهٔ مجاز بیابید، سپس رویداد دیگری را تا آن زمان بشمارید. برای دوره‌های $p=4,q=6,r=9$، زمان‌های «فقط» دو رویداد $q,r$ از $18,54,90$ آغاز می‌شوند؛ ۳۶ و ۷۲ به‌سبب وقوع هر سه حذف می‌شوند. در رویداد مجاز سوم، $T=90$ و تعداد رویدادهای تنها از نوع اول $22-7-2+2=15$ است. ضرب شمارهٔ سوم در دورهٔ هم‌زمانی زوجی، به‌اشتباه در ۵۴ متوقف می‌شود.

برای «حداقل دو»، اجتماع سه مجموعهٔ هم‌زمانی زوجی را بگیرید. معادل آن، جمع تعدادهای زوجی منهای دو برابر تعداد سه‌تایی است. برای «دقیقاً دو»، سه برابر تعداد سه‌تایی را از جمع زوجی کم کنید. این فرمول‌ها فرض می‌کنند هر جریان رویداد در هر لحظه حداکثر یک رویداد دارد.

برنامهٔ تکراری: چرخه‌های کامل به‌اضافهٔ پیشوند

تحویل چرخه‌ای درون هر چرخه یکنواخت توزیع نمی‌شود. فرض کنید شلنگ با دبی یک لیتر در دقیقه، دو دقیقه در الف، یک دقیقه در ب و سه دقیقه در ج قرار گیرد. هر چرخهٔ شش‌دقیقه‌ای $(2,1,3)$ لیتر می‌دهد. با $t=6q+r$ و $0\le r<6$، مقدارها پیش از هر سرریز چنین‌اند:

در دقیقهٔ ۱۷، $q=2,r=5$ و مقدارها $(6,3,8)$ لیترند. اگر ظرفیت‌ها $(7,5,9)$ باشند، ج نخست در دقیقهٔ ۱۸ پر می‌شود؛ الف و ب در آن لحظه ۶ و ۳ لیتر دارند. الف بعدتر، در دقیقهٔ ۱۹، به ۷ می‌رسد. میانگین سهم تحویل به‌تنهایی زمان ۲۱ را برای الف پیش‌بینی می‌کند و زمان واقعی درون چرخه را از دست می‌دهد. همهٔ زمان‌های نامزدِ نخستین پرشدن را با برنامهٔ واقعی مقایسه کنید و فرمول را پس از نقض فرض نبود سرریز ادامه ندهید.

جابه‌جایی متناوب رتبه و عبور

رتبه از ابتدای صف شمرده می‌شود؛ وجود $k$ نفر بین دو نفر یعنی اختلاف رتبهٔ $k+1$. در جابه‌جایی‌های متناوب، ابتدا مجموع حرکت خود هر نفر را حساب کنید. مثلاً حرکت‌های رو به عقبِ مراحل فرد به‌اندازهٔ $2,4,\ldots,2k$ مجموع $k(k+1)$ دارند و حرکت‌های رو به جلوی مراحل زوج به‌اندازهٔ $3,5,\ldots,2k+1$ مجموع $k(k+2)$.

سپس رتبهٔ هر فرد نام‌برده‌ای را که عبور بر او اثر دارد اصلاح کنید. اگر الف از رتبهٔ ۷ شش جایگاه عقب برود و از ب در رتبهٔ ۱۲ بگذرد، رتبهٔ نهایی الف ۱۳ و ب ۱۱ است. میانشان یک نفر است و مجاور نیستند. حرکت رو به جلو نیز فردِ پشت‌سرگذاشته‌شده را یک رتبه عقب می‌برد. در هر مرحله حدود صف را کنترل کنید و پیش از اعمال فاصلهٔ نهایی، حالت‌های وقوع یا عدم وقوع عبور را جدا کنید. اصلاح یک عبور را در مراحل بعد دوباره اضافه نکنید.

قرارداد کفایت ۱۱۴۸: ۱ = دقیقاً یک اطلاع به‌تنهایی کافی؛ ۲ = فقط ترکیب کافی؛ ۳ = هرکدام به‌تنهایی کافی؛ ۴ = حتی ترکیب ناکافی است. برای آزمون نامزدها به کارت کفایت مراجعه کنید. اگر دو اطلاعِ مستقل و کافی، حالت‌های ناسازگار بدهند، ناسازگاری را مشخص کنید؛ از آن حالت مشترک مجاز ساخته نمی‌شود.

تلهٔ رایج: «فقط» هم هنگام یافتن رویداد توقف و هم هنگام شمارش رویدادهای پیش از آن، هم‌زمانی‌های ممنوع را حذف می‌کند. هر بار بازه و قرارداد دو سر آن را مشخص کنید.

نکتهٔ کنکوری: یک چرخهٔ کامل را صریح بنویسید، خارج‌قسمت و باقی‌مانده بگیرید و پیش از تعمیم شمارش، یک حالت نزدیک مرز را کنترل کنید.