aria-haman/haman-fa-wikipedia-articles-186k huggingface dataset:
موضوع مقاله: مبدل با حالت محدود | مخاطب: عمومی | لحن: دانشنامه‌ای | ساختار: عنوان، مقدمه، 3 بخش، جمع‌بندی | مقاله: | # مبدل با حالت محدود | مقدمه: حالت ساده‌اش دو نوار یکی نوار ورودی و دیگری نوار خروجی دارد که با خواندن از روی نوار ورودی، نوار خروجی را ایجاد می‌کند. | ## بخش 1: مبدل با حالت محدود | تفاوت مبدل با حالت متناهی با ماشین با حالت متناهی در این است که ماشین تنها برای تشخیص اینکه رشته‌ای در زبان منظم است به کار می‌رود ولی مبدل علاوه بر تشخیص وجود رشته، رشتهٔ خروجی را از رشته ورودی می‌سازد. در واقع این مبدل شکل بسط داده شده‌ای از ماشین با حالت متناهی است و دو مجموعه از نمادها را به هم می‌نگارد و مترجم و مربوط‌کننده رشته دو نوار تعبیر می‌شود. تعریف رسمی یک مبدل حالت متناهی را با ۶ تاپل (چندتایی) نمایش می‌دهند: : مجموعه متناهی از حالت‌هایی که یک مبدل می‌تواند داشته باشد. (برای نمایش رشته خالی است) نحوه نمایش برای نمایش مبدل حالت متناهی می‌توانیم از گراف جهت‌دار که گراف انتقال نیز نامیده می‌شود استفاده کنیم. راس‌های این گراف، مجموعه حالت‌های مبدل اند و به معنی وجود یالی از رأس به رأس است که نماد برچسب ورودی و برچست خروجی یال است و متناسب با نوع مبدل، در دو نوار اعمال می‌شود. یال ۰:۱ به این معنی است که در این انتقال، مبدل نماد ۰ را از نوار اولی می‌خواند و در دومین نوار می‌نویسد. | ## بخش 2: مبدل با حالت محدود | انواع مبدل‌ها برحسب اینکه از کدام نوار بخواند و در کدام نوار بنویسد، مبدل به چند نوع تبدیل می‌شود. نوع تولیدکننده، که قادر است در هر دو نوار بنویسد و نوع تشخیص دهنده که قادر است از هر دو نوار بخواند. نوع چپ به راست، از نوار اول می‌خواند و در نوار دوم می‌نویسد و نوع راست به چپ هم برعکس قبلی عمل می‌کند. مبدل حالت محدود وزن‌دار با افزودن وزن به هر یک از انتقالات مبدل با حالت متناهی، مبدل وزن‌دار آن تشکیل می‌شود. ایده این نوع مبدل تنها در وجود وزن به انتقال‌ها نیست، بلکه یک سطحی از مفاهیم ریاضی را که به نام نیم-حلقه را در مبدل‌ها را موجب می‌شود. در واقع این مفهوم ریاضی مشخص می‌کند چگونه در طی عملیات‌ها روی مبدل، این وزن انتقال‌ها ترکیب می‌شود. | ## بخش 3: مبدل با حالت محدود | روابط منظم همان‌طور که ماشین حالت محدود، هم متناظر زبان‌های منظم است، مبدل حالت محدود نیز متناظر روابط منظم و نمایش دهندهٔ آنهاست. همانند زبان‌های منظم، تحت اجتماع بسته‌اند ولی تحت تفاضل و مکمل‌گیری و اشتراک بسته نیستند. (البته بیشتر روابط منظم که در آن از استفاده نشده‌است، به احتمال زیاد تحت این عملیات‌ها بسته هستند) کاربردها مبدل با حالت محدود، کاربرهای فراوانی هم در کامپایلرها و هم در حوزه پردازش زبان طبیعی دارد. تجزیه تکواژشناسی جهت به دست آوردن ویژگی‌ها و ساختار یک واژه از جمله اسم یا فعل کاربرد دارد. | ## جمع‌بندی | مثلاً رایانه‌ها ← اسم + علامت جمع ترجمه ساده بین زبان‌ها برای مثال ترجمه از زبان فارسی به انگلیسی (به صورت کلمه به کلمه) دستورهای ساده ساخته‌شده برای رایانه در ترجمه دستورهای صوتی که به وسیله الکترونیکی از طریق دستیار شخصی صوتی هوشمند مثل نرم‌افزارهایی همچون سیری، وارد می‌شود نیز کاربرد مورد استفاده است.
موضوع مقاله: ماشین حالت یو.ام.ال | مخاطب: عمومی | لحن: دانشنامه‌ای | ساختار: عنوان، مقدمه، 3 بخش، جمع‌بندی | مقاله: | # ماشین حالت یو.ام.ال | مقدمه: حالت مرکب، از یک یا چند ناحیه تشکیل شده‌است که هر ناحیه، خودش یک ماشین حالت یو.ام. | ## بخش 1: ماشین حالت یو.ام.ال | ال است و حالت شروع و پایان دارد و وقتی وارد این حالت شدیم، ماشین، از حالت شروع درون این حالت، شروع به کار می‌کند و زمانی که به حالت پایانی رسید، بر اساس یال‌های خروجی آن، به حالت‌های دیگر می‌رود. اجرای همزمان چند ناحیه همان‌طور که بالاتر ذکر شد، در حالت‌های مرکب، ممکن است چند ناحیه داشته باشیم و این ناحیه‌ها بخواهند همزمان اجرا شوند. | ## بخش 2: ماشین حالت یو.ام.ال | در این صورت، بین یال‌های ورودی به آن ناحیه‌ها، یک خط عمودی رسم کنیم و بین یال‌های خروجی از آن‌ها نیز یک خط عمودی رسم می‌کنیم. حالت تاریخ این حالت برای زمانی استفاده می‌شود که از یک حالت مرکب خارج شویم و بخواهیم دوباره به آن وارد شویم و بخواهیم اطلاعات مرحله قبل حفظ شود. | ## بخش 3: ماشین حالت یو.ام.ال | برای این منظور، هنگام ورود مجدد به درون حالت مرکب، ابتدا به حالتی به نام "H" یا "*H" می‌رویم و سپس به حالت مدنظر منتقل می‌شویم. | ## جمع‌بندی | "H" برای زمانی استفاده می‌شود که بخواهیم فقط اطلاعات خود حالت مرکب را ذخیره کنیم اما "*H" برای زمانی است که بخواهیم اطلاعات تمام ماشین را ذخیره کنیم.
موضوع مقاله: زبان توصیف کامپایلر | مخاطب: عمومی | لحن: دانشنامه‌ای | ساختار: عنوان، مقدمه، 3 بخش، جمع‌بندی | مقاله: | # زبان توصیف کامپایلر | مقدمه: زبان توصیف کامپایلر یک زبان برنامه‌نویسی است که برای توسعهٔ کامپایلرها و بر پایهٔ دستور زبان‌های ضمیمه بنا شده‌است. | ## بخش 1: زبان توصیف کامپایلر | ظهور این زبان هم‌زمان بود با ظهور زبان برنامه‌نویسی الگول۶۸ و اولین آزمایش زبان توصیف کامپایلر با این زبان انجام شد. این زبان سال‌ها در دانشگاه صنعتی برلین(غربی) برای درس طراحی کامپایلر تدریس می‌شد. در کشورهای دیگری نظیر فرانسه، مجارستان و جمهوری دموکراتیک آلمان نیز از این زبان استفاده می‌شده است. بسیاری از کسانی که از این زبان استفاده می‌کردند آن را مطابق خواست خود گسترش داده‌اند. نسخهٔ ثانویه در سال ۱۹۷۵ با اعمال تغییراتی نسخهٔ جدید این زبان با نام CDL2 تثبیت شد. برای این که این زبان روی ماشین‌های مختلف قابل اجرا باشد، چند نسخه تولیدکنندهٔ کد برای آن نوشته شد. از قبیل: بهینه‌سازی سراسری کامپایل‌های جداگانه بررسی معنایی ایستا برنامه‌نویسی پودمانی این زبان مبانی CDL1 را پابرجا نگه داشته بود، ولی برای اجرای پروژه‌های بزرگتر مناسب‌تر بود. بهینه‌سازی‌های استفاده شده در این زبان فقط مختص زمان و مکان خود نبودند و در سطح جهانی مطرح شدند. | ## بخش 2: زبان توصیف کامپایلر | در سال ۱۹۷۶ زبان توصیف کامپایلر پا از حوزهٔ دانشگاهی فراتر گذاشت و سازندگان آن با چند سازندهٔ آلمانی قرارداد بستند. در نتیجهٔ این قرارداد پروژه‌ای در سال ۱۹۷۷ در دانشگاه صنعتی برلین با هدف ساختن یک سیستم برنامه‌نویسی مبتنی بر CDL2 و مناسب استفاده در صنعت کلید خورد. در کنار این پروژه در دانشگاه رادبود توسعه و نگه‌داری کامپایلر CDL2 در حال انجام بود. هدف این پیاده‌سازی آشنایی قشر گسترده‌تری از مردم با این زبان و فلسفهٔ ایجاد آن بود. طراحی نسخهٔ اوّلیهٔ این زبان بسیاری از ویژگی‌های زبان‌های معمول برنامه‌نویسی را ندارد. از جملهٔ این ویژگی‌ها داشتن عملگرهای توکار مثل جمع، ضرب، مقایسه و یا عمل تخصیص است. قواعد ارزیابی این زبان شبیه به نحو قواعد فرم باکوس نائور است که برای بیان قواعد زبان‌های مستقل از متن ارائه شده‌است. این زبان اساساً از یک سری قاعده تشکیل شده‌است که می‌تواند به موفقیت یا شکست منجر شود. | ## بخش 3: زبان توصیف کامپایلر | به خاطر این که هر اجرای قاعده مطابق است با ارزیابی موفقیت یا عدم موفقیت آن، به هر اجرا یک ارزیابی می‌گویند. هر قاعده زمانی که ارزیابی می‌شود می‌تواند روی داده‌هایی که نوعشان مشخص‌نشده است عمل انجام دهد. در شرایط ایده‌آل نتیجهٔ این عمل تا وقتی که آن قاعده موفق ارزیابی نشود اعمال نمی‌شود. زمانی که داده‌ها به‌طور ایستا بررسی می‌شوند، این مشکل وجود دارد که حتی اگر قاعده‌ای موفق باشد، ممکن است قاعده‌ای که آن را فراخوانی کرده موفق نبوده باشد. استفاده زبان توصیف کامپایلر هم برای طراحی کامپایلرها و هم مقاصد دیگر استفاده شده‌است. سیستم MProlog پیاده‌سازی‌ای صنعتی از زبان برنامه‌نویسی منطقی پرولوگ است که بر روی معماری‌های عظیم مانند رایانهٔ بزرگ آی‌بی‌ام و اینتل اجرا می‌شد. | ## جمع‌بندی | علاوه بر این‌ها یک نرم‌افزار رابط کاربری گرافیکی تجاری هم به زبان CDL نوشته و نگه‌داری شده.
موضوع مقاله: تأثیر رنگ بر انسان | مخاطب: عمومی | لحن: دانشنامه‌ای | ساختار: عنوان، مقدمه، 3 بخش، جمع‌بندی | مقاله: | # تأثیر رنگ بر انسان | مقدمه: تأثیر اولیه رنگ به دریافت احساسی رنگ (فامداری) مربوط می‌شود که از طیف نور مرئی رنگ ناشی شده و از آن به احساس ذهنی تعبیر شده‌است. | ## بخش 1: تأثیر رنگ بر انسان | به عنوان نمونه فشار ملایم بر پلک‌ها و قرارگیری انسان تحت شوک الکتریکی در یک محیط تاریک احساس رنگ را برای انسان ایجاد می‌نماید که این احساس اثر مرئی، از خارج چشم نیست. تأثیر دیگر رنگ‌ها اثرات ذهنی رنگ‌های عینی می‌باشد و احساس‌های معینی را شامل می‌گردد که رنگ‌ها در بیننده ایجاد می‌نماید. در این شکل از تأثیر فامها به دو دسته پیش آینده و پس رونده تقسیم‌بندی می‌گردند که به ترتیب نزدیک بودن و دور بودن اشیا را در ذهن تداعی می‌نماید. بر همین اساس فام‌های دارای طول موج بلندتر (مثل قرمز و نارنجی) گرمتر از فام‌های طول موج کوتاه تر (مثل آبی و سبز) احساس می‌شوند. احساس گرمی و سردی، پیش آیندگی و پس روندگی در واقع اثرات ذهنی رنگ‌های عینی هستند که از جنبه روان‌شناسی رنگ نه از جنبه فیزیولوژیک رنگ، مورد بحث قرار می‌گیرد. پاسخ‌های فیزیولوژیکی و بیو مکانیکی فعال و دقیق از تشعشعات خورشیدی و محیط‌های مصنوعی بر روی بدن انسان اثبات این موضوع می‌باشد. | ## بخش 2: تأثیر رنگ بر انسان | انطباق ریتم‌های هورمونی بدن با شبانه روز و تاریکی و روشنی از پاسخ‌های بدن به رنگ‌ها می‌باشد. (موعدی، 1379: 56)موعدی، محمد امین، کاربرد رنگ در ارگونومی، انتشارات حس برتر، تهران، صفحه 56، 1379. در سال ۱۹۷۱ دکتر یوگن شورل ۱۴ در یک کلینیک در سوئیس با تحقیقاتی در زمینه رنگ درمانی تأثیر رنگ‌ها بر فشار خون، ضربان قلب، سرعت تنفس، حواس جسمانی، اثرات درد و واکنش‌های روانی مورد آزمایش قرار داد که به نتایج قابل ملاحظه ای در این زمینه دست یافت. در این آزمایش‌ها رنگ قرمز و زرد به عنوان رنگ‌های محرک و رنگ‌ سبز آرام‌کننده بود؛ بنابراین رنگ هابا طول موج بلند محرک تر از رنگ‌ها با طول موج کوتاه هستند. (بختیاری فرد، 1388: 85-88)بختیاری فرد، حمید رضا، رنگ و ارتباطات، انتشارات فخراکیا، تهران، صفحه 85-88، 1388. نکته حائز توجه به این رنگ‌ها در ارتباط با طبیعت، فرهنگ، باورهای دینی و تجربه‌های زندگی، هر یک معنایی ویژه به خود اختصاص می‌دهند. | ## بخش 3: تأثیر رنگ بر انسان | اما به هر حال تابع موقعیت‌های زمانی، مکانی و جغرافیایی بوده یا از فرهنگ، دین و آیین مردم نشات گرفته‌است. از سوی دیگر مفاهیمی که زمانی توسط افرادی برای رنگ‌ها برگزیده شده، در همان دوره اعتبار داشته‌است. (باخزری، 1345: 34-37)باخزری، ابوالمفاخر یحیی، اورادالاحباب و فصوص الآداب، جلد دوم، به کوشش ایرج افشار، انتشارات دانشگاه تهران، ص 34-37، 1345 در یک دسته‌بندی کلی رنگ‌ها به دو دسته رنگ‌های اصلی شامل زرد، آبی، قرمز و رنگ‌های فرعی نظیر سبز، بنفش، نارنجی، زرد مایل به سبز، سبز مایل به آبی، آبی مایل به سبز، بنفش مایل به قرمز و… که از ترکیب رنگ‌های دیگر به وجود می‌آیند تقسیم‌بندی شده‌است. (لوشر، 1379: 264).لوشر، ماکس، روانشناسی رنگ‌ها، ترجمه لیلا مهردادپی، انتشارات حسام، صفحه 264، 1379. باخزری، ابوالمفاخر یحیی، اورادالاحباب و فصوص الآداب، جلد دوم، به کوشش ایرج افشار، انتشارات دانشگاه تهران، ص ۳۴–۳۷، ۱۳۴۵ لوشر، ماکس، روانشناسی رنگ‌ها، ترجمه لیلا مهردادپی، انتشارات حسام، صفحه ۲۶۴، ۱۳۷۹. | ## جمع‌بندی | ولان، برید ام، تینا ساتن، هارمونی رنگ، ترجمه مریم مدنی، انتشارات مارلیک، صفحه ۱۹۴، ۱۳۸۷ موعدی، محمد امین، کاربرد رنگ در ارگونومی، انتشارات حس برتر، تهران، صفحه ۵۶، ۱۳۷۹.
موضوع مقاله: چینش باد | مخاطب: عمومی | لحن: دانشنامه‌ای | ساختار: عنوان، مقدمه، 3 بخش، جمع‌بندی | مقاله: | # چینش باد | مقدمه: به عبارتی دیگر، تغییر محلی بُردار باد یا هریک از مؤلفه‌های آن در یک راستای معین را چینش باد می‌گویند. | ## بخش 1: چینش باد | چینش باد به تغییر ناگهانی سرعت باد در یک فاصلهٔ کوتاه افقی گفته می‌شود که در این شرایط تغییر سریعی در میزان لیفت و در پی آن ارتفاع هواپیما رخ می‌دهد. همواره میزان زیادی چینش باد در جو موجود است اما برش‌های باد قوی موجب تشکیل چرخند و تگرگ می‌شود. هنگامی که برش باد ضعیف باشد توفان که قسمتی از چرخند است به صورت قائم رشد می‌کند و گرمای نهان ناشی از چگالش در هوایی که مستقیماً در بالای توفان قرار دارد آزاد می‌شود و به توسعه توفان کمک می‌کند هنگامی که برش باد قوی‌تری وجود داشته باشد توفان به صورت اریب و کج در می‌آید و گرمای نهان بر روی منطقه گسترده‌تری آزاد می‌شود. تغییرات سرعت عمودی بیشتر از نیز به عنوان چینش باد قابل توجه برای هواپیما شناخته می‌شود. | ## بخش 2: چینش باد | چینش باد در سطح پایین می‌تواند بر سرعت هواپیما در هنگام برخاستن و فرود به روش‌های فاجعه بار تأثیر بگذارد و خلبانان هواپیما آموزش دیده‌اند تا از ریزش باد ناشی از ریزپکش (کاهش باد مخالف بیش از ) جلوگیری کنند. دلایل آن شامل موارد زیر است: شدت ریزپکش می‌تواند در یک دقیقه یا کمتر دو برابر شود، بادها می‌توانند به سمت بادهای متقابل بیش از حد تغییر کنند، سرعت آستانه بقا در برخی از مراحل فعالیت در ارتفاع پایین است، چندین مورد از حوادث تاریخی ناشی از چینش باد شامل ریزپکش‌های با سرعت بوده است. چینش باد یک پدیده هواشناسی ریزمقیاس است که در فاصله بسیار کمی رخ می‌دهد، اما می‌توان آن را با پدیده‌های هواشناسی میان‌مقیاس یا مقیاس سینوپتیک مانند خط‌های تندوَزه یا جبهه‌های هوای سرد مرتبط کرد. چینش باد معمولاً در نزدیکی مراکز ریزپکش و فروپکش ناشی از جبهه‌های توفان تندری، مناطقی با بادهای سطح پایین محلی بالاتر که به آنها رودبادهای سطح پایین گفته می‌شود، در نزدیکی کوه‌ها، وارونگی تابشی که به دلیل آسمان صاف و بادهای آرام رخ می‌دهد، ساختمان‌ها، توربین‌های بادی و قایق‌های بادبانی دیده می‌شود. | ## بخش 3: چینش باد | برش باد اثرات قابل توجهی در کنترل هواپیما دارد و تنها یا یکی از دلایل بسیاری از سوانح هوایی بوده است. حرکت صوت در اتمسفر تحت تأثیر چینش باد قرار می‌گیرد، که می‌تواند جبهه موج را خم کند و باعث شود صداها در جایی قایل شنیدن باشند که معمولاً شنیده نمی‌شوند. چینش باد عمودی قوی در تروپوسفر همچنین گسترش چرخند حاره‌ای را مهار می‌کند، اما به سازماندهی توفان‌های تندری جداگانه در چرخه‌های زندگی طولانی‌تر کمک می‌کند که سپس می‌تواند هوای شدید ایجاد کند. | ## جمع‌بندی | مفهوم گرماباد توضیح می‌دهد که چگونه تفاوت سرعت باد در ارتفاعات مختلف به تفاوت دمای افقی بستگی دارد و وجود رودباد را توضیح می‌دهد.
موضوع مقاله: پیونددهنده پویا | مخاطب: عمومی | لحن: دانشنامه‌ای | ساختار: عنوان، مقدمه، 3 بخش، جمع‌بندی | مقاله: | # پیونددهنده پویا | مقدمه: سیستم‌های عامل بر پایهٔ یونیکس در بسیاری از سیستم‌های عامل بر پایهٔ یونیکس (به انگلیسی: Unix) کتابخانه‌های اشتراکی کاملاً مانند برنامه‌های اجرایی عادی هستند. | ## بخش 1: پیونددهنده پویا | استفاده از این کتابخانه‌های اجرایی در یک برنامه باعث می‌شود کتابخانهٔ اشتراکی مورد استفاده قبل از بارگذاری برنامهٔ اصلی در فضای حافظهٔ برنامه قرار گیرد، سپس برنامهٔ اصلی بارگذاری شده، ارجاع‌های انجام شده در آن به کتابخانه‌های اشتراکی آدرس‌دهی می‌شوند و در نهایت اجرای برنامهٔ اصلی شروع می‌شود. اگر بنابر علتی بارگذاری کتابخانهٔ اشتراکی موفقیت‌آمیز نباشد، روال اجرای برنامهٔ اصلی با شکست روبه‌رو خواهد شد. وظیفهٔ بارگذاری رویه‌های کتابخانه‌های اشتراکی و برنامهٔ اصلی در فضای آدرس دهی برنامه و در نهایت شروع روال اجرا بر عهدهٔ پیونددهندهٔ پویا است. | ## بخش 2: پیونددهنده پویا | در سیستم‌های عامل لینوکس (به انگلیسی: Linux) فایل‌های کتابخانه‌های اجرایی اشتراکی از پسوند SO استفاده می‌کنند. به این منظور آدرس فایل اجرایی دودویی این پیونددهنده در فضای آدرس دهی پردازه قرار داده می‌شود. فایل‌های کتابخانه‌های اشتراکی در این سیستم‌های عامل از پسوند DYLIB استفاده می‌کنند. | ## بخش 3: پیونددهنده پویا | برنامهٔ اجرایی در این سیستم‌های عامل می‌تواند حین اجرای پیوند دهنده یا حین اجرای خود با پیونددهندهٔ پویا تعامل داشته باشد. | ## جمع‌بندی | پیونددهندهٔ پویای اپل در سیستم‌عامل macOS یک پیونده‌دهندهٔ متن باز است که از طریق پروژهٔ متن باز اپل در دسترس عموم قرار دارد.
موضوع مقاله: ان ال | مخاطب: عمومی | لحن: دانشنامه‌ای | ساختار: عنوان، مقدمه، 3 بخش، جمع‌بندی | مقاله: | # ان ال | مقدمه: در نظریه پیچیدگی محاسباتی اِن‌اِل (NL) به کلاس پیچیدگی مسائلی از مسائل تصمیم‌گیری گفته می‌شود که توسط ماشین تورینگ غیرقطعی و با حافظه لگاریتمی نسبت به اندازه ورودی، قابل حل هستند. | ## بخش 1: ان ال | NL تعمیمی از مسائل کلاس اِل است که در مسائل کلاس L مسائلی قرار دارند که با پیچیدگی حافظه لگاریتمی نسبت به اندازه ورودی بر روی ماشین تورینگ قطعی قابل حل هستند. این در حالی است که رابطه NL با برخی دیگر از کلاس‌ها همچنان به عنوان بعضی از مهم‌ترین مسائل حل نشده در نظریه پیچیدگی مطرح می‌شوند. ماشین تورینگ مورد بررسی در مسائل پیچیدگی فضا به کمک تعریف اصلی ماشین تورینگ ساده که تنها دارای یک نوار است، مسائل پیچیدگی فضای لگاریتمی قابل بحث نیستند زیرا اندازه خود ورودی به صورت بدیهی از مرتبه است و استفاده از حافظه از مرتبه بی‌معنی خواهد بود. در این نوع ماشین تورینگ، دو نوار وجود دارد: نوار فقط-خواندنی که روی آن ورودی قرار داده شده‌است و این نوار یک سر دارد که آزادانه روی آن می‌تواند حرکت کند ولی خود نوار غیرقابل تغییر است. نوار دوم هم که نوار خواندن-نوشتن است مانند ماشین تورینگ عادی یک سر دارد و قابلیت خواندن و نوشتن را فراهم می‌کند. | ## بخش 2: ان ال | با توجه به اینکه بر روی نوار فقط-خواندنی امکان علامت‌گذاری خانه‌های آن و به تبع آن تشخیص دو انتهای چپ و راست نوار وجود ندارد، فرض می‌کنیم که قابلیت تشخیص رسیدن به دو سر نوار برای ماشین تورینگ وجود دارد. حال به کمک این تعریف از ماشین تورینگ، پیچیدگی فضا برابر با تعداد خانه‌های خوانده شده بر روی نوار خواندن-نوشتن تعریف می‌شود و در نتیجه با قرار گرفتن ورودی بر روی نوار فقط-خواندنی، در مسائل کلاس حجمی لگاریتمی، مستقل از نوار ورودی، می‌توان از لگاریتم اندازه ورودی از نوار خواندن-نوشتن استفاده کرد. مسائل اِن‌اِل-کامل مبدّل فضای لگاریتمی یک مبدّل فضای لگاریتمی یک ماشین تورینگ با تعریف اشاره شده در بالا است که در نوار خواندن-نوشتن آن می‌تواند تنها شامل نماد باشد. مبدل فضای لگاریتمی M تابع است و هنگامی که رشته ورودی روی نوار فقط-خواندن باشد، رشته باقی‌مانده بر روی نوار خواندن-نوشتن در پایان است. زبان به زبان با فضای لگاریتمی قابل کاهش است اگر یک نگاشت قابل کاهش از به به وسیله یک تابع قابل محاسبه در فضای لگاریتمی مانند وجود داشته باشد. | ## بخش 3: ان ال | نمادگذاری جمله بالا به صورت زیر است: تعریف مسائل اِن‌اِل-کامل زبان یک زبان NL-Complete است اگر و هر زبان مانند که در NL است، با فضای لگاریتمی قابل کاهش به باشد. در مسئله اتصال-ST به عنوان ورودی یک گراف و دو راس S و T داده می‌شوند و مسئله تصمیم‌گیری وجود داشتن یک مسیر از S به T است. در مسئله 2-ارضاپذیری هم ارضاپذیر بودن یک عبارت منطقی حاصل AND منطقی بین چند عبارت که خود این عبارات نیز از OR شدن 2 متغیر تشکیل شده اند، سؤال می‌شود. نمونه‌ای از عبارات منطقی به شکل زیر است: روابط اِن‌اِل با سایر مجموعه‌ها به دلیل وجود الگوریتم چندجمله‌ای برای حل مسئله 2-ارضاپذیری و با توجه به NL-Complete بودن آن، مجموعه P شامل مجموعه NL می‌شود. | ## جمع‌بندی | طبق قضیه ساویچ هر الگوریتمی را که به صورت غیرقطعی با حافظه معینی پیاده‌سازی شده باشد، می‌توان با حداکثر مربع آن حجم از حافظه به صورت قطعی پیاده‌سازی کرد.
موضوع مقاله: مسئله تناظر پست | مخاطب: عمومی | لحن: دانشنامه‌ای | ساختار: عنوان، مقدمه، 3 بخش، جمع‌بندی | مقاله: | # مسئله تناظر پست | مقدمه: با نگاشت این مسئله بر روی مسائل تصمیم‌ناپذیر دیگر می‌توانیم تصمیم‌ناپذیری آن‌ها را نیز اثبات کنیم (مانند تصمیم‌ناپذیری ماشین‌های تورینگ). | ## بخش 1: مسئله تناظر پست | علاوه بر این که یکی از دلایل اهمیت این مسئله اثبات دیگر مسائل تصمیم‌ناپذیر به‌وسیلهٔ آن است، می‌توان به این موضوع نیز اشاره نمود که درک و اثبات این مسئله بسیار ساده‌تر از دیگر مسائل تصمیم‌ناپذیر، مانند مسالهٔ توقف در ماشین تورینگ است. هر نمونه از این مسئله شامل دو لیست از رشته‌هایی است که بر روی الفبای تعریف شده‌اند. | ## بخش 2: مسئله تناظر پست | فرض کنید این دو لیست و نام دارند که برای یک مقدار این‌گونه تعریف می‌شوند: برای هر جفت را یک جفت تناظر می‌گویند. جواب مسئلهٔ تناظر پست را نیز این‌گونه تعریف می‌کنیم: برای یک نمونه از مسئله جواب وجود دارد اگر دنباله‌ای از اعداد صحیح مانند ، ، … و وجود داشته باشد که شرط زیر را ارضاء کند: پس به‌طور کلی مسئلهٔ تناظر پست این‌گونه تعریف می‌شود: «آیا برای یک نمونه از مسئلهٔ تناظر پست جوابی وجود دارد یا خیر؟» مثال فرض کنید و دو لیست و را این‌گونه در نظر بگیرید: list A list B aaaa۱abaaaab۲abb۳ یک جواب برای این نمونه با ، این‌گونه است: ؛ زیرا در این صورت: که این دو شرط را ارضاء می‌کنند. | ## بخش 3: مسئله تناظر پست | اثبات تصمیم ناپذیری مسئلهٔ تناظر پست ایدهٔ کلی برای اثبات تصمیم ناپذیری مسئلهٔ تناظر پست این است که آن را بر روی یک مسئلهٔ تصمیم ناپذیر معروف دیگری نگاشت کنیم و بهترین گزینه مسالهٔ توقف است.Sipser, Michael. | ## جمع‌بندی | این نگاشت را این‌گونه در نظر بگیرید: «یک مسئلهٔ تناظر پست می‌تواند یک ماشین تورینگ دلخواه را با یک ورودی خاص اجرا کند.
موضوع مقاله: وابستگی داده | مخاطب: عمومی | لحن: دانشنامه‌ای | ساختار: عنوان، مقدمه، 3 بخش، جمع‌بندی | مقاله: | # وابستگی داده | مقدمه: برای مثال، یک دستور تا زمانی که داده‌­های مورد نیازش آماده و در دسترس نباشند نمی‌­تواند اجرا شود. | ## بخش 1: وابستگی داده | در علوم رایانه، وابستگی داده به موقعیتی گفته می‌شود که یک دستور به داده‌های دستورها قبل و یا بعد از خود نیاز دارد. به‌طور کلی، اگر اجرای هم‌زمان دو دستور ممکن نباشد و اجرای آن‌ها باید به صورت متوالی انجام شود، آن‌ها را وابسته می‌گوییم. وابستگی داده دو دستور و را در نظر می‌گیریم که دستور در جایی بعد از دستور قرار دارد. و را به ترتیب مجموعه خانه‌هایی از حافظه که از آن‌ها می‌خواند و مجموعه خانه‌هایی از حافظه که در آن‌ها می‌نویسد، تعریف می‌کنیم. مثال زیر را با فرض اینکه مقدار x و y از قبل محاسبه شده‌است در نظر بگیرید:a = x + y; b = 2 * a;در این مثال، دستور دوم به دستور اول وابستگی جریان دارد؛ چرا که از مقدار تولیدی در دستور اول استفاده می‌کند. به این ترتیب در این مثال نمی‌توان دستورها اول و دوم را به صورت هم زمان اجرا کرد. | ## بخش 2: وابستگی داده | مثال زیر را با فرض اینکه مقدار x و y و z از قبل محاسبه شده‌است در نظر بگیرید:a = x + y; b = 2 * a; a = z + 1;در این مثال دستور دوم به دستور سوم پاد وابستگی دارد. توجه داریم که ترتیب این دستورها نمی‌تواند عوض شود؛ چرا که مقدار نهایی متغیر b را تغییر می‌دهد. همچنین اجرای هم‌زمان دستورها نیز به دلیل احتمال بروز خطا در مقدار نهایی امکان‌پذیر نیست. پاد وابستگی مثالی از وابستگی نام است؛ به این معنا که وابستگی می‌تواند با تغییر نام برخی متغیرها برطرف شود. برای مثال کد زیر را برای رفع وابستگی مثال قبل در نظر بگیرید:a2 = x + y; b = 2 * a2; a = z + 1;به ابن ترتیب با تغییر نام متغیر a به متغیر جدید a2 در دستورها پیش از بازنویسی آن، پاد وابستگی میان دستورها دوم و سوم از بین رفته‌است و اکنون اجرای هم‌زمان آن‌ها امکان‌پذیر است. مثال زیر را در نظر بگیرید:b = 7; a = 2 * b; b = 11;در این مثال دستور سوم به دستور اول وابستگی خروجی دارد. | ## بخش 3: وابستگی داده | مثال زیر را در نظر بگیرید:b = 7; a = 2 * b; c = b;در این مثال دستور سوم به دستور دوم وابستگی ورودی دارد. توجه داریم که وابستگی ورودی در عمل مشکلی در اجرای هم‌زمان دستورها ایجاد نمی‌کند. در نتیجه در بسیاری از موارد می‌توان با تغییر نام برخی از متغیرها این وابستگی را از بین برد. وابستگی کنترل اگر نتیجه دستور مشخص‌کننده اجرا و یا عدم اجرای دستور باشد، آنگاه دستور به دستور وابستگی کنترل دارد. مثال زیر را در نظر بگیرید:if (a == b) { c = 2 * a; a = a + b; } b = a + b;در این مثال نتیجه دستور اول مشخص می‌کند که دستورها سه و چهار اجرا می‌شوند یا خیر. گراف جریان کنترل گرافی جهت‌دار است که مسیرهای مختلفی که اجرای برنامه ممکن است بپیماید را نشان می‌دهد. | ## جمع‌بندی | در صورتی که امکان انتقال مستقیم از تکه برنامه i به تکه برنامه j وجود داشته‌باشد، یالی از راس i به راس j خواهیم داشت.
موضوع مقاله: مسئله ارتفاع ستاره | مخاطب: عمومی | لحن: دانشنامه‌ای | ساختار: عنوان، مقدمه، 3 بخش، جمع‌بندی | مقاله: | # مسئله ارتفاع ستاره | مقدمه: مسئلهٔ ارتفاع ستاره که توسط Eggan Lawrence C مطرح شده‌است، مسئله‌ای در تئوری زبان صوری است که سعی در پاسخ به این پرسش دارد که آیا می‌توان همهٔ زبان منظم را به کمک عبارات منظمی که ارتفاع ستارهٔ محدودی دارند بیان کرد؟ | ## بخش 1: مسئله ارتفاع ستاره | ارتفاع ستارهٔ یک عبارت منظم، بیشینهٔ عمق ستاره‌های تو در تویی است که در آن عبارت وجود دارد. به‌طور مشخص‌تر، این مسئله بیان می‌کند که آیا همیشه عمق تو در توی یک کافی است و امکان‌پذیر است که همهٔ زبان‌های منظم را با عبارات منظم به عمق یک نشان داد؟ اگر پاسخ این سؤال منفی است، آیا الگوریتمی وجود دارد که عمق مورد نیاز را مشخص کند؟ ساخت این عبارات به صورت بازگشتی است و به این ترتیب صورت می‌گیرد که عبارت ، از کنار هم قرار دادن دو نسخهٔ و تغییر نام نسخهٔ دوم با نام‌های جدید و پس از آن اضافه کردن یک نشانهٔ جدید در انتها و اضافه کردن پرانتز و ستاره در اطراف عبارت ساخته شده تا اینجا، صورت می‌گیرد. | ## بخش 2: مسئله ارتفاع ستاره | Eggan ثابت کرد که هیچ عبارت منظمی با ارتفاع ستارهٔ کمتر از n وجود ندارد که معادل با باشد [۱]. هرچند مثال ارائه شده توسط او از الفبای بزرگی استفاده می‌کند که برای زبانی با ارتفاع ستارهٔ n، اندازهٔ آن 2n-۱ است. به همین دلیل، سؤال دیگری که مطرح کرد این بود که آیا مثال‌هایی روی الفبای دودویی وجود دارد که به این شکل باشند؟ در هر گام به این صورت ساخته می‌شود که ابتدا به تعداد 2n نشانهٔ اول و سپس و پس از آن به تعداد 2n نشانهٔ دوم و در انتها نیز قرار می‌گیرد. | ## بخش 3: مسئله ارتفاع ستاره | سؤال مطرح شدهٔ دوم، پاسخ به نسبت پیچیده‌تری نسبت به سؤال اول دارد و برای حدود دو دهه به عنوان یکی از مسائل معروف حل نشدهٔ حوزهٔ زبان‌های صوری شناخته می‌شد [2]. اما این الگوریتم عملی نیست و به محاسباتی می‌انجامد که حتی برای مثال‌های کوچک نیز امکان‌پذیر نیست. | ## جمع‌بندی | الگوریتم بهینه‌تری توسط Kirsten در سال ۲۰۰۵ ارائه شد، اما حتی این الگوریتم هم فاصلهٔ زیادی با آنچه که قابل انجام است، دارد [۵].