책 이미지
책 정보
· 제목 : Introduction to Computational Thinking: Problem Solving, Algorithms, Data Structures, and More (Paperback)
· 분류 : 외국도서 > 컴퓨터 > 컴퓨터 공학
· ISBN : 9781484270769
· 쪽수 : 657쪽
· 분류 : 외국도서 > 컴퓨터 > 컴퓨터 공학
· ISBN : 9781484270769
· 쪽수 : 657쪽
목차
1 Introduction 1
Models of the world and formalising problems . . 4
What is computational thinking? . . . . . . . . . 6
Computational thinking in a broader context . . . 12
What is to come . . . . . . . . . . . . . . . . . . 15
2 Introducing Python programming 19
Obtaining Python . . . . . . . . . . . . . . . . . 20
Running Python . . . . . . . . . . . . . . . . . . 22
Expressions in Python . . . . . . . . . . . . . . . 22
Logical (or boolean) expressions . . . . . . . . . . 26
Variables . . . . . . . . . . . . . . . . . . . . . . 30
Working with strings . . . . . . . . . . . . . . . . 32
Lists . . . . . . . . . . . . . . . . . . . . . . . . 36
Tuples . . . . . . . . . . . . . . . . . . . . . . . 41
iii
Sets and dictionaries . . . . . . . . . . . . . . . . 42
Input and output . . . . . . . . . . . . . . . . . . 44
Conditional statements (if statements) . . . . . . 47
Loops (for and while) . . . . . . . . . . . . . . . 50
Using modules . . . . . . . . . . . . . . . . . . . 543 Introduction to algorithms 57
Designing algorithms . . . . . . . . . . . . . . . 62
Exercises for sequential algorithms . . . . . . . . 81
Exercises on lists . . . . . . . . . . . . . . . . . . 87
4 Algorithmic eciency 95
The RAM model of a computer and its primitive
operations . . . . . . . . . . . . . . . . . . 97
Types of eciency . . . . . . . . . . . . . . . . . 107
Asymptotic running time and big-Oh notation . . 116
Empirically validating an algorithms running time 135
5 Searching and sorting 141
Searching . . . . . . . . . . . . . . . . . . . . . . 142
Sorting . . . . . . . . . . . . . . . . . . . . . . . 147
Generalising searching and sorting . . . . . . . . 182
How computers represent numbers . . . . . . . . 186
6 Functions 197
Parameters and local and global variables . . . . . 203
Side eects . . . . . . . . . . . . . . . . . . . . . 210
Returning from a function . . . . . . . . . . . . . 215
Higher order functions . . . . . . . . . . . . . . . 221
Functions vs function instances . . . . . . . . . . 227
Default parameters and keyword arguments . . . 230
Generalising parameters . . . . . . . . . . . . . . 234
Exceptions . . . . . . . . . . . . . . . . . . . . . 239
Writing your own Python modules . . . . . . . . 251
7 Inner functions 253
A comparison function for a search algorithm . . 256
Counter function . . . . . . . . . . . . . . . . . . 261
Apply . . . . . . . . . . . . . . . . . . . . . . . . 265
Currying functions . . . . . . . . . . . . . . . . . 269
Function composition . . . . . . . . . . . . . . . 274
Thunks and lazy evaluation . . . . . . . . . . . . 276
Decorators . . . . . . . . . . . . . . . . . . . . . 281
Eciency . . . . . . . . . . . . . . . . . . . . . . 288
8 Recursion 291
Denitions of recursion . . . . . . . . . . . . . . 291
Recursive functions . . . . . . . . . . . . . . . . 293
Recursion stacks . . . . . . . . . . . . . . . . . . 297Recursion and iteration . . . . . . . . . . . . . . 307
Tail-calls . . . . . . . . . . . . . . . . . . . . . . 316
Continuations . . . . . . . . . . . . . . . . . . . 324
Continuations, thunks and trampolines . . . . . . 335
9 Divide and conquer and dynamic programming 343
Divide and conquer running times . . . . . . . . 355Dynamic programming . . . . . . . . . . . . . . 371
Representing oating point numbers . . . . . . . 392
10 Hidden Markov models 399
Probabilities . . . . . . . . . . . . . . . . . . . . 399
Conditional probabilities and dependency graphs . 410
Markov models . . . . . . . . . . . . . . . . . . . 412
Hidden Markov models . . . . . . . . . . . . . . 421
Forward algorithm . . . . . . . . . . . . . . . . . 425
Viterbi algorithm . . . . . . . . . . . . . . . . . . 433
11 Data structures, objects and classes 439
Classes . . . . . . . . . . . . . . . . . . . . . . . 441
Exceptions and classes . . . . . . . . . . . . . . . 448
Methods . . . . . . . . . . . . . . . . . . . . . . 453
Magical methods . . . . . . . . . . . . . . . . . . 460
Class variables . . . . . . . . . . . . . . . . . . . 464
Objects, classes, meta-classes, and attributes . . . 471
Return of the decorator . . . . . . . . . . . . . . 494
Polymorphism . . . . . . . . . . . . . . . . . . . 500
Abstract data structures . . . . . . . . . . . . . . 504
12 Class hierarchies and inheritance 507
Inheritance and code reuse . . . . . . . . . . . . 516
Multiple inheritance . . . . . . . . . . . . . . . . 524
Mixins . . . . . . . . . . . . . . . . . . . . . . . 532
13 Sequences 537
Sequences . . . . . . . . . . . . . . . . . . . . . 538Linked lists sequences . . . . . . . . . . . . . . . 540
Doubly linked lists . . . . . . . . . . . . . . . . . 560
A word on garbage collection . . . . . . . . . . . 579
Iterators . . . . . . . . . . . . . . . . . . . . . . 587
Python iterators and other interfaces . . . . . . . 590
Generators . . . . . . . . . . . . . . . . . . . . . 59814 Sets 607
Sets with builtin lists . . . . . . . . . . . . . . . . 612
Linked lists sets . . . . . . . . . . . . . . . . . . . 618
Search trees . . . . . . . . . . . . . . . . . . . . 620
Hash table . . . . . . . . . . . . . . . . . . . . . 648
Dictionaries . . . . . . . . . . . . . . . . . . . . 663
15 Red-black search trees 669
A persistent recursive solution . . . . . . . . . . . 670
An iterative solution . . . . . . . . . . . . . . . . 712
16 Stacks and queues 739
Building stacks and queues from scratch . . . . . 745
Expression stacks and stack machines . . . . . . . 748
Quick-sort and the call stack . . . . . . . . . . . . 761
Writing an iterator for a search tree . . . . . . . . 763
Merge sort with an explicit stack . . . . . . . . . . 768
Breadth-rst tree traversal and queues . . . . . . 775
17 Priority queues 779
A tree representation for a heap . . . . . . . . . . 782
Leftist heaps . . . . . . . . . . . . . . . . . . . . 786Binomial heaps . . . . . . . . . . . . . . . . . . . 794
Binary heaps . . . . . . . . . . . . . . . . . . . . 814
Adding keys and values . . . . . . . . . . . . . . 825
Comparisons . . . . . . . . . . . . . . . . . . . . 842
Human encoding . . . . . . . . . . . . . . . . . 846
18 Conclusions 853Where to go from here . . . . . . . . . . . . . . 855
