Mathematical Foundations of Computer Science
portes grátis
Mathematical Foundations of Computer Science
Lall, Ashwin
Taylor & Francis Ltd
11/2024
214
Dura
9781032467894
Pré-lançamento - envio 15 a 20 dias após a sua edição
Descrição não disponível.
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
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
Este título pertence ao(s) assunto(s) indicados(s). Para ver outros títulos clique no assunto desejado.
discrete mathematics;combinatorics;probability;elementary number theory;computer science
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
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
Este título pertence ao(s) assunto(s) indicados(s). Para ver outros títulos clique no assunto desejado.
