《Introduction.to.Computation.and.Programming.Using.Python.2nd.Edition原版完整文件.docx》由会员分享，可在线阅读，更多相关《Introduction.to.Computation.and.Programming.Using.Python.2nd.Edition原版完整文件.docx（315页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、Introduction to Computation and Programming Using PythonRevised and Expanded EditionJohn V. GuttagIntroduction to Computation and Programming Using PythonIntroduction to Computation and Programming Using PythonRevised and Expanded EditionJohn V. GuttagThe MIT Press Cambridge, MassachusettsLondon, En
2、gland 2013 Massachusetts Institute of TechnologyAll rights reserved. No part of this book may be reproduced in any form by any electronic or mechanical means (including photocopying, recording, or information storage and retrieval) without permission in writing from the publisher.MIT Press books may
3、 be purchased at special quantity discounts for business or sales promotional use. For information, please email special_salesmitpress.mit.edu or write to Special Sales Department, The MIT Press, 55 Hayward Street, Cambridge, MA 02142.Printed and bound in the United States of America.Library of Cong
4、ress Cataloging-in-Publication Data Guttag, John.Introduction to computation and programming using Python / John V. Guttag. Revised and expanded edition.pagescm Includes index.ISBN 978-0-262-52500-8 (pbk. : alk. paper)1. Python (Computer program language) 2. Computer programming. I. Title. QA76.73.P
5、48G882013005.133dc2310987654321To my family:Olga David Andrea Michael Mark AddieCONTENTSPREFACExiiiACKNOWLEDGMENTSxv1 GETTING STARTED12 INTRODUCTION TO PYTHON72.1 The Basic Elements of Python82.1.1 Objects, Expressions, and Numerical Types92.1.2 Variables and Assignment112.1.3 IDLE132.2 Branching Pr
6、ograms142.3 Strings and Input162.3.1 Input182.4 Iteration183 SOME SIMPLE NUMERICAL PROGRAMS213.1 Exhaustive Enumeration213.2 For Loops233.3 Approximate Solutions and Bisection Search253.4 A Few Words About Using Floats293.5 Newton-Raphson324 FUNCTIONS, SCOPING, and ABSTRACTION344.1 Functions and Sco
7、ping354.1.1 Function Definitions354.1.2 Keyword Arguments and Default Values364.1.3 Scoping374.2 Specifications414.3 Recursion444.3.1 Fibonacci Numbers454.3.2 Palindromes484.4 Global Variables504.5 Modules514.6 Files535 STRUCTURED TYPES, MUTABILITY, AND HIGHER-ORDER FUNCTIONS. 565.1 Tuples565.1.1 Se
8、quences and Multiple Assignment575.2 Lists and Mutability585.2.1 Cloning635.2.2 List Comprehension635.3 Functions as Objects645.4 Strings, Tuples, and Lists665.5 Dictionaries676 TESTING AND DEBUGGING706.1 Testing706.1.1 Black-Box Testing716.1.2 Glass-Box Testing736.1.3 Conducting Tests746.2 Debuggin
9、g766.2.1 Learning to Debug786.2.2 Designing the Experiment796.2.3 When the Going Gets Tough816.2.4 And When You Have Found “The” Bug827 EXCEPTIONS AND ASSERTIONS847.1 Handling Exceptions847.2 Exceptions as a Control Flow Mechanism877.3 Assertions908 CLASSES AND OBJECT-ORIENTED PROGRAMMING918.1 Abstr
10、act Data Types and Classes918.1.1 Designing Programs Using Abstract Data Types968.1.2 Using Classes to Keep Track of Students and Faculty968.2 Inheritance998.2.1 Multiple Levels of Inheritance1018.2.2 The Substitution Principle1028.3 Encapsulation and Information Hiding1038.3.1 Generators1068.4 Mort
11、gages, an Extended Example1089 A SIMPLISTIC INTRODUCTION TO ALGORITHMIC COMPLEXITY1139.1 Thinking About Computational Complexity1139.2 Asymptotic Notation1169.3 Some Important Complexity Classes1189.3.1 Constant Complexity1189.3.2 Logarithmic Complexity1189.3.3 Linear Complexity1199.3.4 Log-Linear C
12、omplexity1209.3.5 Polynomial Complexity1209.3.6 Exponential Complexity1219.3.7 Comparisons of Complexity Classes12310 SOME SIMPLE ALGORITHMS AND DATA STRUCTURES12510.1 Search Algorithms12610.1.1 Linear Search and Using Indirection to Access Elements12610.1.2 Binary Search and Exploiting Assumptions1
13、2810.2 Sorting Algorithms13110.2.1 Merge Sort13210.2.2 Exploiting Functions as Parameters13510.2.3 Sorting in Python13610.3 Hash Tables13711 PLOTTING AND MORE ABOUT CLASSES14111.1 Plotting Using PyLab14111.2 Plotting Mortgages, an Extended Example14612 STOCHASTIC PROGRAMS, PROBABILITY, AND STATISTIC
14、S15212.1 Stochastic Programs15312.2 Inferential Statistics and Simulation15512.3 Distributions16612.3.1 Normal Distributions and Confidence Levels16812.3.2 Uniform Distributions17012.3.3 Exponential and Geometric Distributions17112.3.4 Benfords Distribution17312.4 How Often Does the Better Team Win?
15、17412.5 Hashing and Collisions17713 RANDOM WALKS AND MORE ABOUT DATA VISUALIZATION17913.1 The Drunkards Walk17913.2 Biased Random Walks18613.3 Treacherous Fields19114 MONTE CARLO SIMULATION19314.1 Pascals Problem19414.2 Pass or Dont Pass?19514.3 Using Table Lookup to Improve Performance19914.4 Findi
16、ng p20014.5 Some Closing Remarks About Simulation Models20415 UNDERSTANDING EXPERIMENTAL DATA20715.1 The Behavior of Springs20715.1.1 Using Linear Regression to Find a Fit21015.2 The Behavior of Projectiles21415.2.1 Coefficient of Determination21615.2.2 Using a Computational Model21715.3 Fitting Exp
17、onentially Distributed Data21815.4 When Theory Is Missing22116 LIES, DAMNED LIES, AND STATISTICS22216.1 Garbage In Garbage Out (GIGO)22216.2 Pictures Can Be Deceiving22316.3 Cum Hoc Ergo Propter Hoc22516.4 Statistical Measures Dont Tell the Whole Story22616.5 Sampling Bias22816.6 Context Matters2291
18、6.7 Beware of Extrapolation22916.8 The Texas Sharpshooter Fallacy23016.9 Percentages Can Confuse23216.10 Just Beware23317 KNAPSACK AND GRAPH OPTIMIZATION PROBLEMS23417.1 Knapsack Problems23417.1.1 Greedy Algorithms23517.1.2 An Optimal Solution to the 0/1 Knapsack Problem23817.2 Graph Optimization Pr
19、oblems24017.2.1 Some Classic Graph-Theoretic Problems24417.2.2 The Spread of Disease and Min Cut24517.2.3 Shortest Path: Depth-First Search and Breadth-First Search24618 DYNAMIC PROGRAMMING25218.1 Fibonacci Sequences, Revisited25218.2 Dynamic Programming and the 0/1 Knapsack Problem25418.3 Dynamic P
20、rogramming and Divide-and-Conquer26119 A QUICK LOOK AT MACHINE LEARNING26219.1 Feature Vectors26419.2 Distance Metrics26619.3 Clustering27019.4 Types Example and Cluster27219.5 K-means Clustering27419.6 A Contrived Example27619.7 A Less Contrived Example28019.8 Wrapping Up286PYTHON 2.7 QUICK REFEREN
21、CE287INDEX289PREFACEThis book is based on an MIT course that has been offered twice a year since 2006. The course is aimed at students with little or no prior programming experience who have desire to understand computational approaches to problem solving. Each year, a few of the students in the cla
22、ss use the course as a stepping stone to more advanced computer science courses. But for most of the students it will be their only computer science course.Because the course will be the only computer science course for most of the students, we focus on breadth rather than depth. The goal is to prov
23、ide students with a brief introduction to many topics, so that they will have an idea of whats possible when the time comes to think about how to use computation to accomplish a goal. That said, it is not a “computation appreciation” course. It is a challenging and rigorous course in which the stude
24、nts spend a lot of time and effort learning to bend the computer to their will.The main goal of this book is to help you, the reader, become skillful at making productive use of computational techniques. You should learn to apply computational modes of thoughts to frame problems and to guide the pro
25、cess of extracting information from data in a computational manner. The primary knowledge you will take away from this book is the art of computational problem solving.The book is a bit eccentric. Part 1 (Chapters 1-8) is an unconventional introduction to programming in Python. We braid together fou
26、r strands of material: The basics of programming, The Python programming language, Concepts central to understanding computation, and Computational problem solving techniques.We cover most of Pythons features, but the emphasis is on what one can do with a programming language, not on the language it
27、self. For example, by the end of Chapter 3 the book has covered only a small fraction of Python, but it has already introduced the notions of exhaustive enumeration, guess-and-check algorithms, bisection search, and efficient approximation algorithms. We introduce features of Python throughout the b
28、ook. Similarly, we introduce aspects of programming methods throughout the book. The idea is to help you learn Python and how to be a good programmer in the context of using computation to solve interesting problems.Part 2 (Chapters 9-16) is primarily about using computation to solve problems. It as
29、sumes no knowledge of mathematics beyond high school algebra, but it does assume that the reader is comfortable with rigorous thinking and not intimidated by mathematical concepts. It covers some of the usual topics found in an introductory text, e.g., computational complexity and simple algorithms.
30、ACKNOWLEDGMENTSBut the bulk of this part of the book is devoted to topics not found in most introductory texts: data visualization, probabilistic and statistical thinking, simulation models, and using computation to understand data.Part 3 (Chapters 17-19) looks at three slightly advanced topicsoptim
31、ization problems, dynamic programming, and clustering.Part 1 can form the basis of a self-contained course that can be taught in a quarter or half a semester. Experience suggests that it is quite comfortable to fit both Parts 1 and 2 of this book into a full-semester course. When the material in Par
32、t 3 is included, the course becomes more demanding than is comfortable for many students.The book has two pervasive themes: systematic problem solving and the power of abstraction. When you have finished this book you should have: Learned a language, Python, for expressing computations, Learned a sy
33、stematic approach to organizing, writing and debugging medium-sized programs, Developed an informal understanding of computational complexity, Developed some insight into the process of moving from an ambiguous problem statement to a computational formulation of a method for solving the problem, Lea
34、rned a useful set of algorithmic and problem reduction techniques, Learned how to use randomness and simulations to shed light on problems that dont easily succumb to closed-form solutions, and Learned how to use computational tools, including simple statistical and visualization tools, to model and
35、 understand data.Programming is an intrinsically difficult activity. Just as “there is no royal road to geometry,”1 there is no royal road to programming. It is possible to deceive students into thinking that they have learned how to program by having them complete a series of highly constrained “fi
36、ll in the blank” programming problems. However, this does not prepare students for figuring out how to harness computational thinking to solve problems.If you really want to learn the material, reading the book will not be enough. At the very least you should try running some of the code in the book
37、. All of the code in the book can be found at http:/mitpress.mit.edu/ICPPRE. Various versions of the course have been available on MITs OpenCourseWare (OCW) Web site since 2008. The site includes video recordings of lectures and a complete set of problem sets and exams. Since the fall of 2012, edX a
38、nd MITx, have offered an online version of this course. We strongly recommend that you do the problem sets associated with one of the OCW or edX offerings.1 This was Euclids purported response, circa 300 BC, to King Ptolemys request for an easier way to learn mathematics.This book grew out of a set
39、of lecture notes that I prepared while teaching an undergraduate course at MIT. The course, and therefore this book, benefited from suggestions from faculty colleagues (especially Eric Grimson, Srinivas Devadas, and Fredo Durand), teaching assistants, and the students who took the course.The process
40、 of transforming my lecture notes into a book proved far more onerous than I had expected. Fortunately, this misguided optimism lasted long enough to keep me from giving up. The encouragement of colleagues and family also helped keep me going.Eric Grimson, Chris Terman, and David Guttag provided vit
41、al help. Eric, who is MITs Chancellor, managed to find the time to read almost the entire book with great care. He found numerous errors (including an embarrassing, to me, number of technical errors) and pointed out places where necessary explanations were missing. Chris also read parts of the manus
42、cript and discovered errors. He also helped me battle Microsoft Word, which we eventually persuaded to do most of what we wanted. David overcame his aversion to computer science, and proofread multiple chapters.Preliminary versions of this book were used in the MIT course 6.00 and the MITx course 6.
43、00x. A number of students in these courses pointed out errors. One 6.00x student, J.C. Cabrejas, was particularly helpful. He found a large number of typos, and more than a few technical errors.Like all successful professors, I owe a great deal to my graduate students. The photo on the back cover of
44、 this book depicts me supporting some of my current students. In the lab, however, it is they who support me. In addition to doing great research (and letting me take some of the credit for it), Guha Balakrishnan, Joel Brooks, Ganeshapillai Gartheeban, Jen Gong, Yun Liu, Anima Singh, Jenna Wiens, an
45、d Amy Zhao all provided useful comments on this manuscript.I owe a special debt of gratitude to Julie Sussman, P.P.A. Until I started working with Julie, I had no idea how much difference an editor could make. I had worked with capable copy editors on previous books, and thought that was what I need
46、ed for this book. I was wrong. I needed a collaborator who could read the book with the eyes of a student, and tell me what needed to be done, what should be done, and what could be done if I had the time and energy to do it.Julie buried me in “suggestions” that were too good to ignore. Her combined
47、 command of both the English language and programming is quite remarkable.Finally, thanks to my wife, Olga, for pushing me to finish and for pitching in at critical times.1GETTING STARTEDA computer does two things, and two things only: it performs calculations and it remembers the results of those calculations. But it does those two things extremely well. The typical computer