logo资料库

Python Algorithm（Python 算法教程）PDF版.pdf

发布时间：2022-06-13 发布人：admin 分类：说明书 资料大小：2.70M 资料格式：pdf 举报 版权申诉
第1页 / 共325页
第2页 / 共325页
第3页 / 共325页
第4页 / 共325页
第5页 / 共325页
第6页 / 共325页
第7页 / 共325页
第8页 / 共325页
资料共325页，剩余部分请下载后查看
    Title Page
    Copyright Page
    Contents at a Glance
    Table of Contents
    About the Author
    About the Technical Reviewer
    Acknowledgments
    Preface
    C H A P T E R 1 Introduction
    What’s All This, Then?
    Why Are You Here?
    Some Prerequisites
    What’s in This Book
    Summary
    If You’re Curious …
    Exercises
    References
    C H A P T E R 2 The Basics
    Some Core Ideas in Computing
    Asymptotic Notation
    It’s Greek to Me!
    Rules of the Road
    Taking the Asymptotics for a Spin
    Three Important Cases
    Empirical Evaluation of Algorithms
    Implementing Graphs and Trees
    Adjacency Lists and the Like
    Adjacency Matrices
    Implementing Trees
    A Multitude of Representations
    Beware of Black Boxes
    Hidden Squares
    The Trouble with Floats
    Summary
    If You’re Curious …
    Exercises
    References
    C H A P T E R 3 Counting 101
    The Skinny on Sums
    More Greek
    Working with Sums
    A Tale of Two Tournaments
    Shaking Hands
    The Hare and the Tortoise
    Subsets, Permutations, and Combinations
    Recursion and Recurrences
    Doing It by Hand
    A Few Important Examples
    Guessing and Checking
    The Master Theorem: A Cookie-Cutter Solution
    So What Was All That About?
    Summary
    If You’re Curious …
    Exercises
    References
    C H A P T E R 4 Induction and Recursion ... and Reduction
    Oh, That’s Easy!
    One, Two, Many
    Mirror, Mirror
    Designing with Induction (and Recursion)
    Finding a Maximum Permutation
    The Celebrity Problem
    Topological Sorting
    Stronger Assumptions
    Invariants and Correctness
    Relaxation and Gradual Improvement
    Reduction + Contraposition = Hardness Proof
    Problem Solving Advice
    Summary
    If You’re Curious …
    Exercises
    References
    C H A P T E R 5 Traversal: The Skeleton Key of Algorithmics
    A Walk in the Park
    No Cycles Allowed
    How to Stop Walking in Circles
    Go Deep!
    Depth-First Timestamps and Topological Sorting (Again)
    Infinite Mazes and Shortest (Unweighted) Paths
    Strongly Connected Components
    Summary
    If You’re Curious …
    Exercises
    References
    C H A P T E R 6 Divide, Combine, and Conquer
    Tree-Shaped Problems: All About the Balance
    The Canonical D&C Algorithm
    Searching by Halves
    Traversing Search Trees … with Pruning
    Selection
    Sorting by Halves
    How Fast Can We Sort?
    Three More Examples
    Closest Pair
    Convex Hull
    Greatest Slice
    Tree Balance … and Balancing∗
    Summary
    If You’re Curious …
    Exercises
    References
    C H A P T E R 7 Greed Is Good? Prove It!
    Staying Safe, Step by Step
    The Knapsack Problem
    Fractional Knapsack
    Integer Knapsack
    Huffman’s Algorithm
    The Algorithm
    The First Greedy Choice
    Going the Rest of the Way
    Optimal Merging
    Minimum spanning trees
    The Shortest Edge
    What About the Rest?
    Kruskal’s Algorithm
    Prim’s Algorithm
    Greed Works. But When?
    Keeping Up with the Best
    No Worse Than Perfect
    Staying Safe
    Summary
    If You’re Curious …
    Exercises
    References
    C H A P T E R 8 Tangled Dependencies and Memoization
    Don’t Repeat Yourself
    Shortest Paths in Directed Acyclic Graphs
    Longest Increasing Subsequence
    Sequence Comparison
    The Knapsack Strikes Back
    Binary Sequence Partitioning
    Summary
    If You’re Curious …
    Exercises
    References
    C H A P T E R 9 From A to B with Edsger and Friends
    Propagating Knowledge
    Relaxing like Crazy
    Finding the Hidden DAG
    All Against All
    Far-Fetched Subproblems
    Meeting in the Middle
    Knowing Where You’re Going
    Summary
    If You’re Curious …
    Exercises
    References
    C H A P T E R 10 Matchings, Cuts, and Flows
    Bipartite Matching
    Disjoint Paths
    Maximum Flow
    Minimum Cut
    Cheapest Flow and the Assignment Problem∗
    Some Applications
    Summary
    If You’re Curious …
    Exercises
    References
    C H A P T E R 11 Hard Problems and (Limited) Sloppiness
    Reduction Redux
    Not in Kansas Anymore?
    Meanwhile, Back in Kansas …
    But Where Do You Start? And Where Do You Go from There?
    A Ménagerie of Monsters
    Return of the Knapsack
    Cliques and Colorings
    Paths and Circuits
    When the Going Gets Tough, the Smart Get Sloppy
    Desperately Seeking Solutions
    And the Moral of the Story Is …
    Summary
    If You’re Curious …
    Exercises
    References
    A P P E N D I X A Pendal to the Metal: Accelerating Python
    A P P E N D I X B List of Problems and Algorithms
    Problems
    Algorithms and Data Structures
    A P P E N D I X C Graph Terminology
    A P P E N D I X D Hints for Exercises
    Chapter 1
    Chapter 2
    Chapter 3
    Chapter 4
    Chapter 5
    Chapter 6
    Chapter 7
    Chapter 8
    Chapter 9
    Chapter 10
    Chapter 11
    Index
    Python Algorithms Mastering Basic Algorithms in the Python Language ■ ■ ■ Magnus Lie Hetland
    Python Algorithms: Mastering Basic Algorithms in the Python Language Copyright © 2010 by Magnus Lie Hetland All rights reserved. No part of this work may be reproduced or transmitted in any form or by any means, electronic or mechanical, including photocopying, recording, or by any information storage or retrieval system, without the prior written permission of the copyright owner and the publisher. ISBN-13 (pbk): 978-1-4302-3237-7 ISBN-13 (electronic): 978-1-4302-3238-4 Printed and bound in the United States of America 9 8 7 6 5 4 3 2 1 Trademarked names, logos, and images may appear in this book. Rather than use a trademark symbol with every occurrence of a trademarked name, logo, or image we use the names, logos, and images only in an editorial fashion and to the benefit of the trademark owner, with no intention of infringement of the trademark. The use in this publication of trade names, trademarks, service marks, and similar terms, even if they are not identified as such, is not to be taken as an expression of opinion as to whether or not they are subject to proprietary rights. President and Publisher: Paul Manning Lead Editor: Frank Pohlmann Development Editor: Douglas Pundick Technical Reviewer: Alex Martelli Editorial Board: Steve Anglin, Mark Beckner, Ewan Buckingham, Gary Cornell, Jonathan Gennick, Jonathan Hassell, Michelle Lowman, Matthew Moodie, Duncan Parkes, Jeffrey Pepper, Frank Pohlmann, Douglas Pundick, Ben Renow-Clarke, Dominic Shakeshaft, Matt Wade, Tom Welsh Coordinating Editor: Adam Heath Compositor: Mary Sudul Indexer: Brenda Miller Artist: April Milne Cover Designer: Anna Ishchenko Photo Credit: Kai T. Dragland Distributed to the book trade worldwide by Springer Science+Business Media, LLC., 233 Spring Street, 6th Floor, New York, NY 10013. Phone 1-800-SPRINGER, fax (201) 348-4505, e-mail orders-ny@springer-sbm.com, or visit www.springeronline.com. For information on translations, please e-mail rights@apress.com, or visit www.apress.com. Apress and friends of ED books may be purchased in bulk for academic, corporate, or promotional use. eBook versions and licenses are also available for most titles. For more information, reference our Special Bulk Sales–eBook Licensing web page at www.apress.com/info/bulksales. The information in this book is distributed on an “as is” basis, without warranty. Although every precaution has been taken in the preparation of this work, neither the author(s) nor Apress shall have any liability to any person or entity with respect to any loss or damage caused or alleged to be caused directly or indirectly by the information contained in this work. The source code for this book is available to readers at www.apress.com
    For my students. May your quest for knowledge be richly rewarded.
    &RQWHQWVDWD*ODQFH ■ CONTENTS Contents...................................................................................................................vi About the Author ...................................................................................................xiii About the Technical Reviewer ...............................................................................xiv Acknowledgments ..................................................................................................xv Preface ..................................................................................................................xvi ■ Chapter 1: Introduction........................................................................................1 ■ Chapter 2: The Basics ..........................................................................................9 ■ Chapter 3: Counting 101 ....................................................................................45 ■ Chapter 4: Induction and Recursion … and Reduction......................................71 ■ Chapter 5: Traversal: The Skeleton Key of Algorithmics .................................101 ■ Chapter 6: Divide, Combine, and Conquer........................................................125 ■ Chapter 7: Greed Is Good? Prove It!.................................................................151 ■ Chapter 8: Tangled Dependencies and Memoization .......................................175 ■ Chapter 9: From A to B with Edsger and Friends.............................................199 ■ Chapter 10: Matchings, Cuts, and Flows .........................................................221 ■ Chapter 11: Hard Problems and (Limited) Sloppiness .....................................241 ■ Appendix A: Pedal to the Metal: Accelerating Python .....................................271 ■ Appendix B: List of Problems and Algorithms .................................................275 ■ Appendix C: Graph Terminology.......................................................................285 ■ Appendix D: Hints for Exercises.......................................................................291 ■ Index ................................................................................................................307 v
    ■ CONTENTS &RQWHQWV Contents at a Glance.................................................................................................v About the Author ...................................................................................................xiii About the Technical Reviewer ...............................................................................xiv Acknowledgments ..................................................................................................xv Preface ..................................................................................................................xvi ■ Chapter 1: Introduction........................................................................................1 What’s All This, Then? .....................................................................................................2 Why Are You Here? ..........................................................................................................3 Some Prerequisites .........................................................................................................4 What’s in This Book .........................................................................................................5 Summary .........................................................................................................................6 If You’re Curious … .........................................................................................................6 Exercises .........................................................................................................................7 References.......................................................................................................................7 ■ Chapter 2: The Basics ..........................................................................................9 Some Core Ideas in Computing .......................................................................................9 Asymptotic Notation ......................................................................................................10 It’s Greek to Me! ...................................................................................................................................12 Rules of the Road .................................................................................................................................14 Taking the Asymptotics for a Spin........................................................................................................16 Three Important Cases .........................................................................................................................19 Empirical Evaluation of Algorithms.......................................................................................................20 vi
    ■ CONTENTS Implementing Graphs and Trees....................................................................................23 Adjacency Lists and the Like................................................................................................................25 Adjacency Matrices ..............................................................................................................................29 Implementing Trees..............................................................................................................................32 A Multitude of Representations ............................................................................................................35 Beware of Black Boxes..................................................................................................36 Hidden Squares ....................................................................................................................................37 The Trouble with Floats ........................................................................................................................38 Summary .......................................................................................................................40 If You’re Curious … .......................................................................................................41 Exercises .......................................................................................................................42 References.....................................................................................................................43 ■ Chapter 3: Counting 101 ....................................................................................45 The Skinny on Sums ......................................................................................................45 More Greek ...........................................................................................................................................46 Working with Sums ..............................................................................................................................46 A Tale of Two Tournaments...........................................................................................47 Shaking Hands......................................................................................................................................47 The Hare and the Tortoise ....................................................................................................................49 Subsets, Permutations, and Combinations....................................................................53 Recursion and Recurrences...........................................................................................56 Doing It by Hand ...................................................................................................................................57 A Few Important Examples...................................................................................................................58 Guessing and Checking ........................................................................................................................62 The Master Theorem: A Cookie-Cutter Solution ...................................................................................64 So What Was All That About? ........................................................................................67 Summary .......................................................................................................................68 If You’re Curious … .......................................................................................................69 Exercises .......................................................................................................................69 vii
    ■ CONTENTS References.....................................................................................................................70 ■ Chapter 4: Induction and Recursion … and Reduction......................................71 Oh, That’s Easy!.............................................................................................................72 One, Two, Many.............................................................................................................74 Mirror, Mirror .................................................................................................................76 Designing with Induction (and Recursion).....................................................................81 Finding a Maximum Permutation .........................................................................................................81 The Celebrity Problem ..........................................................................................................................85 Topological Sorting...............................................................................................................................87 Stronger Assumptions ...................................................................................................91 Invariants and Correctness............................................................................................92 Relaxation and Gradual Improvement............................................................................93 Reduction + Contraposition = Hardness Proof ..............................................................94 Problem Solving Advice .................................................................................................95 Summary .......................................................................................................................96 If You’re Curious … .......................................................................................................97 Exercises .......................................................................................................................97 References.....................................................................................................................99 ■ Chapter 5: Traversal: The Skeleton Key of Algorithmics .................................101 A Walk in the Park .......................................................................................................107 No Cycles Allowed ..............................................................................................................................108 How to Stop Walking in Circles ..........................................................................................................109 Go Deep! ......................................................................................................................110 Depth-First Timestamps and Topological Sorting (Again) ..................................................................112 Infinite Mazes and Shortest (Unweighted) Paths.........................................................114 Strongly Connected Components ................................................................................118 Summary .....................................................................................................................121 viii
    分享到：
    赞 收藏

    相关推荐

    资料库

    课程资源

    共收录17145份资料，累计13个分类，关注成员有19位，主要包括：PHP,网络管理,网页制作,Java,.Net,数据库,3G/移动开发,C/C++,游戏开发,嵌入式,讲义,软件测试,专业指导

    热门标签

    PHP 网络管理 网页制作 Java .Net 数据库 3G/移动开发 C/C++ 游戏开发 嵌入式 讲义 软件测试 专业指导

    最新资料