الگوریتمستان

برنامه‌نویسی، طراحی الگوریتم و حل مسئله‌های الگوریتمی

 
در صورت ناخوانا بودن نوشته‌ها، از مرورگر دیگری استفاده کنید.
کتاب Competetive Programming - الگوریتمستان
الگوریتمستان
  »  

کتاب Competetive Programming

        معرفی کتاب Competitive Programming برای علاقه‌مندان به شرکت در مسابقات برنامه‌نویسی و المپیاد کامپیوتر با قابلیت دانلود نسخه‌ی الکترونیکی

ویراست سوم کتاب برنامه‌نویسی رقابتی با نام کامل Competitive Programming 3: The New Lower Bound of Programming Contests با تلاش Steven Halim و Felix Halim از مربیان تیم‌های برنامه‌نویسی ACM-ICPC سنگاپور تالیف و  در سال ۲۰۱۳ منتشر شده است که امروزه به عنوان یکی از منابع مناسب برای آمادگی تیم‌های شرکت‌کننده در مسابقات برنامه‌نویسی الگوریتمی بویژه مسابقات برنامه‌نوسی ACM-ICPC توصیه می‌شود.

این کتاب شامل نکات تکنیکی برنامه‌نویسی در مسابقات ACM-ICPC و همینطور معرفی ساختمان داده‌ها و الگوریتم‌های پر کاربرد در ۹ فصل با جزئیات زیر است.

1 Introduction

    1.1 Competitive Programming

    1.2 Tips to be Competitive

        1.2.1 Tip 1: Type Code Faster!

        1.2.2 Tip 2: Quickly Identify Problem Types

        1.2.3 Tip 3: Do Algorithm Analysis

        1.2.4 Tip 4: Master Programming Languages

        1.2.5 Tip 5: Master the Art of Testing Code

        1.2.6 Tip 6: Practice andMore Practice

        1.2.7 Tip 7: TeamWork (for ICPC)

    1.3 Getting Started: The Easy Problems

        1.3.1 Anatomy of a Programming Contest Problem

        1.3.2 Typical Input/Output Routines

        1.3.3 Time to Start the Journey

    1.4 The Ad Hoc Problems

2 Data Structures and Libraries

    2.1 Overview and Motivation

    2.2 Linear DS with Built-in Libraries

    2.3 Non-Linear DS with Built-in Libraries

    2.4 Data Structures with Our Own Libraries

        2.4.1 Graph

        2.4.2 Union-Find Disjoint Sets

        2.4.3 Segment Tree

        2.4.4 Binary Indexed (Fenwick) Tree

3 Problem Solving Paradigms

    3.1 Overview and Motivation

    3.2 Complete Search

        3.2.1 Iterative Complete Search

        3.2.2 Recursive Complete Search3.2.3 Tips

    3.3 Divide and Conquer

        3.3.1 Interesting Usages of Binary Search

    3.4 Greedy

        3.4.1 Examples

    3.5 Dynamic Programming

        3.5.1 DP Illustration

        3.5.2 Classical Examples

        3.5.3 Non-Classical Examples

4 Graph

    4.1 Overview and Motivation

    4.2 Graph Traversal

        4.2.1 Depth First Search (DFS)

        4.2.2 Breadth First Search (BFS)

        4.2.3 Finding Connected Components (Undirected Graph)

        4.2.4 Flood Fill - Labeling/Coloring the Connected Components

        4.2.5 Topological Sort (Directed Acyclic Graph)

        4.2.6 Bipartite Graph Check

        4.2.7 Graph Edges Property Check via DFS Spanning Tree

        4.2.8 Finding Articulation Points and Bridges (Undirected Graph)

        4.2.9 Finding Strongly Connected Components (Directed Graph)

    4.3 Minimum Spanning Tree

        4.3.1 Overview and Motivation

        4.3.2 Kruskals Algorithm

        4.3.3 Prims Algorithm

        4.3.4 Other Applications

    4.4 Single-Source Shortest Paths

        4.4.1 Overview and Motivation

        4.4.2 SSSP on Unweighted Graph

        4.4.3 SSSP on Weighted Graph

        4.4.4 SSSP on Graph with Negative Weight Cycle

    4.5 All-Pairs Shortest Paths

        4.5.1 Overview and Motivation

        4.5.2 Explanation of Floyd Warshalls DP Solution

        4.5.3 Other Applications

    4.6 Network Flow

        4.6.1 Overview and Motivation

        4.6.2 Ford Fulkersons Method

        4.6.3 Edmonds Karps Algorithm

        4.6.4 Flow Graph Modeling - Part 1

        4.6.5 Other Applications

        4.6.6 Flow Graph Modeling - Part 2

    4.7 Special Graphs

        4.7.1 Directed Acyclic Graph

        4.7.2 Tree

        4.7.3 Eulerian Graph

        4.7.4 Bipartite Graph

5 Mathematics

    5.1 Overview and Motivation

    5.2 Ad Hoc Mathematics Problems

    5.3 Java BigInteger Class

        5.3.1 Basic Features

        5.3.2 Bonus Features

    5.4 Combinatorics

        5.4.1 Fibonacci Numbers

        5.4.2 Binomial Coefficients

        5.4.3 Catalan Numbers

        5.4.4 Remarks about Combinatorics in Programming Contests

    5.5 Number Theory

        5.5.1 Prime Numbers

        5.5.2 Greatest Common Divisor & Least Common Multiple

        5.5.3 Factorial

        5.5.4 Finding Prime Factors with Optimized Trial Divisions

        5.5.5 Working with Prime Factors

        5.5.6 Functions Involving Prime Factors

        5.5.7 Modified Sieve

        5.5.8 Modulo Arithmetic

        5.5.9 Extended Euclid: Solving Linear Diophantine Equation

        5.5.10 Remarks about Number Theory in Programming Contests

    5.6 Probability Theory

    5.7 Cycle-Finding

        5.7.1 Solution(s) using Efficient Data Structure

        5.7.2 Floyds Cycle-Finding Algorithm

    5.8 Game Theory

        5.8.1 Decision Tree

        5.8.2 Mathematical Insights to Speed-up the Solution

    5.8.3 Nim Game

6 String Processing

    6.1 Overview and Motivation

    6.2 Basic String Processing Skills

    6.3 Ad Hoc String Processing Problems

    6.4 String Matching

        6.4.1 Library Solutions

        6.4.2 Knuth-Morris-Pratts (KMP) Algorithm

        6.4.3 StringMatching in a 2D Grid

    6.5 String Processing with Dynamic Programming

        6.5.1 String Alignment (Edit Distance)

        6.5.2 Longest Common Subsequence

        6.5.3 Non Classical String Processing with DP

    6.6 Suffix Trie/Tree/Array

        6.6.1 Suffix Trie and Applications

        6.6.2 Suffix Tree

        6.6.3 Applications of Suffix Tree

        6.6.4 Suffix Array

        6.6.5 Applications of Suffix Array

7 (Computational) Geometry

    7.1 Overview and Motivation

    7.2 Basic Geometry Objects with Libraries

        7.2.1 0D Objects: Points

        7.2.2 1D Objects: Lines

        7.2.3 2D Objects: Circles

        7.2.4 2D Objects: Triangles

        7.2.5 2D Objects: Quadrilaterals

    7.3 Algorithmon Polygon with Libraries

        7.3.1 Polygon Representation

        7.3.2 Perimeter of a Polygon

        7.3.3 Area of a Polygon

        7.3.4 Checking if a Polygon is Convex

        7.3.5 Checking if a Point is Inside a Polygon

        7.3.6 Cutting Polygon with a Straight Line

        7.3.7 Finding the Convex Hull of a Set of Points

    7.4 Solution to Non-Starred Exercises

8 More Advanced Topics

    8.1 Overview and Motivation

    8.2 More Advanced Search Techniques

        8.2.1 Backtracking with Bitmask

        8.2.2 Backtracking with Heavy Pruning

        8.2.3 State-Space Search with BFS or Dijkstras

        8.2.4 Meet in theMiddle (Bidirectional Search)

        8.2.5 Informed Search: A* and IDA*

    8.3 More Advanced DP Techniques

        8.3.1 DP with Bitmask

        8.3.2 Compilation of Common (DP) Parameters

        8.3.3 Handling Negative Parameter Values with Offset Technique

        8.3.4 MLE? Consider Using Balanced BST asMemo Table

        8.3.5 MLE/TLE? Use Better State Representation

        8.3.6 MLE/TLE? Drop One Parameter, Recover It fromOthers

    8.4 Problem Decomposition

        8.4.1 Two Components: Binary Search the Answer and Other

        8.4.2 Two Components: Involving 1D Static RSQ/RMQ

        8.4.3 Two Components: Graph Preprocessing and DP

        8.4.4 Two Components: Involving Graph

        8.4.5 Two Components: InvolvingMathematics

        8.4.6 Two Components: Complete Search and Geometry.

        8.4.7 Two Components: Involving Efficient Data Structure

        8.4.8 Three Components

9 Rare Topics

    9.1 2-SAT Problem

    9.2 Art Gallery Problem

    9.3 Bitonic Traveling Salesman Problem

    9.4 Bracket Matching

    9.5 Chinese Postman Problem

    9.6 Closest Pair

    9.7 Dinics Algorithm

    9.8 Formulas or Theorems

    9.9 Gaussian Elimination Algorithm

    9.10 GraphMatching

    9.11 Great-Circle Distance

    9.12 Hopcroft Karps Algorithm

    9.13 Independent and Edge-Disjoint Paths

    9.14 Inversion Index

    9.15 Josephus Problem

    9.16 Knight Moves

    9.17 Kosarajus Algorithm

    9.18 Lowest Common Ancestor

    9.19 Magic Square Construction (Odd Size

    9.20 Matrix Chain Multiplication

    9.21 Matrix Power

    9.22 MaxWeighted Independent Set

    9.23 Min Cost (Max) Flow

    9.24 Min Path Cover on DAG

    9.25 Pancake Sorting

    9.26 Pollards rho Integer Factoring Algorithm

    9.27 Postfix Calculator and Conversion

    9.28 Roman Numerals

    9.29 Selection Problem

    9.30 Shortest Path Faster Algorithm

    9.31 Sliding Window

    9.32 Sorting in Linear Time

    9.33 Sparse Table Data Structure

    9.34 Tower of Hanoi

زبان برنامه‌نویسی استفاده شده در کتاب ++C است و از مجموعه سوالات UVA Online Judge و همینطور المپیاد کامپیوتر دانش‌آموزی برای آموزش یا تمرین استفاده‌ی فراوانی شده که در انتهای هر فصل پاسخ برخی از تمرین‌ها آمده است. همچنین می‌توان درستی پاسخ تمرین‌های کتاب را از طریق وب‌سایت uHunt بررسی کرد.

نسخه‌ی الکترونیکی ویراست سوم این کتاب از این پیوند قابل دریافت است که اصلاحات آن برای اعمال در ویراست چهارم در این پیوند آمده است.

به اشتراک‌گذاری نوشته
اشتراک‌گذاری در LinkedIn     Cloob     اشتراک‌گذاری در Twitter     اشتراک‌گذاری در Facebook     ارسال با Telegram
امتیاز نوشته
  • 1
  • 2
  • 3
  • 4
  • 5

نام: *  

پست الکترونیک:

وبگاه:

متن پیام: *

01 02 03 04 05 06 07 08 09 10 11 12 13 14

 


الگوریتمستان در تلگرام

   

 

پیوند کوتاه: عمر نوشته:  ۷۲ روز
کل بازدید:  ۱۲۱۴ بازدید
تعداد امتیاز:  ۰ امتیاز
میانگین امتیاز:  ۰.۰۰  از  ۵.۰۰
»  ابزار CodinGame
        معرفی وب‌سایت CodinGame.com برای تمرین برنامه‌نویسی و حل مسئله با پیاده‌سازی عامل بازی
»  کتاب مقدمه‌ای بر مسابقات برنامه‌نویسی
        معرفی کتاب فارسی «مقدمه‌ای بر مسابقات برنامه‌نویسی» برای علاقه‌مندان به مباحث الگوریتم‌ها و شرکت‌کنندگان در مسابقات برنامه‌نویسی با امکان دانلود نسخه‌ی الکترونیکی
»  کتاب راهنمای برنامه‌نویسان رقابتی
        معرفی کتاب Competitive Programmer's Handbook (راهنمای برنامه‌نویسان رقابتی) برای علاقه‌مندان به مباحث الگوریتم‌ها و شرکت‌کنندگان در مسابقات برنامه‌نویسی با امکان دانلود
»  دوره‌ی طراحی و تحلیل الگوریتم دانشگاه استنفورد
        ویدئوهای آموزشی دوره‌ی Algorithms: Design and Analysis دانشگاه استنفورد با زیرنویس انگلیسی
»  راه حل سوالات مسابقه‌ی جهانی ACM-ICPC 2016
        راه حل سوالات مسابقه‌ی جهانی ACM-ICPC 2016
»  ویدئوهای آموزشی کلاس Programming Challenges
        ویدئوهای آموزشی کلاس Programming Challenges شامل مباحث الگوریتم‌ها، ساختمان داده‌ها و ریاضیات محاسباتی برای آمادگی مسابقات برنامه‌نویسی
»  کتاب الکترونیکی ساختمان داده‌ها
        معرفی کتاب آموزش الکترونیکی رایگان «ساختمان داده‌ها» به زبان فارسی با قابلیت دانلود
»  کتاب طراحی الگوریتم با رویکردی خلاقانه
        معرفی کتاب Introduction to Algorithms: A Creative Approach  با قابلیت دانلود نسخه‌ی الکترونیکی
»  کتاب مقدمه‌ای بر الگوریتم‌ها
        معرفی کتاب Introduction to Algorithms (ویراست سوم) به عنوان مرجع مباحث طراحی الگوریتم‌ها و ساختمان داده‌ها با قابلیت دانلود
»  کتاب Concrete Mathematics
        معرفی کتاب Concrete Mathematics برای علاقه‌مندان حل سوالات الگوریتمی و شرکت‌کنندگان مسابقات برنامه‌نویسی با قابلیت دانلود
»  کتاب چالش‌های برنامه‌نویسی
        معرفی کتاب Programming Challenges برای علاقه‌مندان حل سوالات الگوریتمی و شرکت‌کنندگان مسابقات برنامه‌نویسی با قابلیت دانلود کتاب، فایل‌های صوتی، تصویری و اسلایدهای کلاس درس نویسنده
»  کتاب هنر مسابقات برنامه‌نویسی
        معرفی کتاب Art of Programming Contest برای علاقه‌مندان حل سوالات الگوریتمی و شرکت‌کنندگان مسابقات برنامه‌نویسی با قابلیت دانلود نسخه‌ی الکترونیکی