advertise laitec sharif univercity تبلیغات در سایت سورس کد تبلیغات در سایت سورس کد
دانلود PDF مجموعه 300 نکته جالب برنامه نویسی در سی شارپ #C

دانلود PDF مجموعه 300 نکته جالب برنامه نویسی در سی شارپ #C

3000 تومان
دانلود پروژه کامل مهندسی نرم افزار ، شرکت نرم افزاری

دانلود پروژه کامل مهندسی نرم افزار ، شرکت نرم افزاری

3000 تومان
دانلود پروژه مهندسی نرم افزار ، نمایندگی ایران خودرو

دانلود پروژه مهندسی نرم افزار ، نمایندگی ایران خودرو

3000 تومان
دانلود پروژه فروشنده دوره گرد با الگوریتم ازدحام ذرات PSO در #C

دانلود پروژه فروشنده دوره گرد با الگوریتم ازدحام ذرات PSO در #C

4800 تومان
دانلود پروژه پایانی طراحی وب سایت مخابرات با Asp.net

دانلود پروژه پایانی طراحی وب سایت مخابرات با Asp.net

14000 تومان

آشنایی با نظریه NP در طراحی الگوریتم

نظریهNP (نظریه پیچیدگی محاسباتی) شاخه ای از نظریه محاسبات و ریاضی و علوم کامپیوتری است که به بررسی دشواری حل مسائل بصورت الگوریتمی می پردازد.
آشنایی با نظریه NP در طراحی الگوریتم

آشنایی با نظریه NP در طراحی الگوریتم

نظریهNP  (نظریه پیچیدگی محاسباتی) شاخه ای از نظریه محاسبات و ریاضی و علوم کامپیوتری است که به بررسی دشواری حل مسائل  بصورت الگوریتمی می پردازد. برای آشنایی با این نظریه بهتر است ابتدا مفاهیمی را تعریف کنیم:

 

مسائل بغرنج intractable

الگوریتم زمانی چند جمله ای، الگوریتمی است که در بدترین حالت پیچیدگی زمانی آن تابع چندجمله ای از اندازه ورودی باشد. مسئله ای بغرنج است که حل آن توسط الگوریتمی با زمان چندجمله ای غیر ممکن باشد. بحث ما بر سر خود مساله است و نه الگوریتم حل مساله. ممکن است برای حل مساله الگوریتم های متعددی با زمان های مختلف وجود داشته باشد. مثلا حل مساله ی سری فیبوناچی با روش تقسیم و حل از مرتبه نمایی و با روش پویا از مرتبه خطی است، پس مسئله فیبوناچی از نوع بغرنج نیست.

برای آنکه مسئله ای بغرنج باشد باید اثبات کرد که هیچ الگوریتمی با مرتبه چندجمله ای برای آن وجود ندارد. از نظر بغرنج بودن یا نبودن، مسائل علوم کامپیوتر سه دسته هستند:

► مسائلی که الگوریتم هایی با پیچیدگی زمانی چندجمله ای برای آنها پیدا شده است.

► مسائلی که اثبات شده است که بغرنج هستند، یعنی الگوریتم چندجمله ای برای آن یافت نمیشود.

► مسائلی که بغرنج بودن آنها ثابت نشده است ولی از طرف دیگر هیچ الگوریتم چندجمله ای هم برای انها پیدا نشده است.

مثلا جستوجوی دودویی در آرایه مرتب θ(lgn) ، مساله مرتب سازی آرایه ها θ(nlgn)، ضرب زنجیره ای ماتریسها θ(n3) از دسته اول هستند. همچنین مسائل کوتاهترین مسیر فلوید θ(n3)، درخت دودویی بهینه θ(n3) و مساله درخت پوشای کمینه پریم θ(n2) با اینکه الگوریتم های نمایی نیز دارند ولی چون برای آنها الگوریتم هایی از نوع چندجمله ای یافت شده است از این دسته اند.تعداد مسائلی که جزو دسته دوم بوده و بغرنج بودن آنها اثبات شده است، نسبتا کم بوده است. نمونه ای از این مسائل دسته دوم، حساب پرزبرگر است.

مساله کوله پشتی صفر و یک و مساله فروشنده دوره گرد از دسته سوم هستند.

 

رابطه مسائل بهینه سازی با مسائل تصمیم گیری

خروجی مسائل بهینه سازی یک حل بهینه است و خروجی مسائل تصمیم گیری جواب بله یا خیر است. هر مساله بهینه سازی را میتوان متناظر با یک مسئله تصمیم گیری در نظر گرفت. پس در ادامه روی مسائل تصمیم گیری به جای مسائل بهینه سازی تمرکز میکنیم:

 

کلاس P

بطور کلی مسائل تصمیم گیری را به چهار کلاس تقسیم میکنیم. مسائلی که برای حل آنها الگوریتم یا الگوریتم هایی با مرتبه زمانی چندجمله ای یافت شده است کلاس الگوریتم های معین یا الگوریتم های قطعی را تشکیل میدهند. این کلاس را با علامت ویژه p که کوتاه شده polynomial میباشد نمایش میدهیم.

الگوریتم هایی که برای کامپیوترهای رایج طراحی میگردند الگوریتم های معین نامیده میشوند. در این الگوریتم ها نتیجه هر عمل کاملا مشخص، معین و قطعی است. P کلاس کلیه مسائل تصمیم گیری است که برای حل آنها الگوریتم معین با مرتبه زمانی چندجمله ای وجود دارد.

 

کلاس NP (Nondeterministic polynomial)

برای معرفی کلاس NP  باید ماشینی (کامپیوتری) با مشخصات جدید تعریف کنیم. ماشینی را تصور کنید که افزون بر توانایی اجرای دستورهای معین و قطعی قادر است برخی دستورهای نامعین را نیز اجرا کند. یک دستور نامعین دستوری است که نتیجه اجرای آن از قبل قابل پیش بینی نیست. الگوریتم هایی که برای یک کامپیوتر نامعین طراحی میشوند الگوریتم های نامعین نامیده میشوند. برای بیان اینگونه الگوریتم ها افزون بر دستورهایی که برای بیان الگوریتم های معین وجود دارد  از سه تابع زیر استفاده خواهیم کرد:

 تابع choice (S) : این تابع یکی از عناصر مجموعه S را به دلخواه انتخاب میکند. عمل انتخاب برای یک کامپیوتر نامعین عمل ساده ای است و مرتبه زمانی آن O(1) است.

 تابع failure() : این تابع پایان ناموفق عملیات الگوریتم را اعلام مکیند. این اعلام به مفهوم جواب false برای مساله تصمیم گیری مورد نظر میباشد. مرتبه زمانی این تابع هم O(1) است.

► تابع success() : این تابع پایان موفق عملیات الگوریتم را اعلام می کند. این اعلام به مفهوم جواب true برای مساله تصمیم گیری مورد نظر می باشد. مرتبه زمانی این تابع نیز برای کامپیوترهای نامعین O(1) است.

تشخیص اول یا اول نبودن یک عدد طبیعی، مرتب کردن اطلاعات و صدق پذیری نمونه هایی از مسائلی هستند که میتوان الگوریتم های نامعین ساده ای برایشان طراحی کرد. در بیان یک الگوریتم نامعین ممکن است از همه دستورها و بویژه از دستورهای choice، failure و success استفاده نشود. بنابراین هر الگوریتم معین توسط یک کامپیوتر نامعین قابل اجرا است.پس P زیرمجموعه NP است. محققین زیادی سعی کرده اند ثابت کنند P = NP اگر این مساله ثابت شود مفهوم آن این است که هر مساله ای که برای آن الگوریتم نامعین با مرتبه زمانی چندجمله ای وجود دارد میتوان برای آن یک الگوریتم معین با مرتبه زمانی چندجمله ای پیدا کرد.

یکی از مسائل عضو کلاس NP مساله صدق پذیری است. مسئله صدق پذیری بررسی این مطلب است که آیا یک عبارت منطقی داده شده به ازای مقادیری از لفظ های تشکیل دهنده آن درست خواهد بود. طراحی یک الگوریتم نامعین که تشخیص بدهد یک عبارت داده شده صدق پذیر است یا خیر مشکل نیست.

در سال 1971، S.A.Cook ثابت کرد که چنانچه ثابت شود که صدق پذیری به کلاس P تعلق دارد، آنگاه P = NP است و بالعکس. با بیان این مطلب مساله صدق پذیری از اهمیت بالایی برخوردار میشود، به گونه ای که کلاسهای NP-hard و NP-complete بر محور این قضیه شکل میگیرند. افزون بر آن تلاش دانشمندانی را که در مسیر اثبات P = NP فعالیت میکنند جهتدار مینماید و فعالیت آنها را حول محور تلاش برای یافتن راه حل  معین چندجمله ای برای مساله صدق پذیری متمرکز میکند.

 

کلاس NP-hard

ابتدا مفهوم کاهش پذیری بین مسائل را تعریف میکنیم.

فرض کنید M1 و M2 دو مساله باشند. مساله M1 به مسئله M2 کاهش پیدا میکند (M2M1 )  اگر و فقط اگر چنانچه یک الگوریتم معین با مرتبه زمانی چند جمله ای برای M2 وجود داشته باشد، آنگاه بتوان با به کار گیری الگوریتم معین با مرتبه زمانی چند جمله ای که M2 را حل میکند، M1 را با الگوریتمی معین و زمان چندجمله ای حل کرد. رابطه کاهش پذیری یک رابطه با خاصیت تعدی است یعنی اگر M1M2و M2M3 آنگاه: M1M3.

مساله M یک مساله NP-hard است اگر و فقط اگر صدق پذیری به آن کاهش پیدا کند (satisfiability→M).

کلاس NP-hard تنها به مسائل تصمیم گیری محدود نمیشود. نمونه ای از مسائل NP-hard که در عین حال NP-complete نیست "مساله توقف پذیری" است. در این مساله هدف ساختن الگوریتمی است که مشخص کند آیا یک برنامه کامپیوتری داده شده هیچ وقت پایان خواهد یافت (یعنی اجزای آن تکمیل خواهد شد و توقف خواهد کرد و یا وارد حلقه نامتناهی خواهد گردید) . ورودی چنین الگوریتمی میتواند هر برنامه کامپیوتری و طیف داده های آن باشد و خروجی چنین الگوریتمی بله یا خیر است. بله یعنی اینکه برنامه ورودی توقف خواهد کرد و خیر یعنی برنامه ورودی در حلقه ای نامتناهی گیر خواهد افتاد. الگوریتمی که برای هر برنامه ورودی و طیف داده های آن جواب درستی بدهد محاسبه ناپذیر است، یعنی هیچ راه حل الگوریتمی برای آن وجود ندارد. نتیجه اینکه "مساله توقف پذیری" به کلاس NP تعلق ندارد.

 

کلاس NP-complete

کلاس NP-complete زیرکلاس ، کلاسهای NP و NP-hard است. در واقع کلاس NP-complete فصل مشترک کلاسهای NP و NP-hard را تشکیل میدهد.

مساله M یک مساله NP-complete است اگر و فقط اگر M یک مساله NP-hard باشد و در عین حال M زیر مجموعه NP.

برخی از عبارتهای منطقی بصورت ترکیبی عطفی نوشته میشوند. این گونه عبارتهای منطقی یا یک بند هستند و یا ترکیب عطفی (and) چند بند. میگوییم این عبارتها به شکل نرمال عطفی هستند . با علامت اختصاری CNF نشان داده میشوند.

شکل نرمال عطفی در واقع همان شکل حاصل ضرب مجموع هاست. ثابت میشود که صدق پذیری عبارتهای CNF یک مسئله NP-complete است. متعاقبا میتوان ثابت کرد که صدق پذیری خود به کلاس NP-complete تعلق دارد.

نمونه دیگری از مسائل NP-complete مسئله سه رنگ پذیری است. اگر G یک گراف بدون جهت باشد مساله سه رنگ پذیری بررسی می نماید که آیا این گراف سه رنگ پذیر میباشد یا خیر. آیا میشود گره های گراف ا با استفاده از تنها سه رنگ رنگ آمیزی کرد که هیچ دو گره مجاور رنگ یکسانی نداشته باشند. چهار رنگ پذیری گرافها نیز یک مساله NP-complete است اما دورنگ پذیری بک مساله P است.

 

 



3
نظرات
  • user avatar محبوبه موسوی:
    ۱۷:۲۰:۲۶ __ ۱۳۹۴/۱۱/۱۷

    سلاممرسی از آموزشتون ...

  • user avatar عسل:
    ۰۰:۳۰:۴۷ __ ۱۳۹۴/۱۲/۰۸

    خیلی عالی ممنون

  • user avatar رضا:
    ۲۳:۴۹:۱۴ __ ۱۳۹۵/۰۹/۱۰

    خیلی عالی وگویا توضیح دادین،ممنون

نظر خود را ارسال کنید



نام:
ایمیل:
دیدگاه:
captcha
کد امنیتی :


advertise
کلاسهای NP چگونه اند؟نظریه NPچیست؟کلاس Nondeterministic polynomialمفاهمی ابتدایی کلاس NPتعریف مسائل بغرنج intractableنمونه مسئله های بغرنجآیا p=NP?الگوریتم های نامعین در نظریه ان پیکلاس NP-hardکلاس NP-completeرابطه مسائل بهینه سازی با مسائل تصمیم گیرینظریه چندجمله ای غیر قطعیالگوریتم های قطعی و غیر قطعی NP لیست برچسب ها
تمامی حقوق این سایت اعم از محتوی ، تصاویر ، قالب و ... متعلق به گروه مهندسی وب سایت سورس کد می باشد.
SourceCodes.ir ، افقی روشن برای برنامه نویسان ، از مبتدی تا حرفه ای

سفارش پروژه در سورس کد

پیشنهادات ویژه سورس کد

پکیج ویژه پروژه پایانی رشته کامپیوتر دانلود مجموعه 70 پروژه کاربردی سی شارپ وب سایت فروشگاه با php