Ashwin Lall

Mathematical Foundations of Computer Science

• Gebundenes Buch

Produktbeschreibung

Mathematical Foundations of Computer Science introduces students to the discrete mathematics needed later in their Computer Science coursework with theory of computation topics interleaved throughout. Students learn about mathematical concepts just in time to apply them to theory of computation ideas.

---

Hinweis: Dieser Artikel kann nur an eine deutsche Lieferadresse ausgeliefert werden.

Produktdetails

• Verlag: CRC Press
• Seitenzahl: 214
• Erscheinungstermin: 5. November 2024
• Englisch
• Abmessung: 254mm x 178mm x 14mm
• Gewicht: 612g
• ISBN-13: 9781032467894
• ISBN-10: 1032467894
• Artikelnr.: 70727869

Autorenporträt

Ashwin Lall is Professor of Computer Science at Denison University. He joined the Denison faculty in 2010. Prior to this, he was a postdoctoral researcher at Georgia Tech, a Ph.D. student and Sproull fellow at the University of Rochester, and a math/computer science double major at Colgate University. Dr. Lall has taught all the existing flavors of the introductory Computer Science course as well as advanced topics such as Theory of Computation and Design/Analysis of Algorithms. He also enjoys teaching the Game Design elective in the CS major.

Inhaltsangabe

Preface Chapter 1
Mathematical Data Types 1.1 WHY YOU SHOULD CARE 1.2 SETS 1.3 SET TERMINOLOGY 1.4 SET-BUILDER NOTATION 1.5 UNION, INTERSECTION, DIFFERENCE, COMPLEMENT 1.6 VENN DIAGRAMS 1.7 POWER SETS 1.8 TUPLES AND CARTESIAN PRODUCTS 1.9 FUNCTIONS 1.10 STRINGS 1.11 LANGUAGES 1.12 CHAPTER SUMMARY AND KEY CONCEPTS Chapter 2
Deterministic Finite Automata 2.1 WHY YOU SHOULD CARE 2.2 A VENDING MACHINE EXAMPLE 2.3 FORMAL DEFINITION OF A DFA 2.4 MATCHING PHONE NUMBERS 2.5 COMPUTATIONAL BIOLOGY 2.6 STOP CODONS 2.7 DIVVYING UP CANDY 2.8 DIVISIBILITY IN BINARY 2.9 CHAPTER SUMMARY AND KEY CONCEPTS Chapter 3
Logic 3.1 WHY YOU SHOULD CARE 3.2 LOGICAL STATEMENTS 3.3 LOGICAL OPERATIONS 3.4 TRUTH TABLES 3.5 CONDITIONAL STATEMENTS 3.6 QUANTIFIERS 3.7 BIG-O NOTATION 3.8 NEGATING LOGICAL STATEMENTS 3.9 CHAPTER SUMMARY AND KEY CONCEPTS Chapter 4
Nondeterministic Finite Automata 4.1 WHY YOU SHOULD CARE 4.2 WHY NFAS CAN BE SIMPLER THAN DFAS 4.3 MORE EXAMPLE NFAS 4.4 FORMAL DEFINITION OF AN NFA 4.5 LANGUAGE OF AN NFA 4.6 SUBSET CONSTRUCTION 4.7 NFAS WITH
TRANSITIONS 4.8 CHAPTER SUMMARY AND KEY CONCEPTS Chapter 5
Regular Expressions 5.1 WHY YOU SHOULD CARE 5.2 WHY REGULAR EXPRESSIONS 5.3 REGULAR EXPRESSION OPERATIONS 5.4 FORMAL DEFINITION OF REGULAR EXPRESSIONS 5.5 APPLICATIONS 5.6 REGULAR EXPRESSIONS IN PYTHON 5.7 CHAPTER SUMMARY AND KEY CONCEPTS Chapter 6
Equivalence of Regular Languages and Regular Expressions 6.1 WHY YOU SHOULD CARE 6.2 CONVERTING A REGULAR EXPRESSION TO A
-NFA 6.3 CONVERTING A DFA TO A REGULAR EXPRESSION 6.4 ANOTHER DEFINITION FOR REGULAR LANGUAGES 6.5 CHAPTER SUMMARY AND KEY CONCEPTS Chapter 7
Direct Proof and Closure Properties 7.1 WHY YOU SHOULD CARE 7.2 TIPS FOR WRITING PROOFS 7.3 THE IMPORTANCE OF DEFINITIONS 7.4 NUMERICAL PROOFS 7.5 CLOSURE UNDER SET OPERATIONS 7.6 CHAPTER SUMMARY AND KEY CONCEPTS Chapter 8
Induction 8.1 WHY YOU SHOULD CARE 8.2 INDUCTION AND RECURSION 8.3 AN ANALOGY FOR UNDERSTANDING INDUCTION 8.4 INDUCTION FOR ANALYZING SORTING RUN-TIME 8.5 HOW MANY BIT STRINGS ARE THERE OF LENGTH (AT MOST) N ? 8.6 COMPARING GROWTH OF FUNCTIONS 8.7 COMMON ERRORS WHEN USING INDUCTION 8.8 STRONG INDUCTION 8.9 AN ANALOGY FOR UNDERSTANDING STRONG INDUCTION 8.10 PROOFS WITH REGULAR EXPRESSIONS 8.11 CORRECTNESS OF BINARY SEARCH 8.12 CHAPTER SUMMARY AND KEY CONCEPTS Chapter 9
Proving the Language of a DFA 9.1 WHY YOU SHOULD CARE 9.2 A SIMPLE EXAMPLE 9.3 A MORE INVOLVED EXAMPLE 9.4 AN EXAMPLE WITH SINK STATES 9.5 CHAPTER SUMMARY AND KEY CONCEPTS Chapter 10
Proof by Contradiction 10.1 WHY YOU SHOULD CARE 10.2 OVERVIEW OF THE TECHNIQUE 10.3 WHY YOU CAN'T WRITE
2 AS AN INTEGER FRACTION 10.4 WILL WE RUN OUT OF PRIME NUMBERS? 10.5 THE MINDBENDING NUMBER OF LANGUAGES 10.6 CHAPTER SUMMARY AND KEY CONCEPTS Chapter 11
Pumping Lemma for Regular Languages 11.1 WHY YOU SHOULD CARE 11.2 THE PIGEONHOLE PRINCIPLE 11.3 APPLYING THE PUMPING LEMMA 11.4 SELECTING THE STRING FROM THE LANGUAGE 11.5 SPLITTING THE CHOSEN STRING 11.6 CHOOSING THE NUMBER OF TIMES TO PUMP 11.7 A MORE COMPLEX EXAMPLE 11.8 CHAPTER SUMMARY AND KEY CONCEPTS Chapter 12
Context-Free Grammars 12.1 WHY YOU SHOULD CARE 12.2 AN EXAMPLE CONTEXT-FREE GRAMMAR 12.3 PALINDROMES 12.4 CONTEXT-FREE GRAMMARS FOR REGULAR LANGUAGES 12.5 FORMAL DEFINITION OF CFGS 12.6 CLOSURE UNDER UNION 12.7 APPLICATIONS OF CFGS 12.8 CHAPTER SUMMARY AND KEY CONCEPTS Chapter 13
Turing Machines 13.1 WHY YOU SHOULD CARE 13.2 AN EXAMPLE TURING MACHINE 13.3 FORMAL DEFINITION OF A TURING MACHINE 13.4 RECOGNIZING ADDITION 13.5 CONDITIONAL BRANCHING WITH A TURING MACHINE 13.6 TURING MACHINES CAN ACCEPT ALL REGULAR LANGUAGES 13.7 TURING MACHINES AS COMPUTERS OF FUNCTIONS 13.8 CHAPTER SUMMARY AND KEY CONCEPTS Chapter 14
Computability 14.1 WHY YOU SHOULD CARE 14.2 VARIATIONS OF TURING MACHINES 14.3 THE CHURCH-TURING THESIS 14.4 UNIVERSAL TURING MACHINES 14.5 RECURSIVE AND RECURSIVELY ENUMERABLE LANGUAGES 14.6 A NON-COMPUTABLE PROBLEM 14.7 REDUCTIONS 14.8 PROGRAM COMPARISON 14.9 THE HALTING PROBLEM 14.10CLASSES OF LANGUAGES 14.11CHAPTER SUMMARY AND KEY CONCEPTS Appendix A
Counting A.1 Why you should care A.2 The Multiplication Rule A.3 Arrangements without repeats, order matters A.4 Arrangements without repeats, order doesn't matter A.5 Chapter Summary and Key Concepts Appendix B
Probability B.1 Why you should care B.2 Sample Spaces B.3 Events B.4 Chapter Summary and Key Concepts Appendix C
Elementary Number Theory C.1 Why you should care C.2 Modular arithmetic C.3 Euclid's Algorithm for GCD C.4 Chapter Summary and Key Concepts Appendix D
Asymptotic Notation D.1 Why you should care D.2 Why Asymptotic Notation D.3 Theta notation D.4 Big-O and Big-
notation D.5 Strict bounds D.6 Common Errors D.7 Chapter Summary and Key Concepts Appendix E
Graphs E.1 Why you should care E.2 Formal Definition E.3 Graph Representation E.4 Graph Terminology E.5 Chapter Summary and Key Concepts Appendix F
Loop Invariants F.1 Why you should care F.2 Summing a list F.3 Exponentiation F.4 Insertion Sort F.5 Chapter Summary and Key Concepts Appendix G
Recurrence Relations G.1 Why you should care G.2 Merge Sort G.3 Recursion Tree Method G.4 A Review of Some Log Rules G.5 Substitution Method G.6 Analyzing the Karatsuba-Ofman Algorithm G.7 Chapter Summary and Key Concepts Further Reading Bibliography Index

---

Preface

Chapter 1 - Mathematical Data Types

1.1 WHY YOU SHOULD CARE

1.2 SETS

1.3 SET TERMINOLOGY

1.4 SET-BUILDER NOTATION

1.5 UNION, INTERSECTION, DIFFERENCE, COMPLEMENT

1.6 VENN DIAGRAMS

1.7 POWER SETS

1.8 TUPLES AND CARTESIAN PRODUCTS

1.9 FUNCTIONS

1.10 STRINGS

1.11 LANGUAGES

1.12 CHAPTER SUMMARY AND KEY CONCEPTS

Chapter 2 - Deterministic Finite Automata

2.1 WHY YOU SHOULD CARE

2.2 A VENDING MACHINE EXAMPLE

2.3 FORMAL DEFINITION OF A DFA

2.4 MATCHING PHONE NUMBERS

2.5 COMPUTATIONAL BIOLOGY

2.6 STOP CODONS

2.7 DIVVYING UP CANDY

2.8 DIVISIBILITY IN BINARY

2.9 CHAPTER SUMMARY AND KEY CONCEPTS

Chapter 3 - Logic

3.1 WHY YOU SHOULD CARE

3.2 LOGICAL STATEMENTS

3.3 LOGICAL OPERATIONS

3.4 TRUTH TABLES

3.5 CONDITIONAL STATEMENTS

3.6 QUANTIFIERS

3.7 BIG-O NOTATION

3.8 NEGATING LOGICAL STATEMENTS

3.9 CHAPTER SUMMARY AND KEY CONCEPTS

Chapter 4 - Nondeterministic Finite Automata

4.1 WHY YOU SHOULD CARE

4.2 WHY NFAS CAN BE SIMPLER THAN DFAS

4.3 MORE EXAMPLE NFAS

4.4 FORMAL DEFINITION OF AN NFA

4.5 LANGUAGE OF AN NFA

4.6 SUBSET CONSTRUCTION

4.7 NFAS WITH TRANSITIONS

4.8 CHAPTER SUMMARY AND KEY CONCEPTS

Chapter 5 - Regular Expressions

5.1 WHY YOU SHOULD CARE

5.2 WHY REGULAR EXPRESSIONS

5.3 REGULAR EXPRESSION OPERATIONS

5.4 FORMAL DEFINITION OF REGULAR EXPRESSIONS

5.5 APPLICATIONS

5.6 REGULAR EXPRESSIONS IN PYTHON

5.7 CHAPTER SUMMARY AND KEY CONCEPTS

Chapter 6 - Equivalence of Regular Languages and Regular Expressions

6.1 WHY YOU SHOULD CARE

6.2 CONVERTING A REGULAR EXPRESSION TO A -NFA

6.3 CONVERTING A DFA TO A REGULAR EXPRESSION

6.4 ANOTHER DEFINITION FOR REGULAR LANGUAGES

6.5 CHAPTER SUMMARY AND KEY CONCEPTS

Chapter 7 - Direct Proof and Closure Properties

7.1 WHY YOU SHOULD CARE

7.2 TIPS FOR WRITING PROOFS

7.3 THE IMPORTANCE OF DEFINITIONS

7.4 NUMERICAL PROOFS

7.5 CLOSURE UNDER SET OPERATIONS

7.6 CHAPTER SUMMARY AND KEY CONCEPTS

Chapter 8 - Induction

8.1 WHY YOU SHOULD CARE

8.2 INDUCTION AND RECURSION

8.3 AN ANALOGY FOR UNDERSTANDING INDUCTION

8.4 INDUCTION FOR ANALYZING SORTING RUN-TIME

8.5 HOW MANY BIT STRINGS ARE THERE OF LENGTH (AT MOST) N ?

8.6 COMPARING GROWTH OF FUNCTIONS

8.7 COMMON ERRORS WHEN USING INDUCTION

8.8 STRONG INDUCTION

8.9 AN ANALOGY FOR UNDERSTANDING STRONG INDUCTION

8.10 PROOFS WITH REGULAR EXPRESSIONS

8.11 CORRECTNESS OF BINARY SEARCH

8.12 CHAPTER SUMMARY AND KEY CONCEPTS

Chapter 9 - Proving the Language of a DFA

9.1 WHY YOU SHOULD CARE

9.2 A SIMPLE EXAMPLE

9.3 A MORE INVOLVED EXAMPLE

9.4 AN EXAMPLE WITH SINK STATES

9.5 CHAPTER SUMMARY AND KEY CONCEPTS

Chapter 10 - Proof by Contradiction

10.1 WHY YOU SHOULD CARE

10.2 OVERVIEW OF THE TECHNIQUE

10.3 WHY YOU CAN'T WRITE 2 AS AN INTEGER FRACTION

10.4 WILL WE RUN OUT OF PRIME NUMBERS?

10.5 THE MINDBENDING NUMBER OF LANGUAGES

10.6 CHAPTER SUMMARY AND KEY CONCEPTS

Chapter 11 - Pumping Lemma for Regular Languages

11.1 WHY YOU SHOULD CARE

11.2 THE PIGEONHOLE PRINCIPLE

11.3 APPLYING THE PUMPING LEMMA

11.4 SELECTING THE STRING FROM THE LANGUAGE

11.5 SPLITTING THE CHOSEN STRING

11.6 CHOOSING THE NUMBER OF TIMES TO PUMP

11.7 A MORE COMPLEX EXAMPLE

11.8 CHAPTER SUMMARY AND KEY CONCEPTS

Chapter 12 - Context-Free Grammars

12.1 WHY YOU SHOULD CARE

12.2 AN EXAMPLE CONTEXT-FREE GRAMMAR

12.3 PALINDROMES

12.4 CONTEXT-FREE GRAMMARS FOR REGULAR LANGUAGES

12.5 FORMAL DEFINITION OF CFGS

12.6 CLOSURE UNDER UNION

12.7 APPLICATIONS OF CFGS

12.8 CHAPTER SUMMARY AND KEY CONCEPTS

Chapter 13 - Turing Machines

13.1 WHY YOU SHOULD CARE

13.2 AN EXAMPLE TURING MACHINE

13.3 FORMAL DEFINITION OF A TURING MACHINE

13.4 RECOGNIZING ADDITION

13.5 CONDITIONAL BRANCHING WITH A TURING MACHINE

13.6 TURING MACHINES CAN ACCEPT ALL REGULAR LANGUAGES

13.7 TURING MACHINES AS COMPUTERS OF FUNCTIONS

13.8 CHAPTER SUMMARY AND KEY CONCEPTS

Chapter 14 - Computability

14.1 WHY YOU SHOULD CARE

14.2 VARIATIONS OF TURING MACHINES

14.3 THE CHURCH-TURING THESIS

14.4 UNIVERSAL TURING MACHINES

14.5 RECURSIVE AND RECURSIVELY ENUMERABLE LANGUAGES

14.6 A NON-COMPUTABLE PROBLEM

14.7 REDUCTIONS

14.8 PROGRAM COMPARISON

14.9 THE HALTING PROBLEM

14.10CLASSES OF LANGUAGES

14.11CHAPTER SUMMARY AND KEY CONCEPTS

Appendix A - Counting

A.1 Why you should care

A.2 The Multiplication Rule

A.3 Arrangements without repeats, order matters

A.4 Arrangements without repeats, order doesn't matter

A.5 Chapter Summary and Key Concepts

Appendix B - Probability

B.1 Why you should care

B.2 Sample Spaces

B.3 Events

B.4 Chapter Summary and Key Concepts

Appendix C - Elementary Number Theory

C.1 Why you should care

C.2 Modular arithmetic

C.3 Euclid's Algorithm for GCD

C.4 Chapter Summary and Key Concepts

Appendix D - Asymptotic Notation

D.1 Why you should care

D.2 Why Asymptotic Notation

D.3 Theta notation

D.4 Big-O and Big- notation

D.5 Strict bounds

D.6 Common Errors

D.7 Chapter Summary and Key Concepts

Appendix E - Graphs

E.1 Why you should care

E.2 Formal Definition

E.3 Graph Representation

E.4 Graph Terminology

E.5 Chapter Summary and Key Concepts

Appendix F - Loop Invariants

F.1 Why you should care

F.2 Summing a list

F.3 Exponentiation

F.4 Insertion Sort

F.5 Chapter Summary and Key Concepts

Appendix G - Recurrence Relations

G.1 Why you should care

G.2 Merge Sort

G.3 Recursion Tree Method

G.4 A Review of Some Log Rules

G.5 Substitution Method

G.6 Analyzing the Karatsuba-Ofman Algorithm

G.7 Chapter Summary and Key Concepts

Further Reading

Bibliography

Index