Giáo Trình Cấu Trúc Dữ Liệu và Giải Thuật Ngành Công Nghệ Thông Tin Cao Đẳng

Giáo trình cấu trúc dữ liệu và giải thuật cung cấp kiến thức cần thiết cho sinh viên ngành công nghệ thông tin cao đẳng, giúp nâng cao kỹ năng lập trình.

• Người hướng dẫn: Trần Thái Mộc - Chủ Biên
• Trường học: Cao đẳng Xây dựng số 1
• 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 Cao Đẳng
• Loại tài liệu: giáo trình
• Năm xuất bản: 2021
• Địa điểm: Hà Nội

Mục lục chi tiết

• 1. CHƯƠNG 1: GIẢI THUẬT
• 1.1. Cấu trúc dữ liệu
• 1.2. Các đặc trưng của giải thuật
• 1.3. Dữ liệu vào
• 1.4. Dữ liệu ra
• 1.5. Tính hiệu quả
• 1.6. Tính chính xác
• 1.7. Tính ứng dụng
• 1.8. Ngôn ngữ diễn đạt
• 1.8.1. Ngôn ngữ thông thường
• 1.8.2. Lưu đồ
• 1.8.3. Ngôn ngữ lập trình
• 1.9. Phương pháp thiết kế giải thuật
• 1.9.1. Mô-đun hóa và việc giải quyết bài toán
• 1.9.2. Tinh chỉnh từng bước
• 1.10. Đánh giá độ phức tạp của giải thuật
• 1.10.1. Đặt vấn đề
• 1.10.2. Xác định độ phức tạp tính toán
• 2. CHƯƠNG 2: DANH SÁCH
• 2.1. Danh sách tuyến tính
• 2.2. Kiểu mảng
• 2.3. Kiểu ngăn xếp
• 2.4. Kiểu hàng đợi
• 3. CHƯƠNG 3: MÔ HÌNH CÂY VÀ ĐỒ THỊ
• 4. CHƯƠNG 4: CÁC GIẢI THUẬT SẮP XẾP VÀ TÌM KIẾM

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 Cao Đẳng

Giáo trình "Cấu trúc dữ liệu và giải thuật" là tài liệu quan trọng cho sinh viên ngành Công nghệ thông tin. Nó cung cấp kiến thức cơ bản về các kiểu cấu trúc dữ liệu và giải thuật, giúp sinh viên nắm vững các khái niệm cốt lõi. Nội dung giáo trình được chia thành 4 chương, mỗi chương tập trung vào một khía cạnh khác nhau của cấu trúc dữ liệu và giải thuật.

1.1. Mục tiêu và nội dung của giáo trình

Giáo trình nhằm cung cấp kiến thức về các kiểu cấu trúc dữ liệu thông dụng và giải thuật. Nội dung bao gồm các khái niệm cơ bản, ứng dụng thực tiễn và các bài tập thực hành.

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

Giáo trình được thiết kế cho sinh viên cao đẳng ngành Công nghệ thông tin, đặc biệt là những người học lập trình và phát triển phần mềm.

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 chỉ đơn thuần là việc ghi nhớ lý thuyết. Sinh viên thường gặp khó khăn trong việc áp dụng kiến thức vào thực tiễn. Các vấn đề như hiểu sai khái niệm, thiếu kỹ năng lập trình và không biết cách tối ưu hóa giải thuật là những thách thức lớn.

2.1. Khó khăn trong việc áp dụng lý thuyết vào thực tiễn

Nhiều sinh viên gặp khó khăn trong việc chuyển đổi lý thuyết thành mã lập trình thực tế. Điều này đòi hỏi sự thực hành thường xuyên và tư duy logic.

2.2. Thiếu kỹ năng lập trình cơ bản

Kỹ năng lập trình là yếu tố quan trọng để hiểu và áp dụng cấu trúc dữ liệu. Sinh viên cần nắm vững ngôn ngữ lập trình trước khi học sâu về giải thuật.

III. Phương pháp học hiệu quả Cấu Trúc Dữ Liệu và Giải Thuật

Để học tốt môn 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 hiệu quả. Việc kết hợp lý thuyết với thực hành, tham gia các dự án thực tế và làm bài tập thường xuyên sẽ giúp củng cố kiến thức.

3.1. Kết hợp lý thuyết và thực hành

Việc thực hành lập trình thường xuyên giúp sinh viên hiểu rõ hơn về các khái niệm lý thuyết. Thực hành trên các bài tập cụ thể sẽ giúp sinh viên ghi nhớ lâu hơn.

3.2. Tham gia dự án thực tế

Tham gia vào các dự án thực tế sẽ giúp sinh viên áp dụng kiến thức đã học vào thực tiễn, từ đó nâng cao kỹ năng lập trình và giải quyết vấn đề.

IV. Ứng dụng thực tiễn 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 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 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

Cấu trúc dữ liệu giúp tổ chức và quản lý dữ liệu hiệu quả trong các ứng dụng phần mềm, từ đó nâng cao hiệu suất và khả năng mở rộng.

4.2. Ứng dụng trong khoa học dữ liệu

Trong khoa học dữ liệu, việc sử dụng các giải thuật tối ưu giúp phân tích và xử lý dữ liệu lớn một cách hiệu quả, từ đó đưa ra các quyết định chính xác.

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 sẽ tiếp tục đóng vai trò quan trọng trong sự phát triển của công nghệ thông tin. Việc nắm vững kiến thức này không chỉ giúp sinh viên thành công trong học tập mà còn trong sự nghiệp sau này.

5.1. Tầm quan trọng của việc học Cấu Trúc Dữ Liệu

Nắm vững cấu trúc dữ liệu giúp sinh viên có nền tảng vững chắc để phát triển các kỹ năng lập trình và giải quyết vấn đề trong tương lai.

5.2. Xu hướng phát triển trong lĩnh vực này

Với sự phát triển nhanh chóng của công nghệ, các giải thuật và cấu trúc dữ liệu mới sẽ tiếp tục được nghiên cứu và phát triển, mở ra nhiều cơ hội cho sinh viên.

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 (Mã môn học: MH13) được biên soạn bởi chủ biên Trần Thị Mơ, ban hành theo Quyết định số 368ĐT/QĐ-CĐXD1 ngày 10 tháng 08 năm 2021 của Hiệu trưởng Trường Cao đẳng Xây dựng số 1. Tài liệu được thiết kế phục vụ công tác giảng dạy và học tập cho trình độ Cao đẳng chính quy ngành Công nghệ thông tin (chuyên ngành Ứng dụng phần mềm).

Trong chương trình đào tạo, Cấu trúc dữ liệu và giải thuật là môn học cơ sở ngành bắt buộc. Thời lượng môn học được xác định là 60 giờ, phân bổ cụ thể thành: 30 giờ lý thuyết; 27 giờ thực hành, thí nghiệm, thảo luận, bài tập; và 3 giờ kiểm tra định kỳ.

Mục tiêu đào tạo của giáo trình được xác lập trên ba phương diện:

• Kiến thức: Cung cấp các khái niệm nền tảng về giải thuật, phương pháp đánh giá độ phức tạp tính toán, các kiểu cấu trúc dữ liệu tuyến tính và phi tuyến tính thông dụng cùng các thuật toán thao tác tương ứng.
• Kỹ năng: Hình thành năng lực thiết kế, cài đặt các giải thuật tìm kiếm, sắp xếp; vận dụng linh hoạt cấu trúc dữ liệu để giải quyết các bài toán kỹ thuật lập trình thực tiễn.
• Năng lực tự chủ và trách nhiệm: Rèn luyện ý thức kỷ luật lao động, tư duy nghiên cứu chủ động, sáng tạo trong việc tổ chức và tối ưu hóa chương trình.

Cấu trúc giáo trình xây dựng trên mối quan hệ nền tảng: $\text{Cấu trúc dữ liệu} + \text{Giải thuật} = \text{Chương trình}$. Cách tiếp cận đi từ việc hình thành tư duy thuật toán, kỹ thuật biểu diễn và đánh giá độ phức tạp đến việc khảo sát chi tiết các cấu trúc dữ liệu cụ thể (danh sách, cây, đồ thị) và các thuật toán xử lý dữ liệu chuẩn tắc.

---

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

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

Nội dung giáo trình được cấu trúc thành 04 chương chính với tính liên kết logic chặt chẽ:

• Chương 1: Giải thuật (Trang 1 - 9): Cung cấp các khái niệm tổng quan về giải thuật; 8 đặc trưng tiêu chuẩn của giải thuật (tính xác định, tính khả thi, tính dừng, dữ liệu vào/Input, dữ liệu ra/Output, tính hiệu quả, tính chính xác, tính ứng dụng/hữu hạn); 3 phương pháp biểu diễn giải thuật (ngôn ngữ tự nhiên, sơ đồ khối/lưu đồ, mã giả và ngôn ngữ lập trình); phương pháp thiết kế giải thuật theo mô hình từ trên xuống (Top-down design), kỹ thuật tinh chỉnh từng bước; đánh giá độ phức tạp thuật toán thông qua ký hiệu $O$-lớn ($O(1)$, $O(\log n)$, $O(n)$, $O(P(n))$, $O(a^n)$).
• Chương 2: Danh sách (Trang 10 - 27): Trình bày tập hợp các cấu trúc dữ liệu tuyến tính gồm mảng một chiều, kiểu ngăn xếp (Stack hoạt động theo cơ chế LIFO - Last In First Out với các thao tác push, pop), kiểu hàng đợi (Queue hoạt động theo cơ chế FIFO - First In First Out với các thao tác put, get), và hệ thống danh sách liên kết (danh sách liên kết đơn - Singly Linked List, danh sách liên kết kép - Doubly Linked List, danh sách liên kết vòng - Circular Linked List). Chương cung cấp toàn bộ định nghĩa cấu trúc dữ liệu struct node, struct dNode, struct sList, struct dList và các hàm cài đặt bằng ngôn ngữ C++: createNode, insertHead, insertTail, insertAfter, processList, searchList, deleteList, List_Selection_Sort, List_Interchange_Sort.
• Chương 3: Mô hình cây và đồ thị (Trang 28 - 43): Khảo sát cấu trúc phi tuyến tính. Phần Cây phân tích quan hệ cha - con (parenthood), mô hình cây nhị phân, các tính chất toán học ($n \le 2^h - 1$, $n \ge h \ge \log_2(n+1)$) và 3 phương pháp duyệt cây (tiền thứ tự - NLR, trung thứ tự - LNR, hậu thứ tự - LRN). Phần Đồ thị định nghĩa đồ thị có hướng $G = \langle V, E \rangle$ (bậc trong, bậc ngoài), đồ thị vô hướng và đồ thị có trọng số; 2 phương pháp biểu diễn đồ thị (ma trận kề kích thước $n \times n$ và danh sách kề); 2 phương pháp duyệt đồ thị (duyệt theo chiều rộng - BFS sử dụng hàng đợi, duyệt theo chiều sâu - DFS sử dụng đệ quy và mảng đánh dấu daxet); thuật toán Dijkstra tìm đường đi ngắn nhất và giải thuật Kruskal tìm cây khung nhỏ nhất (MST) dựa trên phương pháp tham lam.
• Chương 4: Các giải thuật sắp xếp và tìm kiếm (Trang 64): Phân tích các thuật toán sắp xếp đổi chỗ trực tiếp, sắp xếp vun đống (Heap Sort); các thuật toán tìm kiếm tuần tự, tìm kiếm nhị phân và mô hình cấu trúc cây nhị phân tìm kiếm (Binary Search Tree - BST).

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

Giáo trình thiết lập hệ thống kiến thức nền tảng khoa học máy tính thông qua:

• Hệ thống lý thuyết cơ bản: Nguyên lý tổ chức dữ liệu tuyến tính và phi tuyến tính; bản chất của biến con trỏ và cơ chế cấp phát/giải phóng bộ nhớ động (new, delete) trong C++; lý thuyết đồ thị và cây.
• Các nguyên lý cốt lõi: Cơ chế lưu trữ và truy xuất theo thứ tự đảo ngược (LIFO) hoặc bảo toàn thứ tự (FIFO); nguyên lý thiết kế mô-đun hóa và chia nhỏ bài toán phức tạp thành các bài toán độc lập; nguyên tắc tối ưu hóa tài nguyên phần cứng (bộ nhớ trong và thời gian tính toán).
• Khung phân tích thuật toán: Quy chuẩn toán học về độ phức tạp thời gian và không gian $R(n)$ qua tiệm cận $O$-lớn, giúp định lượng tài nguyên xử lý trước khi cài đặt phần mềm.

Kỹ năng phát triển

• Kỹ năng kỹ thuật: Cài đặt mã nguồn hoàn chỉnh trên ngôn ngữ C/C++ cho các cấu trúc ngăn xếp, hàng đợi, danh sách liên kết đơn/kép/vòng; thực hiện các thao tác quản lý con trỏ head, tail, next, pre; cài đặt thuật toán duyệt đồ thị BFS, DFS và giải thuật Euclid, Dijkstra, Kruskal.
• Kỹ năng phân tích: Đánh giá ưu điểm và nhược điểm giữa cấu trúc mảng và danh sách liên kết; lựa chọn giữa ma trận kề và danh sách kề tùy theo mật độ cạnh của đồ thị; phân tích độ phức tạp thuật toán để chọn giải pháp tối ưu.
• Năng lực ứng dụng thực tiễn: Chuyển hóa các bài toán nghiệp vụ (quản lý danh sách sinh viên có tiêu chí lọc điểm $\text{ĐTB} \ge 5$, bài toán quản lý hồ sơ lương cán bộ, bài toán tính nghiệm phương trình bậc hai, bài toán chuyển đổi hệ cơ số 10 sang cơ số 2) thành các chương trình máy tính có cấu trúc dữ liệu phù hợp.

---

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

Giáo trình áp dụng cách tiếp cận sư phạm đi từ trừu tượng hóa mô hình đến thực thi chi tiết. Tiến trình bài học được thiết kế tuần tự: $$\text{Khái niệm lý thuyết} \longrightarrow \text{Mô hình hóa/Sơ đồ khối} \longrightarrow \text{Mã giả/C++} \longrightarrow \text{Phân tích độ phức tạp} \longrightarrow \text{Bài tập ứng dụng}$$

Về mặt thực hành và tình huống (case studies), giáo trình tích hợp các ví dụ minh họa gắn với bài toán cụ thể:

• Ví dụ về thuật toán Euclid tìm ước chung lớn nhất để giải thích tính dừng của thuật toán.
• Lưu đồ và mã giả giải phương trình bậc hai $ax^2 + bx + c = 0$ minh họa cho cấu trúc rẽ nhánh và các nút điều khiển trong sơ đồ khối.
• Bài toán quản lý hệ thống bảo trì hồ sơ lương cán bộ phục vụ minh họa phương pháp thiết kế từ trên xuống (Top-down design).
• Thuật toán sắp xếp dãy $n$ số nguyên theo thứ tự tăng dần minh họa cho kỹ thuật tinh chỉnh từng bước.
• Bài toán chuyển đổi số nguyên dương (ví dụ số 23) sang hệ nhị phân minh họa cơ chế hoạt động của Stack (LIFO).
• Bài toán quản lý danh sách sinh viên gồm các trường thông tin: mã SV, họ tên, năm sinh, điểm trung bình, yêu cầu thực hiện các thao tác chèn, xóa, sắp xếp theo điểm/mã SV, tìm kiếm và lọc dữ liệu.

Phương pháp đánh giá kết quả học tập được xác định qua cơ cấu 60 giờ đào tạo: đánh giá thường xuyên qua 27 giờ thực hành/thảo luận trên lớp, hệ thống câu hỏi lý thuyết và bài tập lập trình cuối mỗi chương, cùng 3 giờ dành riêng cho kiểm tra định kỳ. Đối với việc tự học, giáo trình cung cấp hệ thống câu hỏi ôn tập và bài tập lập trình có đáp án mã nguồn khung ở cuối các Chương 1, Chương 2 và Chương 3 để người học tự kiểm tra và củng cố kiến thức.

---

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

• Căn cứ pháp lý và chuẩn đào tạo mới: Giáo trình được ban hành năm 2021 theo Quyết định số 368ĐT/QĐ-CĐXD1 của Hiệu trưởng Trường Cao đẳng Xây dựng số 1, được biên soạn chuẩn hóa theo đề cương chi tiết học phần Cấu trúc dữ liệu và giải thuật (MH13) trình độ Cao đẳng Công nghệ thông tin.
• Phương pháp diễn đạt đa tầng: Tài liệu kết hợp đồng thời ba hình thức biểu diễn giải thuật: ngôn ngữ tự nhiên, sơ đồ khối chuẩn tắc (với quy ước rõ ràng về nút thao tác, nút điều khiển, nút khởi đầu/kết thúc, cung nối) và mã lập trình thực thi bằng C/C++.
• Mã nguồn cài đặt chi tiết: Các thao tác trên cấu trúc dữ liệu động (danh sách liên kết đơn, danh sách liên kết kép) được viết bằng mã C++ hoàn chỉnh, có xử lý tường minh các điều kiện biên: kiểm tra tràn bộ nhớ (if (p == NULL)), kiểm tra danh sách rỗng (l.head == NULL), thao tác giải phóng bộ nhớ động bằng lệnh delete, hạn chế tối đa việc sử dụng mã giả thuần túy.
• Mô phỏng từng bước các giải thuật kinh điển: Các giải thuật phức tạp như thuật toán tìm đường đi ngắn nhất Dijkstra và giải thuật tìm cây khung nhỏ nhất Kruskal được mô tả qua từng bước biến đổi trạng thái (bước loại bỏ vòng/cạnh song song, bước sắp xếp trọng số cạnh, bước kiểm tra chu trình và bổ sung từng cạnh vào cây khung nhỏ nhất MST).
• Gắn kết thực tế kỹ thuật: Các cấu trúc dữ liệu trừu tượng được đối sánh với các hiện tượng kỹ thuật và đời sống thực tế: cơ chế đảo chiều toa xe lửa/ngăn kéo tài liệu/hộp băng đạn đối với Stack; hàng đợi in ấn/dãy máy bay chờ trên đường băng đối với Queue; bản đồ giao thông liên tỉnh đối với đồ thị có trọng số; danh mục sách thư viện/danh bạ điện thoại đối với danh sách liên kết.

---

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

• Sinh viên chuyên ngành: Giáo trình được thiết kế trực tiếp cho sinh viên hệ Cao đẳng chính quy ngành Công nghệ thông tin (định hướng Ứng dụng phần mềm). Tài liệu được sử dụng trong giai đoạn học các môn cơ sở ngành (năm thứ nhất hoặc đầu năm thứ hai).
• Điều kiện tiên quyết (Prerequisites): Người học cần hoàn thành học phần Nhập môn lập trình/Kỹ thuật lập trình cơ bản, nắm vững cú pháp lập trình C/C++ hoặc Pascal cơ bản, các cấu trúc điều khiển (rẽ nhánh if-else, vòng lặp for, while), khái niệm mảng dữ liệu và kiểu bản ghi (struct/record).
• Giảng viên và công tác giảng dạy: Giảng viên sử dụng tài liệu làm khung bài giảng chuẩn cho học phần MH13 (60 giờ), làm căn cứ phân bổ nội dung giảng dạy lý thuyết (30 giờ), thiết kế giáo án thực hành phòng máy (27 giờ) và xây dựng ngân hàng đề kiểm tra/đánh giá (3 giờ).
• Tự học và tài liệu tham khảo: Tài liệu là nguồn tham khảo nền tảng cho lập trình viên muốn củng cố bản chất hoạt động của bộ nhớ máy tính, sinh viên các ngành kỹ thuật liên quan cần tài liệu tra cứu về các cấu trúc dữ liệu căn bản và các thuật toán tìm kiếm, sắp xếp, duyệt đồ thị.

---

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

1. Giáo trình này phù hợp với đối tượng người học nào?

Giáo trình phục vụ trực tiếp cho sinh viên trình độ Cao đẳng ngành Công nghệ thông tin (Ứng dụng phần mềm) theo học học phần Cấu trúc dữ liệu và giải thuật (MH13), đồng thời phù hợp cho người bắt đầu nghiên cứu về cấu trúc dữ liệu và giải thuật trong lập trình.

2. Người học cần chuẩn bị kiến thức nền tảng nào trước khi tiếp cận giáo trình?

Người học cần nắm vững kiến thức lập trình cơ sở bằng ngôn ngữ C/C++ hoặc Pascal, bao gồm các kiểu dữ liệu cơ bản, cấu trúc điều khiển rẽ nhánh, vòng lặp, kiểu cấu trúc (struct) và khái niệm cơ bản về con trỏ.

3. Giáo trình này có điểm khác biệt gì về mặt cấu trúc so với các tài liệu lý thuyết khác?

Giáo trình phân bổ thời lượng cân bằng giữa lý thuyết và thực hành (30 giờ lý thuyết, 27 giờ thực hành), tập trung vào các giải thuật thông dụng và cung cấp mã nguồn C++ có thể biên dịch trực tiếp, lược bỏ các chứng minh toán học phức tạp để ưu tiên khả năng cài đặt ứng dụng.

4. Phương pháp tự học giáo trình như thế nào để đạt hiệu quả cao nhất?

Người học nên tiếp cận theo trình tự: đọc hiểu định nghĩa giải thuật $\rightarrow$ vẽ lại sơ đồ khối/lưu đồ giải thuật $\rightarrow$ tự gõ và thực thi các đoạn mã C++ minh họa trong giáo trình $\rightarrow$ giải toàn bộ các câu hỏi lý thuyết và bài tập lập trình quản lý dữ liệu ở cuối mỗi chương.

5. Giáo trình cung cấp những dạng bài tập và tài liệu bổ trợ nào?

Giáo trình tích hợp hệ thống câu hỏi kiểm tra lý thuyết (so sánh ưu/nhược điểm các cấu trúc dữ liệu) và bài tập lập trình thực tế (bài toán quản lý hồ sơ sinh viên, biểu diễn cây nhị phân, vẽ ma trận kề, duyệt đồ thị theo BFS/DFS, áp dụng Dijkstra và Kruskal) ở cuối các chương 1, 2 và 3.

---

Kết luận

Giáo trình Cấu trúc dữ liệu và giải thuật (MH13) của Trường Cao đẳng Xây dựng số 1 là tài liệu học thuật cơ sở ngành, cung cấp toàn diện các kiến thức về giải thuật, cấu trúc dữ liệu tuyến tính (mảng, ngăn xếp, hàng đợi, danh sách liên kết), cấu trúc dữ liệu phi tuyến (cây, đồ thị) và các thuật toán xử lý dữ liệu chuẩn tắc.

Lộ trình học tập được thiết kế mạch lạc: bắt đầu từ phương pháp thiết kế và đánh giá độ phức tạp giải thuật (Chương 1), phát triển sang các cấu trúc dữ liệu tuyến tính (Chương 2), mở rộng lên các mô hình phi tuyến tính phức tạp cây và đồ thị (Chương 3), hoàn thiện bằng các giải thuật tìm kiếm và sắp xếp nâng cao (Chương 4).

Người học kết hợp nội dung giáo trình với môi trường thực hành lập trình C++ để rèn luyện kỹ năng cài đặt thuật toán, đáp ứng chuẩn đầu ra của chương trình đào tạo Cao đẳng Công nghệ thông tin.

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

Chương 1: Giải thuật Chương 2: Danh sách Chương 3: Mô hình cây và đồ thị Chương 4: Các giải thuật sắp xếp và tìm kiếm Mặc dù có nhiều cố gắng, nhưng trong quá trình biên soạn, biên tập và in ấn khó tránh khỏi những thiếu sót. Chúng tôi rất mong nhận được sự đóng góp ý kiến từ phía các thầy cô và bạn đọc để hoàn thiện giáo trình hơn! Xin trân trọng cảm ơn! Hà Nội, ngày……tháng……năm……… Tham gia biên so¿n Trần Thá M¢ - Chủ biên v Tên môn hác: CÄU TRÚC Dþ LIàU VÀ GIÀI THU¾T Mã môn hác: MH13 Thßi gian thāc hián môn hác: 60 giß; (Lý thuyÁt: 30 giß; Thāc hành, thí nghiệm, thÁo luÁn, bài tÁp: 27giß; Kiểm tra:3 giß) I. Vß trí, tính chÃt của môn hác: - Vá trí: Môn Cấu trúc dÿ liệu và giÁi thuÁt là môn học bÃt buác thuác nhóm các môn học, mô đun đào t¿o ngành Công nghệ thông tin. - Tính chất: Môn Cấu trúc dÿ liệu đ°ợc ứng dụng ráng rãi trong các lĩnh vāc tin học, góp phần nâng cao chất l°ợng đào t¿o nghề và phát triển nguán nhân lāc trong giai đo¿n mới.

Mÿc tiêu môn hác: - Về kiÁn thức: Các khái niệm c¢ bÁn về giÁi thuÁt, đánh giá đá phức t¿p của giÁi thuÁt. Các kiểu cấu trúc dÿ liệu thông dụng và mát sß giÁi thuÁt trên các kiểu cấu trúc dÿ liệu đó. - Về kỹ năng: ThiÁt kÁ đ°ợc mát sß giÁi thuÁt sÃp xÁp , tìm kiÁm. VÁn dụng các kiểu cấu trúc dÿ liệu thông dụng và các giÁi thuÁt để giÁi mát sß bài toán thāc tiễn.

- Về năng lāc tā chủ và trách nhiệm: Tích cāc nghiên cứu nhÿng kiÁn thức về cấu trúc dÿ liệu, giÁi thuÁt. Rèn luyện ý thức chấp hành kỷ luÁt lao đáng, phát huy tinh thần chủ đáng nghiên cứu, học hỏi, sáng t¿o trong học tÁp và làm việc. vi CH¯¡NG 1: GIÀI THU¾T Mÿc tiêu bài hác 1. Cung cấp cho ng°ßi học các kiÁn thức c¢ bÁn về c¢ bÁn về giÁi thuÁt: các đặc tr°ng giÁi thuÁt, ngôn ngÿ diễn đ¿t giÁi thuÁt, ph°¢ng pháp thiÁt kÁ giÁi thuÁt, đánh giá đá phức t¿p của giÁi thuÁt trong mát sß bài toán cụ thể.

CH¯¡NG 1: GIÀI THU¾T 1. GiÁi thu¿t 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, ? 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. Sā lāa chọn này cũng có thể góp phần đáng kể trong việc giÁm bớt công việc của ng°ßi lÁp trình trong phần cài đặt thuÁt toán trên mát ngôn ngÿ cụ thể. CÃu trúc dÿ liáu Mßi quan hệ giÿa cấu trúc dÿ liệu và GiÁi thuÁt có thể minh họa b¿ng đÁng thức: Cấu trúc dÿ liệu + GiÁi thuÁt = Ch°¢ng trình. Nh° vÁy, khi đã có cấu trúc dÿ liệu tßt, nÃm vÿng giÁi thuÁt thāc hiện thì việc thể hiện ch°¢ng trình b¿ng mát ngôn ngÿ cụ thể chß là vấn đề thßi gian.

Khi có cấu trúc dÿ liệu mà ch°a tìm ra thuÁt giÁi thì không thể có ch°¢ng trình và ng°ợc l¿i không thể có ThuÁt giÁi khi ch°a có cấu trúc dÿ liệu. Mát ch°¢ng trình máy tính chß có thể đ°ợc hoàn thiện khi có đầy đủ cÁ Cấu trúc dÿ liệu để l°u trÿ dÿ liệu và GiÁi thuÁt xử lý dÿ liệu theo yêu cầu của bài toán đặt ra. Để đánh giá mát cấu trúc dÿ liệu chúng ta th°ßng dāa vào mát sß tiêu chí sau: - Cấu trúc dÿ liệu phÁi tiÁt kiệm tài nguyên (bá nhớ trong) - Cấu trúc dÿ liệu phÁi phÁn Ánh đúng thāc tÁ của bài toán - Cấu trúc dÿ liệu phÁi dễ dàng trong việc thao tác dÿ liệu. Các đặc tr°ng của giÁi thu¿t - Tính xác định: Mßi b°ớc của thuÁt giÁi cần phÁi đ°ợc mô tÁ mát cách chính xác, chß có mát cách hiểu duy nhất.

Bái vì, nÁu mát b°ớc có thể hiểu theo nhiều cách khác nhau, thì cùng mát dÿ liệu vào, nhÿng ng°ßi thāc hiện thuÁt giÁi khác nhau có thể cho ra kÁt quÁ khác nhau. NÁu ta mô tÁ thuÁt giÁi b¿ng ngôn ngÿ tā nhiên, không có gì đÁm bÁo ng°ßi đọc hiểu đúng ý của ng°ßi viÁt thuÁt giÁi, bái ngôn ngÿ tā nhiên th°ßng là đa nghĩa. Để đÁm bÁo đòi hỏi này, thuÁt giÁi cần đ°ợc mô tÁ trong mát ngôn ngÿ lÁp trình, chÁng h¿n mát ngôn ngÿ lÁp trình (Pascal, C. trong các ngôn ngÿ này, các mệnh đề đ°ợc t¿o thành theo các qui tÃc cú pháp nghiêm nghặt và chß có mát ý nghĩa duy nhất.

- Tính khả thi: Tất cÁ các phép giÁi có mặt trong các b°ớc của thuÁt giÁi phÁi đủ đ¢n giÁn. Điều đó có nghĩa là các phép giÁi phÁi sao cho, ít nhất về nguyên tÃc có thể 2 thāc hiện đ°ợc bái con ng°ßi trong mát khoÁng thßi gian hÿu h¿n. ChÁng h¿n trong thuÁt giÁi Euclid, ta chß cần thāc hiện các phép chia các sß nguyên, các phép gán và các phép so sánh. - Tính dừng: Với mọi bá dÿ liệu vào thoÁ mãn điều kiện qui đánh, thuÁt giÁi phÁi dừng l¿i sau mát sß hÿu h¿n b°ớc thāc hiện.

ChÁng h¿n đßi với thuÁt giÁi Euclid là thuÁt giÁi thoÁ mãn điều kiện này. Bái vì sß d° r luôn nhỏ h¢n n, nÁu r0 thì giá trá của n á b°ớc sau là giá trá của r á b°ớc tr°ớc, ta có n>r=n1>r1=n2>r2.Dãy sß nguyên d°¢ng giÁm dần cần phÁi kÁt thúc á 0, do đó sau mát sß b°ớc giá trá của r=0 thuÁt giÁi dừng. Dÿ liáu vào - Input: Mßi thuÁt giÁi cần có mát sß (có thể b¿ng không) dÿ liệu vào. Đó là giá trá cần đ°a vào khi thuÁt giÁi bÃt đầu làm việc.

Dÿ liáu ra - Output: Mßi thuÁt giÁi cần có mát hoặc nhiều dÿ liệu ra. Đó là các giá trá có quan hệ xác đánh với giá trá vào và là kÁt quÁ của sā thāc hiện thuÁt giÁi. 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 chính xác 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. Tính ứng dụng 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ā. Tính hÿu h¿n Các giÁi thuÁt phÁi kÁt thúc sau mát sß hÿu h¿n các b°ớc. Ngôn ngÿ dißn đ¿t 1.

Ngôn ngÿ thông thường Trong cách biểu diễn thuÁt giÁi theo ngôn ngÿ tā nhiên, ng°ßi ta sử dụng ngôn ngÿ th°ßng ngày để liệt kê các b°ớc của thuÁt giÁi (Các ví dụ về thuÁt giÁi trong mục 1 của ch°¢ng sử dụng ngôn ngÿ tā nhiên). Ph°¢ng pháp biểu diễn này không yêu cầu ng°ßi viÁt thuÁt giÁi cũng nh° ng°ßi đọc thuÁt giÁi phÁi nÃm các quy tÃc. Tuy vÁy, cách biểu diễn này th°ßng dài dòng, không thể hiện rõ cấu trúc của thuÁt giÁi, đôi lúc gây hiểu lầm hoặc khó hiểu cho ng°ßi đọc. Gần nh° không có mát quy tÃc cß đánh nào trong việc thể hiện thuÁt giÁi b¿ng ngôn ngÿ tā nhiên 1.

Lưu đồ L°u đá hay s¢ đá khßi là mát công cụ trāc quan để diễn đ¿t các thuÁt giÁi. Biểu diễn thuÁt giÁi b¿ng l°u đá s¿ giúp ng°ßi đọc theo dõi đ°ợc sā phân cấp các tr°ßng hợp và quá trình xử lý của thuÁt giÁi. Ph°¢ng pháp l°u đá th°ßng đ°ợc dùng trong nhÿng thuÁt giÁi có tính rÃc rßi, khó theo dõi đ°ợc quá trình xử lý. 3 Các nút biểu diễn giải thuật bằng sơ đồ khối: Nút thao tác Nút điều khiển: trong đó ghi điều kiện cần kiểm tra trong quá trình tính toán.

Nút khái đầu, kÁt thúc Cung V¿ l°u đá hoặc s¢ đá khßi, mßi khßi mô tÁ mát b°ớc. Sử dụng mũi tên nßi khßi này với khßi kia để chß trình tā thāc hiện các b°ớc. Để dễ dàng nhÁn biÁt chức năng của từng khßi, mßi khßi đ°ợc thể hiện á mát d¿ng nh° sau: Ví dụ: Tìm nghiệm thāc của ph°¢ng trình bÁc hai ax2+bx+c=0. ThuÁt toán gám các b°ớc sau: + NhÁp dÿ liệu a, b, c.

+ Tính biệt sß  = b2-4ac. + So sánh  với 0. B°ớc tiÁp theo s¿ phụ thuác vào giá trá của . + NÁu <0, đáp sß của bài toán là <Vô nghiệm=.

+ NÁu =0, tính và ghi đáp sß trá của nghiệm kép. + NÁu >0, tính và ghi đáp sß trá của hai nghiệm phân biệt:. L°u đá biểu diễn thuÁt toán này đ°ợc thể hiện nh° sau: 4 1. Ngôn ngÿ l¿p trình Tuy s¢ đá khßi thể hiện rõ quá trình xử lý và sā phân cấp các tr°ßng hợp của thuÁt toán nh°ng l¿i cáng kềnh.

Để mô tÁ mát thuÁt toán nhỏ ta phÁi dùng mát không gian rất lớn. Đôi khi, ta có thể thể hiện thuÁt toán b¿ng ngôn ngÿ lÁp trình nào đó. Mọi ngôn ngÿ lÁp trình đều có nhÿng thao tác c¢ bÁn là xử lý, r¿ nhánh và lặp. Nh° vÁy, có thể tÁn dụng đ°ợc các khái niệm trong ngôn ngÿ lÁp trình, vừa giúp ng°ßi cài đặt dễ dàng hiểu chính xác thuÁt toán.

Mát khi đã vay m°ợn cú pháp và khái niệm của ngôn ngÿ lÁp trình thì chÃc chÃn mã giÁ s¿ bá phụ thuác vào ngôn ngÿ lÁp trình đó. Mát đo¿n mã giÁ của thuÁt toán giÁi ph°¢ng trình bÁc hai: if Delta > 0 then begin end else if delta = 0 then xuất kết quả : phương trình có nghiệm kép là -b/(2*a) else {trường hợp delta < 0 } xuất kết quả : phương trình vô nghiệm x1=(-b+sqrt(delta))/(2*a) x2=(-b-sqrt(delta))/(2*a) 5 xuất kết quả : phương trình có hai nghiệm là x1 và x2 1. Ph°¢ng pháp thi¿t k¿ giÁi thu¿t 1. Mô-đun hóa và viác giÁi quyết bài toán Các bài toán giÁi trên máy tính càng ngày càng đa d¿ng và phong phú d¿n tới quy mô ch°¢ng trình ngày càng lớn.

Quy mô càng lớn d¿n tới việc lÁp và kiểm soát ch°¢ng tình càng gặp nhiều khó khăn h¢n.