Reader Resources
- Accompanying Code
- Accompanying Python Code
- Introduction to Computer Science and Programming OpenCourseWare
- Introduction to Computer Science and Programming edX Course
https://mitpress.mit.edu/books
CONTENTS PREFACE .......................................................................................................xiii ACKNOWLEDGMENTS.....................................................................................xv
CONTENTS PREFACE .......................................................................................................xiii ACKNOWLEDGMENTS.....................................................................................xv
1 GETTING STARTED .................................................................................... 1 ✓
2 INTRODUCTION TO PYTHON ...................................................................... 7 ✓
2.1 The Basic Elements of Python............................................................... 8
2.1.1 Objects, Expressions, and Numerical Types.................................... 9
2.1.2 Variables and Assignment ............................................................ 11
2.1.3 IDLE ............................................................................................ 13
2.2 Branching Programs ........................................................................... 14
2.3 Strings and Input ............................................................................... 16
2.3.1 Input............................................................................................ 18
2.4 Iteration.............................................................................................. 18
3.1 Exhaustive Enumeration .................................................................... 21
3.2 For Loops............................................................................................ 23
3.3 Approximate Solutions and Bisection Search ...................................... 25
3.4 A Few Words About Using Floats ........................................................ 29
3.5 Newton-Raphson ................................................................................ 32
4 FUNCTIONS, SCOPING, and ABSTRACTION ............................................. 34 ✓
4.1 Functions and Scoping ....................................................................... 35
4.1.1 Function Definitions..................................................................... 35
4.1.2 Keyword Arguments and Default Values ....................................... 36
4.1.3 Scoping ........................................................................................ 37
4.2 Specifications ..................................................................................... 41
4.3 Recursion ........................................................................................... 44
4.3.1 Fibonacci Numbers ...................................................................... 45
4.3.2 Palindromes ................................................................................. 48
4.4 Global Variables ................................................................................. 50
4.5 Modules.............................................................................................. 51
4.6 Files ................................................................................................... 53 viii
5 STRUCTURED TYPES, MUTABILITY, AND HIGHER-ORDER FUNCTIONS .. 56 ✓
5.1 Tuples ................................................................................................ 56
5.1.1 Sequences and Multiple Assignment ............................................. 57
5.2 Lists and Mutability ............................................................................ 58
5.2.1 Cloning ........................................................................................ 63
5.2.2 List Comprehension ..................................................................... 63
5.3 Functions as Objects .......................................................................... 64
5.4 Strings, Tuples, and Lists ................................................................... 66
5.5 Dictionaries ........................................................................................ 67
6 TESTING AND DEBUGGING ...................................................................... 70 ✓
6.1 Testing ................................................................................................ 70
6.1.1 Black-Box Testing ........................................................................ 71
6.1.2 Glass-Box Testing ........................................................................ 73
6.1.3 Conducting Tests ......................................................................... 74
6.2 Debugging .......................................................................................... 76
6.2.1 Learning to Debug ........................................................................ 78
6.2.2 Designing the Experiment ............................................................ 79
6.2.3 When the Going Gets Tough ......................................................... 81
6.2.4 And When You Have Found “The” Bug .......................................... 82
7 EXCEPTIONS AND ASSERTIONS .............................................................. 84 ✓
7.1 Handling Exceptions ........................................................................... 84
7.2 Exceptions as a Control Flow Mechanism ........................................... 87
7.3 Assertions ........................................................................................... 90
8 CLASSES AND OBJECT-ORIENTED PROGRAMMING ............................... 91 ✓
8.1 Abstract Data Types and Classes ........................................................ 91
8.1.1 Designing Programs Using Abstract Data Types ............................ 96
8.1.2 Using Classes to Keep Track of Students and Faculty ................... 96
8.2 Inheritance ......................................................................................... 99
8.2.1 Multiple Levels of Inheritance ..................................................... 101
8.2.2 The Substitution Principle .......................................................... 102
8.3 Encapsulation and Information Hiding .............................................. 103
8.3.1 Generators ................................................................................. 106
8.4 Mortgages, an Extended Example ..................................................... 108 ix
9 A SIMPLISTIC INTRODUCTION TO ALGORITHMIC COMPLEXITY............ 113
9.1 Thinking About Computational Complexity ....................................... 113
9.2 Asymptotic Notation.......................................................................... 116
9.3 Some Important Complexity Classes ................................................. 118
9.3.1 Constant Complexity .................................................................. 118
9.3.2 Logarithmic Complexity.............................................................. 118
9.3.3 Linear Complexity ...................................................................... 119
9.3.4 Log-Linear Complexity................................................................ 120
9.3.5 Polynomial Complexity ............................................................... 120
9.3.6 Exponential Complexity.............................................................. 121
9.3.7 Comparisons of Complexity Classes............................................ 123
10 SOME SIMPLE ALGORITHMS AND DATA STRUCTURES......................... 125
10.1 Search Algorithms .......................................................................... 126
10.1.1 Linear Search and Using Indirection to Access Elements .......... 126
10.1.2 Binary Search and Exploiting Assumptions .............................. 128
10.2 Sorting Algorithms .......................................................................... 131
10.2.1 Merge Sort................................................................................ 132
10.2.2 Exploiting Functions as Parameters.......................................... 135
10.2.3 Sorting in Python ..................................................................... 136
10.3 Hash Tables.................................................................................... 137
11 PLOTTING AND MORE ABOUT CLASSES................................................ 141
11.1 Plotting Using PyLab....................................................................... 141
11.2 Plotting Mortgages, an Extended Example....................................... 146
12 STOCHASTIC PROGRAMS, PROBABILITY, AND STATISTICS................... 152
12.1 Stochastic Programs ....................................................................... 153
12.2 Inferential Statistics and Simulation ............................................... 155
12.3 Distributions .................................................................................. 166
12.3.1 Normal Distributions and Confidence Levels............................. 168
12.3.2 Uniform Distributions .............................................................. 170
12.3.3 Exponential and Geometric Distributions ................................. 171
12.3.4 Benford’s Distribution .............................................................. 173
12.4 How Often Does the Better Team Win?............................................ 174
12.5 Hashing and Collisions ................................................................... 177 x
13 RANDOM WALKS AND MORE ABOUT DATA VISUALIZATION ................. 179
13.1 The Drunkard’s Walk ...................................................................... 179
13.2 Biased Random Walks .................................................................... 186
13.3 Treacherous Fields .......................................................................... 191
14 MONTE CARLO SIMULATION .................................................................. 193
14.1 Pascal’s Problem ............................................................................. 194
14.2 Pass or Don’t Pass? ......................................................................... 195
14.3 Using Table Lookup to Improve Performance ................................... 199
14.4 Finding π ........................................................................................ 200
14.5 Some Closing Remarks About Simulation Models ............................ 204
15 UNDERSTANDING EXPERIMENTAL DATA .............................................. 207
15.1 The Behavior of Springs .................................................................. 207
15.1.1 Using Linear Regression to Find a Fit ....................................... 210
15.2 The Behavior of Projectiles .............................................................. 214
15.2.1 Coefficient of Determination ..................................................... 216
15.2.2 Using a Computational Model ................................................... 217
15.3 Fitting Exponentially Distributed Data ............................................ 218
15.4 When Theory Is Missing .................................................................. 221
16 LIES, DAMNED LIES, AND STATISTICS .................................................. 222
16.1 Garbage In Garbage Out (GIGO) ...................................................... 222
16.2 Pictures Can Be Deceiving .............................................................. 223
16.3 Cum Hoc Ergo Propter Hoc ............................................................... 225
16.4 Statistical Measures Don’t Tell the Whole Story ............................... 226
16.5 Sampling Bias ................................................................................. 228
16.6 Context Matters .............................................................................. 229
16.7 Beware of Extrapolation .................................................................. 229
16.8 The Texas Sharpshooter Fallacy ...................................................... 230
16.9 Percentages Can Confuse ................................................................ 232
16.10 Just Beware .................................................................................. 233
17 KNAPSACK AND GRAPH OPTIMIZATION PROBLEMS .............................. 234
17.1 Knapsack Problems ........................................................................ 234
17.1.1 Greedy Algorithms .................................................................... 235
17.1.2 An Optimal Solution to the 0/1 Knapsack Problem ................... 238 xi
17.2 Graph Optimization Problems ......................................................... 240
17.2.1 Some Classic Graph-Theoretic Problems................................... 244
17.2.2 The Spread of Disease and Min Cut.......................................... 245
17.2.3 Shortest Path: Depth-First Search and Breadth-First Search.... 246
18 DYNAMIC PROGRAMMING ..................................................................... 252
18.1 Fibonacci Sequences, Revisited ....................................................... 252
18.2 Dynamic Programming and the 0/1 Knapsack Problem................... 254
18.3 Dynamic Programming and Divide-and-Conquer............................. 261
19 A QUICK LOOK AT MACHINE LEARNING................................................ 262
19.1 Feature Vectors .............................................................................. 264
19.2 Distance Metrics ............................................................................. 266
19.3 Clustering....................................................................................... 270
19.4 Types Example and Cluster............................................................. 272
19.5 K-means Clustering ........................................................................ 274
19.6 A Contrived Example ...................................................................... 276
19.7 A Less Contrived Example............................................................... 280
19.8 Wrapping Up................................................................................... 286
PYTHON 2.7 QUICK REFERENCE................................................................. 287
INDEX .......................................................................................................... 289
Sem comentários:
Enviar um comentário