Giáo trình Cấu trúc dữ liệu và giải thuật - PGS. Đỗ Xuân Lôi, NXB Đại học Quốc gia Hà Nội

Giáo trình Cấu trúc dữ liệu và giải thuật của PGS. Đỗ Xuân Lôi cung cấp kiến thức nền tảng về thuật toán, mảng, cây, đồ thị cùng kỹ thuật sắp xếp và tìm kiếm.

• Tác giả: Đỗ Xuân Lôi
• Chuyên ngành: Công nghệ thông tin
• Đề tài: Cấu trúc dữ liệu và giải thuật
• Loại tài liệu: Giáo trình
• Năm xuất bản: 2006
• Địa điểm: Hà Nội

Tóm tắt

I. Tổng quan về giáo trình Cấu trúc dữ liệu và giải thuật Đỗ Xuân Lôi

Giáo trình Cấu trúc dữ liệu và giải thuật do Phó Giáo sư Đỗ Xuân Lôi biên soạn là tài liệu kinh điển trong đào tạo ngành Công nghệ Thông tin tại Việt Nam. Tác phẩm xuất bản lần đầu năm 1993 qua Nhà xuất bản Đại học Quốc gia Hà Nội. Trải qua nhiều lần tái bản và chỉnh lý, sách duy trì vị thế chuẩn mực học thuật suốt hơn ba thập kỷ. Nội dung giáo trình phản ánh khung chương trình đào tạo kỹ sư tin học chuẩn mực với thời lượng 90 tiết học. Cấu trúc nội dung phân chia thành ba phần logic bao gồm 11 chương chuyên sâu. Phần một tập trung vào tư duy thiết kế, phân tích độ phức tạp và thuật toán đệ quy. Phần hai trình bày các cấu trúc dữ liệu tuyến tính và phi tuyến kinh điển. Phần ba hoàn thiện hệ thống kiến thức thông qua bài toán sắp xếp và tìm kiếm. Tác giả kết hợp chặt chẽ giữa cơ sở lý thuyết toán học và kỹ thuật cài đặt chương trình. Cuốn sách đáp ứng đầy đủ yêu cầu nghiên cứu của sinh viên cao đẳng, đại học và sau đại học.

1.1. Lịch sử phát triển và vai trò học thuật của giáo trình

Giáo trình xuất bản lần đầu năm 1993 bởi Nhà xuất bản Đại học Quốc gia Hà Nội. Tác phẩm gắn liền với sự phát triển của công nghệ thông tin tại Việt Nam. Cuốn sách tái bản nhiều lần với các chỉnh lý sâu sắc về nội dung. Tác giả đúc kết kinh nghiệm từ thực tiễn giảng dạy đại học nhiều năm. Nhờ vậy, giáo trình trở thành tài liệu học tập chính quy của sinh viên công nghệ thông tin. Các trường đại học kỹ thuật hàng đầu sử dụng sách làm tài liệu bắt buộc. Giáo trình xây dựng nền móng tư duy lập trình vững chắc. Người học dễ dàng tiếp cận kiến thức từ mức độ nhập môn đến chuyên sâu. Đây là nguồn tài liệu chuẩn mực cho kỹ sư phần mềm.

1.2. Bố cục 3 phần chuẩn mực trong chương trình đào tạo

Bố cục cuốn sách phân chia khoa học thành ba phần chính yếu. Phần một xây dựng cơ sở phương pháp luận về mối quan hệ giữa cấu trúc dữ liệu và giải thuật. Phần này làm rõ kỹ thuật thiết kế, phân tích hiệu năng và thuật toán đệ quy. Phần hai đi sâu vào các cấu trúc dữ liệu cụ thể như mảng, danh sách, cây và đồ thị. Sinh viên được rèn luyện kỹ năng xử lý các bài toán phi số phức tạp. Phần ba tập trung vào bài toán sắp xếp và tìm kiếm dữ liệu. Đây là hai thao tác cốt lõi trong mọi hệ thống phần mềm. Cấu trúc 11 chương sách cung cấp lượng kiến thức toàn diện cho 90 tiết học lý thuyết lẫn thực hành.

II. Phân tích bài toán cấu trúc dữ liệu và giải thuật Đỗ Xuân Lôi

Giáo trình đặt trọng tâm vào việc phân tích bản chất các vấn đề tính toán phức tạp. Trong kỹ thuật phần mềm, việc lựa chọn sai cấu trúc dữ liệu dẫn đến lãng phí tài nguyên máy tính. Chương trình hoạt động kém hiệu quả khi không có thuật toán tối ưu đi kèm. PGS. Đỗ Xuân Lôi phân tích chi tiết sự phụ thuộc mật thiết giữa cấu trúc lưu trữ và tốc độ xử lý giải thuật. Giáo trình nêu bật thách thức từ lớp bài toán NP-đầy đủ trong khoa học máy tính. Điển hình là bài toán tô màu đồ thị ứng dụng trong điều phối giao thông đô thị. Khi không gian tìm kiếm mở rộng theo cấp số nhân, phương pháp duyệt vét cạn trở nên bất khả thi. Thời gian thực thi tăng vọt vượt quá giới hạn phần cứng cho phép. Sách chỉ rõ hạn chế của các giải pháp ngây thơ khi đối mặt với dữ liệu quy mô lớn. Việc hiểu rõ độ phức tạp tính toán giúp người lập trình nhận diện nút thắt cổ chai trong hệ thống. Đây là tiền đề để thiết kế thuật toán khả thi.

2.1. Thách thức từ bài toán NP đầy đủ và tô màu đồ thị

Tài liệu mổ xẻ bài toán tô màu đồ thị đại diện cho lớp bài toán NP-đầy đủ. Mỗi đỉnh biểu thị một tuyến đường giao thông xung khắc. Mỗi cung liên kết hai luồng giao thông không thể di chuyển cùng thời điểm. Mục tiêu đặt ra là phân bố số màu ít nhất cho các đỉnh của đồ thị. Số màu tối thiểu tương ứng với số pha đèn tín hiệu giao thông cần thiết. Tuy nhiên, việc tìm kiếm nghiệm tối ưu đòi hỏi chi phí tính toán bùng nổ. Phương pháp duyệt mọi khả năng trở nên quá tải khi số lượng đỉnh tăng cao. Vấn đề cốt lõi là cân bằng giữa thời gian tính toán và chất lượng lời giải trong điều kiện thực tế.

2.2. Vấn đề bùng nổ tổ hợp trong bài toán Tám quân hậu

Bài toán Tám quân hậu là ví dụ kinh điển về sự bùng nổ không gian trạng thái. Nhiệm vụ đặt tám quân hậu trên bàn cờ kích thước 8x8 sao cho không quân nào khống chế nhau. Hai quân bất kỳ không được nằm trên cùng hàng, cùng cột hoặc cùng đường chéo. Không gian tìm kiếm thuần túy chứa tới hơn bốn tỷ trường hợp sắp xếp. Nếu kiểm tra toàn bộ tổ hợp một cách ngẫu nhiên, hệ thống sẽ cạn kiệt tài nguyên xử lý. Lời giải đòi hỏi mô hình hóa chính xác các ràng buộc logic chặt chẽ. Giáo trình phân tích cách ánh xạ điều kiện biên thành các mảng kiểm tra trạng thái hiệu quả. Đây là bài toán mẫu mực để nghiên cứu các thuật toán tìm kiếm có kiểm soát.

III. Phương pháp giải thuật trong giáo trình của PGS

Để giải quyết các bài toán tối ưu và bùng nổ tổ hợp, tác giả giới thiệu những giải pháp thiết kế thuật toán kinh điển. Trọng tâm của phương pháp luận nằm ở kỹ thuật quay lui kết hợp đệ quy. Thuật toán tiến hành thử từng khả năng theo từng bước tuần tự. Khi phát hiện một nhánh tìm kiếm dẫn đến ngõ cụt, hệ thống lập tức lùi lại bước trước đó để đổi hướng. Cách tiếp cận này loại bỏ sớm hàng loạt nhánh tìm kiếm vô nghiệm trên cây quyết định. Bên cạnh quay lui, giáo trình trình bày chi tiết chiến lược tham lam để tìm kiếm lời giải xấp xỉ cho bài toán NP-đầy đủ. Tác giả minh họa cụ thể qua thuật toán tô màu đồ thị thực dụng: ưu tiên gán màu hiện tại cho tối đa các đỉnh tương thích trước khi dùng màu mới. Ngoài ra, việc tổ chức mảng boolean đánh dấu trạng thái giúp giảm độ phức tạp kiểm tra ràng buộc xuống O(1). Sự kết hợp này mang lại hiệu năng cao và tiết kiệm bộ nhớ.

3.1. Kỹ thuật đệ quy quay lui qua thủ tục TRY chuẩn mực

Giáo trình minh chứng sức mạnh của kỹ thuật quay lui qua thủ tục đệ quy TRY trong bài toán Tám quân hậu. Thuật toán sử dụng ba mảng boolean a, b và c để kiểm soát hàng ngang cùng hai đường chéo. Khi chọn vị trí cột j cho quân hậu ở hàng i, thủ tục kiểm tra điều kiện an toàn tức thì. Nếu hợp lệ, hệ thống đánh dấu trạng thái chiếm giữ và đệ quy sang cột tiếp theo. Trường hợp gặp bế tắc, giải thuật bỏ đánh dấu và thử phương án mới. Cấu trúc lặp repeat-until đảm bảo dừng ngay khi tìm thấy một nghiệm hợp lệ. Để xuất toàn bộ nghiệm, thủ tục chuyển sang vòng lặp for và gọi lệnh in kết quả tuần tự.

3.2. Chiến lược Heuristic và tham lam giải bài toán thực tế

Bên cạnh giải thuật chính xác, giáo trình nhấn mạnh giá trị thực tiễn của phương pháp gần đúng heuristic. Đối với bài toán tô màu đồ thị quy mô lớn, việc tìm kiếm nghiệm tối ưu tuyệt đối tiêu tốn quá nhiều tài nguyên máy tính. Tác giả đề xuất giải thuật tham lam có hiệu lực thực tế cao. Nguyên tắc cốt lõi là cố gắng tận dụng tối đa một màu trước khi chuyển sang màu tiếp theo. Thuật toán duyệt qua danh sách các đỉnh và gán cùng một màu cho các đỉnh không kề nhau. Khi không thể mở rộng tập đỉnh độc lập, màu mới mới được kích hoạt. Cách tiếp cận này tạo ra lời giải khả thi nhanh chóng. Đây là phương pháp hiệu quả trong bài toán phân luồng giao thông.

IV. Giá trị ứng dụng từ giáo trình cấu trúc dữ liệu Đỗ Xuân Lôi

Giáo trình Cấu trúc dữ liệu và giải thuật của PGS. Đỗ Xuân Lôi không chỉ đơn thuần là sách giáo khoa lý thuyết. Tác phẩm là chiếc cầu nối giữa khoa học máy tính hàn lâm và kỹ thuật phần mềm thực chiến. Các mô hình giải thuật trong sách trang bị nền tảng trực tiếp cho nhiều môn học chuyên ngành nâng cao. Sinh viên dễ dàng tiếp thu kiến thức về cơ sở dữ liệu quan hệ, trí tuệ nhân tạo, hệ chuyên gia và công nghệ trình dịch. Trong thời đại chuyển đổi số, năng lực xử lý dữ liệu tối ưu càng khẳng định tính trường tồn của các nguyên lý kinh điển. Thuật toán sắp xếp và tìm kiếm tiếp tục vận hành bên dưới các công cụ tìm kiếm hiện đại. Cấu trúc cây và đồ thị là xương sống của cơ sở dữ liệu lớn và mạng xã hội. Nắm vững giáo trình giúp lập trình viên viết mã nguồn sạch, tối ưu hóa bộ nhớ và tăng tốc độ xử lý phần mềm.

4.1. Nền tảng chuyên môn cho các môn học công nghệ chuyên sâu

Nội dung giáo trình là điều kiện tiên quyết trước khi bước vào các học phần chuyên sâu. Sinh viên cần kiến thức về danh sách liên kết và cây nhị phân để hiểu cơ chế chỉ mục trong cơ sở dữ liệu. Cấu trúc đồ thị hỗ trợ nghiên cứu mạng nơ-ron và thuật toán định tuyến trong mạng máy tính. Kiến thức về giải thuật đệ quy và cây cú pháp tạo tiền đề xây dựng chương trình dịch và ngôn ngữ hình thức. Ngoài ra, các phương pháp tối ưu hóa cung cấp tư duy giải quyết bài toán trong lĩnh vực trí tuệ nhân tạo và hệ chuyên gia. Cuốn sách giúp người học xây dựng khung lý thuyết toàn diện để tiếp thu công nghệ mới.

4.2. Tầm quan trọng của tư duy thuật toán đối với kỹ sư phần mềm

Tư duy thuật toán định hình năng lực cạnh tranh cốt lõi của kỹ sư phần mềm chuyên nghiệp. Ngôn ngữ lập trình hay công nghệ phát triển ứng dụng luôn thay đổi theo thời gian. Ngược lại, tư duy cấu trúc dữ liệu và giải thuật luôn giữ vững giá trị nền tảng. Việc phân tích độ phức tạp thời gian và không gian giúp kỹ sư viết mã nguồn tối ưu. Kỹ sư có thể dự đoán chính xác ngưỡng chịu tải của phần mềm trong môi trường sản xuất lớn. Năng lực làm chủ giải thuật phân biệt kỹ sư phát triển phần mềm cao cấp với lập trình viên thông thường. Giáo trình của PGS. Đỗ Xuân Lôi là kim chỉ nam bồi dưỡng tư duy kỹ thuật bền vững.

Nội dung chính

Tổng quan về giáo trình

Giáo trình "Cấu trúc dữ liệu và giải thuật" do Phó Giáo sư Đỗ Xuân Lôi biên soạn, Nhà xuất bản Đại học Quốc gia Hà Nội xuất bản (ấn bản lần thứ chín có sửa chữa, năm 2006). Công trình phản ánh nội dung môn học cơ sở trong khung chương trình đào tạo kỹ sư, cử nhân và cao đẳng tin học. Tài liệu được biên soạn dựa trên thực tiễn giảng dạy tại Khoa Tin học, Trường Đại học Bách khoa Hà Nội, cùng ý kiến đóng góp từ GS. Nguyễn Đình Trí (Chủ nhiệm đề tài cấp nhà nước KC01-13), PGS. Nguyễn Xuân Huy (Viện Tin học Việt Nam), PGS. Nguyễn Văn Ba và PTS. Nguyễn Thanh Thủy.

Về vị trí đào tạo, học phần có thời lượng 90 tiết (gồm lý thuyết và bài tập), học sau môn Tin học đại cương. Môn học đóng vai trò nền tảng, chuẩn bị kiến thức phục vụ trực tiếp cho các môn học chuyên ngành tiếp theo như Cơ sở dữ liệu, Trí tuệ nhân tạo, Hệ chuyên gia, Ngôn ngữ hình thức và Chương trình dịch.

Mục tiêu học tập của giáo trình là làm rõ mối liên hệ giữa cấu trúc dữ liệu và giải thuật, nâng cao kỹ thuật lập trình, rèn luyện phương pháp giải bài toán phi số và kỹ năng phân tích độ phức tạp thời gian. Toàn bộ nội dung gồm 11 chương chia làm 3 phần: Phần I nghiên cứu phương pháp thiết kế, phân tích giải thuật và giải thuật đệ qui; Phần II khảo sát các cấu trúc mảng, danh sách, cây, đồ thị; Phần III tập trung vào sắp xếp và tìm kiếm. Điểm đặc sắc của giáo trình là sử dụng "ngôn ngữ tựa PASCAL" linh hoạt, diễn đạt bằng tiếng Việt, giúp người học tập trung vào bản chất thuật toán mà không bị ràng buộc bởi các quy tắc cú pháp cơ học.

Nội dung kiến thức cốt lõi

Các chương/chủ đề chính

Nội dung tài liệu được triển khai theo trật tự logic chặt chẽ qua các chương trọng tâm:

• Chương 1 (Mở đầu): Xác định giải thuật là chuỗi câu lệnh xác định thứ tự thao tác trên đối tượng dữ liệu. Tác giả phân tích dữ liệu nguyên tử (atoms), cấu trúc dữ liệu, cấu trúc lưu trữ trong và ngoài, cấu trúc dữ liệu tiền định và tự định nghĩa; đồng thời thiết lập quy tắc cho "ngôn ngữ tựa PASCAL" với các lệnh gán, lệnh ghép, lệnh tuyển (case), vòng lặp (for, while, repeat) và chương trình con (function, procedure).
• Chương 2 (Thiết kế và phân tích giải thuật): Trình bày chiến lược chia để trị, thiết kế từ đỉnh xuống (top-down) qua bài toán quản lý hồ sơ học bổng; phương pháp tinh chỉnh từng bước (stepwise refinement) qua bài toán sắp xếp SORT và in đường chéo ma trận vuông INCHEO; giải thuật tham ăn (greedy algorithm) giải bài toán tô màu đồ thị điều khiển đèn giao thông. Chương này xác lập lý thuyết độ phức tạp qua ký pháp Big-O, quy tắc cộng, quy tắc nhân và đánh giá hiệu năng trung bình của giải thuật tìm kiếm SEARCH.
• Chương 3 (Giải thuật đệ qui): Định nghĩa bản chất đệ qui, đệ qui trực tiếp và gián tiếp, vai trò của trường hợp suy biến (degenerate case) qua các bài toán tính giai thừa FACTORIAL, dãy số Fibonacci, Tháp Hà Nội và thuật toán quay lui (backtracking) giải bài toán 8 quân hậu.
• Phần II và Phần III: Phát triển các cấu trúc mảng, danh sách, cây, đồ thị cùng các giải thuật sắp xếp và tìm kiếm dữ liệu.

Kiến thức nền tảng được xây dựng

Giáo trình xây dựng ba khối kiến thức nền tảng:

• Mối quan hệ giữa cấu trúc dữ liệu và giải thuật: Tác giả nhấn mạnh cấu trúc dữ liệu và giải thuật gắn bó chặt chẽ; cấu trúc dữ liệu thay đổi kéo theo giải thuật thay đổi tương ứng. Khi lựa chọn cấu trúc dữ liệu, người học phải đồng thời xác định các phép toán tương ứng tác động trên cấu trúc đó.
• Nguyên lý thiết kế phần mềm có cấu trúc: Vận dụng mô-đun hóa kết hợp chiến lược chia để trị, phân chia bài toán lớn thành các mô-đun con độc lập; áp dụng quy trình tinh chỉnh từng bước từ ngôn ngữ tự nhiên sang giả mã rồi chuyển đổi về ngôn ngữ lập trình.
• Khung lý thuyết tiệm cận toán học: Định nghĩa hình thức cấp độ lớn thời gian $f(n) = O(g(n))$ bị chặn trên bởi $c \cdot g(n)$; phân loại các họ hàm thời gian gồm nhóm hàm đa thức ($\log_2 n, n, n \log_2 n, n^2, n^3$) và nhóm hàm mũ ($2^n, n!, n^n$); nguyên lý phân tích phép toán tích cực và mô hình hóa bài toán đồ thị thuộc lớp NP-đầy đủ.

Kỹ năng phát triển

Qua nội dung giáo trình, người học được rèn luyện các nhóm kỹ năng thực hành và tư duy:

• Kỹ năng kỹ thuật: Khả năng ánh xạ cấu trúc dữ liệu logic sang cấu trúc lưu trữ vật lý trong bộ nhớ; kỹ thuật cài đặt giải thuật đệ qui và giải thuật quay lui lưu vết trạng thái; kỹ năng viết mã giả tựa PASCAL chuẩn hóa để chuyển đổi sang các ngôn ngữ lập trình như PASCAL hoặc C.
• Kỹ năng phân tích: Năng lực đánh giá độ phức tạp thuật toán độc lập với phần cứng; phân tích thời gian thực hiện trong tình huống tốt nhất, xấu nhất và trung bình dựa trên xác suất; nhận diện bài toán tối ưu tổ hợp phức tạp để lựa chọn giải thuật heuristic phù hợp.
• Năng lực thực tế: Kỹ năng xử lý các bài toán phi số với dữ liệu lớn và biến động; khả năng mô hình hóa bài toán thực tế thành bài toán đồ thị và ma trận; kỹ năng tổ chức dữ liệu tệp tin và bản ghi trong các ứng dụng quản lý.

Phương pháp giảng dạy và học tập

Phương pháp sư phạm của giáo trình được xây dựng theo nguyên tắc kết hợp giữa lý thuyết hình thức và thực nghiệm lập trình. Tác giả áp dụng cách tiếp cận quy nạp: xuất phát từ những bài toán thực tiễn quen thuộc để dẫn dắt người học đến các khái niệm khoa học trừu tượng. Ví dụ, mối quan hệ giữa cấu trúc dữ liệu và giải thuật được phân tích qua bài toán tra danh bạ điện thoại: từ phương pháp tìm kiếm tuần tự khi danh sách ngắn, đến tìm kiếm từ điển khi dữ liệu đã có thứ tự, và tìm kiếm phân nhóm khi bổ sung bảng mục lục chữ cái đầu.

Tiến trình giải quyết vấn đề tuân thủ phương pháp thiết kế từ đỉnh xuống và tinh chỉnh từng bước. Bài toán quản lý hồ sơ học bổng sinh viên được phân chia thành các nhiệm vụ chính gồm đọc tệp, xử lý tệp, ghi tệp, sau đó chi tiết hóa thành các thao tác tìm kiếm, cập nhật và in ấn. Quy trình tinh chỉnh giả mã đi từ mô tả ngôn ngữ tự nhiên, chuyển sang mã giả với các cấu trúc điều khiển (if-then, case, for, while, repeat, call, return), trước khi hình thành chương trình PASCAL hoàn chỉnh như bài toán INCHEO in các đường chéo ma trận vuông.

Hệ thống bài tập cuối mỗi chương được thiết kế ở mức độ trung bình, giúp người học củng cố lý thuyết và tiếp cận các kiến thức mở rộng không trình bày trực tiếp trên lớp. Bài tập bao gồm câu hỏi lý thuyết phân tích (so sánh thiết kế top-down và bottom-up), bài toán đồ thị tổ hợp (xếp lịch thi đấu 6 đội bóng A, B, C, D, E, F trong số tuần ít nhất), và bài tập xác định độ phức tạp Big-O qua các vòng lặp lồng nhau.

Đối với hoạt động tự học, giáo trình đặt ra hệ thống câu hỏi định hướng tư duy giúp người học tự thẩm định tính đúng đắn của giải thuật, rèn luyện kỹ năng đánh giá thời gian thực thi qua phép toán tích cực và chủ động chuyển đổi các thuật toán mẫu sang các ngôn ngữ lập trình hiện đại.

Điểm nổi bật và cập nhật

Giáo trình "Cấu trúc dữ liệu và giải thuật" ghi nhận quá trình chỉnh lý qua nhiều lần xuất bản. Từ bản in đầu tiên vào tháng 8 năm 1993 đến lần tái bản thứ chín năm 2006 (hiệu chỉnh từ lần thứ bảy), tác giả Đỗ Xuân Lôi đã bổ sung nhiều chuyên đề lý thuyết và bài tập dựa trên kinh nghiệm giảng dạy tại Trường Đại học Bách khoa Hà Nội, giúp nội dung phù hợp với nhiều hệ đào tạo khác nhau.

Về mặt khoa học, điểm nổi bật của giáo trình là việc tập trung vào các bài toán phi số (non-numerical problems). Khác với bài toán khoa học kỹ thuật truyền thống chỉ thao tác trên vectơ hay ma trận số học, bài toán phi số xử lý khối lượng dữ liệu lớn, đa dạng và có cấu trúc liên tục biến động. Giáo trình phân định rành mạch giữa cấu trúc dữ liệu và cấu trúc lưu trữ (trong và ngoài), đồng thời xác lập các phép toán chuyên biệt gồm tạo lập, hủy bỏ, truy cập, bổ sung và loại bỏ phần tử.

Bên cạnh đó, tài liệu tích hợp các phương pháp giải quyết bài toán công nghiệp thực tế. Điển hình là việc mô hình hóa hệ thống 13 tuyến đường giao nhau tại một giao lộ thành đồ thị vô hướng. Nhận diện đây là bài toán tô màu đồ thị thuộc lớp bài toán NP-đầy đủ, giáo trình đưa vào giải thuật heuristic "tham ăn" (greedy algorithm) để đạt được phân hoạch 4 pha đèn tín hiệu tối ưu về mặt thực tiễn trong thời gian ngắn. Ngoài ra, việc tổ chức dữ liệu dạng bản ghi (record) và trường (field) phản ánh trực tiếp cấu trúc của các hệ thống cơ sở dữ liệu hiện đại.

Đối tượng sử dụng giáo trình

Giáo trình "Cấu trúc dữ liệu và giải thuật" được biên soạn phục vụ các nhóm đối tượng trong hệ thống giáo dục đại học và nghiên cứu công nghệ thông tin:

• Sinh viên đại học và cao đẳng: Tài liệu là giáo trình chính khóa cho sinh viên hệ kỹ sư tin học, cử nhân tin học và cao đẳng tin học. Chương trình học được thiết kế cho thời lượng 90 tiết học gồm cả lý thuyết và bài tập.
• Kiến thức tiên quyết (Prerequisites): Sinh viên trước khi học cần hoàn thành môn Tin học đại cương, nắm vững các cấu trúc dữ liệu tiền định cơ bản (biến, mảng, bản ghi), cú pháp lập trình cơ bản và các khái niệm đại số, giải tích nền tảng.
• Học viên cao học và nghiên cứu sinh: Giáo trình cung cấp nội dung mở rộng làm tài liệu tham khảo cho sinh viên cao học, nghiên cứu sinh, đặc biệt trong các chủ đề đánh giá độ phức tạp thời gian trung bình bằng xác suất, lớp bài toán NP-đầy đủ, giải thuật heuristic và thuật toán quay lui.
• Giảng viên và cán bộ tin học: Cuốn sách là tài liệu tham khảo giảng dạy cho giảng viên tin học, đồng thời giúp các cán bộ kỹ thuật củng cố phương pháp luận thiết kế chương trình, chuẩn hóa kỹ thuật mô-đun hóa và tối ưu hóa giải thuật trong phát triển phần mềm.

Câu hỏi thường gặp

1. Giáo trình này phù hợp với ai? Giáo trình phù hợp làm tài liệu học tập chính thức cho sinh viên hệ kỹ sư, cử nhân, cao đẳng tin học; đồng thời là tài liệu tham khảo cho học viên cao học, nghiên cứu sinh, giảng viên và cán bộ kỹ thuật muốn nâng cao năng lực thiết kế giải thuật.

2. Cần kiến thức nền nào để học? Người học cần hoàn thành môn Tin học đại cương, hiểu biết về cú pháp của một ngôn ngữ lập trình bậc cao (như PASCAL, C), nắm được các cấu trúc dữ liệu tiền định cơ bản và có kiến thức toán học về logic, hàm số, giải tích và xác suất cơ bản.

3. Điểm khác biệt với giáo trình khác? Giáo trình phân định rõ ràng giữa cấu trúc dữ liệu logic và cấu trúc lưu trữ vật lý trong bộ nhớ; sử dụng "ngôn ngữ tựa PASCAL" tiếng Việt độc lập với cú pháp máy móc; đồng thời tích hợp lý thuyết phân tích độ phức tạp tiệm cận Big-O với các giải thuật heuristic giải bài toán NP-đầy đủ trên đồ thị.

4. Làm sao để tự học hiệu quả? Người học nên áp dụng phương pháp tinh chỉnh từng bước: phân tích bài toán bằng ngôn ngữ tự nhiên, chuyển thể sang mã giả tựa PASCAL, sau đó cài đặt trực tiếp trên trình biên dịch để kiểm thử; đồng thời hoàn thành toàn bộ hệ thống bài tập lý thuyết và bài toán thuật toán cuối mỗi chương.

5. Có tài liệu bổ trợ nào kèm theo? Giáo trình tích hợp sẵn hệ thống bài tập chọn lọc cuối chương (gồm bài tập lý thuyết, phân tích Big-O và lập lịch đồ thị), các chương trình PASCAL mẫu hoàn chỉnh (như INCHEO) và các sơ đồ cấu trúc phân cấp, mô hình đồ thị trực quan.

Kết luận

Giáo trình "Cấu trúc dữ liệu và giải thuật" của PGS. Đỗ Xuân Lôi là tài liệu khoa học hệ thống về tổ chức dữ liệu và phương pháp thiết kế giải thuật trong chương trình đào tạo kỹ sư tin học. Giá trị cốt lõi của cuốn sách thể hiện ở tính sư phạm, sự gắn kết giữa lý thuyết toán học hình thức và khả năng giải quyết các bài toán phi số trong thực tiễn.

Về lộ trình học tập, tài liệu định hướng người học tiếp cận từ nhận thức về mối quan hệ giữa dữ liệu và giải thuật, kỹ thuật phân tích tiệm cận thời gian Big-O và giải thuật đệ qui ở Phần I; tiến tới làm chủ các cấu trúc dữ liệu tuyến tính và phi tuyến ở Phần II; sau đó hoàn thiện kỹ năng cài đặt qua các giải thuật sắp xếp, tìm kiếm ở Phần III trước khi bước vào các môn học chuyên ngành.

Hệ thống bài tập phân loại cùng các mã giả tựa PASCAL trong tài liệu là nguồn tài nguyên học thuật nền tảng hỗ trợ sinh viên và cán bộ kỹ thuật phát triển năng lực tư duy lập trình chuyên sâu.

Trích đoạn nội dung tài liệu

CHƯƠNG 1 1. Tìm thêm các ví dụ minh họa mối quan hệ giữa cấu trúc dữ liệu và giải thuật. | Các bài toán phi số khác với các bài toán khoa học kỹ thuật ở những đặc điểm gì? 1. Cấu trúc dữ liệu và cấu trúc lưu trữ khác nhau ở chỗ nào? 1.

Hãy nêu một vài cấu trúc đữ liệu tiền định của các ngôn ngữ mà anh (chị) biết. L5: Các cấu trúc dữ liệu tiền định trong một ngôn ngữ có đủ đáp ứng mọi yêu cầu về tổ chức dữ liệu không? Có thể có cấu trúc dữ liệu do người dùng định ra không? 1. Một chương trình PASCAL có phải là một tập dữ liệu có cấu trúc không? 1. Hãy nêu các tính chất của một giải thuật và cho ví dụ mịnh hoa.ð§ À` $t 18 Chương 2 THIẾT KẾ VÀ PHÂN TÍCH GIẢI THUẬT 2.1 Từ bài toán đến chương trình 2.1 Mô-đun hoá và việc giải quyết bài toán Các bài toán giải được trên máy tính điện tử ngày càng đa dạng và phức tạp.

Các giải thuật và chương trình để giải chúng cũng ngày càng có quy mô lớn và càng khó khi thiết lập cũng như khi muốn tìm hiểu. Tuy nhiên, ta cũng thấy rằng mọi việc sẽ đơn giản hơn nếu như có thê phân chia bài toán lớn của ta thành các bài toán nhỏ. Điều đó cũng có nghĩa là nêu coi bài toán của ta như một mô-đun chính thì cần chia nó thành các mô-đun con, và đi nhiên, với tinh thần như thế, đến lượt nó, mỗi mô-đun này lại được phân chia tiếp cho tới những mô-đun ứng với các phần việc cơ bản mà ta đã biết cách giải quyết. Như vậyviệc tổ chức lời giải của bài toán sẽ được thể hiện theo một cấu trúc phân cấp, có dạng như hình sau: Hình 2.1 Chiến thuật giải quyết bài toán theo tinh thần như vậy chính là chiến thuật "chia để trị" (divide and conquer).

Để thể hiện chiến thuật đó, người ta dùng cách thiết kế “ft đỉnh xuống” (top-down design). Đó là cách phân I9 tích tổng quát toàn bộ vấn đề, xuất phát từ đữ kiện và các mục tiêu đặt ra, để đề cập đến những công việc chủ yếu, rồi sau đó mới di dần vào giải quyết các phần cụ thể một cách chỉ tiết hơn (cũng vì vậy mà người ta gọi là cách thiết kế từ khái quát đến chỉ tiết). Ví dụ ta nhận được từ Chủ tịch Hội đồng xét cấp học bổng của trường một yêu cầu là: "Dùng máy tính điện tử để quản lý và bảo trì các hồ sơ về học bổng của các sinh viên ở diện được tài trợ, đồng thời thường kỳ phải lập các báo cáo tổng kết để đệ trình lên Bộ”. Như vậy trước hết ta phải hình dung được cụ thể hơn đầu vào và đầu ra của bài toán.

Có thể coi như ta đã có mội tập các hồ sơ (mà ta gọi là /¿/2 - file) bao gồm các bản ghi (records) về các thông tin liên quan tới học bổng của sinh viên, chẳng hạn: số hiệu sinh viên, điểm trung bình (theo học kỳ), điểm đạo đức, khoản tiền tài trợ. Và chương trình lập ra phải tạo điều kiện cho người sử dụng giải quyết được các yêu cầu sau: 1) Tìm lại và hiển thị được bản ghi của bất kỳ sinh viên nào tại thiết bị cuối (terminal) của người dùng. 2) Cập nhật (update) được bản ghi của một sinh viên cho trước bằng cách thay đổi điểm trung bình, điểm đạo đức, khoản tiền tài trợ, nếu cần. 3) In bản tổng kết chứa những thông tin hiện thời (đã được cập nhật mỗi khi có thay đổi) gồm số hiệu, điểm trung bình, điểm đạo đức, khoản tiền tài trợ.