Skip to main content

Discrete Structure

The course is divided into 3 sections:

  1. Mathematical foundations
  2. Discrete structures
  3. Selected topics

Lectures​

Mathematical foundations​

  1. Abstractions, definitions, modular arithmetic, exponents
  2. Data representations, bits, bit strings
  3. Logic, proofs, axioms recursion
  4. Sets
  5. Predicate logic

Discrete structures​

  1. Relations, functions
  2. Graphs
  3. Trees
  4. Digraphs

Selected topics​

  1. Finite state automata and regular languages
  2. Linear algebra
  3. Probability and Baysian reasoning
  4. Program correctness

Learning Resources​

Appendix​

automata

noun
  1. A machine or robot designed to follow a precise sequence of instructions.
  2. A person who acts like a machine or robot, often defined as having a monotonous lifestyle and lacking in emotion.
  3. A formal system, such as finite automaton.
  4. A toy in the form of a mechanical figure.
  5. The self-acting power of the muscular and nervous systems, by which movement is effected without intelligent determination.

axioms

noun
  1. A seemingly self-evident or necessary truth which is based on assumption; a principle or proposition which cannot actually be proved or disproved.
  2. (proof theory) A fundamental assumption that serves as a basis for deduction of theorems; a postulate (sometimes distinguished from postulates as being universally applicable, whereas postulates are particular to a certain science or context).
  3. An established principle in some artistic practice or science that is universally received.