Bảo khoa học máy tính là những gì nói về những cái máy, thì cũng như nói khoa học vũ trụ là những gì nói về chiếc kính viễn vọng cả. Khoa học máy tính là những gì mà ở sâu ở nền tảng, nơi xuất phát vẻ đẹp của nó, là những gì được cất lên bằng toán học - EDSGER DIJKSTRA
Những chiếc máy tính cần sự có mặt của chúng ta để "xé" (phần tách - break down) một vấn đề (bài toán) để chúng có thể "nhai" vấn đề đó một cách dễ dàng. Để làm được điều đó, chúng ta cần toán học. Đừng hoảng sợ, đây không phải là khoa học hỏa tiễn - để viết một dòng code tốt bạn không nhất thiết phải dùng đến những phương trình phức tạp. Chương này sẽ cho bạn biết một bộ công cụ (toolbox) để giải quyết vấn đề (problem solving)
Ở chương này em sẽ học những công cụ sau:
- Mô hình những ý tưởng dưới dạng biểu đồ luồng (flowchart) và mã giả (pseudocode)
- Phân biệt đúng và sai bằng luận lý logic
- Bài toán đếm
- Tính toán xác suất
Với những công cụ trên, em có thể biến các ý tưởng của mình thành một lời giải điện toán (lời giải mà có thể mô tả (viết) được bằng ngôn ngữ lập trình).
Khi em có một công việc phức tạp (complex là phức tạp - complex task), việc đầu tiên em nên làm, không phải ngồi sợ hay than vãn là: viết tất những gì quan trọng lên một tờ giấy. Bộ não em giống như bộ nhớ trong của máy tính (RAM) sẽ nhanh chóng bị quá tải mới những ý tưởng hoặc các thực tế (fact là thực tế). Viết mọi thứ xuống một tờ giấy là công việc tối quan trọng của mọi kỹ năng sắp xếp và giải quyết công việc. Có một vài cách để làm việc đó. Đầu tiên chúng ta sẽ tham khảo biểu đồ luồng (flowchart) dùng để mô tả các quá trình. Sau đó chúng ta sẽ học cách mô tả các tiến trình lập trình bằng mã giả (pseudocode). Chúng ta cũng sẽ học cách mô hình (model) một bài toán, vấn đề đơn giản bằng toán học.
Khi những biên tập viên của Wikipedia mô tả về quá trình làm việc nhóm (collaboration process) của họ, thì họ tạo ra một biểu đồ luồng. Họ cho rằng đưa ra một hình ảnh trực quan về tiến trình này sẽ giúp công việc làm việc nhóm của họ sẽ được thông suốt hơn.
Cũng giống như quá trình chỉnh sửa bài viết của Wiki, code máy tính cũng chỉ đơn giản là một tiến trình (process). Lập trình viên thường dùng những biểu đồ luồng để mô tả các tiến trình máy tính. Muốn tạo ra được biểu đồ luồng người khác có thể hiểu, trước em phải tuân theo các chỉ dẫn như sau:
- Mô tả trạng thái và các bước chỉ dẫn (instruction step) bên trong hình hộp chữ nhật
- Mô tả các bước quyết định, rẽ nhánh bên trong một hình thoi.
- Đừng bao giờ nhập nhằng giữ các bước chỉ dẫn và các bước rẽ nhánh.
- Sử dụng mũi tên để nối các bước đi liền.
- Đánh dấu bằng màu (hoặc bằng một dấu hiếu nào đó) trạng thái bắt đầu và trạng thái kết thúc.
Ví dụ dưới đây mô tả công việc tìm số lớn nhất trong ba số:
Cũng giống như flowcharts (từ nay anh sẽ viết biểu đồ luồng là flowcharts), mã giả cũng dùng để mô tả các tiến trình điện toán (computational process - computational là tính từ chỉ những gì liên quan đến điện toán máy tính). Ví dụ dưới đây là mô tả các bước tìm số lớn nhất trong ba số bằng mã giả:
[^Chú thích 2]: ← là phép gán: x ← 1 tức là gán 1 cho x
Chú ý rằng mã giả không phải là một ngôn ngữ lập trình thực thụ, dù nhìn khác giống, nó không có các luật cú pháp chặt chẽ như ngôn ngữ lập trình ? Thậm chí em có thể đọc nó lên bằng ngôn ngữ thông thường! Tương tự như việc sử dụng flowcharts để tạo một "bản đồ tư duy" thông thường, hãy để luồng sáng tạo thoải mái khi em viết mã giả.
[^Chú thích hình ảnh]: Màu xanh - để mô tả một thuật toán, màu hồng - một công cụ để những sinh viên năm một ngành khoa học máy tính (mới bắt đầu học lập trình) mô tả những hành động ngu ngốc của họ
Một mô hình (model - cần nhớ định nghĩa này, một từ khóa liên quan đến triết học, và phương pháp tư duy) là một tập hợp các khái niệm (concept) dùng để mô tả một bài toán và các đặc tính của nó. Nó cho phép chúng ta dễ dàng đưa ra lý lẽ và phân tích bài toán đó. Kỹ năng mô hình hóa là một kỹ năng quan trọng thường được dạy trong trường học. Toán cấp 3 dạy chúng ta mô hình hóa các bài toán dưới dạng các con số và các đẳng thức, và sau đó áp dụng các kỹ thuật suy ra, khi và chỉ khi, nhằm đi đến kết luận cần chứng minh.
Sử dụng các mô hình toán học để mô tả bài toán mang lại cho chúng ta rất nhiều lợi thế: chúng ta có thể đưa vào máy tính để lưu trữ một cách dễ dàng, vì vốn dĩ máy tính được tạo bởi các kỹ thuật toán rất vững chắc. Nếu như mô hình của em có các đồ thị (graphs), thì ta sẽ sử dụng lý thuyết đồ thị (graph theory) để mô tả bài toán của chúng ta. Nếu chúng có các đẳng thức, ta sử dụng đại số. Mô hình bài toán máy tính bằng toán học giống như ta đang đứng trên vai người khổng lồ để giải quyết vấn đề điện toán. Bây giờ ta sẽ xem xét các ví dụ sau đây:
BÀI TOÁN HÀNG RÀO TRANG TRẠI: Trang trại của bạn có hai loại gia súc. Bạn có 100 đơn vị dây kẽm để tạo ra hàng rào hình chữ nhật cho gia súc của bạn, và với một đường thẳng chung để chia đôi chúng. Bạn sẽ tạo khung rào như nào để tối đa được diện tích chuồng trại ?
Với bài toán trên ta sẽ coi w, l tương ứng là chiều rộng và chiều dài của trang trại; như vậy w x l là diện tích của trang trại. Chúng ta cần tối đa diện tích của trang trại, như vậy ta sẽ sử dụng hết chiều dài dây kẽm có. Như vậy ta sẽ có những đẳng thức sau:
A = w x l
100 = 2w + 3l
Như vậy bài toán sau sẽ được mô hình dưới dạng ngôn ngữ toán học như sau: $$ A = w \times l \ 100 = 2w + 3l \ $$ Chọn w và l sao cho A là lớn nhất.
Như vậy để giải quyết bài toán trên ta đơn giản giải quyết một bài toán tìm cực trị đơn giản. Đầu tiên ta sẽ chuyển vế đẳng thức 2 để xác định l: $$ l = \frac{100 - 2w}{2} $$ Thay l vào phương trình thứ nhất ta được: $$ A = \frac{100}{3}w - \frac{2}{3}w^2 $$ Đây là một phương trình bậc hai! để tìm cực trị của nó ta chỉ cần sử dụng công thức bậc hai (quadratic formular) là ra được. Phương trình bậc hai quan trọng cho người giải giống hệt như nồi áp suất quan trọng đối với việc nấu ăn vậy. Chúng tiết kiệm thời gian cho ta, và giúp ta giải toán nhanh hơn. Hãy nhớ rằng, trách nhiệm của em là giải quyết các bài toán, và em cần biết các công cụ mà mình có, giống như đầu bếp có dao và thớt. EM cần biết cách mô hình một phát biển bài toán dưới dạng toán học, và cần biết sử dụng logic để giải quyết nó.