Algebra for Computer Science
The aim of this book is to teach the reader the topics in algebra which are useful in the study of computer science. In a clear, concise style, the author present the basic algebraic structures, and their applications to such topics as the finite Fourier transform, coding, complexity, and automata t...
Main Authors: | , |
---|---|
Format: | eBook |
Language: | English |
Published: |
New York, NY
Springer New York
1988, 1988
|
Edition: | 1st ed. 1988 |
Series: | Universitext
|
Subjects: | |
Online Access: | |
Collection: | Springer Book Archives -2004 - Collection details see MPG.ReNa |
Table of Contents:
- 5.3 Abstract linear algebra
- Literature
- 6 Algebraic complexity theory
- 6.1 Polynomial rings in several variables
- 6.2 Complexity with respect to multiplication
- 6.3 Appendix. The fast Fourier transform is optimal
- Literature
- 7 Polynomial rings, algebraic fields, finite fields
- 7.1 Divisibility in a polynomial ring
- 7.2 Algebraic numbers and algebraic fields
- 7.3 Finite fields
- Literature
- 8 Shift registers and coding
- 8.1 The theory of shift registers
- 8.2 Generalities about coding
- 8.3 Cyclic codes
- 8.4 The BCH codes and the Reed-Solomon codes
- 8.5 Restrictions for error-correcting codes
- Literature
- 9 Groups
- 9.1 General theory
- 9.2 Finite groups
- Literature
- 10 Boolean algebra
- 10.1 Boolean algebras and rings
- 10.2 Finite Boolean algebras
- 10.3 Equivalence classes of switching functions
- Literature
- 11 Monoids, automata, languages
- 11.1 Matrices with elements in a non-commutative algebra
- 11.2 Monoids and languages
- 11.3 Automata and rational languages
- 11.4 Every rational language is accepted by a finite automaton
- Literature
- References
- 1 Number theory
- 1.1 Divisibility
- 1.2 Congruences
- 1.3 The theorems of Fermat, Euler and Wilson
- 1.4 Squares and the quadratic reciprocity theorem
- 1.5 The Gaussian integers
- 1.6 Algebraic numbers
- 1.7 Appendix. Primitive elements and a theorem by Gauss
- Literature
- 2 Number theory and computing
- 2.1 The cost of arithmetic operations
- 2.2 Primes and factoring
- 2.3 Pseudo-random numbers
- Literature
- 3 Abstract algebra and modules
- 3.1 The four operations of arithmetic
- 3.2 Modules
- 3.3 Module morphisms. Kernels and images
- 3.4 The structure of finite modules
- 3.5 Appendix. Finitely generated modules
- Literature
- 4 The finite Fourier transform
- 4.1 Characters of modules
- 4.2 The finite Fourier transform
- 4.3 The finite Fourier transform and the quadratic reciprocity law
- 4.4 The fast Fourier transform
- Literature
- 5 Rings and fields
- 5.1 Definitions and simple examples
- 5.2 Modules over a ring. Ideals and morphisms