MARC details
| 000 -LEADER |
|---|
| fixed length control field |
18024nam a22002897a 4500 |
| 003 - CONTROL NUMBER IDENTIFIER |
|---|
| control field |
EG-NcFUE |
| 005 - DATE AND TIME OF LATEST TRANSACTION |
|---|
| control field |
20251127114127.0 |
| 008 - FIXED-LENGTH DATA ELEMENTS--GENERAL INFORMATION |
|---|
| fixed length control field |
251113b ua|||||| |||| 00| 0 eng d |
| 020 ## - INTERNATIONAL STANDARD BOOK NUMBER |
|---|
| International Standard Book Number |
9781032467870 |
| 040 ## - CATALOGING SOURCE |
|---|
| Language of cataloging |
eng |
| 043 ## - GEOGRAPHIC AREA CODE |
|---|
| Geographic area code |
ua |
| 082 #4 - DEWEY DECIMAL CLASSIFICATION NUMBER |
|---|
| Edition number |
23 |
| Classification number |
004.0151 LAM |
| 100 1# - MAIN ENTRY--PERSONAL NAME |
|---|
| Relator term |
AUTHOR. |
| Fuller form of name |
Lall, Ashwin. |
| 245 1# - TITLE STATEMENT |
|---|
| Title |
Mathematical Foundations of Computer Science/ |
| Statement of responsibility, etc |
Ashwin Lall. |
| 250 ## - EDITION STATEMENT |
|---|
| Edition statement |
1st Edition. |
| 264 #1 - PUBLICATION, DISTRIBUTION, ETC. (IMPRINT) |
|---|
| Place of publication, distribution, etc |
Baco Raton: |
| Name of publisher, distributor, etc |
CRC Press, |
| Date of publication, distribution, etc |
©2025. |
| 300 ## - PHYSICAL DESCRIPTION |
|---|
| Extent |
xv, 220 p. : |
| Other physical details |
illustrations ; |
| Dimensions |
18 cm. |
| 336 ## - CONTENT TYPE |
|---|
| Source |
rdacontent |
| Content type term |
text |
| 337 ## - MEDIA TYPE |
|---|
| Source |
rdamedia |
| Media type term |
unmediated |
| 338 ## - CARRIER TYPE |
|---|
| Source |
rdacarrier |
| Carrier type term |
volume |
| 505 ## - FORMATTED CONTENTS NOTE |
|---|
| Formatted contents note |
Chapter 1 ■ Mathematical Data Types<br/>1.1 WHY YOU SHOULD CARE <br/>1.2 SETS <br/>1.3 SET TERMINOLOGY <br/>1.4 SET-BUILDER NOTATION <br/>1.5 UNION, INTERSECTION, DIFFERENCE, COMPLEMENT <br/>1.6 VENN DIAGRAMS <br/>1.7 POWER SETS <br/>1.8 TUPLES AND CARTESIAN PRODUCTS <br/>1.9 FUNCTIONS <br/>1.10 STRINGS <br/>1.11 LANGUAGES <br/>1.12 CHAPTER SUMMARY AND KEY CONCEPTS <br/>Chapter 2 ■ Deterministic Finite Automata <br/>2.1 WHY YOU SHOULD CARE <br/>2.2 A VENDING MACHINE EXAMPLE <br/>2.3 FORMAL DEFINITION OF A DFA <br/>2.4 MATCHING PHONE NUMBERS <br/>2.5 COMPUTATIONAL BIOLOGY <br/>2.6 STOP CODONS <br/>2.7 DIVVYING UP CANDY <br/>2.8 DIVISIBILITY IN BINARY <br/>2.9 CHAPTER SUMMARY AND KEY CONCEPTS <br/>Chapter 3 ■ Logic <br/>3.1 WHY YOU SHOULD CARE <br/>3.2 LOGICAL STATEMENTS <br/>3.3 LOGICAL OPERATIONS <br/>3.4 TRUTH TABLES <br/>3.5 CONDITIONAL STATEMENTS <br/>3.6 QUANTIFIERS <br/>3.7 BIG-O NOTATION <br/>3.8 NEGATING LOGICAL STATEMENTS <br/>3.9 CHAPTER SUMMARY AND KEY CONCEPTS <br/>Chapter 4 ■ Nondeterministic Finite Automata <br/>4.1 WHY YOU SHOULD CARE <br/>4.2 WHY NFAS CAN BE SIMPLER THAN DFAS <br/>4.3 MORE EXAMPLE NFAS <br/>4.4 FORMAL DEFINITION OF AN NFA <br/>4.5 LANGUAGE OF AN NFA <br/>4.6 SUBSET CONSTRUCTION <br/>4.7 NFAS WITH λ TRANSITIONS <br/>4.8 CHAPTER SUMMARY AND KEY CONCEPTS <br/>Chapter 5 ■ Regular Expressions <br/>5.1 WHY YOU SHOULD CARE <br/>5.2 WHY REGULAR EXPRESSIONS <br/>5.3 REGULAR EXPRESSION OPERATIONS <br/>5.4 FORMAL DEFINITION OF REGULAR EXPRESSIONS <br/>5.5 APPLICATIONS <br/>5.6 REGULAR EXPRESSIONS IN PYTHON <br/>5.7 CHAPTER SUMMARY AND KEY CONCEPTS <br/>Chapter 6 ■ Equivalence of Regular Languages and Regular Expressions<br/>6.1 WHY YOU SHOULD CARE <br/>6.2 CONVERTING A REGULAR EXPRESSION TO A λ-NFA <br/>6.3 CONVERTING A DFA TO A REGULAR EXPRESSION <br/>6.4 ANOTHER DEFINITION FOR REGULAR LANGUAGES <br/>6.5 CHAPTER SUMMARY AND KEY CONCEPTS <br/>Chapter 7 ■ Direct Proof and Closure Properties <br/>7.1 WHY YOU SHOULD CARE <br/>7.2 TIPS FOR WRITING PROOFS <br/>7.3 THE IMPORTANCE OF DEFINITIONS <br/>7.4 NUMERICAL PROOFS <br/>7.5 CLOSURE UNDER SET OPERATIONS <br/>7.6 CHAPTER SUMMARY AND KEY CONCEPTS <br/>Chapter 8 ■ Induction <br/>8.1 WHY YOU SHOULD CARE <br/>8.2 INDUCTION AND RECURSION <br/>8.3 AN ANALOGY FOR UNDERSTANDING INDUCTION <br/>8.4 INDUCTION FOR ANALYZING SORTING RUN-TIME <br/>8.5 HOW MANY BIT STRINGS ARE THERE OF LENGTH (AT MOST) N ? <br/>8.6 COMPARING GROWTH OF FUNCTIONS <br/>8.7 COMMON ERRORS WHEN USING INDUCTION <br/>8.8 STRONG INDUCTION <br/>8.9 AN ANALOGY FOR UNDERSTANDING STRONG INDUCTION <br/>8.10 PROOFS WITH REGULAR EXPRESSIONS <br/>8.11 CORRECTNESS OF BINARY SEARCH <br/>8.12 CHAPTER SUMMARY AND KEY CONCEPTS <br/>Chapter 9 ■ Proving the Language of a DFA <br/>9.1 WHY YOU SHOULD CARE <br/>9.2 A SIMPLE EXAMPLE <br/>9.3 A MORE INVOLVED EXAMPLE <br/>9.4 AN EXAMPLE WITH SINK STATES <br/>9.5 CHAPTER SUMMARY AND KEY CONCEPTS <br/>Chapter 10 ■ Proof by Contradiction <br/>10.1 WHY YOU SHOULD CARE <br/>10.2 OVERVIEW OF THE TECHNIQUE <br/>10.3 WHY YOU CAN’T WRITE √2 AS AN INTEGER FRACTION <br/>10.4 WILL WE RUN OUT OF PRIME NUMBERS? <br/>10.5 THE MINDBENDING NUMBER OF LANGUAGES <br/>10.6 CHAPTER SUMMARY AND KEY CONCEPTS <br/>Chapter 11 ■ Pumping Lemma for Regular Languages <br/>11.1 WHY YOU SHOULD CARE <br/>11.2 THE PIGEONHOLE PRINCIPLE <br/>11.3 APPLYING THE PUMPING LEMMA <br/>11.4 SELECTING THE STRING FROM THE LANGUAGE <br/>11.5 SPLITTING THE CHOSEN STRING<br/>11.6 CHOOSING THE NUMBER OF TIMES TO PUMP <br/>11.7 A MORE COMPLEX EXAMPLE <br/>11.8 CHAPTER SUMMARY AND KEY CONCEPTS <br/>Chapter 12 ■ Context-Free Grammars <br/>12.1 WHY YOU SHOULD CARE <br/>12.2 AN EXAMPLE CONTEXT-FREE GRAMMAR <br/>12.3 PALINDROMES <br/>12.4 CONTEXT-FREE GRAMMARS FOR REGULAR LANGUAGES <br/>12.5 FORMAL DEFINITION OF CFGS <br/>12.6 CLOSURE UNDER UNION <br/>12.7 APPLICATIONS OF CFGS <br/>12.8 CHAPTER SUMMARY AND KEY CONCEPTS <br/>Chapter 13 ■ Turing Machines <br/>13.1 WHY YOU SHOULD CARE <br/>13.2 AN EXAMPLE TURING MACHINE <br/>13.3 FORMAL DEFINITION OF A TURING MACHINE <br/>13.4 RECOGNIZING ADDITION <br/>13.5 CONDITIONAL BRANCHING WITH A TURING MACHINE <br/>13.6 TURING MACHINES CAN ACCEPT ALL REGULAR LANGUAGES <br/>13.7 TURING MACHINES AS COMPUTERS OF FUNCTIONS <br/>13.8 CHAPTER SUMMARY AND KEY CONCEPTS <br/>Chapter 14 ■ Computability <br/>14.1 WHY YOU SHOULD CARE <br/>14.2 VARIATIONS OF TURING MACHINES <br/>14.3 THE CHURCH-TURING THESIS <br/>14.4 UNIVERSAL TURING MACHINES <br/>14.5 RECURSIVE AND RECURSIVELY ENUMERABLE LANGUAGES <br/>14.6 A NON-COMPUTABLE PROBLEM <br/>14.7 REDUCTIONS <br/>14.8 PROGRAM COMPARISON <br/>14.9 THE HALTING PROBLEM <br/>14.10CLASSES OF LANGUAGES <br/>14.11CHAPTER SUMMARY AND KEY CONCEPTS <br/>Appendix A ■ Counting<br/>A.1 Why you should care <br/>A.2 The Multiplication Rule <br/>A.3 Arrangements without repeats, order matters <br/>A.4 Arrangements without repeats, order doesn’t matter <br/>A.5 Chapter Summary and Key Concepts <br/>Appendix B ■ Probability <br/>B.1 Why you should care <br/>B.2 Sample Spaces <br/>B.3 Events <br/>B.4 Chapter Summary and Key Concepts <br/>Appendix C ■ Elementary Number Theory <br/>C.1 Why you should care <br/>C.2 Modular arithmetic <br/>C.3 Euclid’s Algorithm for GCD <br/>C.4 Chapter Summary and Key Concepts <br/>Appendix D ■ Asymptotic Notation <br/>D.1 Why you should care <br/>D.2 Why Asymptotic Notation <br/>D.3 Theta notation <br/>D.4 Big-O and Big-Ω notation <br/>D.5 Strict bounds <br/>D.6 Common Errors <br/>D.7 Chapter Summary and Key Concepts <br/>Appendix E ■ Graphs <br/>E.1 Why you should care <br/>E.2 Formal Definition <br/>E.3 Graph Representation <br/>E.4 Graph Terminology <br/>E.5 Chapter Summary and Key Concepts <br/>Appendix F ■ Loop Invariants <br/>F.1 Why you should care <br/>F.2 Summing a list <br/>F.3 Exponentiation <br/>F.4 Insertion Sort <br/>F.5 Chapter Summary and Key Concepts |
| 520 ## - SUMMARY, ETC. |
|---|
| Summary, etc |
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. <br/><br/>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. <br/><br/>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.<br/><br/>The authors hope this book breeds curiosity into the subject and is designed to satisfy this to some extent by reading this book. The book will prepare readers for deeper study of game theory applications in many fields of study. |
| 650 17 - SUBJECT ADDED ENTRY--TOPICAL TERM |
|---|
| Source of heading or term |
qarmk. |
| General subdivision |
Computer science—Mathematics. |
| 650 17 - SUBJECT ADDED ENTRY--TOPICAL TERM |
|---|
| Source of heading or term |
qarmk. |
| General subdivision |
Logic, Symbolic and mathematical. |
| 650 17 - SUBJECT ADDED ENTRY--TOPICAL TERM |
|---|
| Source of heading or term |
qarmk |
| General subdivision |
Computational complexity. |
| 942 ## - ADDED ENTRY ELEMENTS (KOHA) |
|---|
| Source of classification or shelving scheme |
Dewey Decimal Classification |
| Koha item type |
Books |