title: اتوماتای سلولی زندگی-گونه

text: با توجه به نوع قواعد توصیف شده می‌توان دید تعداد قواعد ممکن برای اتوماتای سلولی زندگی-گونه بسیار زیاد است. در حالت کلی وضعیت هر خانه با توجه به زنده یا مرده بودنش و با توجه به امکان‌پذیر بودن یا نبودن هر یک از اعداد ۰ تا ۸ برای وضعیت زندگی‌اش در مرحله بعد از دو رشته که هر کدام formula_1 حالت دارند پس در کل formula_2 قاعده متفاوت می‌توانیم داشته باشیم. اما تعداد اندکی از این قواعد به صورت دقیق بررسی شده‌اند و برخی از این قواعد نام‌های خاص خودشان را دارند. معروف‌ترین این قواعد قاعده بازی زندگی کانوی است، قاعده این بازی به صورت ۲۳/۳ است و تعداد زیادی از الگوهای آن مورد بررسی قرار گرفته‌اند. قواعد بسیار زیادی با الهام گرفتن از بازی زندگی کانوی به وجود آمده‌اند، تلاش عمده این قواعد برای ایجاد و پخش گلایدرهای منظم است.


title: اتوماتای سلولی زندگی-گونه

text: چند نمونه از قواعد معروف را در این بخش می‌آوریم: این موراد فقط چند مورد از موارد متعدد بررسی شده از اتوماتای سلولی زندگی-گونه هستند. در سایت mirekw توصیف تعداد بیشتری از این اتوماتا آمده‌است.


title: اتوماتای سلولی زندگی-گونه

text: انواع متعددی از اتوماتای سلولی با الهام گرفتن از اتوماتای سلولی زندگی-گونه ساخته شده‌اند. در اغلب این اتوماتا تعداد همسایگی بیشتر از همسایگی مور است. در نوع دیگری از اتوماتای سلولی به جای فضای دوبعدی از فضای سه‌بعدی استفاده می‌کنند، همچنین انواعی از اتوماتای سلولی که سلول‌ها به صورت مثلث یا شش ضلعی هستند نیز طراحی شده‌اند.


title: سوفیک سارگسیان

text: سوفیک سارگسیان (؛ ؛ زاده ) یک هنرپیشه اهل ارمنستان است. وی از سال ۱۹۷۴ میلادی فعالیت می‌کند.


title: سوفیک سارگسیان

text: وی در ۸ دسامبر ۱۹۵۱ در ایروان به دنیا آمد و از فارغ‌التحصیل شد. سارگسیان بین سال‌های ۱۹۷۸–۱۹۸۰ به هنرپیشه در تئاتر نمایشی هراچیا غاپلانیان فعالیت کرده‌است. وی از سال ۱۹۹۵ در انستیتو دولتی سینما و تئاتر ایروان تدریس می‌کند.


title: ماشین الگوریتم حالت

text: روش ماشین الگوریتمی(انگلیسی: Algorithmic state machine) یا (ASM) یک روش برای طراحی ماشین‌ها است. این ماشین برای نشان دادن نمودارهایمدارهای دیجیتال یکپارچه شده‌استفاده می‌شود. نمودار ASM، مانند نمودار حالت است اما غیررسمی تر و در نتیجه درک آن آسان‌تر است. یک نمودار ASM یک روش توصیف عملیاتی پی در پی و متوالی یک سیستم دیجیتال است.


title: ماشین الگوریتم حالت

text: روش ASM از مراحل زیر تشکیل شده‌است.


title: ماشین الگوریتم حالت

text: نمودار ASM، شامل چهار عنصر اساسی است. نام واحد، واحد، چک کردن واحد، خروجی‌های شرطی. یک ASM به صورت یک مستطیل نشان داده می‌شود که حالت‌ها از یک نمودار منظم می‌باشد. خروجی از نوع ماشین مور در درون مستطیل نشان داده شده‌است. نام واحد: نام یک واحد در داخل دایره نشان داده شده‌است؛ و دایره در گوشه سمت چپ قرار دارد یا نام بدون دایره قرار دارد. باکس واحد خروجی واحد در داخل مستطیل نشان داده شده‌است. باکس تصمیم‌گیری یک لوزی نشان می‌دهد که شرط بیان شده مورد آزمایش قرار گرفته و مسیر خروجی به ترتیب انتخاب می-شود. شرایط بیان شامل یک یا چند ورودی به FSM می‌باشد. برای وضعیت ASM نشان داده شده توسط یک لوزی یا یک ورودی و دو خروجی است و به شرط انتقال بین دو حالت یا یک حالت و خروجی مشروط استفاده می‌شود. باکس تصمیم‌گیری حاوی شرایط بیان شده برای آزمایش بوده و این بیان شامل ورودی برای FSM می‌باشد. باکس خروجی شرطی: باکس خروجی شرطی به شکل بیضی نشان داده می‌شود که سیگنال خروجی از نوع میلی می‌باشد. این خروجی‌ها نه تنها به واحد بلکه همچنین به ورودی‌های FSM نیز بستگی دارد.


title: ماشین الگوریتم حالت

text: هنگامی که عملیات مورد نظر در یک مدار با استفاده از عملیات RTL توصیف شده‌است، اجراهای مسیر داده می‌توانند مشتق شوند. هر متغیر منحصر به فرد که یک مقدار در برنامه RTL را به خود اختصاص داده‌است که می‌تواند به عنوان یک واحد ثبت شده اجرا شود، وابسته به عملیات عملکردی که هنگام اختصاص یک مقدار به یک متغیر انجام می‌شود، ثبت برای آن متغیر ممکن است به صورت ساده بوده و متغیر در آن دیده شود و یک شمارنده پیش از بلوک منطقی به صورت ترتیبی قرار بگیرد. بلوک منطقی ترتیبی با یک ثبت مرتبط است؛ و می‌تواند یک کامپایلر را از طریق تابع منطقی ترکیبی اجرا کند.


title: ماشین الگوریتم حالت

text: هنگامی که مسیر داده طراحی شد، نمودار ASM به یک نمودار دقیق تبدیل می‌شود. نماد RTL با سیگنال‌های تعریف شده در مسیر داده جایگزین می‌شود.


title: رودولف قوندیان

text: رودولف قوندیان (؛ ؛ زاده – درگذشته ۱۷ ژوئیه ۲۰۱۹) یک هنرپیشه اهل ارمنستان بود که بین سال‌های ۱۹۷۰ تا ۲۰۱۰ میلادی فعالیت می‌کرد.


title: رودولف قوندیان

text: وی در ۶ مارس ۱۹۵۲ در کیسلوفودسک، سرزمین استاوروپول به دنیا آمد و از فرهنگستان دولتی تئاتر سوندوکیان فارغ‌التحصیل شد. وی همچنین برندهٔ جوایزی همچون هنرمند مردمی ارمنستان (۲۰۱۷) شده‌است. وی در ۱۷ ژوئیهٔ ۲۰۱۹ در سن ۶۷ سالگی در بلژیک درگذشت.


title: رودولف قوندیان

text: از فیلم‌ها یا برنامه‌های تلویزیونی که وی در آن نقش داشته‌است می‌توان به "ناهاپت" (۱۹۷۷)، "رفیق پانجونی" (۱۹۹۳)، "خون"، اشاره کرد.


title: برداری‌سازی خودکار

text: برداری‌سازی خودکار، یک روش بهینه‌سازی کامپایلر است که در آن بهینه‌سازی بر روی آرایه (ساختمان داده‌ها)ها صورت می‌گیرد. این روش با موازی‌سازی عملیات بر روی آرایه‌ها باعث می‌شود که سرعت برای حلقه‌های خاصی بسیار بهبود می‌یابد. برای مثال فرض کنید که قرار است دو بردار را با هم جمع کنید. در این حالت حلقه‌ای داریم که پارامترهای متناظر دو بردار را با هم جمع می‌کند. حال از آن‌جا که پارامترهای مختلف هر بردار بر روی هم تأثیری نمی‌گذارند می‌توان تمام این عملیات جمع کردن را با هم انجام داد و آن را از حالت سری که در حلقه وجود دارد می‌توان خارج کرد. برای مثال اگر فضای برداری ما ۴ بعدی باشد عملاً مجموع دو بردار به صورت زیر پیاده‌سازی می‌شود. حال اگر همین مثال بالا را بخواهیم برای فضای برداری n بعدی پیاده‌سازی کنیم باید از حلقه استفاده کنیم و می‌توانیم به روشی که در پایین اشاره شده‌است بسنده کنیم.


title: برداری‌سازی خودکار

text: for (i=0; iرایانه‌های اولیه تمام عملیات‌های خود را به صورت سری انجام می‌دادند به عبارتی در هر واحد زمانی یک کار انجام می‌دادند. با گذشت زمان رایانه‌ها این قابلیت را پیدا کردند که چند کار را در یک واحد زمانی انجام دهند و از ان زمان مسئله موازی‌سازی مطرح بود. کامپایلرها نیز ازین قاعده مستثنا نبودند و به سمت موازی‌سازی رفته‌اند که یکی از این روش‌ها برداری‌سازی خودکار است.


title: برداری‌سازی خودکار

text: Intel's MMXو SSEو AVX و AltiVec و ARM's NEON از این نوع خودکارسازی پشتیبانی می‌کنند.


title: برداری‌سازی خودکار

text: مانند هر بهینه‌سازی دیگر اهمیت زیادی دارد که بهینه‌سازی انجام شده باعث به وجود آمدن خطا در پاسخ نشود. روش برداری‌سازی خودکار از حساس‌ترین روش‌ها به این آفت است. در پایین دو مورد از خطاهایی که ممکن است با آن مواجه شویم را آورده‌ایم.


title: برداری‌سازی خودکار

text: تمام وابستگی‌ها در متغیرها را باید در نظر بگیریم. ممکن است در حلقهٔ ما متغیرها بعد از مدتی تغییر کنند و طبعاً موازی‌سازی می‌تواند باعث به وجود آمدن جواب غلط شوند. برای بررسی این مسئله نیز الگوریتمی موجود است که به وسیلهٔ ساخت گراف وابستگی این مسئله را برای ما حل می‌کند. به عبارتی در صورتی می‌توانیم بین دو قسمت مختلف حلقه موازی‌سازی انجام که در گراف وابستگی به هم متصل نباشند.


title: برداری‌سازی خودکار

text: ممکن است متغیرهای موجود در بردارها از نوع متفاوتی باشند و ممکن است در انجام عملیات‌های مجبور باشیم بعضی از آن‌ها را به هم تبدیل کنیم و برای همین موازی‌سازی می‌تواند باعث به وجود آمدن خطا در داده‌ها شود.


title: برداری‌سازی خودکار

text: همان‌طور که در بخش قبل گفتیم اولین مرحله در روش برداری‌سازی خودکار پیدا کردن وابستگی بین داده هاست. به عبارتی نباید دو دو خط از حلقهٔ مورد نظر که به هم مرتبطند را هم‌زمان انجام دهیم برای مثال:


title: برداری‌سازی خودکار

text: for (i = 0; i < 128; i++) { }در مثال بالا همان‌طور که می‌بینیم اگر دو جملهٔ متوالی را بخواهیم به صورت موازی با هم انجام دهیم به نتیجهٔ غلطی می‌رسیم. پس بنا بر مثالی که در بالاتر دیدیم وابستگی داده‌ها اهمیت زیادی دارد و با ساخت درخت وابستگی و انجام الگوریتم‌های مشخص می‌توانیم این موازی سازی‌ها را انجام دهیم.


title: برداری‌سازی خودکار

text: برخی از برداری‌سازی‌ها در زمان کامپایل به صورت کامل انجام می‌گیرند به عبارتی می‌توان در همان زمان کامپایل وابستگی داده‌ها به هم را تشخیص داد و با استفاده از برداری سازی، موازی‌سازی انجام داد برای مثال در همان زمان کامپایل کد زیر را می‌توان به صورت کامل بر روی آن انجام داد. int a[128]; int b[128]; // initialize b


title: برداری‌سازی خودکار

text: for (i = 0; i<128; i++) برخی از کدها ممکن است در زمان اجرا به هم مرتبط شوند پس نمی‌توان در همان زمان کامپایل گراف وابستگی آن‌ها را به‌طور کامل انجام داد. برای مثال کد زیر کاملاً مشابه کد بالاست با این تفاوت که دو متغیر در زمان اجرا ساخته می‌شوند و در زمان کامپایل قابل تشخیص نیستند.


title: برداری‌سازی خودکار

text: int *a = malloc(128*sizeof(int)); int *b = malloc(128*sizeof(int)); // initialize b


title: برداری‌سازی خودکار

text: for (i = 0; i<128; i++, a++, b++) // ... free(b); free(a); دراین جا به یک مثال ساده برای مفهوم شدن نحوهٔ برداری‌سازی ارائه می‌کنیم. این مثال را در نظر بگیرید:


title: برداری‌سازی خودکار

text: بر اساس میزان موازی‌سازی که می‌توانیم انجام دهیم برداری‌سازی انجام می‌شود. مثلاً اینجا می‌خواهیم هر سه جمله را به‌طور موازی با هم ضرب کنیم.


title: ورویر پانویان

text: ورویر مارتیروسی پانویان (؛ ؛ زاده – درگذشته ) یک هنرپیشه اهل ارمنستان بود. وی بین سال‌های ۱۹۶۷ تا ۱۹۷۷ میلادی فعالیت می‌کرد.


title: ورویر پانویان

text: وی در ۳ سپتامبر ۱۹۰۷ در وانادزور، استان لوری به دنیا آمد وی همچنین برندهٔ جوایزی همچون هنرمند مردمی ارمنستان شوروی (1961) شده‌است. وی در ۲۷ مهٔ ۱۹۷۷ در سن ۶۹ سالگی در آرتاشات درگذشت.


title: ورویر پانویان

text: از فیلم‌ها یا برنامه‌های تلویزیونی که وی در آن نقش داشته‌است می‌توان به ناهاپتاشاره کرد.


title: آرتاشس گیوداکیان

text: آرتاشس مکرتچی گیوداکیان (؛ ؛ – ) یک هنرپیشه اهل ارمنستان بود. وی بین سال‌های ۱۹۷۴ تا ۱۹۹۲ میلادی فعالیت می‌کرد.


title: آرتاشس گیوداکیان

text: وی برندهٔ جوایزی همچون هنرمند افتخاری ارمنستان شوروی شده‌است.


title: آرتاشس گیوداکیان

text: از فیلم‌ها یا برنامه‌های تلویزیونی که وی در آن نقش داشته‌است می‌توان به "ناهاپت" (۱۹۷۷)، "رفیق پانجونی" (۱۹۹۳)، "ستاره امید" (۱۹۷۸)، "یک تکه از آسمان (فیلم ۱۹۸۰)" (۱۹۸۰)، "آرئویک (فیلم)" (۱۹۷۸)، "تانگوی کودکی ما)" (۱۹۸۴) اشاره کرد.


title: ماراته‌آ

text: ماراته‌آ (به ایتالیایی: Maratea) یک کومونه در ایتالیا است که در استان پوتنزا واقع شده‌است. ماراته‌آ ۶۷ کیلومتر مربع مساحت و ۵٬۲۰۵ نفر جمعیت دارد و ۳۰۰ متر بالاتر از سطح دریا واقع شده‌است.


title: ماراته‌آ

text: شهرهای بولتسانو، سنتو، فرارا، کاروزینو و آوترانا خواهرخوانده‌های ماراته‌آ هستند.


title: الگوریتم مارکوف

text: در علوم نظری کامپیوتر، الگوریتم مارکوف یک سیستم بازنویسی رشته‌ای است که قوانین گرامر-مانندی را بر روی رشته‌ای از نمادها اعمال می‌کند. الگوریتم مارکوف به عنوان یک تورینگ کامل نشان داده شده‌است که به این معنی است که آن‌ها به عنوان یک مدل کلی از یک سری محاسبات مناسب هستند که می‌توانند بیانگر هر عبارت ریاضی از علامت ساده خود باشد. الگوریتم مارکوف به نام آندرس مارکوف ریاضیدان سابق نامگذاری شده‌است.


title: الگوریتم مارکوف

text: Refal یک زبان برنامه‌نویسی مبتنی بر الگوریتم مارکوف است.


title: الگوریتم مارکوف

text: الگوریتم‌های عادی، کلامی هستند که به عنوان کلماتی که در الفباهای مختلف به کار برده می‌شوند، در نظر گرفته می‌شود.


title: الگوریتم مارکوف

text: تعریف هر الگوریتم عادی شامل دو بخش است: یکی تعریف الفبای الگوریتم (الگوریتم برای کلمات این نمادهای الفبایی به کار برده خواهد شد) و دیگری تعریف برای طرح آن است. طرح الگوریتم عادی یک مجموعه محدود از فرمول‌هایی است که به اصطلاح به آن‌ها فرمول جایگزینی می‌گوییم که هر کدام می‌تواند ساده یا نهایی باشد. یک فرمول جایگزینی ساده کلماتی هستند به شکل formula_1، که formula_2 و formula_3 دو کلمه دلخواه در الفبای الگوریتم هستند (که به ترتیب سمت چپ و سمت راست در فرمول جایگزینی نامیده می‌شوند) به‌طور مشابه فرمول جایگزینی نهایی کلماتی هستند به شکل formula_4، هستند که formula_2 و formula_3 دو کلمه دلخواه در الفبای الگوریتم هستند. با این فرض که کاراکترهای کمکی formula_7و formula_8 ، به الفبای الگوریتم تعلق ندارند.


title: الگوریتم مارکوف

text: یک مثال از طرح الگوریتم عادی که شامل الفبای پنج حرفی formula_9 است می‌تواند مانند طرح زیر باشد.


الگوریتم مارکوف


title: الگوریتم مارکوف

text: روند استفاده از الگوریتم عادی برای یک کلمه دلخواه formula_11 در الفبای الگوریتم، یک توالی گسسته از مراحل ساده است که شامل موارد زیر است. فرض کنیم formula_12 کلمه‌ای است که در مرحله قبلی الگوریتم به دست آمده‌است، (یا کلمه اصلی formula_11، اگر مرحله فعلی قدم اول شماست). اگر در بین فرمول‌های جایگزینی، سمت چپی وجود نداشته باشد که شاملformula_12 باشد، کار الگوریتم تکمیل شده و نتیجه این الگوریتم کلمه formula_12 در نظر گرفته می‌شود. در غیر این صورت گزینه‌هایی هستند که در سمت چپ آن‌ها قسمتی از formula_12 ظاهر شده‌است اولین گزینه را انتخاب می‌کنیم، اگر فرمول جایگزینی یه شکل formula_1 باشد پس از بین تمام حالت‌های مختلفی که می‌توان formula_12 را به شکل formula_19 نشان داد حالتی را انتخاب می‌کنیم که formula_20 کوچکترین طول را داشته باشد، بعد از اعمال آن قانون نتیجه مرحله فعلی formula_21 می‌شود و به سراغ مرحله بعد می‌رویم. حال اگر این فرمول جایگزینی به شکل formula_4 باشد، پس از انجام مراحل قبل که جواب آن به formula_21 ختم می‌شود و کار الگوریتم به پایان می‌رسد.


title: الگوریتم مارکوف

text: برای مثال در طول فرایند به‌کارگیری الگوریتم با استفاده از طرح بالا، روی کلمه formula_24 به ترتیب کلمات formula_25، formula_26، formula_27، formula_28، formula_29، formula_30، formula_31، formula_32، formula_33، formula_34 و formula_35 ظاهر می‌شود، پس از آن الگوریتم با نتیجه formula_36 متوقف می‌شود.


title: الگوریتم مارکوف

text: هر الگوریتم عادی معادل ماشین تورینگ است و بالعکس، هر ماشین تورینگ معادل الگوریتم عادی است. یک نسخه از تز چرچ-تورینگ که در رابطه با الگوریتم عادی فرموله شده‌است، اصل نرمالیزاسیون نامیده می‌شود.


title: الگوریتم مارکوف

text: الگوریتم‌های عادی ثابت کرده‌اند که ابزار مناسبی برای ساخت بسیاری از بخش‌های برساخت‌گرایی ریاضیات هستند. علاوه بر این، به‌طور ذاتی الگوریتم‌های عادی در تعدادی از ایده‌های مربوط به اداره اطلاعات نمادها در زبان‌های برنامه‌نویسی استفاده شده‌است. به عنوان مثال در Refal


title: الگوریتم مارکوف

text: قوانین توالی به صورت جفت رشته‌ها هستند. معمولاً به شکل الگوی → نشان داده می‌شوند. هر قاعده ممکن است عادی یا نهایی باشد.


title: الگوریتم مارکوف

text: با توجه به یک رشته ورودی:


title: الگوریتم مارکوف

text: مثال زیر نشانگر عملیاتی ساده از الگوریتم مارکوف است."I bought a B of As from T S."


title: الگوریتم مارکوف

text: اگر الگوریتم برای مثال بالا به کار برده شود، رشته نماد به روش زیر تغییر خواهد کرد. سپس الگوریتم خاتمه خواهد یافت.


title: الگوریتم مارکوف

text: این قوانین مثالی جالب تر را ارائه می‌دهد، آن‌ها اعداد دودویی را به شکل تعداد معادلی خط بازنویسی می‌کنند. به عنوان مثال ۱۰۱ به یک رشته از ۵ خط متوالی بازنویسی خواهد شد."۱۰۱"


title: الگوریتم مارکوف

text: اگر الگوریتم برای مثال بالا اجرا شود. بعد از مراحل زیر الگوریتم متوقف خواهد شد.


title: سان بازیله

text: سان بازیله (به ایتالیایی: San Basile) یک کومونه در ایتالیا است که در استان کزنتزا واقع شده‌است. سان بازیله ۱۸ کیلومتر مربع مساحت و ۱٬۲۸۳ نفر جمعیت دارد و ۵۴۰ متر بالاتر از سطح دریا واقع شده‌است.


title: کانا (کالابریا)

text: کانا (به ایتالیایی: Canna) یک کومونه در ایتالیا است که در استان کزنتزا واقع شده‌است. کانا ۲۰ کیلومتر مربع مساحت و ۸۲۸ نفر جمعیت دارد و ۴۱۷ متر بالاتر از سطح دریا واقع شده‌است.


title: چیکالا

text: چیکالا (به ایتالیایی: Cicala) یک کومونه در ایتالیا است که در استان کاتانزارو واقع شده‌است. چیکالا ۹ کیلومتر مربع مساحت و ۹۶۴ نفر جمعیت دارد و ۸۳۷ متر بالاتر از سطح دریا واقع شده‌است.


title: کاسانا آلیونیو

text: کاسانا آلیونیو (به ایتالیایی: Cassano all'Ionio) یک کومونه در ایتالیا است که در استان کزنتزا واقع شده‌است. کاسانا آلیونیو ۱۵۴ کیلومتر مربع مساحت و ۱۸٬۶۵۲ نفر جمعیت دارد و ۲۵۰ متر بالاتر از سطح دریا واقع شده‌است.


title: چینش باد

text: چینش باد یا برش باد () به معنای تغییر سمت و سرعت باد در ارتفاعات مختلف جوی است. به عبارتی دیگر، تغییر محلی بُردار باد یا هریک از مؤلفه‌های آن در یک راستای معین را چینش باد می‌گویند.


title: چینش باد

text: چینش باد به تغییر ناگهانی سرعت باد در یک فاصلهٔ کوتاه افقی اطلاق می‌گردد که در این شرایط تغییر سریعی در میزان لیفت و در پی آن ارتفاع هواپیما رخ می‌دهد. همواره میزان زیادی چینش باد در جو موجود است اما برش‌های باد قوی موجب تشکیل چرخند و تگرگ می‌شود همواره میزان زیادی چینش باد در نزدیک جبهه‌ها و جت استریم‌ها وجود دارد چینش باد یک لایه جوی ناپایدار است که در CAT هم به وجود می‌آید.


title: چینش باد

text: چینش قائم باد در محیط اطراف چرخندهای گرمسیری بسیار با اهمیت است. منظور از چینش باد میزان تغییر در سرعت و جهت باد با افزایش ارتفاع است. هنگامی که برش باد ضعیف باشد توفان که قسمتی از چرخنده است به صورت قائم رشد می‌کند و گرمای نهان ناشی از چگالش در هوایی که مستقیماً در بالای توفان قرار دارد آزاد می‌شود و به توسعه توفان کمک می‌کند هنگامی که برش باد قوی تری وجود داشته باشد توفان به صورت اریب و کج در می‌آید و گرمای نهان بر روی منطقه گسترده‌تری آزاد می‌شود.


title: ملیکوکا

text: ملیکوکا (به ایتالیایی: Melicuccà) یک کومونه در ایتالیا است که در استان رجو کالابریا واقع شده‌است. ملیکوکا ۱۷٫۲ کیلومتر مربع مساحت و ۱٬۰۲۸ نفر جمعیت دارد.


title: چنتولا

text: چنتولا (به ایتالیایی: Centola) یک کومونه در ایتالیا است که در استان سالرنو واقع شده‌است. چنتولا ۴۷ کیلومتر مربع مساحت و ۵٬۰۷۳ نفر جمعیت دارد و ۳۳۶ متر بالاتر از سطح دریا واقع شده‌است.


title: چروینو (کامپانیا)

text: چروینو (به ایتالیایی: Cervino) یک کومونه در ایتالیا است که در استان کسرتا واقع شده‌است. چروینو ۸٫۰ کیلومتر مربع مساحت و ۵٬۱۳۷ نفر جمعیت دارد.


title: ساککو

text: ساککو (به ایتالیایی: Sacco) یک کومونه در ایتالیا است که در استان سالرنو واقع شده‌است. ساککو ۲۳ کیلومتر مربع مساحت و ۵۸۲ نفر جمعیت دارد و ۵۰۰ متر بالاتر از سطح دریا واقع شده‌است.


title: ارریا

text: اُرریا (به ایتالیایی: Orria) یک کومونه در ایتالیا است که در استان سالرنو واقع شده‌است. ارریا ۲۶٫۵۵ کیلومتر مربع مساحت و ۱٬۱۶۱ نفر جمعیت دارد و ۵۴۰ متر بالاتر از سطح دریا واقع شده‌است.


title: کنتورسی ترمه

text: کُنتورسی تِرمه (به ایتالیایی: Contursi Terme) یک کومونه در ایتالیا است که در استان سالرنو واقع شده‌است. کنتورسی ترمه ۲۸٫۹۰ کیلومتر مربع مساحت و ۳٬۲۸۱ نفر جمعیت دارد و ۲۵۰ متر بالاتر از سطح دریا واقع شده‌است.


title: کنتورسی ترمه

text: شهر مورو لوکانو خواهرخواندهٔ کنتورسی ترمه هست.


title: چرازو

text: چِرازو (به ایتالیایی: Ceraso) یک کومونه در ایتالیا است که در استان سالرنو واقع شده‌است. چرازو ۴۵٫۹۵ کیلومتر مربع مساحت و ۲٬۵۱۰ نفر جمعیت دارد و ۳۴۰ متر بالاتر از سطح دریا واقع شده‌است.


title: پیونددهنده پویا

text: در نظریهٔ محاسبات، پیوند دهندهٔ پویا (به انگلیسی: Dynamic Linker) بخشی از سیستم‌عامل است که وظیفهٔ بارگذاری منابع و کتابخانه‌های مورد نیاز برنامهٔ اجرایی و پیوند دادن آن‌ها را به برنامه در زمان اجرا بر عهده دارد.


title: پیونددهنده پویا

text: پیوند دادن معمولاً به فرایندی اطلاق می‌شود که در آن منابع مورد نیاز یک برنامه قبل از اجرا، در زمان کامپایل و توسط کامپایلر به آن برنامه متصل می‌شوند تا یک بستهٔ اجرایی (به انگلیسی: Executable) کامل ایجاد شود. در مقابل پیوند دهندهٔ پویا منابع مورد نیاز را در زمان اجرای برنامه در آن بارگذاری کرده و سپس آن‌ها را به برنامهٔ در حال اجرا مقید (به انگلیسی: Bind) می‌کند.


title: پیونددهنده پویا

text: پیونده دهندهٔ پویا عملیات بارگذاری و پیوند منابع و کتابخوانه‌ها را در زمان اجرای برنامه بر عهده دارد. به این صورت که کتابخوانه‌های اشتراکی (به انگلیسی: Shared Libraries) و منابع مورد نیاز برنامه را در زمان اجرا و در صورتی که در حافظهٔ اصلی موجود نباشند، از حافظهٔ پایدار (به انگلیسی: Persistent Storage) به حافظهٔ اصلی منتقل کرده، سپس جدول‌های پرش (به انگلیسی: Jump Table) برنامهٔ بارگذاری شده را با آدرس‌های منابع اشتراکی تکمیل و اشاره‌گرهای (به انگلیسی: Pointer) با آدرس مطلق برنامه را آدرس دهی می‌کند.


title: پیونددهنده پویا

text: پیاده‌سازی پیوند دهندهٔ پویا و بارگذار پویا و توانایی‌ها و کاربردهای آن‌ها بسته به نوع و ردهٔ سیستم‌عامل و نوع فایل‌های اجرایی و منابع مورد نیاز آن‌ها ممکن است متفاوت باشد.


title: پیونددهنده پویا

text: کتابخانهٔ پیوندی پویا (به انگلیسی Dynamic-link library) یا DLL نام پیاده‌سازی شرکت مایکروسافت از مفهوم کتابخانهٔ اشتراکی است.


title: پیونددهنده پویا

text: این پیاده‌سازی در سیستم‌های عامل ویندوز و OS/2 به کار گرفته شده‌است. فایل‌های کتابخانه‌ای در این پیاده‌سازی معمولاً از پسوند DLL استفاده می‌کنند.


title: پیونددهنده پویا

text: ساختار و قالب این فایل‌ها مانند فایل‌های اجرایی سیستم‌عامل ویندوز (فایل‌های با پسوند EXE) است، از این رو این فایل‌ها می‌توانند شامل بخش‌های مختلفی از جنس کد منبع، اطلاعات برنامه و منابع اجرایی باشند.


title: پیونددهنده پویا

text: کتابخانه‌های اجرایی که تنها شامل اطلاعات و منابع اجرایی باشند را DLLهای منبع می‌نامند.


title: پیونددهنده پویا

text: به عنوان مثالی از این نوع کتابخانه‌های اشتراکی می‌توان کتابخانه‌های آیکون (با پسوند ICL) و برخی از قلم‌ها (به انگلیسی: font) (با پسوندهای FON و FOT) اشاره کرد.


title: پیونددهنده پویا

text: در بسیاری از سیستم‌های عامل بر پایهٔ یونیکس (به انگلیسی: Unix) کتابخانه‌های اشتراکی کاملاً مانند برنامه‌های اجرایی عادی هستند.


title: پیونددهنده پویا

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


title: پیونددهنده پویا

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


title: پیونددهنده پویا

text: وظیفهٔ بارگذاری رویه‌های کتابخانه‌های اشتراکی و برنامهٔ اصلی در فضای آدرس دهی برنامه و در نهایت شروع روال اجرا بر عهدهٔ پیونددهندهٔ پویا است.


title: پیونددهنده پویا

text: در سیستم‌های عامل لینوکس (به انگلیسی: Linux) فایل‌های کتابخانه‌های اجرایی اشتراکی از پسوند SO استفاده می‌کنند.


title: پیونددهنده پویا

text: در سیستم‌عامل داروین (به انگلیسی: Darwin) شرکت اپل و سیستم‌های عامل macOS و iOS که بر پایهٔ آن بنا شده‌اند نوع پیونده‌دهندهٔ پویایی که باید برای پیونددادن برنامه و کتابخانه‌های مورد استفاده‌اش استفاده شود در زمان پیوند مشخص می‌شود. به این منظور آدرس فایل اجرایی دودویی این پیونددهنده در فضای آدرس دهی پردازه قرار داده می‌شود.


title: پیونددهنده پویا

text: فایل‌های کتابخانه‌های اشتراکی در این سیستم‌های عامل از پسوند DYLIB استفاده می‌کنند.


title: پیونددهنده پویا

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


title: پیونددهنده پویا

text: در این سیستم‌های عامل، یک برنامه می‌تواند مدت‌ها پس از شروع اجرایش با تعامل با پیوند دهنده باعث بارگذاری منابع بیشتر یا خارج کردن منابع قبلی از حافظه شود.


title: پیونددهنده پویا

text: این رفتار ویژه به منظور ارائهٔ سرویس‌های مورد نیاز در رابط‌های برنامه‌نویسی کاربردی (به انگلیسی: Application Programming Interface یا API) شرکت اپل مانند Cocoa و Objective-C در نظر گرفته شده‌است.


title: پیونددهنده پویا

text: پیونددهندهٔ پویای اپل در سیستم‌عامل macOS یک پیونده‌دهندهٔ متن باز است که از طریق پروژهٔ متن باز اپل در دسترس عموم قرار دارد.


title: پیونددهنده پویا

text: در سیستم‌های عامل بر پایهٔ XCOFF مانند AIX شرکت IBM فایل‌های کتابخانه‌های اجرایی اشتراکی از پسوند A استفاده می‌کنند.


title: ان ال

text: در نظریه پیچیدگی محاسباتی اِن‌اِل (NL) به کلاس پیچیدگی مسائلی از مسائل تصمیم‌گیری گفته می‌شود که توسط ماشین تورینگ غیرقطعی و با حافظه لگاریتمی نسبت به اندازه ورودی، قابل حل هستند.


title: ان ال

text: NL تعمیمی از مسائل کلاس اِل است که در مسائل کلاس L مسائلی قرار دارند که با پیچیدگی حافظه لگاریتمی نسبت به اندازه ورودی بر روی ماشین تورینگ قطعی قابل حل هستند. کلاس NL به کمک نمادگذاری NPSPACE نیز قابل تعریف است: formula_1


title: ان ال

text: نتایج مهم در نظریه پیچیدگی کلاس مسائل NL را به برخی از کلاس‌های دیگر مرتبط می‌کند. این در حالی است که رابطه NL با برخی دیگر از کلاس‌ها همچنان به عنوان بعضی از مهم‌ترین مسائل حل نشده در نظریه پیچیدگی مطرح می‌شوند. یکی از این مسائل بررسی برقراری تساوی بین L و NL یا به‌طور دقیق‌تر "آیا formula_2 است؟" می‌باشد.


title: ان ال

text: به کمک تعریف اصلی ماشین تورینگ ساده که تنها دارای یک نوار است، مسائل پیچیدگی فضای لگاریتمی قابل بحث نیستند زیرا اندازه خود ورودی به صورت بدیهی از مرتبه formula_3 است و استفاده از حافظه از مرتبه formula_4 بی‌معنی خواهد بود. به همین دلیل تعریف ماشین تورینگ تغییر پیدا می‌کند.


title: ان ال

text: در این نوع ماشین تورینگ، دو نوار وجود دارد: نوار فقط-خواندنی که روی آن ورودی قرار داده شده‌است و این نوار یک سر دارد که آزادانه روی آن می‌تواند حرکت کند ولی خود نوار غیرقابل تغییر است. نوار دوم هم که نوار خواندن-نوشتن است مانند ماشین تورینگ عادی یک سر دارد و قابلیت خواندن و نوشتن را فراهم می‌کند. با توجه به اینکه بر روی نوار فقط-خواندنی امکان علامت‌گذاری خانه‌های آن و به تبع آن تشخیص دو انتهای چپ و راست نوار وجود ندارد، فرض می‌کنیم که قابلیت تشخیص رسیدن به دو سر نوار برای ماشین تورینگ وجود دارد. حال به کمک این تعریف از ماشین تورینگ، پیچیدگی فضا برابر با تعداد خانه‌های خوانده شده بر روی نوار خواندن-نوشتن تعریف می‌شود و در نتیجه با قرار گرفتن ورودی بر روی نوار فقط-خواندنی، در مسائل کلاس حجمی لگاریتمی، مستقل از نوار ورودی، می‌توان از لگاریتم اندازه ورودی از نوار خواندن-نوشتن استفاده کرد.


title: ان ال

text: یک مبدّل فضای لگاریتمی یک ماشین تورینگ با تعریف اشاره شده در بالا است که در نوار خواندن-نوشتن آن می‌تواند تنها شامل formula_4 نماد باشد. مبدل فضای لگاریتمی M تابع formula_6 است و هنگامی که formula_7 رشته ورودی روی نوار فقط-خواندن باشد، formula_8 رشته باقی‌مانده بر روی نوار خواندن-نوشتن در پایان است. در این صورت formula_9 یک تابع قابل محاسبه در فضای لگاریتمی است.


title: ان ال

text: زبان formula_10 به زبان formula_11 با فضای لگاریتمی قابل کاهش است اگر یک نگاشت قابل کاهش از formula_10 به formula_11 به وسیله یک تابع قابل محاسبه در فضای لگاریتمی مانند formula_9 وجود داشته باشد. نمادگذاری جمله بالا به صورت زیر است:


ان ال


title: ان ال

text: زبان formula_11 یک زبان NL-Complete است اگر


title: ان ال

text: مسائل مشهوری مانند اتصال-ST و 2-ارضاپذیری NL-Complete هستند. در مسئله اتصال-ST به عنوان ورودی یک گراف و دو راس S و T داده می‌شوند و مسئله تصمیم‌گیری وجود داشتن یک مسیر از S به T است. در مسئله 2-ارضاپذیری هم ارضاپذیر بودن یک عبارت منطقی حاصل AND منطقی بین چند عبارت که خود این عبارات نیز از OR شدن 2 متغیر تشکیل شده اند، سؤال می‌شود. نمونه‌ای از عبارات منطقی به شکل زیر است:


title: ان ال

text: به دلیل وجود الگوریتم چندجمله‌ای برای حل مسئله 2-ارضاپذیری و با توجه به NL-Complete بودن آن، مجموعه P شامل مجموعه NL می‌شود. این در حالی است که به سوال‌هایformula_21 یا formula_22 هنوز جوابی داده نشده‌است.


title: ان ال

text: در مورد مقایسه NL و co-NL ثابت شده‌است که formula_23. این مسئله در سال 1987 به‌طور مستقل توسط Neil Immerman و Róbert Szelepcsényi ثابت شد که حالت خاصی از قضیه Immerman-Szelepcsényi است که در آن ثابت می‌شود کلاس‌های غیرقطعی پیچیدگی فضا تحت عمل مکمل‌گیری بسته‌اند. این دو نفر در سال 1995 جایزه Gödel را دریافت کردند.


title: ان ال

text: در پیچیدگی مدار NL را می‌توان در سلسله مراتب NC قرار داد. در Papadimitriou 1994، قضیه 16.1 آمده است:


title: ان ال

text: همچنین به کمک قضیه ساویچ می‌توان NL را به پیچیدگی فضای کلاس مسائل قطعی مرتبط کرد. طبق قضیه ساویچ هر الگوریتمی را که به صورت غیرقطعی با حافظه معینی پیاده‌سازی شده باشد، می‌توان با حداکثر مربع آن حجم از حافظه به صورت قطعی پیاده‌سازی کرد. نتیجه این قضیه در مورد کلاس NL به صورت زیر می‌شود:


title: ان ال

text: طبق آن‌چه که در بالا گفته شد از قضیه Immerman-Szelepcsényi نتیجه می‌شود که NL تحت عملگر مکمل‌گیری بسته است. علاوه بر این NL تحت عملگرهای الحاق و ستاره کلین نیز بسته است.


title: مسئله تناظر پست

text: مسئلهٔ تناظر پست (به انگلیسی: Post correspondence problem) یک مسالهٔ تصمیم‌ناپذیر بر روی رشته‌ها است که در سال ۱۹۴۶ میلادی به‌وسیلهٔ امیل پست معرفی و اثبات شد. با نگاشت این مسئله بر روی مسائل تصمیم‌ناپذیر دیگر می‌توانیم تصمیم‌ناپذیری آن‌ها را نیز اثبات کنیم (مانند تصمیم‌ناپذیری ماشین‌های تورینگ).


title: مسئله تناظر پست

text: علاوه بر این که یکی از دلایل اهمیت این مسئله اثبات دیگر مسائل تصمیم‌ناپذیر به‌وسیلهٔ آن است، می‌توان به این موضوع نیز اشاره نمود که درک و اثبات این مسئله بسیار ساده‌تر از دیگر مسائل تصمیم‌ناپذیر، مانند مسالهٔ توقف در ماشین تورینگ است.


title: مسئله تناظر پست

text: یک "نمونه" از مسألهٔ تناظر پست را این‌گونه تعریف می‌کنیم:


title: مسئله تناظر پست

text: هر نمونه از این مسئله شامل دو لیست از رشته‌هایی است که بر روی الفبای formula_1 تعریف شده‌اند. فرض کنید این دو لیست formula_2 و formula_3 نام دارند که برای یک مقدار formula_4 این‌گونه تعریف می‌شوند:


مسئله تناظر پست


title: مسئله تناظر پست

text: برای هر formula_7 جفت formula_8 را یک جفت تناظر می‌گویند.


title: مسئله تناظر پست

text: "جواب" مسألهٔ تناظر پست را نیز این‌گونه تعریف می‌کنیم:


title: مسئله تناظر پست

text: برای یک نمونه از مسئله "جواب" وجود دارد اگر دنباله‌ای از اعداد صحیح مانند formula_9، formula_10، … و formula_11 وجود داشته باشد که شرط زیر را ارضاء کند:


title: مسئله تناظر پست

text: پس به‌طور کلی مسألهٔ تناظر پست این‌گونه تعریف می‌شود:


title: مسئله تناظر پست

text: «"آیا برای یک نمونه از مسألهٔ تناظر پست جوابی وجود دارد یا خیر؟"»


title: مسئله تناظر پست

text: فرض کنید formula_13 و دو لیست formula_2 و formula_3 را این‌گونه در نظر بگیرید:


title: مسئله تناظر پست

text: یک جواب برای این نمونه با formula_16، این‌گونه است: formula_17؛ زیرا در این صورت:


title: مسئله تناظر پست

text: که این دو شرظ formula_20 را ارضاء می‌کنند.


title: مسئله تناظر پست

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


title: ماشین پست-تورینگ

text: ماشین پُست-تورینگ (به انگلیسی: Post-Touring Machine) نام رده‌ای خاص از توصیف برنامه‌های محاسباتی است که بر اساس نسخه‌ای ساده از ماشین تورینگ تعریف می‌شود. این نسخهٔ ماشین تورینگ با الهام از مدل ریاضی و ماشین ارائه شده توسط امیل پُست (به انگلیسی: Emel Post) برای محاسبات ساخته و توصیف می‌شود.


title: ماشین پست-تورینگ

text: یک ماشین پُست-تورینگ همانند ماشین تورینگ از حافظه‌ای دودویی (به انگلیسی: Binary) و از دو طرف نامتناهی برای انجام محاسبات خود استفاده کرده و از یک الفبای دودویی برای ذخیرهٔ داده در این حافظه بهره می‌برد (هر خانهٔ حافظه می‌تواند علامت خورده یا بدون علامت باشد). زبان برنامه‌نویسی این ماشین از اعمالی ابتدایی مانند انتقال به خانهٔ چپ یا راست از یک خانهٔ حافظه و تغییر مقدار ذخیره شده در یک خانهٔ آن پشتیبانی می‌کند. در شروع عملیات پردازش تعدادی متناهی از خانه‌های حافظه علامت خورده و بقیه بدون علامت هستند. ماشین از یکی از خانه‌های حافظه که به عنوان «خانهٔ آغازین» مشخص شده عملیات خود را شروع کرده و در هر لحظه یکی از این پنج عمل را انجام می‌دهد: علیرغم شباهت توصیف‌های امیل پُست و آلن تورینگ (به انگلیسی: Alan Touring) از مدل‌های محاسباتی شان، این مدل‌ها مستقل از هم توسعه یافته و هر دو در سال ۱۹۳۶ منتشر شده‌اند. اصطلاحات «ماشین پُست-تورینگ» و «برنامهٔ پُست-تورینگ» توسط مارتین دیویس (به انگلیسی: Martin Davis) استاد دانشگاه نیویورک مورد استفاده قرار گرفته‌اند.


title: ماشین پست-تورینگ

text: امیل پُست در مقاله‌ای که در سال ۱۹۳۶ به نام "ضابطه‌بندی فرایند ترکیبیاتی متناهی - ۱" منتشر کرد مدلی بسیار ساده از محاسبات ارائه کرد و حدس زد این مدل "منطقا معدل مدل بازگشتی" است. درستی این فرض بعداً اثبات شد.


title: ماشین پست-تورینگ

text: مدل پُست با مدل ماشین تورینگ در اعمال پایه‌ای و قوانین اعمال شده بر آن‌ها تفاوت‌هایی دارد.


title: ماشین پست-تورینگ

text: مدل پُست از یک فضای یک بعدی ذخیره‌سازی دودویی (نوار ذخیره‌سازی) از دو طرف نامتناهی استفاده می‌کند و از الفبایی دودویی برای ذخیره‌سازی اطلاعات در هریک از خانه‌های این حافظه بهره می‌برد (هر خانهٔ حافظه می‌تواند علامت خورده یا بی علامت باشد).


title: ماشین پست-تورینگ

text: در شروع عملیات پردازش، تعداد متناهی از خانه‌های حافظه علامت دار و باقی خانه‌ها بدون علامت هستند.


title: ماشین پست-تورینگ

text: ماشین از یکی از خانه‌های حافظه که به عنوان «خانهٔ آغازین» مشخص شده عملیات خود را شروع کرده و در هر لحظه یکی از این پنج عمل را انجام می‌دهد:


title: ماشین پست-تورینگ

text: پُست در مقالهٔ خود اشاره می‌کند که مدل ارائه شده «در مرحلهٔ اولیهٔ توسعه» قرار دارد و گزینه‌هایی برای افزایش انعطاف‌پذیری مدل در مرحلهٔ نهایی‌اش پیشنهاد می‌کند:


title: ماشین پست-تورینگ

text: امیل پُست در سال ۱۹۴۷ مؤلفه‌های ۵ تایی تعریف ماشین تورینگ را به مؤلفه‌هایی ۴ تایی اتمی کاهش داد:


title: ماشین پست-تورینگ

text: مولفه‌های ۴ تایی توصیف پُست در واقع همان مؤلفه‌های ۵ تایی توصیف تورینگ هستند. به این صورت که دستورها استاندارد پُست شامل نوشتن (یا بازنویسی) یا حرکت به سمت چپ یا راست اند در حالی که دستورها استاندارد توصیف تورینگ همواره به صورت ترکیبی از نوشتن و حرکت به سمت چپ یا راست هستند.


title: ماشین پست-تورینگ

text: پاک کردن خانهٔ حافظه در مدل پُست مانند مدل تورینگ، معادل نوشتن علامت تهی (معمولاً '⏘') در آن خانه در نظر گرفته می‌شود.


title: ماشین پست-تورینگ

text: به این صورت مدل پُست تنها سه نوع ۴ تایی را مورد پذیرش قرار می‌دهد:


ماشین پست-تورینگ


title: ماشین پست-تورینگ

text: formula_4و formula_4حالات ماشین تورینگ و formula_6و formula_7حروف الفبای حافظهٔ ماشین هستند. formula_8بیانگر حرکت به سمت چپ و formula_9بیانگر حرکت به سمت راست روی حافظه است.


title: ماشین پست-تورینگ

text: از مدل وانگ (ارائه شده به ACM در سال ۱۹۵۴ و انتشار در سال ۱۹۵۷) معمولاً به عنوان مرجع ضابطه‌بندی برنامه‌های ماشین‌های تورینگ با نوار دودویی شناخته می‌شود.


title: ماشین پست-تورینگ

text: در این مدل بندی دستورها زیر به عنوان دستورها مرجع شناخته می‌شوند: در این مدل فرض شده دستورها ورودی ماشین به صورت متوالی و پشت سر هم اجرا می‌شوند.


title: ماشین پست-تورینگ

text: همچنین در اینجا "صفر" معادل خانهٔ بدون علامت و "یک" معادل خانهٔ علامت دار در نظر گرفته شده‌است.


title: ماشین پست-تورینگ

text: وانگ در مورد مدل پیشنهادی‌اش این نکات را یادآور می‌شود: بنا بر این یک ماشین تورینگ با نوار دودویی به سادگی به یک برنامهٔ وانگ قابل تبدیل است.


title: ماشین پست-تورینگ

text: مارتین دیویس یکی از دانشجویان کارشناسی امیل پُست بود. او به همراه استیون کول کلینی، دکترای خود را زیر نظر آلونزو چرچ به پایان رساند.


title: ماشین پست-تورینگ

text: او مدل محاسباتی را در دوران تدریس در دانشگاه نیویورک و در سال ۱۹۷۳ و ۱۹۷۴ مورد استفاده قرار داد که آن را ماشین پُست-تورینگ نامیده‌است. دستورها زبان پُست-تورینگ به صورت ترتیبی اجرا می‌شوند و این‌گونه هستند: دقت شود که در این مدل هم دستوری برای توقف روال اجرا وجود ندارد و برنامه زمانی متوقف می‌شود که تمامی دستورها آن اجرا شده باشند.


title: ماشین پست-تورینگ

text: در سال ۱۹۷۸ دیویس دومین مدل خود را در قالب مقالهٔ "محاسبات چیست" (به انگلیسی: "what is computation") به نام ماشین تورینگ-پُست ارائه کرد.


title: ماشین پست-تورینگ

text: در این مدل حرف '۱' معادل خانهٔ علامت دار مدل پُست و حرف '۰' معادل خانهٔ بدون علامت است.


title: ماشین پست-تورینگ

text: در مدل دوم دیویس ۷ نوع دستور وجود دارد: تقسیم دستورها پرش به دو نوع دستور، مجموعهٔ دستورها مدل تورینگ-پُست را بزرگتر کرده ولی استفاده از آن را به دلیل سادگی این دستورها آسان‌تر کرده‌است.


title: ماشین پست-تورینگ

text: از ویژگی‌های برجستهٔ این مدل می‌توان به این موارد اشاره کرد: دستورها پایه‌ای در این ماشین عبارتند از: در این مدل تفاوتی بین دستورها پرش شرطی و غیر شرطی وجود ندارد.


title: ماشین پست-تورینگ

text: مدل‌های معرفی شده همگی به لحاظ قدرت محاسباتی، معادل ماشین تورینگ استاندارد هستند.


title: ماشین پست-تورینگ

text: یک‌نویس (معادل معنایی انگلیسی: Busy Beaver) وظیفه دارد قبل از اتمام روال اجرایی‌اش بیشترین تعداد '۱' ممکن را در حافظه بنویسد. دستور print یا (P) حرف '۱' و دستور Erase یا 'E' حرف '۰' را در موقعیت فعلی بر روی نوار می‌نویسد. دستور Left یا (L) نوار را به سمت چپ و دستور Right یا (R) نوار را به سمت راست حرکت می‌دهد.


title: ماشین پست-تورینگ

text: جدول حالات ماشین تورینگ یک‌نویس ۲ حالته به این صورت است:


title: ماشین پست-تورینگ

text: دستورها در نسخهٔ معادل پُست-تورینگ ماشین دوحالتهٔ یک‌نویس (دقت شود که دستورها در یک خط و به ترتیب آمده‌اند. این نسخه یک تغییر عمده نسبت به نمایش ماشین تورینگ و معادل آن چیزی است که به آن «برنامهٔ کامپیوتر» می‌گوییم):


title: ماشین پست-تورینگ

text: منظور از J1 در جدول بالا پرش در صورتی است که در خانهٔ فعلی '۱' نوشته شده باشد.


title: ماشین پست-تورینگ

text: به صورت معادل می‌توانیم این جدول را به صورت یک رشته نمایش دهیم. به این صورت که عملوندهای دستورها را بعد از علامت ':' و بعد از نام دستور بنویسیم و دستورها متوالی را با ',' از هم جدا کنیم؛ بنابراین به عنوان مثال رشتهٔ معادل جدول بالا به این صورت است: J1:5, P, R, J:8, P, L, J:8, J1:12, P, L, J1:1, P, N, J:15, H نمودار حالت یک ماشین تورینگ دو حالتهٔ یک‌نویس با تبدیل هر حالت ماشین تورینگ به ۷ دستور معادل به حالت معادل ماشین پُست-تورینگ تبدیل می‌شود. حالت توقف هم باید به عنوان یک حالت جداگانه در نظر گرفته شود.


title: ماشین پست-تورینگ

text: در شکل زیر روال اجرای ماشین پُست-تورینگ یک‌نویس با تمام حالات میانی نمایش داده شده‌است:


title: ماشین پست-تورینگ

text: این مثال روال محاسبهٔ حاصل ضرب دو عدد طبیعی را در یک ماشین تک نوارهٔ پُست-تورینگ با الفبای دو تایی '۱' و '⏘' نشان می‌دهد.


title: ماشین پست-تورینگ

text: این ماشین پُست-تورینگ عملیات محاسبهٔ ضرب را به صورت بازگشتی توسط دو حلقه انجام می‌دهد.


title: ماشین پست-تورینگ

text: عملیات از ابتدای سمت چپ نوار و جایی که علائم مربوط به عدد a قرار دارند شروع می‌شود.


title: دختر دشت آرارات

text: دختر دشت آرارات () یک فیلم است محصول سال ۱۹۴۹، به کارگردانی هامو بیک-نازاریان


title: وابستگی داده

text: یکی از محدودیت‌های پایه‌ای در امکان اجرای همروند دستورها یک برنامه، مفهوم وابستگی داده (به انگلیسی: Data Dependency) است. برای مثال، یک دستور تا زمانی که داده‌های مورد نیازش آماده و در دسترس نباشند نمی‌تواند اجرا شود. در علوم رایانه، وابستگی داده به موقعیتی گفته می‌شود که یک دستور به داده‌های دستورها قبل و یا بعد از خود نیاز دارد.


title: وابستگی داده

text: به‌طور کلی، اگر اجرای هم‌زمان دو دستور ممکن نباشد و اجرای آن‌ها باید به صورت متوالی انجام شود، آن‌ها را وابسته می‌گوییم.


title: وابستگی داده

text: انواع وابستگی عبارت اند از: در نظریه کامپایلر، برای تشخیص وابستگی از فنون آنالیز وابستگی (به انگلیسی: ) استفاده می‌شود.


title: وابستگی داده

text: دو دستور formula_1 و formula_2 را در نظر می‌گیریم که دستور formula_2در جایی بعد از دستور formula_1 قرار دارد. formula_5 و formula_6 را به ترتیب مجموعه خانه‌هایی از حافظه که formula_7 از آن‌ها می‌خواند و مجموعه خانه‌هایی از حافظه که formula_7 در آن‌ها می‌نویسد، تعریف می‌کنیم. در این صورت با برقراری شرط زیر که به شرط Bernstein موسوم است، می‌گوییم formula_2 به formula_1 وابسته است: formula_11


title: وابستگی داده

text: به این ترتیب انواع وابستگی داده به صورت زیر تعریف می‌شود: در برخی منابع، نوع چهارمی هم به صورت زیر تعریف می‌شود:


title: وابستگی داده

text: "وابستگی جریان (به انگلیسی: Flow Dependency)" که به آن "وابستگی داده (به انگلیسی: Data Dependency)"، "وابستگی صحیح (به انگلیسی: True Dependency) و خواندن بعد از نوشتن (به انگلیسی: (RAW) Read-after-write)" نیز گفته می‌شود، هنگامی رخ می‌دهد که یک دستور به نتیجه دستوری قبل از خود وابسته باشد. مثال زیر را با فرض اینکه مقدار x و y از قبل محاسبه شده‌است در نظر بگیرید: a = x + y; b = 2 * a; در این مثال، دستور دوم به دستور اول وابستگی جریان دارد؛ چرا که از مقدار تولیدی در دستور اول استفاده می‌کند. به این ترتیب در این مثال نمی‌توان دستورها اول و دوم را به صورت هم زمان اجرا کرد.


title: وابستگی داده

text: "پاد وابستگی (به انگلیسی: Anti-dependency)" که به آن "نوشتن بعد از خواندن (به انگلیسی: Write-after-read (WAR))" نیز گفته می‌شود، هنگامی رخ می‌دهد که یک دستور به داده‌ای نیاز دارد که در دستور بعدی بازنویسی می‌شود. مثال زیر را با فرض اینکه مقدار x و y و z از قبل محاسبه شده‌است در نظر بگیرید: a = x + y; b = 2 * a; a = z + 1; در این مثال دستور دوم به دستور سوم پاد وابستگی دارد. توجه داریم که ترتیب این دستورها نمی‌تواند عوض شود؛ چرا که مقدار نهایی متغیر b را تغییر می‌دهد. همچنین اجرای هم‌زمان دستورها نیز به دلیل احتمال بروز خطا در مقدار نهایی امکان‌پذیر نیست.


title: وابستگی داده

text: پاد وابستگی مثالی از وابستگی نام است؛ به این معنا که وابستگی می‌تواند با تغییر نام برخی متغیرها برطرف شود. برای مثال کد زیر را برای رفع وابستگی مثال قبل در نظر بگیرید: a2 = x + y; b = 2 * a2; a = z + 1; به ابن ترتیب با تغییر نام متغیر a به متغیر جدید a2 در دستورها پیش از بازنویسی آن، پاد وابستگی میان دستورها دوم و سوم از بین رفته‌است و اکنون اجرای هم‌زمان آن‌ها امکان‌پذیر است.


title: وابستگی داده

text: "وابستگی خروجی (به انگلیسی: Output Dependency)" که به آن "نوشتن بعد از نوشتن (به انگلیسی: Write-after-write (WAW))" نیز گفته می‌شود، هنگامی رخ می‌دهد که یک متغیر در دو دستور نوشته شود. به بیان دیگر ترتیب اجرای دو دستور تعیین‌کننده مقدار نهایی یک متغیر است. مثال زیر را در نظر بگیرید: b = 7; a = 2 * b; b = 11; در این مثال دستور سوم به دستور اول وابستگی خروجی دارد. توجه داریم که تغییر ترتیب این دستورها موجب تغییر مقدار نهایی متغیرها خواهد شد.


title: وابستگی داده

text: وابستگی خروجی هم مثال دیگری از وابستگی نام است. برای مثال در کد زیر با تغییر نام متغیر b به متغیر b2 در دستورها قبل از بازنویسی آن، وابستگی خروجی مثال قبل برطرف شده‌است: b2 = 7; a = 2 * b2; b = 11; "وابستگی ورودی (به انگلیسی: Input Dependency)" که به آن "خواندن بعد از خواندن (به انگلیسی: Read-after-read (RAR))" نیز گفته می‌شود، هنگامی رخ می‌دهد که یک متغیر در دو دستور خوانده شود. مثال زیر را در نظر بگیرید: b = 7; a = 2 * b; c = b; در این مثال دستور سوم به دستور دوم وابستگی ورودی دارد.


title: وابستگی داده

text: توجه داریم که وابستگی ورودی در عمل مشکلی در اجرای هم‌زمان دستورها ایجاد نمی‌کند. همچنین تغییر ترتیب دستورها نیز قابل انجام است.


title: وابستگی داده

text: به وضوح، وابستگی ورودی نیز نوعی از وابستگی نام است.


title: وابستگی داده

text: وابستگی نام (به انگلیسی: Name Dependency) هنگامی رخ می‌دهد که دو دستور از محل یکسانی از حافظه استفاده می‌کنند اما هیچ جریان داده‌ای میان آن‌ها برقرار نیست. در نتیجه در بسیاری از موارد می‌توان با تغییر نام برخی از متغیرها این وابستگی را از بین برد.


title: وابستگی داده

text: از مهم‌ترین انواع وابستگی‌های نام، وابستگی خروجی و پاد وابستگی هستند.


title: وابستگی داده

text: اگر نتیجه دستور formula_1 مشخص‌کننده اجرا و یا عدم اجرای دستور formula_2 باشد، آنگاه دستور formula_2 به دستور formula_1 وابستگی کنترل دارد. مثال زیر را در نظر بگیرید: if (a == b) b = a + b; در این مثال نتیجه دستور اول مشخص می‌کند که دستورها سه و چهار اجرا می‌شوند یا خیر. برای بیان کردن و نشان دادن دقیق و راحت وابستگی کنترل، معمولاً از مفهوم "گراف جریان کنترل (به انگلیسی: Control flow Graph (CFG))" استفاده می‌شود.


title: وابستگی داده

text: گراف جریان کنترل گرافی جهت‌دار است که مسیرهای مختلفی که اجرای برنامه ممکن است بپیماید را نشان می‌دهد. رأس‌های این گراف را تکه‌های مجزای برنامه تشکیل می‌دهند. در صورتی که امکان انتقال مستقیم از تکه برنامه i به تکه برنامه j وجود داشته‌باشد، یالی از راس i به راس j خواهیم داشت.


title: مسئله ارتفاع ستاره

text: مسئلهٔ ارتفاع ستاره که توسط Eggan Lawrence C مطرح شده‌است، مسئله‌ای در تئوری زبان صوری است که سعی در پاسخ به این پرسش دارد که آیا می‌توان همهٔ زبان منظم را به کمک عبارات منظمی که ارتفاع ستارهٔ محدودی دارند بیان کرد؟ ارتفاع ستارهٔ یک عبارت منظم، بیشینهٔ عمق ستاره‌های تو در تویی است که در آن عبارت وجود دارد. به‌طور مشخص‌تر، این مسئله بیان می‌کند که آیا همیشه عمق تو در توی یک کافی است و امکان‌پذیر است که همهٔ زبان‌های منظم را با عبارات منظم به عمق یک نشان داد؟ اگر پاسخ این سؤال منفی است، آیا الگوریتمی وجود دارد که عمق مورد نیاز را مشخص کند؟


title: مسئله ارتفاع ستاره

text: مسئلهٔ اولیه، نخستین بار توسط Eggan پاسخ داده شد [۱]. او با ارائه مثالی نشان داد که پاسخ این پرسش منفی است. او برای هر عدد طبیعی مانند n، یک زبان منظم با ارتفاع ستارهٔ n ارائه داد. ساخت این عبارات به صورت بازگشتی است و به این ترتیب صورت می‌گیرد که عبارت formula_1، از کنار هم قرار دادن دو نسخهٔ formula_2 و تغییر نام نسخهٔ دوم با نام‌های جدید و پس از آن اضافه کردن یک نشانهٔ جدید در انتها و اضافه کردن پرانتز و ستاره در اطراف عبارت ساخته شده تا اینجا، صورت می‌گیرد. با به‌کارگیری تنظیم «چپ» تصویر در سمت چپ متن ظاهر می‌شود. Eggan ثابت کرد که هیچ عبارت منظمی با ارتفاع ستارهٔ کمتر از n وجود ندارد که معادل با formula_2 باشد [۱]. هرچند مثال ارائه شده توسط او از الفبای بزرگی استفاده می‌کند که برای زبانی با ارتفاع ستارهٔ n، اندازهٔ آن 2-۱ است. به همین دلیل، سؤال دیگری که مطرح کرد این بود که آیا مثال‌هایی روی الفبای دودویی وجود دارد که به این شکل باشند؟ این سؤال به سرعت توسط Dejean و Schützenberger پاسخ داده شد [۳]. آن‌ها مثالی بازگشتی از چنین عباراتی به ازای هر n ارائه دادند. formula_2 در هر گام به این صورت ساخته می‌شود که ابتدا به تعداد 2 نشانهٔ اول و سپس formula_2 و پس از آن به تعداد 2 نشانهٔ دوم و در انتها نیز formula_2 قرار می‌گیرد. در نهایت پرانتز دور این عبارت قرار گرفته و ستاره اضافه می‌شود.


title: مسئله ارتفاع ستاره

text: Dejean و Schützenberger و Salomaa نشان دادند که هیچ عبارت منظمی با ارتفاع ستارهٔ کمتری نمی‌تواند n را توصیف کند [۳٬۴].


title: مسئله ارتفاع ستاره

text: سؤال مطرح شدهٔ دوم، پاسخ به نسبت پیچیده‌تری نسبت به سؤال اول دارد و برای حدود دو دهه به عنوان یکی از مسائل معروف حل نشدهٔ حوزهٔ زبان‌های صوری شناخته می‌شد [2]. Hashiguchi در سال ۱۹۸۸ الگوریتمی برای تعیین ارتفاع ستارهٔ هر عبارت منظمی ارائه داد. اما این الگوریتم عملی نیست و به محاسباتی می‌انجامد که حتی برای مثال‌های کوچک نیز امکان‌پذیر نیست. الگوریتم بهینه‌تری توسط Kirsten در سال ۲۰۰۵ ارائه شد، اما حتی این الگوریتم هم فاصلهٔ زیادی با آنچه که قابل انجام است، دارد [۵]. این الگوریتم توسط Colcombet و Löding در سال ۲۰۰۸ کلی‌سازی و بهینه‌سازی شده‌است [۶] و در سال ۲۰۱۷ در ابزار Stamina پیاده‌سازی شده‌است [۷].


title: گسل‌های ایران

text: هر ناپیوستگی ثانویه زمین‌ساختی که بعد از ایجاد شکستگی در آن جابجایی رخ داده باشد به عنوان گسل شناخته می‌شود. بر این اساس هم گسله‌های کوچک در حد چند میلی‌متر و هم گسل‌هایی با طول چندین کیلومتر در این تعریف می‌گنجند.


title: گسل‌های ایران

text: گسل‌ها بر تحولات زمین‌ساختی و تکوین حوضه‌های ساختاری - رسوبی ایران اثر قابل توجهی داشته‌اند. در این میان، گسل‌های طولی عمده هم‌زمان با جنبش‌های کوه‌زایی کاتانگایی (پرکامبرین پسین) به مراتب بیشتر است. روند این گسل‌ها در بیشتر جاها با روندهای زمین‌ساختی مربوط به چین‌خوردگی کاتانگایی هم‌خوان است و در راستای شمالی - جنوبی قرار دارد، ولی روندهای شمال‌غربی - جنوب‌شرقی (روند زاگرس) نیز گزارش شده است.علاوه بر این دو روند، راستای دیگری نیز در امتداد شمال‌شرقی - جنوب‌غربی بر گسل‌های ایران حاکم است؛ به گونه‌ای که سه امتداد اصلی قابل تشخیص است:


title: گسل‌های ایران

text: این گسل‌ها مرز واحدهای ساختاری - رسوبی مختلف ایران را تشکیل می‌دهند و با فعالیت خود موجب تغییرات عمده در رخساره‌های سنگی، ضخامت رسوبات و تحولات زمین‌ساختی (ماگماتیسم، دگرگونی، شدت و الگوی چین‌خوردگی و...) می‌شوند و بنابراین شناخت آن‌ها از نظر زمان تشکیل، فعالیت، تأثیر آن‌ها بر زمین‌شناسی ایران و لرزه‌زمین‌ساخت بسیار مهم است.


title: گسل‌های ایران

text: تعداد گسل‌های شناخته شده ایران ۵۷۵ عدد است. تعداد گسل‌های خطرناک ایران ۱۲۰ عدد است. میزان شهرهای لرزان ایران یعنی شهرهای با ریسک خطر بالا ۷۸ درصد می‌باشد.


title: گسل‌های ایران

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


title: گسل‌های ایران

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


title: گسل‌های ایران

text: بیشتر گسل‌های زمین‌لرزه‌ای شناخته‌شده ایران طول بیش از ۴۰ کیلومتر دارند و همه آن‌ها با زمین‌لرزه‌های مخرب با بزرگی بیش از ۷ همراهند. در همه حالت‌ها جهت گسل‌های زمین‌لرزه‌ای ایران گویای جهت فشاری در راستای شمال شمال‌شرقی - جنوب جنوب‌غربی است که با جهت حرکت شمال‌شرقی صفحه عربستان هماهنگی دارد.«مناطق کم خطر زلزله در ایران». ۲۰۱۷. جستجوگر اخبار تی نیوز Tnews.Ir. Accessed December 31 2017. http://tnews.ir/news/b44c101773523.html.


title: کاهش‌پذیری تورینگ

text: عمل کاهش تورینگ در نظریهٔ زبان‌ها و ماشین‌ها، فرایندی است که در آن یک مسئله مانند formula_1 به مسئله‌ای مانند formula_2 تبدیل می‌شود به‌طوری‌که حل مسئلهٔ formula_2 منجر به حل مسئلهٔ formula_1 خواهد شد. این فرایند را کاهش مسئلهٔ formula_1 به مسئلهٔ formula_2 می‌نامند. فرایند کاهش را به صورت تئوری با تابعی تعریف می‌کنند که در ورودی مسئله‌ای در قالب مسئلهٔ formula_1 را می‌خواند و در خروجی مسئله‌ای در قالب مسئلهٔ formula_2 را تولید می‌کند. در این صورت مسائل ورودی و خروجی تابع معادل شده و اگر مسئله حاصل در قالب formula_2 حل شود، پاسخ آن پاسخی بر مسئلهٔ formula_1 نیز خواهد بود.


title: کاهش‌پذیری تورینگ

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


title: کاهش‌پذیری تورینگ

text: اولین بار وجود ارتباط میان حل مسائل با عنوان "حل وابسته" یا "محاسبهٔ نسبی" توسط آلن تورینگ در سال ۱۹۳۹ از دیدگاه ماشین‌های اوراکل مطرح شد. بعدتر آن را "کاهش وابسته" یا "کاهش نسبی" نیز نامیدند. پس از آن استیون کول کلینی در سال‌های ۱۹۴۳ و ۱۹۵۲ مفهومی مشابه را از دیدگاه توابع بازگشتی مطرح کرد. در سال ۱۹۴۴ امیل لئون پست عنوان «کاهش تورینگ» را برای تعریف این مفهوم به کار گرفت. کاهش تورینگ در زمان خطی نیز به نام استیون کوک، "کاهش کوک" نام گرفت.


title: کاهش‌پذیری تورینگ

text: ما در عمل، به‌طور معمول روزانه بارها و بارها از فرایند کاهش استفاده می‌کنیم. برای مثال فرض کنید می‌خواهید از شهری به شهر دیگری سفر کنید. برای این کار نیاز به تهیهٔ بلیت برای سفر دارید. برای تهیهٔ بلیت به تهیهٔ پول نیاز دارید و برای تهیهٔ پول باید کار کنید. در همین فرایند چند مرحله‌ای معمول، مسئلهٔ سفر به مسئلهٔ خرید بلیت، مسئلهٔ خرید بلیت به مسئلهٔ تهیهٔ پول و مسئلهٔ تهیهٔ پول به مسئلهٔ کار کردن کاهش یافت. بنابراین عمل کاهش به صورت کلی بخشی از ساده‌ترین اعمال زندگی روزمرهٔ ما می‌باشد.


title: کاهش‌پذیری تورینگ

text: کاربرد فنی‌تر عمل کاهش، در مسائل ریاضی می‌باشد. یکی از این کاربردها دسته‌بندی مسائل ریاضی است. این دسته‌بندی، مسائل مختلف را از نظر تشخیص‌پذیری، تصمیم‌پذیری، زمان و حافظه به هم مربوط می‌کند و تلاش‌های دنیای علم را در راستای حل مسائل سامان می‌بخشد.


title: کاهش‌پذیری تورینگ

text: از دیدگاه الگوریتمی، شرح عمل کاهش به این صورت است که الگوریتمی برای حل مسئلهٔ formula_1 تعریف می‌شود به‌طوری‌که در آن بخش اصلی حل مسئله بر دوش زیرروالی است که خود شامل الگوریتم حل مسئلهٔ formula_2 است. این پیاده‌سازی را می‌توان به کمک ماشین‌های اوراکل به انجام رساند. دو مجموعهٔ formula_1 و formula_2 متشکل از اعداد طبیعی را در نظر بگیرید. کاهش‌پذیری formula_1 به formula_2 به معنای وجود تابعی است که دامنهٔ آن مجموعهٔ formula_1 و تابع هدف آن مجموعهٔ formula_2 باشد و به صورت زیر نمایش داده می‌شود:


کاهش‌پذیری تورینگ


title: کاهش‌پذیری تورینگ

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


title: کاهش‌پذیری تورینگ

text: اگر formula_1 و formula_2 هر دو به یکدیگر کاهش‌پذیر باشند، formula_1 و formula_2 را هم‌ارز تورینگ می‌نامند. به این صورت تمامی مسائل به کلاس‌های هم‌ارزی تورینگ تقسیم خواهد شد که عضویت در هر یک از این کلاس‌ها درجه تورینگ مسائل را نشان می‌دهد.


title: کاهش‌پذیری تورینگ

text: در یک مجموعه از مسائل مانند مجموعهٔ formula_41، اگر هر مسئله مانند formula_42 در مجموعهٔ formula_41، به مسئلهٔ مشخصی مانند formula_44 کاهش‌پذیر باشد، formula_44 را تورینگ-سخت برای مجموعهٔ formula_41 می‌نامند. همچنین در صورتی که formula_44 خود عضوی از مجموعهٔ formula_41 باشد، آن را تورینگ-تمام برای مجموعهٔ formula_41 تعریف می‌کنند.


title: کاهش‌پذیری تورینگ

text: عمل کاهش را در اثبات تصمیم‌ناپذیری یکی از مسائل معروف ریاضی شرح می‌دهیم. مجموعهٔ formula_50 را مجموعه جفت ماشین تورینگ‌هایی تعریف می‌کنیم که تولیدکننده یک زبان مساوی هستند. مجموعهٔ formula_51 را نیز مجموعه ماشین تورینگ‌هایی تعریف می‌کنیم که زبانشان تهی است. می‌دانیم مسئلهٔ formula_51 تصمیم‌ناپذیر است. با کاهش مسئلهٔ formula_51 به مسئلهٔ formula_50 می‌توان نتیجه گرفت که formula_50 نیز تصمیم‌ناپذیر است. زیرا در صورتی که تصمیم‌پذیر باشد، با توجه به این که formula_51 به این مسئله کاهش یافته، formula_51 نیز تصمیم‌پذیر خواهد شد که یک تناقض را نتیجه می‌دهد. برای کاهش مسئلهٔ formula_51 به مسئلهٔ formula_50، خاصیت تهی بودن یک زبان را می‌توان با خاصیت تساوی آن زبان با یک زبان تهی معادل کرد. بنابراین در صورتی که ورودی مسئلهٔ formula_51 را با ماشین یک زبان تهی به مسئلهٔ formula_50 بدهیم، پاسخ آن برای formula_51 نیز پاسخی صحیح است. بنابراین کاهشی از مسئلهٔ formula_51 به formula_50 وجود دارد و هر مسئله از formula_51 را می‌توان با formula_50 حل کرد.


title: کاهش‌پذیری تورینگ

text: به صورت مشابه تصمیم‌ناپذیری مسائلی همچون مجموعهٔ ماشین‌های زبان‌های منظم، ماشین‌های با نوار محدود و زبان تهی، مسئلهٔ معروف formula_67 و دیگر مسائل ثابت شده‌است.


title: نظریه مک‌ناتون

text: در نظریه اتوماتا نظریه مک‌ناتون اشاره دارد به قضیه‌ای که بیان می‌دارد مجموعه‌ای از زبان‌های ω-منظم برابر خواهد بود با مجموعه‌ای که توسط ماشین مولر قطعی تشخیص داده شود. برای اثبات این قضیه الگوریتمی ارائه می‌شود که در آن برای هر زبان ω-منظم یک ماشین مولر قطعی ساخته می‌شود و بالعکس. این قضیه نتایج مهم و متعددی دارد. از آنجایی که ماشین بوچی و زبان‌های ω-منظم هر دو بیانی از یکدیگر هستند، این قضیه این نتیجه را می‌رساند که ماشین بوچی و ماشین قطعی مولر به‌طور مساوی بیانگر یکدیگر هستند.


title: نظریه مک‌ناتون

text: در مقاله اصلی مک‌ناتون، قضیه بدین صورت بیان شده‌است که: " یک ω-رویداد منظم است اگر و فقط اگر حالت متناهی باشد."


title: نظریه مک‌ناتون

text: امروزه از عبارت ω-زبان‌ها به جای ω-رویدادها استفاده می‌شود. همچنین طبق تعریف مک‌ناتون یک ω-رویداد، یک رویداد حالت متناهی است اگر یک ماشین مولر قطعی وجود داشته باشد که آن را تشخیص دهد.


title: نظریه مک‌ناتون

text: اثبات یک طرف این قضیه بدین صورت است که نشان داده می‌شود هر ماشین مولر داده شده یک زبان ω-منظم را تشخیص می‌دهد. فرض کنید ("A" = (Q,Σ,δ,q,F یک ماشین قطعی مولر باشد. اتحاد تعداد زیاد و معینی از زبان‌های ω-منظم، یک زبان ω-منظم را تولید می‌کند، لذا بدون کم شدن از کلیت مساله می‌توان فرض نمود که شرط قبولی مولر F دقیقاً شامل یک مجموعه از حالت‌های {q...,q} می‌شود. فرض می‌شود که α یک زبان منظم باشد که عناصرش "A" را از q تا q دربر بگیرد. برای هر i از 1 تا β ،n یک زبان منظمی باشد که عناصرش "A" را از q تا q را بدون عبور از هر وضعیتی خارج از {q...,q} در بر بگیرند. ادعا می‌شود که α(β) یک زبان ω-منظم است که توسط ماشین مولر A تشخیص داده می‌شود.


title: نظریه مک‌ناتون

text: سمت دیگر قضیه را بدین طریق می‌توان اثبات کرد که به ازای هر زبان ω-منظم داده شده یک ماشین مولر وجود دارد که آن را تشخیص بدهد. اتحاد تعداد متناهی و زیادی از ماشین‌های قطعی مولر به سادگی قابل ساخت است، لذا بدون کم شدن از کلیت مساله، فرض می‌شود که زبان ω-منظم داده شده به شکل αβ است. همچنین فرض شود که ω-کلمه w=a,a... ∈ αβ. "w"(i,j یک بخش معین شامل a از w در نظر گرفته می‌شود. برای ساختن ماشین مولر مرتبط با αβ، دو مفهموم در رابطه با w معرفی می‌شود. خدمت  زمان j در خدمت زمان i است اگر  j > i و "*w"(0,i) ∈ αβ و "*w"(i,j) ∈ β. هم‌ارزی  با "ارزیابی" در زمان i، k "هم‌ارز" است با j اگر *i,j≤k "w"(0,j) ∈ αβ*، "w"(0,i) ∈ αβ، و برای هر کلمه x در "*w"(i,k)x ∈ β*، Σ، اگر و فقط اگر "*w"(j,k)x ∈ β یا به عبارتی "(E(i,j,k". به سادگی می‌توان توجه کرد که اگر "(E(i,j,k" آنگاه برای همه k


title: گسترش در خط

text: در علوم کامپیوتر گسترش در خط به معنی جایگزینی دستور فراخوانی یک تابع با متن خود آن تابع است. این کار به صورت دستی توسط برنامه‌نویس (به‌طور مثال به وسیله کلیدواژه‌های تعریف‌شده زبان) یا به صورت خودکار (توسط کامپایلر) انجام می‌شود.


title: گسترش در خط

text: این عمل بسیار شبیه به گسترش ماکرو است، ولی تفاوت عمدهای که گسترش در خط دارد این است که در زمان کامپایل انجام می‌شود ولی جایگزینی ماکروها در زمان پیش از کامپایل صورت می‌گیرد و متن برنامه ورودی تحلیل‌گر کامپایلر تغییر پیدا می‌کند. مزیت گسترش در خط نسبت به ماکرو این است که ایرادهای ماکرو را از قبیل احتمال رعایت نشدن اولویت عملیات ریاضی ندارد.


title: گسترش در خط

text: گسترش در خط تأثیر زیادی بر عملکرد کامپایلر دارد و یکی از بهینه‌سازی‌های ساده در کامپایلرها است که می‌تواند منجر به افزایش سرعت شود. البته گسترش در خط بیش از حد به دلیل اشغال کردن قسمت عمده‌ای حافظه نهان دستورها ممکن است باعث کندتر شدن برنامه گردد. بررسی عملکرد گسترش در خط در مقاله‌های دهه ۸۰ تا ۹۰ میلادی در سال ۱۹۹۹ توسط Jones و Marlow انجام شده‌است


title: گسترش در خط

text: همان‌طور که گفته شد گسترش در خط از گسترش ماکرو سریع‌تر است و دلیل آن این است که در گسترش در خط سر بار فراخوانی تابع (که شامل ذخیره‌سازی مقادیر ثبّات‌ها و پرش است) دیگر وجود ندارد و خطوط مربوط به متن تابع مستقیماً اجرا می‌شود. از جهت دیگر اما گسترش در خط می‌تواند باعث هدر رفتن حافظه شود زیرا به ازای هر محل از برنامه که تابع فراخوانی شده باشد، یک رونوشت از متن تابع در آن‌جا اضافه می‌گردد. در نتیجه استفاده از گسترش در خط معمولاً در حالتی که متن تابع کوتاه است می‌تواند کارساز باشد.


title: گسترش در خط

text: به‌طور مثال در زبان ++C، توابعی که عضو کلاس‌ها هستند در صورتی که در داخل تعریف کلاس تعریف شوند به‌طور پیش‌فرض در خط سازی می‌شوند. در غیر این صورت برنامه‌نویس می‌بایستی صراحتاً از کلیدواژه inline استفاده کند. همچنین دلیل اشاره شده بالا، کامپایلر این زبان، توابع بزرگی که برنامه‌نویس صراحتاً درخواست خطی‌سازی آن‌ها را کرده‌است، خطی‌سازی نمی‌کند.


title: گسترش در خط

text: همچنین در برنامه‌نویسی تابعی، گسترش در خط معمولاً پس از تبدیل کاهش بتا صورت می‌گیرد.


title: گسترش در خط

text: گسترش در خط سر بار فراخوانی تابع را کاهش می‌دهد ولی دلیل اصلی انجام آن زمینه‌سازی برای بهینه‌سازی‌های دیگر است زیرا گسترش در خط اندازه برنامه را زیاد می‌کند و بهینه‌سازی‌های بهتری بر روی برنامه‌های با اندازه بزرگتر قابل انجام است پیش‌بینی اثر نهایی گسترش در خط بر روی عملکرد برنامه پیچیده‌است و به دلیل اثر آن بر روی حافظه نهان دستورها، بسته به برنامه و اندازه حافظه نهان متفاوت است


title: گسترش در خط

text: همچنین میزان این تأثیر بین زبان‌های مختلف متفاوت است. به‌طور مثال در زبان‌های سطح پایین مانند C و Fortran، به اندازه ۱۰–۲۰٪ افزایش سرعت مشاهده می‌شود، در حالی که در زبان‌های سطح بالاتر و انتزاعی‌تر گسترش در خط می‌تواند چندین مرحله از اجرای برنامه را حذف کند. مثال این‌گونه زبان‌ها، زبان سلف (زبان_برنامه‌نویسی) است که ضریب بهبودی بین ۴ تا ۵۵ داشته‌است


title: گسترش در خط

text: کامپایلرها از روش‌های مختلفی برای تشخیص اینکه چه تابعی را گسترش در خط دهند، استفاده می‌کنند. این روش‌ها عبارتند از:


title: گسترش در خط

text: گسترش در خط در بسیاری از زبان‌ها به صورت خودکار توسط کامپایلر صورت می‌گیرد و کامپایلر بررسی می‌کند که آیا این عمل برای سرعت برنامه مفید است یا خیر. همچنین کلیدواژه‌هایی مانند inline نیز در برخی از زبان‌ها به عنوان پیشنهادی از طرف برنامه‌نویس برای در خطی سازی تابع وجود دارد. هرچند که همان‌طور که گفته شد این کلیدواژه‌ها کامپایلر را مجبور به انجام این عمل نمی‌کند.


title: گسترش در خط

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


title: گسترش در خط

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


title: گسترش در خط

text: پیوند دهندهها نیز می‌توانند گسترش در خط انجام دهند. پیونددهنده‌ها توابعی را که از کتابخانه‌های دیگر استفاده شده و در متن برنامه اولیه موجود نبوده را گسترش در خط می‌دهند.


title: گسترش در خط

text: در مثال زیر یک گسترش در خط به صورت دستی انجام شده‌است: int pred(int x) {


title: گسترش در خط

text: "قبل از در خط سازی:"


title: گسترش در خط

text: "بعد از آن:"


title: گسترش در خط

text: int f(int y) {


title: گسترش در خط

text: پیش از C99 در زبان سی در خط سازی به کمک ماکروها انجام می‌شد. مزایای گسترش در خط نسبت به ماکروها عبارتند از:


title: گسترش در خط

text: بی‌یارنه استراس‌تروپ خالق زبان سی پلاس‌پلاس نیز استفاده از توابع در خط را به جای ماکروها توصیه می‌کند.


title: درخت رونده اتوماتا

text: یک درخت رونده اتوماتا یک نوع اتوماتا متناهی است که به جای رشته‌ها درخت‌ها را تحلیل می‌کند. این مفهوم توسط Aho و Ullman پیشنهاد شده‌است.


title: درخت رونده اتوماتا

text: این درخت بسیار شبیه درخت گرامر درخت منظم و ماشین درختی به عبارتی می‌توان گفت این درخت نمایشی متفاوت از دو درخت یاد شده‌است.


title: درخت رونده اتوماتا

text: تمام درخت‌های به این شکل دودویی هستند و دارای برچسب‌هایی با الفبای ثابت هستند در واقعیت این درخت‌ها دارای تعدادی حالت هستند که با آمدن حروف جدید مانند اتومات‌های واقعی از حالتی به حالت دیگر حرکت می‌کند و در نهایت اگر در حالت تأیید به کار خود پایان داد که آن درخت تأیید می‌شود و اگر در حالت رد یا حلقهٔ بی‌نهایت به کار خود پایان داد آن درخت رد می‌شود.


title: درخت رونده اتوماتا

text: اگر بخواهیم به صورت ریاضی تر آن را بگوییم هر درخت غیر قطعی رونده اتوماتا یک شش‌تایی A = (Q, Σ, I, F, R, δ) است که Σ الفبایی ثابت بوده، Q مجموعهٔ حالت‌ها ،I حالت‌های شروع، F حالت‌های تأیید و R حالت‌های رد است. همان‌طور که در تمامی اتومات‌ها رابطه‌هایی وجود دارد که با دیدن یک حرف از حالی به حالت دیگر می‌رود. δ ⊆ (Q × { root, left, right, leaf } × Σ × { up, left, right } × Q) Q اول به معنای حالت فعلی است که در حالت فعلی یکی از چهار حالت مشخص شده را داریم. منظور از Σ حرف دیده شده‌است و مورد بعدی به معنای حرکتی است که می‌کنیم که یکی از بالا، راست و چب است و Q آخر نیز به معنای حالتی است که در آن می‌رویم. پس رابطه‌های به صورت ۵ تایی‌هایی درین اتوماتا نمایان می‌شوند.


title: درخت رونده اتوماتا

text: یک مثال ساده از این درخت برای اجرا کردن الگوریتم جستجوی عمق اول بر روی درخت ورودی است. طبعاً برای هر مثال باید پارامترهای تعریف را مشخص کنیم. این اتومات‌های ۳ حالت دارد، formula_1. در ابتدا از ریشه که حالت ۰ است شروع می‌کنیم. حال با آمدن هر راس جدید به حالت چپ وارد می‌شویم و در صورتی که در برگ درخت باشیم به بالا می‌رویم که متناظر با همان حرکت بالا بود که در تعریف از آن یاد کرده بودیم. همان‌طور که گفتیم درین درخت می‌توان مشخص کرد که آیا زیر درختی پردازش شده‌است یا نه در این‌جا هم هر جا که زیر درخت سمت چپ پردازش شده باشد باید به حالت سمت راست برویم.formula_2


title: درخت رونده اتوماتا

text: بر خلاف ماشین درختی، درخت رونده اتوماتا به سختی قابل تجزیه و تحلیل است و حتی خواص سادهٔ آن نیز به سختی اثبات می‌شود و بعضاً اثبات‌های بسیار پیچیده و غیر بدیهی دارند.


title: درخت رونده اتوماتا

text: درین به برخی از خواص آن که اثبات شده‌است اشاره می‌کنیم


title: منطق جدایی

text: منطق جدایی تعمیمی از منطق هور (Hoare logic) است که هدف اصلی ابداع آن، بررسی و وارسی ریاضی برنامه‌هایی است که داده‌ها را در حافظه تغییر می‌دهند و خانه‌های مختلف از حافظه هستند که در معرض تحول هستند. این منطق توسط جان سی رینولدز, Peter O'Hearn, Samin Ishtiaq و Hongseok Yang معرفی شده‌است.


title: منطق جدایی

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


title: منطق جدایی

text: منظور ما در این‌جا از حالت، وضعیت مقادیر موجود در حافظهٔ تصادفی و همچنین حافظهٔ پشته است. اعلان formula_2 در منطق جدایی، تعدادی حالت را مشخص می‌کند که در آن‌ها formula_2 درست است. با تعریف استقرایی ساختار لغوی منطق جدایی، عبارت formula_4 حالاتی را مشخص می‌کند که formula_2 در یک قسمت از ساختار حافظهٔ تصادفی/پشته و formula_6 در قسمتی کاملاً مجزا از آن درست باشد. پس تعریف استقرایی زبان منطق به این صورت است:


title: منطق جدایی

text: حال می‌توان این عملگرها را در مفاهیم منطق مرتبهٔ اول به کار برد و با آن عباراتی در مورد تأثیر یک برنامه بر حافظه گفت یا در بیان مشخصات حافظه استفاده کرد.


title: منطق جدایی

text: در این منطق هم مانند دیگر منطق‌ها می‌توان اصول استنتاج تعریف و طبق آن‌ها استدلال کرد. برای مثال طبق تعریف عملگر formula_10، داریم: formula_12


title: منطق جدایی

text: تمامی قواعد استنتاج در منطق هور، در منطق جدایی هم معتبر هستند؛ و همچنین در این منطق، قاعدهٔ قاب هست که برای سه‌تایی‌های هور تعریف می‌شود. یک سه‌تایی هور، به شکل کلی formula_13 است که یعنی اگر، حافظه قبل از اجرای برنامهٔ formula_14، در حالت formula_2 باشد، پس از اجرای آن به حالت formula_6 می‌رود. حال طبق قاعدهٔ قاب داریم:


منطق جدایی


title: منطق جدایی

text: به‌وسیلهٔ این قاعده، می‌توان استدلالات محلی در مورد حافظه را گسترش داد و در مورد بخش بزرگ‌تری از حافظه صحبت کرد. استدلال محلی برای یک برنامهٔ formula_14، یعنی استدلال در مورد تمامی متغیرها و خانه‌های حافظه که توسط formula_14 تغییر می‌یابند. این‌ها را O'Hearn، ردپای formula_14 می‌نامد. او بیان می‌دارد که: «برای فهم رفتار یک برنامه، باید در مورد خانه‌هایی اطلاع کسب کنید که توسط آن برنامه تغییر می‌یابند. ارزش دیگر خانه‌ها به صورت خودبه‌خود ثابت باقی می‌ماند.»


title: منطق جدایی

text: منطق جدایی به دلیل کاربرد در درستی‌یابی برنامه‌های کامپیوتری، عملکرد وسیعی در ابزارهای مختلف وارسی مدل‌ها و همچنین کاربردهای صنعتی دارد. به‌نحوی‌که O'Hearn که از مبدعین این منطق بوده، از سال ۲۰۱۳ در شرکت فیسبوک مشغول به کار است. به صورت کلی، ابزارهایی که از منطق جدایی استفاده می‌کنند در دسته‌های مختلف هستند:


title: چرخان‌تاژک‌داران

text: چرخان‌تاژک‌داران یا داینوفلاژله‌ها نام یک شاخه از حبابچه‌داران است که تک‌یاخته و اکثراً دریازی هستند.


title: چرخان‌تاژک‌داران

text: این جانوران پلانکتونی‌اند و در آن‌ها کپسول مشخصی از جنس سلولز وجود دارد. کپسول دو قسمتی است و شیاری در آن وجود دارد که در برگیرنده دو تاژک است، یکی از تاژک‌ها رو به عقب امتداد دارد و دیگری تقریباً افقی است. معمولاً دارای لکه چشمی و تعدادی زیاد کلروپلاست قهوه ای، زرد یا مایل به سبز هستند. هسته درشت و یکی است. حضور تعدادی کیسه بزرگ که توسط کانال‌ها یا مجاری به بیرون راه دارند، از مشخصات این جانوران است. این حجم‌های غیر انقباضی که پوسول (pusule) نام گرفته‌اند، گرچه به سیستم کریچهای شباهت ندارند ولی احتمالاً درگرفتن آب و در عمل هیدرواستاتیک نقش ایفا می‌کنند.


title: چرخان‌تاژک‌داران

text: دسته‌ای از چرخان‌تاژک‌داران فاقد رنگیزه هستند و به‌طریق جانوران تغذیه می‌کنند. از نظر ریخت‌شناسی شبه آمیب‌ها هستند.


title: چرخان‌تاژک‌داران

text: تولید مثل در چرخان‌تاژک‌داران تا حدودی شبیه تقسیم دوتایی طولی تاژکداران است و در امتداد یک صفحه مورب صورت می‌گیرد. این نوع تقسیم حتی در کیست نیز اتفاق می‌افتد. حتی در حالت کیستی تقسیم می‌تواند از نوع چندتایی باشد. افراد حاصل از تقسیمات متوالی دوتایی گاهی به‌طور موقت به هم چسبیده می‌مانند (مانند زنجیر). شواهد کافی از ممزوج شدن گامت‌ها یا یاخته‌های جنسی وجود ندارد.


title: چرخان‌تاژک‌داران

text: یک نمونه معروف از تاژک‌داران چرخان، سراتیوم (Ceratium) است که نمونه‌ای زره دار و دارای خار و دو تاژک است و به روش گیاهان تغذیه می‌کند. زره یا تک(Theca)، ضخیم و غیرقابل انعطاف است. خارها از امتداد بخش‌هایی از صفحات سازنده زره ایجاد شده‌اند و راست یا خمیده‌اند. خار جلویی، خار راسی (Apical spine) و خار یا خارهای عقبی (تا ۴ خار عقبی می‌تواند وجود داشته باشد)، خار یا خارهای مقابل راسی (Anapical spine) نامیده می‌شوند. طبق معمول بین صفحات سازنده زره دو شیار وجود دارد. شیار در مو قعیت استوایی یا افقی به نام حلقه یا انولوس (Annulus) نیز نامیده می‌شود که معمولاً با یک صفحه به نام سینگولوم (Cingulum) پوشیده شده‌است. از میان منافذ زره برجستگی‌ها یا پاپیلاهای سیتوپلاسمی متعددی خارج و به شبکه‌ای از پاهای کاذب منتهی می‌شوند. این پاها باعث صید موجودات ریز می‌شوند، تغذیه گاهی از این نوع است. انواع آب شیرین دارای کلروپلاست‌های سبز و انواع دریایی زرد یا قهوه‌ای هستند.


title: چرخان‌تاژک‌داران

text: نمونه دیگر نوکتیلوکا (Noctiluca)است که همچون یک کره بزرگ (ژلاتینی) به قطر 1mmیا بیشتر است. شناور بر سطح دریا و معمولاً نزدیک ساحل یافت می‌شود. بی‌رنگ و بیگانه‌خوار است. یک تاژک کوتاه ضخیم و یک تاژک ظریف دارد. این موجود دارای خاصیت زیست‌تابی و مسئول فسفرسانس آب‌های ساحلی دریاها است.


title: سرعت نور (اتوماتای سلولی)

text: در بازی زندگی کانوی (و اتوماتای سلولی مربوط) سرعت نور یک نرخ انتشار در سراسر شبکه از دقیقاً یک گام (به صورت افقی عمودی و یا مورب) در هر نسل است. در یک نسل یک سلول تنها می‌تواند همسایه‌های نزدیکش را تحت تأثیر قرار دهد و بنابراین سرعت نور (در قیاس با سرعت نور در فیزیک) حداکثر نرخی که با آن اطلاعات می‌توانند منتشر شوند. از این رو یک حد بالا برای سرعتی که با آن هر الگوی حرکت می‌کند داریم.


title: سرعت نور (اتوماتای سلولی)

text: همان‌طور که در فیزیک سرعت نور با حرف . این در عوض مرجعی است برای توصیف میانگین سرعت انتشار هر سفینه فضایی. برای مثال یک گلایدر گفته می‌شود که سرعتی برابر توسط یک سلول ترجمه شود. به طور مشابه «سفینه فضایی سبک» گفته شده است که سرعتی برابر هر حالت داده شده ۴ نسل طول می‌کشد تا توسط دو سلول ترجمه شود.


title: سرعت نور (اتوماتای سلولی)

text: در حالی که  یک کران بالای مطلق برای سرعت انتشار است حداکثر سرعت یک سفینه فضایی در بازی زندگی کانوی در واقع . دلیل این امر آن است که ساخت یک سفینه فضایی که بتواند در هر نسل حرکت کند غیرممکن است. (هر چند این موضوع در حالت کلی برای اتوماتای سلولی درست نیست؛ به عنوان مثال بسیاری از سفینه‌های فضایی با سرعت نور در دانه‌ها وجود دارند) با این حال این برای اشیاء ممکن است که با سرعت نور سفر کنند اگر آن‌ها به جای فضای خالی از مدیوم حرکت کنند. چنین رسانه ای شامل مسیرهای کهیر و خطوط سلول‌های زنده و مرده است. اگر با سرعت نور د کهکشان حرکت کنیم در30ثانیه به ماه میرسیم و 8/30دقیقه به خورشید میرسیم و2000سال طول میکشد از کهکشان راهشیری خارج شدیم و چند میلیون سال طول میکشد تا به نزدیک ترین کهکشان راهشیری برسیم!


title: سرعت نور (اتوماتای سلولی)

text: الگوهای خاص می‌توانند به نظر برسند که با سرعت بیشتر از یک سلول در هر نسل حرکت می‌کنند اما مانند پدیده‌های سریع تر از نور در فیزیک این امر گمراه کننده است.


title: سرعت نور (اتوماتای سلولی)

text: به عنوان مثال "Star Gate", ترتیبی از سه گلایدر همگرا که متقابلاً در برخورد نابود می‌شوند. اگر یک سفینه فضایی سبک (LWSS) با گلایدرهای همگرا برخورد کند به نظر می‌رسد که در ۶ نسل ۱۱ حرکت رو به جلو انجام داده و در نتیجه سفری سریع تر از نور داشته است. این توهم به این خاطر اتفاق می‌افتد که واکنش حاصل از نابودی گلایدر با ایجاد و به زودی تخریب یکی دیگر از LWSSها همراه است. هنگامی که LWSS ورودی با گلایدرهای همگرا برخورد می‌کند به جای دیگر منتقل نمی‌شود اما به جای آن واکنش را به طوری که LWSS به تازگی ایجاد شده می‌تواند زنده بماند تغییر می‌دهد. تنها سیگنالی که منتقل می‌شود این است که تعیین کند آیا LWSS خروجی باید زنده بماند یا نه. این نیازی به رسیدن به مقصد خود ندارد تا بعد از اینکه LWSS منتقل شده است و بنابراین هیچ اطلاعاتی نیاز به سفر سریع تر از نور ندارد.


title: فرم باکوس نائور توسعه یافته

text: فرم باکوس نائور توسعه یافته یا EBNF در علوم رایانه ای، یک خانواده از نمادهای متاسینتاکس است که هر کدام از آن‌ها می‌توانند برای بیان یک دستور زبان مستقل از متن استفاده شود. EBNF برای توصیف زبان صوری استفاده می‌شود که می‌تواند یک زبان برنامه‌نویسی کامپیوتری هم باشد. این‌ها شامل فرمت‌های بنتاکس (BNF) است. ابتدا EBNF توسط نیکلاوس ویرت توسعه داده شد و برخی از مفاهیم را به صورت نحوی به کار برد. با این حال بسیاری از انواع EBNF در استانداردسازی یک استاندارد) (ISO/IEC 14977 را برای EBNF مورد تصویب قرار داده‌است. این مقاله از EBNF که توسط استاندارد مشخص شده‌است را برای تمام مثال‌های EBNFها استفاده می‌کند. دیگر انواع EBNF از قوانین نحوی متفاوت استفاده می‌کنند).


title: فرم باکوس نائور توسعه یافته

text: EBNF یک کد است که دستور زبان رسمی را بیان می‌کند. یک EBNF شامل علائم ترمینال و قوانین تولید نامحدود است که محدودیت‌هایی را در مورد این که چگونه نمادهای ترمینال را می‌توان به یک ترتیب قانونی ترکیب کرد ارائه می‌کند. مثال‌هایی از نمادهای ترمینال عبارت اند از کاراکترهای الفبایی، نشانه‌های نقطه گذاری شده و نشانه‌های سجاوندی. EBNF قوانین تولید را تعریف می‌کند که در آن دنباله‌های نمادها به ترتیب به صورت غیرانتصابی اختصاص داده می‌شوند.


title: فرم باکوس نائور توسعه یافته

text: digit excluding zero = "1" | "2" | "3" | "4" | "5" | "6" | "7" | "8" | "9" ; digit = "0" | digit excluding zero ;


title: فرم باکوس نائور توسعه یافته

text: این قوانین تولید به صورت عددی غیرمنتظره ای است که در سمت چپ قرار داشته و آن‌ها را تعریف می‌کند. نمودار عمودی یک جایگزین را نشان می‌دهد و نمادهای ترمینال علامت نقل قول همراه یا یک نقطه متوقف می‌شود. از این رو یک رقم بوده و می‌تواند ۱ یا ۲ یا ۳ … ۹ باشد. یک قانون تولیدی همچنین می‌تواند دنباله ای از پایانه‌ها یا غیر ترمینال‌ها می‌باشد که هر کدام با یک کاما جدا شده‌اند.


title: فرم باکوس نائور توسعه یافته

text: twelve = "1", "2" ; two hundred one = "2", "0", "1" ; three hundred twelve = "3", twelve ; twelve thousand two hundred one = twelve, two hundred one ; ساختارهایی که ممکن است حذف یا تکرار شوند را می‌توان از طریق شکل‌های مجاور نشان داد. natural number = digit excluding zero, { digit } ; در این مورد، رشته‌های 1, 2, … , 10, 12345, … عبارت‌های صحیح هستند. برای نشان دادن این مورد، همه موارد را در داخل پارانتزهای مجاور قرار می‌گیرند. ممکن است اغلب به صورت خودسرانه تکرار شوند. از جمله این که در همه موارد وجود ندارد یک گزینه را می‌توان از طریق براکت مربعی نشان داد و این بدان معنی است که هر چیزی که درون مربع قرار دارد ممکن است فقط یک بار و نه در همه جا باشد. integer = "0" | ["-"], natural number ;


title: فرم باکوس نائور توسعه یافته

text: بنابراین یک عدد صحیح صفر یا یک عدد طبیعی بیش از یک عدد اختیاری باشد. EBNF همچنین در میان موارد دیگر به نحوی برای توصیف تکرار ما اقدام می‌کند تا برخی از بخش‌های تولید را حذف کرده و نظرات را در دستور زیاد EBNF قرار دهد.


title: فرم باکوس نائور توسعه یافته

text: در زیر استاندار ISO/IEC 14977 پیشنهاد شده توسط آر. اس اسکون است در صفحه ۷ و در جدول ۱ نشان داده شده‌است. حتی EBNF را می‌توان با استفاده از خود EBNF توصیف نمود. دستورالعمل زیر را در نظر بگیرید :


title: فرم باکوس نائور توسعه یافته

text: letter = "A" | "B" | "C" | "D" | "E" | "F" | "G" digit = "0" | "1" | "2" | "3" | "4" | "5" | "6" | "7" | "8" | "9" ; symbol = "[" | "]" | "{" | "}" | "(" | ")" | "" character = letter | digit | symbol | "_" ;


title: فرم باکوس نائور توسعه یافته

text: identifier = letter , { letter | digit | "_" } ; terminal = "'" , character , { character } , "'"


title: فرم باکوس نائور توسعه یافته

text: lhs = identifier ; rhs = identifier


title: فرم باکوس نائور توسعه یافته

text: rule = lhs , "=" , rhs , ";" ; grammar = { rule } ;


title: فرم باکوس نائور توسعه یافته

text: یک زبان برنامه‌نویسی مانند پاسکال تعاریف را می‌تواند در EBNF به شرح زیر تعریف کند.


title: فرم باکوس نائور توسعه یافته

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


title: فرم باکوس نائور توسعه یافته

text: هر دستور زبان EBNF نیز می‌تواند در BNF نمایش داده شود. اگر چه نمایه‌های آن دارای عمر طولانی تری می‌باشند. به عنوان مثال گزینه‌ها و تکرارها نمی‌تواند به‌طور مستقیم در BNF بیان شود و نیازمند استفاده از یک قانون متوسط یا تولید جایگزین است که تعریف شده یا چیزی را به‌طور اختیاری و تکراری تولید کرده‌است. همان سازنده‌ها هنوز هم می‌توانند در EBNF استفاده شوند. BNF از نماد (, |, ::=) برای خود استفاده می‌کند، اما نقل قول‌ها در اطراف رشته‌های ترمینال را شامل نمی‌شود. این مانع از این کاراکترها در زبان می‌شود و نیاز به یک نماد ویژه برای رشته خاصی دارد. EBNF پایانه‌ها به وضوح در داخل علامت “ “ یا ' ' محصور می‌شوند. براکت زاویه را برای غیرترمینال‌ها می‌توان حذف نمود. همچنین BNF تنها می‌تواند یک قاعده را در یک خط نشان دهد. در حالی که در EBNF دستورهای متناوب وجود داشته‌است. علاوه بر این، EBNF شامل مکانیزیم‌هایی برای پیشرفت بوده که تعریف تعدادی از تکرارها به استثنای جایگزین‌های کامنت و غیره را دارد.


title: فرم باکوس نائور توسعه یافته

text: معاهده‌های زیر استفاده می‌شوند. ۱- هر شناسه فرعی BNF به عنوان یک یا چند عبارت با هم ترکیب شده‌اند. ۲- یک فراشناسایی که با استفاده از علایم پایان می‌یابد. براساس نام نماد ترمینال BNF تمدید شده‌است. کاراکترهای نمادی که هر اپراتور BNF از آن تمدید شده و اولویت ضمنی آن را نشان می‌دهند.  - except-symbol = defining-symbol . terminator-symbol اولویت عادی توسط جفت‌های براکت زیر لغو می‌شود. ' first-quote-symbol first-quote-symbol ' نماد اول آپستروف است که توسط ISO/IEC 646:1991 تعریف شده‌است. با این حال این استاندارد کاراکتر ISO هفت بیتی را برای تبادل اطلاعات را به عنوان یک مرجع قانونی و بدون هیچ نامی از سایر مجموعه کاراکترها را دارد؛ بنابراین به‌طور رسمی، هیچ گونه سردرگمی با کاراکترهای یونیکد خارج از محدوده هفت بیتی ASCTE را ندارد. به عنوان مثال قوانین زیر برای بیان تکرار نشان داده شده‌اند.


title: فرم باکوس نائور توسعه یافته

text: aa = "A"; bb = 3 * aa, "B"; cc = 3 * [aa], "C"; dd = {aa}, "D"; ee = aa, {aa}, "E"; ff = 3 * aa, 3 * [aa], "F"; gg = {3 * aa}, "G";


title: فرم باکوس نائور توسعه یافته

text: رشته‌های ترمینال تعریف شده توسط این قوانین به شرح زیر می‌باشند. aa: A


title: فرم باکوس نائور توسعه یافته

text: با توجه به استاندارد ISO 14977، EBNF به معنی توسعه پذیری بوده و دو امکان برای آن ذکر شده‌است. اولین قسمت بخشی از زبان EBNF بوده که دارای دنباله خاصی است و متن دلخواه در یک دنباله خاص فراتر از محدوده استاندارد EBNF می‌باشد. برای مثال کاراکتر فضای خالی می‌تواند توسط قوانین زیر بیان شود.


title: فرم باکوس نائور توسعه یافته

text: دومین حالت برای توسعه با استفاده از این واقعیت است که پرانتز در EBNF نمی‌تواند در کنار شناسه قرار گیرد؛ لذا EBNF زیر معتبر است.


title: فرم باکوس نائور توسعه یافته

text: براساس شرایط مثال زیر EBNF معتبر نیست.


title: فرم باکوس نائور توسعه یافته

text: بنابراین گسترش EBNF می‌تواند با استفاده از این علامت‌ها انجام شود. به عنوان مثال در گرامر Lisp، تابع کاربردی را می‌توان با قانون زیر بیان نمود.


title: نساج شبکه‌های عصبی

text: شبکه‌های عصبی عمیق (DNNs) مدل‌های یادگیری هستند که دارای محاسبات خیلی زیادی‌اند. این مدل‌ها کاربردهای روزافزونی در بخش‌های مختلف دارند. از آنجا که FPGA ها یک زیرساخت قابل‌برنامه‌نویسی برای شتاب‌دادن به محاسبات می‌دهند و همچنین امروزه در بیشتر دنیا به سادگی قابل دسترس‌اند، FPGAها یک انتخاب خیلی خوب برای پیاده‌سازی مدل‌های DNN هستند. اما استفاده از FPGAها به دلیل اینکه به‌دست آوردن کارایی و مصرف انرژی کم آنها به‌طور همزمان کار خیلی سختی است و همچنین DNNها به حافظه زیادی نیاز دارند (در FPGA معمولاً حافظه روی برد کم است)، پیاده‌سازی مدل‌ها با FPGA بسیار دشوار است. نساج شبکه‌های عصبی (DNNWEAVER) یک چارچوب است که به صورت خودکار یک کد قابل‌سنتز برای یک زوج مرتب (DNN, FPGA) تولید می‌کند. مدل DNN را به صورتی که در Caffe معرفی می‌کنند به عنوان ورودی می‌دهند.


title: نساج شبکه‌های عصبی

text: روند کلی کار این برنامه به این صورت است که ابتدا مدل ورودی را به یک زبان میانی تبدیل می‌کند که یک گراف از جریان داده کلی را نشان می‌دهد. در این مرحله با الگوریتمهای مختلف مدل داده شده را گروه‌بندی می‌کند تا با توجه به حافظه FPGA و دیگر منابع موجود روی FPGA به حداکثر استفاده مجدد از داده‌ها و بالاترین سطح کارایی برسد. بعد از آن نتیجه نهایی یک کد سنتزپذیر است که با بالاترین کارایی روی FPGA موردنظر تمامی نیازهای مدل ورودی را برآورده می‌سازد.


title: نساج شبکه‌های عصبی

text: این کار کمک می‌کند تا چرخه طولانی لازم برای استفاده از FPGA در شبکه‌های عصبی عمیق کوتاه‌تر شود. هدف از این کار تولید یک چارچوب خودکار است که اولاً برنامه‌نویس را از جزییات مربوط به طراحی و بهینه‌سازی سخت‌افزار جدا می‌کند. دوماً خود چارچوب به منابع محدود موجود روی FPGA دست و پنجه نرم می‌کند؛ و در نهایت چارچوب پایدار برای FPGA فراهم می‌کند که کارایی بالایی را برای پیاده‌سازی مدل‌های مختلف شبکه‌های عصبی عمیق روی FPGAهای گوناگون ارائه می‌کند. برای رسیدن به چنین هدف‌هایی DNNWEAVER طراحی شده‌است. در مرحله اول DNNWEAVER نیاز به یک مدل شبکه عصبی عمیق دارد که با استفاده از یک رابط سطح بالا مشخص شده‌است.


title: نساج شبکه‌های عصبی

text: ورودی برنامه DNNWEAVER یک توصیف‌گر سطح بالا از شبکه‌های عصبی عمیق است که در دانشگاه برکلی با نام قالب Caffe درست شده‌است.


title: نساج شبکه‌های عصبی

text: Caffe یکی از پراستفاده‌ترین چارچوب‌های یادگیری عمیق است که توصیف شبکه را به عنوان ورودی می‌گیرد و به مدلی قابل اجرا روی CPU یا GPU تبدیل می‌کند.


title: نساج شبکه‌های عصبی

text: DNNWEAVER به صورت خودکار مدل ورودی را به کد سنتزپذیر زبان وریلاگ تبدیل می‌کند. DNNWEAVER از چهار بخش نرم‌افزاری تشکیل شده‌است:


title: نساج شبکه‌های عصبی

text: ترجمه‌گر شبکه عمیق توصیف‌شده را به معماری مجموعه دستورها خاصی که مسیر داده را مشخص می‌کند تبدیل می‌کند. هر دستور در این مجموعه نشان دهنده یک گره در گراف مسیر داده شبکه است. توجه کنید که FPGA مستقیماً این دستورها را اجرا نمی‌کند. کامپایلر DNNWEAVER این دستورها را به سیگنال‌های کنترلی FPGA می‌نگارد و یک تقویم اجرا را درست می‌کند. این روش یک واسط نرم‌افزار-سخت‌افزار یکپارچه را فراهم می‌کند؛ بنابراین به کمک این معماری مجموعه دستورها انواع گوناگونی از پیاده‌سازی شتاب‌دهنده‌ها را که با محدودیت‌های FPGA مقصد سازگار است، امکان‌پذیر می‌کند.


title: نساج شبکه‌های عصبی

text: نقشه‌کش طرح دستورها تولید شده در مرحله قبل را به عنوان ورودی می‌گیرد و با کمک الگوریتم بهینه‌سازی منابع الگو قالب‌های سخت‌افزاری را برای FPGA مقصد بهینه می‌کند. نقشه‌کش طرح محاسبات هر لایه را به گروه‌هایی از عملگرها بخش‌بندی می‌کند که داده‌ها را به اشتراک می‌گذارند یا استفاده مجدد می‌کنند. به هرکدام این بخش‌ها تکه می‌گوییم. هر تکه بعد از محاسبه در حافظه ریخته می‌شود و FPGA به سراغ محاسبه تکه بعدی می‌رود. شتاب‌دهنده شبکه‌های عصبی مشکل اساسی با مقدار زیاد حافظه موردنیاز برخلاف حافظه کم FPGA دارد که DNNWEAVER این مشکل را با استفاده از الگوریتم بهینه‌سازی منابع الگو بهبود می‌دهد و به کمک آن یک تعادل بین عملگرهای موازی و استفاده مجدد از داده‌ها با توجه به محدودیت‌های FPGA مقصد برقرار می‌کند.


title: نساج شبکه‌های عصبی

text: نسّاجی طرح مرحله یکی‌مانده به آخر از DNNWEAVER است که ورودی آن مقدار منابع موردنیاز و تقویم اجرای تولید شده در مرحله قبل است و به کمک آن هسته شتاب‌دهنده را تولید می‌کند. DNNWEAVER از تعدادی قالب بهینه‌سازی دستی استفاده می‌کند که با توجه به گرفتن منابع و سازمان‌دهی سخت‌افزار که در مرحله قبل تولید شده از آن قالب‌ها استفاده می‌کند.


title: نساج شبکه‌های عصبی

text: آخرین قسمت DNNWEAVER مجتمع‌کننده است. در این مرحله کدهای رابط حافظه به کدهای شتاب‌دهنده اضافه می‌شود. از آنجایی که FPGAهای مختلف از رابط‌های مختلفی برای ارتباط با DRAM خارجی استفاده می‌کنند، این بخش شامل کتابخانه‌هایی از رابط‌های DRAM است که در هر بار کد لازم را اضافه می‌کند.


title: نساج شبکه‌های عصبی

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


title: نساج شبکه‌های عصبی

text: Tabla یک شتاب‌دهنده FPGA برای فاز آموزش الگوریتم‌های یادگیری ماشین ارائه می‌کند در حالی که DNNWEAVER رو رابط شبکه‌های عصبی تمرکز دارد. Tabla از زبان ریاضیاتی مختص به خودش استفاده می‌کند در حالی که DNNWEAVER از زبان Caffe برای مشخص کردن مدل استفاده می‌کند.


title: نساج شبکه‌های عصبی

text: کار انجام شده توسط چن و همکارانش روی طرحی تحلیلی بر اساس مدل خط بیشترین کار می‌کند تا با استفاده از آن سریع‌ترین طرح را برای شبکه عصبی عمیق مربوطه روی FPGA بیابند. اما این کار برخی لایه‌ها مثل ائتلافی (Pooling) را دربر نمی‌گیرد.


title: جدول کنترل

text: جدول کنترل به دسته‌ای از جداول گفته می‌شود که اطلاعات لازم برای کنترل جریان برنامه یا بخشی از این اطلاعات را در خود ذخیره کرده‌است. اطلاعات این جدول جزء اطلاعات سطح بالای سیستم تعریف می‌شود و معمولاً فقط برنامه‌نویس متخصص یا مدیر سیستم دسترسی تغییر در ساختار آن را دارد. جدول کنترل معمولاً به صورت جدول نشان داده می‌شود زیرا دیدن اطلاعات در جدول آسانتر است و ساختار دو بعدی آن مناسب نشان دادن رابطه اطلاعات است، اما جدول کنترل محدود به فقط جدول نیست می‌توان جدول را با استفاده از ماشین حالات متناهی یا ماشین حالات UML نشان داد. در جدول‌های کنترل ساختار مشابه با ساختار شرطی و صدا زدن تابع وجود دارد و با استفاده از این جدول می‌توان از تکرار ساختارهای تکراری جلوگیری کرد. جدول کنترل می‌تواند یک بعدی، دو بعدی یا چند بعدی باشد. اندازه جدول می‌تواند ثابت یا متغیر باشد. همچنین این امکان وجود دارد که بتوان جدول را برای دستگاه‌های متعدد ساخت به این صورت که الگوریتم در جدول کنترل قرار بگیرد و برای هر دستگاه متناسب با آن دستگاه مفسر مناسب ساخته شود. برای ساخت این جدول می‌توان از روش‌های مختلفی مانند درهم‌سازی یا آدرس‌دهی مستقیم استفاده کرد و برای برنامه جدول می‌توان از هر زبانی از جمله زبان‌های سطح بالا نیز استفاده کرد. می‌توان جدول را روی حافظه اصلی یا حافظه‌های جانبی ذخیره کرد ولی مکان جدول برای اجرای مفسر روی آن باید در کل زمان اجرای برنامه ثابت باشد. برای رسیدن به سرعت مناسب جدول کنترل باید در حافظه اصلی ذخیره شود. از این جدول برای تصمیم‌گیری سریع استفاده می‌کنند که سرعت اجرا را بسیار بالا می‌برد ولی نیاز به حافظه زیاد دارد و ساختارهای پیچیده را نمی‌توان با استفاده از آن تفسیر کرد.


title: جدول کنترل

text: معمولاً جدول‌های ساخته‌شده برای تفسیر زبان‌ها نیاز به مهارت زیادی دارند و قابل استفاده در سیستم‌های مختلف نیستند و برای یک سیستم خاص طراحی می‌شوند، اما در صورت ساخته شدن جدول کنترل کوچک سرعت اجرای برنامه می‌تواند بسیار بهتر شود.


title: جدول کنترل

text: جدول اسکی یک نمونه از جدول کنترل یک بعدی است، این جدول اطلاعات خام عددی را به نمادها و کاراکترها تبدیل می‌کند. همچنین جدول شاخه‌ای که کد زبان ماشین و شاخه‌ها در آن نوشته می‌شود یک نمونه از جدول کنترل یک بعدی است.


title: جدول کنترل

text: از جدول‌های کنترل چند بعدی می‌توان برای پیاده‌سازی درخت‌های تصمیم و تصمیم‌های چند مرحله‌ای استفاده کرد.


title: جدول کنترل

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


title: جدول کنترل

text: در موارد دیگر می‌توان از جدول کنترل برای پیاده‌سازی زبان‌های مبتنی بر ماشین‌های حالت متناهی و پیاده‌سازی درخت‌های تصمیم‌گیری استفاده کرد. از جدول کنترل برای ساختن جدول جستجو نیز استفاده می‌شود.


title: جدول کنترل

text: صفحات گسترده که برای ذخیره اطلاعات استفاده می‌شوند نیز می‌توانند یک نمونه از جدول کنترل باشند.


title: جدول کنترل

text: می‌توان ساختار switch که در زبان‌های برنامه‌نویسی متعددی استفاده می‌شود را با استفاده از جدول جستجو که یک مثال از جدول کنترل است ساخت. مثلاً اگر برنامه بخواهد یک حرف ورودی از کنسول بخواند و بر حسب آن تصمیم بگیرد چه عملی انجام بدهد جدول زیر می‌تواند برای انجام این کار کمک کند: CT1


title: جدول کنترل

text: یک مثال دیگر از کاربرد این زبان ماشین IBM/360 است. این ماشین ۱۶MB حافظه قابل آدرس‌دهی دارد و برای بررسی کردن یک کاراکتر ۲۵۶ حالت مختلف وجود دارد که با استفاده از جدول کنترل بررسی کاراکترها در ۲۶۵ خط کد قابل انجام است اما با استفاده از دستورهای مقایسه و شاخه شاخه کردن نیاز به ۵۱۲ خط کد دارد که با توجه به حجم کم حافظه در این ماشین روش اول بسیار بهتر است.


title: جدول کنترل

text: . default action … none of the values in table match, do something else . alternatively be in-line code) . instruction(s) to add . instruction(s) to subtract . etc..


title: جدول کنترل

text: از مزایای جدول کنترل می‌توان به تمیز بودن و واضح بودن برنامه، قابلیت پیاده‌سازی روی دستگاه‌های متفاوت، انعطاف‌پذیری زیاد، استفاده مجدد و بهینه از ساختارهای تکراری، قابلیت گسترش، قابلیت فشرده سازی و میزان حافظه مورد نیاز کمتر اشاره کرد. اما در کنار این مزایا این جدول‌ها برخی معایب نیز دارند از جمله این که طراحی جدول‌ها بسیار سخت و وقت‌گیر است و نیاز به مهارت زیادی دارد، برخی تغییرات کوچک برنامه می‌تواند باعث ایجاد تغییرات عمده در ساختار جدول شود، همچنین همه ساختارهای پیچیده قابل پیاده‌سازی با استفاده از جدول کنترل نیستند.


title: حذف کد مرده

text: در نظریه کامپایلر، شاخه‌ای از علوم کامپیوتر نظری، حذف کد مرده (به انگلیسی: ) نوعی از بهینه‌سازی کامپایلر (به انگلیسی: ) است، که برای حذف بخشی از کد، که در نتیجهٔ برنامه تأثیری ندارد، استفاده می‌شود. کد مرده شامل بخشی از کد است که هیچ‌گاه اجرا نمی‌شود و یا در صورت اجرا، خروجی آن مورد استفاده قرار نگرفته و در واقع فقط بر روی متغیرهای مرده (متغیرهایی که در بقیه بخش‌های برنامه خوانده نمی‌شوند و از آن‌ها استفاده‌ای نمی‌شود) تأثیر می‌گذارد. به‌طور معمول، کامپایلرها در زمان کامپایل برنامه، به صورت بازگشتی تعیین می‌کنند که کدام متغیرها و بخش‌های برنامه استفاده شده‌اند. متغیرها و بخش‌های استفاده شده علامت گذاری می‌شوند و در نهایت بخش‌های علامت نخورده، از برنامه حذف می‌شوند. اکثر کامپایلرهای پیشرفته، گزینه‌های متعددی را در سطوح مختلف برای حذف کد مرده در اختیار قرار می‌دهند. در سطوح پایین، کامپایلر فقط بخش‌هایی از کد که اجرای آن‌های غیرممکن است را حذف می‌کند. در سطوح بالاتر کامپایلر فضایی را برای ذخیره‌سازی متغیرهای بی‌استفاده در نظر نمی‌گیرد. در سطوح بالاتر از آن نیز، کامپایلر دستورها و توابع بی‌استفاده را شناسایی و حذف می‌کند.


title: حذف کد مرده

text: حذف کد مرده مزیت‌های فراوانی دارد که از جملهٔ آن‌ها می‌توان به کم شدن اندازهٔ برنامه اشاره کرد، که بدین ترتیب از اجرا شدن کدی که در نتیجهٔ برنامه تأثیری ندارد و عمل‌هایی که می‌توان بدون انجام آن‌ها به نتیجه رسید، جلوگیری می‌شود. در نتیجه، مدت زمان اجرای برنامه کاهش می‌یابد و این موضوع در بسیاری از اوقات، می‌تواند تأثیر زیادی در بهینه‌تر شدن برنامه داشته باشد. علاوه بر این، حذف کد مرده باعث ساده‌تر شدن ساختار برنامه می‌شود و به این صورت، راه برای انجام دیگر بهینه‌سازی‌ها باز می‌شود.


title: حذف کد مرده

text: از طرفی باید در عملیات حذف کد مرده بسیار دقت نمود، چرا که ممکن است نتیجهٔ محاسبات بخشی از کد، در جای دیگری استفاده نشود، ولی آن محاسبات باعث ایجاد تغییر در یک متغیر سراسری و یا تولید استثنا (به انگلیسی: ) شود، که در این صورت حذف آن بخش از کد، باعث ایجاد خطا در عملکرد برنامه می‌شود. به‌طور معمول، کامپایلرها زمانی که در مورد مرده بودن بخشی از کد ابهام هست، به صورت محافظ کارانه عمل می‌کنند.


title: حذف کد مرده

text: این برنامه که با زبان سی () نوشته شده‌است را در نظر می‌گیریم. تحلیلی ساده از کاربرد مقادیر، مشخص می‌کند که متغیر codice_1 بعد از این‌که برای اولین بار در خط چهارم مقداردهی می‌شود، در تابع codice_2 استفاده نمی‌شود. از طرفی، متغیر codice_1 یک متغیر محلی در تابع codice_2 است و به این دلیل نمی‌تواند خارج از codice_2 استفاده شود. بنابراین متغیر codice_1 مرده است و کامپایلر در زمان بهینه‌سازی می‌تواند آن‌را حذف نماید.


title: حذف کد مرده

text: همچنین از آن‌جا که تابع همواره در خط هفتم، با دستور بازگشت به کار خود پایان می‌دهد، هیچ مسیر اجرایی به خط هشتم که متغیر codice_1 برای دومین بار در آن مقداردهی می‌شود نمی‌رسد. بنابراین، دسترسی به این مقداردهی امکان‌پذیر نمی‌باشد و این بخش از کد، قابل حذف شدن است. باید دقت شود که اگر برنامه ساختار پیچیده تری داشت، به عنوان مثال بعد از دستور بازگشت از تابع در خط هفتم، برچسبی وجود داشت و از جای دیگری از برنامه دستور codice_8 به آن برچسب بود، آن موقع ممکن بود مسیر اجرایی به دومین مقداردهی متغیر codice_1 وجود داشته باشد و دیگر codice_1 غیرقابل دسترس نبود.


title: حذف کد مرده

text: علاوه بر این، با این‌که محاسباتی در این تابع انجام می‌شود، مقدار آن محاسبات در جایی که خارج از حوزهٔ این تابع قابل دسترسی باشد ذخیره نمی‌شود. بنابراین با توجه به اینکه تابع همواره مقدار ۹۶ را بازمی‌گرداند، ممکن است در زمان بهینه‌سازی به مقداری که بازمی‌گرداند ساده شود.


title: حذف کد مرده

text: حال برنامهٔ دیگری که با زبان سی نوشته شده‌است را در نظر می‌گیریم. در این مثال نیز از آنجا که مقدار صفر، همواره برابر با false در نظر گرفته می‌شود، دستور if هیچ‌گاه اجرا نخواهد شد و بنابراین کل بخش if در هنگام بهینه‌سازی از برنامه حذف می‌شود.


title: حذف کد مرده

text: گاهی اوقات غیرقابل دسترس و مرده بودن بخشی از کد، در شرایط خاصی اتفاق می‌افتد و در هنگام کامپایل مشخص نمی‌شود. به عنوان مثال این شرایط را ورودی برنامه‌ها می‌توانند ایجاد کنند و باعث شوند بخشی از کد هیچ‌گاه در زمان اجرای برنامه، اجرا نشوند. بخشی از کد به صورت پویا مرده (به انگلیسی: Dynamically dead) است اگر بسته به شرایط برنامه در زمان اجرا، مقادیری که آن بخش از کد تولید می‌کند، در جای دیگری از برنامه استفاده نشود. به بیان دیگر، یک دستور به صورت پویا مرده، نمونه‌ای از یک دستور ایستا (به انگلیسی: Static instruction) است، که یک مقدار ثبات (به انگلیسی: Register) مرده را ایجاد می‌کند. محققان دریافته‌اند که کسر عظیمی از دستورات اجرا شدهٔ برنامه‌ها به صورت پویا مرده‌اند.


title: نظریه پاریک

text: قضیهٔ پاریک یکی از قضایای علوم کامپیوتر نظری است که در سال ۱۹۶۱ توسط روهیت پاریک(Rohit Parikh) اثبات شده‌است و در سال ۱۹۶۶ اثبات ساده تری برای آن ارائه شده‌است.[3] اثبات می‌کند که یک زبان مستقل از متن روی یک الفبای تک حرفی باید منظم باشد. از قضیهٔ پاریک می‌توان در اثبات مستقل از متن بودن یا نبودن یک زبان استفاده کرد. علاوه بر این از این قضیه برای اثبات این که یک زبان حاوی رشته‌ای با تعداد برابری از دو پایانه داده شده هست یا خیر.[1] این قضیه بیان می‌کند که اگر توالی نشانه‌ها در نظر گرفته نشود آنگاه زبان‌های مستقل از متن از نظر مجموعه‌های منظم و نشان دادن وجود یک زبان مستقل از متن ذاتاً مبهم غیر متمایزاند.


title: نظریه پاریک

text: اگر formula_1 مجموعهٔ یک الفبا باشد، بردار پاریک یک کلمه به صورت یک تابع در قالب formula_2 خواهد بود به‌طوری‌که formula_3 و formula_4 نشان دهندهٔ تعداد حرف formula_5 در کلمهٔ formula_6 است. می‌گوییم زیرمجموعه‌ای از formula_7 خطی است اگر به ازای بردارهای formula_8 این زیر مجموعه به صورت formula_9 باشد. می‌گوییم یک زیرمجموعه از formula_7 شبه‌خطی است اگر اجتماعی از چند زیرمجموعهٔ خطی باشد. فرض کنید formula_11 یک زبان مستقل از متن و formula_12مجموعهٔ بردارهای پاریک کلمات در formula_11باشد که formula_14. آنگاه formula_12 یک مجموعهٔ شبه خطی است. می‌گوییم دو زبان جابه‌جایی‌پذیرند اگر دارای مجموعهٔ بردارهای پاریک برابر باشند. اگر formula_16 یک مجموعه ی شبه‌خطی باشد، زبان شامل کلماتی که بردارهای پاریک آن‌ها در formula_16 است با بعضی از زبان‌های منطم جابه‌جایی‌پذیرند. در نتیجه هر زبان مستقل از متنی با بعضی از زبان‌های منظم جابه‌جایی‌پذیرند. در قضیهٔ پاریک اثبات می‌شود که بعضی از زبان‌های مستقل از متن فقط میتوانند گرامرهای مبهم داشته باشند که به این زبان ها، زبان‌های ذاتاً مبهم گفته می‌شود. به عبارتی دیگر بعضی از گرامرهای مستقل از متن را نمی‌توان به گرامر مستقل از متن غیر مبهمی تبدیل کرد. فرض کنید formula_1 الفبای یک زبان باشد که formula_19 و ترتیب formula_20 دلخواه ولی ثابت است. برای formula_21 تصویر پاریک معادل است با: که هر formula_23 تعداد formula_5ها در formula_6 hsj. نگاشت پاریک روی یک زبان به صورت مقابل تعریف می‌شود: برای یک زبان دلخواه مانند formula_11 که formula_27 قرار دهید formula_28 مثال: (نگاشت پاریک کلمات یک گرامر مستقل از متن) گرامر مستقل از متن formula_29 را با قواعد زیر در نظر بگیرید: این بدین معناست که زبان تولید شده توسط formula_33 دارای رشته‌هایی است که a و bها میتوانند در آن به صورت درهم آمیخته ظاهر شوند. اما از آنجایی که از تعریف زبان پیداست تعداد آن‌ها در رشته برابر خواهد بود. علاوه بر این همیشه از هر حرف حداقل یکی وجود دارد. حال اگر formula_34 و formula_35 را با توجه به تعریف بالا به ترتیب formula_36 و formula_37 بگیریم و رشته‌های formula_38 و formula_39 فرض کنیم. هر دو این رشته‌ها دارای نگاشت پاریک یکسان هستند؛ formula_40 که داریم formula_41 این قضیه با استقرا روی یک مجموعه از درخت‌های اشتقاق و با استفاده از نگاشت‌های پاریک به دست آمده از مجموعه ی درخت‌های اشتقاق پایانه‌ها و امکان بزرگ کردن آن‌ها در طول اشتقاق اثبات می‌شود.


title: محمدخان ایروانی

text: محمد خان ایروانی از فرماندهان نظامی ایران در دوره محمدشاه قاجار بود که درجه امیرتومانی داشت و بخشی از سپاه ایران را در جنگ هرات فرماندهی می‌کرد.


title: محمدخان ایروانی

text: او در سال ۱۲۵۲ قمری به دستور محمدشاه قاجار به حکومت عراق عجم منصوب شد.


title: محمدخان ایروانی

text: محمدخان در سال ۱۲۵۴ قمری با زینت‌الدوله دختر فتحعلی‌شاه قاجار ازدواج کرد و یک سال بعد در زمان محاصره شهر هرات درگذشت.


title: اردوگاه پناهندگان خان‌یونس

text: اردوگاه پناهندگان خان‌یونس (به عربی: مخیم خان یونس)؛ (انگلیسی: Khan Yunis Camp) یک منطقهٔ مسکونی در فلسطین است، که در خان یونس واقع در غرب شهر خان یونس و ۲ کیلومتری شرق ساحل مدیترانه که در نوار غزه جنوبی قرار دارد. اردوگاه پناهندگان خان‌یونس ۳۷٬۷۰۵ نفر جمعیت دارد.


title: اردوگاه پناهندگان خان‌یونس

text: در حالی که آژانس امداد و اقدام سازمان ملل متحد برای آوارگان فلسطینی در خاور نزدیک UNRWA اعلام کرده‌است در سال ۲۰۱۰ که حدود ۷۲۰۰۰ پناهنده فلسطینی در اردوگاه زندگی می‌کنند، اداره مرکزی آمار فلسطین در سرشماری سال ۲۰۰۷ آمار جمعیت خان یونس را ۳۷۷۰۵ نفر ثبت کرده‌است.


title: اردوگاه پناهندگان خان‌یونس

text: اردوگاه خان یونس پس از جنگ شش روزه ۱۹۴۸-اعراب- اسرائیل احداث شد و حدود ۳۵٫۰۰۰ پناهنده فلسطینی در آن اسکان داده شدند. در ۳ نوامبر ۱۹۵۶، اردوگاه و شهر خان یونس توسط نیروهای ارتش اسرائیل اشغال شد و در عملیات تهاجمی که صورت گرفت حدود ۲۷۵ نفر کشته شدند که ۱۴۰ پناهنده از اردوگاه را در بر می‌گرفت. ساکنان اردوگاه تصریح کردند که بیشتر تلفات پس از پایان جنگ‌ها رخ داد و آن هنگامی بود که ارتش به خانه‌هایی که مظنون به حضور شورشیان مسلح می‌دید تهاجم کرد. با این حال، مقامات اسرائیلی اعلام کردند که تلفات ناشی از مقاومت ساکنان اردوگاه بوده‌است.


title: اردوگاه پناهندگان خان‌یونس

text: طبق گزارش آژانس امداد و اقدام سازمان ملل متحد برای آوارگان فلسطینی در خاور نزدیک UNRWA، بسیاری از ساکنان این اردوگاه‌ها به دلیل عملیات توسط ارتش اسرائیل، خانه‌های خود را از دست دادند. UNRWA در اوائل دهه ۲۰۰۰ تلاش‌های بازسازی را آغاز کرد اما به دلیل تصرف این منطقه توسط حماس و محاصره اسرائیل در نوار غزه عمدتاً این پروژه متوقف شده‌است. UNRWA می‌گوید که حداقل ۱۰٬۰۰۰ خانه باید ساخته شوند.


title: ارزیابی کندرو

text: در میان استراتژی‌های ارزیابی در نظریهٔ زبان‌های برنامه‌نویسی، ارزیابی کندرو یا فراخوانی به هنگام نیاز استراتژی‌ای برای ارزیابی است که دارای دو ویژگی ارزیابی غیرموکد و اشتراک‌گذاری می‌باشد. ارزیابی غیرموکد موجب می‌شود که محاسبه و ارزیابی یک عبارت تا جای ممکن به تأخیر افتاده و در اولین زمانی که دسترسی به آن نیاز بود، محاسبه شود. ارزیابی کندرو به وسیلهٔ اشتراک‌گذاری از ارزیابی‌های تکراری جلوگیری می‌کند. به کمک اشتراک‌گذاری، زمان اجرای یک تابع به صورت توانی نسبت به دیگر استراتژی‌هایی که ارزیابی غیرموکد دارند کاهش می‌یابد و به این صورت ترکیب این دو ویژگی، ارزیابی کندرو را نسبت به دیگر استراتژی‌ها بهبود می‌بخشد. از جمله این استراتژی‌ها می‌توان استراتژی فراخوانی با نام را نام برد.


title: ارزیابی کندرو

text: در مقابل ارزیابی کندرو، ارزیابی تندرو یا استراتژی موکد قرار دارد. این استراتژی ارزیابی در بیشتر زبان‌های برنامه‌نویسی مورد استفاده قرار می‌گیرد. به‌طور خلاصه، در این ارزیابی برخلاف ارزیابی کندرو، رویهٔ یک تابع، حتی اگر هیچگاه مورد استفاده قرار نگیرد و یا بعد از زمان زیادی به آن نیاز داشته باشد، به محض فراخوانی برای یک یا چندین متغیر با مقادیر مشخص اجرا می‌شود.


title: ارزیابی کندرو

text: ارزیابی کندرو ابتدا برای جبر لاندا توسط کریستوفر وادزورث تعبیه شد. پیتر هندرسون و جیمز هیرام موریس و همچنین دنیل پائول فریدمن و دیوید وایس هر یک این ارزیابی را برای زبان‌های برنامه‌نویسی به‌طور مستقل تعریف کردند.


title: ارزیابی کندرو

text: ارزیابی کندرو طبق شرح جان لوئیس بنتلی در گزارش "«نوشتن برنامه کارآمد»" معمولاً با مموایز کردن ترکیب می‌شود. در عمل به هر عبارت که معادل تابعی از یک یا چند متغیر با مقادیری مشخص می‌باشد، خانه‌ای از حافظه تعلق می‌گیرد که این خانه با داشتن مقادیر متغیرها قابل دسترسی است. در مموایز کردن عبارات به دو دسته تقسیم می‌شوند. دستهٔ اول عباراتی هستند که برای بار اول محاسبه می‌شوند. در این دسته پس از محاسبهٔ عبارت، مقدار حاصل را در خانهٔ مربوطه نیز ذخیره می‌کنند. دستهٔ دوم عباراتی هستند که برای بار دوم و یا بیشتر مورد استفاده قرار می‌گیرند. این عبارات از دفعهٔ دوم به بعد، به جای محاسبهٔ مجدد، به خانهٔ حافظهٔ مربوطه رجوع کرده و مقدار را از خانهٔ حافظه برمی‌دارند. کارکرد مموایز کردن در ارزیابی کندرو تنها این تفاوت را قائل می‌شود که محاسبه و ذخیره‌سازی عبارت را تا اولین زمان نیاز به مقدار عبارت، به تأخیر می‌اندازد. روشن است که ایجاد این تأخیر اثر مخربی بر فرایند مموایز کردن ندارد و سلسله عملکرد آن را حفظ خواهد کرد.


title: ارزیابی کندرو

text: بنابراین در ارزیابی کندرو در صورت مواجه شدن با یک عبارت، ابتدا تا اولین نیاز به مقدار آن هیچ اقدامی صورت نمی‌گیرد. سپس در هنگام نیاز به مقدار عبارت، ابتدا بررسی می‌شود که این اولین باریست که نیاز به محاسبهٔ عبارت وجود دارد یا خیر. اگر اولین بار باشد، مقدار عبارت طبق رویهٔ تابع محاسبه گردیده و مقدار آن در خانهٔ مربوطه نیز ذخیره می‌شود. در غیر این صورت، بدون محاسبهٔ مجدد عبارت، مقدار آن که در مراحل قبل محاسبه شده، از خانهٔ مربوطه برداشته می‌شود و مورد استفاده قرار می‌گیرد. بخشی از حافظه را که به مقادیر عبارات تعلق می‌گیرد، جدول مراجع می‌نامند. غیرموکد بودن این ارزیابی، با توجه به این که ذخیرهٔ مقدار را تا زمان نیاز به تأخیر می‌اندازد، موجب کاهش حافظهٔ مورد استفاده در هر لحظه خواهد شد. اما با این حال محاسبهٔ حافظهٔ مورد استفاده در این روش ارزیابی قابل پیش‌بینی نیست. علاوه بر این در عبارات ساختاریافته، می‌توان با بخش‌بندی کردن عبارت، تنها بخش‌های مورد نیاز آن را محاسبه کرد و برای سایر بخش‌ها جدول مراجع و مقادیر ثابت را مورد استفاده قرار داد. با توجه به این که ایجاد لیست واسط نیز تا زمان نیاز به تعویق می‌افتد، استفاده از آن لزوماً هزینهٔ زیادی به همراه نخواهد داشت و این هزینه در موارد خاص چشمگیر خواهد بود. همچنین این ارزیابی، به کمک مموایز کردن، محاسبات تکراری را کاهش داده و زمان اجرای برنامه را بهبود می‌دهد.


title: ارزیابی کندرو

text: علی‌رغم وجود این مزایا، غیرموکد بودن ارزیابی موجب بهم ریختن ترتیب اجرای دستورات شده و ترکیب این ارزیابی با ویژگی‌های ضروری دیگر را دشوار می‌سازد. از جمله این ویژگی‌ها می‌توان مدیریت استثناءها و مدیریت ورودی/خروجی را نام برد. علاوه بر این ارزیابی کندرو می‌تواند موجب نشت حافظه شود.


title: ارزیابی کندرو

text: برخی از زبان‌های برنامه‌نویسی به تأخیر انداختن ارزیابی عبارات را به صورت معمول انجام می‌دهند. در عین حال برخی زبان‌های دیگر از توابع و نمادهای خاصی برای این کار استفاده می‌کنند. برای مثال در زبان‌های میراندا و هاسکل این کار به‌طور معمول انجام می‌شود، در حالی که در زبان اسکیم از عباراتی معادل "تاخیر" و "اجرا" و در زبان اکمل از عباراتی معادل "کندرو" و "اجرای کندرو" استفاده می‌شود. برخی دیگر از زبان‌ها، ارزیابی کندرو را تنها برای برخی از ساختمان‌داده‌ها و یا تنها بر روی یک ساختمان‌دادهٔ خودساخته تعریف می‌کنند. برای مثال در زبان پرل۶ ارزیابی کندرو بر روی لیست‌ها تعریف شده، در حالی که این ارزیابی در این زبان برای محاسبهٔ توابع و عملگرهای ریاضی تعبیه نشده‌است.


title: ارزیابی کندرو

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


title: تجزیه‌کننده کاهشی بازگشتی

text: تجزیه‌کننده کاهشی بازگشتی (انگلیسی: Recursive descent parser) یک تجزیه‌کننده بالا به پایین است که درخت تجزیه را از بالا و حالت اولیه می‌سازد تا به رشته ورودی کاربر برسد. این تجزیه‌کننده به صورت بازگشتی، ورودی را تجزیه می‌کند تا درخت تجزیه را بسازد.


title: تجزیه‌کننده کاهشی بازگشتی

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