Mathematical Foundations of Computer Science

1. Auflage 2024
ISBN: 978-1-032-46789-4
Verlag: CRC Press

Buch, Englisch, 228 Seiten, Format (B × H): 178 mm x 254 mm, Gewicht: 612 g

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.

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.

Zielgruppe

Undergraduate Advanced and Undergraduate Core

Autoren/Hrsg.

Lall, Ashwin

Fachgebiete

• Mathematik | Informatik Mathematik Numerik und Wissenschaftliches Rechnen Angewandte Mathematik, Mathematische Modelle
• Mathematik | Informatik Mathematik Mathematik Allgemein Mathematische Logik
• Mathematik | Informatik EDV | Informatik Programmierung | Softwareentwicklung Programmier- und Skriptsprachen
• Mathematik | Informatik EDV | Informatik Informatik
• Mathematik | Informatik Mathematik Mathematik Allgemein Diskrete Mathematik, Kombinatorik
• Mathematik | Informatik EDV | Informatik Business Application Mathematische & Statistische Software
• Mathematik | Informatik EDV | Informatik Programmierung | Softwareentwicklung Spiele-Programmierung, Rendering, Animation

Inhaltsverzeichnis

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

Über Autor(innen)

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.