"Bài giảng Cấu trúc dữ liệu và giải thuật – Bài 1: Giới thiệu chung" trình bày đôi nét về khái niệm về cấu trúc dữ liệu và giải thuật, giải thuật, dữ liệu và các cấu trúc dữ liệu, biểu diễn giải thuật, độ phức tạp của giải thuật.
AMBIENT/
Chủ đề:
Nội dung Text: Bài giảng Cấu trúc dữ liệu và giải thuật – Bài 1: Giới thiệu chung
- Cấu trúc dữ liệu và giải thuật
Bài 1. Giới thiệu chung
Lecturer: Dr. Ngo Huu Phuc
Tel: 0438 326 077
Mob: 098 5696 580
Email: ngohuuphuc76@gmail.com
1 @Copyrights by Dr. Ngo Huu Phuc, Le Quy Don Technical University
- Tài liệu tham khảo
Mastering Algorithms with C, Kyle Loudon, 1999.
Introduction to Algorithms, Thomas H. Cormen, Charles
E. Leiserson, Ronald L. Rivest and Clifford Stein, The MIT
Press © 2001.
Data Structures, Algorithms, and Object-Oriented
Programming. NXB McGraw Hill; Tác giả Gregory
Heilleman -1996
Cấu trúc dữ liệu và giải thuật, Đỗ Xuân Lôi.
2 @Copyrights by Dr. Ngo Huu Phuc, Le Quy Don Technical University
- Bài 1. Giới thiệu
Nội dung:
1.0. Đôi nét về khái niệm.
1.1. Giải thuật.
1.2. Dữ liệu và các cấu trúc dữ liệu.
1.3. Biểu diễn giải thuật.
1.4. Độ phức tạp của giải thuật.
Tham khảo:
Elliz Horowitz - Fundamentals of data structures,
Chapter 1: Introduction
3 @Copyrights by Dr. Ngo Huu Phuc, Le Quy Don Technical University
- 1.0. Đôi nét về khái niệm
Để giải một bài toán, bắt đầu từ câu hỏi “phải làm gì?”, sau
đó trả lời câu hỏi “làm như thế nào?” → đó là cách tiếp cận
đến giải thuật và cấu trúc dữ liệu.
Các bài toán trong thực tế không dễ giải bằng cách hiểu
thông thường và để giảm độ phức tạp, trong nhiều trường
hợp có thể mô hình hóa bài toán.
Từ việc mô hình hóa, trong thực tế thấy rằng có nhiều bài
toán có cùng một mô hình hóa.
4 @Copyrights by Dr. Ngo Huu Phuc, Le Quy Don Technical University
- 1.0.1. Một số ví dụ (1)
Ví dụ 1: Tô màu bản đồ thế giới.
Yêu cầu:
Ta c ần phải tô màu cho các nước trên bản đồ thế giới.
Trong đó mỗi nước đều được tô một màu.
Hai nước láng giềng (cùng biên giới) thì phải được tô bằng
hai màu khác nhau.
Hãy tìm một phương án tô màu sao cho số màu sử dụng là
ít nhất.
5 @Copyrights by Dr. Ngo Huu Phuc, Le Quy Don Technical University
- 1.0.2. Một số ví dụ (2)
Hướng giải quyết bằng mô hình hóa:
Ta có th ể xem mỗi nước trên bản đồ thế giới là một đỉnh của đồ thị.
Hai nước láng giềng của nhau thì hai đỉnh ứng với nó được nối với
nhau bằng một cạnh.
Bài toán lúc này trở thành bài toán tô màu cho đồ thị như sau:
Mỗi đỉnh đều phải được tô màu.
Hai đỉnh có cạnh nối thì phải tô bằng hai màu khác nhau.
Cần tìm một phương án tô màu sao cho số màu được sử dụng là ít
nhất.
6 @Copyrights by Dr. Ngo Huu Phuc, Le Quy Don Technical University
- 1.0.3. Một số ví dụ (3)
Ví dụ 2: Đèn giao thông
Cho một ngã năm như hình 1.
C và E là các đường một chiều theo chiều mũi tên.
Các đường khác là hai chiều.
Hãy thiết kế một bảng đèn hiệu điều khiển giao thông tại ngã năm này
một cách hợp lý: sao cho:
Phân chia các lối đi tại ngã năm này thành các nhóm
Mỗi nhóm gồm các lối đi có thể cùng đi đồng thời nhưng không xảy ra tai nạn
giao thông (các hướng đi không cắt nhau),
Và số lượng nhóm là ít nhất có thể được.
7 @Copyrights by Dr. Ngo Huu Phuc, Le Quy Don Technical University
- 1.0.4. Hướng giải quyết (VD2)
Ta có thể xem đầu vào (input) của bài toán là tất cả các lối
đi tại ngã năm này.
Đầu ra (output) của bài toán là các nhóm lối đi có thể đi
đồng thời mà không xảy ra tai nạn giao thông.
Mỗi nhóm sẽ tương ứng với một pha điều khiển của đèn
hiệu, vì vậy ta phải tìm kiếm lời giải với số nhóm là ít nhất
để giao thông không bị tắc nghẽn vì phải chờ đợi quá lâu.
8 @Copyrights by Dr. Ngo Huu Phuc, Le Quy Don Technical University
- 1.0.4. Hướng giải quyết (VD2) (t)
Trước hết ta nhận thấy rằng tại ngã năm này có 13 lối đi: AB, AC, AD,
BA, BC, BD, DA, DB, DC, EA, EB, EC, ED.
Thể hiện các lối có thể đi đồng thời.
Ví dụ cặp AB và EC có thể đi đồng thời, nhưng AD và EB thì không, vì
các hướng giao thông cắt nhau.
Sử dụng sơ đồ trực quan:
Tên của 13 lối đi được viết lên mặt phẳng,
Hai lối đi nào nếu đi đồng thời sẽ xảy ra đụng nhau (tức là hai hướng đi cắt
qua nhau) ta nối lại bằng một đoạn thẳng.
Ta sẽ có một sơ đồ như hình 2. Như vậy, trên sơ đồ này, hai lối đi có cạnh nối
lại với nhau là hai lối đi không thể cho đi đồng thời.
9 @Copyrights by Dr. Ngo Huu Phuc, Le Quy Don Technical University
- Hình 2
10 @Copyrights by Dr. Ngo Huu Phuc, Le Quy Don Technical University
- 1.0.4. Hướng giải quyết (VD2) (t)
Với cách biểu diễn như vậy ta đã có một đồ thị (Graph), tức là ta đã mô
hình hoá bài toán giao thông ở trên theo mô hình toán là đồ thị.
Mỗi lối đi trở thành một đỉnh của đồ thị, hai lối đi không thể cùng đi đồng
thời được nối nhau bằng một đoạn ta gọi là cạnh của đồ thị.
Bây giờ ta phải xác định các nhóm, với số nhóm ít nhất, mỗi nhóm gồm
các lối đi có thể đi đồng thời, nó ứng với một pha của đèn hiệu điều
khiển giao thông.
Giả sử rằng, ta dùng màu để tô lên các đỉnh của đồ thị này sao cho:
Các lối đi cho phép cùng đi đồng thời sẽ có cùng một màu: Dễ dàng nhận
thấy rằng hai đỉnh có cạnh nối nhau sẽ không được tô cùng màu.
Số nhóm là ít nhất: ta phải tính toán sao cho số màu được dùng là ít nhất.
11 @Copyrights by Dr. Ngo Huu Phuc, Le Quy Don Technical University
- 1.0.4. Hướng giải quyết (VD2) (t)
"Tô màu cho đồ thị ở hình 2 sao cho:
Hai đỉnh có cạnh nối với nhau (hai còn gọi là hai đỉnh kề nhau) không
cùng màu.
Số màu được dùng là ít nhất."
Nhận xét:
Hai bài toán thực tế “tô màu bản đồ thế giới” và “đèn giao
thông” xem ra rất khác biệt nhau nhưng sau khi mô hình
hóa, chúng thực chất chỉ là một, đó là bài toán “tô màu đồ
thị”.
12 @Copyrights by Dr. Ngo Huu Phuc, Le Quy Don Technical University
- 1.0.5. Thiết kế giải thuật để giải bài toán “ tô màu đồ thị”
Bài toán “tô màu đồ thị không có giải thuật tối ưu.
Để có kết quả tối ưu, cần sử dụng phương pháp vét cạn.
Phương pháp này tốt khi số phép thử là nhỏ.
Thông thường, để đơn giản hóa, có thể:
Thêm thông tin vào bài toán để đồ thị có một số tính chất đặc biệt và
dùng các tính chất đặc biệt này ta có thể dễ dàng tìm lời giải, hoặc
Thay đổi yêu cầu bài toán một ít cho dễ giải quyết, nhưng lời giải tìm
được chưa chắc là lời giải tối ưu.
Cách này được xem là "Cố gắng tô màu cho đồ thị bằng ít
màu nhất một cách nhanh chóng".
Một giải pháp như thế gọi là một HEURISTIC.
13 @Copyrights by Dr. Ngo Huu Phuc, Le Quy Don Technical University
- 1.0.6. Giải thuật HEURISTIC
HEURISTIC cho bài toán tô màu đồ thị, thường gọi là giải
thuật "háu ăn" (GREEDY) là:
Chọn một đỉnh chưa tô màu và tô nó bằng một màu mới C nào đó.
Duyệt danh sách các đỉnh chưa tô màu. Đối với một đỉnh chưa tô
màu, xác định xem nó có kề với một đỉnh nào được tô bằng màu C đó
không. Nếu không có, tô nó bằng màu C đó.
Ý tưởng của Heuristic này là hết sức đơn giản: dùng một
màu để tô cho nhiều đỉnh nhất có thể được (các đỉnh được
xét theo một thứ tự nào đó), khi không thể tô được nữa với
màu đang dùng thì dùng một màu khác. Như vậy ta có thể
"hi vọng" là số màu cần dùng sẽ ít nhất
14 @Copyrights by Dr. Ngo Huu Phuc, Le Quy Don Technical University
- Ví dụ về HEURISTIC
Ví dụ: Tô mầu đồ thị hình 3
Tô theo GREEDY
(xét lần lượt theo số thứ tự các đỉnh)
1: đỏ; 2: đỏ; 3: xanh;4: xanh; 5: vàng
Tối ưu
(thử tất cả các khả năng)
1,3,4 : đỏ; 2,5 : xanh
15 @Copyrights by Dr. Ngo Huu Phuc, Le Quy Don Technical University
- Giải bài toán giao thông bằng HEURISTIC
Trở lại bài toán giao thông ở trên và áp dụng HEURISTIC
Greedy cho đồ thị trong hình 2 (theo thứ tự các đỉnh đã liệt
kê ở trên), ta có kết quả:
Tô màu xanh cho các đỉnh: AB,AC,AD,BA,DC,ED
Tô màu đỏ cho các đỉnh: BC,BD,EA
Tô màu tím cho các đỉnh: DA,DB
Tô màu vàng cho các đỉnh: EB,EC
Chú ý: 4 màu là 1 lời giải, nhưng chưa kết luận được có tối
ưu hay không.
16 @Copyrights by Dr. Ngo Huu Phuc, Le Quy Don Technical University
- Chứng minh về số mầu cần thiết để tô là 4?
Định lý:
Một đồ thị trong đó có k đỉnh mà mỗi cặp đỉnh bất kỳ trong k
đỉnh này đều được nối nhau thì không thể dùng ít hơn k
màu để tô cho đồ thị.
Chứng minh:
Đồ thị trong hình I.2 có 4 đỉnh: AC,DA,BD,EB mà mỗi cặp đỉnh
bất kỳ đều được nối nhau vậy đồ thị hình I.2 không thể tô
với ít hơn 4 màu. Điều này khẳng định rằng lời giải vừa tìm
được ở trên trùng với lời giải tối ưu.
17 @Copyrights by Dr. Ngo Huu Phuc, Le Quy Don Technical University
- 1.1. Các giải thuật
1.1.1. Thế nào là giải thuật.
1.1.2. Ví dụ về giải thuật: Sắp xếp một dãy.
1.1.3. Định nghĩa giải thuật.
18 @Copyrights by Dr. Ngo Huu Phuc, Le Quy Don Technical University
- 1.1.1. Thế nào là giải thuật?
Giải thuật là các ý tưởng đằng sau chương trình trên máy tính.
Giải thuật không thay đổi khi viết trên các ngôn ngữ khác nhau.
Giải thuật phải giải quyết được các vấn đề tổng quát cũng như
các vấn đề riêng của một bài toán.
Giải thuật cần có đầu vào và đầu ra rõ ràng.
19 @Copyrights by Dr. Ngo Huu Phuc, Le Quy Don Technical University
- 1.1.2. Ví dụ về giải thuật: Sorting
Input: Một dãy số gồm N phần tử.
a[1], a[2], … , a[n].
Output: Sắp xếp lại dãy số trên
dãy số trên có dạng:
a[1]
Thêm vào BST
Báo xấu
Download
Vui lòng tải xuống để xem tài liệu đầy đủ
