intTypePromotion=1
zunia.vn Tuyển sinh 2024 dành cho Gen-Z zunia.vn zunia.vn
ADSENSE
 » 
 » 

Bài giảng Nhập môn Số học thuật toán: Chương 1, 2 - Nguyễn Đạt Thông

Chia sẻ: Ngocnga Ngocnga | Ngày: | Loại File: PDF | Số trang:54

Thêm vào BST
Báo xấu
174
lượt xem 12
download
 
  Download Vui lòng tải xuống để xem tài liệu đầy đủ

Bài giảng Nhập môn Số học thuật toán - Chương 1, 2 cung cấp cho sinh viên các kiến thức cơ bản của số học và thuật toán, bao gồm các định nghĩa, định lý, các bài toán cũng như các vấn đề tiêu biểu trong số học. Trong chương này các bạn sẽ cùng tìm hiểu một số vấn đề cơ bản về thuật toán và số nguyên. Mời các bạn cùng tham khảo.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Bài giảng Nhập môn Số học thuật toán: Chương 1, 2 - Nguyễn Đạt Thông

  1. Giới thiệu Thuật toán Số nguyên Số nguyên tố Euclide Alg. CRT Phân số liên tục Nhập môn SỐ HỌC THUẬT TOÁN Nguyễn Đạt Thông ndthong@math.hcmus.edu.vn Bộ môn Ứng dụng Tin học Khoa Toán - Tin học 2010 Nhập môn Số học và Thuật toán 1/54
  2. Giới thiệu Thuật toán Số nguyên Số nguyên tố Euclide Alg. CRT Phân số liên tục Giới thiệu Tên học phần: Nhập môn số học thuật toán. Số tín chỉ: 4. Chuyên ngành: Phương pháp Toán trong Tin học. Học phần tiên quyết: Đại số đại cương. Học phần liên quan: Phân tích thuật toán. Lý thuyết mã hóa thông tin. Nhập môn Số học và Thuật toán 2/54
  3. Giới thiệu Thuật toán Số nguyên Số nguyên tố Euclide Alg. CRT Phân số liên tục Mục tiêu Cung cấp cho sinh viên các kiến thức cơ bản của số học và thuật toán, bao gồm các định nghĩa, định lý, các bài toán cũng như các vấn đề tiêu biểu trong số học. Trình bày các ý tưởng và các cài đặt cơ bản của các thuật toán liên quan đến việc biểu diễn, tính toán, giải quyết các vấn đề của số học trên máy tính. Giới thiệu một số ứng dụng tiêu biểu của số học trong các lĩnh vực mật mã và mã hóa. Nhập môn Số học và Thuật toán 3/54
  4. Giới thiệu Thuật toán Số nguyên Số nguyên tố Euclide Alg. CRT Phân số liên tục Yêu cầu Sinh viên cần tham dự các buổi học lý thuyết và thực hành, tham khảo tài liệu, làm bài tập nhóm, ... để có thể nắm đầy đủ nội dung chương trình. Sinh viên cần có các kỹ năng tính toán, suy luận, chứng minh, ... để có thể hiểu rõ và nắm vững các kiến thức nền tảng của số học. Sinh viên cần có các kỹ năng tư duy logic, lập trình, debug, ... để có thể cài đặt và kiểm tra các thuật toán của số học. Nhập môn Số học và Thuật toán 4/54
  5. Giới thiệu Thuật toán Số nguyên Số nguyên tố Euclide Alg. CRT Phân số liên tục Nội dung lý thuyết 1 Thuật toán 2 Số nguyên 3 Các hàm số học 4 Thặng dư bình phương 5 Đường cong Elliptic 6 Một số thuật toán phân tích số nguyên 7 Một số thuật toán giải bài toán logarit rời rạc 8 Ứng dụng số học vào lý thuyết mật mã Nhập môn Số học và Thuật toán 5/54
  6. Giới thiệu Thuật toán Số nguyên Số nguyên tố Euclide Alg. CRT Phân số liên tục Nội dung thực hành 1 Ngôn ngữ lập trình Python 2 Tính toán trên số nguyên 3 Các hàm số học và tính thặng dư bình phương 4 Tính toán đường cong Elliptic trên trường Zp 5 Kiểm tra số nguyên tố 6 Tìm căn theo modulo n 7 Phân tích số nguyên 8 Giải bài toán logarit rời rạc Nhập môn Số học và Thuật toán 6/54
  7. Giới thiệu Thuật toán Số nguyên Số nguyên tố Euclide Alg. CRT Phân số liên tục Tài liệu tham khảo 1 Hà Huy Khoái, Phạm Huy Điển, Số học thuật toán, Hà Nội, 2002, NXB Đại học Quốc Gia Hà Nội. 2 Alfred J. Menezes, Paul C. van Oorschot, Scott A. Vanstone, Handbook of Applied Cryptography, 1997, CRC Press. 3 Douglas R. Stinson, Cryptography - Theory and Practice, 3rd Edition, Ontario, 1995, CRC Press. 4 David M. Burton, Elementary Number Theory, 2nd Edition, Massachusetts, 1980, Allyn and Bacon. 5 Allen Downey, ThinkPython, Massachusetts, 2008, Green Tee Press. Nhập môn Số học và Thuật toán 7/54
  8. Giới thiệu Thuật toán Số nguyên Số nguyên tố Euclide Alg. CRT Phân số liên tục Tài liệu tham khảo 6 H. C. William, M. C. Wunderlich, On the Parallel Generation of the Residues for the Contrinued Fraction Factoring Algorithm, Mathematics of Computation Vol 48, 1987, American Mathematical Society. 7 Donald E. Knuth, The Art of Computer Programming, Vol. 2 - Seminumerical Algorithms, 3rd Edition, Canada, 1998, Addison Wesley. 8 T. M. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein, Introduction to Algorithms, 2nd Edition, 2001, The MIT Press. Nhập môn Số học và Thuật toán 8/54
  9. Giới thiệu Thuật toán Số nguyên Số nguyên tố Euclide Alg. CRT Phân số liên tục Phương pháp đánh giá Bài tập lý thuyết và thực hành: 20% Kiểm tra giữa kỳ: 15% Thảo luận đề tài: 15% Kiểm tra cuối kỳ: 50% Nhập môn Số học và Thuật toán 9/54
  10. Giới thiệu Thuật toán Số nguyên Số nguyên tố Euclide Alg. CRT Phân số liên tục Câu hỏi Q&A Nhập môn Số học và Thuật toán 10/54
  11. Giới thiệu Thuật toán Số nguyên Số nguyên tố Euclide Alg. CRT Phân số liên tục Chương 1 THUẬT TOÁN Nguyễn Đạt Thông ndthong@math.hcmus.edu.vn Bộ môn Ứng dụng Tin học Khoa Toán - Tin học 2010 Chương 1: Thuật toán 11/54
  12. Giới thiệu Thuật toán Số nguyên Số nguyên tố Euclide Alg. CRT Phân số liên tục Thuật toán Định nghĩa Thuật toán là một quy tắc để, với những dữ liệu ban đầu đã cho, tìm được lời giải sau một khoảng thời gian hữu hạn. Tính chất 1 Tính hữu hạn. Thuật toán cần phải kết thúc sau một số hữu hạn bước. Khi ngừng làm việc, kết quả của thuật toán phải được xác định. 2 Tính xác định. Ở mỗi bước, thuật toán cần phải xác định, nghĩa là chỉ rõ việc cần làm. Chương 1: Thuật toán 12/54
  13. Giới thiệu Thuật toán Số nguyên Số nguyên tố Euclide Alg. CRT Phân số liên tục Ví dụ về thuật toán Bài toán Cho n số X[1], X[2], ..., X[n], tìm m và j sao cho m = X[j] = max X[k] 1≤k≤n và j lớn nhất có thể. Thuật toán 1 [Xuất phát] Đặt j ← n, k ← n − 1, m ← X[n]. 2 [Kết thúc] Nếu k = 0, kết thúc. 3 [So sánh] Nếu X[k] ≤ m, chuyển sang bước 5. 4 [Cập nhật] Đặt j ← k, m ← X[k]. 5 [Giảm k] Đặt k ← k − 1, quay lại bước 2. Chương 1: Thuật toán 13/54
  14. Giới thiệu Thuật toán Số nguyên Số nguyên tố Euclide Alg. CRT Phân số liên tục Độ phức tạp của thuật toán Độ phức tạp của thuật toán được đo bằng số phép tính nhị phân phải làm khi thực hiện thuật toán. Với cùng một thuật toán, số phép tính cần thực hiện phụ thuộc vào cỡ của bài toán, tức là độ lớn của đầu vào. Nói cách khác, độ phức tạp của thuật toán là một hàm số phụ thuộc độ lớn của đầu vào. Hàm số độ phức tạp của thuật toán được ước lượng trong trường hợp xấu nhất của thuật toán. Cỡ n của dữ liệu đầu vào tương đương với cỡ k = [log2 n] + 1 trên máy tính. Chương 1: Thuật toán 14/54
  15. Giới thiệu Thuật toán Số nguyên Số nguyên tố Euclide Alg. CRT Phân số liên tục Bậc O-lớn Định nghĩa Giả sử f (n) và g(n) là hai hàm xác định trên tập hợp các số nguyên dương. Ta nói f (n) có bậc O-lớn của g(n), và viết f (n) = O(g(n)) hoặc f = O(g), nếu tồn tại một số C > 0 sao cho với n đủ lớn, các hàm f (n) và g(n) đều dương, đồng thời f (n) < Cg(n). Bậc O-lớn là công cụ được dùng để ước lượng hàm số độ phức tạp của thuật toán. Nếu hàm số độ phức tạp của một thuật toán được ước lượng bởi O(g), ta nói thuật toán này có độ phức tạp O(g). Nếu một thuật toán có độ phức tạp O(g), thì cũng có thể nói nó có độ phức tạp O(h) với mọi hàm h > g. Tuy nhiên, ước lượng độ phức tạp của thuật toán phải là ước lượng tốt nhất có thể để tránh hiểu sai về độ phức tạp thực sự của thuật toán. Chương 1: Thuật toán 15/54
  16. Giới thiệu Thuật toán Số nguyên Số nguyên tố Euclide Alg. CRT Phân số liên tục Tính chất của O-lớn Tính chất 1 Nếu f (n) = ad nd + ad−1 nd−1 + ... + a1 n + a0 thì f (n) = O(nd ). 2 Nếu f1 (n) = O(g(n)) và f2 (n) = O(g(n)) thì f1 + f2 = O(g). 3 Nếu f1 = O(g1 ) và f2 = O(g2 ) thì f1 f2 = O(g1 g2 ). f (n) 4 Nếu tồn tại giới hạn hữu hạn lim thì f = O(g). n→∞ g(n) 5 Với mọi số ε > 0, log n = O(nε ). Chương 1: Thuật toán 16/54
  17. Giới thiệu Thuật toán Số nguyên Số nguyên tố Euclide Alg. CRT Phân số liên tục Độ phức tạp đa thức Định nghĩa Một thuật toán được gọi là có độ phức tạp đa thức, hoặc có thời gian đa thức, nếu số các phép tính cần thiết khi thực hiện thuật toán không vượt quá O(logd n), trong đó n là độ lớn của đầu vào, và d là số nguyên dương nào đó. Nếu một thuật toán có độ phức tạp đa thức và có đầu vào n là một số k-bit thì độ phức tạp của thuật toán này là O(k d ), tức một đa thức của k. Các thuật toán có thời gian O(αn ), với α > 1, được gọi là các thuật toán có độ phức tạp mũ, hoặc thời gian mũ. Các thuật toán có thời gian O(nd ) với d > 1 là các thuật toán có độ phức tạp tương đương mũ. Chương 1: Thuật toán 17/54
  18. Giới thiệu Thuật toán Số nguyên Số nguyên tố Euclide Alg. CRT Phân số liên tục Độ phức tạp dưới mũ Ngoài ra còn có những thuật toán có độ phức tạp trung gian giữa đa thức và mũ, được gọi là các thuật toán dưới mũ. Chẳng hạn, thuật toán nhanh nhất được biết hiện nay để phân tích một số nguyên n ra thừa số nguyên tố là thuật toán có độ phức tạp √ log n log log n e Với một máy tính có khả năng thực hiện 1 triệu phép tính trong 1 giây, thời gian cần thiết để chạy thuật toán này được mô tả trong bảng sau: Số chữ số thập phân Số phép tính bit Thời gian 50 1.4 × 1010 3.9 giờ 75 9.0 × 1012 104 ngày 100 2.3 × 1015 74 năm 200 1.2 × 1023 3.8 × 109 năm 300 1.5 × 1029 4.9 × 1015 năm 500 1.3 × 1039 4.2 × 1025 năm Chương 1: Thuật toán 18/54
  19. Giới thiệu Thuật toán Số nguyên Số nguyên tố Euclide Alg. CRT Phân số liên tục Câu hỏi Một thuật toán cần khoảng 1027 năm để hoàn thành thì có thể xem là một thuật toán xác định không? Có 2 thuật toán phân tích thừa số nguyên tố chạy trên cùng một hệ thống máy tính. Thuật toán thứ nhất mất 3 ngày để hoàn thành, thuật toán thứ hai chạy 27 ngày vẫn chưa xong. Có thể nói thuật toán thứ nhất tốt hơn (hiệu quả hơn) thuật toán thứ hai không? Có 2 thuật toán sắp xếp dãy số chạy trên cùng một hệ thống máy tính. Để sắp xếp một dãy gồm n phần tử, thuật toán thứ nhất cần thực hiện 2n2 phép tính trong khi thuật toán thứ hai cần 50n log2 n. Có thể nói thuật toán thứ hai phức tạp hơn thuật toán thứ nhất không? Chương 1: Thuật toán 19/54
  20. Giới thiệu Thuật toán Số nguyên Số nguyên tố Euclide Alg. CRT Phân số liên tục Chương 2 SỐ NGUYÊN Nguyễn Đạt Thông ndthong@math.hcmus.edu.vn Bộ môn Ứng dụng Tin học Khoa Toán - Tin học 2010 Chương 2: Số nguyên 20/54
ADSENSE

CÓ THỂ BẠN MUỐN DOWNLOAD

THÔNG TIN
TRỢ GIÚP
HỖ TRỢ KHÁCH HÀNG
Theo dõi chúng tôi

Chịu trách nhiệm nội dung:

Nguyễn Công Hà - Giám đốc Công ty TNHH TÀI LIỆU TRỰC TUYẾN VI NA

LIÊN HỆ

Địa chỉ: P402, 54A Nơ Trang Long, Phường 14, Q.Bình Thạnh, TP.HCM

Hotline: 093 303 0098

Email: support@tailieu.vn

Giấy phép Mạng Xã Hội số: 670/GP-BTTTT cấp ngày 30/11/2015 Copyright © 2022-2032 TaiLieu.VN. All rights reserved.

 

Đồng bộ tài khoản
2=>2