فرمت فایل: پاورپوینت - ppt  

کتاب سبز - قابل ویرایش ) 

تعداد اسلاید : 27
طراحي الگوريتم ها پیچیدگی مسائل پیچیدگی چندجمله ای پیچیدگی نمایی و فاکتوریل این الگوریتم ها برای مسائل با اندازه کوچک بد نیستند ولی با افزایش اندازه ورودی به شدت کند می شوند مساله کنترل ناپذیر برای مساله راه حلی با زمان چندجمله ای وجود ندارد مسائل رام نشدنی(Intractable) اثبات می گردد که یافتن راه حل کارآمد غیر ممکن است مثلا یافتن کلیه مسیر های همیلتونی مسائل NP-Complete مسائلی هستند که یافتن راه حل کارآمد برای آنها غیر ممکن نیست (ثابت نشده است رام نشدنی هستند) مانند کوله پشتی 0-1 و فروشنده دوره گرد و رنگ آمیزی گراف ها الگوریتم قطعی: نتیجه هر عمل کاملا معین و قطعی است مانند الگوریتم جستجوی دودویی و مرتب سازی و ... کامپیوتر های قطعی الگوریتم غیر قطعی: الگوریتمی است که دارای دستورات غیر قطعی است دستورات غیر قطعی: دستوراتی که نتیجه اجرای آن از قبل قابل پیش بینی نیست(مثلا دستوری که از 100 عنصر یکی را انتخاب کند) یا دستورات مبتنی بر اعداد تصادفی تست تورینگ 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 NP-Complete Problems Class of Problems P (Polynomial) NP (none-deterministic Polynomial) NP is the set of decision problems solvable in polynomial time by a non-deterministic Turing machine. NP is the class of decision problems for which there is a polynomially bounded non-deterministic algorithm NP-Complete A 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 A 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 دسته بندی مسائل تمام مسائلی که کنترل ناپذیری آنها ثابت شده است جزء مسایل NP نیستند کلاس های مختلف Abstract Problems Encodings Concrete Problem Class of Problems The Class NP The Class NP-Complete Polynomial Reductions Circuit-satisfiability problem is NP-Complete NP-Completeness Proofs Solving hard problems:Approximation Algorithms Approximation Algorithm e.g. Bin Packing Bin Packing: First fit decreasing strategy Algorithm: Bin Packing (first fit decreasing) The Traveling Salesperson Problem Approximation algorithm for TSP

قسمتی از متن بالا پروژه میباشد که به صورت نمونه ، بعد از پرداخت آنلاین در جزوه باز آنی فایل را دانلود نمایید .

  

 « پرداخت آنلاین و دانلود در قسمت پایین »