Giới thiệu về giải thuật – Algorithm

Đây là bài đầu tiên mình viết về chủ đề khoa hc máy tính, nằm trong phân mục con cơ s toán cho lp trình. Bài này sẽ là bài mở đầu cho loạt bài bàn luận về nền tảng toán học và tư duy toán học trong lập trình với “độ sâu” ở mức vừa phải vì lý do kiến thức còn hạn hẹp. Nghĩa là hiểu và vận dụng được toán học vào trong việc thiết kế, phân tích, đánh giá một dự án tin học. Toán và tin có mối liên hệ rất chặt chẽ, tạo lập được một nền tảng toán học tốt sẽ thuận lợi rất nhiều cho những programers và developers như chúng ta. Mình rất muốn các bạn chia sẻ và tranh luận nhiệt tình để chúng ta có thể khắc phục được những thiếu sót và học hỏi thêm lẫn nhau. Bài đầu tiên này mình muốn viết về giải thuật hay thuật toán (Algorithm).

Có rất nhiều cách định nghĩa nhưng mình xin đưa ra đây một định nghĩa trên wikipedia : “Thuật toán , còn gọi là giải thuật, là một tập hợp hữu hạn của các chỉ thị hay phương cách được đnh nghĩa rõ ràng cho việc hoàn tt một số sự việc từ một trạng thái ban đầu cho trước; khi các chỉ thị này được áp dụng triệt để thì sẽ dn đến kết qu sau cùng như đã d đoán”. Nói cách khác, thuật toán là một bộ các qui tắc hay qui trình cụ thể nhằm giải quyết một vấn đề trong một số bước hữu hạn, hoặc nhằm cung cấp một kết quả từ một tập hợp của các dữ kiện đưa vào. Như vậy, thuật toán là một phương pháp thể hiện lời giải của vấn đề – bài toán.

Khái niệm này, theo mình, cũng giống như khái niệm hàm số (function) vậy (chính xác hơn là khái niệm ánh xạ – reflect). Một hàm số y = f(x) có thể nhận các giá trị x đầu vào từ một tập D. Và ứng với mỗi x  D chỉ cho ra một y duy nhất. Điều này giống như thuật toán có thể giải quyết không chỉ một bài toán mà có thể giải quyết cho một lớp bài toán tương tự nhau (đầu vào lấy từ một tập xác định  D’ nào đó). Với mỗi một bài toán đầu vào, thuật toán sẽ cho một giá trị đầu ra duy nhất. Giá trị đầu ra duy nhât nhất này không phải chỉ là một nghiệm, mà có thể là một bộ nghiệm. Ví dụ chương trình giải phương trình bậc 2, với các giá trị đầu vào là các hằng số a, b, c tương ứng, giả sử a = 1; b = 3; c = 2 (phương trình là x2 + 3x +2 = 0). Chương trình chạy sẽ cho x1 = -1; x2 = -2. Vậy tính duy nhất của đầu ra không phải là nó ra duy nhất một nghiệm, mà nằm ở chỗ, với cùng một thuật toán, chạy trên các máy (bộ vi xử lý) khác nhau sẽ thu được kết quả giống nhau, đó là tính duy nhất.

Tiếp theo mình muốn nói đến những đặc trưng cơ bản nhất của một thuật toán. Chúng bao gồm :

  1. Yếu t vào – ra (input/output): mọi thuật toán dù đơn giản đến mấy cũng phải có đầu vào (input) và đàu ra (output)
  2. Tính dng (Finitary) : sau một số bước hữu hạn thuật toán phải dừng.
  3. Tính chính xác (Exactitude): đảm bảo các bước tính toán là chính xác và cho kết quả tính toán chính xác đúng như mong đợi. Việc test thử chương trình chỉ giúp ta phát hiện chương trình có sai hay không chứ hoàn toàn không thể đảm bảo chương trình sẽ chạy đúng. Để chứng minh chính xác là chương trình sẽ chạy đúng ta phải dung đến toán học. VIệc làm này thường rất khó, nếu có thời gian mình sẽ post trong một bài khác.
  4. Tính hiu qu (effectiveness): Tính hiệu quả của thuật toán được đánh giá dựa trên một số tiêu chuẩn như khi lưng tính toán (khả năng chịu đựng của thuật toán), không gian (dung lượng bộ nhớ sử dụng – thông thường quan tâm đến bộ nhớ RAM) và thi gian khi thuật toán được thi hành. Tính hiệu quả của thuật toán là một yếu tố quyết định để đánh giá, chọn lựa cách giải quyết vấn đề – bài toán trên thực tế. Có rất nhiều phương pháp để đánh giá tính hiệu quả của thuật toán. Mình sẽ viết về chủ đề phân tích độ phức tạp của thuật toán trong những chủ đề sau.
  5. Tính tng quát (generalliness): thuật toán có tính tổng quát là thuật toán phải áp dụng được cho mọi trường hợp của bài toán chứ không phải chỉ áp dụng được cho một số trường hợp riêng lẻ nào đó. Nói cách khác, thuật toán có thể giải được mọi bài toán trong miền xác định input. Chẳng hạn giải phương trình bậc hai bằng Delta đảm bảo được tính chất này vì nó luôn giải được với mọi giá trị số thực a,b,c bất kỳ. Tuy nhiên, không phải thuật toán nào cũng đảm bảo được tính tổng quát. Trong thực tế, có lúc người ta chỉ xây dựng thuật toán cho một dạng đặc trưng của bài toán mà thôi.

Hiện nay, hầu như các bài toán thực tế đều ẩn chứa các lĩnh vực tìm kiếm, hoặc sp xếp nên các giải thuật về những lĩnh vực này rất nhiều. Những thuật toán đó là những điều tối thiểu mà chúng cần phải nắm được nếu muốn trở thành một tay lập trình viên hạng “xịn”. Mình sẽ lần lượt giới thiệu chúng trong các bài tiếp theo. Chúc các bạn thu được nhiều điều bổ ích từ bài viết này

From Rocky

Gửi phản hồi

Mời bạn điền thông tin vào ô dưới đây hoặc kích vào một biểu tượng để đăng nhập:

WordPress.com Logo

Bạn đang bình luận bằng tài khoản WordPress.com Log Out / Thay đổi )

Twitter picture

Bạn đang bình luận bằng tài khoản Twitter Log Out / Thay đổi )

Facebook photo

Bạn đang bình luận bằng tài khoản Facebook Log Out / Thay đổi )

Google+ photo

Bạn đang bình luận bằng tài khoản Google+ Log Out / Thay đổi )

Connecting to %s

%d bloggers like this: