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

 اسلاید 1 :

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

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

اسلاید 2 :

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

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

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

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

  • مسائل NP-Complete

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

Q

Q

اسلاید 3 :.

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

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

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

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

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

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

اسلاید 4 :

  • تست تورینگ

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

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

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

Q

Q

Q

Q

Q

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

اسلاید 5 :

  • Class of Problems

QP (Polynomial)

QNP (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

QNP-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

QNP-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

QApproximation 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 :

Qa formal notion of what a “problem” is

Qhigh-level description of a problem

  • We define an abstract problem Q to be

Qa binary relation on

Qa set I of problem instances, and

Qa set S of problem solutions.

QQ ÎI ´ S

  • Three Kinds of Problems

QDecision Problem

fe.g. Is there a solution better than some given bound?

QOptimal Value

fe.g. What is the value of a best possible solution?

QOptimal Solution

fe.g. Find a solution that achieves the optimal value.

اسلاید 9 :

Q// Data Structure

Qdescribing abstract problems (for solving by computers)

Qin terms of data structure or binary strings

  • An encoding of a set S of abstract objects is

Qa mapping e from S to the set of binary strings.

  • Encoding for Decision problems

QProblem instances,  e : I à {0, 1}*

QSolution, e : S à {0, 1}

  • “Standard” encoding

Qcomputing time may be a function of encoding

f// The size of the input (the number of bit to represent one input)

Qpolynomially related encodings

Qassume encoding in a reasonable concise fashion

اسلاید 10 :

Qproblem instances and solutions are represented in data structure or binary strings

Q// Language (in formal-language framework)

  • We call a problem whose instance set (and solution set) is the set of binary strings a concrete problem.
  • Computer algorithm solves concrete problems!

Qsolves a concrete problem in time O(T(n))

Qif provided a problem instance i of length n = |i|,

Qthe algorithm can produce the solution

Qin a most O(T(n)) time.

  • A concrete problem is polynomial-time solvable

Qif there exists an algorithm to solve it in time O(nk)

Qfor some constant k. (also called polynomially bounded)

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