Trong những bài toán về dãy số, 1 cấu trúc dữ liệu thường được sử dụng thay thế cho interval tree là Binary Indexed Tree. Mặc dù vậy, cấu trúc của 1 cây Binary Indexed Tree lại khác hoàn toàn với Interval Tree. Tuy gọi là “tree” nhưng có vẻ Binary Indexed Tree lại giống 1 rừng - gồm nhiều cây hơn là giống 1 cây.

Chỉ cần qua câu nói "Algorithms+Data Structures = Program" của Niklaus Wirth ta đã có thể thấy được tầm quan trọng của các loại cấu trúc dữ liệu [data structures] trong giải các bài toán tin. Ứng dụng 1 cách thuần thục hiệu quả các loại cấu trúc sẽ đem đến những thuận lợi vô cùng lớn cho các lập trình viên. Ngoài những cấu trúc dữ liệu chuẩn, quen thuộc như array, record, queue,... còn có 1 số cấu trúc dữ liệu khác có hiệu quả đặc biệt trong 1 số dạng bài tập. Mặc dù vậy, tài liệu tiếng việt về những cấu trúc này lại khá ít, đặc biệt là Interval Tree, Binary Indexed Tree và Range minimum Query. Trong chuyên đề này sẽ đề cập tới 1 số loại cấu trúc thường xuyên được sử dụng: Interval tree, Binary Indexed Tree, Heap, Range Minimum Query và Disjoint set. Để giúp bạn hiểu rõ các cấu trúc đó, sẽ có thêm 1 số ví dụ điển hình cho những ứng dụng khác nhau của chúng.

Thuật ngữ đường cong (curvefitting) hay điều chỉnh dữ liệu được dùng để mô tả bài toán tổng quát của việc tìm các hàm khớp với một tập các giá trị đang được quan sát ứng với một tập điểm.

Trong đồ họa máy tính có khá nhiều thuật toàn tô màu (Scanline, tô loang...) cho 1 vùng kín (đặc) như các đa giác, các đường tròn... Xong mỗi thuật toán lại tỏ ra có những ưu việt và hạn chế riêng đối với từng bài toán cụ thể. Với thuật toán tô màu theo dòng quét (Scanline), khi tô màu cho một vùng kín đôi khi cần phải xác định cho được các trường hợp đặc biệt của bài toán để sao cho kết quả trả về sẽ tô được những vùng cần thiết như mong muốn.

1. Định nghĩa

Ta nói một đối tượng là đệ quy nếu nó được định nghĩa qua chính nó hoặc một đối tượng khác cùng dạng với chính nó bằng quy nạp.

Nếu lời giải của một bài toán T được thực hiện bằng lời giải của bài toán T’ có dạng giống T thì đó là một lời giải đệ quy. Giải thuật tương ứng với lời giải như vậy được gọi là giải thuật đệ quy. Chú ý, T’ có dạng giống T nhưng theo một nghĩa nào đó thì T’ phải “nhỏ” hơn T, dễ giải hơn T và việc giải T’ không phụ thuộc vào T.

Tất cả chúng ta có lẽ không ai không biết đến bài toán cổ nổi tiếng sau:

"Vừa gà vừa chó

Bó lại cho tròn

Ba mươi sáu con

Một trăm chân chẵn

Hỏi có bao nhiêu gà bao nhiêu chó?"

Như chúng ta đã biết, chèn là một trong những phương pháp sắp xếp cơ bản. Chèn là một thuật toán gần như đơn giản ngang với thuật toán sắp xếp chọn nhưng có lẽ mềm dẻo hơn. Đây là phương pháp người ta thường dùng để sắp xếp các thanh tay cầu: xét các phần tử mỗi cái ở một thời điểm, chèn từng từng cái vào trong vị trí thích hợp của nó trong số các phần tử đã xét rồi (đã được sắp xếp rồi). Phần tử đang được xét được chèn một cách đơn giản bằng cách chuyển các phần tử lớn hơn sang phải một vị trí và sau đó chèn phần tử vào vị trí đã được bỏ.

Lý thuyết đồ thị là một lĩnh vực toán học được nghiên cứu từ rất lâu, những ý tưởng cơ bản của nó được đưa ra từ thế kỷ XVIII bởi nhà toán học lỗi lạc người thuỵ sĩ Leonhard Euler. Đặc biệt trong những thập niên gần đây, cùng với sự ra đời của máy tính điện tử, sự phát triển nhanh chóng của khoa học máy tính, lý thuyết đồ thị ngày càng được quan tâm nghiên cứu nhiều hơn. Các thuật toán trên đồ thị được ứng dụng trong rất nhiều lĩnh vực khác nhau như: Mạng máy tính, Vật lý vật chất ngưng tụ, Lý thuyết mã hóa, Tối ưu hoá, Kinh tế học…

Trong lý thuyết số, thuật toán Euclid là một thuật toán để xác định ước số chung lớn nhất (GCD – Greatest Common Divisor) của 2 phần tử thuộc vùng Euclid (ví dụ: các số nguyên). Điều quan trọng chủ yếu là nó không yêu cầu việc phân tích thành thừa số 2 số nguyên, và nó cũng mang ý nghĩa lớn vì nó là một trong những thuật toán cổ nhất được biết đến, từ thời Hy Lạp cổ đại.

Tiếp theo bài viết “Học thuật toán qua các bài toán”, trong bài viết này tôi xin tiếp tục giới thiệu với các bạn độc giả yêu thích thuật toán và lập trình một số ví dụ khá thú vị về thuật toán qua các bài toán. Trước hết chúng ta hãy bắt đầu bằng bài toán “Nhân hai ma trận”.

Học tập thuật toán là một trong những yêu cầu cơ bản để trở thành các lập trình viên. Đối với các sinh viên ngành tin học và những ai yêu thích lập trình, việc học thuật toán còn là một thú vui, giúp nâng cao tư duy logic và làm phong phú thêm kiến thức về việc xây dựng các giải thuật cho các bài toán mới. Trong bài báo nhỏ này tôi xin đưa ra một số bài toán nhỏ, để qua đó trình bày một số thuật toán khá tinh tế để giải quyết chúng, mong rằng bài báo sẽ mang lại cho các bạn độc giả những điều thú vị.

Cho một tập điểm trong mặt phẳng, một câu hỏi hiển nhiên là tìm các điểm rơi trong một vùng đã cho nào đó. “Liệt kê tên tất cả các quốc gia trong khu vực Đông Nam Á” là một câu hỏi thuộc loại này với tập điểm là các quốc gia trên bản đồ khu vực Đông Nam Á. Cũng có thể thấy một ví dụ điển hình trong thực tế “ Lịêt kê những người từ 20 đến 23 tuổi với mức thu nhập nào đó”.

Trong quá trình học lập trình và thuật toán, đa số trong chúng ta đã từng nghe tới và làm các bài tập về các số bè bạn (friend numbers) và số hoàn hảo (perfect numbers). Các số bè bạn n, m là hai số nguyên mà tổng ước số của n bằng m và tổng các ước của m bằng n, ví dụ như cặp số bè bạn nhỏ nhất là 220 và 284. Các số hoàn hảo là các số mà tổng các ước thực sự của nó bằng chính nó, ví dụ như các số hoàn thiện đầu tiên là 6, 28 ...

Như chúng ta đã biết, thường thì các thuật toán hình học thì khó phân tích hơn các thuật toán trong những lĩnh vực khác. Vì khó mô tả được đặc điểm của đầu vào (và đầu ra) hơn. Bài này, là một trong những thuật toán hình học rất hay mà không hề khó hiểu. Gramham là phương phám đáng chú ý vì hầu hết các tính toán dành cho việc sắp xếp: thuật toán có chứa một sắp xếp không tốn kém lắm. Thuật toán bắt đầu bằng việc xây dựng một đa giác đơn khép kín từ các điểm đã cho. Việc xây dựng này dùng một hàm: sắp các điểm theo khoá là giá trị của hàm theta (chúng ta sẽ xét cụ thể trong bài) tương ứng với góc giữa trục hoành và đường thẳng nối mỗi điểm chốt p[1] (điểm có tung độ nhỏ nhất), và khi lần theo p[1], p[2],…, p[N], p[1] ta sẽ được một đa giác khép kín.

Thông thường, khi thiết kế thuật toán chúng ta thường chú tâm tới việc sao cho thuật toán chạy càng ít tốn thời gian càng tốt, sau đó mới nghĩ tới việc tiết kiệm chỗ. Bài viết này sẽ hướng các bạn tới một vài thuật toán theo hướng ngược lại, tức là: các phương pháp được thiết kế chủ yếu để giảm bớt lượng không gian sử dụng mà không tốn quá nhiều thời gian chạy.

Có nhiều bài toán đòi hỏi người lập trình phải xử lý file ảnh như: nhận dạng chữ viết tay, nhận dạng các đối tượng hình học, tính gần đúng diện tích/khoảng cách,… Bài viết này trình bày chi tiết hai bit màu (ảnh đen trắng) về file văn bản tương ứng chỉ gồm các bit 0 và 1 góp phần giải những bài toán phương pháp chuyển file ảnh theo định dạng Bitmap (*.bmp) chỉ gồm đó.

1. Phép Băm

Một cách tiếp cận đầy đủ tới việc tìm kiếm khác với tìm kiếm trên các cấu trúc cây là phép băm. Phép Băm là một phương pháp tham chiếu trực tiếp đến các mẩu tin bằng cách thực hiện các phép chuyển đổi số học từ các khoá vào các địa chỉ bảng. Nếu chúng ta biết rằng các khóa là các số nguyên phân biệt từ 1 đến N thì chúng ta có thể lưu mẩu tin với khoá i trong vị trí i của bảng, chuẩn bị để truy xuất tức thời nhờ vào giá trị khoá. Phép bắm là sự tổng quát hoá của phương pháp tầm thường khi chúng ta không có sự hiểu biết đặc biệt về khoá (chưa có thông tin cụ thể về các giá trị khoá).

1. Sắp xếp topo:

Sắp xếp topo (topological sorting) là một trong những bài toán có tính ứng dụng cao cả trong Tin học lẫn Toán học và đời sống thường ngày. Đây là quá trình sắp xếp một dãy các phần tử sao cho thứ tự mới vẫn đảm bảo được thứ tự cục bộ (một cách nôm na có nghĩa là thứ tự được xác định đối với một vài cặp phần tử chứ không phải là tất cả các phần tử) vốn có của chúng. Một số ví dụ sẽ minh hoạ điều này

1. Xích ngăn vách

Hoạt động của hàm băm là đổi các khoá thành các địa chỉ bảng, chúng ta cần xử lý tổng hợp hai cách áp đến cùng một địa chỉ. Phương pháp đơn giản nhất có thể nghĩ đến ngay là xây dựng một danh sách liên kết các mẩu tin mà khóa của chúng áp với địa chỉ đó. Bởi các khoá mà áp đến cùng một vị trí trên bảng được lưu trong một danh sách liên kết, chúng cũng phải được lưu theo thứ tự. Điều này đưa đến một sự tổng quát của phương pháp tìm kiếm trên danh sách.

Trong dân gian có câu

Cây lăn tăn khó ăn dễ trèo

Cây lèo tèo khó trèo dễ ăn

Vận dụng trong học tập, câu này có thể hiểu là có những bài Toán Tin khá dễ hiểu nhưng giải thì khó lắm, ngược lại, có những bài, khi đọc đề thì toát mồ hôi, dựng tóc gáy, nhưng khi sờ tay vào bàn phím thấy nhẹ nhàng như không, loáng cái đã giải xong. Chúng ta thử xem bài sau đây là lăn tăn hay lèo tèo nhé