The Algorithm Design Manual
Steven S.Skiena
ㅣ
Springer
제휴몰 주문 시 고객보상, 일부 이벤트 참여 및 증정품 증정, 하루/당일 배송에서 제외되므로 참고 바랍니다.
{*DRAFT*}
Introduction to Algorithm Design
Algorithm Analysis
Data Structures
Sorting and Searching
Divide and Conquer
Randomized Algorithms and Hashing
Graph Traversal
Weighted Graph Algorithms
Combinatorial Search and Heuristic Methods
Dynamic Programming
NP-Completeness
Dealing with Hard Problems
How to Design Algorithms
14 A Catalog of Algorithmic Problems 437
15 Data Structures 439
15.1 Dictionaries . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 440
15.2 Priority Queues . . . . . . . . . . . . . . . . . . . . . . . . . . . . 445
15.3 Sux Trees and Arrays . . . . . . . . . . . . . . . . . . . . . . . 448
15.4 Graph Data Structures . . . . . . . . . . . . . . . . . . . . . . . . 452
15.5 Set Data Structures . . . . . . . . . . . . . . . . . . . . . . . . . 456
15.6 Kd-Trees . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 460
16 Numerical Problems 465
16.1 Solving Linear Equations . . . . . . . . . . . . . . . . . . . .... . . 467
16.2 Bandwidth Reduction . . . . . . . . . . . . . . . . . . . . . . . . 470
16.3 Matrix Multiplication . . . . . . . . . . . . . . . . . . . . . . . . 472
16.4 Determinants and Permanents . . . . . . . . . . . . . . . . . . . 475
16.5 Constrained/Unconstrained Optimization . . . . . . . . . . . . . 478
16.6 Linear Programming . . . . . . . . . . . . . . . . . . . . . . . . . 482
16.7 Random Number Generation . . . . . . . . . . . . . . . . . . . . 486
16.8 Factoring and Primality Testing . . . . . . . . . . . . . . . . . . . 490
16.9 Arbitrary-Precision Arithmetic . . . . . . . . . . . . . . . . . . . 493
16.10Knapsack Problem . . . . . . . . . . . . . . . . . . . . . . . . . . 497
16.11Discrete Fourier Transform . . . . . . . . . . . . . . . . . . . . . 501
17 Combinatorial Problems 505
17.1 Sorting . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 506
17.2 Searching . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 510
17.3 Median and Selection . . . . . . . . . . . . . . . . . . . . . . . . . 514
17.4 Generating Permutations . . . . . . . . . . . . . . . . . . . . . . 517
17.5 Generating Subsets . . . . . . . . . . . . . . . . . . . . . . . . . . 521
17.6 Generating Partitions . . . . . . . . . . . . . . . . . . . . . . . . 524
17.7 Generating Graphs . . . . . . . . . . . . . . . . . . . . . . . . . . 528
17.8 Calendrical Calculations . . . . . . . . . . . . . . . . . . . . . . . 532
17.9 Job Scheduling . . . . . . . . . . . . . . . . . . . . . . . . . . . . 534
17.10Satisability . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 537
18 Graph Problems: Polynomial-Time 541
18.1 Connected Components . . . . . . . . . . . . . . . . . . . . . . . 542
18.2 Topological Sorting . . . . . . . . . . . . . . . . . . . . . . . . . . 546
18.3 Minimum Spanning Tree . . . . . . . . . . . . . . . . . . . . . . . 549
18.4 Shortest Path . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 554
18.5 Transitive Closure and Reduction . . . . . . . . . . . . . . . . . . 559
18.6 Matching . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 562
18.7 Eulerian Cycle/Chinese Postman . . . . . . . . . . . . . . . . . . 565
18.8 Edge and Vertex Connectivity . . . . . . . . . . . . . . . . . . . . 568
16 CONTENTS
18.9 Network Flow . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 571
18.10Drawing Graphs Nicely . . . . . . . . . . . . . . . . . . . . . . . 574
18.11Drawing Trees . . . . . . . . . . . . . . . . . . . . . . . . . . . . 578
18.12Planarity Detection and Embedding . . . . . . . . . . . . . . . . 581
19 Graph Problems: NP-Hard 585
19.1 Clique . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 586
19.2 Independent Set . . . . . . . . . . . . . . . . . . . . . . . . . . . 589
19.3 Vertex Cover . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 591
19.4 Traveling Salesman Problem . . . . . . . . . . . . . . . . . . . . . 594
19.5 Hamiltonian Cycle . . . . . . . . . . . . . . . . . . . . . . . . . . 598
19.6 Graph Partition . . . . . . . . . . . . . . . . . . . . . . . . . . . . 601
19.7 Vertex Coloring . . . . . . . . . . . . . . . . . . . . . . . . . . . . 604
19.8 Edge Coloring . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 608
19.9 Graph Isomorphism . . . . . . . . . . . . . . . . . . . . . . . . . 610
19.10Steiner Tree . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 614
19.11Feedback Edge/Vertex Set . . . . . . . . . . . . . . . . . . . . . . 618
20 Computational Geometry 621
20.1 Robust Geometric Primitives . . . . . . . . . . . . . . . . . . . . 622
20.2 Convex Hull . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 626
20.3 Triangulation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 630
20.4 Voronoi Diagrams . . . . . . . . . . . . . . . . . . . . . . . . . . 634
20.5 Nearest Neighbor Search . . . . . . . . . . . . . . . . . . . . . . . 637
20.6 Range Search . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 641
20.7 Point Location . . . . . . . . . . . . . . . . . . . . . . . . . . . . 644
20.8 Intersection Detection . . . . . . . . . . . . . . . . . . . . . . . . 648
20.9 Bin Packing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 652
20.10Medial-Axis Transform . . . . . . . . . . . . . . . . . . . . . . . . 655
20.11Polygon Partitioning . . . . . . . . . . . . . . . . . . . . . . . . . 658
20.12Simplifying Polygons . . . . . . . . . . . . . . . . . . . . . . . . . 661
20.13Shape Similarity . . . . . . . . . . . . . . . . . . . . . . . . . . . 664
20.14Motion Planning . . . . . . . . . . . . . . . . . . . . . . . . . . . 667
20.15Maintaining Line Arrangements . . . . . . . . . . . . . . . . . . . 671
20.16Minkowski Sum . . . . . . . . . . . . . . . . . . . . . . . . . . . . 674
21 Set and String Problems 677
21.1 Set Cover . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 678
21.2 Set Packing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 682
21.3 String Matching . . . . . . . . . . . . . . . . . . . . . . . . . . . 685
21.4 Approximate String Matching . . . . . . . . . . . . . . . . . . . . 688
21.5 Text Compression . . . . . . . . . . . . . . . . . . . . . . . . . . 693
21.6 Cryptography . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 697
21.7 Finite State Machine Minimization . . . . . . . . . . . . . . . . . 702
21.8 Longest Common Substring/Subsequence . . . . . . . . . . . . . 706
21.9 Shortest Common Superstring . . . . . . . . . . . . . . . . . . . . 709
CONTENTS 17
22 Algorithmic Resources 713
22.1 Algorithm Libraries . . . . . . . . . . . . . . . . . . . . . . . . . 713
22.1.1 LEDA . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 713
22.1.2 CGAL . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 714
22.1.3 Boost Graph Library . . . . . . . . . . . . . . . . . . . . . 714
22.1.4 Netlib . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 714
22.1.5 Collected Algorithms of the ACM . . . . . . . . . . . . . 715
22.1.6 GitHub and SourceForge . . . . . . . . . . . . . . . . . . . 715
22.1.7 The Stanford GraphBase . . . . . . . . . . . . . . . . . . 715
22.1.8 Combinatorica . . . . . . . . . . . . . . . . . . . . . . . . 716
22.1.9 Programs from Books . . . . . . . . . . . . . . . . . . . . 716
22.2 Data Sources . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 717
22.3 Online Bibliographic Resources . . . . . . . . . . . . . . . . . . . 718
22.4 Professional Consulting Services . . . . . . . . . . . . . . . . . . 718
23 Bibliography 719
Index 771
Steven S.Skiena [저]
전체 0개의 구매후기가 있습니다.
인터파크도서는 고객님의 단순 변심에 의한 교환과 반품에 드는 비용은 고객님이 지불케 됩니다.
인터파크 도서는 모든 상품에 대해 배송완료예정일을 웹사이트에 표시하고 있습니다.
<인터파크 직배송 상품>
<업체 직접배송/오픈마켓 상품>
* 세트상품의 경우 부분취소 시 추가 배송비가 부과될 수 있습니다.
;)
전체 0개의 구매후기가 있습니다.
교환 및 반품이 가능한 경우 
상품을 공급 받은 날로부터 7일이내 가능 
상품은 월~토요일 오전 10시 이전 주문분에 대하여 당일 출고/당일 배송완료를 보장하는 상품입니다.
상품은 서울지역/평일 주문분은 당일 출고/익일 배송완료를 보장하며,
상품은, 입고예정일(제품출시일)+택배사배송일(1일)에 배송완료를 보장합니다.
~ 
상품은 유통특성상 인터파크에서 재고를 보유하지 않은 상품으로
상품은 업체가 주문을 확인하고, 출고하기까지 걸리는 시간입니다.
