home libri books Fumetti ebook dvd top ten sconti 0 Carrello


Torna Indietro

skiena steven s. - the algorithm design manual

The Algorithm Design Manual




Disponibilità: Normalmente disponibile in 15 giorni


PREZZO
81,98 €
NICEPRICE
77,88 €
SCONTO
5%



Questo prodotto usufruisce delle SPEDIZIONI GRATIS
selezionando l'opzione Corriere Veloce in fase di ordine.


Pagabile anche con Carta della cultura giovani e del merito, 18App Bonus Cultura e Carta del Docente


Facebook Twitter Aggiungi commento


Spese Gratis

Dettagli

Genere:Libro
Lingua: Inglese
Editore:

Springer

Pubblicazione: 10/2020
Edizione: 3rd ed. 2020





Trama

Most professional programmers that I’ve encountered are not well prepared to tacklealgorithmdesignproblems.Thisisapity,becausethetechniquesofalgorithm design form one of the core practical technologies of computer science. Designing correct, e?cient, and implementable algorithms for real-world problems requires access to two distinct bodies of knowledge: • Techniques – Good algorithm designers understand several fundamental - gorithm design techniques, including data structures, dynamic programming, depth-?rst search, backtracking, and heuristics. Perhaps the single most - portantdesigntechniqueismodeling,theartofabstractingamessyreal-world application into a clean problem suitable for algorithmic attack. • Resources – Good algorithm designers stand on the shoulders of giants. Ratherthanlaboringfromscratchtoproduceanewalgorithmforeverytask, they can ?gure out what is known about a particular problem. Rather than re-implementing popular algorithms from scratch, they seek existing imp- mentations to serve as a starting point. They are familiar with many classic algorithmic problems, which provide su?cient source material to model most any application. This book is intended as a manual on algorithm design, providing access to combinatorial algorithm technology for both students and computer professionals.




Sommario

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 . . . .





Autore

Dr. Steven S. Skiena is Distinguished Teaching Professor of Computer Science at Stony Brook University, with research interests in data science, natural language processing, and algorithms. He was awarded the IEEE Computer Science and Engineering Undergraduate Teaching Award “for outstanding contributions to undergraduate education ...and for influential textbooks and software.”  











Altre Informazioni

ISBN:

9783030542559

Condizione: Nuovo
Collana: Texts in Computer Science
Dimensioni: 235 x 178 mm Ø 1569 gr
Formato: Copertina rigida
Illustration Notes:XVII, 793 p. 1 illus.
Pagine Arabe: 793
Pagine Romane: xvii


Dicono di noi