DiscreteStructures < Main

Main

Main.DiscreteStructuresr1.6 - 27 Sep 2007 - 15:32 - Main.novatopic end

---++ Discrete Structures

Basic Set Theory
   * Functions 
      * surjections and injections
      * inverse
      * composition of functions
   * Relations
      * reflexivity, symmetry, transitivity
      * equivalence relations
   * Sets
      * Definitions,  notation, Venn Diagrams
      * Operators on sets
         * Union
         * Intersection
         * Complement 
         * Power sets
         * Cartesian products
      * Cardinality and countability
         * finite sets
         * countably infinite sets
         * uncountable sets
      * Well orderings

Mathematical (or Computational) logic
   * Propositional logic
      * Logical connectives
      * Boolean functions and formulae
         * Truth tables
         * Normal forms (e.g., conjunctive and disjunctive)
         * Valid, satisfiable, unsatisfiable formulas
   * Predicate logic
      * Universal and existential quantification
      * Limitations of predicate logic
   * Modal logic
      * Temporal logic
   * Model theory
      * Finite model theory
   * Lambda calculus
   * Automated deduction
   * Automated verification
      * Model checking
   * Nonmonotonic reasoning
   * Logic Programming
   * Descriptive Complexity
   * Logics of uncertainty
      * Fuzzy logic
   * Proof Theory
   * Term rewriting systems
   * Constraint programming

Proof techniques
   * Notions of implication, converse, inverse, contrapositive, negation, and contradiction
   * The structure of formal proofs
   * Direct proofs
   * Modus ponens and modus tollens
   * Proof by counterexample
   * Proof by contraposition
   * Proof by contradiction
   * Mathematical induction
      * strong induction
      * weak induction
      * induction on things other than integers

Recursive mathematical definitions

Combinatorics
   * Counting arguments
   * The pigeonhole principle
   * Permutations and combinations
   * Solving recurrence relations
   * Generating functions

Graphs and trees
   * Trees
   * Undirected graphs
   * Directed graphs
   * Hypergraphs
   * Spanning trees
   * Traversal strategies

Discrete probability
   * Finite probability space, probability measure, events
   * Probability measure
   * Events
   * (Discrete) Random variables
   * Expectation
   * Conditional probability
   * Independences
   * Bayes Theorem

to top

End of topic
Skip to action links | Back to top

Edit | Attach image or document | Printable version | Raw text | More topic actions
Revisions: | r1.6 | > | r1.5 | > | r1.4 | Total page history | Backlinks

You are here: Main > DiscreteStructures

to top