Giáo trình cấu trúc dữ liệu và giải thuật ngành CNTT trung cấp - CĐXD số 1

Giáo trình cấu trúc dữ liệu và giải thuật cho ngành công nghệ thông tin trung cấp. Nắm vững kiến thức cơ bản, thuật toán thông dụng, ứng dụng thực tế.

• Tác giả: Trần Thị M¢
• Trường học: Trường cao đẳng xây dựng số 1
• Chuyên ngành: Công nghệ thông tin (ứng dụng phần mềm)
• Đề 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: 2023
• Địa điểm: Hà Nội

Mục lục chi tiết

• Lời nói đầu
• 1. CHƯƠNG 1: GIẢI THUẬT
• 1.1. Các khái niệm về giải thuật
• 1.2. Các đặc trưng của giải thuật
• 1.3. Tính hiệu quả. Tính chính xác
• 1.4. Tính ứng dụng
• 1.5. Ngôn ngữ diễn đạt giải thuật
• 1.6. Ngôn ngữ thông thường
• 1.7. Ngôn ngữ lập trình
• 1.8. Phương pháp thiết kế giải thuật
• 1.9. Tinh chỉnh từng bước
• 2. CHƯƠNG 2: CÂU TRÚC DỮ LIỆU
• 2.1. Danh sách tuyến tính
• 2.2. Danh sách liên kết
• 2.3. Danh sách liên kết đơn
• 2.4. Các dạng khác của danh sách liên kết
• 2.5. Cây nhị phân
• 2.6. Biểu diễn cây nhị phân
• 2.7. Duyệt cây nhị phân
• 2.8. Cây nhị phân tìm kiếm
• 2.9. Duyệt đồ thị theo chiều rộng
• 2.10. Duyệt theo chiều sâu

Tóm tắt

I. Tổng quan Cấu trúc dữ liệu và giải thuật trung cấp DSA CNTT 55 ký tự

Giáo trình Cấu trúc dữ liệu và giải thuật (CTDL&GT) được biên soạn nhằm phục vụ cho giảng dạy và học tập trình độ trung cấp ngành Công nghệ thông tin (Ứng dụng phần mềm). Môn học này cung cấp kiến thức cơ bản về các kiểu cấu trúc dữ liệu cơ bản thông dụng và một số giải thuật cơ bản trên các kiểu cấu trúc dữ liệu đó. Nội dung giáo trình gồm 2 chương: Giải thuật và Cấu trúc dữ liệu. Mục tiêu là cung cấp cho người học các khái niệm về giải thuật, các đặc trưng của 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 và đánh giá độ phức tạp của giải thuật trong một số bài toán cụ thể. CTDL&GT quan trọng trong ngành CNTT, là nền tảng để xây dựng các chương trình hiệu quả. Giáo trình này sẽ trình bày những kiến thức quan trọng liên quan đến CTDL&GT một cách chi tiết và dễ hiểu nhất cho người học.

1.1. Định nghĩa và tầm quan trọng của CTDL GT trong CNTT

Khái niệm CTDL&GT hay thuật giải 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, bằng sơ đồ hoặc bằng mã giả. Trong thực tế, giải thuật thường được minh họa hay thể hiện bằng mã giả dựa trên một hay một số ngôn ngữ lập trình nào đó, chẳng hạn như C, Pascal. CTDL&GT là môn học cơ sở ngành, cung cấp kiến thức cơ bản về các khái niệm, 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 đó. Mối quan hệ giữa CTDL&GT 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. 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.

1.2. Mối liên hệ giữa Data Structures and Algorithms DSA và lập trình

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, người 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), phản ánh đúng thực tế của bài toán, dễ dàng trong việc thao tác dữ liệu. 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.

II. Cách nhận diện và giải quyết bài toán CTDL GT phức tạp 58 ký tự

Việc lựa chọn phương pháp phù hợp có thể 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ác đặc trưng của giải thuật bao gồm tính xác định, tính khả thi, tính dừng. 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. 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. Với mọi bộ dữ liệu vào thỏa 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.

2.1. Phân tích độ phức tạp thuật toán Big O Notation trong bài toán

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. 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. 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ự.

2.2. Các yếu tố ảnh hưởng đến hiệu suất của giải thuật cơ bản

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. 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.

2.3. Thiết kế thuật toán hiệu quả bằng phương pháp chia để trị

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ý. 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 đó.

III. Hướng dẫn sử dụng mảng danh sách liên kết và ứng dụng 60 ký tự

Danh sách là tập hợp các phần tử dữ liệu có cùng kiểu được cấu trúc, sắp xếp (logic) theo một trật tự tuyến tính. Như vậy, danh sách tuyến tính là một chuỗi các phần tử, tồn tại phần tử đầu và phần tử cuối, mỗi phần tử có phần tử trước và phần tử sau. Các thao tác thường sử dụng nhất là thêm phần tử và xóa phần tử.

3.1. Ưu điểm và nhược điểm của Mảng Arrays trong lưu trữ dữ liệu

Ưu điểm của mảng là tìm kiếm dễ dàng (tuần tự hoặc tìm kiếm nhị phân), truy cập nhanh (ngẫu nhiên, thời gian truy cập đến mọi phần tử là như nhau), duyệt các phần tử dễ dàng sử dụng chỉ số. Nhược điểm là thêm và xóa không dễ dàng, danh sách thường xuyên thêm bớt phần tử => Không biết trước số phần tử, tốn bộ nhớ vì phải cấp phát nhiều hơn cần thiết để giữ chỗ. Thêm một phần tử thứ i vào mảng: Chuyển các phần tử từ I đến n xuống các vị trí từ i+1 đến n+1; Thêm phần tử cần thêm vào vị trí thứ i.

3.2. Ứng dụng thực tế của Danh sách liên kết Linked Lists và các dạng

Danh sách liên kết (Linked List) là một cấu trúc dữ liệu tuyến tính, bao gồm một chuỗi các node kết nối với nhau. Mỗi node có thể xem như một phần tử trong danh sách. Mỗi node sẽ lưu trữ dữ liệu (data) của node đó và địa chỉ (address) của node kế tiếp. Danh sách liên kết phải có node bắt đầu, được gọi là HEAD. Node cuối cùng được gọi là TAIL. Mỗi node có nhiều nhất 1 phần tử đứng trước cũng như có nhiều nhất 1 phần tử đứng sau. Có nhiều trường hợp trong thực tế có thể được lưu trữ bằng cách sử dụng Linked List như: danh sách học sinh, danh mục sách trong thư viện, danh bạ điện thoại, danh sách các nhân viên trong công ty.

3.3. So sánh hiệu năng giữa CTDL GT sử dụng mảng và danh sách liên kết

Danh sách liên kết đơn (singly linked list) có đặc điểm là mỗi node (phần tử) chỉ liên kết với node đứng sau nó trong danh sách. Mỗi node trong danh sách liên kết gồm 2 phần: Phần dữ liệu (data) dùng để lưu nội dung của node. Phần địa chỉ liên kết (address), thường ký hiệu là next, là các con trỏ có cùng kiểu với node. Các con trỏ này lưu trữ địa chỉ của node kế tiếp trong danh sách. Nếu là node cuối cùng thì con trỏ trỏ đến NULL. Có thể sử dụng kiểu dữ liệu cấu trúc (struct) để xây dựng một node.

IV. Bí quyết làm chủ ngăn xếp hàng đợi cây và đồ thị CNTT 59 ký tự

Ngăn xếp (stack) là một cấu trúc dữ liệu tuyến tính, hoạt động theo cơ chế LIFO (Last In First Out), tạm dịch là <vào sau ra trước=. Có nghĩa là phần tử nào được thêm vào sau trong stack thì sẽ được lấy ra trước. Hàng đợi (queue) là một mô hình mà tác động bổ sung vào nó được thực hiện ở một phía của nó và tác động loại bỏ một phần tử được thực hiện ở phía còn lại. Ta hình dung hàng đợi như một dãy người xếp hàng tại một quầy hàng để mua một mặt hàng nào đó mà chỉ có thể thêm vào hàng đợi từ cuối và bớt đi phần tử ở đầu của hàng đợi.

4.1. Ngăn xếp Stacks Cơ chế hoạt động LIFO và ứng dụng thực tế

Một ngăn xếp (stack) là một mô hình (cơ cấu) mà các tác động vào nó chỉ được thực hiện tại một phía của nó. Phía này được gọi là đỉnh của ngăn xếp. Trong tin học, một ngăn xếp là là một danh sách tuyến tính mà các tác động vào nó chỉ được thực hiện tại một phía của nó. Với kiểu ngăn xếp, ta chỉ có thể thực hiện các thao tác sau: Khởi tạo một ngăn xếp, đẩy (push) một phần tử mới vào ngăn xếp nếu ngăn xếp chưa đầy, lấy (pop) một phần tử ra khỏi ngăn xếp nếu ngăn xếp khác rỗng, kiểm tra xem ngăn xếp có hay không có phần tử (rỗng hay không), kiểm tra xem ngăn xếp đã đầy hay chưa.

4.2. Hàng đợi Queues Cơ chế FIFO và ứng dụng trong xử lý tác vụ

Trong tin học, một hàng đợi là một danh sách tuyến tính mà thao tác bổ sung chỉ được thực hiện ở một đầu và thao tác bớt đi được thực hiện ở phía còn lại của nó. Với kiểu hàng đợi, ta quy ước chỉ có thể thực hiện các thao tác sau: Khởi tạo một hàng đợi, đặt (put) một phần tử mới vào hàng đợi nếu hàng đợi chưa đầy, nhận lại (get) một phần tử từ hàng đợi nếu hàng đợi khác rỗng, kiểm tra xem hàng đợi có hay không có phần tử (rỗng hay không), kiểm tra xem hàng đợi đã đầy hay chưa. Vì vậy, khi nói đến hàng đợi ta hiểu đó là danh sách kiểu FIFO.

4.3. Khám phá cấu trúc Cây Trees và Đồ thị Graphs trong CNTT

Cây nhị phân là cây rỗng hoặc là cây mà mỗi nút có tối đa hai nút con. Hơn nữa các nút con của cây được phân biệt thứ tự rõ ràng, một nút con gọi là nút con trái và một nút con gọi là nút con phải. Ta qui ước vẽ nút con trái bên trái nút cha và nút con phải bên phải nút cha, mỗi nút con được nối với nút cha của nó bởi một đoạn thẳng. Đồ thị có hướng G = <V,E> bao gồm: V là một tập hữu hạn các đỉnh, E là một tập hữu hạn, có thứ tự các cặp đỉnh của V, gọi là cạnh.

V. Phương pháp sắp xếp và tìm kiếm dữ liệu hiệu quả 57 ký tự

Trong trường hợp số bản ghi cần tìm rất lớn, việc tìm kiếm tuần tự có thể là một giải pháp không hiệu quả về mặt thời gian. Một giải pháp tìm kiếm khác hiệu quả hơn có thể được sử dụng dựa trên mô hình <chia để trị<. Cây nhị phân tìm kiếm là một phương pháp tìm kiếm rất hiệu quả và được xem như là một trong những thuật toán cơ sở của khoa học máy tính.

5.1. Các thuật toán Sắp xếp Sorting phổ biến và độ phức tạp

Để làm được điều này, tập các phần tử cần phải được sắp, và sử dụng chỉ số của mảng để xác định nửa cần tìm. Đầu tiên, so sánh giá trị cần tìm với giá trị của phần tử ở giữa. Nếu nó nhỏ hơn, tiến hành tìm ở nửa đầu dãy, ngược lại, tiến hành tìm ở nửa sau của dãy. Quá trình được lặp lại tương tự cho nửa dãy vừa được xác định này. Trong thủ tục này, x là giá trị cần tìm trong dãy a. Hai biến left và right dùng để giới hạn phân đoạn của mảng mà quá trình tìm kiếm sẽ được thực hiện trong mỗi bước.

5.2. Tìm kiếm Searching nhị phân và ứng dụng trong CTDL GT

Để chèn 1 phần tử vào cây nhị phân tìm kiếm, đầu tiên tiến hành quá trình tìm kiếm nút cần chèn trong cây theo các bước như đã nói ở trên. Nếu tìm thấy nút trong cây, có nghĩa là cây đã tồn tại một nút có khóa bằng nút cần chèn và việc chèn thêm nút này vào cây là không hợp lệ. Nếu không tìm thấy nút trong cây thì quá trình tìm kiếm kết thúc không thành công và ta tiến hành chèn nút vào điểm kết thúc của quá trình tìm kiếm.

5.3. Đệ quy Recursion trong thiết kế giải thuật tìm kiếm và sắp xếp

Để xóa một nút khỏi cây nhị phân, ta xét các trường hợp sau: Xóa 1 nút lá: Thao tác xóa 1 nút không có nút con nào là trường hợp đơn giản nhất. Chỉ cần tiến hành loại bỏ nút ra khỏi cây. Xóa nút có 1 nút con: Tiến hành loại bỏ nút khỏi cây và thay nó bằng nút con. Xóa nút có 2 nút con: Tiến hành loại bỏ nút và thay thế nó bằng nút con ngoài cùng bên trái của cây con bên phải hoặc nút con ngoài cùng bên phải của cây con bên trái.

VI. Ứng dụng và tương lai của CTDL GT trong phát triển phần mềm 60 ký tự

Quá trình duyệt theo chiều rộng cũng bắt đầu từ một đỉnh nào đó của đồ thị. Tiếp đến, các đỉnh kề của nó sẽ được thăm, rồi tiếp tục đến các đỉnh kề của các đỉnh vừa thăm. Như vậy, quá trình duyệt theo chiều rộng không duyệt theo từng nhánh của đồ thị mà duyệt theo độ sâu của các đỉnh so với đỉnh ban đầu. Quá trình duyệt theo chiều sâu bắt đầu từ một đỉnh nào đó của đồ thị. Sau khi thăm đỉnh này, quá trình duyệt theo chiều sâu được lặp lại với tất cả các đỉnh kề của nó.

6.1. Ứng dụng của cấu trúc dữ liệu và giải thuật trong lập trình game

Để kiểm tra việc duyệt mỗi đỉnh đúng 1 lần, chúng ta sử dụng một mảng daxet gồm n phần tử (tương ứng với n đỉnh). Nếu đỉnh thứ i đã được duyệt, daxet[i]=1, ngược lại daxet[i]=0. Thuật toán tìm kiếm theo chiều sâu bắt đầu từ đỉnh v nào đó sẽ duyệt tất cả các đỉnh liên thông với v. Thủ tục DeepFirstSearch sẽ thăm tất cả các đỉnh cùng thành phần liên thông với v mỗi đỉnh đúng một lần.

6.2. Tầm quan trọng của CTDL GT trong phát triển ứng dụng di động

Với trình tự duyệt như trên, quá trình duyệt sẽ duyệt hết một nhánh của đồ thị rồi mới sanh nhánh khác. Do vậy, phương pháp duyệt này được gọi là duyệt theo chiều sâu.Ví dụ, với đồ thị ở trên, quá trình duyệt theo chiều sâu là bắt đầu từ đỉnh a sẽ cho thứ tự duyệt như sau: Sau khi thăm đỉnh a, tiến hành thăm đỉnh kề với a là b. Tiếp theo thăm đỉnh kề b là d. Đỉnh d không kề đỉnh nào, do vậy quay lại bước trước. Đỉnh b chỉ có 1 đỉnh kề là d đã thăm, do vậy quay trở lại bước trước.

Nội dung chính

TỔNG QUAN HỌC THUẬT: GIÁO TRÌNH CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT (MÃ MÔN HỌC: MH10)

---

Tổng quan về giáo trình (250-300 từ)

Giáo trình Cấu trúc dữ liệu và giải thuật (Mã môn học: MH10) do tác giả Trần Thị Mơ chủ biên, được ban hành chính thức theo Quyết định số 597/QĐ-CĐXD1 ngày 29 tháng 12 năm 2023 của Hiệu trưởng Trường Cao đẳng Xây dựng số 1. Tài liệu được biên soạn phục vụ công tác giảng dạy và học tập cho trình độ Trung cấp, ngành Công nghệ thông tin (chuyên ngành Ứng dụng phần mềm). Môn học có tổng thời lượng 60 giờ (bao gồm 30 giờ lý thuyết; 27 giờ thực hành, thí nghiệm, thảo luận, bài tập và 03 giờ kiểm tra), được bố trí giảng dạy tại kỳ học thứ 02 trong chương trình đào tạo và không yêu cầu môn học tiên quyết.

Về mục tiêu học tập, giáo trình trang bị cho người học hệ thống lý thuyết nền tảng về giải thuật, các đặc trưng và phương pháp thiết kế giải thuật; định nghĩa và nguyên lý hoạt động của các cấu trúc dữ liệu thông dụng (danh sách tuyến tính, mảng, ngăn xếp, hàng đợi, danh sách liên kết, cây nhị phân, đồ thị) cùng các giải thuật thao tác tương ứng. Về kỹ năng, người học có khả năng vận dụng các kiểu dữ liệu để cài đặt các chương trình ứng dụng quy mô nhỏ trên ngôn ngữ lập trình cụ thể, đồng thời hình thành năng lực tự chủ, định hướng và thích nghi trong môi trường chuyên môn.

Về cấu trúc, tài liệu được phân chia thành 02 chương trọng tâm: Chương 1 tập trung vào Giải thuật và Chương 2 đi sâu vào Cấu trúc dữ liệu. Điểm đặc sắc trong cách tiếp cận của giáo trình là việc xây dựng tư duy lập trình thông qua đẳng thức kinh điển: $\text{Cấu trúc dữ liệu} + \text{Giải thuật} = \text{Chương trình}$, kết hợp song song giữa phân tích thuật toán bằng lưu đồ khối và cài đặt chi tiết bằng mã lệnh ngôn ngữ lập trình C/Pascal.

---

Nội dung kiến thức cốt lõi (500-600 từ)

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

Cấu trúc tài liệu triển khai theo quy trình logic từ lý thuyết giải thuật đại cương đến việc cài đặt từng cấu trúc dữ liệu cụ thể:

• Chương 1: Giải thuật: Cung cấp các khái niệm cốt lõi về giải thuật (phương pháp giải quyết vấn đề); 08 đặc trưng cơ bản gồm 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 và tính hữu hạn. Trình bày 03 phương thức diễn đạt giải thuật: ngôn ngữ tự nhiên, ngôn ngữ lưu đồ/sơ đồ khối (gồm nút thao tác, nút điều khiển, nút khởi đầu/kết thúc, cung nối) và ngôn ngữ lập trình/mã giả. Giới thiệu các phương pháp thiết kế giải thuật: thiết kế từ trên xuống (Top-down design) và phương pháp tinh chỉnh từng bước. Các ví dụ minh họa gồm thuật toán Euclid, giải phương trình bậc hai $ax^2 + bx + c = 0$, thuật toán tìm số nguyên tố, phần tử dãy Fibonacci và sắp xếp dãy số.
• Chương 2: Cấu trúc dữ liệu: Triển khai chi tiết các mô hình dữ liệu chính:
  • Danh sách tuyến tính & Mảng: Khái niệm phần tử, cấu trúc bản ghi (record/struct), ưu/nhược điểm của mảng tĩnh trong truy cập ngẫu nhiên và chi phí dịch chuyển bộ nhớ khi thêm/xóa.
  • Ngăn xếp (Stack): Hoạt động theo nguyên lý LIFO (Last In First Out), các thao tác push, pop, kiểm tra rỗng/đầy, ứng dụng đổi số nguyên sang hệ nhị phân.
  • Hàng đợi (Queue): Hoạt động theo nguyên lý FIFO (First In First Out), các thao tác put, get, kiểm tra rỗng/đầy, mô hình hóa trên danh sách liên kết hoặc mảng một chiều.
  • Danh sách liên kết (Linked List): Khái niệm node (data, con trỏ next), con trỏ HEAD, TAIL. Chi tiết danh sách liên kết đơn (hàm createNode, insertHead, insertTail, insertAfter, processList, searchList, deleteList, List_Selection_Sort); danh sách liên kết kép (struct dNode với con trỏ pre và next, các thao tác chèn/hủy đầu/cuối, List_Interchange_Sort); danh sách liên kết vòng (đơn vòng, đôi vòng).
  • Cây nhị phân (Binary Tree): Định nghĩa, nút con trái/phải, tính chất toán học quan hệ giữa số nút $n$ và chiều cao $h$ ($n \le 2^h - 1$, $n \ge h \ge \log_2(n+1)$), cấu trúc động treenode, ba phép duyệt cây gồm tiền tự (NLR), trung tự (LNR), hậu tự (LRN). Thuật toán tìm kiếm nhị phân (binary_search) độ phức tạp $\lg N$. Cây nhị phân tìm kiếm (BST): quy tắc khóa trái nhỏ hơn gốc, khóa phải lớn hơn hoặc bằng gốc; các hàm tree_search, tree_insert, tree_creation, giải thuật xóa nút lá, nút có 1 con và nút có 2 con.
  • Đồ thị (Graph): Đồ thị có hướng $G=\langle V,E\rangle$ (bán bậc ngoài $A(u)$, bán bậc trong $I(v)$, đường đi, chu trình, tính liên thông), đồ thị vô hướng, đồ thị có trọng số. Hai phương pháp biểu diễn đồ thị: ma trận kề ($n \times n$) và danh sách kề. Hai thuật toán duyệt đồ thị: duyệt theo chiều rộng (BreadthFirstSearch) sử dụng hàng đợi và duyệt theo chiều sâu (DeepFirstSearch) đệ quy sử dụng mảng đánh dấu daxet[].

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

• Lý thuyết nền tảng (Fundamental theories): Lý thuyết thuật toán, nguyên lý lưu trữ dữ liệu tuyến tính và phi tuyến tính, toán học rời rạc ứng dụng trong cấu trúc cây và đồ thị.
• Nguyên tắc cốt lõi (Core principles): Cơ chế quản lý bộ nhớ động (malloc/free, new/delete), nguyên tắc LIFO của Stack, FIFO của Queue, tính đối xứng trong ma trận kề của đồ thị vô hướng, tính phân cấp của cây nhị phân.
• Khung phân tích chuẩn mực (Essential frameworks): Bộ tiêu chuẩn đánh giá cấu trúc dữ liệu (tiết kiệm bộ nhớ trong, phản ánh chính xác thực tế bài toán, thuận tiện trong thao tác); mô hình phân tích bài toán từ trên xuống và quy tắc tinh chỉnh từng bước.

Kỹ năng phát triển

• Kỹ năng kỹ thuật (Technical skills): Cài đặt cấu trúc dữ liệu bằng mã lệnh C/C++ (struct, con trỏ); hiện thực hóa các giải thuật sắp xếp (Selection Sort, Interchange Sort), giải thuật tìm kiếm tuần tự và nhị phân; xây dựng hàm đệ quy và quản lý con trỏ bộ nhớ.
• Kỹ năng phân tích (Analytical skills): Khả năng chuyển đổi bài toán thực tế thành sơ đồ khối hoặc mã giả; phân tích ưu - nhược điểm của cấu trúc lưu trữ tĩnh (mảng) so với động (danh sách liên kết); lựa chọn cấu trúc dữ liệu phù hợp dựa trên tiêu chí tài nguyên và tốc độ xử lý.
• Kỹ năng thực hành (Practical competencies): Xây dựng các mô đun phần mềm xử lý dữ liệu hồ sơ; mô hình hóa bài toán đồ thị mạng lưới bằng ma trận kề/danh sách kề; lập trình duyệt các thành phần liên thông trên đồ thị.

---

Phương pháp giảng dạy và học tập (300-350 từ)

Giáo trình áp dụng phương pháp sư phạm kết hợp chặt chẽ giữa truyền thụ lý thuyết và rèn luyện kỹ năng thực hành theo tỷ lệ cân đối: 30 giờ lý thuyết, 27 giờ thực hành/thảo luận/bài tập và 03 giờ kiểm tra. Tiến trình giảng dạy tuân thủ phương pháp đi từ trừu tượng đến cụ thể: bắt đầu bằng định nghĩa hình thức, mô hình hóa qua sơ đồ khối trực quan, chuyển thể sang mã giả và hoàn thiện bằng mã nguồn C/C++ có thể biên dịch.

Hệ thống bài tập và nghiên cứu tình huống được xây dựng chi tiết ở cuối mỗi chương:

• Bài tập tư duy giải thuật (Chương 1): Viết giải thuật kiểm tra số nguyên tố, tìm số hạng thứ $n$ của dãy Fibonacci, mô hình hóa hệ thống chương trình quản lý bảo trì hồ sơ lương cán bộ theo sơ đồ phân rã Top-down.
• Bài tập thực hành cấu trúc dữ liệu (Chương 2): Bao gồm 08 câu hỏi lý thuyết đối chiếu ưu/nhược điểm và 07 bài tập lập trình hoàn chỉnh. Tiêu biểu là bài tập thiết kế danh sách liên kết đơn quản lý sinh viên (mã sinh viên, họ tên, năm sinh, điểm trung bình) với đầy đủ các hàm chức năng: nhập/xuất, lọc điểm $\ge 5$, sắp xếp giảm theo điểm, sắp xếp tăng theo mã, tìm kiếm theo mã/họ tên và thêm phần tử; các bài tập thao tác trên danh sách liên kết kép; bài tập biểu diễn và xác định thứ tự duyệt cây nhị phân (tiền tự, trung tự, hậu tự); bài tập lập ma trận kề, danh sách kề và mô phỏng từng bước thuật toán BFS/DFS trên đồ thị cho trước.

Phương pháp đánh giá kết quả học tập gồm đánh giá quá trình thông qua các bài thực hành viết mã trên máy, bài tập giải thuật cá nhân/nhóm và bài kiểm tra định kỳ 03 giờ theo quy định. Đối với việc tự học, giáo trình yêu cầu người học tự thực hiện lại các bước tinh chỉnh giải thuật, cài đặt độc lập toàn bộ các cấu trúc dữ liệu mẫu và hoàn thành 100% hệ thống câu hỏi trắc nghiệm/tự luận cuối mỗi chương.

---

Điểm nổi bật và cập nhật (250-300 từ)

• Tính chuẩn hóa theo khung chương trình đào tạo nghề nghiệp: Giáo trình được ban hành năm 2023 theo Quyết định số 597/QĐ-CĐXD1 của Hiệu trưởng Trường Cao đẳng Xây dựng số 1, bám sát các yêu cầu thực tiễn của trình độ Trung cấp CNTT, đảm bảo lượng kiến thức vừa đủ, không mang tính trừu tượng quá mức mà tập trung vào khả năng ứng dụng.
• Minh họa bằng mã nguồn thực thi cụ thể: Khác với các tài liệu thuần lý thuyết, giáo trình cung cấp đầy đủ các khai báo kiểu dữ liệu (struct node, struct sList, struct dNode, struct dList, treenode) và định nghĩa hàm xử lý hoàn chỉnh bằng ngôn ngữ C/C++, kèm các điều kiện biên như xử lý danh sách rỗng, tràn bộ nhớ (NULL), giải phóng bộ nhớ (delete, free).
• Tích hợp bài toán ứng dụng thực tế: Mỗi cấu trúc dữ liệu đều đi kèm với ngữ cảnh ứng dụng rõ ràng trong đời sống và kỹ thuật:
  • Ngăn xếp: Cơ chế đảo ngược dữ liệu, bài toán chuyển đổi cơ số từ hệ thập phân sang nhị phân.
  • Hàng đợi: Bài toán điều phối công việc trong máy tính (hàng đợi in ấn, xử lý tiến trình) hoặc điều phối đường băng sân bay.
  • Danh sách liên kết: Ứng dụng quản lý danh bạ điện thoại, danh mục sách thư viện, hồ sơ nhân sự/sinh viên.
  • Đồ thị: Ứng dụng mô tả mạng lưới giao thông, khoảng cách giữa các thành phố trên bản đồ số, sơ đồ chuyển trạng thái máy.
• Phân tích đối chiếu ưu - nhược điểm hệ thống: Cung cấp các mục phân tích so sánh trực tiếp giữa các cấu trúc dữ liệu tương đồng (mảng tĩnh đối chiếu danh sách liên kết động; Stack LIFO đối chiếu Queue FIFO; ma trận kề đối chiếu danh sách kề), giúp người học định hình tiêu chí lựa chọn cấu trúc tối ưu cho từng bài toán cụ thể.

---

Đối tượng sử dụng giáo trình (200-250 từ)

• Sinh viên/Người học mục tiêu: Tài liệu được thiết kế chuyên biệt cho sinh viên trình độ Trung cấp ngành Công nghệ thông tin (Ứng dụng phần mềm) tại học kỳ thứ 02. Ngoài ra, giáo trình phù hợp cho học sinh, sinh viên các ngành kỹ thuật liên quan có nhu cầu trang bị kiến thức cơ sở về lập trình và giải thuật.
• Kiến thức tiên quyết (Prerequisites): Theo khung chương trình đào tạo của môn học MH10, môn học không yêu cầu môn học tiên quyết bắt buộc. Tuy nhiên, để tiếp thu tốt nội dung giáo trình, người học cần có kiến thức cơ bản về tin học đại cương và hiểu biết ban đầu về cú pháp lệnh lập trình cơ bản (C/Pascal).
• Giảng viên và cán bộ giảng dạy: Tài liệu là căn cứ chuẩn hóa dùng để xây dựng đề cương bài giảng chi tiết, kế hoạch giảng dạy lý thuyết (30 giờ), phân bổ nội dung thực hành/thảo luận (27 giờ) và thiết kế ngân hàng đề kiểm tra đánh giá (03 giờ).
• Người tự học và tham khảo chuyên môn: Là tài liệu tự học có hệ thống dành cho lập trình viên mới bắt đầu, người chuẩn bị ôn thi chuyển cấp hoặc người làm việc trong lĩnh vực phần mềm cần củng cố lại các giải thuật tìm kiếm, sắp xếp và thao tác trên cấu trúc dữ liệu động.

---

Câu hỏi thường gặp (250-300 từ)

1. Giáo trình này phù hợp với ai?

Giáo trình được biên soạn phục vụ chính thức cho sinh viên trình độ Trung cấp ngành Công nghệ thông tin (Ứng dụng phần mềm). Đồng thời, tài liệu phù hợp cho bất kỳ cá nhân nào bắt đầu học lập trình và muốn nắm vững bản chất của việc tổ chức dữ liệu và thuật toán xử lý.

2. Cần kiến thức nền nào để học?

Môn học không quy định môn học tiên quyết. Người học chỉ cần có tư duy logic cơ bản và đã làm quen với các khái niệm lập trình nhập môn như biến, kiểu dữ liệu nguyên thủy, cấu trúc rẽ nhánh (if-else), vòng lặp (for, while).

3. Điểm khác biệt với giáo trình khác?

Tài liệu tập trung cô đọng trong 02 chương trọng tâm (Giải thuật và Cấu trúc dữ liệu), giảm thiểu các chứng minh toán học phức tạp, thay vào đó tập trung trực tiếp vào giải thuật dưới dạng mã lệnh C/C++, bảng so sánh ưu/nhược điểm thực tế và các bài tập mô phỏng cụ thể.

4. Làm sao để tự học hiệu quả?

Người học nên tuân thủ quy trình 4 bước: (1) Đọc hiểu đặc trưng và nguyên lý hoạt động của cấu trúc; (2) Tự vẽ lại sơ đồ khối/lưu đồ giải thuật; (3) Gõ và chạy thử các đoạn mã C mẫu trong giáo trình; (4) Tự giải quyết trọn vẹn 07 bài tập lập trình lớn ở cuối Chương 2.

5. Có tài liệu bổ trợ nào kèm theo?

Giáo trình được xây dựng dựa trên sự kế thừa từ các tài liệu tham khảo học thuật chính thức được liệt kê tại trang 47:

1. Đỗ Xuân Lôi (2012), Cấu trúc dữ liệu và giải thuật, Nhà xuất bản Đại học Quốc gia Hà Nội.
2. Nguyễn Đình Hóa (2010), Cấu trúc dữ liệu và giải thuật, Nhà xuất bản Đại học Quốc gia Hà Nội.
3. Lê Hữu Lập, Nguyễn Duy Phương (2013), Giáo trình Kỹ thuật lập trình, Học viện Công nghệ Bưu chính Viễn thông.

---

Kết luận (150 từ)

Giáo trình 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 phần cơ sở ngành cung cấp toàn diện hệ thống tri thức nền tảng từ khái niệm giải thuật, phương pháp thiết kế từ trên xuống đến các 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) và phi tuyến tính (cây nhị phân, đồ thị).

Lộ trình học tập đề xuất cho người học gồm 3 giai đoạn: bắt đầu từ việc nắm vững lý thuyết đặc trưng và ngôn ngữ diễn đạt giải thuật tại Chương 1; tiến hành thực hành cài đặt cấu trúc dữ liệu động trên ngôn ngữ C tại Chương 2; và hoàn thiện năng lực chuyên môn bằng việc giải quyết hệ thống bài toán quản lý dữ liệu ứng dụng. Để mở rộng kiến thức chuyên sâu, người học có thể kết hợp tham khảo các giáo trình của tác giả Đỗ Xuân Lôi, Nguyễn Đình Hóa và Lê Hữu Lập được nêu trong danh mục tài liệu tham khảo.

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

Chương 1: Giải thuật Chương 2: Cấu trúc dữ liệu 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 2 MþC LþC CH¯¡NG 1: GIÀI THUÀT. Các khái niám về giÁi thuÁt. Các đặc tr°ng của giÁi thuÁt.

Tính hiáu quÁ. Tính chính xác. Tính ứng dụng. Ngôn ngā dißn đ¿t giÁi thuÁt.

Ngôn ngā thông th°ờng. Ngôn ngā lÁp trình. Ph°¢ng pháp thiết kế giÁi thuÁt. Tinh chỉnh từng b°ớc.

11 CH¯¡NG 2: CÂU TRÚC DĀ LIàU. Danh sách tuyến tính. Danh sách liên kết. Danh sách liên kết đ¢n.

Các d¿ng khác của danh sách liên kết. Cây nhị phân. Biểu dißn cây nhị phân. Duyát cây nhị phân.

Cây nhị phân tìm kiếm. Duyát đồ thị theo chiều ráng. Duyát theo chiều sâu. 43 4 Tên môn hác: CÂU TRÚC Dþ LIàU VÀ GIÀI THU¾T Mã môn hác: MH10 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: 27 giờ; Kiểm tra 03 giờ) I.

Vß trí, tính chÃt cÿa môn hác: - Vị trí: + Môn học đ°ợc bố trí ở kỳ học thứ 02. + Môn học tiên quyết: Không - Tính chÃt: là môn học c¢ sở ngành, cung cÃp các kiến thức c¢ bÁn về các khái niám c¢ bÁn, 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 đó. Mÿc tiêu môn hác: 1. Về kiến thức: - Trình bày đ°ợc các khái niám về giÁi thuÁt, các đặc tr°ng của giÁi thuÁt; - Trình bày đ°ợc mát số ngôn ngā dißn đ¿t giÁi thuÁt; - Trình bày đ°ợc mát số ph°¢ng pháp thiết kế giÁi thuÁt; - Trình bày đ°ợc mát số kiểu dā liáu danh sách tuyến tính và thao tác trên kiểu dā liáu đó; - Trình bày đ°ợc mát số kiểu dā liáu danh sách liên kết và thao tác trên kiểu dā liáu đó; - Trình bày đ°ợc kiến thức về cây nhị phân, phép duyát và ứng dụng cây nhị phân tìm kiếm; - Trình bày đ°ợc kiến thức về đồ thị: biểu dißn đồ thị, phép duyát và ứng dụng của đồ thị.

Về kỹ năng: - VÁn dụng các kiểu dā liáu thông dụng nh° danh sách tuyến tính, cây nhị phân, đồ thị để cài đặt các ch°¢ng trình ứng dụng nhỏ. Về năng lăc tă chủ và trách nhiám: Có năng lăc tă định h°ớng, thích nghi với các môi tr°ờng làm viác khác nhau; tă học tÁp, tích lũy kiến thức, kinh nghiám để nâng cao trình đá chuyên môn nghiáp vụ. 5 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. Các khái niám vÁ 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ể 7 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 giÁi thu¿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. Ngôn ngÿ 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ý.

8 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: 9 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.