ผลต่างระหว่างรุ่นของ "204211-src-51-1"

รุ่นแก้ไขปัจจุบันเมื่อ 05:04, 14 กันยายน 2551

การนับ
- นับเบื้องต้น เส้นตรง, วงกลม, nCr, nPr
- inclusion-exclusion techniques
  - bijections
- advanced counting (placing rods)

Proof Techniques
- logics
- direct proof
- indirect proof
- proof by contradiction

$ --- absence, to be covered

review basic induction & counting.
inclusion-exclusion principles.
using bijection in counting. (without actually define what a bijection is)
- a bijection between subsets and bitstrings
- a bijection between odd-sized subsets and even-sized subsets
  - gave out idea of the bijection without proof: will be in homework
- proof of the inclusion-exclusion principle (sketch)

review of modular arithmatics
- basic identities
- if $\gcd(a,b)=1$ $\gcd(a,b)=1$ then $a^{-1}{\pmod {p}}$ $a^{-1}{\pmod {p}}$ exists.
  - the proof didn't use the fact that a pair $x,y$ such that $ax+by=\gcd(a,b)$ exists
RSA, Euler's Theorem, and Fermat's Little Theorem (without proofs)
TODO: (Homework) RSA by hand, Proof of Fermat's Little Theorem
NEXT: Proof of Euler's Theorem and correctness of RSA

Number Theory
- Review of RSA, why hacking RSA is hard, its assumption (hard to factor large numbers)
  - Need large primes to do RSA
- Primality testing
  - Testing in exponential time ($O(p)$ and $O(\sqrt{p})$ for testing $p$)
    - Proved (quick): for a composite $a$, one of its factor must be at most $\sqrt{a}$
  - Testing based on Fermat's Little Theorem
    - Implementation of the test: Repeated squaring
    - Success probability of the test and Carmicheal number
  - Proof of Fermat's Little Theorem
- Euler Theorem and RSA
  - Idea of the proof of Euler Theorem (should be completed in h.w.)
  - Euler Theorem => Correctness of RSA
Recursions
- Recursive definition and counting
- Recursive algorithms, divide and conquer

@@ แถว 18: / แถว 18: @@
 *** strong induction
 *** examples used: tiling, placing dominoes, induction on matrices, Fibonacci numbers
-*** recursive thinking $
+*** recursive thinking
-** Pigeon-Hole Principle $
+** Pigeon-Hole Principle
 ** diagonalization
@@ แถว 28: / แถว 28: @@
 ** modular arithematics
 ** Fermat's Little Theorem
-** polynomials $
+** polynomials
-** secret sharing, coding $
+** secret sharing, erasure codes
-** RSA $
+** RSA
+* Stable marriage
+* Intro to Graph theory
 $ --- absence, to be covered
@@ แถว 68: / แถว 72: @@
 **** Success probability of the test and [http://en.wikipedia.org/wiki/Carmichael_number Carmicheal number]
 *** Proof of Fermat's Little Theorem
-** Proof of Euler Theorem and RSA
+** Euler Theorem and RSA
+*** Idea of the proof of Euler Theorem (should be completed in h.w.)
+*** Euler Theorem => Correctness of RSA
 * Recursions
 ** Recursive definition and counting
 ** Recursive algorithms, divide and conquer
+===14 ก.ย. 51===
+====เช้า====
+* polynomials and codes
+** polynomials: two properties:
+*** any degree-$d$ polynomial has at most $d$ roots.
+*** any degree-$d$ polynomial can be determined exactly with $d+1$ points.
+** polynomial interpolation
+*** by solving a system of linear equations
+*** using Lagrange method
+====บ่าย====
+* polynomials and codes (cont.)
+** finite fields
+** secret sharing
+** erasure codes
+* stable matching