دسترسی نامحدود
برای کاربرانی که ثبت نام کرده اند
دانلود کتاب Exact Exponential Algorithms
دانلود کتاب الگوریتم های نمایی دقیق
مشخصات کتاب
Exact Exponential Algorithms
ویرایش: نویسندگان: Fedor V. Fomin, Dieter Kratsch سری: Texts in Theoretical Computer Science. An EATCS Series ISBN (شابک) : 364216532X, 9783642165320 ناشر: Springer سال نشر: 2010 تعداد صفحات: 206 [218] زبان: English فرمت فایل : PDF (درصورت درخواست کاربر به PDF، EPUB یا AZW3 تبدیل می شود) حجم فایل: 3 Mb
قیمت کتاب (تومان) : 34,000
در صورت تبدیل فایل کتاب Exact Exponential Algorithms به فرمت های PDF، EPUB، AZW3، MOBI و یا DJVU می توانید به پشتیبان اطلاع دهید تا فایل مورد نظر را تبدیل نمایند.
توجه داشته باشید کتاب الگوریتم های نمایی دقیق نسخه زبان اصلی می باشد و کتاب ترجمه شده به فارسی نمی باشد. وبسایت اینترنشنال لایبرری ارائه دهنده کتاب های زبان اصلی می باشد و هیچ گونه کتاب ترجمه شده یا نوشته شده به فارسی را ارائه نمی دهد.
توضیحاتی در مورد کتاب الگوریتم های نمایی دقیق
برای مدت طولانی دانشمندان کامپیوتر بین ریتم الگوبرداری سریع و کند تمایز قائل شده اند. الگوریتم‌های سریع (یا خوب) الگوریتم‌هایی هستند که در زمان چندجمله‌ای اجرا می‌شوند، به این معنی که تعداد مراحل مورد نیاز الگوریتم برای حل یک مسئله با چند جمله‌ای در طول ورودی محدود می‌شود. همه الگوریتم های دیگر کند هستند (یا بد). زمان اجرای الگوریتم های کند معمولاً نمایی است. این کتاب در مورد الگوریتم های بد است. دلایل مختلفی وجود دارد که چرا ما به الگوریتم های زمان نمایی علاقه مند هستیم. بسیاری از ما معتقدیم که بسیاری از مسائل طبیعی وجود دارد که با الگوریتم های زمانی چند جمله ای قابل حل نیستند. معروف ترین و قدیمی ترین خانواده مسائل سخت، خانواده مسائل کامل NP است. به احتمال زیاد هیچ گوریتم زمانی چند جمله ای برای حل این مسائل سخت وجود ندارد و در بدترین حالت زمان اجرای نمایی اجتناب ناپذیر است. هر مسئله ترکیبی با برشمردن همه راه‌حل‌های ممکن در زمان آخر قابل حل است. ه. با جستجوی زور وحشیانه اما آیا جستجوی بی رحمانه همیشه غیرقابل اجتناب است؟ البته نه. قبلاً در دهه 1960 و 70 شناخته شده بود که برخی از مسائل کامل NP را می توان به میزان قابل توجهی سریعتر از جستجوی brute force حل کرد. سه مثال کلاسیک الگوریتم های زیر برای مسئله فروشنده دوره گرد، حداکثر مجموعه مستقل و رنگ آمیزی هستند.
توضیحاتی درمورد کتاب به خارجی
For a long time computer scientists have distinguished between fast and slow algo rithms. Fast (or good) algorithms are the algorithms that run in polynomial time, which means that the number of steps required for the algorithm to solve a problem is bounded by some polynomial in the length of the input. All other algorithms are slow (or bad). The running time of slow algorithms is usually exponential. This book is about bad algorithms. There are several reasons why we are interested in exponential time algorithms. Most of us believe that there are many natural problems which cannot be solved by polynomial time algorithms. The most famous and oldest family of hard problems is the family of NP complete problems. Most likely there are no polynomial time al gorithms solving these hard problems and in the worst case scenario the exponential running time is unavoidable. Every combinatorial problem is solvable in ?nite time by enumerating all possi ble solutions, i. e. by brute force search. But is brute force search always unavoid able? De?nitely not. Already in the nineteen sixties and seventies it was known that some NP complete problems can be solved signi?cantly faster than by brute force search. Three classic examples are the following algorithms for the TRAVELLING SALESMAN problem, MAXIMUM INDEPENDENT SET, and COLORING.
فهرست مطالب
Cover Texts in Theoretical Computer Science: An EATCS Series Exact Exponential Algorithms Copyright 9783642165320 Preface Acknowledgements Contents 1 Introduction 1.1 Preliminaries 1.2 Dynamic Programming for TSP 1.3 A Branching Algorithm for Independent Set 2 Branching 2.1 Fundamentals 2.2 k-Satisfiability 2.3 Independent Set 3 Dynamic Programming 3.1 Basic Examples 3.1.1 Permutation Problems 3.1.2 Partition Problems 3.2 Set Cover and Dominating Set 3.3 TSP on Graphs of Bounded Degree 3.4 Partition into Sets of Bounded Cardinality 4 Inclusion-Exclusion 4.1 The Inclusion-Exclusion Principle 4.2 Some Inclusion-Exclusion Algorithms 4.2.1 Computing the Permanent of a Matrix 4.2.2 Directed Hamiltonian Path 4.2.3 Bin Packing 4.3 Coverings and Partitions 4.3.1 Coverings and Graph Coloring 4.3.2 Partitions 4.3.3 Polynomial Space Algorithms 4.4 Counting Subgraph Isomorphisms 5 Treewidth 5.1 Definition and Dynamic Programming 5.2 Graphs of Maximum Degree 3 5.3 Counting Homomorphisms 5.4 Computing Treewidth 5.4.1 Computing the Treewidth Using Potential Maximal Cliques 5.4.2 Counting Minimal separators and Potential Maximal Cliques 6 Measure & Conquer 6.1 Independent Set 6.2 Feedback Vertex Set 6.2.1 An Algorithm for Feedback Vertex Set 6.2.2 Computing a Minimum Feedback Vertex Set 6.3 Dominating Set 6.3.1 The Algorithm msc 6.3.2 A Measure & Conquer Analysis 6.4 Lower Bounds 7 Subset Convolution 7.1 Fast zeta Transform 7.2 Fast Subset Convolution 7.3 Applications and Variants 7.4 f-width and Rank-width 8 Local Search and SAT 8.1 Random Walks to Satisfying Assignments 8.2 Searching Balls and Cover Codes 9 Split and List 9.1 Sort and Search 9.2 Maximum Cut 10 Time Versus Space 10.1 Space for Time: Divide & Conquer 10.2 Time for Space: Memorization 11 Miscellaneous 11.1 Bandwidth 11.2 Branch & Recharge 11.3 Subexponential Algorithms and ETH 12 Conclusions, Open Problems and Further Directions References Appendix: Fundamental Notions on Graphs Index
