Skip to the content ForoHackers
Log inJoin

Discrete mathematics: start here

Discrete mathematics
#3135 · · Quote · Report

Discrete mathematics is the mathematics of countable things: integers, sets, logical statements, graphs and finite structures. Computers work on exactly these, so it is the working language of algorithms, cryptography, databases and proofs. It also teaches the habit of stating a claim precisely and proving it.

Key concepts

  • Logic and proof: implications, quantifiers, direct proof, contradiction and induction.
  • Sets, relations and functions: the vocabulary for describing any structure, including equivalence relations and orderings.
  • Number theory: divisibility, primes, gcd and modular arithmetic, the base of hashing and cryptography.
  • Counting and recurrences: how many objects there are, and how a sequence defines itself.
  • Graphs and trees: the basic model of connected things.

Vocabulary

  • Induction: prove a base case and that each case implies the next, to cover all natural numbers.
  • Congruence: two integers are congruent modulo n when n divides their difference.
  • Bijection: a one-to-one matching between two sets, used to compare sizes.
  • Partial order: a relation that is reflexive, antisymmetric and transitive, as in "divides".

What to study, in order

  1. Propositional logic and truth tables; then write proofs by contradiction and by induction.
  2. Sets, functions and relations, and test equivalence relations in code.
  3. Modular arithmetic: implement Euclid's algorithm and modular exponentiation.
  4. Counting: permutations, combinations, the pigeonhole principle, and recurrences solved by hand.
  5. Graph basics, then a small project that uses several of these together, such as a toy RSA.

Related tags

#combinatorics #graph-theory #logic #cryptography #algorithms

You are not logged in, so this goes up anonymously: no account, no name and no address is stored with it, and it may carry no link and no image. Log in or join to post under your name. Our web server's logs keep the address and time of every request for up to 14 days; to keep yours out of them, use Tor. To reach the staff in confidence, use the drop. Sign as a returning source (a key kept only in this browser)

Sending takes a few seconds here: your browser first works out a proof of work against spam.

Reply