CS ATLAS A map of computing

Domain 01 —

Foundations & Mathematics

6 topics350 BC — 1948
350 BCFormal Logic1654Probability & Statistics1854Boolean Algebra & Switching Circuits1874Set Theory & Infinity1931Gödel’s Incompleteness Theorems1948Information Theory

Chronology — 27 entries

Chronology

Every milestone in this domain, ordered by date. An event shared by several topics is counted once.

350 BCAristotle, OrganonSystematised the syllogism and introduced the idea of formal validity.Formal Logic
1654Pascal and Fermat correspondProbability is born from a problem about gambling.Probability & Statistics
1713Bernoulli, Ars ConjectandiThe law of large numbers is proved for the first time.Probability & Statistics
1763Bayes' theorem publishedInverse probability and the updating of belief.Probability & Statistics
1854Boole, The Laws of ThoughtDescribed propositional logic in algebra: truth values 0/1, with and, or, not as multiply, add, complement.Formal Logic
1874Cantor proves the reals uncountableThe diagonal argument appears, and infinity splits into different cardinalities.Set Theory & Infinity
1879Frege, BegriffsschriftIntroduced quantifiers and predicates, building the first complete first-order logic.Formal Logic
1901Russell's paradoxNaive set theory develops a crack.Set Theory & Infinity
1908Zermelo's axiomatisationThe axiom of separation restricts how sets may be constructed.Set Theory & Infinity
1922ZFC takes shapeFraenkel and Skolem complete the axiom of replacement.Set Theory & Infinity
1928Hilbert poses the EntscheidungsproblemHe asks for a decision procedure for predicate logic.Gödel’s Incompleteness Theorems
1928Hartley measures information in logarithmsA precursor to Shannon's theory.Information Theory
1930Gödel's completeness theoremSemantic entailment and formal provability in first-order logic coincide exactly.Formal Logic
1931The incompleteness theoremsSelf-reference and coding expose the intrinsic limits of formal systems.Gödel’s Incompleteness Theorems
1933Kolmogorov's axiomatisationProbability becomes part of measure theory.Probability & Statistics
1936Turing defines computabilityThe Turing machine reformulates 'algorithm' and proves the halting problem undecidable.Gödel’s Incompleteness Theorems
1937Shannon's master's thesisProves switching circuits are isomorphic to Boolean algebra: circuit design gains a mathematical tool.Boolean Algebra & Switching Circuits
1948A Mathematical Theory of CommunicationEntropy, channel capacity and rate–distortion arrive together.Information Theory
1950Hamming codesThe first practical error-correcting code.Information Theory
1952Quine–McCluskey algorithmA tabular method for minimal sum-of-products, implementable as a program.Boolean Algebra & Switching Circuits
1953Karnaugh mapsAdjacent minterms in a grid make hand simplification visual.Boolean Algebra & Switching Circuits
1953Rice's theoremEvery non-trivial semantic property of programs is undecidable.Gödel’s Incompleteness Theorems
1963The continuum hypothesis is independentCohen's forcing shows CH cannot be decided from ZFC.Set Theory & Infinity
1970Logic synthesis tools appearSimplification moves from paper into programs, and scale takes off.Boolean Algebra & Switching Circuits
1990MCMC becomes practicalHigh-dimensional posterior inference becomes feasible.Probability & Statistics
1993Turbo codesIterative decoding that approaches the Shannon limit.Information Theory
2008Polar codesAdopted for 5G control channels.Information Theory

Curriculum

Courses and labs

Which university courses this domain usually maps to, and whether the practical work is a standalone project course or an in-class lab.

Problem sets and proofs, almost no lab

Courses like these have almost no lab sessions; assessment is problem sets and proofs, with programming only a supporting tool. Boolean algebra and Karnaugh maps appear as paper exercises inside discrete mathematics.

Courses

Discrete MathematicsLinear AlgebraProbability and StatisticsMathematical Logic (elective)

Open courses

  • MIT 6.042J Mathematics for Computer Science
  • Berkeley CS 70 Discrete Mathematics and Probability Theory

What the labs look like

  • Programming assignments

    Enumerate properties of sets, relations and graphs with code, or check probability results by Monte Carlo

  • Truth tables and Karnaugh maps

    The Boolean-algebra chapter of discrete mathematics: simplify expressions and draw maps, all on paper, with no lab

  • Proof grading

    Most schools assess written proofs; lab hours are close to zero