بخشی از پاورپوینت

--- پاورپوینت شامل تصاویر میباشد ----

اسلاید 1 :

پیچیدگی مسائل

  • پیچیدگی چندجمله ای
  • پیچیدگی نمایی و فاکتوریل

این الگوریتم ها برای مسائل با اندازه کوچک بد نیستند ولی با افزایش اندازه ورودی به شدت کند می شوند

اسلاید 2 :

  • مساله کنترل ناپذیر

برای مساله راه حلی با زمان چندجمله ای وجود ندارد

  • مسائل رام نشدنی(Intractable)

اثبات می گردد که یافتن راه حل کارآمد غیر ممکن است مثلا یافتن کلیه مسیر های همیلتونی

  • مسائل NP-Complete

مسائلی هستند که یافتن راه حل کارآمد برای آنها غیر ممکن نیست (ثابت نشده است رام نشدنی هستند) مانند کوله پشتی 0-1 و فروشنده دوره گرد و رنگ آمیزی گراف ها

 

 

اسلاید 3 :

  • الگوریتم قطعی:

نتیجه هر عمل کاملا معین و قطعی است مانند الگوریتم جستجوی  دودویی و مرتب سازی و ...

کامپیوتر های قطعی

  • الگوریتم غیر قطعی:

الگوریتمی است که دارای دستورات غیر قطعی است

دستورات غیر قطعی: دستوراتی که نتیجه اجرای آن از قبل قابل پیش بینی نیست(مثلا دستوری که از 100 عنصر یکی را انتخاب کند) یا دستورات مبتنی بر اعداد تصادفی

اسلاید 4 :

  • تست تورینگ

test defined by the mathematician Allen Turing for testing the ability of a machine to simulate human intelligence

  • ماشين‌ تورينگ‌ (turing machine)

ماشینی تئوری است که با دریافت ورودی ها اثبات ریاضی(حل مسائل) را انجام می دهد

 

 

 

 

 

name for a theoretical machine that can make simple input/output actions which are used to in mathematical proofs

اسلاید 5 :

  • Class of Problems

P (Polynomial)

NP (none-deterministic Polynomial)

fNP is the set of decision problems solvable in polynomial time by a non-deterministic Turing machine.

fNP is the class of decision problems for which there is a polynomially bounded non-deterministic algorithm

NP-Complete

fA problem p in NP is also in NPC if and only if every other problem in NP can be transformed into p in polynomial time

NP-Hard

fA problem H is NP-hard if and only if there is an NP-complete problem L that is polynomial time Turing-reducible to H

  • Solving hard problems

Approximation Algorithms

اسلاید 6 :

دسته بندی مسائل 

  • چند جمله ایP (Polynomial) : مسائل تصمیم گیری که در زمان چند جمله ای توسط الگوریتم قطعی(ماشین تورینگ قطعی) قابل حل می باشد
  • چند جمله ای غیر قطعی NP(none-deterministic Polynomial): مسائل تصمیم گیری که برای آن ها کسی راه حل چندجمله ای نیافته است اما توسط الگوریتم غیر قطعی(ماشین تورینگ غیر قطعی) در زمان چند جمله ای قابل حل است P Í NP
  • NP-Complete: مساله P، NP-Complete است اگر NP باشد و سایر مسائل NP را در زمان چند جمله ای بتوان به آن تبدیل کرد
  • NP-Hard: مساله H، NP-Hard است اگر وفقط اگر یک مساله NP-Compelete ، L وجود داشته باشد که در زمان چند جمله ای قابل تبدیل به H باشد

اسلاید 7 :

  • تمام مسائلی که کنترل ناپذیری آنها ثابت شده است جزء مسایل NP نیستند

اسلاید 8 :

کلاس های مختلف

  • P• NP• co-NP • NP-C • co-NP-C • NP-hard • UP • #P • #P-C • L • NL • NC • P-C • PSPACE • PSPACE-C • EXPTIME • NEXPTIME • EXPSPACE • 2-EXPTIME • PR • RE • Co-RE • RE-C • Co-RE-C • R • B P • BPP • RP • ZPP • PCP • IP • PH

اسلاید 9 :

Class of Problems

// What makes a problem hard?

// Make simple: classify decision problems

  • Definition: The class P

P is the class of decision problems that are polynomially bounded.

f// there exist a deterministic algorithm

  • Definition: The class NP

NP is the class of decision problems for which there is a polynomially bounded non-deterministic algorithm.

fThe name NP comes from “Non-deterministic Polynomially bounded.”

f// there exist a non-deterministic algorithm

  • Theorem: P Í NP

اسلاید 10 :

The Class NP

  • NP is a class of decision problems for which

a given proposed solution (called certificate) for

a given input

can be checked uickly (in polynomial time)

to see if it really is a solution.

  • A non-deterministic algorithm

The non-deterministic “guessing” phase.

fSome completely arbitrary string s, “proposed solution”

feach time the algorithm is run the string may differ

The deterministic “verifying” phase.

fa deterministic algorithm takes the input of the problem and the proposed solution s, and

freturn value true or false

The output step.

fIf the verifying phase returned true, the algorithm outputs yes. Otherwise, there is no output.

در متن اصلی پاورپوینت به هم ریختگی وجود ندارد. برای مطالعه بیشتر پاورپوینت آن را خریداری کنید