دوستان عزیز لطفا توی جواب این سوالات بهم کمک کنید
1- آیا آنالیز الگوریتم ها روی یک مدل انتزاعی انجام میشه؟چرا؟
2-رابطه ی تز تورینگ با طراحی الگوریتم چیه؟
3- آیا معادل بودن ماشین تورینگ قطعی و غیر قطعی دلیلی بر برابری p=np هست؟چرا؟
ممنون
در پاسخ به سوال 2 فکرکنم:
الگوریتم وتز تورینگ هر دو هیچ یا چندین کمیت ورودی دارند ،هردو حتما خروجی دارند (هرچند به صورت مفهومی)، هردو قطعیت دارند ولی اگر ماشین تورینگ در حلقه بی پایان قرار بگیرد الگوریتمی جهت پذیرش ورودی یا مسئله ندارند.
امیدوارم به پاسخ سوالت رسیده باشی،موفق باشی
جواب سوال اول :
این رو میشه اینجوری استدلال کرد که زمان اجرای الگوریتم ها وابسته به موارد متفاوتی است مثلا وابسته به کامپایلر ومعماری ماشین واندازه ورودی حالا سوالی که پیش میاد اینه که چطور میشه اجراهای مختلف الگوریتم ها رو باهم مقایسه کرد به عبارتی یعنی بر چه معیاری میشه گفت که یه الگوریتم از یه الگوریتم دیگه سریعتره یانه برای همین یه مفهومی بنام نماد های مجانبی تعریف میشه که این نمادها الگوریتم ها رو مستقل از ماشین و کامپایلر و.. ارزیابی میکنن حالا اگه دقیق بشیم اندازه های ورودی هم یه عدد ثابت نیست یعنی که مثلا n رو به عنوان ورودی الگوریتم هیچوقت ۱۰۰ یا ۲۰۰ یا ۱۰۰۰۰۰۰۰۰۰۰۰۰۰ نمی گیری بلکه میگید برای n های بزرگ در واقع حالت حدی مسئله میشه که n به سمت بینهایت میل کنه شما الگوریتم هاتون رو ارزیابی می کنید بنابراین با تمام این تفاسیر میشه این نتیجه رو گرفت که ارزیابی الگوریتم ها بخاطر وابستگی به مواردی که گفتم روی یه مدل انتزاعی بررسی میشه . منبع CLRS
(18 اردیبهشت 1391 01:04 ق.ظ)لهمشد نوشته شده توسط: [ -> ]جواب سوال اول :
این رو میشه اینجوری استدلال کرد که زمان اجرای الگوریتم ها وابسته به موارد متفاوتی است مثلا وابسته به کامپایلر ومعماری ماشین واندازه ورودی حالا سوالی که پیش میاد اینه که چطور میشه اجراهای مختلف الگوریتم ها رو باهم مقایسه کرد به عبارتی یعنی بر چه معیاری میشه گفت که یه الگوریتم از یه الگوریتم دیگه سریعتره یانه برای همین یه مفهومی بنام نماد های مجانبی تعریف میشه که این نمادها الگوریتم ها رو مستقل از ماشین و کامپایلر و.. ارزیابی میکنن حالا اگه دقیق بشیم اندازه های ورودی هم یه عدد ثابت نیست یعنی که مثلا n رو به عنوان ورودی الگوریتم هیچوقت ۱۰۰ یا ۲۰۰ یا ۱۰۰۰۰۰۰۰۰۰۰۰۰۰ نمی گیری بلکه میگید برای n های بزرگ در واقع حالت حدی مسئله میشه که n به سمت بینهایت میل کنه شما الگوریتم هاتون رو ارزیابی می کنید بنابراین با تمام این تفاسیر میشه این نتیجه رو گرفت که ارزیابی الگوریتم ها بخاطر وابستگی به مواردی که گفتم روی یه مدل انتزاعی بررسی میشه . منبع CLRS
ممنونم دوست عزیز
(16 اردیبهشت 1391 11:14 ب.ظ)Nici نوشته شده توسط: [ -> ]در پاسخ به سوال ۲ فکرکنم:
الگوریتم وتز تورینگ هر دو هیچ یا چندین کمیت ورودی دارند ،هردو حتما خروجی دارند (هرچند به صورت مفهومی)، هردو قطعیت دارند ولی اگر ماشین تورینگ در حلقه بی پایان قرار بگیرد الگوریتمی جهت پذیرش ورودی یا مسئله ندارند.
امیدوارم به پاسخ سوالت رسیده باشی،موفق باشی
تشکر و بسیار ممنون