مرجع دانلود پاورپوینت های درسی

حجم فایل : 94.3 KB
نوع فایل : پاور پوینت
تعداد اسلاید ها : 25
تئوری ساختی با قابليت تعيين پيچيدگی محاسباتی مقدمه تئوری پيچيدگی
ايجاد زيربنای رياضياتی لازم برای محاسبات کارآ
تئوری اثبات
معرفی سيستم‌های اثبات گوناگون
فرماليزه نمودن يک منطق
بررسی توانايی‌ها و محدوديت‌ها
قابليت بيان يک قضيه
قابليت اثبات يک قضيه مقدمه (ادامه) پيچيدگی اثبات
حاصل مواجهه تئوری پيچيدگی و تئوری اثبات
بررسی سيستم‌های اثبات گوناگون
تعيين حد بالا و پايين برای کوچک‌ترين اثبات‌ها
تعريف منطق‌هايی برای مشخص‌ساختن کلاس‌های پيچيدگی
نمونه‌هايی از منطق‌های کلاسيک مانند و PV
نمونه‌ای از منطق‌های شهودگرا مانند IPV مقدمه (ادامه) منطق ساختی
مهم‌ترين منطق شهودگرای موجود
اثبات معادل است با برنامه
تئوری انواع
از مهم‌ترين فرماليسم‌های موجود برای منطق ساختی
فقط قابليت بيان توابع کامل
نسخه‌هايی با قابليت بيان توابع جزيی موجودند
همه کلاس‌های پيچيدگی معروف در مجموعه توابع کامل هستند مقدمه (ادامه) تئوری انواع
قابليت بيان توصيف يک برنامه يا مساله

قابليت بيان اثبات يک توصيف
از طريق قوانين معرفی و حذف عملگرها و استقرا
وجود نرم‌افزارهای گوناگون برای کار با تئوری انواع
مانند Nuprl
قابليت تعبير توسط تئوری مارتين-لوف هدف پايان‌نامه تعريف برخی کلاس‌های پيچيدگی در تئوری انواع
ارائه اصول و قوانين استنتاج به نحوی که
اثبات يک قضيه با اين اصول و قوانين معادل است با بودن در کلاس پيچيدگی مربوطه
برخورداری از خصوصيات مهم تئوری انواع
قابليت خوانده‌شدن به صورت انواع
خصوصيت نوع به جای گزاره
خصوصيت نوع به جای برنامه
خصوصيت نوع به جای مجموعه مزايا عدم نياز به اثبات بودن در يک کلاس پيچيدگی
وجود اثبات برای يک مساله نشانگر داشتن راه‌حلی در کلاس پيچيدگی مربوطه است
اثبات عدم‌اثبات‌پذيری در اين تئوری نشان‌گر عدم وجود در يک کلاس پيچيدگی است
استفاده از اثبات‌گرهای خودکار کارهای پيشين مشخص‌کردن کلاس‌های پيچيدگی در
مدل‌های محدود
توصيف مساله‌ها
اثبات مساله‌ها
پياده‌سازی مساله‌ها مدل‌های محدود مدل‌های محدود
کاربرد بسيار در مسائل مهندسی و رياضی
مدل نمودن بسياری از پديده‌ها در قالب گراف‌ها و ديگر مدل‌های محدود
مدل‌های محدود و کلاس‌های پيچيدگی
سختی توصيف يک مدل
سختی توصيف يک خصوصيت در يک مدل
سختی بررسی يک خصوصيت برای يک مدل توصيف مساله‌ها توصيف مدلی است معمولا منطقی شامل
توصيف ورودی‌های مساله و پيش‌شرط‌ها
توصيف خروجی‌های مساله
رابطه ورودی‌ها و خروجی‌ها


زبان‌های توصيف مانند: منطق‌های مرتبه اول و دوم، تئوری انواع، زبان B توصيف مساله‌ها (ادامه) مبحث پيچيدگی در توصيف
محدودشده زبان توصيفی
قابليت بيان توصيف يک برنامه معادل است...