Câu 1. (2,0 điểm) thuật toán là gì? trình bày các thành phần chính của thuật toán?
Show Viblo Algorithm @viblo.algorithm Đã đăng vào thg 9 3, 2021 7:59 SA 10 phút đọc
Thuậ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 250025002500 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ó đủ 555 đặ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 NNN đượ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á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 111 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) return false; 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-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 252525 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}1014) 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!} 1014×60×60×24×3651025≈3170 na˘m! Tuy nhiên, nếu tinh ý ta có thể nhận xét như sau: Một số NNN có ước là x (x≤N)x \ (x \le \sqrt{N})x (x≤N) thì chắc chắn nó cũng có ước là Nx≥N\frac{N}{x} \ge \sqrt{N}xN≥N. Do đó, thay vì duyệt từ 222 tới N−1N - 1N−1 thì ta chỉ cần duyệt từ 222 tới N\sqrt{N}N là có thể biết được NNN có ước nào trong đoạn này hay không: bool is_prime(int N) { if (N < 2) return false; 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 252525 chữ số nhưng thời gian kiểm tra sẽ giảm xuống còn: 10251014≈0.03 giaˆy!\frac{\sqrt{10^{25}}}{10^{14}} \approx 0.03 \text{ giây!} 10141025≈0.03 giaˆy! III. Phương pháp đánh giá độ phức tạp thuật toánTrong 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ố nnn. 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, 21,2 hay 101010 giây). Ta sử dụng hàm số T(n)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à nnn. Độ lớn của hàm T(n)T(n)T(n) được biểu diễn bằng một hàm O(f(n))O(f(n))O(f(n)) với T(n)T(n)T(n) và f(n)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))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)f(n). Nói một cách dễ hiểu, T(n)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,n, chẳng hạn trong bài toán kiểm tra tính nguyên tố của số n,n,n, nếu nnn 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: #includeThời gian thực hiện chương trình trên phụ thuộc vào số nnn. 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) 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: Đoạn chương trình trên có thời gian thực hiện phụ thuộc vào số NNN. 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)O(N2). 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:
All rights reserved |