آموزش تئوری محاسبات – p2 – مروری سریع بر بخش اول

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

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

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