Về độ phức tạp của các thuật toán số học

➤ Gửi thông báo lỗi ⚠️ Báo cáo tài liệu vi phạm

Loại tài liệu: PDF

Số trang: 51 Trang

Tài liệu: ✅ ĐÃ ĐƯỢC PHÊ DUYỆT

TẢI VỀ

Nội dung chi tiết: Về độ phức tạp của các thuật toán số học

Về độ phức tạp của các thuật toán số học

1BỌ GIÁO DỤC VÀ ĐÀO TẠO TRƯỜNG ĐẠI HỌC VINHLÊ THANH XUÂNVẺ Độ PHÚC TẠP CỦA CÁC THUẬT TOÁN SÔ HỌCLUẬN VĂN THẠC sĩ TOÁN HỌCNghệ An, 12. 20112MỤC LỤC Tra

Về độ phức tạp của các thuật toán số học ang Mục lục1Mờ dầu2Chirơng 1: Các kiến thức cơ sừ về dộ phức tạp cùa các thuật toán 5 I. I. Khái niệm về thuật toán...................................

.... 51.2.('ác dạng diễn dạt thuật toán..................... ỉ ỉ1.3.Dộ phức l ạ p ihuậ 1l oán.................................... 131.4.Đánh giá dộ ph Về độ phức tạp của các thuật toán số học

ức tạp của thuật toán............... 17Chưoiìg 2: Độ phức tạp cúa các thuật toán số học202.1. Biêu diễn so nguyên và các phép tinh so học........202.2

Về độ phức tạp của các thuật toán số học

.Sô nguyên lô................................................. 282.3.Ihuật toán Euclid............................................ 382.4.Thuậl toán J.

Về độ phức tạp của các thuật toán số học .................................. 43Kết luận49Tài liệu tham khảo ................................................ 50♦3MỜ DẲƯNeu nhu trước thập kỵ 70

cùa the ký XX. số học vẫn được xem là một trong những ngành lý thuyết xa rời thực lien nhất, thi ngày nay những thành lựu mới nliâl cua số học có ứng Về độ phức tạp của các thuật toán số học

dụng trục liếp vào các vấn đê cua đời sông, như thông tin mật mà. kỳ thuật máy lính. Một phưong hướng mới cua Sô học ra dò4 và phát triền mạnh mè: So

Về độ phức tạp của các thuật toán số học

học thuật toán, ('ỏ thè nói rang, So học thuật toán - đó là cilice cầu nòi giừa Sò học và Tin học. Sự phát tricn cua Tin học dôi hói phái xây dựng các

Về độ phức tạp của các thuật toán số học uật toán.Thời gian mà máy tính khi thực hiện một thuật toán không chi phụ thuộc vào bán thân thuật toán dó, ngoài ra côn tùy thuộc từng máy tính. Đe đ

ánh giá hiệu quá cùa một thuật toán, có thè xét số các phép lính phai thực hiện khi thực hiện thuật toán nảy. Ibông thường so các phép tinh dược thực Về độ phức tạp của các thuật toán số học

hiện phụ thuộc vào cờ cùa bài toán, tức là độ lớn cua đâu vào. Vi the độ phức lạp thuật toán là một hàm phụ thuộc đau vào. Tuy nhicn trong nhùng ứng d

Về độ phức tạp của các thuật toán số học

ụng thực lien, chúng la không cần biết chính xác hàm này mà chi can biết một ước lượng đu tôl cùa chúng. Dê ước lượng độ phức lạp cua một thuật toán,

Về độ phức tạp của các thuật toán số học o, ()(I). số phép tính, thời gian chạy dung lượng bộ nhớ không phụ thuộc vào độ lớn đầu vào. Chăng hạn như các thao tác hệ thống: đóng, mờ file.4-Độ p

hức tạp tuyến tinh. O(n). số phép tinh, thời gian chạy/dung lượng bộ nhớ có xu hướng ti lệ thuận với độ lớn đàu vào. Châng hạn như tính tông các phan Về độ phức tạp của các thuật toán số học

tứ của một máng một chiều.-DỘ phức lạp đa thức. O(P(nỴ), với p là đa thức bậc cao (lừ 2 trờ len). Chẳng hạn như các thao tác tinh toán với máng nhiêu

Về độ phức tạp của các thuật toán số học

chiêu (tinh định thức ma trận).-Độ phức tạp lôgarit, (7(log/>) (chú ý: bậc của nỏ thắp hơn so với O(nỴ) . Chang hạn Ihuậl toán Euclid de tim ước so ch

Về độ phức tạp của các thuật toán số học học” nhàm tim hiểu sâu hơn ứng dụng về các thuật toán số học trong Tin học. Với mục đích đó, ngoài phân mớ đau và kết luận, Luận vãn dược chia làm ha

i chương.Chương 1. Các kiến thức cơ sờ về dộ phức tạp cùa các thuật toán Về độ phức tạp của các thuật toán số học