Quy trình giải quyết một vấn đề – phần 1

Bài viết được dịch ở chương 4 trong Object First của Stephen Edwards, Brian Dorn, và Dean Sanders. Ở phần này, tác giả giới thiệu ngắn gọn một quy trình cơ bản để xây dựng và tìm ra giải pháp cho một vấn đề. Và nó không chỉ dành riêng cho khoa học máy tính. Quy trình này có thể được sử dụng để giải quyết rất nhiều vấn đề, bao gồm những vấn đề ngoài phạm trù liên quan đến IT.

Vấn đề, giải pháp và công cụ hỗ trợ

Tôi có một vấn đề! Tôi cần cảm ơn dì Kay vì món quà sinh nhật. Tôi có thể gửi một lá thư cảm ơn, có thể gọi điện thoại hoặc gửi một email, thậm chí tôi có thể lái xe đến và cảm ơn dì ấy trực tiếp. Trong thực tế, có rất nhiều cách để cảm ơn dì tôi, nhưng đó không phải vấn đề. Vấn đề là tôi phải quyết định tôi sẽ giải quyết vấn đề như thế nào và sử dụng công cụ hỗ trợ thích hợp để thực hiện kế hoạch của mình. Dịch vụ bưu chính, điện thoại, internet và ô tô của tôi là những công cụ mà tôi có thể sử dụng, nhưng không cách nào trong số này thực sự giải quyết được vấn đề. Tương tự, máy tính không tự giải quyết được vấn đề, nó chỉ là một công cụ hỗ trợ được tôi sử dụng để thực hiện theo kế hoạch nhằm giải quyết vấn đề của mình.

Biết rằng dì Kay đánh giá cao sự sáng tạo và khác thường, tôi đã quyết định thuê một người đưa tin để gửi lời cảm ơn. Trong trường hợp này, người đưa tin là một công cụ, nhưng tôi cũng cần phải hướng dẫn anh ấy. Tôi phải nói với người đưa tin nơi dì đang sống, muốn gửi tin nhắn vào thời điểm nào, và lời bài hát tôi muốn hát. Một chương trình máy tính là cái gì đó tương tự như hướng dẫn của tôi với người đưa tin.

Câu chuyện với dì Kay đã sử dụng một trường hợp quen thuộc để tạo ra một viễn cảnh cho một quan điểm liên quan đến máy tính và chương trình máy tính. Danh sách sau tóm tắt các khía cạnh chính của quan điểm này.

• Máy tính là một công cụ được sử dụng để hiện thực một kế hoạch nhằm giải quyết một vấn đề.
• Một chương trình máy tính là một tập hợp các lời chỉ dẫn cho một máy tính. Những chỉ dẫn này miêu tả các bước để máy tính theo đó triển khai kế hoạch.
• Một thuật toán là một kế hoạch để giải quyết vấn đề.
• Một người cần phải thiết kế một thuật toán.
• Một người phải chuyển hóa một thuật toán thành một chương trình máy tính.

Quan điểm này đặt ra cách nhìn tổng quát cho quy trình mà chúng ta sẽ sử dụng để xây dựng giải pháp cho các vấn đề. Quy trình cơ bản này rất quan trọng vì nó có thể được sử dụng để giải quyết nhiều vấn đề, bao gồm cả những vấn đề mà hướng giải quyết sẽ được viết bằng nhiều ngôn ngữ lập trình khác nhau.

Một quy trình xây dựng thuật toán

Tất cả mọi hướng giải quyết bắt đầu với một kế hoạch. Kế hoạch đó được gọi là một thuật toán.

Có rất nhiều cách để viết ra một thuật toán. Một số không chính thức, một số khá chính thức và có tính chất toán học, và một số có tính đồ thị. Các chỉ thị để kết nối đầu DVD với TV là một thuật toán. Một công thức toán học như πR² là một trường hợp đặc biệt của một thuật toán. Biểu thức không đặc biệt quan trọng miễn là nó cung cấp một cách hợp lí để mô tả và kiểm tra tính logic của hướng giải quyết đề ra.

Việc xây dựng một thuật toán (một kế hoạch) là một bước quan trọng để giải quyết vấn đề. Một khi chúng ta nắm được thuật toán, chúng ta có thể chuyển hóa nó thành một chương trình máy tính bằng một số ngôn ngữ lập trình. Quy trình phát triển một thuật toán cơ bản bao gồm năm bước chính.

Bước 1: Nắm được các miêu tả của vấn đề.

Step 2: Phân tích vấn đề.

Step 3: Phát triển thuật toán cấp cao.

Step 4: Tinh chỉnh thuật toán bằng cách thêm chi tiết.

Step 5: Xem xét lại thuật toán.

Bước 1: Nắm được các miêu tả của vấn đề

Bước này khó hơn nhiều so với tưởng tượng. Trong phần đề cập dưới đây, từ “client” để chỉ đến những người muốn tìm một giải pháp cho một vấn đề, và từ “developer” để chỉ những ai muốn tìm cách giải quyết vấn đề đó. Developer phải viết được một thuật toán để giải quyết vấn đề của client.

Client chịu trách nhiệm tạo ra bản mô tả cho một vấn đề, nhưng đây thường là mắc xích lỏng lẻo nhất của quy trình. Vì nó thường gặp phải một số trường hợp khiếm khuyết sau : Những mô tả dựa trên các giả định không rõ ràng, mô tả quá mơ hồ, các bản mô tả không đầy đủ, mô tả có những mâu thuẫn từ bên trong. Những khiếm khuyết này không phải hoàn toàn do sự thiếu thận trọng của client. Mà là do cách giao tiếp giữa các ngôn ngữ bản xứ ( english, french, korean, etc) không chính xác. Một phần trách nhiệm của developer là xác định các khiếm khuyết trong cả bản mô tả vấn đề, và làm việc với client khắc phục nó.

Bước 2: phân tích vấn đề

Mục đích của bước này là xác định điểm bắt đầu và kết thúc để giải quyết vấn đề. Quá trình này tương tự như cách nhà toán học xác định những gì được đưa ra và những gì được chứng minh. Một bản mô tả vấn đề tốt sẽ là đòn bẩy để hoàn thành bước này dễ dàng hơn.

Khi xác định điểm bắt đầu chúng ta nên bắt đầu tìm kiếm câu trả lời dựa theo những câu hỏi sau:

• Có những dữ liệu gì ?
• Dữ liệu nằm ở đâu ?
• Công thức nào liên quan đến vấn đề ?
• Các quy tắc nào nên tồn tại để làm việc với dữ liệu ?
• Mối quan hệ nào tồn tại giữa các giá trị dữ liệu ?

Khi xác định điểm kết thúc, chúng ta cần mô tả các đặc tính của một giải pháp. Nói cách khác, chúng ta sẽ biết khi nào chúng ta đã làm xong? Trả lời các câu hỏi sau sẽ giúp chúng ta xác định được điểm kết thúc:

• Sẽ có những sự kiện mới nào?
• Những mục nào sẽ thay đổi?
• Những thay đổi nào sẽ được thực hiện trong những mục đó?
• Những gì sẽ bị xóa đi?

Bước 3: Xây dựng một thuật toán cấp cao

Một thuật toán là một kế hoạch để giải quyết vấn đề, nhưng kế hoạch vẫn có nhiều cấp độ về tính chi tiết.  Chúng ta nên bắt đầu với một thuật toán cấp cao với phần chính của nó, nhưng không liệt kê chi tiết cụ thể về sau. Chúng ta có thể sử dụng một ví dụ đơn giản thường ngày để thể hiện thuật toán cấp cao.

Vấn đề: Tôi cần gửi một tấm thiệp chúc mừng sinh nhật cho anh trai mình, Mark

Phân tích: Tôi không có một tấm thiệp. Tôi thích mua nó hơn là tự làm.

Thuật toán cấp cao:

• Đến cửa hàng bán thiệp chúc mừng
• Chọn mua một
• Thanh toán
• Gửi thiệp

Thuật toán rất hợp lí để sử dụng, nhưng nó thiếu chi tiết cần phải bổ sung để một máy tính có thể thực hiện theo. Những chi tiết này là câu trả lời cho các câu hỏi như sau:

• “Tôi sẽ đến cửa hàng nào?”
• “Làm thế nào để đến đó: đi bộ, lái xe, xe đạp, xe buýt?”
• “Loại thiệp nào mà Mark thích: hài hước, tình cảm?”

Những chi tiết này sẽ được xem xét trong bước tiếp theo của quy trình .

Bước 4: Tinh chỉnh thuật toán bằng cách thêm chi tiết

Thuật toán cấp cao cho thấy các bước chính để giải quyết vấn đề. Bây giờ chúng ta cần thêm chi tiết cho các bước này, nhưng nên bổ sung bao nhiêu chi tiết? Câu trả lời phụ thuộc vào tình hình bạn gặp phải. Chúng ta phải xem xét ai (hoặc những gì) sẽ thực hiện thuật toán và số người đó đã biết làm như thế nào chưa?. Nếu ai đó sẽ thay mặt tôi mua thiệp sinh nhật cho Mark, những hướng dẫn của tôi phải được điều chỉnh cho phù hợp với việc người đó có quen thuộc với các cửa hàng trong thành phố và cho anh ta biết được loại thiệp mà anh trai tôi thích.

Khi mục tiêu của chúng ta là xây dựng các thuật toán hướng dẫn các chương trình máy tính, chúng ta cần xem xét các tính năng của máy tính và cung cấp đủ chi tiết để người khác có thể sử dụng thuật toán viết một chương trình máy tính theo các bước trong thuật toán đó. Cũng như vấn đề với thiệp sinh nhật, chúng ta cần điều chỉnh mức độ chi tiết để phù hợp với khả năng của người lập trình.

Hầu hết các ví dụ sẽ chuyển từ một mức độ cao đến một thuật toán chi tiết trong một bước, nhưng điều này không phải lúc nào cũng hợp lý. Đối với các vấn đề phức tạp hơn, thông thường phải trải qua quá trình này nhiều lần, chỉ phát triển các thuật toán ở mức trung bình. Mỗi lần, chúng ta thêm chi tiết cho thuật toán trước đó, và thấy không có lợi ích để chỉnh sửa thêm hãy dừng lại. Kỹ thuật chuyển hóa mức cao đến một thuật toán chi tiết được gọi là stepwise refinement.

Stepwise refinement is a process for developing a detailed algorithm by gradually adding detail to a high-level algorithm.

Bước 5: Xem lại thuật toán.

Bước cuối cùng xem lại thuật toán. Chúng ta đang tìm kiếm cái gì? Trước tiên, chúng ta cần phải chạy trên toàn bộ thuật toán từng bước để xác định liệu nó sẽ giải quyết vấn đề ban đầu đưa ra không? Một khi thuật toán đã giải quyết được vấn đề, chúng ta bắt đầu tìm kiếm những thứ khác. Những câu hỏi điển hình sau đây sẽ được đưa ra khi chúng ta xem xét một thuật toán.

1. Liệu thuật toán này giải quyết một vấn đề cụ thể hay nó giải quyết một vấn đề tổng quát hơn? Nếu nó giải quyết một vấn đề cụ thể, nó có nên được tổng quát?
   • Ví dụ, một thuật toán tính diện tích của một vòng tròn có bán kính 5.2 mét (công thức π*5.2²) giải quyết một vấn đề rất cụ thể, nhưng một thuật toán tính diện tích của bất kỳ vòng tròn nào (công thức π*R²) giải quyết một vấn đề tổng quát hơn.
2. Thuật toán này có thể được đơn giản hóa không?
   • Công thức tính chu vi của một hình chữ nhật là: chiều dài + chiều rộng + chiều dài + chiều rộng . Công thức đơn giản là: 2,0 * (chiều dài + chiều rộng).
3. Đây có phải là giải pháp tương tự như các giải pháp cho vấn đề khác? Họ giống nhau như thế nào? Họ khác nhau như thế nào?
   • Ví dụ, hãy xem xét hai công thức sau:
     • Diện tích chữ nhật = chiều rộng * chiều rộng
     • Diện tích tam giác = 0,5 * đường cơ sở * chiều cao
   • Các điểm tương đồng: Mỗi phép tính đều tính diện tích. Đều là nhân hai biến.
   • Sự khác biệt: Các phép nhân khác nhau. Công thức tam giác có 0.5.
   • Giả thuyết: Có lẽ mỗi công thức tính diện tích đều bao gồm 2 giá trị đo.

Ví dụ:

Phần này là một ví dụ mở rộng thể hiện quy trình xây dựng thuật toán. Để hoàn thành, chúng ta cần phải biết rằng mỗi Jeroo có thể nhảy về phía trước, rẽ trái và phải, chọn một bông hoa từ vị trí hiện tại của nó, và trồng một bông hoa ở vị trí hiện tại của nó.

 Bước 1 : Trình bày vấn đề

Jeroo bắt đầu ở (0, 0) không có hoa trong túi. Có một bông hoa ở vị trí (3, 0). Viết một chương trình để giúp Jeroo lấy hoa và trồng ở vị trí (3, 2). Không có lưới săn bắt ( vật cản ) hay một con Jeroo khác.

Bắt đầu                                                                            Kết thúc

Bước 2: Phân tích vấn đề

1. Hoa cách Jeroo chính xác 3 ô.
2. Hoa sẽ được trồng tại vị trí cách hai ô ở phía dưới với vị trí hiện tại của nó.
3. Không có lưới săn bắt để tránh.

Bước 3 : Thuật toán cấp cao 

Hãy đặt tên cho Jeroo là Bobby. Bobby nên làm như sau:

• Lấy hoa
• Trồng hoa

Bước 4: Triển khai chi tiết

Hãy đặt tên cho Jeroo là Bobby.

Bobby nên làm như sau:

• Lấy hoa
  • Nhảy về bên phải 3 lần
  • Lấy hoa
• Trồng hoa
  • Rẽ phải nhảy 2 lần
  • Trồng hoa

Bước 5 : Xem lại thuật toán

1. Thuật toán cấp cao phân chia vấn đề thành 2 bài toán con khá dễ. Đây là một kỹ thuật tốt.
2. Thuật toán này giải quyết một vấn đề rất cụ thể vì Jeroo và hoa ở những vị trí rất cụ thể.
3. Thuật toán này cũng có thể coi là một thuật toán hơi tổng quát trong trường hợp Jeroo ở bất kì vị trí nào và hoa cách Jeroo theo đường thẳng 3 ô.

Tectalk via sofia.cs.vt.edu