Giáo Trình Cấu Trúc Dữ Liệu và Giải Thuật Trung Cấp

Khám phá giáo trình cấu trúc dữ liệu và giải thuật cho nghề công nghệ thông tin trung cấp, cung cấp kiến thức và kỹ năng cần thiết cho sinh viên.

• Tác giả: Nguyễn Như Cường
• Trường học: Trường Trung Cấp Trường Sơn Đắk Lắk
• Chuyên ngành: Cấu Trúc Dữ Liệu và Giải Thuật
• Đề tài: Giáo Trình Cấu Trúc Dữ Liệu và Giải Thuật Trung Cấp
• Loại tài liệu: giáo trình
• Năm xuất bản: 2022
• Địa điểm: Đắk Lắk

Mục lục chi tiết

• LỜI GIỚI THIỆU
• 1. CHƯƠNG I: THIẾT KẾ VÀ PHÂN TÍCH GIẢI THUẬT
• 1.1. Modul hóa việc giải quyết bài toán
• 1.2. Phương pháp tinh chỉnh từng bước
• 1.3. Phân tích giải thuật
• 1.4. Độ phức tạp tính toán của giải thuật
• 2. CHƯƠNG II: ĐỆ QUY VÀ GIẢI THUẬT ĐỆ QUY
• 2.1. Khái niệm đệ quy
• 2.2. Giải thuật đệ quy và thủ tục đệ quy
• 2.3. Bài toán tính n!
• 2.4. Dãy số Fibonacci
• 2.5. Bài toán tháp Hà Nội
• 3. CHƯƠNG III: MẢNG VÀ DANH SÁCH
• 3.1. Khái niệm
• 3.2. Cấu trúc lưu trữ của mảng
• 3.3. Đánh nghĩa kiểu cấu trúc
• 3.4. Khai báo biến cấu trúc
• 3.5. Lưu trữ kế tiếp của danh sách tuyến tính
• 4. CHƯƠNG IV: CÁC KHÁI NIỆM CƠ BẢN
• 4.1. Đánh nghĩa cây
• 4.2. Biểu diễn cây
• 4.3. Cây nhị phân (Binary Tree)
• 4.4. Phép duyệt cây nhị phân
• 4.4.1. Duyệt theo thứ tự trước NLR (Node – Left – Right)
• 4.4.2. Duyệt theo thứ tự giữa LNR (Left – Node – Right)
• 4.4.3. Duyệt theo thứ tự sau LRN (Left – Right – Node)
• 4.5. Cây nhị phân tìm kiếm
• 4.6. Độ thưa và một vài cấu trúc phi tuyến
• 4.7. Các khái niệm về đồ thị
• 4.8. Biểu diễn đồ thị
• 4.9. Phép duyệt đồ thị
• 4.9.1. Tìm kiếm theo chiều sâu
• 4.9.2. Tìm kiếm theo chiều rộng
• 4.10. Giải thuật Kruskal
• 4.11. Giải thuật Prim
• 4.12. Câu hỏi và bài tập
• 5. CHƯƠNG V: ĐÁ THÁ VÀ MỘT VÀI CẤU TRÚC PHI TUYẾN
• 6. CHƯƠNG VI: SẮP XẾP VÀ TÌM KIẾM
• 6.1. Mật số phương pháp sắp xếp
• 6.2. Khái quát và tìm kiếm
• 6.3. Câu hỏi và bài tập
• TÀI LIỆU THAM KHẢO

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 Trung Cấp

Giáo trình Cấu trúc dữ liệu và giải thuật trung cấp là tài liệu quan trọng trong chương trình đào tạo ngành Công nghệ thông tin. Tài liệu này cung cấp kiến thức cơ bản về các cấu trúc dữ liệu và thuật toán, giúp sinh viên nắm vững các khái niệm và ứng dụng trong lập trình. Việc hiểu rõ về cấu trúc dữ liệu sẽ giúp sinh viên phát triển kỹ năng lập trình và giải quyết vấn đề hiệu quả hơn.

1.1. Khái niệm về Cấu Trúc Dữ Liệu

Cấu trúc dữ liệu là cách tổ chức và lưu trữ dữ liệu trong máy tính. Nó cho phép việc truy cập và sửa đổi dữ liệu một cách hiệu quả. Các loại cấu trúc dữ liệu phổ biến bao gồm mảng, danh sách liên kết, ngăn xếp và hàng đợi.

1.2. Vai trò của Giải Thuật trong Lập Trình

Giải thuật là một tập hợp các bước để giải quyết một vấn đề cụ thể. Việc áp dụng giải thuật đúng cách giúp tối ưu hóa hiệu suất của chương trình, giảm thiểu thời gian và tài nguyên cần thiết cho việc xử lý dữ liệu.

II. Những Thách Thức trong Việc Học Cấu Trúc Dữ Liệu và Giải Thuật

Học cấu trúc dữ liệu và giải thuật không phải là điều dễ dàng. Sinh viên thường gặp khó khăn trong việc hiểu và áp dụng các khái niệm phức tạp. Ngoài ra, việc lựa chọn cấu trúc dữ liệu phù hợp cho từng bài toán cũng là một thách thức lớn.

2.1. Khó khăn trong Việc Hiểu Các Khái Niệm Cơ Bản

Nhiều sinh viên gặp khó khăn trong việc nắm bắt các khái niệm như danh sách liên kết, ngăn xếp và hàng đợi. Việc thiếu thực hành cũng làm cho việc hiểu sâu về các cấu trúc này trở nên khó khăn hơn.

2.2. Lựa Chọn Giải Thuật Phù Hợp

Việc lựa chọn giải thuật phù hợp cho từng bài toán là một thách thức lớn. Sinh viên cần phải hiểu rõ về độ phức tạp thời gian và không gian của từng giải thuật để đưa ra quyết định đúng đắn.

III. Phương Pháp Học Hiệu Quả Cấu Trúc Dữ Liệu và Giải Thuật

Để học hiệu quả cấu trúc dữ liệu và giải thuật, sinh viên cần áp dụng các phương pháp học tập tích cực. Việc thực hành thường xuyên và tham gia vào các dự án thực tế sẽ giúp củng cố kiến thức và kỹ năng lập trình.

3.1. Thực Hành Thông Qua Dự Án

Tham gia vào các dự án thực tế giúp sinh viên áp dụng lý thuyết vào thực tiễn. Việc này không chỉ giúp củng cố kiến thức mà còn phát triển kỹ năng làm việc nhóm.

3.2. Sử Dụng Tài Nguyên Học Tập Trực Tuyến

Có nhiều tài nguyên học tập trực tuyến như video, bài giảng và diễn đàn thảo luận. Sử dụng các tài nguyên này sẽ giúp sinh viên tiếp cận kiến thức một cách dễ dàng và hiệu quả hơn.

IV. Ứng Dụng Cấu Trúc Dữ Liệu và Giải Thuật trong Thực Tiễn

Cấu trúc dữ liệu và giải thuật có ứng dụng rộng rãi trong nhiều lĩnh vực như phát triển phần mềm, khoa học dữ liệu và trí tuệ nhân tạo. Việc hiểu rõ về chúng sẽ giúp sinh viên có thể giải quyết các bài toán phức tạp trong thực tế.

4.1. Ứng Dụng trong Phát Triển Phần Mềm

Trong phát triển phần mềm, việc lựa chọn cấu trúc dữ liệu phù hợp có thể ảnh hưởng lớn đến hiệu suất của ứng dụng. Các lập trình viên cần nắm vững các cấu trúc này để tối ưu hóa mã nguồn.

4.2. Ứng Dụng trong Khoa Học Dữ Liệu

Trong khoa học dữ liệu, cấu trúc dữ liệu và giải thuật được sử dụng để xử lý và phân tích dữ liệu lớn. Việc áp dụng đúng các thuật toán sẽ giúp rút ra thông tin giá trị từ dữ liệu.

V. Kết Luận và Tương Lai của Cấu Trúc Dữ Liệu và Giải Thuật

Cấu trúc dữ liệu và giải thuật là nền tảng quan trọng trong lập trình. Việc nắm vững kiến thức này không chỉ giúp sinh viên trong học tập mà còn trong sự nghiệp sau này. Tương lai của lĩnh vực này sẽ tiếp tục phát triển với sự xuất hiện của các công nghệ mới.

5.1. Tầm Quan Trọng của Cấu Trúc Dữ Liệu

Cấu trúc dữ liệu đóng vai trò quan trọng trong việc tối ưu hóa hiệu suất của các ứng dụng. Việc hiểu rõ về chúng sẽ giúp lập trình viên phát triển các giải pháp hiệu quả hơn.

5.2. Xu Hướng Phát Triển trong Giải Thuật

Các giải thuật mới đang được phát triển để đáp ứng nhu cầu ngày càng cao trong xử lý dữ liệu. Việc cập nhật kiến thức về các giải thuật mới sẽ giúp sinh viên luôn đi đầu trong lĩnh vực công nghệ.

Nội dung chính

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

Giáo trình môn học Cấu trúc dữ liệu và giải thuật (Mã môn học: MH10) là tài liệu học tập thuộc khối kiến thức cơ sở nghề trong chương trình đào tạo trình độ Trung cấp nghề Công nghệ thông tin (chuyên ngành Ứng dụng phần mềm), đồng thời được sử dụng làm tài liệu tham khảo cho các ngành nghề kỹ thuật liên quan. Giáo trình được biên soạn bởi nhóm tác giả: Nguyễn Như Cường (Chủ biên), Nguyễn Thị Nhung và Lưu Thị Thương, ban hành theo Quyết định số 140/QĐ-TCTS ngày 02 tháng 8 năm 2022 của Hiệu trưởng Trường Trung cấp Trường Sơn Đắk Lắk. Trong tiến trình đào tạo, môn học được bố trí giảng dạy sau các môn học chung và trước các mô-đun chuyên môn nghề.

Mục tiêu học tập của giáo trình tập trung vào việc trang bị cho người học mối quan hệ bản chất giữa cấu trúc dữ liệu và giải thuật trong xây dựng phần mềm; cung cấp phương pháp xác định thời gian thực hiện giải thuật và độ phức tạp tính toán thông qua ký hiệu tiệm cận; làm rõ nguyên lý của giải thuật đệ quy; phương pháp biểu diễn và cài đặt các cấu trúc dữ liệu tuyến tính (Mảng, Danh sách liên kết, Ngăn xếp, Hàng đợi) cũng như cấu trúc dữ liệu phi tuyến (Cây, Đồ thị); cùng hệ thống các thuật toán sắp xếp và tìm kiếm thông dụng.

Về cấu trúc và thời lượng, giáo trình được thiết kế với tổng thời lượng 60 giờ, bao gồm 15 giờ lý thuyết, 43 giờ thực hành và 2 giờ kiểm tra định kỳ. Nội dung được triển khai theo hướng kết hợp giữa phân tích cơ sở lý thuyết toán học/logic và hướng dẫn cài đặt cụ thể trên hai ngôn ngữ lập trình C và Pascal. Điểm đặc thù của giáo trình là tỷ trọng thực hành chiếm hơn 71% tổng thời lượng đào tạo (43/60 giờ), chú trọng việc minh họa giải thuật bằng mã giả (pseudo-code) và mã nguồn hoàn chỉnh của các cấu trúc dữ liệu.

---

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

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

Giáo trình gồm 6 chương với tiến trình tiếp cận từ lý thuyết phân tích giải thuật, cấu trúc tuyến tính, cấu trúc phi tuyến đến các thuật toán xử lý dữ liệu nâng cao:

• Chương I: Thiết kế và phân tích giải thuật (7 giờ: 2 lý thuyết, 5 thực hành): Thiết lập phương trình nền tảng $\text{Cấu trúc dữ liệu} + \text{Giải thuật} = \text{Chương trình}$. Giới thiệu phương pháp modul hóa, phương pháp tinh chỉnh từng bước. Phân tích độ phức tạp thuật toán qua độ phức tạp thời gian ($T(n)$) và độ phức tạp bộ nhớ; đánh giá theo các trường hợp: tốt nhất ($T_{min}$), xấu nhất ($T_{max}$), trung bình ($T_{avg}$); chuẩn hóa đánh giá thông qua ký hiệu độ phức tạp Big-O, áp dụng quy tắc cộng và quy tắc nhân.
• Chương II: Đệ quy và giải thuật đệ quy (5 giờ: 2 lý thuyết, 3 thực hành): Định nghĩa hàm đệ quy, giải thuật và thủ tục đệ quy. Quy trình thiết kế thuật toán đệ quy; cơ chế phân tích thứ tự gọi hàm và quy tắc đánh trả giá trị theo chiều ngược lại. Cài đặt các bài toán mẫu: tính giai thừa $n!$, dãy số Fibonacci ($Fibonacci(n) = Fibonacci(n-1) + Fibonacci(n-2)$), và bài toán Tháp Hà Nội.
• Chương III: Mảng và danh sách (8 giờ: 2 lý thuyết, 5 thực hành, 1 kiểm tra): Cấu trúc lưu trữ của mảng 1 chiều, mảng 2 chiều theo hàng trong bộ nhớ; định nghĩa kiểu dữ liệu có cấu trúc (struct, typedef struct). Phân tích hai cơ chế lưu trữ danh sách tuyến tính: danh sách đặc (lưu trữ kế tiếp) và danh sách liên kết (đơn, đôi, vòng). Phân tích cấu trúc Ngăn xếp (Stack - LIFO) quản lý qua con trỏ đỉnh SP và ứng dụng trong ký pháp Ba Lan (biểu thức hậu tố); cấu trúc Hàng đợi (Queue - FIFO) quản lý qua hai chỉ số Front và Rear, kỹ thuật tổ chức mảng xoay vòng và giải pháp chống tràn hàng đợi.
• Chương IV: Cây (17 giờ: 4 lý thuyết, 13 thực hành): Định nghĩa cây tổng quát ($N$-phân) theo phương pháp quy nạp đệ quy; các khái niệm nút gốc, cây con, bậc của nút/cây, nút lá, nút trung gian, mức nút, chiều cao cây, chiều dài đường đi trong và ngoài. Khảo sát chi tiết Cây nhị phân (Binary Tree) với các phép duyệt: tiền thứ tự (NLR), trung thứ tự (LNR), hậu thứ tự (LRN). Xây dựng Cây nhị phân tìm kiếm (BST): thuật toán tìm kiếm đệ quy và không đệ quy, thuật toán chèn nút (ChenNut), thuật toán xóa nút (XoaNut qua 3 trường hợp và kỹ thuật tìm nút thế mạng TimNutTheMang), thuật toán giải phóng bộ nhớ (XoaCay). Giới thiệu ứng dụng cây quyết định và mã nén Huffman.
• Chương V: Đồ thị và một vài cấu trúc phi tuyến (8 giờ: 2 lý thuyết, 6 thực hành): Hệ thống các định nghĩa: đơn đồ thị, đa đồ thị, giả đồ thị, đồ thị có hướng, đồ thị vô hướng nền. Phương pháp biểu diễn đồ thị qua ma trận liền kề $A=(a_{ij})$ và danh sách lân cận. Thuật toán duyệt đồ thị: tìm kiếm theo chiều sâu (DFS - sử dụng Stack, độ phức tạp $O(|V|+|E|)$) và tìm kiếm theo chiều rộng (BFS - sử dụng Queue). Xây dựng cây khung nhỏ nhất thông qua hai giải thuật: giải thuật Kruskal (độ phức tạp $O(p^2)$ hoặc $O(n^2)$) và giải thuật Prim (độ phức tạp $O(n^3)$ trên ma trận trọng số).
• Chương VI: Sắp xếp và tìm kiếm (15 giờ: 3 lý thuyết, 11 thực hành, 1 kiểm tra): Phân loại sắp xếp nội (trên bộ nhớ trong) và sắp xếp ngoại (trên tệp tin). Trình bày cơ chế và mã cài đặt các thuật toán sắp xếp nội: Sắp xếp nổi bọt (Bubble Sort với công thức tính số phép so sánh $S = \frac{1}{2}N(N-1)$ và số phép hoán vị $H_{avg} = \frac{1}{4}N(N-1)$), Sắp xếp chọn (Selection Sort), Sắp xếp chèn (Insertion Sort), Sắp xếp nhanh (Quick Sort sử dụng hàm phân hoạch Partition và đệ quy), Sắp xếp hòa nhập (Merge Sort).

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

Giáo trình hình thành nền tảng lý thuyết thông qua ba nhóm kiến thức:

1. Lý thuyết kiểu dữ liệu trừu tượng (ADT): Nguyên lý đóng gói dữ liệu và các thao tác đi kèm, phân biệt giữa cấu trúc logic và cấu trúc vật lý trong bộ nhớ RAM.
2. Lý thuyết phân tích hiệu năng: Đánh giá tiệm cận hàm thời gian, đo lường số phép so sánh, phép gán, và phép hoán vị để ước lượng tài nguyên tính toán.
3. Kỹ thuật thiết kế thuật toán cốt lõi: Áp dụng nguyên lý đệ quy, phương pháp phân rã bài toán, kỹ thuật chia để trị (Divide and Conquer) và phương pháp tham lam (Greedy).

Kỹ năng phát triển

• Kỹ năng kỹ thuật (Technical skills): Định nghĩa và thao tác cấu trúc dữ liệu bằng con trỏ, cấp phát và giải phóng bộ nhớ động; cài đặt danh sách liên kết đơn, danh sách liên kết đôi, ngăn xếp, hàng đợi, cây nhị phân tìm kiếm bằng ngôn ngữ C/Pascal.
• Kỹ năng phân tích (Analytical skills): Khả năng phân tích trường hợp tốt nhất, xấu nhất của thuật toán; so sánh hiệu năng giữa duyệt đồ thị DFS và BFS, giữa giải thuật cây khung Kruskal và Prim trên đồ thị thưa hoặc dày.
• Năng lực thực hành (Practical competencies): Chuyển đổi biểu thức trung tố sang hậu tố, giải thuật toán khử đệ quy cho QuickSort bằng Stack, chuyển đổi cây nhị phân sang danh sách liên kết đôi, xử lý bài toán Josephus bằng danh sách liên kết vòng.

---

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

Giáo trình áp dụng phương pháp tiếp cận sư phạm đi từ mô tả bài toán thực tế, mô hình hóa cấu trúc dữ liệu, phân tích mã giả đến cài đặt mã nguồn chi tiết:

• Phương pháp giảng dạy: Giảng viên sử dụng phương pháp diễn giải kết hợp phân tích thuật toán từng bước qua bảng theo dõi biến số. Các nội dung phức tạp như duyệt cây đệ quy, xoay vòng hàng đợi hay thuật toán tìm cây khung Prim được minh họa cụ thể qua bảng trạng thái và ma trận trọng số.
• Bài tập và tình huống thực hành: Giáo trình lồng ghép các bài toán điển hình vào nội dung học tập, ví dụ: bài toán quản lý bản ghi sinh viên (SinhVien, NgayThang), bài toán tổ chức thư mục trên đĩa cứng dưới dạng cây, bài toán Tháp Hà Nội, Tháp Sài Gòn, bài toán xếp tiền (Selection Sort), bài toán chia bài (Insertion Sort).
• Hệ thống bài tập tự rèn luyện: Cuối mỗi chương đều có hệ thống câu hỏi lý thuyết và bài tập lập trình yêu cầu sinh viên tự thiết kế cấu trúc, cài đặt thuật toán xử lý danh sách liên kết quản lý bằng con trỏ đầu/cuối, tính toán các chỉ số của cây nhị phân (đếm nút lá, nút trung gian, tính chiều dài đường đi), và tối ưu hóa bộ nhớ khi chuyển đổi giữa cây và danh sách.
• Phương pháp đánh giá: Đánh giá năng lực người học thông qua 43 giờ thực hành trên máy và 2 bài kiểm tra định kỳ (ở Chương III và Chương VI). Tiêu chí đánh giá dựa trên tính đúng đắn của giải thuật, khả năng biên dịch mã nguồn không lỗi, và hiệu quả phân bổ bộ nhớ.
• Hướng dẫn tự học: Người học được yêu cầu vẽ sơ đồ khối, thực hiện chạy tay (trace code) từng bước với các bộ dữ liệu mẫu trước khi lập trình trên máy tính; phân tích tính tối ưu của từng cấu trúc dữ liệu tương ứng với từng yêu cầu bài toán.

---

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

• Chuẩn hóa theo chương trình khung giáo dục nghề nghiệp: Giáo trình được biên soạn và thẩm định theo Quyết định số 140/QĐ-TCTS năm 2022, đáp ứng chương trình khung đào tạo Trung cấp nghề và Cao đẳng nghề Công nghệ thông tin.
• Tính tường minh trong cài đặt thuật toán: Toàn bộ các giải thuật trọng tâm đều đi kèm nguyên mẫu hàm (prototype) và mã nguồn hoàn chỉnh bằng ngôn ngữ C, ví dụ hàm BubbleSort, InsertionSort, QuickSort, các hàm duyệt cây DuyetNLR, DuyetLNR, DuyetLRN, hàm chèn nút ChenNut, xóa nút XoaNut, tìm phần tử thế mạng TimNutTheMang.
• Minh họa phân tích toán học chính xác: Cung cấp phương pháp chứng minh quy nạp tính đúng đắn của thuật toán Prim và thuật toán Kruskal; lập bảng theo dõi 7 bước lặp chi tiết khi tìm cây khung nhỏ nhất trên đồ thị 8 đỉnh kèm ma trận trọng số.
• Gắn kết giữa cấu trúc dữ liệu và ứng dụng thực tế: Giáo trình tích hợp các ứng dụng tiêu biểu như cơ chế hàng đợi xoay vòng tránh tràn bộ nhớ, phương pháp đánh giá biểu thức Ba Lan bằng ngăn xếp, kỹ thuật nén dữ liệu Huffman và mô hình phân loại cây quyết định.

---

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

• Sinh viên và học viên: Giáo trình phục vụ trực tiếp cho học sinh, sinh viên theo học hệ Trung cấp và Cao đẳng ngành Công nghệ thông tin (chuyên ngành Ứng dụng phần mềm). Ngoài ra, tài liệu phù hợp cho người học các chuyên ngành kỹ thuật công nghệ cần củng cố kiến thức nền tảng về giải thuật.
• Yêu cầu tiên quyết (Prerequisites): Người học cần hoàn thành khối kiến thức chung, có hiểu biết về toán học rời rạc cơ bản và nắm vững kỹ thuật lập trình cơ bản bằng ngôn ngữ C hoặc Pascal (cú pháp, câu lệnh điều khiển, mảng, hàm và con trỏ).
• Đối với giảng viên: Tài liệu đóng vai trò là khung chương trình chuẩn để giảng dạy mô-đun MH10 thời lượng 60 giờ, làm căn cứ thiết kế giáo án lý thuyết, bài giảng thực hành phòng máy và xây dựng đề thi đánh giá kết thúc môn học.
• Nghiên cứu và tự học: Tài liệu cung cấp hệ thống phân loại danh mục cấu trúc dữ liệu và giải thuật cơ bản, hỗ trợ người tự học tra cứu mã nguồn mẫu và phương pháp tính toán độ phức tạp thuật toán.

---

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

1. Giáo trình này phù hợp với đối tượng nào? Tài liệu được thiết kế cho học sinh, sinh viên trình độ Trung cấp và Cao đẳng nghề Công nghệ thông tin (Ứng dụng phần mềm), đồng thời làm tài liệu tham khảo cho sinh viên các ngành kỹ thuật liên quan đến lập trình.

2. Cần chuẩn bị kiến thức nền tảng nào trước khi học? Người học cần hoàn thành các môn học chung, nắm vững kỹ năng lập trình căn bản trên ngôn ngữ C hoặc Pascal, bao gồm thao tác với biến, mảng, con trỏ, hàm và cấu trúc rẽ nhánh/lặp.

3. Điểm khác biệt của giáo trình này so với các tài liệu lý thuyết khác là gì? Giáo trình tập trung vào thực hành (chiếm 43/60 giờ), cung cấp đầy đủ mã nguồn C thực tế cho từng thao tác dữ liệu, kèm theo bảng mô phỏng từng bước lặp thay vì chỉ trình bày thuật toán dưới dạng lý thuyết thuần túy.

4. Phương pháp tự học giáo trình này như thế nào để đạt hiệu quả? Người học nên kết hợp đọc hiểu lý thuyết phân tích độ phức tạp, tự viết mã nguồn theo các prototype được cung cấp trong giáo trình, chạy thử nghiệm trên trình biên dịch và hoàn thành các bài tập nâng cao ở cuối mỗi chương.

5. Giáo trình có cung cấp các giải thuật tối ưu trên đồ thị không? Có. Chương V của giáo trình trình bày chi tiết hai thuật toán tìm cây khung nhỏ nhất là Kruskal và Prim, bao gồm cả chứng minh toán học, đánh giá độ phức tạp tính toán và bảng theo dõi từng bước lặp trên ma trận trọng số.

---

Kết luận

Giáo trình Cấu trúc dữ liệu và giải thuật (MH10) do Trường Trung cấp Trường Sơn Đắk Lắk ban hành là tài liệu học thuật chuẩn hóa, cung cấp hệ thống tri thức hoàn chỉnh từ phân tích độ phức tạp giải thuật, cấu trúc tuyến tính, cấu trúc phi tuyến đến các thuật toán sắp xếp và tìm kiếm.

Tiến trình học tập đề xuất cho người học bao gồm: tiếp cận phương pháp phân tích độ phức tạp Big-O và đệ quy (Chương I, II); làm chủ kỹ thuật tổ chức bộ nhớ trên Mảng, Danh sách liên kết, Stack, Queue (Chương III); mở rộng sang cấu trúc phi tuyến Cây và Đồ thị (Chương IV, V); và hoàn thiện kỹ năng tối ưu xử lý với Sắp xếp và Tìm kiếm (Chương VI). Tài liệu bổ trợ cần thiết bao gồm môi trường thực hành biên dịch ngôn ngữ C/Pascal và hệ thống bài tập lập trình mở rộng được nêu chi tiết trong toàn bộ giáo trình.

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

Sæ LAO ĐàNG, TH¯¡NG BINH VÀ Xà HàI ĐÂK LÂK TR¯âNG TRUNG CÂP TR¯âNG S¡N GIÁO TRÌNH MÔN HàC: CÂU TRÚC Dþ LIàU VÀ GIÀI THU¾T NGHÀ: CÔNG NGHà THÔNG TIN TRÌNH ĐÞ: TRUNG CÂP Ban hành kèm theo Quyết định số: 140/QĐ-TCTS ngày 02 tháng 8 năm 2022 của Hiệu trưởng Trường trung cấp Trường Sơn ĐÁk LÁk, năm 2022 TUYÊN Bà BÀN QUYÀN Tài liÉu này thuác lo¿i sách giáo trình nên các nguán thông tin có thÅ đ°āc phép dùng nguyên bÁn hoặc trích dùng cho các măc đích và đào t¿o và tham khÁo. Mãi măc đích khác mang tính lÉch l¿c hoặc sÿ dăng vãi măc đích kinh doanh thiÁu lành m¿nh s¿ bá nghiêm cÃm. ii LâI GIàI THIàU HiÉn nay, t¿i Tr°ång ch°a có giáo trình CÃu trúc dā liÉu & giÁi thuÁt. Đặc biÉt trên thá tr°ång không có tài liÉu hãc tÁp, tham khÁo phù hāp vãi ch°¢ng trình khung Cao đẳng nghÃ, trung cÃp nghà thuác nghà Công nghÉ thông tin (CNTT) trong quá trình đào t¿o nghà hiÉn nay.

Nhóm tác giÁ biên so¿n giáo trình lÁp trình c¢ bÁn nhằm măc đích giúp hãc sinh, sinh viên (HSSV) sÿ dăng giáo trình làm tài liÉu nghiên cću và hãc tÁp mát cách thuÁn tiÉn. Ch°¢ng trình môn hãc đ°āc sÿ dăng đÅ giÁng d¿y cho sinh viên trung cÃp nghà Công nghÉ thông tin (ćng dăng phần mÃm) và làm tài liÉu tham khÁo cho các nghà thuác các ngành nghà kỹ thuÁt. VÁy, rÃt mong đ°āc să góp ý cąa b¿n đãc đÅ tài liÉu này ngày càng đ°āc hoàn thiÉn h¢n, chúng tôi xin chân thành cÁm ¢n. Xin chân thành cÁm ¢n!.

ĐÃk LÃk, ngày 02 tháng 8 nm 2022 Tham gia biên so¿n 1. NguyÇn Nh° C°ång - Chą biên 2. NguyÇn Thá Nhung 3. L°u Thá Th°¢ng iii MĂC LĂC LäI GIâI THIÈU.

III GIÁO TRÌNH MÔN HâC. THIÀT KÀ VÀ PHÂN TÍCH GIÀI THUÀT. TĈ BÀI TOÁN ĐÀN CH¯¡NG TRÌNH:.1 Modul hóa viÉc giÁi quyÁt bài toán: .2 Ph°¢ng pháp tinh chßnh tĉng b°ãc. PHÂN TÍCH GIÀI THUÀT:.

Đà PHĆC T¾P TÍNH TOÁN CĄA GIÀI THUÀT .3 Xác đánh đá phćc t¿p tính toán cąa giÁi thuÁt:. 10 CH¯¡NG II. ĐÈ QUY VÀ GIÀI THUÀT ĐÈ QUY. KHÁI NIÈM ĐÈ QUY:.

GIÀI THUÀT ĐÈ QUY VÀ THĄ TĂC ĐÈ QUY. THIÀT KÀ GIÀI THUÀT ĐÈ QUY.1 Bài toán tính n! .3 Bài toán tháp Hà Nái:. 14 CH¯¡NG III. MÀNG VÀ DANH SÁCH.

CÂU TRÚC L¯U TRĀ CĄA MÀNG .2 Đánh nghĩa kiÅu cÃu trúc .3 Khai báo biÁn cÃu trúc. L¯U TRĀ KÀ TIÀP CĄA DANH SÁCH TUYÀN TÍNH .3 Khai báo biÁn kiÅu tÁp hāp:. 19 4 STACK HAY DANH SÁCH KIÄU NGN XÀP:. Khái niÉm - CÃu trúc dā liÉu: .2 L°u trā Stack bằng mÁng .3 Ćng dăng cąa ngn xÁp (BiÅu thćc hÁu tß - ký pháp Ba Lan) .2 L°u trā Queue bằng mÁng:.

23 CH¯¡NG IV. CÁC KHÁI NIÈM C¡ BÀN:. Đánh nghĩa cây:. Mát sß khái niÉm liên quan.

BiÅu diÇn cây. CÂY NHà PHÂN (BINARY TREE):. BiÅu diÇn cây nhá phân:. PHÉP DUYÈT CÂY NHà PHÂN: .1 DuyÉt theo thć tă tr°ãc NLR (Node – Left – Right) .2 DuyÉt theo thć tă giāa LNR (Left – Node – Right) .3 DuyÉt theo thć tă sau LRN (Left – Right – Node ).

CÂY NHà PHÂN TÌM KIÀM:. Tìm kiÁm trên cây nhá phân tìm kiÁm .Thêm phần tÿ mãi vào cây nhá phân tìm kiÁm.Xóa phần tÿ khåi cây nhá phân tìm kiÁm. Xóa toàn bá cây nhá phân. Đà THà VÀ MàT VÀI CÂU TRÚC PHI TUYÀN.

CÁC KHÁI NIÈM V Đà THà. BIÄU DIÆN Đà THà .1 BiÅu diÇn bằng ma trÁn lân cÁn: .2 BiÅu diÇn bằng danh sách lân cÁn. PHÉP DUYÈT MàT Đà THà .1 Tìm kiÁm theo chiÃu sâu: .2 Tìm kiÁm theo chiÃu ráng: .1 GiÁi thuÁt Kruskal .2 GiÁi thuÁt Prim: .CÂU HäI VÀ BÀI TÀP. 45 CH¯¡NG VI.

SÂP XÀP VÀ TÌM KIÀM. Mát sß ph°¢ng pháp sÃp xÁp .1 Khái quát và tìm kiÁm. CÂU HäI VÀ BÀI TÀP. 55 TÀI LIÈU THAM KHÀO.

57 vi GIÁO TRÌNH MÔN HâC Tên môn hác: CÂU TRÚC DĀ LIÈU VÀ GIÀI THUÀT Mã môn hác: MH10 Vß trí, tính chÃt, ý nghĩa và vai trò của mô đun: - Vá trí: Là môn hãc c¢ sç nghà trong ch°¢ng trình đào t¿o Trung cÃp nghà Công nghÉ thông tin (ćng dăng phần mÃm). Môn hãc này đ°āc hãc sau khßi môn hãc chung và tr°ãc các môn hãc, mô đun chuyên môn ngành, nghÃ. - Tính chÃt: Môn hãc cung cÃp nhāng kiÁn thćc c¢ bÁn và phân tích thiÁt kÁ và đánh giá đá phćc t¿p thuÁt toán và các kiÅu dā liÉu c¢ sç. cách cài đặt và các thao tác Các cÃu trúc dā liÉu trĉu t°āng, cÃu trúc dā liÉu cây nhá phân: cài đặt và các thao tác trên cây nhá phân.

Đáng thåi, cài đặt danh sách liên kÁt - ngn xÁp - hàng đāi, cài đặt cây nhá phân Cài đặt các thuÁt toán sÃp xÁp - tìm kiÁm và các thao tác liên quan. - Ý nghĩa và vai trò cąa mô đun: Mục tiêu của mô đun: - VÁ ki¿n thức: - Trình bày đ°āc mßi quan hÉ giāa cÃu trúc dā liÉu và giÁi thuÁt trong viÉc xây dăng ch°¢ng trình; - Trình bày đ°āc khái niÉm thåi gian thăc hiÉn giÁi thuÁt, đá phćc t¿p tính toán cąa giÁi thuÁt và các yÁu tß liên quan đÁn thåi gian thăc hiÉn giÁi thuÁt; - Trình bày đ°āc các khái niÉm và đÉ quy, giÁi thuÁt đÉ quy và thą tăc đÉ quy; - Trình bày đ°āc các khái niÉm, cÃu trúc l°u trā, phân lo¿i, cách duyÉt cây; - Trình bày đặc điÅm cąa các cách biÅu diÇn đá thá; - Trình bày đ°āc các phép duyÉt đá thá vãi các giÁi thuÁt minh hãa; - Trình bày đ°āc ý t°çng, thuÁt toán chi tiÁt cąa mát sß ph°¢ng pháp sÃp xÁp; - Trình bày đ°āc ý t°çng, thuÁt toán chi tiÁt cąa mát sß ph°¢ng pháp tìm kiÁm; - Trình bày đ°āc các khái niÉm và đÉ quy, giÁi thuÁt đÉ quy và thą tăc đÉ quy. - VÁ kỹ năng: - Xây dăng đ°āc låi giÁi mát bài toán: chia mát bài toán thành nhiÃu bài toán nhå đÅ giÁi sau đó phßi hāp, ghép các bài toán nhå l¿i vãi nhau đÅ đ°a và bài toán ban đầu; - Xác đánh, phân tích đ°āc trên mát sß ví dă và đÉ quy và giÁi thuÁt đÉ quy; - Cài đặt đ°āc mát sß thao tác xÿ lý danh sách liên kÁt, ngn xÁp, hàng đāi trên ngôn ngā C, Pascal; - BiÅu diÇn đ°āc cách biÅu diÇn cây nhá phân - Phân biÉt đ°āc các lo¿i đá thá: Đá thá đánh h°ãng, đá thá không đánh h°ãng, đánh h°ãng liên thông và đánh h°ãng không liên thông; - Phân biÉt đ°āc các phép tìm kiÁm theo chiÃu ráng và tìm kiÁm theo chiÃu sâu vãi các đá thá; 7 - Áp dăng mát sß thuÁt toán sÃp xÁp, tìm kiÁm vào thăc hiÉn viÉc sÃp xÁp và tìm kiÁm các dãy khóa că thÅ; - VÁ năng lực tự chủ và trách nhiám: - Xây dăng đ°āc låi giÁi mát bài toán: chia mát bài toán thành nhiÃu bài toán nhå đÅ giÁi sau đó phßi hāp, ghép các bài toán nhå l¿i vãi nhau đÅ đ°a và bài toán ban đầu; - Xác đánh, phân tích đ°āc trên mát sß ví dă và đÉ quy và giÁi thuÁt đÉ quy; - Cài đặt đ°āc mát sß thao tác xÿ lý danh sách liên kÁt, ngn xÁp, hàng đāi trên ngôn ngā C, Pascal; - BiÅu diÇn đ°āc cách biÅu diÇn cây nhá phân - Phân biÉt đ°āc các lo¿i đá thá: Đá thá đánh h°ãng, đá thá không đánh h°ãng, đánh h°ãng liên thông và đánh h°ãng không liên thông; - Phân biÉt đ°āc các phép tìm kiÁm theo chiÃu ráng và tìm kiÁm theo chiÃu sâu vãi các đá thá; - Áp dăng mát sß thuÁt toán sÃp xÁp, tìm kiÁm vào thăc hiÉn viÉc sÃp xÁp và tìm kiÁm các dãy khóa că thÅ. Nßi dung của môn hác: Thãi gian TT Tên ch°¢ng, mục Tång Lý Thực Kiểm sá thuy¿t hành, tra* 1 Ch°¢ng I.

ThiÁt kÁ và phân tích giÁi thuÁt 7 2 5 2 Ch°¢ng II. ĐÉ quy và giÁi thuÁt đÉ quy 5 2 3 3 Ch°¢ng III. MÁng và danh sách 8 2 5 1 4 Ch°¢ng IV. Cây 17 4 13 Ch°¢ng V.

Đá thá và mát vài cÃu trúc phi 5 8 2 6 tuyÁn 6 Ch°¢ng VI. SÃp xÁp và tìm kiÁm 15 3 11 1 TäNG CÞNG 60 15 43 2 8 CH¯¡NG I. THI¾T K¾ VÀ PHÂN TÍCH GIÀI THU¾T Giái thiáu: Mục tiêu: Học xong chương này, người học có khả năng: - Trình bày đ°āc khái niÉm giÁi thuÁt và ý nghĩa cąa giÁi thuÁt đÅ giÁi mát bài toán bằng ch°¢ng trình; - Trình bày đ°āc quy trình xây dăng låi giÁi mát bài toán; - Trình bày đ°āc khái niÉm thåi gian thăc hiÉn giÁi thuÁt, đá phćc t¿p tính toán cąa giÁi thuÁt và các yÁu tß liên quan đÁn thåi gian thăc hiÉn giÁi thuÁt; - Phân biÉt đ°āc các quy tÃc tổng, quy tÃc nhân khi xác đánh đá phćc t¿p cąa thuÁt toán; - Có thái đá nghiêm túc, cháu khó tìm tòi hãc håi; - Rèn luyÉn tính cẩn thÁn, tß mß, chính xác, sáng t¿o, linh ho¿t trong công viÉc. Từ bài toán đ¿n ch°¢ng trình: Có thÅ nói rằng không có mát ch°¢ng trình máy tính nào mà không có dā liÉu đÅ xÿ lý.

Dā liÉu có thÅ là dā liÉu đ°a vào (input data), dā liÉu trung gian hoặc dā liÉu đ°a ra (output data). Do vÁy, viÉc tổ chćc đÅ l°u trā dā liÉu phăc vă cho ch°¢ng trình có ý nghĩa rÃt quan trãng trong toàn bá hÉ thßng ch°¢ng trình. ViÉc xây dăng cÃu trúc dā liÉu quyÁt đánh rÃt lãn đÁn chÃt l°āng cũng nh° công sćc cąa ng°åi lÁp trình trong viÉc thiÁt kÁ, cài đặt ch°¢ng trình.1 Modul hóa viÉc giÁi quyÁt bài toán: Khái niÉm giÁi thuÁt hay thuÁt giÁi mà nhiÃu khi còn đ°āc gãi là thuÁt toán dùng đÅ chß ph°¢ng pháp hay cách thćc (method) đÅ giÁi quyÁt vần đÃ. GiÁi thuÁt có thÅ đ°āc minh hãa bằng ngôn ngā tă nhiên (natural language), bằng s¢ đá (flow chart) hoặc bằng mã giÁ (pseudo code).

Trong thăc tÁ, giÁi thuÁt th°ång đ°āc minh hãa hay thÅ hiÉn bằng mã giÁ tăa trên mát hay mát sß ngôn ngā lÁp trình nào đó (th°ång là ngôn ngā mà ng°åi lÁp trình chãn đÅ cài đặt thuÁt toán), chẳng h¿n nh° C, Pascal, ? 1.2 Ph°¢ng pháp tinh chßnh tĉng b°ãc Khi đã xác đánh đ°āc cÃu trúc dā liÉu thích hāp, ng°åi lÁp trình s¿ bÃt đầu tiÁn hành xây dăng thuÁt giÁi t°¢ng ćng theo yêu cầu cąa bài toán đặt ra trên c¢ sç cąa cÃu trúc dā liÉu đã đ°āc chãn. ĐÅ giÁi quyÁt mát vÃn đà có thÅ có nhiÃu ph°¢ng pháp, do vÁy să lăa chãn ph°¢ng pháp phù hāp là mát viÉc mà ng°åi lÁp trình phÁi cân nhÃc và tính toán.