Giáo trình Cấu trúc dữ liệu - Ngành: Hệ thống thông tin, thiết kế trang web, công nghệ thông tin (Ứng dụng phần mềm)
ỦY BAN NHÂN DÂN THÀNH PHỐ HỒ CHÍ MINH
TRƯỜNG CAO ĐẲNG KINH TẾ KỸ THUẬT
THÀNH PHỐ HỒ CHÍ MINH
GIÁO TRÌNH
MÔN HỌC: CẤU TRÚC DỮ LIỆU
NGÀNH: HỆ THỐNG THÔNG TIN, THIẾT KẾ TRANG WEB, CÔNG
NGHỆ THÔNG TIN (ỨNG DỤNG PHẦN MỀM)
TRÌNH ĐỘ: CAO ĐẲNG
Thành phố Hồ Chí Minh, năm 2020
ỦY BAN NHÂN DÂN THÀNH PHỐ HỒ CHÍ MINH
TRƯỜNG CAO ĐẲNG KINH TẾ KỸ THUẬT
THÀNH PHỐ HỒ CHÍ MINH
GIÁO TRÌNH
MÔN HỌC: CẤU TRÚC DỮ LIỆU
NGÀNH: HỆ THỐNG THÔNG TIN, THIẾT KẾ TRANG WEB, CÔNG
NGHỆ THÔNG TIN (ỨNG DỤNG PHẦN MỀM)
TRÌNH ĐỘ: CAO ĐẲNG
THÔNG TIN CHỦ NHIỆM ĐỀ TÀI
Họ tên: Võ Đào Thị Hồng Tuyết
Học vị: Thạc Sỹ
Đơn vị: Khoa Công Nghệ Thông Tin
Email: [email protected]
TRƯỞNG KHOA
TRƯỞNG
BỘ MÔN
CHỦ NHIỆM
ĐỀ TÀI
HIỆU TRƯỞNG
DUYỆT
Thành phố Hồ Chí Minh, năm 2020
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.
GIỚI THIỆU
Cấu trúc dữ liệu một trong những môn học cơ bản của sinh viên ngành Công
Nghệ Thông Tin. Hiểu và vận dụng các cấu trúc dữ liệu và các giải thuật là cơ sở để
sinh viên tiếp cận với việc thiết kế và xây dựng phần mềm cũng như sử dụng các công
cụ lập trình hiện đại.
Cấu trúc dữ liệu có thể được xem như là 1 phương pháp lưu trữ dữ liệu trong
máy tính nhằm sử dụng một cách có hiệu quả các dữ liệu này. Và để sử dụng các dữ
liệu một cách hiệu quả thì cần phải có các thuật toán áp dụng trên các dữ liệu đó. Do
vậy, cấu trúc dữ liệu và giải thuật là 2 yếu tố không thể tách rời và có những liên quan
chặt chẽ với nhau. Việc lựa chọn một cấu trúc dữ liệu có thể sẽ ảnh hưởng lớn tới việc
lựa chọn áp dụng giải thuật nào.
Bài giảng “Cấu Trúc Dữ Liệu” bao gồm 4 chương, trình bày về các cấu trúc dữ
liệu và các giải thuật cơ bản nhất trong tin học.
Chương 1 trình bày về phân tích và thiết kế thuật toán. Đầu tiên là cách phân
tích 1 vấn đề, từ thực tiễn cho tới chương trình, cách thiết kế một giải pháp cho vấn đề
theo cách giải quyết bằng máy tính. Trình bày về đệ qui, một khái niệm rất cơ bản
trong toán học. Việc sử dụng đệ qui có thể xây dựng được những chương trình giải
quyết được các vấn đề rất phức tạp chỉ bằng một số ít câu lệnh, đặc biệt là các vấn đề
mang bản chất đệ qui.
Chương 2 trình bày về các thuật toán sắp xếp và tìm kiếm. Các thuật toán này
cùng với các kỹ thuật được sử dụng trong đó được coi là các kỹ thuật cơ sở cho lập
trình máy tính. Các thuật toán được xem xét bao gồm các lớp thuật toán đơn giản và cả
các thuật toán cài đặt phức tạp nhưng có thời gian thực hiện tối ưu.
Chương 3, 4 trình bày về các cấu trúc dữ liệu được sử dụng rất thông dụng như
mảng và danh sách liên kết, ngăn xếp và hàng đợi, cây. Đó là các cấu trúc dữ liệu cũng
rất gần gũi với các cấu trúc trong thực tiễn.
Cuối mỗi phần đều có các câu hỏi và bài tập để sinh viên ôn luyện và tự kiểm
tra kiến thức của mình. Cuối tài liệu có các phụ lục hướng dẫn trả lời câu hỏi, mã
nguồn tham khảo và tài liệu tham khảo.
Về nguyên tắc, các cấu trúc dữ liệu và các giải thuật có thể được biểu diễn và
cài đặt bằng bất cứ ngôn ngữ lập trình hiện đại nào. Tuy nhiên, để có được các phân
tích sâu sắc hơn và có kết quả thực tế hơn, tác giả đã sử dụng ngôn ngữ lập trình C để
minh hoạ cho các cấu trúc dữ liệu và thuật toán. Do vậy, ngoài các kiến thức cơ bản về
tin học, sinh viên cần có kiến thức về ngôn ngữ lập trình C.
Cuối cùng, mặc dù đã hết sức cố gắng nhưng chắc chắn không tránh khỏi các
thiếu sót. Tác giả rất mong nhận được sự góp ý của đồng nghiệp và sinh viên để tài
liệu được hoàn thiện hơn.
MỤC LỤC
GIÁO TRÌNH MÔN HỌC
Tên môn học: CẤU TRÚC DỮ LIỆU
Mã môn học: MH3101302
Thời gian thực hiện môn học: 60 giờ; (Lý thuyết: 30 giờ; Thực hành: 28 giờ;
Kiểm tra: 2 giờ)
I. Vị trí, tính chất của môn học:
- Vị trí: Môn học được bố trí sau khi người học học xong môn học kỹ thuật lập
trình, học kỳ 1.
- Tính chất: Là môn học đào tạo nghề bắt buộc.
II. Mục tiêu môn học:
- Về kiến thức:
+ Trình bày được các bước phân tích, đánh giá độ phức tạp của thuật toán
+ Trình bày được các cấu trúc kiểu dữ liệu trừu tượng, các thao tác tương
tứng trên các kiểu dữ liệu.
+ Trình bày được các thuật toán tìm kiếm, sắp xếp
- Về kỹ năng:
+ Vận dụng cấu trúc dữ liệu, các thao tác trên cấu trúc dữ liệu đã được sử
dụng theo một bài toán cụ thể.
+ Vận dụng được các thuật toán tìm kiếm, sắp xếp và tự cài đặt theo một
bài toán cụ thể.
+ Vận dụng các vấn đề cơ bản và mối quan hệ giữa cấu trúc dữ liệu và giải
thuật, phân tích thiết kế thuật toán.
- Về năng lực tự chủ và trách nhiệm:
+ Sinh viên có khả năng lựa chọn thuật toán cũng như cấu trúc dữ liệu phù
hợp cho từng bài toán.
KHOA CÔNG NGHỆ THÔNG TIN
III. Nội dung môn học:
1. Nội dung tổng quát và phân bổ thời gian:
Thời gian (giờ)
Bài tập,
Số
TT
Tên chương, mục
Tổng
số
Lý
Kiểm
thuyết
Tra
thực hành
Chương 1: Thiết kế giải
thuật - Thuật giải đệ qui
1. Thiết kế giải thuật
1.1. Giải thuật và ngôn ngữ
diễn đạt giải thuật
1.2. Các bước cơ bản để giải
quyết tập bài toán
1
8
4
4
2. Thuật giải đệ quy
2.1. Khái niệm về đệ qui
2.2.Thiết kế giải thuật đệ qui
2.3. Áp dụng thuật giải đệ
qui
Chương 2: Các thuật giải
sắp xếp và tìm kiếm
1. Một số phương pháp sắp
xếp đơn giản
1.1. Đổi chỗ trực tiếp
(Interchange Sort)
1.2. Nổi bọt (Bubble Sort)
2
16
8
7
1
1.3. Chèn trực tiếp (Insertion
Sort)
1.4. Chọn trực tiếp
(Selection Sort)
1.5. Phân hoạch (Quick Sort)
1.6 Nhận xét, đánh giá
2. Một số phương pháp tìm
KHOA CÔNG NGHỆ THÔNG TIN
Thời gian (giờ)
Bài tập,
Số
TT
Tên chương, mục
Tổng
số
Lý
Kiểm
thuyết
Tra
thực hành
kiếm
2.1. Tìm kiếm tuần tự
2.2. Tìm kiếm nhị phân
2.3. Nhận xét, đánh giá
Chương 3: Các cấu trúc dữ
liệu
1.Danh sách liên kết đơn
3
24
12
11
1
2.Danh sách kiểu ngăn xếp
(Stack)
3.3.Danh sách kiểu hàng đợi
(Queue)
Chương 4: Cây
1. Định nghĩa và khái niệm
2. Cây tổng quát
2.1. Biểu diễn
4
12
6
6
2.2. Phép duyệt
2.3. Cây nhị phân
Cộng
60
30
28
2
Nội dung chi tiết:
Chương 1: Thiết kế giải thuật - Thuật giải đệ qui
Thời gian: 8 giờ
Mục tiêu: Trình bày được các bước cơ bản để giải quyết bài tập, và dần hình thành việc
thiết kế giải thuật để giải quyết theo yêu cầu. Trình bày được khái niệm về giải thuật đệ
quy, trình bày được các bước xây dựng thuật giải đệ quy. Qua đó đề xuất hướng áp dụng
thuật giải đệ quy cho bài toán cụ thể.
Nội dung:
KHOA CÔNG NGHỆ THÔNG TIN
1. Thiết kế giải thuật
1.1.Giải thuật và ngôn ngữ diễn đạt giải thuật
1.2.Các bước cơ bản để giải quyết tập bài toán
2. Thuật giải đệ quy
2.1.Khái niệm về đệ qui
2.2.Thiết kế giải thuật đệ qui
2.3.Áp dụng thuật giải đệ qui
Chương 2: Các thuật giải sắp xếp và tìm kiếm
Thời gian: 16 giờ
Mục tiêu: Tình bày được các giải thuật sắp xếp và tìm kiếm. Phân biệt được các thuật
toán sắp xếp và tìm kiếm. Sinh viên có khả năng cài đặt được các thuật toán sắp xếp và
tìm kiếm
Nội dung:
1. Một số phương pháp sắp xếp đơn giản
1.1. Đổi chỗ trực tiếp (Interchange Sort)
1.2. Nổi bọt (Bubble Sort)
1.3. Chèn trực tiếp (Insertion Sort)
1.4. Chọn trực tiếp (Selection Sort)
1.5. Phân hoạch (Quick Sort)
1.6 Nhận xét, đánh giá
2. Một số phương pháp tìm kiếm
2.1. Tìm kiếm tuần tự
2.2. Tìm kiếm nhị phân
2.3. Nhận xét, đánh giá
Chương 3: Các cấu trúc dữ liệu
Thời gian: 24 giờ
Mục tiêu: Trình bày được các cấu trúc dữ liệu cơ bản như ngăn xếp, hàng đợi, danh sách
liên kết. Trình bày được các thao tác cơ bản trên cấu trúc dữ liệu. Vận dụng cấu trúc dữ
liệu vào một bài toán cụ thể
KHOA CÔNG NGHỆ THÔNG TIN
Nội dung:
1. Danh sách liên kết đơn
2. Danh sách kiểu ngăn xếp (Stack)
3. Danh sách kiểu hàng đợi (Queue)
Chương 4: Cây
Thời gian: 12 giờ
Mục tiêu: Trình bày được định nghĩa, tính chất của cây. Trình bày được cấu trúc cơ bản
của cây nhị phân, cây nhị phân tìm kiếm và các thao tác cơ bản trên cây nhị phân, cây nhị
phân tìm kiếm.
Nội dung:
1.Định nghĩa và khái niệm
2.Cây tổng quát
2.1. Biểu diễn
2.2. Phép duyệt
2.3.Cây nhị phân
IV. Điều kiện thực hiện môn học:
1. Phòng học chuyên môn hóa/nhà xưởng: phòng máy
2. Trang thiết bị máy móc: máy chiếu, màn chiếu, hệ thống âm thanh
3. Học liệu, dụng cụ, nguyên vật liệu: bảng
4. Các điều kiện khác: không
V. Nội dung và phương pháp, đánh giá:
1. Nội dung:
- Chương 1: Phân tích, thiết kế giải thuật
- Chương 2: Thuật giải đệ qui
- Chương 2: Các thuật giải sắp xếp và tìm kiếm
- Chương 3: Các cấu trúc dữ liệu
- Chương 4: Cây
- Kiến thức:
KHOA CÔNG NGHỆ THÔNG TIN
+ Trình bày được các cấu trúc kiểu dữ liệu trừu tượng, các thao tác tương
tứng trên các kiểu dữ liệu.
+ Trình bày được các thuật toán tìm kiếm, sắp xếp
- Kỹ năng:
+ Vận dụng cấu trúc dữ liệu, các thao tác trên cấu trúc dữ liệu đã được sử
dụng theo một bài toán cụ thể.
+ Vận dụng được các thuật toán tìm kiếm, sắp xếp và tự cài đặt theo một bài
toán cụ thể.
+ Vận dụng các vấn đề cơ bản và mối quan hệ giữa cấu trúc dữ liệu và giải
thuật, phân tích thiết kế thuật toán.
- Năng lực tự chủ và trách nhiệm:
+ Sinh viên có khả năng lựa chọn thuật toán cũng như cấu trúc dữ liệu phù
hợp cho từng bài toán.
2. Phương pháp:
Số cột
Thời
STT
Phương pháp
Hình thức
Viết
kiểm tra gian thi
01 Kiểm tra thường xuyên
02 Kiểm tra định kỳ
1
Viết
Viết
1
90’
90’
03 Thi kết thúc môn học
VI. Hướng dẫn thực hiện môn học:
1. Phạm vi áp dụng môn học: Áp dụng cho khóa học trình độ cao đẳng.
2. Hướng dẫn về phương pháp giảng dạy, học tập môn học:
- Đối với giáo viên, giảng viên:
+ Giáo viên có thể vận dụng phương pháp thuyết trình, giảng giải kết hợp
phương pháp gợi mở, phát vấn để người học nghề có thể tham gia tích cực vào
bài giảng.
+ Phương tiện, dụng cụ giảng dạy: Ngoài phương tiện giảng dạy truyền
thống giáo viên còn có thể sử dụng Máy chiếu Projector, Laptop, sơ đồ, tranh
ảnh minh hoạ giúp làm rõ và sinh động nội dung bài học.
+ Trong điều kiện có thể kết hợp giảng dạy lý thuyết và thực hành trong
cùng một phòng học chuyên môn hoá có máy tính được nối mạng LAN và
mạng Internet, có sử dụng các phương tiện dạy học bằng ngôn ngữ lập trình.
- Đối với người học:
KHOA CÔNG NGHỆ THÔNG TIN
+ Thực hiện đầy đủ và nghiêm túc các qui định đối với môn học và của
giáo viên.
+ Hoàn thành đầy đủ các bài thực hành và tham dự các buổi kiểm tra trên
lớp.
+ Kết thúc khóa học, người học sẽ làm một bài kiểm tra để xác định việc
họ có hoàn thành chương trình học hay không
+ Học sinh tham gia đầy đủ các buổi lên lớp (không nghỉ quá 30% thời
lượng học)
3. Những trọng tâm cần chú ý:
- Trình độ giáo viên: ít nhất phải có bằng cử nhân hoặc bằng cấp tương
đương tính theo kinh nghiệm dạy học trước đó. Có chứng chỉ dạy nghề.
- Nguồn lực đào tạo: Những nguồn lực sau đây được khuyến khích sử dụng
để bổ trợ những phương pháp giảng dạy đề xuất.
+ Cuốn hướng dẫn dành cho giáo viên: được biên soạn và trình bày trong
các khóa tập huấn đào tạo giáo viên.
+ Cơ sở vật chất, trang thiết bị giảng dạy: Lớp học có đầy đủ máy vi tính cho
học sinh thực tập.
+ Sách, giáo trình và tài liệu tham khảo.
+ Kế hoạch giảng dạy và giáo án chi tiết của giáo viên đóng vai trò tài liệu
chính được sử dụng trong quá trình giảng dạy.
- Phương pháp đào tạo: Giáo viên kết hợp nhiều chiến lược giảng dạy để
giúp tất cả người học thuộc mọi đối tượng có những tiến bộ nhất định nào đó.
4. Tài liệu tham khảo:
Tên sách – giáo
Năm
TT
Tên tác giả
NXB
trình
XB
PGS.TS. Hàn Viết Thuận
ThS. Nguyễn Anh Phương
Đại Học Kinh Tế
Quốc Dân
Cấu trúc dữ liệu và
giải thuật
1
2018
Bản dịch tiếng
2
Robert Sedgewick
Việt, NXB Khoa 1994
Algorithms
học và Kỹ thuật,
KHOA CÔNG NGHỆ THÔNG TIN
Chương 1: Thiết kế giải thuật – thuật giải đệ qui
CHƯƠNG 1: THIẾT KẾ GIẢI THUẬT - THUẬT GIẢI ĐỆ QUI
Mục tiêu: Trình bày được các bước cơ bản để giải quyết bài tập và dần hình
thành việc thiết kế giải thuật để giải quyết theo yêu cầu. Trình bày được khái niệm về
giải thuật đệ quy, trình bày được các bước xây dựng thuật giải đệ quy. Qua đó đề xuất
hướng áp dụng thuật giải đệ quy cho bài toán cụ thể.
1. Thiết kế giải thuật
1.1. Giải thuật và ngôn ngữ diễn đạt giải thuật
1.1.1. Giải thuật
Là một dãy các thao tác xác định trên một đối tượng, sao cho sau khi thực hiện
một số hữu hạn các bước thì đạt được mục tiêu. Theo R.A.Kowalski thì bản chất của
giải thuật:
Giải thuật = Logic + Điều khiển
Logic: Đây là phần khá quan trọng, nó trả lời câu hỏi "giải thuật làm gì, giải
quyết vấn đề gì?", những yếu tố trong bài toán có quan hệ với nhau như thế nào v.v…
Ở đây bao gồm những kiến thức chuyên môn mà bạn phải biết để có thể tiến hành giải
bài toán. Ví dụ: để giải một bài toán tính diện tích hình cầu, mà bạn không còn nhớ
công thức tính hình cầu thì bạn không thể viết chương trình cho máy để giải bài toán
này được.
Điều khiển: Thành phần này trả lời câu hỏi: giải thuật phải làm như thế nào?
Chính là cách thức tiến hành áp dụng thành phần logic để giải quyết vấn đề.
1.1.2. Ngôn ngữ diễn đạt giải thuật
Sau khi đã xây dựng được mô hình toán học cho vấn đề cần giải quyết, tiếp
theo, ta có thể hình thành một thuật toán cho mô hình đó. Phiên bản đầu tiên của thuật
toán thường được diễn tả dưới dạng các phát biểu tương đối tổng quát, và sau đó sẽ
được tinh chỉnh dần từng bước thành chuỗi các lệnh cụ thể, rõ ràng hơn.
Mối liên hệ giữa Cấu trúc dữ liệu và giải thuật
Thực hiện một đề án tin học là chuyển bài toán thực tế thành bài toán có thể
giải quyết trên máy tính. Một bài toán thực tế bất kỳ đều bao gồm các đối tượng dữ
liệu và các yêu cầu xử lý trên những đối tượng đó. Vì thế, để xây dựng một mô hình
tin học phản ánh được bài toán thực tế cần chú trọng đến hai vấn đề :
Tổ chức biểu diễn các đối tượng thực tế :
Các thành phần dữ liệu thực tế đa dạng, phong phú và thường chứa đựng
những quan hệ nào đó với nhau, do đó trong mô hình tin học của bài toán, cần phải tổ
chức , xây dựng các cấu trúc thích hợp nhất sao cho vừa có thể phản ánh chính xác các
KHOA CÔNG NGHỆ THÔNG TIN
Trang 1
Chương 1: Thiết kế giải thuật – thuật giải đệ qui
dữ liệu thực tế này, vừa có thể dễ dàng dùng máy tính để xử lý. Công việc này được
gọi là xây dựng cấu trúc dữ liệu (Data structure) cho bài toán.
Xây dựng các thao tác xử lý dữ liệu:
Từ những yêu cầu xử lý thực tế, cần tìm ra các giải thuật tương ứng để xác
định trình tự các thao tác máy tính phải thi hành để cho ra kết quả mong muốn, đây là
bước xây dựng giải thuật (Algorithm) cho bài toán.
Trong một đề án tin học, giải thuật và cấu trúc dữ liệu có mối quan hệ chặt chẽ
với nhau, được thể hiện qua công thức :
Cấu trúc dữ liệu + Giải thuật = Chương trình
1.2. Các bước cơ bản để giải quyết tập bài toán
Chương trình (Program)
Là một tập hợp các mô tả, các phát biểu, nằm trong một hệ thống qui ước về ý
nghĩa và thứ tự thực hiện, nhằm điều khiển máy tính làm việc. Theo Niklaus Wirth thì:
Chương trình = Thuật toán + Cấu trúc dữ liệu
Các thuật toán và chương trình đều có cấu trúc dựa trên 3 cấu trúc điều khiển
cơ bản:
Tuần tự (Sequential): Các bước thực hiện tuần tự một cách chính xác từ trên
xuống, mỗi bước chỉ thực hiện đúng một lần.
Chọn lọc (Selection): Chọn 1 trong 2 hay nhiều thao tác để thực hiện.
Lặp lại (Repetition): Một hay nhiều bước được thực hiện lặp lại một số lần.
Ngôn ngữ lập trình (Programming language)
Ngôn ngữ lập trình là hệ thống các ký hiệu tuân theo các qui ước về ngữ pháp
và ngữ nghĩa, dùng để xây dựng thành các chương trình cho máy tính.
Một chương trình được viết bằng một ngôn ngữ lập trình cụ thể (ví dụ Pascal,
C…) gọi là chương trình nguồn, chương trình dịch làm nhiệm vụ dịch chương trình
nguồn thành chương trình thực thi được trên máy tính.
Các bước lập trình:
Bước 1: Phân tích vấn đề và xác định các đặc điểm. (xác định I-P-O)
Bước 2: Lập ra giải pháp. (đưa ra thuật giải)
Bước 3: Cài đặt. (viết chương trình)
Bước 4: Chạy thử chương trình. (dịch chương trình)
KHOA CÔNG NGHỆ THÔNG TIN
Trang 2
Chương 1: Thiết kế giải thuật – thuật giải đệ qui
Bước 5: Kiểm chứng và hoàn thiện chương trình. (thử nghiệm bằng nhiều số liệu
và đánh giá)
Kỹ thuật lập trình
I-P-O Cycle (Input-Pprocess-Output Cycle) (Quy trình nhập-xử lý-xuất)
Quy trình xử lý cơ bản của máy tính gồm I-P-O.
Input
Output
Process
Hình 1. 1 Quy trình xử lý cơ bản của máy tính
Ví dụ 1: Xác định Input, Process, Output của việc làm 1 ly nước chanh nóng
Input
:
:
ly, đường, chanh, nước nóng, muỗng.
- cho hỗn hợp đường, chanh, nước nóng vào ly.
- dùng muỗng khuấy đều.
Process
Output
:
ly chanh nóng đã sẵn sàng để dùng.
Ví dụ 2: Xác định Input, Process, Output của chương trình tính tiền lương
công nhân tháng 10/2002 biết rằng lương = lương căn bản * ngày công
Input
:
:
:
lương căn bản, ngày công
nhân lương căn bản với ngày công
lương
Process
Output
Ví dụ 3: Xác định Input, Process, Output của chương trình giải phương trình
bậc nhất ax + b = 0
Input
:
:
:
hệ số a, b
Process
Output
chia – b cho a
nghiệm x
Ví dụ 4: Xác định Input, Process, Output của chương trình tìm số lớn nhất của 2
số a và b.
Input
Process
:
:
a, b
Nếu a > b thì Output = a lớn nhất
Ngược lại Output = b lớn nhất
Với mỗi vấn đề cần giải quyết, ta có thể tìm ra nhiều thuật toán khác nhau. Có
những thuật toán thiết kế đơn giản, dễ hiểu, dễ lập trình và sửa lỗi, tuy nhiên thời gian
KHOA CÔNG NGHỆ THÔNG TIN
Trang 3
Chương 1: Thiết kế giải thuật – thuật giải đệ qui
thực hiện lớn và tiêu tốn nhiều tài nguyên máy tính. Ngược lại, có những thuật toán
thiết kế và lập trình rất phức tạp, nhưng cho thời gian chạy nhanh hơn, sử dụng tài
nguyên máy tính hiệu quả hơn. Khi đó, câu hỏi đặt ra là ta nên lựa chọn giải thuật nào
để thực hiện?
Đối với những chương trình chỉ được thực hiện một vài lần thì thời gian chạy
không phải là tiêu chí quan trọng nhất. Đối với bài toán kiểu này, thời gian để lập
trình viên xây dựng và hoàn thiện thuật toán đáng giá hơn thời gian chạy của chương
trình và như vậy những giải thuật đơn giản về mặt thiết kế và xây dựng nên được lựa
chọn.
Đối với những chương trình được thực hiện nhiều lần thì thời gian chạy của
chương trình đáng giá hơn rất nhiều so với thời gian được sử dụng để thiết kế và xây
dựng nó. Khi đó, lựa chọn một giải thuật có thời gian chạy nhanh hơn (cho dù việc
thiết kế và xây dựng phức tạp hơn) là một lựa chọn cần thiết. Trong thực tế, trong giai
đoạn đầu của việc giải quyết vấn đề, một giải thuật đơn giản thường được thực hiện
trước như là 1 nguyên mẫu (prototype), sau đó nó sẽ được phân tích, đánh giá, và cải
tiến thành các phiên bản tốt hơn.
2. Thuật giải đệ quy
2.1.Khái niệm về đệ qui
Khái niệm: Vấn đề đệ quy là vấn đề được định nghĩa bằng chính nó.
Ví dụ:
Tổng S(n) được tính thông qua tổng S(n-1).
Cho S(n) = 1 + 2 + 3 + … + n
=>S(10)? S(11)?
Hình 1. 2 Mô tả các bước tính tổng S(n)=1+2+3+…+n với S(10) và S(11)
KHOA CÔNG NGHỆ THÔNG TIN
Trang 4
Chương 1: Thiết kế giải thuật – thuật giải đệ qui
2 điều kiện quan trọng:
-
-
Tồn tại bước đệ quy.
Điều kiện dừng.
2.2.Thiết kế giải thuật đệ qui
2.2.1.Hệ thức truy hồi
Khái niệm: Hệ thức truy hồi của 1 dãy An là công thức biểu diễn phần tử An thông
qua 1 hoặc nhiều số hạng trước của dãy.
Hình 1. 3 Mô tả hệ thức truy hồi
Ví dụ 1: Vi trùng cứ 1 giờ lại nhân đôi. Vậy sau 5 giờ sẽ có mấy con vi trùng
nếu ban đầu có 2 con?
Giải pháp
- Gọi Vh là số vi trùng tại thời điểm h.
- Ta có:
• Vh = 2Vh-1
• V0 = 2
Đệ quy tuyến tính với V(h)=2*V(h-1) và điều kiện dừng V(0) = 2
Ví dụ 2: Gửi ngân hàng 1000 USD, lãi suất 12%/năm. Số tiền có được sau 30
năm là bao nhiêu?
Giải pháp
- Gọi Tn là số tiền có được sau n năm.
- Ta có:
• Tn = Tn-1 + 0.12Tn-1 = 1.12Tn-1
• V(0) = 1000
Đệ quy tuyến tính với T(n)=1.12*T(n-1) và điều kiện dừng V(0) = 1000
2.2.2.Chia để trị (divide & conquer)
Khái niệm:
- Chia bài toán thành nhiều bài toán con.
KHOA CÔNG NGHỆ THÔNG TIN
Trang 5
Chương 1: Thiết kế giải thuật – thuật giải đệ qui
- Giải quyết từng bài toán con.
- Tổng hợp kết quả từng bài toán con để ra lời giải.
Thuật toán mô tả chia để trị:
{
if (P đủ nhỏ)
Xử lý P
else
{
Chia P P1, P2, …, Pn
for (int i=1;i<=n;i++)
Trị(Pi);
Tổng hợp kết quả
}
}
Ví dụ 1: Cho dãy A đã sắp xếp thứ tự tăng. Tìm vị trí phần tử x trong dãy
(nếu có)
Giải pháp
- mid = (l + r) / 2;
- Nếu A[mid] = x trả về mid.
- Ngược lại
• Nếu x < A[mid] tìm trong đoạn [l, mid – 1]
• Ngược lại tìm trong đoạn [mid + 1, r]
Sử dụng đệ quy nhị phân.
Ví dụ 2: Tính tích 2 chuỗi số cực lớn X và Y
Giải pháp
- X = X2n-1…XnXn-1…X0, Y = Y2n-1…YnYn-1…Y0
- Đặt XL=X2n-1…Xn, XN=Xn-1…X0 X=10nXL+XN
- Đặt YL=Y2n-1…Yn, YN=Yn-1…Y0 Y=10nYL+YN
X*Y = 102nXLYL + 10n(XLYL+XNYN)+XNYN
KHOA CÔNG NGHỆ THÔNG TIN
Trang 6
Chương 1: Thiết kế giải thuật – thuật giải đệ qui
và XLYL+XNYN = (XL-XN)(YN-YL)+XLYL+XNYN
Nhân 3 số nhỏ hơn (độ dài ½) đến khi có thể nhân được ngay.
2.2.3.Lần ngược (Backtracking)
Khái niệm
- Tại bước có nhiều lựa chọn, ta chọn thử 1 bước để đi tiếp.
- Nếu không thành công thì “lần ngược” chọn bước khác.
- Nếu đã thành công thì ghi nhận lời giải này đồng thời “lần ngược” để
truy tìm lời giải mới.
- Thích hợp giải các bài toán kinh điển như bài toán 8 hậu và bài toán mã
đi tuần.
Hình 1. 4 Mô tả lần ngược (Backtracking)
2.3.Áp dụng thuật giải đệ qui
Một số bài toán kinh điển
Hình 1. 5 Một số bài toán kinh điển
2.3.1. Tháp Hà Nội
Mô tả bài toán: Có 3 cột A, B và C và cột A hiện có N đĩa. Tìm cách chuyển N đĩa
từ cột A sang cột C sao cho:
- Một lần chuyển 1 đĩa
- Đĩa lớn hơn phải nằm dưới.
- Có thể sử dụng các cột A, B, C làm cột trung gian.
KHOA CÔNG NGHỆ THÔNG TIN
Trang 7
Tải về để xem bản đầy đủ
96 trang
21160
Free
Bạn đang xem 20 trang mẫu của tài liệu "Giáo trình Cấu trúc dữ liệu - Ngành: Hệ thống thông tin, thiết kế trang web, công nghệ thông tin (Ứng dụng phần mềm)", để tải tài liệu gốc về máy hãy click vào nút Download ở trên
File đính kèm:
- giao_trinh_cau_truc_du_lieu_nganh_he_thong_thong_tin_thiet_k.pdf
