[Search] |

ABOUT:
[Introduction]POINTERS:
[Texts]## 68: Computer science |

Computer science, today more accurately a separate discipline, considers a number of rather mathematical topics. In addition to computability questions arising from many problems in discrete mathematics, and logic questions related to recursion theory, one must consider scheduling questions, stochastic models, and so on.

Computer Science is no more about computers than astronomy is about telescopes.

For papers involving machine computations and programs in a specific mathematical area, See Section --04 in that area. This includes computational issues in group theory, number theory, statistics, and so on.

In particular, for numerical linear algebra see linear algebra, and for graph-theoretic questions such as the traveling salesman problem or scheduling algorithms, see Combinatorics.

Issues of numerical stability of algorithms, rates of convergence, and so on form the field of numerical analysis.

For cellular automata see Dynamical systems

The word programming in this context is essentially unrelated to the use of the word in e.g. Linear Programming. For that topic see 90: Optimization.

This image slightly hand-edited for clarity.

- 68M: Computer system organization
- 68N: Software
- 68P: Theory of data. Includes sorting(68P10). (For encryption, see 94A,Information and communication.)
- 68Q: Theory of computing. For Turing machines see 03D10.
- 68R: Discrete mathematics in relation to computer science
- 68T: Artificial intelligence, see also 92J40
- 68U: Computing methodologies including Computer graphics and computational geometry
- 68W: Algorithms {For numerical algorithms, see 65-XX; for combinatorics and graph theory, see 68Rxx} [new in 2000] Includes 68W30: Symbolic computation, algebraic computation

This is among the largest areas in the Math Reviews database. This is largely because subfield 68Q (computing theory) is among the largest of the three-digits subfields in the database; the extent to which that literature is part of mathematics is not clear. Apart from that area (which is nearly half the total), Computer Science would be nearer the average size of the disciplines. Starting in 2000, much of the material in 68Q is moved elsewhere in section 68. Also 68U05 (computational geometry) is one of the largest 5-digit areas.

Section 68 has been reorganized into subdisciplines several times, including in 1990 and 2000. To increase clarity, this map was made using only data from 1991-1999.

Browse all (old) classifications for this area at the AMS.

Surely Knuth, "The Art of Computer Programming":

- Vol. 1: "Fundamental algorithms", Second printing, Addison-Wesley Publishing Co., Reading, Mass.-London-Don Mills, Ont 1969 634 pp. MR44#3530
- Vol. 2: "Seminumerical algorithms", Second edition. Addison-Wesley Publishing Co., Reading, Mass., 1981. 688 pp. ISBN 0-201-03822-6 MR83i:68003 (First edition: MR44#3531)
- Vol. 3: "Sorting and searching", Addison-Wesley Publishing Co., Reading, Mass.-London-Don Mills, Ont., 1973. 722 pp. (1 foldout). MR56#4281

Online Dictionary of computing.

Large bibliography on theory/foundations of computer science

Schank, Roger C., "What is AI, anyway?" The foundations of artificial intelligence, 3--13; Cambridge Univ. Press, Cambridge, 1990. CMP1114137

Kallay, Michael: "Convex hull made easy", Inform. Process. Lett. 22 (1986), no. 3, 161. CMP833183

Van Hove, H.; Verschoren, A.: "What is `epistasis'?", Bull. Belg. Math. Soc. Simon Stevin 5 (1998), no. 1, 69--77. MR99c:68219

- Newsgroups sci.math.symbolic, comp.theory, and comp.parallel carry discussions of both theoretical and practical interest.
- Pointers to sets of course notes for courses in algorithms
- Ebook

For the major all-in-one software products for handling general mathematical problems (e.g. Ma***, Ma****, etc.), see 68W30: Symbolic computation.

Software of more limited scope is usually mentioned on an appropriate page. See in particular the symbolic-computation resources for number theory and commutative algebra; many of the algorithms for those areas is incorporated in the more general-purpose software.

- Artificial Intelligence, CMU
- Digital Bibliography for computer science
- Computer Science Bibliographies
- collection of Computer Science bibliographies
- Search Computer Science and Artificial Intelligence databases, Max-Planck-Institut
- Theoretical Computer Science Papers Database
- American Association for Artificial Intelligence
- A compendium of NP optimization problems
- ACM Brings You the World of Computing
- Computing Research Association (CRA)
- Here are the AMS and Goettingen resource pages for area 68.
- The Complexity and Computation
- UTK archives page.

- Citations for busy-beaver, Turing-machine etc.
- [Offsite] Development of Busy Beaver Turing Machines (with literature review)
- Possibilities for analogue computers (computing by use of predictable physical systems)
- What are these classes of problems: P, NP, NP-complete?
- What does "NP-hard" mean?
- Existence of non-negative integer solutions to a set of linear equations is NP-complete.
- Annotated reading list for programmers (Nick Maclaren)
- Comparative efficiencies of sort algorithms, with C code
- Quickest way to find 10 largest among a set of 100 numbers (say)?
- What functions have antiderivatives which are elementary functions ? Citations and long article by Matthew Wiener.
- Applications of fuzzy logic to clustering and image processing
- NP completeness -- references
- Expected performance of Heapsort
- Finding the Pareto-optimal points in R^n
- Textbooks, overview of the Lambda Calculus
- Computational complexity of reducing Boolean expressions (for Golomb rulers)
- Strings not containing two identical consecutive substrings
- [Offsite]Top 10 algorithms of the 20th century

Last modified 2003/03/14 by Dave Rusin. Mail: