Introduction to Computing
Explorations in Language, Logic, and Machines
David
Evans
Computer science studies how to describe, predict properties of, and efficiently implement information processes. This book introduces the most important ideas in computing using the Scheme and Python programming languages. It focuses on how to describe information processes by defining procedures, how to analyze the costs required to carry out a procedure, and the fundamental limits of what can and cannot be computed mechanically.
Errata (last update: 24 June 2019)
Contents
Front Matter [PDF]
Preface [PDF]
Introduction
Chapter 1: Computing [PDF]
1.1 Processes, Procedures, and Computers
1.2 Measuring Computing Power (Information, Representing Data, Growth of Computing Power)
1.3 Science, Engineering, and the Liberal Arts
1.4 Summary and Roadmap
1.2 Measuring Computing Power (Information, Representing Data, Growth of Computing Power)
1.3 Science, Engineering, and the Liberal Arts
1.4 Summary and Roadmap
Exercises and solutions: PDF
Part I: Defining Procedures
Chapter 2: Language [PDF]
2.1 Surface Forms and Meanings
2.2 Language Construction
2.3 Recursive Transition Networks
2.4 Replacement Grammars
2.5 Summary
2.2 Language Construction
2.3 Recursive Transition Networks
2.4 Replacement Grammars
2.5 Summary
Exercises and solutions: PDF
Chapter 3: Programming [PDF]
3.1 Problems with Natural Languages
3.2 Programming Languages
3.3 Scheme
3.4 Expressions (Primitives, Application Expressions)
3.5 Definitions
3.6 Procedures (Making Procedures, Substitution Model of Evaluation)
3.7 Decisions
3.8 Evaluation Rules
3.9 Summary
3.2 Programming Languages
3.3 Scheme
3.4 Expressions (Primitives, Application Expressions)
3.5 Definitions
3.6 Procedures (Making Procedures, Substitution Model of Evaluation)
3.7 Decisions
3.8 Evaluation Rules
3.9 Summary
Exercises and solutions: PDF
Chapter 4: Problems and Procedures [PDF]
4.1 Solving Problems
4.2 Composing Procedures (Procedures as Inputs and Outputs)
4.3 Recursive Problem Solving
4.4 Evaluating Recursive Applications
4.5 Developing Complex Programs (Printing. Tracing)
4.6 Summary
4.2 Composing Procedures (Procedures as Inputs and Outputs)
4.3 Recursive Problem Solving
4.4 Evaluating Recursive Applications
4.5 Developing Complex Programs (Printing. Tracing)
4.6 Summary
Exercises and solutions: PDF
Chapter 5: Data [PDF]
Part II: Analyzing Procedures
Chapter 6: Machines [PDF]
6.1 History of Computing Machines
6.2 Mechanizing Logic (Implementing Logic, Composing Operations, Arithmetic)
6.3 Modeling Computing (Turing Machines)
6.4 Summary
6.2 Mechanizing Logic (Implementing Logic, Composing Operations, Arithmetic)
6.3 Modeling Computing (Turing Machines)
6.4 Summary
Chapter 7: Cost [PDF]
7.1 Empirical Measurements
7.2 Orders of Growth (Big O, Omega, Theta)
7.3 Analyzing Procedures (Input Size, Running Time, Worst Case Input)
7.2 Orders of Growth (Big O, Omega, Theta)
7.3 Analyzing Procedures (Input Size, Running Time, Worst Case Input)
7.4 Growth Rates (No Growth: Constant Time, Linear Growth, Quadratic
Growth, Exponential Growth, Faster than Exponential Growth, Non-terminating Procedures)
7.5 Summary
Chapter 8: Sorting and Searching [PDF]
8.1 Sorting (Best-First Sort, Insertion Sort, Quicker
Sorting, Binary Trees, Quicksort)
8.2 Searching (Unstructured Search, Binary Search, Indexed Search)
8.3 Summary
8.2 Searching (Unstructured Search, Binary Search, Indexed Search)
8.3 Summary
Part III: Improving Expressiveness
Chapter 9: Mutation [PDF]
9.1 Assignment
9.2 Impact of Mutation (Names, Places, Frames, and Environments; Evaluation Rules with State)
9.3 Mutable Pairs and Lists
9.4 Imperative Programming (List Mutators, Imperative Control Structures)
9.5 Summary
9.2 Impact of Mutation (Names, Places, Frames, and Environments; Evaluation Rules with State)
9.3 Mutable Pairs and Lists
9.4 Imperative Programming (List Mutators, Imperative Control Structures)
9.5 Summary
Chapter 10: Objects [PDF]
10.1 Packaging Procedures and State (Encapsulation, Messages, Object Terminology)
10.2 Inheritance (Implementing Subclasses, Overriding Methods)
10.3 Object-Oriented Programming
10.4 Summary
10.2 Inheritance (Implementing Subclasses, Overriding Methods)
10.3 Object-Oriented Programming
10.4 Summary
Chapter 11: Interpreters [PDF]
11.1 Python (Python Programs, Data Types, Applications and Invocations, Control Statements)
11.2 Parser
11.5 Summary
11.2 Parser
11.3 Evaluator (Primitives, If Expressions, Definitions and Names,
Procedures, Application, Finishing the Interpreter)
11.4 Lazy Evaluation (Lazy Interpreter, Lazy Programming)11.5 Summary
Part IV: The Limits of Computing
Chapter 12: Computability [PDF]
12.1 Mechanizing Reasoning (Gödel's Incompleteness Theorem)
12.2 The Halting Problem
12.3 Universality
12.4 Proving Non-Computability
12.5 Summary
12.2 The Halting Problem
12.3 Universality
12.4 Proving Non-Computability
12.5 Summary
Indexes [PDF]
Previous versions: Fall 2011 Edition, Spring 2010 Edition, Fall 2009 Edition, Spring 2009 Edition
|
This work is licensed under a Creative Commons Attribution-Noncommercial-Share Alike 3.0 United States License. |