Mặc dù có nhiều lệnh gọi đệ quy trong các chương trình ở phần trước, có một bài tập hướng dẫn để loại đi sự đệ quy một cách có hệ thống. Mỗi lệnh gọi thủ tục có thể được thay bằng một thủ tục cất vào ngăn xếp và thay mỗi thủ tục trả về bởi một lệnh lấy khỏi ngăn xếp, bắt chước những gì hệ Pascal thực hiện để cài đặt đệ quy. Cũng vậy, nhớ lại rằng một lý do để làm điều này là nhiều lệnh gọi có vẻ như đệ quy nhưng lại không thực sự đệ quy. Khi một lệnh gọi thủ tục là hành động cuối cùng của một thủ tục, thì một lệnh goto đơn giản có thể được sử dụng. Nó chuyển expression và term vào những vòng lặp đơn giản có thể được trộn lại với nhau và được tổ hợp với factor để sinh ra một thủ tục duy nhất với một lệnh đẹ quy thực sự (lệnh gọi tới expression trong factor).

Nhiều thuật toán cơ sở đã được phát triển để nhận ra các chương trình máy tính hợp lệ và để phân rã chúng thành một dạng tích hợp cho những công việc xử lý khác nữa. Thao tác này, được gọi là phân tích câu, có ứng dụng vượt khỏi phạm vi khoa học máy tính, vì nó có liên hệ trực tiếp với việc nghiên cứu cấu trúc ngôn ngữ nói chung. Ví dụ, phân tích câu đóng một vai trò quan trọng trong các hệ thống mà nó cố gắng để “hiểu được” các ngôn ngữ tự nhiên và trong hệ thống để dịch từ một ngôn ngữ thành một ngôn ngữ khác. Một trường hợp đáng chú ý đặc biệt là dịch từ một ngôn ngữ máy tính “cấp cao” như Pascal thành một ngôn ngữ “cấp thấp” như hợp ngữ (assembly) hay ngôn ngữ máy. Công việc dịch như vậy được gọi là một trình biên dịch (compiler). Thực ra, ta đã gặp một phương pháp phân tích câu khi xây dựng cấu trúc cây để biểu diễn một biểu thức số học.

Như chúng ta đã biết, các phép sắp xếp cơ bản là: phép sắp chọn, sắp xếp chèn và sắp xếp nổi bọt. Thông thường, các bài toán sắp xếp thường được ứng dụng cho vào các mảng (a) dữ liệu và chúng ta sẽ thực hiện sắp các phần tử trong mảng đó. Dễ dàng thấy được:

Thuật toán Johnson tìm đường đi ngắn nhất giữa tất cả các cặp đỉnh với độ phức tạp là O(V2LgV+VE). Với đồ thị thưa, nó tốt hơn là việc lặp đi lặp lại việc điều chỉnh các ma trận hay thuật toán FLOYD-WARSHALL. Thuật toán cho kết quả trả về ma trận trọng số đường đi ngắn nhất giữa tất cả các cặp đỉnh hay báo cáo về đồ thị nhập vào có chứa chu trình âm (chu trình âm là 1 chu trình trong đồ thị có tổng trọng số các đỉnh thuộc chu trình là 1 số âm, nếu trong đồ thị có chu trình âm, ta cứ đi trên chu trình ấy vô số lần thì ta sẽ có DDNN vô cùng bé ). Thuật toán Johnson sử dụng cả 2 chương trình con là thuật toán Dijkstra và thuật toán Bellman –Ford (tôi không trình bày 2 thuật toán này nữa).

Bài toán Tab game (Cờ bảng)

Cờ bảng gồm một bảng NxM ô vuông đơn vị và một quân cờ kí hiệu là @. Các dòng của bảng được mã số 1..N từ dưới lên, các cột được mã số 1..M từ trái qua phải. Lúc đầu quân cờ @ được đặt tại một ô (x,y) gọi là ô xuất phát. Hai đấu thủ là A và B lần lượt di chuyển quân cờ, A luôn đi trước trong mọi ván cờ. Luật chơi như sau:

Trong tin học chúng ta thường hay gặp yêu cầu xử lý một tập hợp biến động các đối tượng theo một thứ ưu tiên nhất định. Mỗi đối tượng được đặc trưng bởi một khóa thể hiện mức độ ưu tiên của nó, và tập hợp đó không nhất thiết phải được sắp xếp hoàn chỉnh. Thông thường tập hợp các đối tượng phải được thao tác để chọn ra đối tượng có độ ưu tiên lớn nhất để xử lý và cứ tiếp tục như vậy. Một cấu trúc dữ liệu thích hợp đáp ứng yêu cầu trên gồm các thao tác chèn một phần tử mới và lấy ra phần tử có độ ưu tiên lớn nhất được gọi là hàng đợi có độ ưu tiên.

Bài toán tìm kiếm thông tin có vai trò rất quan trọng trong thời kì có sự phát triển của mạng và Internet rất mạnh mẽ ngày nay. Một vấn đề cốt lõi để hệ thống tìm kiếm thông tin hoạt động nhanh và chính xác đó là hệ thống phải được áp dụng những thuật toán hiệu quả để tìm kiếm dữ liệu. Trong bài viết này, chúng tôi giới thiệu một thuật toán đơn giản sử dụng otomat cho bài toán tìm kiếm văn bản, hay còn gọi là so khớp chuỗi.

Xuân này xin giới thiệu với bạn đọc một thuật giải được ứng dụng trong các kỹ thuật giấu dữ liệu (tin mật) trong các môi trường đa phương tiện như ảnh, video, audio…Thuật giải luôn luôn cho phương án tối ưu và điều kỳ lạ thể hiện ở tính đơn giản trong thao tác cũng như trong lập luận về tính đúng của thuật giải.

a. Bài toán: Tìm kiếm trên cây nhị phân là một thuật toán đơn giản, một phương pháp tìm kiếm động hiệu quả. Phương pháp này là một trong các thuật toán nền móng của khoa học máy tính. Sở dĩ thuật tóan này được bàn ở đây và được coi là cơ bản bởi lẽ nó đơn giản; nhưng lại là phương pháp tìm kiếm được chọn lựa trong nhiều trường hợp ứng dụng.

Bài viết này xin giới thiệu với các bạn mới làm quen với tin học và thuật giải một thuật toán đơn giản nhưng lại có hiệu quả rất lớn trong việc tìm đường đi ngắn nhất trong đồ thị. Đó là thuật toán Dijkstra. Đây là thuật toán đã đăng tải trên tạp chí tin học & nhà trường từ những số đầu tiên nhưng bài viết này sẽ đăng tải đầy đủ về bài toán, phương thức đưa ra thuật giải cũng như đoạn chương trình đầy đủ. Rất thích hợp với những bạn mới làm quen với những thuật toán kinh điển.

Tìm kiếm là một yêu cầu rất thường xuyên trong đời sống hàng ngày. Trong tin học nó đặt nền móng cho nhiều tác vụ tính toán quan trọng. Bài toán tìm kiếm là sự xác định vị trí của một hay nhiều phần tử, gọi là đối trị tìm kiếm (Argument), trong một bảng liệt kê có thứ tự các phần tử. Mỗi phần tử đơược đại diện bằng một khoá (Key) phục vụ cho tìm kiếm. Những ứng dụng của tìm kiếm thì rất đa dạng, cũng nhươ có rất nhiều các thuật toán với đặc trương và hiệu suất khác nhau. Một trong những phơương pháp khá hiệu quả là phơương pháp tìm kiếm Tam Phân.

Vét cạn theo nghĩa thông thường là xét hết mọi đối tượng hay mọi trường hợp. Trong lập trình, vét cạn là phương pháp được dùng khi không còn phương pháp nào hiệu quả hơn có thể sử dụng được.

Bài toán: Tính giá trị của đa thức bậc N-1 tại các căn bậc N của đơn vị.

Chúng ta có thể có từng phần thuật toán nhân hai đa thức chỉ sử dụng khoảng NlgN phép toán. Có thể thấy sơ đồ tổng quát là:

- Tính giá trị của đa thức nhập vào tại các căn bậc (2N-1) của đơn vị.

- Nhân hai giá trị tìm được tại mỗi điểm.

- Nội suy để tìm kết quả bằng cách tính giá trị cảu đa thức xác định chỉ bởi các số được tính tại các căn bậc (2N-1) của đơn vị.

Thuật toán Rabin-Karp là một trong những phương pháp tìm kiếm chuỗi. Ý tưởng là chúng ta sẽ khai thác một vùng nhớ lớn bằng cách xem mỗi đoạn M-ký tự có thể có của văn bản như là một khoá (key) trong một bảng băm chuẩn. Nhưng không cần thiết phải giữ một bảng băm tổng thể, vì bài toán được cài đặt sao cho chỉ một khoá là đang được tìm kiếm; việc mà ta cần làm là đi tính hàm băm cho M ký tự từ văn bản vì nó chỉ đơn giản là kiểm tra xem chúng có bằng với mẫu hay không. Với hàm băm: h(k) = k mod q, ở đây q (kích thước bảng) là một số nguyên tố lớn. Trong trường hợp này, không có gì được chứa trong bảng băm, vì vậy q có thể được cho giá trị rất lớn.

Lý thuyết về xử lý song song (parallel processing) bắt đầu cuối những năm 1940 khi J.Von Neumann giới thiệu một số mô hình hạn chế của tính toán song song có tên otomat tế bào mà chủ yếu là một mảng hai chiều các bộ xử lý trạng thái hữu hạn được tương kết theo dạng hình lưới. Từ đó đến nay, lý thuyết về xử lý song song trở thành lĩnh vực nghiên cứu quan trọng và ngày càng đem lại những dấu hiệu khả quan trong việc xây dựng một mô hình lập trình mới có những tính năng vượt trội so với mô hình lập trình tuần tự truyền thống. Vậy tại sao chúng ta phải nghiên cứu xử lý song song, xử lý song song khác xử lý tuần tự ở những điểm nào, muốn đánh giá thuật toán song song ta phải dựa trên những tiêu chí nào?...

Trong số này, tôi xin giới thiệu tới bạn yêu lập trình một bài toán thú vị liên quan một trò chơi quen thuộc: trò chơi gấp giấy. Quá trình tìm lời giải có sự kết hợp giữa phân tích và quan sát. Sau khi xem lời giải, bạn đọc có thể tiếp tục mở rộng và giải bài toán ở mức khó hơn.

Như đã biết, cây hai chiều là một cấu trúc dữ liệu động, rất giống cây nhị phân ngoại trừ điều là nó chia không gian hình học theo một cách thuận tiện cho việc tìm kiếm vùng. Phương pháp cây hai chiều mang ý tưởng là xây dựng cây tìm kiếm nhị phân với các điểm được chứa trong các nút, dùng các toạ độ x và y của các điểm như là các khoá theo một trình tự thay đổi nghiêm ngặt

Đơn hình là phương pháp chỉ các phương pháp tổng quát bài toán quy hoạch tuyến tính bằng phương pháp xoay trụ (pivoting), giống như phép khử Gauss. Nó tương ứng với thao tác hình học chuyển từ đỉnh này tới đỉnh khác của đơn hình để tìm lời giải. Các thuật toán chỉ khác nhau ở thứ tự các đỉnh được xét đến.

Range Minimum Query [RMQ] là 1 dạng cấu trúc đặc biệt hiệu quả trong bài toán tìm min, max của nhiều đoạn liên tiếp khác nhau của 1 dãy số cho trước.

Bài toán: Cho dãy số A gồm N số cho trước. Có 1 số câu hỏi dạng yêu cầu trả về giá trị min/max các phần tử thuộc dãy trong đoạn từ I tới J.

Có thể nói Heap là 1 cấu trúc hữu dụng vào bậc nhất trong giải toán.

Heap là 1 cấu trúc khá quen thuộc, là 1 dạng Priority Queue (hàng đợi có độ ưu tiên), ứng dụng to lớn trong nhiều dạng toán khác nhau. Vì vậy xin chỉ nói sơ qua về Heap:

Heap thực chất là 1 cây cân bằng thoả mãn các điều kiện sau:

- 1 nút chỉ có không quá 2 nút con.

- Nút cha là nút lớn nhất, mọi nút con luôn có giá trị nhỏ hơn nút cha.