نمرات آزمون نهایی پایانی

[Ali Sharifi Zarchi]

سلام

نمره های آزمون نهایی پایانی بر روی سایت قرار گرفت.

نحوه نمره دهی بدین شرح است (برای نوشتن سودوکد هر سوال ۰.۵ نمره اضافه در نظر گرفته شده)

سوال ۱ (بازی قلعه ها) 

قسمت الف:‌

بیان روش درست قراردهی قلعه ها (سطر به سطر یا ستون به ستون) - نمره 0.25

یافتن جواب (سقف m/n) - نمره 0.25

قسمت ب:

استفاده از الگوریتم شار بیشینه یا تطابق بیشینه 0.25
ساختار درست گراف و تحلیل 0.25

سوال ۲ (جایگشت تصادفی)

قسمت الف:

الگوریتم  درست 0.25

زمان اجرای خطی 0.25

قسمت ب:

ارایه Branch مناسب 0.25
ارایه Bound مناسب 0.25

سوال ۳ (فایلهای صوتی)

قسمت الف)

استفاده از روش با زمان n^2 به همراه سودوکد 0.25 و توضیح دقیق نحوه استفاده از FFT معادل 0.5 نمره دارد.

قسمت ب)

ارایه هر یک از سه ویژگی 0.25 

سوال ۴ (Half-Path)

قسمت الف)

نمایش NP بودن مساله با بیان حالت تصمیم گیری، آزمون Certificate در زمان چند جمله ای با کنترل تعداد راسها و تکراری نبودن آنها و وجود یال بین راسهای متوالی 0.5

قسمت ب)

اجرای درست Reduction از مساله Hamiltonian به مساله Half-Path (مثلا با افزودن n راس ایزوله) 0.5 نمره

سوال ۵ (شار بیشینه راسی)

تغییر ساختار گراف با افزودن یال به جای راس 0.25

تعیین موقعیت درست یالهای ورودی و خروجی 0.25

تعیین شار درست بر روی یالها 0.25

تحلیل الگوریتم 0.25

سوال ۶ (قورباغه و مگس ها)

ارایه الگوریتم با زمان اجرای تا سقف n^2 معادل 0.25  

ارایه الگوریتم با زمان اجرای تا سقف n lg n  معادل 0.25 نمره اضافه بر حالت قبل

ارایه ایده ترتیب اکیدا صعودی در ماتریس Dynamic معادل 0.25 نمره اضافه بر حالت قبل

ارایه الگوریتم با زمان اجرای n معادل 0.25 نمره اضافه بر حالت قبل 

ارایه سودوکد با زمان اجرای n^2 معادل 0.25 و زمان اجرای n معادل 0.5  نمره اضافه

نمرات میان ترم ها و همچنین زمان رویت برگه ها و اعتراض نیز به زودی اعلام خواهند شد.

با احترام

علی شریفی

[Reza Moradi]

سلام آقاي شريفي
نمره اينجانب در ليست نيست
شماره دانشجويي: 88209703