1
TRƯỜNG ĐẠI HỌC KIÊN GIANG
KHOA THÔNG TIN & TRUYỀN THÔNG
BÀI GIẢNG
Biên soạn: ThS. Huỳnh Minh Trí
Lưu hành nội bộ - Năm 2019
2
LỜI NÓI ĐẦU
Giải thuật là lĩnh vực nghiên cứu gắn liền các lĩnh vực lập trình, tính toán, thiết
kế chương trình trong những lĩnh vực nghiên cứu lâu đời của khoa học máy tính. Hầu
hết các chương trình được viết ra, chạy trên máy tính, dù lớn hay nhỏ, dù đơn giản hay
phức tạp, đều phải sử dụng các cấu trúc dữ liệu tuân theo các trình tự, logic, cách thức
làm việc theo những nguyên tắc cụ thể, chính là các giải thuật. Việc hiểu biết về các cấu
trúc dữ liệu và thuật toán cho phép các lập trình viên, các nhà khoa học máy tính có
nền tảng lý thuyết vững chắc, có nhiều lựa chọn hơn trong việc đưa ra các giải pháp
cho các bài toán thực tế. Vì vậy việc học tập môn học phân tích thiết kế thuật toán là
một điều rất quan trọng.
Tài liệu này dựa trên những kinh nghiệm và nghiên cứu mà tác giả đã đúc kết,
rút kinh nghiệm, thu thập trong quá trình giảng dạy và nghiên cứu, tham khảo các tài
liệu giảng dạy của các trường đại học, các tác giả đồng ngiệp tại các khoa Công nghệ
Thông tin của các trường Đại học Hàng hải Việt nam, Đại học Cần Thơ, Đại học Công
nhiệp Tp Hồ Chí Minh cùng với sự tham khảo của các tài liệu của các đồng nghiệp,
các tác giả trong và ngoài nước, từ điển trực tuyến Wikipedia. Với các chương được
chia thành các chủ đề khác nhau từ các khái niệm cơ bản cho tới thuật toán, tính độ
phức tạp, các phương pháp sắp xếp, tìm kiếm, … hy vọng sẽ cung cấp cho các em sinh
viên, các bạn đọc giả một tài liệu bổ ích. Mặc dù đã rất cố gắng song vẫn không tránh
khỏi một số thiếu sót, và có vay mượn một số thuật ngữ, từ ngũ của đồng nghiệp, hy
vọng sẽ được các bạn bè đồng nghiệp, các em sinh viên, các bạn độc giả ủng hộ và
góp ý chân thành để tôi có thể hoàn thiện hơn nữa tài liệu này.
Xin gửi lời cảm ơn chân thành tới các bạn bè đồng nghiệp và khoa Thông tin và
Truyền thông, Trường Đại học Kiên Giang đã tạo điều kiện giúp đỡ để tài liệu này có
thể hoàn thành tốt.
3
MỤC LỤC
CHƯƠNG 1: THUẬT TOÁN VÀ HIỆU QUẢ CỦA THUẬT TOÁN .................. 1
SỰ CẦN THIẾT PHẢI PHÂN TÍCH THUẬT TOÁN ........................................ 1
Thuật toán (giải thuật) - Algorithm
................................................................................. 1
Độ phức tạp thuật toán – Algorithm Complexity ............................................................ 4
Tỷ suất tăng
và độ phức tạp thuật toán
......................................................................... 6
Phân tích các chương trình ðệ quy ................................................................................ 11
Các hàm tiến triển khác
........................................................................... 14
Thiết kế thuật toán. ..................................................................................... 14
Phương pháp Vét cạn (Brute force)
............................................................................ 15
Phương pháp Quay lui (Back tracking / try and error)
............................................. 15
Phương pháp Chia để trị (Divide and Conquer)
....................................................... 18
Phương pháp tham lam (Greedy)
................................................................................ 26
Qui hoạch động (Dynamic Programming)
.................................................................. 35
Bài tập
......................................................................................................... 38
CHƯƠNG 2: TÌM KIẾM (SEARCHING)
......................................................... 62
Bài toán tìm kiếm
...................................................................................... 62
Tìm kiếm tuần tự (Sequential search)
................................................... 62
Tìm kiếm nhị phân (binary search)
........................................................ 63
Sắp xếp topo
.............................................................................................. 65
Bài tập
......................................................................................................... 70
CHƯƠNG 3: SẮP XẾP (SORTING) ...................................................................... 71
Bài toán sắp xếp ......................................................................................... 71
Sắp xếp gián tiếp
....................................................................................... 71
Các tiêu chuẩn đánh giá một thuật toán sắp xếp
................................ 72
Các phương pháp sắp xếp cơ bản
........................................................ 73
Sắp xếp chọn (Selection sort) ......................................................................................... 73
Sắp xếp đổi chỗ trực tiếp (Exchange sort) .................................................................... 74
Cài đặt của thuật toán: ........................................................................................ 75
Sắp xếp chèn (Insertion sort) .......................................................................................... 75
Sắp xếp nổi bọt (Bubble sort) ......................................................................................... 78
Cài đặt thuật toán: ................................................................................................ 78
Sắp xếp nhanh (Quick sort) ............................................................................................. 79
Sắp xếp trộn (merge sort) ................................................................................................ 83
Cấu trúc dữ liệu Heap, sắp xếp vun đống (Heap sort). ................................................ 86
Các thuật toán khác ......................................................................................................... 90
Bài tập .......................................................................................................... 92
1
CHƯƠNG 1: THUẬT TOÁN VÀ HIỆU QUẢ CỦA THUẬT TOÁN
SỰ CẦN THIẾT PHẢI PHÂN TÍCH THUẬT TOÁN
Trong khi giải m
ột bài toán chúng ta có thể có một số giải thuật khác nhau,
vấn đề là cần phải đánh giá các giải thuật đó để lựa chọn một giải thuật tốt (nhất).
Thông thường thì ta sẽ căn cứ vào các tiêu chuẩn sau:
Giải thuật đúng đắn.
Giải thuật đơn giản.
Giải thuật thực hiện n
hanh.
Với yêu cầu (1), để kiểm tra tính đúng đắn của giải thuật chúng ta có thể cài đặt
giải thuật đó và cho thực hiện trên máy với một số bộ dữ liệu mẫu rồi lấy kết quả thu được
so sánh với kết quả đã biết. Thực ra thì cách
làm này không chắc chắn bởi vì có thể giải
thuật đúng với tất cả các bộ dữ liệu chúng ta đã thử nhưng lại sai với một bộ dữ liệu
nào đó. Vả lại cách làm này chỉ phát hiện ra giải thuật sai chứ chưa chứng minh được
là nó đúng. Tính đúng đắn của giải thuật cần phải được chứng minh bằng toán học. Tất
nhiên điều này không đơn giản và do vậy chúng ta sẽ không đề cập đến ở đây.
Khi chúng ta viết một chương trình để sử dụng một vài lần thì yêu cầu (2) là
quan trọng nhất. Chúng ta cần một giải thuật dễ viết chương trình để nhanh chóng có
được kết quả, thời gian thực hiện chương trình không được đề cao vì dù sao thì chương
trình đó cũng chỉ sử dụng một vài lần mà thôi.
Tuy nhiên khi một chương trình được sử dụng nhiều lần thì thì yêu cầu tiết
kiệm thời gian thực hiện chương trình lại rất quan trọng đặc biệt đối với những chương
trình mà khi thực hiện cần dữ liệu nhập lớn do
đó yêu cầu (3) sẽ được xem xét một cách
kĩ càng. Ta gọi nó là hiệu quả thời gian thực hiện của giải thuật.
Thuật toán (giải thuật) - Algorithm
1.1.1.1
Định nghĩa thuật toán
Có rất nhiều các định nghĩa cũng như cách phát biểu khác nhau về định nghĩa
của thuật toán. Theo như cuốn sách giáo khoa nổi tiếng viết về thuật toán là
“Introduction to Algorithms” (Second Edition của Thomas H. Cormen, Charles E.
Leiserson, Ronald L. Rivest và Clifford Stein) thì thuật toán được định nghĩa như sau:
“một thuật toán là một thủ tục tính toán xác định (well-defined) nhận các giá trị hoặc
một tập các giá trị gọi là input và sinh ra ra một vài giá trị hoặc một tập giá trị được
gọi là output”.
2
Nói một cách khác các thuật toán giống như là các cách thức, qui trình để
hoàn thành một công việc cụ thể xác định (well-defined) nào đó. Vì thế một đoạn mã
chương trình tính các phần tử của dãy số Fibonaci là một cài đặt của một thuật toán cụ
thể. Thậm chí một hàm đơn giản để cộng hai số cũng là một thuật toán hoàn chỉnh,
mặc dù đó là một thuật toán đơn giản.
1.1.1.2
Đặc trưng của thuật toán
Tính đúng đắn: Thuật toán cần đảm bảo cho một kết quả đúng sau khi thực
hiện đối với các bộ dữ liệu đầu vào. Đây có thể nói là đặc trưng quan trọng nhất với một
thuật toán.
Tính dừng: thuật toán cần phải đảm bảo sẽ dừng sau một số hữu hạn bước.
Tính xác định: Các bước của thuật toán phải được phát biểu rõ ràng, cụ thể,
tránh gây nhập nhằng hoặc nhầm lẫn đối với người đọc và hiểu, cài đặt thuật toán.
Tính hiệu quả: thuật toán được xem là hiệu quả nếu như nó có khả năng giải
quyết hiệu quả bài toán đặt ra trong thời gian hoặc các điều kiện cho phép trên thực tế
đáp ứng được yêu cầu của người dùng.
Tính phổ quát: thuật toán được gọi là có tính phố quát (phổ biến) nếu nó có
thể giải quyết được một lớp các bài toán tương tự.
Ngoài ra mỗi thuật toán theo định nghĩa đều nhận các giá trị đầu vào được gọi
chung là các giá trị dữ liệu Input. Kết quả của thuật toán (thường là một kết quả cụ thể
nào đó tùy theo các bài toán và thuật toán cụ thể) được gọi là Output.
1.1.1.3
Biểu diễn thuật toán
Có nh
iều phương pháp biểu diễn thuật toán .Có thể biểu diễn thuật toán bằng
danh sách các bước, các bước được diễn đạt bằng ngôn ngữ thông thường và các ký
hiệu toán học. Có thể biểu diễn thuật toán bằng sơ đồ khối. Tuy nhiên, để đảm bảo tính
xác định của thuật toán như đã trình bày trên, thuật toán cần được viết trên các ngôn
ngữ lập trình. Một chương trình là sự biểu
diễn
của một thuật toán trong ngôn ngữ lập
trình đã chọn. Thông thường ta dùng ngôn ngữ lập trình Pascal, một ngôn ngữ thường
được chọn để trình bày các thuật toán trong sách báo. Ngôn ngữ thuật toán là ngôn ngữ
dùng để miêu tả thuật toán .Thông thường ngôn ngữ thuật toán bao gồm ba loại: Ngôn
ngữ liệt kê từng bước; Sơ đồ khối; Ngôn ngữ lập trình;
1.1.1.4
Phương pháp liệt kê từng bước
Ngôn ngữ liệt kê từng bước nội dung như sau:
Thuật
toán: Tên thuật toán và chức năng.