khaihanhdk
user-avatar

Tăng Khải Hạnh

Đóng góp: 38

Ngày sinh: 16/09/1995

Đăng ký: 03/07/2015

Lần đăng nhập cuối: 05/02/2017

Kết nối tài khoản

VOJ: khaihanhdk (160.57 điểm)

Topcoder: Chưa kết nối

Khóa học Machine Learning trên Coursera - University of Washington

Chào các bạn, ngày hôm qua, 22/9 khóa học đầu tiên của Machine Learning Specialization vừa mới bắt đầu.

Machine Learning Specialization này bao gồm series 5 khóa học:

- Course 1: Machine Learning Foundations: A Case Study Approach (bắt đầu ngày 22/9/2015)

- Course 2: Regression (bắt đầu tháng 11/2015)

- Course 3: Classification (bắt đầu tháng 12/2015)

- Course 4: Clustering & Retrieval (bắt đầu tháng 2/2016)

- Course 5: Recommender Systems & Dimensionality Reduction (bắt đầu tháng 3/2016)

Và một capstone project: Machine Learning Capstone: An Intelligent Application with Deep Learning (bắt đầu tháng 4/2016).

Đây là link của Machine Learning Specialization: https://www.coursera.org/specializations/machine-learning

Đây là link từng khóa học:

- Course 1: https://www.coursera.org/learn/ml-foundations

- Course 2: https://www.coursera.org/learn/ml-regression

- Course 3: https://www.coursera.org/learn/ml-classification

- Course 4: https://www.coursera.org/learn/ml-clustering-and-retrieval

- Course 5: https://www.coursera.org/learn/ml-recommenders

- Capstone project: Chưa thấy link

Nếu các bạn đăng kí trực tiếp trên trang của bộ môn (specialization) thì họ sẽ yêu cầu tính phí để đăng kí học. Do đó các bạn nên search tên từng khóa, bấm enroll, khi đó họ sẽ yêu cầu tính phí, các bạn chọn option: Full Course, No certificate. Như vậy các bạn sẽ được học free khóa này.

Yêu cầu: biết trước Python.

Chúc các bạn đạt được kết quả tốt trong lĩnh vực này.

 

Tăng Khải Hạnh - khaihanhdk

Thuật toán Euclide mở rộng

Chào các bạn, nhân dịp VNOI mới sập, à nhầm ..., mới được dựng lại, mình xin viết 1 bài mở màn về thuật toán Euclide mở rộng (Extended Euclidean algorithm).

Theo định lí Benzout (Benzout's identity), cho 2 số nguyên a, b, khi đó luôn tồn tại 2 số nguyên x, y sao cho:

ax + by = d       //với d là ước chung lớn nhất của a và b.

Ta có thể viết lại:

\({a \over d}x + {b \over d}y = 1 \)

Giờ ta xét 2 số nguyên a, b nguyên tố cùng nhau và phương trình ax + by = 1. Ta có thể tiến hành tìm nghiệm x, y của bài toán. Áp dụng phương pháp tìm ước chung lớn nhất gcd(a, b) mà các bạn thường code.

Giả sử ta có biểu thức: 52x + 47y = 1 với a = 52, b = 47

  • Bước 1: 52 mod 47 = 5
  • Bước 2: 47 mod 5 = 2
  • Bước 3: 5 mod 2 = 1
  • Bước 4: 2 mod 1 = 0

Vì ở bước 4 kết quả là 0 nên mình không xét. Như vậy mình đi ngược từ bước 3 trở lên. Theo đó ở bước 3 ta có:

5 mod 2 = 1  (1)

=> 5 - 2 * 2 = 1

Theo hàm gcd, giá trị 2 ở trên là do có được từ bước 2 nên 47 mod 5 = 2 => 2 = 47 - 9 * 5

=> Thế kết quả của 2 vào (1) ta được: 5 - 2 * (47 - 9 * 5) = 1   (2)

Tiếp tục ở bước 1 ta có 52 mod 47 = 5 => 5 = 52 - 1 * 47.

Thế kết quả vào (2) ta được: (52 - 47) - 2 * [47 - 9 * (52 - 47)] = 1

Ta cũng có thể viết lại (a - b) - 2 * [b - 9 * (a - b)] = 1

=> 19a - 21b = 1

Vậy khi đó nghiệm của bài toán là: x = 19, y = -21

Ta có thể kiểm tra lại 19 * 52 - 21 * 47 = 1

Từ cách làm trên ta có thể rút ra cách tìm x, y của bài toán theo đoạn code sau (do mình tự viết):

bool isSwap = false   //Biến dùng để kiểm tra 2 số a và b có hoán đổi nhau không
if a < b:
begin
   hoán đổi a, b
   gán isSwap = true
end;
int prex = 0, prey = 0, x = 0, y = 1 //prex và prey là 2 biến lưu giá trị trước của x và y
r = a mod b
Nếu r ≠ 0:
begin
   y = y *  (- int(a / b));
   x = 1, prey = 1
   a = b, b = r
end;
while b ≠ 0:
begin
   r = a mod b
   if r ≠ 0
   begin
      tprex = x, 
      tprey = y, 
      //tprex và tprey là 2 biến tạm thời lưu giá trị x, y
      md = - int(a / b) 
      x = x * md + prex, 
      y = y * md + prey
      prex = tprex, prey = tprey
   end
   a = b, b = r
end
if isSwap = true => trả về bộ 3 (a, y, x)  //Vì a, b đã hoán vị nên ta phải hoán vị cả y và x
Trả về bộ 3 (a, x, y)  //a là ước chung lớn nhất của a, b ban đầu

Theo thuật toán Euclide mở rộng ra cũng rút ra được: abs(x) < abs(b / d) và abs(y) < abs(a / d)

Áp dụng:

Đây có thể xem là thuật toán dùng để thay thế định lí nhỏ Fermat mà các bạn thường dùng cho bài toán:

\({a \over b} \mod m\)

Với m là số nguyên tố.

Theo đó các bạn sẽ tìm kết quả bài toán bằng cách áp dụng định lí nhỏ Fermat với biểu thức biến đổi: \(a * b^{m - 2} (\mod m)\)

Tuy nhiên nếu áp dụng định lí Euclide mở rộng cho bài toán này thì ta có thể tính giá trị b (mod m) theo dạng:

bx + my = 1

Giải phương trình trên bằng thuật toán Euclide mở rộng sẽ tìm được nghiệm x. Nếu kết quả x âm, ta có thể tăng x lên m đơn vị (vì abs(x) < abs(m / 1))

Như vậy khi đó ta lấy x * a (mod m) sẽ tương đương với biểu thức \({a \over b} \mod m\)

Thay thế định lí Fermat nhỏ bằng thuật toán Euclide mở rộng ta được 2 ưu thế:

  • Với bài toán \({a \over b} \mod m\) thì ta có thể tính kết quả với m không nhất thiết là số nguyên tố. Chỉ cần b và m nguyên tố cùng nhau.
  • Tốc độ thực thi của thuât toán Euclide mở rộng nhanh hơn định lí nhỏ Fermat: nếu ta dùng 1 ngôn ngữ lập trình có hỗ trợ số lớn để test thì ta sẽ thấy rằng Euclide mở rộng nhanh hơn rõ rệt so với định lí nhỏ Fermat khi a, b, m có kích thước từ vài nghìn để vài triệu bit nhị phân.

Cảm ơn các bạn đã quan tâm theo dõi, hy vọng sẽ không bị trừ ngay lần đầu tiên post bài :v

Tăng Khải Hạnh - khaihanhdk