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

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

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

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

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