Cấu Trúc Dữ Liệu & Giải Thuật

Ác Mộng của sinh viên hiện tại, là học môn Cấu Trúc Dữ Liệu & Giải Thuật hiện tại ở trường. Đây là một môn học đối với Tâm Gà là quá sức chua cay và khó nhai nhất. Bản thân mình cố gắng tiếp thu được 100% bài học này, mà không thể nào hiểu rõ quy chế và cách thức làm việc của bộ môn này, sau khi ra trường nữa. Tuy nhiên, đối với mình, một khi đã có đủ 90% kiến thức cơ bản của Cấu Trúc Dữ Liệu Giải Thuật này rồi. Thì mọi vấn đề về bài tập về nhà, hay bài tập trên trường, hay cũng như thi kết thúc môn đều có thể giải quyết đơn giản nhất. Nhưng đó là đối với Tâm Gà, còn đối với bạn thì sao thì phải còn chờ đợi hồi sau phân giải.

I. Cấu trúc dữ liệu (Data Structure) là gì ?

Cấu trúc dữ liệu là cách lưu trữ, tổ chức dữ liệu có thứ tự, có hệ thống để dữ liệu có thể được sử dụng một cách hiệu quả. Dưới đây là hai khái niệm nền tảng hình thành nên một cấu trúc dữ liệu:

- Interface: Mỗi cấu trúc dữ liệu có một Interface. Interface biểu diễn một tập hợp các phép tính mà một cấu trúc dữ liệu hỗ trợ. Một Interface chỉ cung cấp danh sách các phép tính được hỗ trợ, các loại tham số mà chúng có thể chấp nhận và kiểu trả về của các phép tính này.

- Implementation (có thể hiểu là sự triển khai): Cung cấp sự biểu diễn nội bộ của một cấu trúc dữ liệu. Implementation cũng cung cấp phần định nghĩa của giải thuật được sử dụng trong các phép tính của cấu trúc dữ liệu.

II. Đặc điểm của một Cấu trúc dữ liệu

Chính xác sự triển khai của Cấu trúc dữ liệu nên triển khai Interface của nó một cách chính xác. Độ phức tạp về thời gian (Time Complexity): Thời gian chạy hoặc thời gian thực thi của các phép tính của cấu trúc dữ liệu phải là nhỏ nhất có thể. Độ phức tạp về bộ nhớ (Space Complexity): Sự sử dụng bộ nhớ của mỗi phép tính của cấu trúc dữ liệu nên là nhỏ nhất có thể.

III. Tại sao Cấu trúc dữ liệu là cần thiết ?

Ngày nay, các ứng dụng ngày càng phức tạp và lượng dữ liệu ngày càng lớn với nhiều kiểu đa dạng. Việc này làm xuất hiện 3 vấn đề lớn mà mỗi lập trình viên phải đối mặt:

- Tìm kiếm dữ liệu: Giả sử có 1 triệu hàng hóa được lưu giữ vào trong kho hàng hóa. Và giả sử có một ứng dụng cần để tìm kiếm một hàng hóa. Thì mỗi khi thực hiện tìm kiếm, ứng dụng này sẽ phải tìm kiếm 1 hàng hóa trong 1 triệu hàng hóa. Khi dữ liệu tăng lên thì việc tìm kiếm sẽ càng trở lên chậm và tốn kém hơn.

- Tốc độ bộ vi xử lý: Mặc dù bộ vi xử lý có tốc độ rất cao, tuy nhiên nó cũng có giới hạn và khi lượng dữ liệu lên tới hàng tỉ bản ghi thì tốc độ xử lý cũng sẽ không còn được nhanh nữa.

- Đa yêu cầu: Khi hàng nghìn người dùng cùng thực hiện một phép tính tìm kiếm trên một Web Server thì cho dù Web Server đó có nhanh đến mấy thì việc phải xử lý hàng nghìn phép tính cùng một lúc là thực sự rất khó. Để xử lý các vấn đề trên, các cấu trúc dữ liệu là một giải pháp tuyệt vời. Dữ liệu có thể được tổ chức trong cấu trúc dữ liệu theo một cách để khi thực hiện tìm kiếm một phần tử nào đó thì dữ liệu yêu cầu sẽ được tìm thấy ngay lập tức.

IV. Độ phức tạp thời gian thực thi trong cấu trúc dữ liệu và giải thuật

Có 3 trường hợp thường được sử dụng để so sánh thời gian thực thi của các cấu trúc dữ liệu khác nhau:

- Trường hợp xấu nhất (Worst Case): là tình huống mà một phép tính của cấu trúc dữ liệu nào đó tốn thời gian tối đa (thời gian dài nhất). Ví dụ với ba số 1, 2, 3 thì nếu sắp xếp theo thứ tự giảm dần thì thời gian thực thi sẽ là dài nhất (và đây là trường hợp xấu nhất); còn nếu sắp xếp theo thứ tự tăng dần thì thời gian thực thi sẽ là ngắn nhất (và đây là trường hợp tốt nhất).

- Trường hợp trung bình (Average Case): miêu tả thời gian thực thi trung bình một phép tính của một cấu trúc dữ liệu.

- Trường hợp tốt nhất (Best Case): là tình huống mà thời gian thực thi một phép tính của một cấu trúc dữ liệu là ít nhất. Ví dụ như trên.

V. Thuật ngữ cơ bản trong Cấu trúc dữ liệu

- Dữ liệu: Dữ liệu là các giá trị hoặc là tập hợp các giá trị.

- Phần tử dữ liệu: Phần tử dữ liệu là một đơn vị đơn lẻ của giá trị.

- Các phần tử nhóm: Phần tử dữ liệu mà được chia thành các phần tử con thì được gọi là các phần tử nhóm.

- Các phần tử cơ bản: Phần tử dữ liệu mà không thể bị chia nhỏ thành các phần tử con thì gọi là các phần tử cơ bản.

- Thuộc tính và Thực thể: Một thực thể là cái mà chứa một vài thuộc tính nào đó, và các thuộc tính này có thể được gán các giá trị.

- Tập hợp thực thể: Các thực thể mà có các thuộc tính tương tự nhau thì cấu thành một tập hợp thực thể.

- Trường: Trường là một đơn vị thông tin cơ bản biểu diễn một thuộc tính của một thực thể.

- Bản ghi: Bản ghi là một tập hợp các giá trị trường của một thực thể đã cho.

- File: Là một tập hợp các bản ghi của các thực thể trong một tập hợp thực thể đã cho.

VI. Cài đặt môi trường trong Cấu Trúc Dữ Liệu

Vì ngôn ngữ C và C++ là ngôn ngữ mà hầu như mọi trường đại học sử dụng để giảng dạy, cho nên trong chương này mình sẽ hướng dẫn các bạn cài đặt C và C++ để làm môi trường chạy các ví dụ trong loạt bài Cấu trúc dữ liệu và giải thuật.

01. Cài đặt IDE để biên dịch và thực thi C

Có một số IDE có sẵn và miễn phí để biên dịch và thực thi các chương trình C. Bạn có thể chọn Dev-C++, Code:: Blocks, hoặc Turbo C. Tuy nhiên, lựa chọn phổ biến nhất và hay được sử dụng nhất là Dev-C++ và các chương trình C trong loạt bài này cũng được biên dịch và thực thi trong Dev-C++. Bạn truy cập theo link sau để tải Dev-C++: Tải Dev-C++. Trên trang này cũng bao gồm cả Code:: Blocks. Sau khi bạn tải xong, để cài đặt IDE này, bạn chỉ cần vào Google và gõ "cài đặt dev-c++" là có rất nhiều video hướng dẫn chi tiết, cho nên mình không cần trình bày thêm nữa. Sau khi đã cài đặt xong, để biên dịch và thực thi một chương trình C, bạn: (a) vào File -> New -> Project -> Console Application -> C project, sau đó nhập tên vào hoặc (b) File -> New -> Source File. Cuối cùng, sao chép và dán chương trình C vào file bạn vừa tạo. Để biên dịch và thực thi, chọn Execute -> Compile & Run.

02. Cài đặt để chạy trên Command Prompt

Nếu bạn muốn cài đặt để biên dịch và chạy trên Command Prompt, thì bạn nên đọc phần sau đây. Nếu bạn đang muốn cài đặt chương trình C, bạn cần phải sử dụng 2 phần mềm trên máy tính của bạn: (a) Chương trình soạn văn bản - Text Editor và (b) Bộ biên dịch C.

03. Text Editor

Được sử dụng để soạn thảo các chương trình. Ví dụ về một vài trình editor như Window Notepad, Notepad ++, vim hay vi… Tên và các phiên bản của các trình editor có thể thay đổi theo các hệ điều hành. Ví dụ, Notepad được sử dụng trên Windows, hoặc vim hay vi được sử dụng trên Linux hoặc UNIX. Các file bạn tạo trong trình editor được gọi là source file (file nguồn) và chứa các chương trình code. Các file trong chương trình C thường được đặt tên với phần mở rộng ".c". Trước khi bắt đầu chương trình của bạn, hãy chắc chắn bạn có một trình editor trên máy tính và bạn có đủ kinh nghiệm để viết các chương trình máy tính, lưu trữ trong file và thực thi nó.

04. Bộ biên dịch C

Mã nguồn được viết trong file nguồn dưới dạng có thể đọc được. Nó sẽ được biên dịch thành mã máy, để cho CPU có thể thực hiện các chương trình này dựa trên các lệnh được viết. Bộ biên dịch được sử dụng để biên dịch mã nguồn (source code) của bạn đến chương trình có thể thực thi. Tôi giả sử bạn có kiến thức cơ bản về một bộ biên dịch ngôn ngữ lập trình. Bộ biên dịch thông dụng nhất là bộ biên dịch GNU C/C++, mặt khác bạn có thể có các bộ biên dịch khác như HP hoặc Solaris với Hệ điều hành tương ứng. Dưới đây là phần hướng dẫn giúp bạn cách cài đặt bộ biên dich GNU C/C++ trên các hệ điều hành khác nhau. Tôi đang đề cập đến C/C++ bởi vì bộ biên dịch GNU gcc hoạt động cho cả ngôn ngữ C và C++.

VII. Giải thuật là gì ?

Giải thuật (hay còn gọi là thuật toán - tiếng Anh là Algorithms) là một tập hợp hữu hạn các chỉ thị để được thực thi theo một thứ tự nào đó để thu được kết quả mong muốn. Nói chung thì giải thuật là độc lập với các ngôn ngữ lập trình, tức là một giải thuật có thể được triển khai trong nhiều ngôn ngữ lập trình khác nhau. Xuất phát từ quan điểm của cấu trúc dữ liệu, dưới đây là một số giải thuật quan trọng:

- Giải thuật Tìm kiếm: Giải thuật để tìm kiếm một phần tử trong một cấu trúc dữ liệu.
- Giải thuật Sắp xếp: Giải thuật để sắp xếp các phần tử theo thứ tự nào đó.
- Giải thuật Chèn: Giải thuật để chèn phần từ vào trong một cấu trúc dữ liệu.
- Giải thuật Cập nhật: Giải thuật để cập nhật (hay update) một phần tử đã tồn tại trong một cấu trúc dữ liệu.
- Giải thuật Xóa: Giải thuật để xóa một phần tử đang tồn tại từ một cấu trúc dữ liệu.

VIII. Đặc điểm của giải thuật

Không phải tất cả các thủ tục có thể được gọi là một giải thuật. Một giải thuật nên có các đặc điểm sau: Tính xác định: Giải thuật nên rõ ràng và không mơ hồ. Mỗi một giai đoạn (hay mỗi bước) nên rõ ràng và chỉ mang một mục đích nhất định. Dữ liệu đầu vào xác định: Một giải thuật nên có 0 hoặc nhiều hơn dữ liệu đầu vào đã xác định. Kết quả đầu ra: Một giải thuật nên có một hoặc nhiều dữ liệu đầu ra đã xác định, và nên kết nối với kiểu kết quả bạn mong muốn. Tính dừng: Các giải thuật phải kết thúc sau một số hữu hạn các bước. Tính hiệu quả: Một giải thuật nên là có thể thi hành được với các nguồn có sẵn, tức là có khả năng giải quyết hiệu quả vấn đề trong điều kiện thời gian và tài nguyên cho phép. Tính phổ biến: Một giải thuật có tính phổ biến nếu giải thuật này có thể giải quyết được một lớp các vấn đề tương tự. Độc lập: Một giải thuật nên có các chỉ thị độc lập với bất kỳ phần code lập trình nào.

VIII. Cách viết một giải thuật ?

Bạn đừng tìm, bởi vì sẽ không có bất kỳ tiêu chuẩn nào cho trước để viết các giải thuật. Như bạn đã biết, các ngôn ngữ lập trình đều có các vòng lặp (do, for, while) và các lệnh điều khiển luồng (if-else), … Bạn có thể sử dụng những lệnh này để viết một giải thuật. Chúng ta viết các giải thuật theo cách thức là theo từng bước một. Viết giải thuật là một tiến trình và được thực thi sau khi bạn đã định vị rõ ràng vấn đề cần giải quyết. Từ việc định vị vấn đề, chúng ta sẽ thiết kế ra giải pháp để giải quyết vấn đề đó và sau đó là viết giải thuật.

VIV. Phân tích giải thuật

Hiệu quả của một giải thuật có thể được phân tích dựa trên 2 góc độ: trước khi triển khai và sau khi triển khai: Phân tích lý thuyết: Có thể coi đây là phân tích chỉ dựa trên lý thuyết. Hiệu quả của giải thuật được đánh giá bằng việc giả sử rằng tất cả các yếu tố khác (ví dụ: tốc độ vi xử lý, …) là hằng số và không ảnh hưởng tới sự triển khai giải thuật. Phân tích tiệm cận: Việc phân tích giải thuật này được tiến hành sau khi đã tiến hành trên một ngôn ngữ lập trình nào đó. Sau khi chạy và kiểm tra đo lường các thông số liên quan thì hiệu quả của giải thuật dựa trên các thông số như thời gian chạy, thời gian thực thi, lượng bộ nhớ cần dùng, … Chương này chúng ta sẽ tìm hiểu phân tích lý thuyết. Còn phân tích tiệm cận chúng ta sẽ cùng tìm hiểu ở chương tiếp theo.

XV. Độ phức tạp giải thuật (Algorithm Complexity)

Về bản chất, độ phức tạp giải thuật là một hàm ước lượng (có thể không chính xác) số phép tính mà giải thuật cần thực hiện (từ đó dễ dàng suy ra thời gian thực hiện của giải thuật) đối với bộ dữ liệu đầu vào (Input) có kích thước n. Trong đó, n có thể là số phần tử của mảng trong trường hợp bài toán sắp xếp hoặc tìm kiếm, hoặc có thể là độ lớn của số trong bài toán kiểm tra số nguyên tố, … Giả sử X là một giải thuật và n là kích cỡ của dữ liệu đầu vào. Thời gian và lượng bộ nhớ được sử dụng bởi giải thuật X là hai nhân tố chính quyết định hiệu quả của giải thuật X: Nhân tố thời gian: Thời gian được đánh giá bằng việc tính số phép tính chính (chẳng hạn như các phép so sánh trong thuật toán sắp xếp). Nhân tố bộ nhớ: Lượng bộ nhớ được đánh giá bằng việc tính lượng bộ nhớ tối đa mà giải thuật cần sử dụng. Độ phức tạp của một giải thuật (một hàm f(n)) cung cấp mối quan hệ giữa thời gian chạy và/hoặc lượng bộ nhớ cần được sử dụng bởi giải thuật.