Sắp xếp

Về vấn đề này, ta chỉ cần nắm 2 cách sắp xếp là:

• Sắp xếp nổi bọt (Bubble Sort).
• Sắp xếp nhanh (Quick Sort).

Trong đây đề cập đến việc sắp xếp tăng một mảng số nguyên.

1. Sắp xếp nổi bọt:
Độ phức tạp: O(n.n).
Đánh giá: Đây là phương pháp sắp xếp đơn giản nhất. Nhưng với bài toán có dữ liệu lớn (n = 50000 chẳng hạn), phương pháp này không khả thi.
Phân tích thuật toán:

• Với hai phần tử a[i] và a[i + 1], nếu a[i] > a[i + 1] thì ta đổi chỗ hai phần tử này.
• Với n phần tử, gọi k đi từ n về 2, i đi từ 1 tới k, nếu a[i] > a[i + 1] thì ta đổi chỗ. Sau mỗi vòng lặp của i, phần tử a[k] là phần tử lớn nhất trong đoạn [1, k].
Áp dụng:

• UVa 299 -  Train Swapping.
• UVa 612 - DNA Sorting.
• UVa 10327 - Flip Sort.
2. Sắp xếp nhanh:
Độ phức tạp trung bình: O(n log n).
Độ phức tạp cao nhất: O(n.n).
Đánh giá: Trong các điều kiện thích hợp, đây là phương pháp sắp xếp nhanh nhất trong các thuật toán sắp xếp thông dụng. Ngoài ra, với ngôn ngữ C/C++, ta có thể rút gọn hàm sắp xếp, giúp tiết kiệm thời gian làm bài cũng như tốc độ xử lý của chương trình.
Phân tích thuật toán:

1. Gọi d và c là hai biến lưu địa chỉ đầu và cuối của đoạn cần sắp xếp, k là giá trị của phần tử A[(d + c) / 2] (phần tử giữa đoạn).
2. gán i = d, j = c.
3. Trong khi A[i] < k thì tăng i 1 đơn vị (phần tử trước nhỏ hơn phần tử sau).
4. Trong khi A[j] > k thì giảm j 1 đơn vị (phần tử sau lớn hơn phần tử trước).
5. Nếu i ≤ j (gặp hai phần tử A[i] > a[j]) thì tiến hành đổi chỗ A[i], A[j], sau đó tăng i 1 đơn vị, giảm j 1 đơn vị.
6. Nếu i > j thì thoát vòng lặp. Ngược lại quay về bước 3.
7. Nếu i < c thì sắp xếp tiếp đoạn [i; h].
8. Nếu d > j thì sắp xếp tiếp đoạn [d, j].

Áp dụng thường: Tìm kiếm nhị phân, thuật giải tham lam (nhằm ưu tiên chọn cái tốt nhất trước), bài toán sắp lịch, tìm đa giác lồi (thuật toán tìm bao lồi Graham), ...

Tham khảo thêm:

• Sắp xếp nổi bọt: http://vi.wikipedia.org/wiki/S%E1%BA%AFp_x%E1%BA%BFp_n%E1%BB%95i_b%E1%BB%8Dt.
• Sắp xếp nhanh: http://vi.wikipedia.org/wiki/S%E1%BA%AFp_x%E1%BA%BFp_nhanh.
• Hàm qsort (sắp xếp nhanh) trong C/C++ (Lưu ý: phải hiểu được cách sử dụng con trỏ trong C/C++ trước khi sử dụng): http://www.cplusplus.com/reference/cstdlib/qsort/.

Phần mềm ...

Nhà trường phổ thông dạy cho chúng ta cách để giải một bài toán, nhưng chưa chắc đã dạy cho chúng ta cách ứng dụng chúng đưa vào đời sống thực tiễn.
Với chuyên tin cũng vậy. Chúng ta được học cách giải một bài toán và giải bài toán đó tối ưu hơn. Nhưng có ai tự hỏi rằng: Bài toán ứng dụng thực tiễn như thế nào? Phần mềm là câu trả lời cho vấn đề trên.
Phần mềm - hai chữ này có vẻ gì đó cao siêu đối với nhiều người. Nhưng thực ra, nó chỉ đóng gói các bước thực hiện một bài toán (hoặc nhiều bài toán) thành một gói duy nhất. Tất nhiên là để tạo ra nó, phải học cách sử dụng công cụ tạo ra nó (IDE và ngôn ngữ lập trình, các công cụ hỗ trợ, ...), và điều đó không quan trọng. Điều quan trọng là: Ý tưởng của bạn là gì? Tính thực tiễn của nó cao hay không? Nó có thể được làm như thế nào? Phương pháp bạn làm có khả thi và tối ưu không?
Với mình, cách để tìm một ý tưởng là: đi dạo, vì chỉ có đi dạo mới thấy được thực tiễn hiện hữu, để thấy những bất cập, những cái người ta cần, và suy nghĩ xem nó có khả thi không (Ví dụ: chẳng ai làm được phần mềm để yêu cả, hay anh không thể dùng phần mềm để bắt mọi người chấp hành luật giao thông).
Có ý tưởng rồi, tạo chúng ư? Công cụ rất nhiều: C/C++, C#, VB.NET, PHP, Java, ... và cả Pascal nữa. Việc học chúng cũng rất đơn giản, nhất là với các ngôn ngữ hỗ trợ sẵn như: C#, VB.NET, Java.
Một số điều mình muốn nói nữa là:

• Cho dù cách bạn giải quyết bài toán rất "đẹp", nhưng nếu bạn không chú ý đến diện mạo phần mềm thì coi như bạn "công cốc". Vì người sử dụng người ta không quan tâm cách bạn giải quyết, người ta chỉ quan tâm: Sử dụng phần mềm như thế nào? Kết quả xử lý có đúng không ?
• Đừng so sánh giữa các ngôn ngữ lập trình với nhau, cái nào cũng có mặt lợi và mặt khó khăn của nó. Đừng nói rằng: "để làm được phần mềm này, bọn tui sử dụng ngôn ngữ abcxyz gì đó, và phải làm việc rất nhiều do ngôn ngữ này không hỗ trợ một thứ gì đó, trong khi các anh dùng ngôn ngữ ghiklm, bọn tui thấy nó hỗ trợ nhiều và lập trình dễ hơn". Vì sao? Đó là so sánh khập khiễn, cách nhìn phiến diện, qua loa mà chưa đứng ở góc độ người làm việc. Bạn có chắc bạn sẽ làm được nó không?
• Ý tưởng mới không có nghĩa là mọi thứ trong ý tưởng đều mới, mà là cách bạn giải quyết chúng theo một hướng hoàn toàn mới.

Ở cấp học phổ thông, về phần mềm thì có cuộc thi Tin học trẻ - bảng D là được biết đến rộng rãi. Nhưng mình thấy những phần mềm ở cuộc thi này hình như thiếu tính thực tiễn, vì mình vẫn chưa thấy phần mềm nào được ứng dụng trong cuộc sống (mình không nói tất cả), và mang tính cạnh tranh quá nhiều (vì tỉnh nhà mà, bất chấp thủ đoạn là điều dễ hiểu). Còn một cuộc thi khác là Sáng tạo khoa học công nghệ thanh thiếu niên nhưng mình chưa tìm hiểu nó.
Tuy nhiên, nếu như có điều kiện, bạn hãy tạo một phần mềm của riêng mình, sau đó có thể đưa nó ra thực tiễn thông qua một thứ gì đó (Google Plays, Apple Store, hay nhờ một người trung gian giới thiệu sản phẩm). Còn nếu đã vì tỉnh nhà và cần có giải, hãy suy nghĩ về một thứ gì đó đơn giản và ứng dụng được (ví dụ như quản lý dữ liệu chẳng hạn), làm một cái giao diện thân thiện, thêm một vài chức năng bạn cảm thấy thích, và quan trọng là trình bày báo cáo một cách rõ ràng. Vì sao ư? Chúng ta có rất ít thời gian để giải quyết chúng (còn học hành nữa).

Một số tính chất đặc biệt khác trong số học, phần 1

1. Tính chất 1:
Giả sử số nguyên N có thể được phân tích thành: N = X1 ^ Y1 * X2 ^ Y2 * ... * Xk ^ Yk, thì số ước của N sẽ là: D = (Y1 + 1) * (Y2 + 1) * ... * (Yk + 1).
Chứng minh:
Có Y1 số X1, Y2 số X2, ..., Yk số Xk. Theo quy tắc nhân, số các số được tạo thành từ các số con số này sẽ là S = (Y1 + 1) * (Y2 + 1) * ... (Yk + 1). Theo giả thiết, S cũng là số lượng ước của N.
Bài mẫu: UVa 294 - Divisors.
2. Tính chất 2:
Dãy fibonacci có dạng:
f(0) = 0
f(1) = 1
f(n) = f(n - 1) + f(n - 2)
Gọi a là một số nguyên dương khác 0.
Khi đó, dãy g(n) = f(n) mod a mang tính chất chu kỳ.
Ví dụ:
a = 3
f(n): 0 1 1 2 3 5 8 13 15 28 43 ...
g(n): 0 1 1 2 0 2 2 1 0 1 1 ...
Thông tin: http://en.wikipedia.org/wiki/Pisano_period.
Bài mẫu: SPOJ FIBVAL - Bản Vanxơ Fibonacci.

Về các bài toán đặc biệt (Ad-hoc problems)

1. Giới thiệu:
Các bài toán đặc biệt là các bài toán không thể phân loại vào bất cứ lớp bài toán nào, và các phương pháp giải quyết bài toán được coi là độc đáo. Các bài toán này có thể được phân loại thành hai dạng: đơn giản và bài toán mô phỏng (bài toán có một số quy tắc mô phỏng câu trả lời).
Các bài toán đặc biệt thường xuất hiện trong các cuộc thi lập trình. Trong một bộ đề chuẩn (10 bài), có thể có 1 - 2 bài toán đặc biệt. Nếu bài toán đơn giản, nó là bài toán đầu tiên mà các thí sinh (hoặc đội thi - ở đây gọi tắt là đội) chọn để giải quyết. Nhưng vẫn tồn tại những bài toán mang tính phức tạp, một số thí sinh (đội) sẽ chọn chiến thuật gác lại bài này để làm các bài khác cho đến hết giờ làm bài.
2. Ví dụ:
Bài toán: UVa 100 - The 3n + 1 Problems.
Nguồn bài: http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=36.

1. Phân tích đề bài:
• Đề cho một giải thuật:
1. Nhập vào số n.
2. In ra số n.
3. Nếu n = 1 thì dừng lại.
4. Nếu n là số lẻ thì n := 3n + 1, ngược lại n := n / 2.
5. Quay lại bước 2.
• Và cho một ví dụ:
Với n = 22, theo thuật toán, ta sẽ in ra màn hình các số như sau: 22 11 34 17 52 26 13 40 20 10 5 16 8 4 2 1. Như vậy, từ lúc nhập vào số n cho đến lúc n = 1, ta sẽ in ra 16 con số, và con số đó được gọi là chu kỳ của số n.
• Yêu cầu:
Cho hai số i và j. Hãy tìm số n (i ≤ n ≤ j) sau cho chu kỳ của số n là lớn nhất.
2. Triển khai thuật toán:
1. Từ hai số i, j đã nhập vào. Nếu i > j ta đổi chỗ i, j.
2. x := i, max (chu kỳ lớn nhất) := 0.
3. Nếu x > y thì in kết quả max, kết thúc chương trình.
4. n := x.
5. k := 1.
6. Nếu n = 1 chuyển sang bước 9.
7. Nếu n là số lẻ thì n := 3n + 1, ngược lại n := n / 2.
8. k := k + 1.
9. Nếu k > max thì max := k.
10. x := x + 1. Quay lại bước 3.
3. Một số bài toán khác:
• UVa 272 - TEX Quotes.
• UVa 394 - Mapmaker.
• UVa 483 - Word Scramble.
• UVa 573 - The Snail.
• UVa 661 - Blowing Fuses.
• UVa 739 - Soundex Indexing.
• UVa 837 - Light and Transparencies.
• UVa 941 - Permutations.
• UVa 10082 - WERTYU.
• UVa 10141 - Request for Proposal.
• UVa 10281 - Average Speed.
• UVa 10363 - Tic Tac Toe.
• UVa 10420 - List of Conquests.
• UVa 10528 - Major Scales.
• UVa 10683 - The decadary watch.
• UVa 10703 - Free spots.
• UVa 10812 - Beat the Spread.
• UVa 10921 - Find the Telephone.
• UVa 11044 - Searching for Nessy.
• UVa 11150 - Cola.
• UVa 11223 - O: dah, dah, dah!.
• UVa 11340 - Newspaper.
• UVa 11498 - Division of Nlogonia.
• UVa 11547 - Automatic Answer.
• UVa 11616 - Roman Numerals.
• UVa 11727 - Cost Cutting.
• UVa 11800 - Determine the Shape.
• SPOJ HAM12 - Khoảng cách Hamming.
• SPOJ FIBVAL - Bản vanxơ Fibonacci.

Tài liệu tham khảo:
Steven Halim, Felix Halim - Competitive Programing - First Edition. National University of Singapore.
USACO Traning Gateway - Ad-hoc Problems.

Chia sẻ:

• Đề bài chuẩn ở đây tương ứng với đề thi ACM/ICPC. Đề chuẩn của các kỳ thi tin học ở cấp THPT hay Olympic tin học sinh viên gồm 3 bài. Riêng đối với thi học sinh giỏi Quốc gia thì có 2 đề, tương ứng với 6 bài thi. Những bài thuộc lớp bài toán đặc biệt thường rơi vào bài số 3 (bài khó nhất). Đôi khi, nó cũng xuất hiện ở bài đầu tiên, nhưng ở mức độ dễ.
• Các lớp bài toán có thể là: Đệ quy, NP, Quy hoạch động, các bài toán không giải được, ...

Làm bài trực tuyến - Làm ở đâu, như thế nào ?

Cũng như các môn học khác, tin học cũng cần phải được rèn luyện thường xuyên để nâng cao kỹ năng, cũng như tiếp cận với các kiểu bài toán mới.
Không như các môn học khác, với tin học, sách là chưa đủ, vì các bài tập trong sách cũng chỉ mang tính chất lý thuyết. Với một bài toán thực nghiệm trong thi đấu là khác. Có khi cũng vẫn kiến thức ấy, nhưng chưa chắc đã giải quyết vấn đề mà đề thi đặt ra.
Rất may, có rất nhiều trang làm bài trực tuyến giúp chúng ta nâng cao trình độ. Các trang này chứa một lượng bài tập đồ sộ, mỗi bài tập đều có đầy đủ các test (bộ dữ liệu) để kiểm tra tính chính xác của bài làm của bạn.
Một số trang làm bài điển hình:

1. SPOJ:
Hỗ trợ trên 40 ngôn ngữ lập trình, bao gồm: C/C++, Pascal, Java.
Hỗ trợ các phương thức chấm: acm, oi, challenge, tutorial.
Ngoài trang chính thức bằng tiếng Anh, SPOJ cũng cung cấp nội dung của nó qua tiếng Ba lan, tiếng Bồ Đào Nha và tiếng Việt.
Nhận xét: điểm yếu của SPOJ là không cung cấp test cho người dùng kiểm tra lại (tuy có một số thành viên tình nguyện cung cấp cho người dùng ở một số bài).
Trang chính thức: http://www.spoj.com/.
Trang tiếng việt: http://vn.spoj.com/.
2. UVa Online Judge:
Trang làm bài của Đại học Valladolid, Tây Ban Nha.
Hỗ trợ các ngôn ngữ lập trình: C/C++, Pascal, Java.
Phương thức chấm: acm.
Điểm đặc biệt của UVa, là các bài tập mang tính chất "chuẩn", có phân theo các chủ đề.
Trang chính thức: http://uva.onlinejudge.org/.
3. Codeforces:
Hỗ trợ nhiều ngôn ngữ lập trình.
Phương thức chấm: acm.
Codeforces cho phép tham khảo mã nguồn của người khác cũng như xem các test chạy đúng. Tuy nhiên, không có nghĩa là bạn có quyền chép mã nguồn và nộp lại với tên của bạn. Codeforces có một chương trình cho phép quét mã nguồn của bạn và kiểm tra sự trùng hợp so với các mã nguồn của các tài khoản khác.
Trang chính thức: http://codeforces.com/.
4. USACO Training:
Đây là trang luyện tập của Olympic tin học Hoa Kỳ.
Hỗ trợ các ngôn ngữ lập trình: C/C++, Pascal.
Việc rèn luyện của bạn sẽ được phân thành các các chương, và bạn phải đi tuần tự qua các chương bằng việc giải quyết các bài tập trong chương đó. Các bài tập mang tính chất chuẩn và cố định. Trang này cũng cho phép bạn xem các test chạy đúng. Hiện tại, trên trang, một số thành viên của VNOI (Olympic tin học Việt Nam) đã tình nguyện dịch ra tiếng Việt một số bài tập.
Trang chính thức: http://ace.delos.com/usacogate.

Giới thiệu một số phần mềm phục vụ lập trình C/C++, Pascal trong nhà trường phổ thông

1. Giới thiệu về Môi trường phát triển tích hợp:
Môi trường phát triển tích hợp (Integrated Development Environment - IDE) hay Môi trường phát triển tương tác là một phần mềm ứng dụng cung cấp toàn diện các công cụ phục vụ cho việc phát triển phần mềm của các lập trình viên.
Một IDE cơ bản bao gồm:

• Trình soạn thảo mã nguồn (source code editor).
• Các công cụ tập hợp tự động (build automation tools).
• Trình gỡ rối (debugger).
Một số IDE hiện đại tích hợp thêm chức năng Intelli-sense (hỗ trợ viết mã nhanh).
Một số IDE tích hợp trình biên dịch (compiler), trình thông dịch ( interpreter), hoặc cả hai, điển hình là Microsoft Visual Studio, Eclipse. Ranh giới giữa Môi trường phát triển tích hợp (IDE) và Môi trường phát triển phần mềm (Software Development Environment) không có sự phân biệt rõ ràng. Đôi khi một hệ thống kiểm soát phiên bản (Version Control System) và các công cụ khác nhau được tích hợp để đơn giản hóa việc xây dựng giao diện người dùng đồ họa (Graphics User Interface - GUI). Nhiều môi trường phát triển tích hợp hiện đại còn tích hợp thêm trình duyệt lớp (class browser), trình duyệt đối tượng (object browser), lượt dồ phân cấp lớp (class hierarchy diagram) nhằm sử dụng cho việc phất triển phần mềm hướng đối tượng (object-oriented software).

2. Eclipse:



Giao diện Eclipse Juno (4.2) Nguồn: Wikipedia.

Là một IDE hỗ trợ đa ngôn ngữ. Nguyên bản của Eclipse được phát triển dành cho ngôn ngữ Java. Ngày nay, Eclipse còn hỗ trợ nhiều ngôn ngữ lập trình khác, như:


• C/C++ (Trình cắm CDT).
• PHP (Trình cắm PDT).
• Pascal (Trình cắm Pascaline).
• HTML.
• XML.
• JavaScript.
• ...

Bản ổn định hiện tại của Eclipse là Indigo.
Lưu ý: Cần cài đặt JRE và các trình biên dịch cho từng ngôn ngữ trước khi bước vào sử dụng.
Địa chỉ tải về:


• Bản Juno (Mới nhất): http://www.eclipse.org/downloads/.
• Bản Indigo: http://www.eclipse.org/downloads/packages/release/indigo/sr2.
• Bản Eclipse Gavab (Tích hợp các ngôn ngữ lập trình: Java, C/C++, Pascal, Ruby, Haskell, PascalFC): http://www.sidelab.es/projects/eclipsegavab/downloads.
3. Free Pascal:



Giao diện IDE Free Pascal. Nguồn: http://free-pascal.en.uptodown.com/screen/4.

Free Pascal (FPK Pascal) là tên của một trình biên dịch dành cho ngôn ngữ Pascal.
Một bộ cài đặt của Free Pascal gồm hai thành phần chính:


• Trình biên dịch.
• Môi trường phát triển tích hợp (Chạy trong chế độ dòng lệnh).

Một số thành phần khác như: các đoạn mã mẫu, các thư viện mở rộng, các văn bản hướng dẫn sử dụng, ...
Địa chỉ tải về: http://www.freepascal.org/.
4. Dev C++:



Giao diện Dev C++. Nguồn: Wikipedia.
Là IDE hỗ trợ ngôn ngữ C/C++, sử dụng trình biên dịch MinGW.
Địa chỉ tải về: http://www.bloodshed.net/devcpp.html.
5. Nhận xét:
Hiện tại, Free Pascal, Dev C++ được sử dụng chính thức trong các kỳ thi lập trình ở cấp THPT. Tuy nhiên,trong học tập, nên tiếp cận với Eclipse, do phần mềm này có những tính năng vượt trội như: giao diện đẹp, dễ dàng quản lý khi gỡ lỗi (debug), định dạng mã nguồn, hỗ trợ viết mã nhanh (Intelli-sense), ...

Các nguồn có thể tham khảo:

• Eclipse documentation: http://www.eclipse.org/documentation/.
• Free Pascal Documentation:  http://www.freepascal.org/docs.var.
• Dev C++ Documentation: http://www.bloodshed.net/dev/doc/.
• Phát triển các ứng dụng bằng cách sử dụng Bộ công cụ phát triển C/C++ của Eclipse: https://www.ibm.com/developerworks/vn/library/os-eclipse-stlcdt/.
• Cài đặt Eclipse CDT và trình biên dịch MinGW: http://www.youtube.com/watch?v=rgt3PJ5DvH4.

Tài liệu sử dụng: Wikipedia - Môi trường phát triển tích hợp: http://en.wikipedia.org/wiki/Integrated_development_environment.

Bắt đầu giải quyết bài toán tin học

Một bài toán tin học (Problem - vấn đề) yêu cầu chúng ta tìm ra giải pháp để đạt được một mục đích xác định từ những điều kiện ban đầu (Dữ liệu đầu vào).
Trước khi bước vào giải quyết một bài toán bằng tin học, điều đầu tiên cần có là: một Thuật giải (Thuật toán) để giải quyết một bài toán. Nhưng, chúng là gì?
Khi dịch ra tiếng Anh, cả Thuật toán và Thuật giải đều là Algorithm. Nhưng, một số nguồn tài liệu tách riêng hai định nghĩa này. Ở đây, tui sẽ trình bày hai định nghĩa trên bằng cách tổng hợp các tài liệu.
Thuật giải (thuật toán) đều được hiểu là: "Một tập hữu hạn các hướng dẫn rõ ràng để người giải toán có thể theo đó mà giải quyết vấn đề" (1). Nói chính xác hơn, thuật giải (thuật toán) được định nghĩa là: "Một dãy hữu hạn các bước không mập mờ và có thể thực thi được, quá trình hành động theo các bước này phải dừng và cho được kết quả như mong muốn" (2).
 Tính chất thuật toán:

• Tính chính xác: để đảm bảo kết quả tính toán hay các thao tác mà máy tính thực hiện được là chính xác.
• Tính rõ ràng: Thuật toán phải được thể hiện bằng các câu lệnh minh bạch; các câu lệnh được sắp xếp theo thứ tự nhất định.
• Tính khách quan: Một thuật toán dù được viết bởi nhiều người trên nhiều máy tính vẫn phải cho kết quả như nhau.
• Tính phổ dụng: Thuật toán không chỉ áp dụng cho một bài toán nhất định mà có thể áp dụng cho một lớp các bài toán có đầu vào tương tự nhau.
• Tính kết thúc: Thuật toán phải gồm một số hữu hạn các bước tính toán.

Một số tính chất khác:

• Đầu vào và đầu ra: mọi thuật giải (thuật toán) đều có dữ liệu đầu vào, xử lý nó, và cho kết quả.
• Tính hiệu quả: dựa trên khối lượng tính toán, không gian và thời gian thi hành thuật toán.

Bài toán ví dụ: tính giai thừa, tính phương trình bậc nhất, bậc hai.
Tuy nhiên, trong quá trình nguyên cứu giải quyết bài toán, người ta đã đưa ra những nhận xét (3):

• Có nhiều bài toán chưa tìm ra được cách giải kiểu thuật toán, và cũng chưa biết có tồn tại thuật toán giải quyết hay không.
• Có nhiều bài toán đã có thuật toán giải quyết, nhưng thời gian tính toán quá lớn hoặc các điều kiện cho thuật toán khó đáp ứng.
• Có những bài toán được giải theo những cách giải vi phạm thuật toán nhưng vẫn chấp nhận (Thường gặp nhất là ở tính chính xác và tính khách quan: kết quả sau khi tính có thể chưa được tối ưu, nhưng phải nằm trong khoảng chấp nhận).

Từ đây, ta có thể gọi các phương pháp như vậy là thuật giải. Một số thuật giải: thuật giải Heuristic, thuật giải Di truyền. Bài toán ví dụ: tìm đường đi ngắn nhất (A*) cho một đối tượng trong game (warcraft, starcraft).

Mô tả thuật giải (thuật toán):
Cách đơn giản nhất là đưa ra từng bước một, ở mỗi bước, hãy suy nghĩ: ta cần làm gì?
Ví dụ: xuất một mảng a (A[0], A[1], ..., A[n - 1]) cho trước có n phần tử.

1. Gán i là 0 (i := 0).
2. Nếu i vẫn còn nhỏ hơn n: chuyển tới bước 3, ngược lại chuyển tới bước 4.
3. Xuất a[i] và tăng i thêm một đơn vị (i := i + 1).
4. Kết thúc chương trình.

Cách thứ hai: dùng sơ đồ khối.
Ưu điểm: Giúp người đọc theo dõi được sự phân cấp các trường hợp và quá trình xử lý của thuật toán. Thường được dùng trong những thuật toán có tính rắc rối, khó theo dõi được quá trình xử lý (4).
Nhược điểm: Cồng kềnh, dùng một không gian rất lớn để mô tả một bài toán. Ngoài ra chỉ phân biệt được hai thao tác: rẽ nhánh và xử lý. Trong thực tế, các thuật giải (thuật toán) còn có thêm thao tác lặp.
Sử dụng:

• Thao tác rẽ nhánh (chọn lựa): Mô tả bằng hình thoi, bên trong hình ghi nội dung điều kiện.
• Thao tác xử lý: Mô tả bằng hình chữ nhật, bên trong hình ghi nội dung cần xử lý.

Cách thứ ba: dùng mã giả (mượn cú pháp của một ngôn ngữ lập trình để mô tả các bước tính toán).
Ưu điểm: Diễn đạt được nội dung bài toán một cách trọn vẹn mà không tốn nhiều không gian.
Ví dụ: Cũng bài toán trên, nhưng được viết bằng mã giả theo kiểu ngôn ngữ Pascal:

For i := 0 to n -1 do
xuất a[i]

Tài liệu tham khảo:
(1), (2), (4): Hoàng Kiếm. GIẢI MỘT BÀI TOÁN TRÊN MÁY TÍNH NHƯ THẾ NÀO?. NXB Giáo dục.
(3): Hoàng Kiếm. THUẬT TOÁN THUẬT GIẢI.
Wikipedia: Algorithm - http://en.wikipedia.org/wiki/Algorithm.