Saltar al contenido ForoHackers

Discrete mathematics: start here

Matemática discreta
#3135 · · Citar · Denunciar

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

No has iniciado sesión, así que esto se publica como anónimo: no se guarda con ello ninguna cuenta, nombre ni dirección, y no puede llevar enlaces ni imágenes. Inicia sesión o únete para publicar con tu nombre. Los registros de nuestro servidor web guardan la dirección y la hora de cada petición hasta 14 días; para que la tuya no quede en ellos, usa Tor. Para escribir al equipo de forma confidencial, usa el buzón. Firmar como fuente habitual (una clave guardada solo en este navegador)

Enviar tarda unos segundos aquí: tu navegador resuelve antes una prueba de trabajo contra el spam.

Responder