دسترسی نامحدود
برای کاربرانی که ثبت نام کرده اند
برای ارتباط با ما می توانید از طریق شماره موبایل زیر از طریق تماس و پیامک با ما در ارتباط باشید
در صورت عدم پاسخ گویی از طریق پیامک با پشتیبان در ارتباط باشید
برای کاربرانی که ثبت نام کرده اند
درصورت عدم همخوانی توضیحات با کتاب
از ساعت 7 صبح تا 10 شب
ویرایش: 2nd ed. 2020
نویسندگان: Antti Laaksonen
سری: Undergraduate Topics in Computer Science
ISBN (شابک) : 3030393569, 9783030393564
ناشر: Springer
سال نشر: 2020
تعداد صفحات: 315
زبان: English
فرمت فایل : PDF (درصورت درخواست کاربر به PDF، EPUB یا AZW3 تبدیل می شود)
حجم فایل: 11 مگابایت
در صورت تبدیل فایل کتاب Guide to Competitive Programming: Learning and Improving Algorithms Through Contests (Undergraduate Topics in Computer Science) به فرمت های PDF، EPUB، AZW3، MOBI و یا DJVU می توانید به پشتیبان اطلاع دهید تا فایل مورد نظر را تبدیل نمایند.
توجه داشته باشید کتاب راهنمای برنامه نویسی رقابتی: یادگیری و بهبود الگوریتم ها از طریق مسابقات (مباحث کارشناسی علوم کامپیوتر) نسخه زبان اصلی می باشد و کتاب ترجمه شده به فارسی نمی باشد. وبسایت اینترنشنال لایبرری ارائه دهنده کتاب های زبان اصلی می باشد و هیچ گونه کتاب ترجمه شده یا نوشته شده به فارسی را ارائه نمی دهد.
با تکیه بر آنچه که در حال حاضر جامع ترین مقدمه برای برنامه نویسی رقابتی است، این کتاب درسی جدید پیشرفته دارای مطالب جدیدی در مورد موضوعات پیشرفته است، مانند محاسبه تبدیل فوریه، یافتن حداقل جریان هزینه در نمودارها، و استفاده از خودکار در مسائل رشته ای. به طور انتقادی، متن به طور قابل دسترس توصیف و نشان میدهد که چگونه برنامهنویسی رقابتی یک روش اثبات شده برای پیادهسازی و آزمایش الگوریتمها، و همچنین توسعه تفکر محاسباتی و بهبود مهارتهای برنامهنویسی و اشکالزدایی است.
موضوعات. و ویژگیها: برنامهنویسی پویا و سایر تکنیکهای طراحی الگوریتم اساسی را معرفی میکند و طیف گستردهای از الگوریتمهای گراف را بررسی میکند. سازگار با برنامه درسی IOI، در عین حال موضوعات پیشرفته تری مانند جریان حداکثر، نظریه Nim و ساختارهای پسوندی را نیز پوشش می دهد. الگوریتم های تخصصی درختان را بررسی می کند و موضوعات ریاضی مرتبط با برنامه نویسی رقابتی را مورد بحث قرار می دهد. ویژگیهای زبان برنامهنویسی C++ را بررسی میکند و نحوه ایجاد الگوریتمهای کارآمد را توضیح میدهد که میتوانند به سرعت مجموعههای داده بزرگ را پردازش کنند. الگوریتمهای مرتبسازی و جستجوی باینری را مورد بحث قرار میدهد و مجموعهای از ساختارهای داده کتابخانه استاندارد C++ را بررسی میکند. موضوعات طراحی الگوریتم پیشرفته مانند موازی بیت و تجزیه و تحلیل استهلاک را پوشش می دهد و تمرکز بر پردازش کارآمد پرس و جوهای محدوده آرایه را ارائه می دهد. مجموعه ای از موضوعات پیشرفته تر، از جمله الگوریتم های ریشه مربع و بهینه سازی برنامه نویسی پویا را شرح می دهد.
این کتاب درسی/راهنمای اصلی بهطور کامل بهروز، گسترش یافته و قابل پیگیری است، مرجعی ایدهآل برای همه دانشآموزانی است که نیاز دارند. برای یادگیری الگوریتم ها و تمرین برای مسابقات برنامه نویسی. دانش مبانی برنامه نویسی فرض می شود، اما سابقه قبلی در طراحی الگوریتم یا مسابقات برنامه نویسی ضروری نیست. این کتاب با گستردگی موضوعات، مثالها و مراجع، هم برای مبتدیان و هم برای خوانندگان با تجربهتر بسیار مناسب است.Building on what already is the most comprehensive introduction to competitive programming, this enhanced new textbook features new material on advanced topics, such as calculating Fourier transforms, finding minimum cost flows in graphs, and using automata in string problems. Critically, the text accessibly describes and shows how competitive programming is a proven method of implementing and testing algorithms, as well as developing computational thinking and improving both programming and debugging skills.
Topics and features: introduces dynamic programming and other fundamental algorithm design techniques, and investigates a wide selection of graph algorithms; compatible with the IOI Syllabus, yet also covering more advanced topics, such as maximum flows, Nim theory, and suffix structures; surveys specialized algorithms for trees, and discusses the mathematical topics that are relevant in competitive programming; reviews the features of the C++ programming language, and describes how to create efficient algorithms that can quickly process large data sets; discusses sorting algorithms and binary search, and examines a selection of data structures of the C++ standard library; covers such advanced algorithm design topics as bit-parallelism and amortized analysis, and presents a focus on efficiently processing array range queries; describes a selection of more advanced topics, including square-root algorithms and dynamic programming optimization.
Fully updated, expanded and easy to follow, this core textbook/guide is an ideal reference for all students needing to learn algorithms and to practice for programming contests. Knowledge of programming basics is assumed, but previous background in algorithm design or programming contests is not necessary. With its breadth of topics, examples and references, the book is eminently suitable for both beginners and more experienced readers alike.Preface to the Second Edition Preface to the First Edition Contents 1 Introduction 1.1 What Is Competitive Programming? 1.1.1 Programming Contests 1.1.2 Tips for Practicing 1.2 About This Book 1.3 CSES Problem Set 1.4 Other Resources 2 Programming Techniques 2.1 Language Features 2.1.1 Input and Output 2.1.2 Working with Numbers 2.1.3 Shortening Code 2.2 Recursive Algorithms 2.2.1 Generating Subsets 2.2.2 Generating Permutations 2.2.3 Backtracking 2.3 Bit Manipulation 2.3.1 Bit Operations 2.3.2 Representing Sets 3 Efficiency 3.1 Time Complexity 3.1.1 Calculation Rules 3.1.2 Common Time Complexities 3.1.3 Estimating Efficiency 3.1.4 Formal Definitions 3.2 Algorithm Design Examples 3.2.1 Maximum Subarray Sum 3.2.2 Two Queens Problem 3.3 Code Optimization 3.3.1 Compiler Output 3.3.2 Processor Features 4 Sorting and Searching 4.1 Sorting Algorithms 4.1.1 Bubble Sort 4.1.2 Merge Sort 4.1.3 Sorting Lower Bound 4.1.4 Counting Sort 4.1.5 Sorting in Practice 4.2 Solving Problems by Sorting 4.2.1 Sweep Line Algorithms 4.2.2 Scheduling Events 4.2.3 Tasks and Deadlines 4.3 Binary Search 4.3.1 Implementing the Search 4.3.2 Finding Optimal Solutions 5 Data Structures 5.1 Dynamic Arrays 5.1.1 Vectors 5.1.2 Iterators and Ranges 5.1.3 Other Structures 5.2 Set Structures 5.2.1 Sets and Multisets 5.2.2 Maps 5.2.3 Priority Queues 5.2.4 Policy-Based Sets 5.3 Experiments 5.3.1 Set Versus Sorting 5.3.2 Map Versus Array 5.3.3 Priority Queue Versus Multiset 6 Dynamic Programming 6.1 Basic Concepts 6.1.1 When Greedy Fails 6.1.2 Finding an Optimal Solution 6.1.3 Counting Solutions 6.2 Further Examples 6.2.1 Longest Increasing Subsequence 6.2.2 Paths in a Grid 6.2.3 Knapsack Problems 6.2.4 From Permutations to Subsets 6.2.5 Counting Tilings 7 Graph Algorithms 7.1 Basics of Graphs 7.1.1 Graph Terminology 7.1.2 Graph Representation 7.2 Graph Traversal 7.2.1 Depth-First Search 7.2.2 Breadth-First Search 7.2.3 Applications 7.3 Shortest Paths 7.3.1 Bellman–Ford Algorithm 7.3.2 Dijkstra\'s Algorithm 7.3.3 Floyd–Warshall Algorithm 7.4 Directed Acyclic Graphs 7.4.1 Topological Sorting 7.4.2 Dynamic Programming 7.5 Successor Graphs 7.5.1 Finding Successors 7.5.2 Cycle Detection 7.6 Minimum Spanning Trees 7.6.1 Kruskal\'s Algorithm 7.6.2 Union-Find Structure 7.6.3 Prim\'s Algorithm 8 Algorithm Design Topics 8.1 Bit-Parallel Algorithms 8.1.1 Hamming Distances 8.1.2 Counting Subgrids 8.1.3 Reachability in Graphs 8.2 Amortized Analysis 8.2.1 Two Pointers Method 8.2.2 Nearest Smaller Elements 8.2.3 Sliding Window Minimum 8.3 Finding Minimum Values 8.3.1 Ternary Search 8.3.2 Convex Functions 8.3.3 Minimizing Sums 9 Range Queries 9.1 Queries on Static Arrays 9.1.1 Sum Queries 9.1.2 Minimum Queries 9.2 Tree Structures 9.2.1 Binary Indexed Trees 9.2.2 Segment Trees 9.2.3 Additional Techniques 10 Tree Algorithms 10.1 Basic Techniques 10.1.1 Tree Traversal 10.1.2 Calculating Diameters 10.1.3 All Longest Paths 10.2 Tree Queries 10.2.1 Finding Ancestors 10.2.2 Subtrees and Paths 10.2.3 Lowest Common Ancestors 10.2.4 Merging Data Structures 10.3 Advanced Techniques 10.3.1 Centroid Decomposition 10.3.2 Heavy-Light Decomposition 11 Mathematics 11.1 Number Theory 11.1.1 Primes and Factors 11.1.2 Sieve of Eratosthenes 11.1.3 Euclid\'s Algorithm 11.1.4 Modular Exponentiation 11.1.5 Euler\'s Theorem 11.1.6 Solving Equations 11.2 Combinatorics 11.2.1 Binomial Coefficients 11.2.2 Catalan Numbers 11.2.3 Inclusion-Exclusion 11.2.4 Burnside\'s Lemma 11.2.5 Cayley\'s Formula 11.3 Matrices 11.3.1 Matrix Operations 11.3.2 Linear Recurrences 11.3.3 Graphs and Matrices 11.3.4 Gaussian Elimination 11.4 Probability 11.4.1 Working with Events 11.4.2 Random Variables 11.4.3 Markov Chains 11.4.4 Randomized Algorithms 11.5 Game Theory 11.5.1 Game States 11.5.2 Nim Game 11.5.3 Sprague–Grundy Theorem 11.6 Fourier Transform 11.6.1 Working with Polynomials 11.6.2 FFT Algorithm 11.6.3 Calculating Convolutions 12 Advanced Graph Algorithms 12.1 Strong Connectivity 12.1.1 Kosaraju\'s Algorithm 12.1.2 2SAT Problem 12.2 Complete Paths 12.2.1 Eulerian Paths 12.2.2 Hamiltonian Paths 12.2.3 Applications 12.3 Maximum Flows 12.3.1 Ford–Fulkerson Algorithm 12.3.2 Disjoint Paths 12.3.3 Maximum Matchings 12.3.4 Path Covers 12.4 Depth-First Search Trees 12.4.1 Biconnectivity 12.4.2 Eulerian Subgraphs 12.5 Minimum Cost Flows 12.5.1 Minimum Cost Paths Algorithm 12.5.2 Minimum Weight Matchings 12.5.3 Improving the Algorithm 13 Geometry 13.1 Geometric Techniques 13.1.1 Complex Numbers 13.1.2 Points and Lines 13.1.3 Polygon Area 13.1.4 Distance Functions 13.2 Sweep Line Algorithms 13.2.1 Intersection Points 13.2.2 Closest Pair Problem 13.2.3 Convex Hull Problem 14 String Algorithms 14.1 Basic Topics 14.1.1 Trie Structure 14.1.2 Dynamic Programming 14.2 String Hashing 14.2.1 Polynomial Hashing 14.2.2 Applications 14.2.3 Collisions and Parameters 14.3 Z-Algorithm 14.3.1 Constructing the Z-Array 14.3.2 Applications 14.4 Suffix Arrays 14.4.1 Prefix Doubling Method 14.4.2 Finding Patterns 14.4.3 LCP Arrays 14.5 String Automata 14.5.1 Regular Languages 14.5.2 Pattern Matching Automata 14.5.3 Suffix Automata 15 Additional Topics 15.1 Square Root Techniques 15.1.1 Data Structures 15.1.2 Subalgorithms 15.1.3 Integer Partitions 15.1.4 Mo\'s Algorithm 15.2 Segment Trees Revisited 15.2.1 Lazy Propagation 15.2.2 Dynamic Trees 15.2.3 Data Structures in Nodes 15.2.4 Two-Dimensional Trees 15.3 Treaps 15.3.1 Splitting and Merging 15.3.2 Implementation 15.3.3 Additional Techniques 15.4 Dynamic Programming Optimization 15.4.1 Convex Hull Trick 15.4.2 Divide and Conquer Optimization 15.4.3 Knuth\'s Optimization 15.5 Backtracking Techniques 15.5.1 Pruning the Search Tree 15.5.2 Heuristic Functions 15.6 Miscellaneous 15.6.1 Meet in the Middle 15.6.2 Counting Subsets 15.6.3 Parallel Binary Search 15.6.4 Dynamic Connectivity Appendix Mathematical Background A.1 Sum Formulas A.2 Sets A.3 Logic A.4 Functions A.5 Logarithms A.6 Number Systems References References Index