Cantitate/Preț
Produs

Mathematical Foundations of Computer Science

Autor Ashwin Lall
en Limba Engleză Paperback – 5 noi 2024
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. For instance, sets motivate the study of finite automata, direct proof is practised using closure properties, induction is used to prove the language of an automaton, and contradiction is used to apply the pumping lemma. 
The main content of the book starts with primitive data types such as sets and strings and ends with showing the undecidability of the halting problem. There are also appendix chapters on combinatorics, probability, elementary number theory, asymptotic notation, graphs, loop invariants, and recurrences. The content is laid out concisely with a heavy reliance on worked examples, of which there are over 250 in the book. Each chapter has exercises, totalling 550. 
This class-tested textbook is targeted to intermediate Computer Science majors, and it is primarily intended for a discrete math / proofs course in a Computer Science major. It is also suitable for introductory theory of computation courses.
Citește tot Restrânge

Toate formatele și edițiile

Toate formatele și edițiile Preț Express
Paperback (1) 25775 lei  3-5 săpt.
  CRC Press – 5 noi 2024 25775 lei  3-5 săpt.
Hardback (1) 67093 lei  3-5 săpt.
  CRC Press – 5 noi 2024 67093 lei  3-5 săpt.

Preț: 25775 lei

Preț vechi: 37328 lei
-31% Nou

Puncte Express: 387

Preț estimativ în valută:
4933 5204$ 4111£

Carte disponibilă

Livrare economică 12-26 decembrie

Preluare comenzi: 021 569.72.76

Specificații

ISBN-13: 9781032467870
ISBN-10: 1032467878
Pagini: 236
Ilustrații: 112
Dimensiuni: 178 x 254 x 17 mm
Greutate: 0.42 kg
Ediția:1
Editura: CRC Press
Colecția Chapman and Hall/CRC
Locul publicării:Boca Raton, United States

Public țintă

Undergraduate Advanced and Undergraduate Core

Cuprins

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) ?     
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  

Notă biografică

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.

Descriere

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.