The Book
An Introduction to Mathematical Computer Science
Author: Kasturi Viswanath
Price : INR.425.00 (About $10.00)
ISBN 978-81-7371-630-0
Page Extent : 304
Year : 2008
Binding : Paperback
Publisher : Universities Press, Hyderabad, India
Copies may be ordered online from here: http://www.universitiespress.com/display.asp?categoryID=26&isbn=978-81-7371-630-0
The Book
An Introduction to Mathematical Computer Science explores an alternative approach to teaching of computer science, an approach that is independent of technology, using a methodology that simultaneously deals with both theory and practice.
The ‘mapcode’ formalism introduced here is based on classical ideas, but this book is the first to explore the possibilities of the formalism extensively to evolve the subject as an area of mathematics. Using only the algebra of sets and maps and no advanced mathematics or formal logic, the book suggests a unified point of view for understanding the structure of finite automata, Turing machines, von Neumann machines, and neural systems. It also introduces a 10-step design process for devising algorithms and verifying their termination and correctness. Recursion and sorting algorithms are examined. Data types and Boolean function theory are explained from a novel point of view. A chapter on topological algorithms relates the mapcode formalism to some tools of analysis and numerical analysis.
The book, with its several illustrative diagrams and exercises, will serve as textbook for mathematics and computer science students at both undergraduate and graduate levels.
Table of Contents:
Foreword by Prof. Kesav Nori
Preface
Chapter 1: Motivation and Notation
1.1 What is a computation?
1.2 Simple Examples
1.3 Notational Conventions
1.4 The Specification Map
1.5 State Space and Program Map
1.6 Input Map and Output Map
1.7 Mapcode Computation
1.8 Complementary Remarks
1.9 Exercises
Chapter 2: Discrete Flows
21. The Limit Map
2.2 Patches and Quilts
2.3 New Maps from Old
2.4 Knuth's Definition of an Algorithm
2.5 Hoare Axiomatics
2.6 Dijkstra's wp Formalism
2.7 Undecidability
2.8 Universality
2.9 Exercises
Chapter 3: Mapcode Machines
3.1 Mapcode Machines
3.2 Documentation
3.3 Standard Programs and Mapcode Algorithms
3.4 Proof Techniques
3.5 Efficiency
3.6 Complemantary Remarks
3.7 Exercises
Chapter 4: Finite Automata
4.1 Definitions
4.2 Examples
4.3 Exercises
Chapter 5: Turing Machines
5.1 Motivation
5.2 Turing Maps
5.3 Recognition and Acceptance of Languages
5.4 Numerical Computations
5.5 Exercises
Chapter 6: What is Programming?
6.1 Formulation of the Problem
6.2 The 10-Step Design Process
6.3 The Dijkstra-Gries Methodology
6.4 Method of Variation of Specificagtions
6.5 Detecting Zero Strings
6.6 Complementary Remarks
6.7 Exercises
Chapter 7: Mapcode Theorems
7.1 Maximum of Two Numbers
7.2 Location and Value of Maximum
7.3 Remainder and Quotient
7.4 Integeral Part of a Square Root
7.5 Integral Powers of Integers
7.6 Dictionary Order of Permutations
7.7 Greatest Common Divisor
7.8 Egyptian Multiplication
7.9 Radix Representation and Change of Base
7.10 The Square Root Revisited
7.11 Fibonacci Numbers
7.12 Towers of Hanoi
7.13 Exercises
Chapter 8: Recursion
8.1 Introduction
8.2 Recursive Computations
8.3 Exercises
Chapter 9: Sorting Algorithms
9.1 Bubblesort
9.2 Subroutine for Bubblesort
9.3 Insertion Sort
9.4 Subroutine for Insertion Sort
9.5 Quicksort
9.6 Subroutine for Quicksort
9.7 Exercises
Chapter 10: Data Types
10.1 Representing Numbers in a Computer
10.2 Preparation
10.3 Unsigned Magnitude
10.4 Addition of Bit Strings
10.5 Addition of Non-Negative Integers
10.6 Signed Magnitude
10.7 Ones' Complements
10.8 Two's Complements
10.9 Addition of Integers
10.10 Decimal Floating Point Representation
10.11 Binary Floating Point Representation
10.12 Exercises
Chapter 11: Boolean Spaces and Maps
11.1 Boolean Algebras
11.2 Boolean Algebras and Logic
11.3 Boolean Polynomials
11.4 Normal Forms
11.5 Decoders and Multiplexers
11.6 Exercises
Chapter 12: What is a Computer?
12.1 A Model Computer
12.2 Machine Language Programming
12.3 Exercises
Chapter 13: Topological Computations
13.1 Introduction
13.2 Definitions and Examples
13.3 The EDSAC Algorithms
13.4 The Real Square Root Algorithm
Chapter 14: Neural Systems
14.1 Learning
14.2 Perceptrons
14.3 Perceptron Convergence Theorems
14.4 Hopfield Nets
14.5 Associative Memories
14.6 General Neural Systems
14.7 Examples of Neural Maps
14.8 Cybenko's Theorem
14.9 The Central Problem
14.10 Multilayer Perceptrons
14.11 Hopfield Nets Revisited
14.12 Exercises
Appendix A Number Representations
Appendix B Arithmetic with Limited Storage
Bibliography/ Index
About the Author:
Kasturi Viswanath received his PhD degree from the Indian Statistical Institute, Kolkata. He worked at the University of Illinois at Urbana-Champaign and the Madurai Kamaraj University before joining the University of Hyderabad in 1978. His interest is in the theory of dynamical systems with special reference to applications in computer science.