Show
Đã đăng vào thg 4 14, 2020 4:57 CH 4 phút đọc 1. Thuật toán là gì ?Thuật toán được được coi là nền tảng của ngành lập trình dữ liệu. Nó bao gồm các quy tắc, chỉ thị hay phương thức nhằm hoàn thành trạng thái ban đầu được đưa ra. Chỉ khi các yêu cầu được được xắp xếp một cách triệt để thì khi ấy thuật toán sẽ đem lại một kết quả chính xác. Đối với dân lập trình, khái niệm về thuật toán không có gì là mấy xa lạ. Nhưng với những người mới bắt đầu bước vào ngành thì việc hiểu ý nghĩa của thuật toán là khá trìu tượng. Bài viết này sẽ giúp bạn hiểu được căn nguyên và cốt lõi của nó. 2. Các tính chất của thuật toán ?Thuật toán có 5 tính chất bao gồm: tính chính xác, tính khách quan, tính phổ dụng, tính rõ ràng, tính kết thúc. Ban đầu, một thuật toán cần có "tính chính xác" vô cùng cao. Nó cũng là yếu tố quan trọng nhất, mang tính chất khả dụng và khách quan của một thuật toán. Bên cạnh đó, một thuật toán luôn luôn được xếp theo một trình tự vô cùng quy củ, với cách xắp xếp lượng bên trong hợp lí giúp các thao tác trở nên trơn chu và nhanh gọn hơn rất nhiều. Đây là "tính rõ ràng", thể hiện trên nguyên tắc lệnh. "Tính khả dụng" của một thuật toán được thể hiện ở việc linh động. Nó không cố định mà dảo hoạt nên có thể ứng dụng trong không chỉ một mà rất nhiều các bài toán với nhiều dạng tương tự. Một thuật toán dù giải theo cách nào cũng chỉ có thể có một đáp án duy nhất. Điều đó khẳng định sự tuyệt đối với kết quả bài toán. Nếu như ra đáp án khác nhau thì cần xem xét lại quá trình xử lí. Đây là "Tính khách quan" của một thuật toán. Cuối cùng, "tính kết thúc" hiểu là kết quả của một thuật toán. Như đã nói, thuật toán là căn nguyên của ngành lập trình học. Vậy bạn hiểu ý nghĩa khi sử dụng thuật toán là như thế nào ? 3. Thuật toán đem lại ý nghĩa lớn như thế nào ?Thuật toán với một lập trình viên, hay một chuyên viên kĩ thuật máy tính vô cùng quan trọng. Bởi công việc của họ là tạo ra các trang wed đồng hành với việc bảo hành cho sự hoạt động hiệu quả. Vậy nên, việc sử dụng các thuật toán sẽ giúp họ có được nhưng dữ liệu chính xác về công trình để kịp thời phát hiện, sửa chữa thậm chí dự đoán về việc xảy ra sự cố ngoài ý muốn. Tất nhiên thuật toán là các dạng các nhau, tùy việc linh động ứng biến các dạng thuật toán cũ hay lựa chọn cách sáng tạo ra các thuật toán mới sẽ đem lại tính hiệu quả cao hơn đối với kết quả, cũng như đối với chất lượng . Mình hi vọng , qua bài viết này bạn đã hiểu thuật toán là gì rồi đúng không? Chúc các bạn thành công !! All rights reserved I. Thuật toán và những tính chất của thuật toán1. Khái niệmThuật toán - hay còn gọi là giải thuật - là khái niệm quan trọng nhất trong Tin học. Nó là nền tảng cho mọi khía cạnh của Tin học. Khái niệm về thuật toán đã tồn tại từ thời cổ đại, sớm nhất ở đế chế Babylonia với thuật toán chia vào năm 25002500 TCN. Khái niệm về thuật toán có thể phát biểu như sau: Thuật toán là một dãy hữu hạn các bước, mỗi bước mô tả chính xác các phép toán hoặc hành động cần thực hiện để giải quyết một vấn đề. Với sự phát triển chóng mặt của khoa học máy tính, các thuật toán cũng ngày càng phát triển về số lượng cũng như chất lượng. Trong phạm vi của lập trình thi đấu, chúng ta sẽ tập trung nghiên cứu chuyên sâu về các thuật toán từ dễ đến khó, phục vụ cho các kỳ thi về thuật toán như HSG Tin học, Tin học trẻ hay các kỳ thi thuật toán online. Toàn bộ các cài đặt sẽ được viết ở ngôn ngữ C++ vì như đã nói ở các chuyên đề lập trình cơ bản, C++ là một ngôn ngữ rất mạnh trong lập trình thi đấu. 2. Các đặc trưng của thuật toánMỗi thuật toán luôn luôn có đủ 55 đặc trưng sau:
Chẳng hạn, dưới đây là thuật toán tìm số ước của một số nguyên dương NN được viết trong một hàm int count_divisors(int N) int count_divisors(int N) { int divisors = 0; for (int i = 1; i <= N; ++i) if (N % i == 0) ++divisors; return divisors; }II. Phân tích tính hiệu quả của thuật toán1. Các tiêu chí đánh giá một thuật toánThông thường, khi giải một bài toán, chúng ta luôn luôn có xu hướng chọn cách giải "tốt" nhất. Nhưng thế nào là "tốt"? Trong toán học, một cách giải "tốt" có thể là cách giải ngắn gọn, xúc tích, hoặc trên tiêu chí sử dụng những kiến thức dễ hiểu. Còn đối với thuật toán trong Tin học thì dựa vào hai tiêu chuẩn sau:
2. Sự cần thiết của thuật toán hiệu quảCông nghệ càng phát triển thì sẽ dẫn tới độ lớn dữ liệu cần tính toán ngày càng lớn, tất nhiên khả năng tính toán của máy tính cũng ngày càng phát triển. Nhưng không phải vì việc máy tính hiện đại mà chúng ta có thể bỏ qua tầm quan trọng của một thuật toán hiệu quả. Để làm rõ vấn đề này, mình xin trích lại một ví dụ trong sách giáo khoa chuyên Tin quyển 11 về thuật toán kiểm tra tính nguyên tố của một số. bool is_prime(int N) { if (N < 2) // Nếu N nhỏ hơn 2 thì chắc chắn không phải số nguyên tố. return false; // Nếu N có ước trong đoạn [2, N - 1] thì N không phải số nguyên tố. for (int i = 2; i < N; ++i) if (N % i == 0) return false; return true; }Bên trên là cách cài đặt đơn giản nhất của giải thuật kiểm tra tính nguyên tố. Thuật toán này cần N−2N-2 bước kiểm tra trong vòng lặp. Hãy giả sử cần kiểm tra một số có khoảng 2525 chữ số, và ta sở hữu một siêu máy tính có thể tính toán được một trăm nghìn tỉ (101410^{14}) phép tính trên giây, thì tổng thời gian cần để kiểm tra là: 10251014×60×60×24×365≈3170 na˘m!\frac{10^{25}}{10^{14} \times 60 \times 60 \times 24 \times 365} \approx 3170 \text{ năm!} Tuy nhiên, nếu tinh ý ta có thể nhận xét như sau: Một số NN có ước là x (x≤N) x \ (x \le \sqrt{N}) thì chắc chắn nó cũng có ước là Nx≥N\frac{N}{x} \ge \sqrt{N}. Do đó, thay vì duyệt từ 22 tới N−1N - 1 thì ta chỉ cần duyệt từ 22 tới N\sqrt{N} là có thể biết được NN có ước nào trong đoạn này hay không: bool is_prime(int N) { if (N < 2) // Nếu N nhỏ hơn 2 thì chắc chắn không phải số nguyên tố. return false; // Nếu N có ước trong đoạn [2, N - 1] thì N không phải số nguyên tố. for (int i = 2; i * i <= N; ++i) if (N % i == 0) return false; return true; }Theo phương pháp này, vẫn là một số nguyên có khoảng 2525 chữ số nhưng thời gian kiểm tra sẽ giảm xuống còn: 102510 14≈0.03 giaˆy!\frac{\sqrt{10^{25}}}{10^{14}} \approx 0.03 \text{ giây!} III. Phương pháp đánh giá độ phức tạp thuật toán1. Phương pháp đánh giá bằng lý thuyếtTrong lập trình thi đấu, người ta sẽ đánh giá độ phức tạp thuật toán bằng phương pháp lý thuyết. Trong phương pháp này, ta quan tâm tới yêu tố kích thước của dữ liệu đầu vào, thông thường là một con số nn. Mối liên hệ giữa yếu tố này và số lượng các phép tính toán để tìm ra được kết quả của bài toán gọi là độ phức tạp thuật toán (chứ không phải thời gian cụ thể như 1,21, 2 hay 1010 giây). Ta sử dụng hàm số T(n)T(n) để biểu diễn thời gian thực hiện của thuật toán với dữ liệu đầu vào kích thước là nn. Độ lớn của hàm T(n)T(n) được biểu diễn bằng một hàm O(f(n))O(f(n)) với T(n)T(n) và f( n)f(n) là hai hàm số thực không âm. Nếu một thuật toán có thời gian thực hiện là T(n)=O(f(n))T(n) = O(f(n)) thì ta nói thuật toán đó có thời gian thực hiện cấp f(n)f(n). Nói một cách dễ hiểu, T(n)T(n) sẽ biểu diễn số phép tính tối đa cần thực hiện trong thuật toán với một bộ dữ liệu cấp n,n, chẳng hạn trong bài toán kiểm tra tính nguyên tố của số n,n, nếu nn là số nguyên tố thì thuật toán sẽ phải thực hiện nhiều lần thử nhất. 2. Các quy tắc đánh giá thời gian thực hiện thuật toánĐể đánh giá thời gian thực hiện thuật toán, ta xuất phát từ các lệnh đơn trong chương trình, rồi tới các câu lệnh có cấu trúc, các khối lệnh phức tạp hơn, sau đó hợp lại thành thời gian thực hiện cả chương trình. Cụ thể ta có các quy tắc:
3. Phân tích ví dụVí dụ 1: Phân tích thời gian thực hiện của đoạn chương trình sau: #include <iostream> using namespace std; int main() { int n; // (1) cin >> n; // (2) int s1 = 0; // (3) for (int i = 1; i <= n; ++i) // (4) s1 += i; // (5) int s2 = 0; // (6) for (int i = 1; i <= n; ++i) // (7) s2 += i * i; // (8) cout << s1 << endl << s2; // (9) }Thời gian thực hiện chương trình trên phụ thuộc vào số nn. Ta phân tích chi tiết:
Vậy thời gian thực hiện của cả thuật toán là: max(O(1),O(n))=O(n)\text{max}(O(1), O(n)) = O(n) Ví dụ 2: Phân tích thời gian thực hiện thuật toán của đoạn chương trình sau: #include <iostream> using namespace std; int main() { int sum = 0; // (1) for (int i = 1; i <= N; ++i) // (2) for (int j = 1; j <= i; ++j) // (3) sum = sum + 1; // (4) cout << sum; // (5) }Đoạn chương trình trên có thời gian thực hiện phụ thuộc vào số NN. Phân tích chi tiết:
⇒\Rightarrow Cả chương trình có thời gian thực hiện là O(N2)O(N^2). 4. Một số lưu ýTrong khi giải các bài toán trong các kỳ thi lập trình, mình có tổng hợp vài quy tắc nho nhỏ rất hữu ích có thể giúp đỡ các bạn trong quá trình học tập như sau:
|