زمان کنونی: ۱۶ آبان ۱۴۰۳, ۰۷:۲۱ ق.ظ مهمان گرامی به انجمن مانشت خوش آمدید. برای استفاده از تمامی امکانات انجمن می‌توانید عضو شوید.
گزینه‌های شما (ورودثبت نام)

[طراحی الگوریتم] شناخت NP و تمایزات بین NP-hard و NP-Complete

ارسال: #۱۶
۱۱ اسفند ۱۳۹۰, ۱۱:۴۸ ب.ظ
RE: [طراحی الگوریتم] شناخت NP و تمایزات بین NP-hard و NP-Complete
(۰۴ دى ۱۳۹۰ ۱۲:۳۷ ق.ظ)Nargeskl نوشته شده توسط:  سلام
میشه به من کمک کنید
لطفایه نمونه مساله از Np-Hard برام مثال بزنید
با اجازه اساتید:
مساله توقف پذیری (halting problem ) یه مثالی از این نوع هستش .که هدف نوشتن برنامه اجرایی هستش که بتونه بگه یه برنامه دیگه خاتمه پیدا میکنه یا خیر.

چه دوستی پاکی دارند کفشها...
هر کدام که گم شوند....
آن یکی را آواره خودش میکند
یافتن تمامی ارسال‌های این کاربر
نقل قول این ارسال در یک پاسخ
ارسال: #۱۷
۱۲ اسفند ۱۳۹۰, ۰۱:۵۲ ق.ظ (آخرین ویرایش در این ارسال: ۱۲ اسفند ۱۳۹۰ ۰۱:۵۲ ق.ظ، توسط alidata.)
[طراحی الگوریتم] شناخت NP و تمایزات بین NP-hard و NP-Complete
TSP هم جز np-hard ها محسوب میشه؟

[تصویر:  99687907715295763434.gif]
یافتن تمامی ارسال‌های این کاربر
نقل قول این ارسال در یک پاسخ
ارسال: #۱۸
۱۴ اسفند ۱۳۹۰, ۰۲:۲۵ ق.ظ
RE: [طراحی الگوریتم] شناخت NP و تمایزات بین NP-hard و NP-Complete
(۱۲ اسفند ۱۳۹۰ ۰۱:۵۲ ق.ظ)alidata نوشته شده توسط:  TSP هم جز np-hard ها محسوب میشه؟
بله .مسله فروشنده دوره گردد از جمله مسائل NP_hard بشمار میره

چه دوستی پاکی دارند کفشها...
هر کدام که گم شوند....
آن یکی را آواره خودش میکند
یافتن تمامی ارسال‌های این کاربر
نقل قول این ارسال در یک پاسخ
ارسال: #۱۹
۰۱ آبان ۱۳۹۱, ۱۲:۲۴ ق.ظ
[طراحی الگوریتم] شناخت NP و تمایزات بین NP-hard و NP-Complete
با سلام.در موردمبحث اینکه بخواهیم مسائل براساس نوع پیچیدگی(np/np-hard/np-complete)دسته بندی کنیم راهنمایی میخوام؟و چند تا مساله بهینه سازی ترکیباتی؟
یافتن تمامی ارسال‌های این کاربر
نقل قول این ارسال در یک پاسخ
ارسال: #۲۰
۰۷ آذر ۱۳۹۲, ۱۲:۰۷ ب.ظ (آخرین ویرایش در این ارسال: ۰۷ آذر ۱۳۹۲ ۱۲:۱۲ ب.ظ، توسط marmar3.)
[طراحی الگوریتم] شناخت NP و تمایزات بین NP-hard و NP-Complete
سلام
من یه سوالی داشتم
وقتی یک مسئله ایی دارای مسئله تصمیم شد میگیم اون مسئله یک NP Complete هست
حالا من از کجا متوجه بشم که آیا اون مسئله NP hard هست یا نه؟
مثالشم مثلا مسئله Partition

آقای دکتر یه سوال دیگه هم داشتم
مسئله ای رو داریم که NP hard باشه ولی NP نباشه؟؟؟؟؟؟
میشه یه مثال بزنید

کلا این مسائل رو چطوری میتونم تشخیص بدم؟؟؟؟

ازتون تشکر میکنم منو راهنمایی کنید
یافتن تمامی ارسال‌های این کاربر
نقل قول این ارسال در یک پاسخ
ارسال: #۲۱
۰۴ دى ۱۳۹۲, ۰۱:۰۳ ب.ظ
RE: [طراحی الگوریتم] شناخت NP و تمایزات بین NP-hard و NP-Complete
(۲۴ تیر ۱۳۹۰ ۱۲:۰۷ ق.ظ)admin نوشته شده توسط:  در نظریه محاسبه پذیری اگر A به B در زمان چند جمله‌ای کاهش پذیر بوده و B تصمیم ناپذیر باشد آن گاه Aنیز تصمیم ناپذیر خواهد بود.

(۲۴ تیر ۱۳۹۰ ۰۴:۲۶ ب.ظ)parimehraban نوشته شده توسط:  در نظریه محاسبه پذیری اگر A به B کاهش پذیر بوده و B تصمیم پذیر باشد آن گاه Aنیز تصمیم پذیر خواهد بود .همین طوراگر A تصمیم پذیر نبوده و به B کاهش یابد، آنگاه B نیز تصمیم پذیر نخواهد بود .

(۲۷ آذر ۱۳۹۰ ۱۱:۳۹ ب.ظ)psps1368 نوشته شده توسط:  مثلا Halting Problem یک مسئله NP-Hard است، چرا که SAT به آن در زمان چند جمله ای کاهش پیدا می کند. واضح هست که Halting Problem، یک مسئله NP نیست.

با توجه به توضیحات بالا، یه سوال دارم.
اگر A در زمان چندجمله ای به B کاهش پیدا کنه، اگرA یه مساله NPC باشه می شه گفت که B یه مساله NPC هست یا اگر B یه مساله NPC می شه گفت که A هم NPC هست؟؟

در واقع سوالم اینه که اگر A و B هر دو تصمیم پذیر باشند یعنی جزو P باشند اونوقت اگر A جزو مسائل P باشه، B هم P می شه و اگر B تصمیم پذیر یا جزو NPC باشه اونوقت َA هم NPC می شه؟

عشق صیدیست که تیرت به خطا هم برود/لذتش کنج دلت تا به ابد خواهد ماند
یافتن تمامی ارسال‌های این کاربر
نقل قول این ارسال در یک پاسخ
ارسال: #۲۲
۰۴ دى ۱۳۹۲, ۰۴:۱۶ ب.ظ
RE: [طراحی الگوریتم] شناخت NP و تمایزات بین NP-hard و NP-Complete
(۰۴ دى ۱۳۹۲ ۰۱:۰۳ ب.ظ)انرژی مثبت نوشته شده توسط:  اگر A در زمان چندجمله ای به B کاهش پیدا کنه، اگرA یه مساله NPC باشه می شه گفت که B یه مساله NPC هست یا اگر B یه مساله NPC می شه گفت که A هم NPC هست؟؟
اگه سوال به این صورت نوشته بشه:
فرض کنید A یک مساله NPC است؛ اگر A در زمان چندجمله ای به B کاهش پیدا کند، می توان گفت B نیز یک مساله NPC است؟
پاسخ مثبته:
.To prove that a problem is NP-complete, we typically reduce a problem that is known to be NP-complete to it

(
مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمی‌باشید. جهت مشاهده پیوندها ثبت نام کنید.
- سکشن ۴، خط اول)

گر وا نمی کنی گره ای، خود گـــره مباش،
ابروگشاده باش چو دستت گشاده نیست
یافتن تمامی ارسال‌های این کاربر
نقل قول این ارسال در یک پاسخ
ارسال: #۲۳
۰۴ دى ۱۳۹۲, ۰۷:۱۰ ب.ظ
RE: [طراحی الگوریتم] شناخت NP و تمایزات بین NP-hard و NP-Complete
(۰۴ دى ۱۳۹۲ ۰۴:۱۶ ب.ظ)Ghiasoddin نوشته شده توسط:  
(04 دى ۱۳۹۲ ۰۱:۰۳ ب.ظ)انرژی مثبت نوشته شده توسط:  اگر A در زمان چندجمله ای به B کاهش پیدا کنه، اگرA یه مساله NPC باشه می شه گفت که B یه مساله NPC هست یا اگر B یه مساله NPC می شه گفت که A هم NPC هست؟؟
اگه سوال به این صورت نوشته بشه:
فرض کنید A یک مساله NPC است؛ اگر A در زمان چندجمله ای به B کاهش پیدا کند، می توان گفت B نیز یک مساله NPC است؟
پاسخ مثبته:
.To prove that a problem is NP-complete, we typically reduce a problem that is known to be NP-complete to it

(
مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمی‌باشید. جهت مشاهده پیوندها ثبت نام کنید.
- سکشن ۴، خط اول)
ممنون (لینک رو قبلا دیده بودم واسه این شک ام بیشتر شد با توجه به توضیحات دوستان که نقل قول کرده بودم!)
می شه گفت سوالم اینه که بین P و NPC بودن فرق هست اینجا؟ یعنی توی جمله بعدم گفتم که با فرض این که A در زمان چند جمله ای به B کاهش پیدا می کنه، باید B مساله P باشه که A هم P باشه؟ ولی در مورد NPC باید A مساله NPC باشه تا B مساله NPC بشه؟

عشق صیدیست که تیرت به خطا هم برود/لذتش کنج دلت تا به ابد خواهد ماند
یافتن تمامی ارسال‌های این کاربر
نقل قول این ارسال در یک پاسخ
ارسال: #۲۴
۰۴ دى ۱۳۹۲, ۰۸:۵۶ ب.ظ
[طراحی الگوریتم] شناخت NP و تمایزات بین NP-hard و NP-Complete
در مورد مسائل P که بدیهیه؛ وقتی A از کلاس P هست یعنی یه الگوریتم قطعی چندجمله ای میتونه اونو حل کنه؛ حالا اگه مسئله B در زمان چندجمله ای به A کاهش پیدا کنه، یعنی B هم از کلاس P هست؛
حالت بر عکسش اینه که اگه A در زمان چندجمله ای به B کاهش پیدا کنه و از طرفی الگوریتم چندجمله ای برای A وجود نداشته باشه (A عضو P نباشه)، در این صورت B هم نمیتونه در چندجمله ای حل بشه (عضو P نیست)؛

گر وا نمی کنی گره ای، خود گـــره مباش،
ابروگشاده باش چو دستت گشاده نیست
یافتن تمامی ارسال‌های این کاربر
نقل قول این ارسال در یک پاسخ
 سپاس‌گزاری شده توسط: انرژی مثبت
ارسال: #۲۵
۱۳ آذر ۱۳۹۵, ۰۵:۵۸ ب.ظ
[طراحی الگوریتم] شناخت NP و تمایزات بین NP-hard و NP-Complete
سلام دوستان
چه گرد و خاکی گرفته اینجا!!
میگم چطور میشه اثبات کرد که توقف پذیری یه مسئله np-hard هست؟

خود را بشکن تا شکنی قلب جهان را
این فتح میسر به شکست دگری نیست...
یافتن تمامی ارسال‌های این کاربر
نقل قول این ارسال در یک پاسخ
ارسال: #۲۶
۲۸ مهر ۱۳۹۶, ۱۲:۲۲ ق.ظ
[طراحی الگوریتم] شناخت NP و تمایزات بین NP-hard و NP-Complete
سلام دوستان من ۴ تا مسئله الگوریتم پیشرفته دارم اگه کسی بلده بهم پیام بده ممنون میشم کمکم کنه
یکی مرتب سازی احمقانه هس
یکی هم کارت شماره ۳
یکی هم دومینوی ۲ و ۳ بعدی
آی دی تلگرام
niam_d3@
یافتن تمامی ارسال‌های این کاربر
نقل قول این ارسال در یک پاسخ


موضوع‌های مرتبط با این موضوع...
موضوع: نویسنده پاسخ: بازدید: آخرین ارسال
  [دانلود] ویس و جزوه ی طراحی الگوریتم سیدجوادی هاتف ۳۳ ۴۴,۱۷۵ ۰۴ تیر ۱۴۰۲ ۰۲:۰۳ ب.ظ
آخرین ارسال: solmaz58
  بین پردازش تصویر و داده کاوی موندم کدوم یکی رو برای پایان نامه انتخاب کنم؟ raheleh1393 ۵ ۸,۴۸۳ ۰۱ دى ۱۴۰۰ ۰۲:۴۸ ب.ظ
آخرین ارسال: golkhorami
  کدام زبان برای هوش مصنوعی بهتر است؟ فرق بین زبان های هوش مصنوعی چیست؟ azam2075 ۳ ۶,۰۱۲ ۱۴ مهر ۱۴۰۰ ۰۷:۲۱ ب.ظ
آخرین ارسال: علیصا
  طراحی ui/ux kimiya1234 ۲ ۲,۳۷۵ ۲۶ بهمن ۱۳۹۹ ۱۰:۴۲ ب.ظ
آخرین ارسال: farsamw
  پکیج آموزشی طراحی وب + فارسی سازی وردپرس + سئو Happiness.72 ۶ ۶,۸۳۷ ۱۸ بهمن ۱۳۹۹ ۰۱:۱۵ ب.ظ
آخرین ارسال: saqarmoshtaq
  طراحی یک سیستم عامل (از صفر) sina4everafter ۱۲ ۱۶,۵۸۶ ۰۶ بهمن ۱۳۹۹ ۱۲:۵۳ ب.ظ
آخرین ارسال: nahalmomen2007@yahoo.com
  طراحی سایت ریسپانسیو wikidemy1 ۰ ۱,۸۴۴ ۱۳ دى ۱۳۹۹ ۰۴:۰۱ ب.ظ
آخرین ارسال: wikidemy1
  طراحی الگوریتم ها amir.m5560@gmail.com ۰ ۱,۷۱۴ ۳۰ آذر ۱۳۹۹ ۰۸:۲۴ ب.ظ
آخرین ارسال: amir.m5560@gmail.com
  طراحی الگوریتم ها amir.m5560@gmail.com ۰ ۱,۵۴۶ ۳۰ آذر ۱۳۹۹ ۰۸:۲۰ ب.ظ
آخرین ارسال: amir.m5560@gmail.com
  مجموعه تمارین و سوالات امتحانی درس طراحی الگوریتم دانشگاه MIT (سال ۲۰۰۰-۲۰۱۲) Farid_Feyzi ۵ ۷,۷۵۷ ۳۰ آبان ۱۳۹۹ ۱۰:۱۵ ب.ظ
آخرین ارسال: s-taheri

پرش به انجمن:

Can I see some ID?

به خاطر سپاری رمز Cancel

Feeling left out?


نگران نباش، فقط روی این لینک برای ثبت نام کلیک کن. رمزت رو فراموش کردی؟ اینجا به یادت میاریم! close

رمزت رو فراموش کردی؟

Feeling left out?


نگران نباش، فقط روی این لینک برای ثبت نام کلیک کن. close