ผลต่างระหว่างรุ่นของ "204211-src-51-1"
ไปยังการนำทาง
ไปยังการค้นหา
Jittat (คุย | มีส่วนร่วม) |
|||
| (ไม่แสดง 9 รุ่นระหว่างกลางโดยผู้ใช้ 2 คน) | |||
| แถว 18: | แถว 18: | ||
*** strong induction | *** strong induction | ||
*** examples used: tiling, placing dominoes, induction on matrices, Fibonacci numbers | *** examples used: tiling, placing dominoes, induction on matrices, Fibonacci numbers | ||
| − | *** recursive thinking | + | *** recursive thinking |
| − | ** Pigeon-Hole Principle | + | ** Pigeon-Hole Principle |
** diagonalization | ** diagonalization | ||
| แถว 28: | แถว 28: | ||
** modular arithematics | ** modular arithematics | ||
** Fermat's Little Theorem | ** Fermat's Little Theorem | ||
| − | ** polynomials | + | ** polynomials |
| − | ** secret sharing, | + | ** secret sharing, erasure codes |
| − | ** RSA | + | ** RSA |
| + | |||
| + | * Stable marriage | ||
| + | |||
| + | * Intro to Graph theory | ||
$ --- absence, to be covered | $ --- absence, to be covered | ||
| แถว 59: | แถว 63: | ||
===31 ส.ค. 51=== | ===31 ส.ค. 51=== | ||
* Number Theory | * Number Theory | ||
| − | ** Primality testing and | + | ** Review of RSA, why hacking RSA is hard, its assumption (hard to factor large numbers) |
| − | ** Proof of Euler Theorem and RSA | + | *** 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 [http://en.wikipedia.org/wiki/Carmichael_number 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 | * Recursions | ||
** Recursive definition and counting | ** Recursive definition and counting | ||
** Recursive algorithms, divide and conquer | ** 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 | ||
รุ่นแก้ไขปัจจุบันเมื่อ 05:04, 14 กันยายน 2551
เนื้อหา
Planed
- การนับ
- นับเบื้องต้น เส้นตรง, วงกลม, nCr, nPr
- inclusion-exclusion techniques
- bijections
- advanced counting (placing rods)
- Proof Techniques
- logics
- direct proof
- indirect proof
- proof by contradiction
- Advanced proof techniques
- mathematical induction
- basic induction
- strong induction
- examples used: tiling, placing dominoes, induction on matrices, Fibonacci numbers
- recursive thinking
- Pigeon-Hole Principle
- diagonalization
- mathematical induction
- Number theory
- divisibility
- congruence
- gcd, extended gcd
- modular arithematics
- Fermat's Little Theorem
- polynomials
- secret sharing, erasure codes
- RSA
- Stable marriage
- Intro to Graph theory
$ --- absence, to be covered
Actual
10 ส.ค. 51
- 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)
17 ส.ค. 51
- diagonalization
- advanced counting: placing rods
24 ส.ค. 51
- review of modular arithmatics
- basic identities
- if then 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
31 ส.ค. 51
- 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
- Testing in exponential time ($O(p)$ and $O(\sqrt{p})$ for testing $p$)
- Euler Theorem and RSA
- Idea of the proof of Euler Theorem (should be completed in h.w.)
- Euler Theorem => Correctness of RSA
- Review of RSA, why hacking RSA is hard, its assumption (hard to factor large numbers)
- 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: two properties:
บ่าย
- polynomials and codes (cont.)
- finite fields
- secret sharing
- erasure codes
- stable matching
