ผลต่างระหว่างรุ่นของ "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

@@ แถว 82: / แถว 82: @@
 ====เช้า====
 * polynomials and codes
-** polynomials, polynomial interpolation
+** 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
-* intro to graph theory
-====บ่าย====
 * stable matching