Biểu đồ Ven thì chúng ta không lạ gì. Nhưng để có thể sáng tạo chúng thì không phải là vấn đề đơn giản. Chúng ta biết rằng biểu đồ Ven thường dùng để biểu diễn tập hợp. Đối với một tập hợp nào đó, ta có thể liệt kê các phần tử, chỉ ra tính chất đặc trưng và minh họa cho nó. Bài báo sau đây xin cung cấp cho các bạn một cách sáng tạo với biểu đồ Ven mà tác giả đã dày công suy nghĩ. Sự kết hợp giữa toán học và tin học cũng là một nét đặc trưng riêng biệt mà tác giả muốn đề cập tới.

Nguyễn Hữu Tuân - tuannhtn@yahoo.com

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 viết̉ 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 viết sẽ mang lại cho các bạn những điều thú vị.

1.Tìm kiếm trên cây nhị phân

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 toán 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.

Như chúng ta đã biết trong một cây: mỗi nút chỉ được trỏ tới bởi duy nhất một nút khác gọi là cha của nó. Một cây nhị phân thì mỗi nút có 2 liền kề trái và phải. Với việc tìm kiếm, mỗi nút của cây có một mẩu tin chứa giá trị khóa. Không mất tính tổng quát, ta giả thiết rằng : trong cây – tìm – kiếm – nhị - phân tất cả các mẩu tin với các khóa nhỏ hơn thì ở trong cây – con – trái và tất cả các mẩu tin trong cây con phải có giá trị khóa lớn hơn hay bằng nhau. Chúng ta thấy rằng sẽ hoàn toàn đơn giản để đảm bảo cho cây tìm kiếm nhị phân thỏa mãn định nghĩa của nó khi chèn thêm vào một cây nút mới.

Thủ tục tìm kiếm giống như thủ tục tìmkiếmnhiphân ta đã xét ở phần trước. Tất nhiên, chúng ta sẽ luôn bám sát với định nghĩa của cây nhị phân.

I. Khái niệm mã hóa dữ liệu và giải mã
Mã hóa dữ liệu là tiến trình che dấu dữ liệu thật (plaintext), nghĩa là chuyển dữ liệu thật thành dữ liệu không có ý nghĩa hoặc có ý nghĩa khác xa với dữ liệu thật. Tiến trình đó gọi là mã hóa (encrytion). Kết quả của tiến trình gọi là bản mã (ciphertext). Từ “encrytion” được tạo ra từ “cryptography” (mật mã) xuất phát từ tiếng Hi Lạp cổ xưa “Kryptos” (Che dấu) và từ “graphia” (viết). Tiến trình mã hóa dữ liệu có thế được thực hiện bằng cách hoán vị dữ liệu thật hoặc thay thế chúng bằng dữ liệu khác. Tiến trình ngược với tiến trình mã hóa tức là chuyển từ bản mã thành dữ liệu ban đầu gọi là giải mã. Mã hóa và giải mã là hai thành phần của mật mã học.

I. Bài toán:

Tìm kiếm luôn là thao tác nền móng cho rất nhiều tác vụ tính toán. Tìm kiếm nghĩa là tìm một hay nhiều mẩu thông tin đã được lưu trữ. Thông thường, thông tin được chia thành các mẩu tin (record), mỗi mẩu tin đều có một KHÓA (key) dùng cho việc tìm kiếm. Ta sẽ luôn có một khoá cho trước giống như khoá của các mẩu tin mà ta cần tìm. Mỗi mẩu tin được tìm thấy sẽ chứa toàn bộ thông tin để cung cấp cho một quá trình xử lý nào đó.

Việc tìm kiếm được áp dụng rất đa dạng và rộng rãi. Một Ngân hàng nắm giữ tất cả thông tin của rất nhiều tài khoản khách hàng và cần tìm kiếm để kiểm tra các biến động. Một hãng Bảo hiểm hay một hệ thống trợ giúp bán vé xe, vé máy bay….Việc tìm kiếm thông tin để đáp ứng việc xắp đặt ghế và các yêu cầu tương tự như vậy là thực sự cần thiết.

Thuật ngữ thường được dùng trong việc mô tả cấu trúc dữ liệu của việc tìm kiếm là TỪ ĐIỂN và BẢNG KÝ HIỆU. Một ví dụ điển hình như ta muốn xây dựng hệ thống tra từ điển Tiếng Anh chẳng hạn. Ở đây, “khoá” là từ và “mẩu tin” là diễn giải cho từ đó, mỗi mẩu tin chứa định nghĩa, cách phát âm và các thông tin khác. BẢNG KÝ HIỆU chính là từ điển cho chương trình và các mẩu tin chứa thông tin mô tả đối tượng được đặt tên.

A. Tìm bao lồi

Khi xử lý một số lớn các điểm, thông thường ta chú ý đến biên của tập các điểm này. Đứng trước biểu đồ các điểm được vẽ trong một mặt phẳng, người xem sẽ khó phân biệt những điểm “nằm trong” với những điểm trên biên. Đây cũng là thuộc tính cơ sở để phân biệt các tập điểm, chúng ta sẽ cùng xét các thuật toán để lấy ra “biên tự nhiên” của các điểm.

Xuân này xin giới thiệu với các bạn một phương pháp tư duy rất "cổ kính" nhưng tỏ ra có hiệu lực trong khá nhiều trường hợp, đó là tư duy, hay lập luận theo phương pháp nhân – quả.

Bản chất của phương pháp này là như sau. Nếu ta đang ở trong tình huống A thì những tình huống nào có thể dẫn đến được tình huống A?

Bài toán: Trên bàn cờ vua, con tượng chỉ có thể di chuyển theo đường chéo và hai con tượng có thể khống chế (ăn) nhau nếu chúng nằm trên đường di chuyển của nhau. Cho một bàn cờ kích thước NxN. Hãy tính số các thế cờ chỉ bao gồm K con tượng mà không có con tượng nào có thể khống chế nhau. (N, K là các số tự nhiên cho trước).

Mảng là một tập có thứ tự gồm một số cố định các phần tử. Không có phép bổ sung phần tử hoặc loại bỏ phần tử được thực hiện đối với mảng. Thường chỉ có các phép tạo lập mảng, tìm kiếm một phần tử của mảng, lưu trữ một phần tử của mảng. Ngoài giá trị, một phần tử của mảng còn được đặc trưng bởi chỉ số (index) thể hiện thứ tự của phần tử đó trong mảng.

Vector là mảng một chiều, mỗi phần tử ai của nó ứng với một chỉ số i. Ma trận là mảng hai chiều, mỗi phần tử aij ứng với hai chỉ số i và j.