علوم نظری رایانه

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

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

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

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

مقاله اصلی: نظریه محاسبات

تئوری محاسبات زمینهٔ وسیعی است که امکان و کارایی حل مسائل گوناگون به وسیلهٔ مدل‌های محاسباتی، با استفاده از الگوریتم‌ها را مورد مطالعه قرار می‌دهد. که به بررسی محاسبه‌پذیری و بررسی پیچیدگی محاسبه تقسیم می‌شود.