مقدمه‌ای بر محاسبات. کاوش‌هایی در زبان، منطق و ماشین‌ها

Computing Processes, Procedures, and Computers Measuring Computing Power Information Representing Data Growth of Computing Power Science, Engineering, and the Liberal Arts Summary and Roadmap Language Surface Forms and Meanings Language Construction Recursive Transition Networks Replacement Grammars Summary Programming Problems with Natural Languages Programming Languages Scheme Expressions Primitives Application Expressions Definitions Procedures Making Procedures Substitution Model of Evaluation Decisions Evaluation Rules Summary Problems and Procedures Solving Problems Composing Procedures Procedures as Inputs and Outputs Recursive Problem Solving Evaluating Recursive Applications Developing Complex Programs Printing Tracing Summary Data Types Pairs Making Pairs Triples to Octuples Lists List Procedures Procedures that Examine Lists Generic Accumulators Procedures that Construct Lists Lists of Lists Data Abstraction Summary of Part I Machines History of Computing Machines Mechanizing Logic Implementing Logic Composing Operations Arithmetic Modeling Computing Turing Machines Summary Cost Empirical Measurements Orders of Growth Big O Omega Theta Analyzing Procedures Input Size Running Time Worst Case Input Growth Rates No Growth: Constant Time Linear Growth Quadratic Growth Exponential Growth Faster than Exponential Growth Non-terminating Procedures Summary Sorting and Searching Sorting Best-First Sort Insertion Sort Quicker Sorting Binary Trees Quicksort Searching Unstructured Search Binary Search Indexed Search Summary Mutation Assignment Impact of Mutation Names, Places, Frames, and Environments Evaluation Rules with State Mutable Pairs and Lists Imperative Programming List Mutators Imperative Control Structures Summary Objects Packaging Procedures and State Encapsulation Messages Object Terminology Inheritance Implementing Subclasses Overriding Methods Object-Oriented Programming Summary Interpreters Python Python Programs Data Types Applications and Invocations Control Statements Parser Evaluator Primitives If Expressions Definitions and Names Procedures Application Finishing the Interpreter Lazy Evaluation Lazy Interpreter Lazy Programming Summary Computability Mechanizing Reasoning Gödel's Incompleteness Theorem The Halting Problem Universality Proving Non-Computability Summary Indexes Index People