آخرین به روزرسانی:

نظریه‌ی علوم‌کامپیوتر - کارشناسی ارشد علوم کامپیوتر

ترم اول سال تحصیلی ۹۶-۱۳۹۵

اخبار درس

۲۵ مهر ۹۵

با سلام. فهرست ارائه‌ها در حال تکمیل است. لیست در حال تکمیل را می‌توانید در اینجا ببینید.

۱۹ شهریور ۹۵

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

اطلاعات عمومی

تاریخ‌های مهم
  • دوشنبه ۱۰ آبان ۱۳۹۵ - میان‌ترم اول - فصل‌های ۳ تا ۵ از [S12]
  • شنبه ۶ آذر ۱۳۹۵ - میان‌ترم دوم - فصل‌های ۲ تا ۶ از [DSW94]
  • دو‌شنبه؛ ۶ دی ۱۳۹۵ - میان‌ترم سوم - فصل‌های ۶ تا ۹ از [S12]
  • آزمون پایان ترم - طبق اعلام سیستم گلستان
سرفصل درس
بخش ۱: نظریه‌ی محاسبه‌پذیری شامل نظریه‌ی چرچ-تورینگ، ماشین‌های تورینگ و انواع آن، تعریف الگوریتم و مسائل هیلبرت، تصمیم‌پذیری، زبان‌های تصمیم‌پذیر، تصمیم‌ناپذیری، قطری سازی، کاهش‌پذیری، مسائل تصمیم‌ناپذیر در نظریه‌ی زبان، توابع محاسبه‌پذیر، قضیه‌ی بازگشتی، تصمیم‌پذیری نظریه‌های منطق، کاهش‌پذیری تورینگ، تعریف اطلاعات، رشته‌های غیرقابل فشردن و تصادفی، اعداد گودل، فضای هربراند، قضایای مختلف در نظریه‌ی بازگشت.
بخش ۲: نظریه‌ی پیچیدگی شامل پیچیدگی زمانی، رده‌های P و NP، NP-کامل بودن و برخی مسائل NP-کامل، پیچیدگی حافظه، قضیه Savitch، رده‌ی PSPACE، PSPACE-کامل بودن، رده‌های L و NL، NL-کامل بودن، برابری NL و coNL، رامش ناپذیری، نسبی‌سازی، پیچیدگی مداری.
بخش ۳: یکی از مباحث زیر به انتخاب دانشجویان:
  • مدل‌ها و الگوریتم‌های پردازش داده‌های حجیم مبتنی بر مرجع:

    Leskovec, Jure, Anand Rajaraman, and Jeffrey David Ullman. Mining of massive datasets. Cambridge University Press, 2014.

  • نظریه‌ی یادگیری محاسباتی مبتنی بر مرجع:

    Kearns, Michael J., and Umesh Virkumar Vazirani. An introduction to computational learning theory. MIT press, 1994.

  • الگوریتم‌های پارامتر ثابت مبتنی بر مرجع:

    Cygan, Marek, et al. Parameterized algorithms. Switzerland: Springer, 2015.
مراجع
  • [S12] Sipser, Michael. Introduction to the Theory of Computation, 3rd edition. Cengage Learning, 2012.
  • [DSW94] Davis, Martin, Ron Sigal, and Elaine J. Weyuker. Computability, Complexity, and Languages: Fundamentals of Theoretical Computer Science. Newnes, 1994.
از مرجع [S12]، فصل‌های ۳ الی ۱۰ و از مرجع [DSW94]، فصل‌های ۲ الی ۶ مورد نیاز خواهند بود.
گزارش پژوهشی
به منظور آشنایی با کاربردهای این درس در مرزهای دانش و یا آشنایی با مباحثی که در طی درس به آن‌ها پرداخته نشده است؛ هر دانشجو لازم است تا یک گزارش پژوهشی را ارائه نماید. علاوه بر گزارش کتبی، لازم است در سمیناری به مدت ۱۵ الی ۲۰ دقیقه، موضوع مورد پژوهش به کلاس ارائه شود. موضوعات می‌توانند توسط دانشجو پیشنهاد شده و یا از لیست موضوعات در صفحه‌ی درسی انتخاب شوند (شیوه‌ی انتخاب به صورت صَف (First in, First served) است). لیستی از مقالات پیشنهادی جهت استفاده پس از انتخاب بخش سوم درس توسط دانشجویان؛ در سایت درسی قرار خواهند گرفت.
پیوندها
تحویل به موقع تمرین‌ها
در این درس حداقل ۱۲ سری تمرین خواهیم داشت و لازم است تا تمرین‌ها در موعد مقرر، تحویل شوند. به ازای هر روز تاخیر در تحویل تمرین، %۱۰ نمره کسر خواهد شد و پس از گذشت 72 ساعت از موعد تحویل، %۱۰۰ نمره کسر می‌گردد.

جلسات درس

جلسه‌ی اول - ۲۷ شهریور ۱۳۹۵
جلسه‌ی دوم - ۲۹ شهریور ۱۳۹۵
جلسه‌ی سوم - ۳ مهر ۱۳۹۵
جلسه‌ی چهارم - ۵ مهر ۱۳۹۵
جلسه‌ی پنجم - ۱۰ مهر ۱۳۹۵
جلسه‌ی ششم - ۱۲ مهر ۱۳۹۵
تمرین‌ها
  • تمرین‌های مربوط به فصل ۴:
    Exercises: 4.4, 4.5, 4.8
    Problems: 4.10, 4.12, 4.18, 4.23
جلسه‌ی هفتم - ۱۷ مهر ۱۳۹۵
جلسه‌ی هشتم - ۲۴ مهر ۱۳۹۵
برنامه‌ی ارائه‌ها
  • برنامه‌ی ارائه‌های شما به شرح زیر است:
    شماره‌ی فصل ارائه‌دهنده
    ۲ خانم ساریخانی
    ۳ خانم عبداللهی
    ۴ خانم احمدی
    ۵
    ۶ آقای صمدی
    ۷ آقای عبدفرحانی
    ۸ آقای آهنی
    ۹ آقای ملک‌زاده
    ۱۰
    ۱۱ خانم محمدی
    ۱۲
تمرین‌ها
  • تمرین‌های مربوط به فصل ۵:
    Exercises: 5.1, 5.5, 5.6, 5.7
    Problems: 5.13, 5.26, 5.28, 5.30, 5.36
جلسه‌ی نهم - ۲۵ مهر ۱۳۹۵ - جبرانی دوشنبه؛ ۱۹ مهر ۹۵
جلسه‌ی دهم - ۲۶ مهر ۱۳۹۵
جلسه‌ی یازدهم - ۱ آبان ۱۳۹۵
جلسه‌ی دوازدهم - ۳ آبان ۱۳۹۵
جلسه‌ی سیزدهم - ۸ آبان ۱۳۹۵
    حل مساله‌های مختلف از فصل‌های ۳ الی ۵ مرجع [S12]
جلسه‌ی چهاردهم - ۱۰ آبان ۱۳۹۵
جلسه‌ی پانزدهم - ۱۵ آبان ۱۳۹۵
جلسه‌ی شانزدهم - ۱۷ آبان ۱۳۹۵
  • اسلایدها
  • مشاهده/دریافت فیلم - متاسفانه ویدئوی این جلسه بر اثر اشتباه ذخیره نشده است.
جلسه‌ی هفدهم - ۲۲ آبان ۱۳۹۵
جلسه‌ی هجدهم - ۲۴ آبان ۱۳۹۵
جلسه‌ی نوزدهم - ۲۹ آبان ۱۳۹۵
جلسه‌ی بیستم - ۱ آذر ۱۳۹۵
جلسه‌ی بیست و یکم - ۶ آذر ۱۳۹۵

آزمون‌ها

...

نمرات

ردیف عنوان نمره شرح
۱ تمرین ۵ شامل حداقل ۱۲ سری تمرین
۲ پروژه‌ی پژوهشی گزارش کتبی ۳
سمینار ۲
۳ آزمون‌های کتبی میان‌ترم اول ۲ ۱۰ شنبه ۱ آبان ۱۳۹۵ (فصل‌های ۳ تا ۵ از [S12])
میان‌ترم دوم ۲ شنبه ۶ آذر ۱۳۹۵ (فصل‌های ۲ تا ۶ از [DSW94])
میان‌ترم سوم ۲ دوشنبه، ۶ دی ۱۳۹۵ (فصل‌های ۶ تا ۹ از [S12])
پایان ترم ۴ کل مباحث
۳ تلاش بیشتر +۲
جمع نمرات ۲۰ + ۲

نمرات تا این لحظه

وضعیت کلاسی شما تا این لحظه در اینجا قابل رویت است.

سوالات رایج

...