Thảo luận về khái niệm thuật toán
- Người học đưa ra một số bài toán trong thực tế được giải quyết như quá trình thực hiện của một thuật toán.
- Phân tích các đặc trưng của thuật toán qua các ví dụ trên.
- Chọn một bài toán để biểu diễn thuật toán bằng một số phương pháp.
Thảo luận về tư tưởng thiết kế thuật toán chia để trị
- Người học tìm một số bài toán trong thực tế, sau đó thảo luận phân tích thành các bài toán nhỏ theo tư tưởng của thuật toán chi để trị.
- Nhận xét công việc thực hiện các bài toán nhỏ so với bài toán ban đầu
- Nhận xét về việc tổng hợp kết quả từ những bài toán nhỏ
=> Từ đó rút ra kết luận về sơ đồ chung của thuật toán chia để trị.
Thảo luận về độ phức tạp tính toán trong thuật toán chia để trị
- Phân tích độ phức tạp thuật toán của các bài toán con
- So sánh với độ phức tạp tính toán của bài toán ban đầu
=> Từ đó rút ra kết luận về ưu điểm của thuật toán chia để trị.
Các bài toán sử dụng phương pháp chia để trị
Các nhóm báo cáo các bài toán đã được phân công
Bài toán tìm kiếm nhị phân
* So sánh tìm kiếm tuần tự và tìm kiếm nhị phân:
- Nhắc lại phương pháp tìm kiếm tuần tự
- So sánh ưu nhược điểm của 2 phương pháp, chỉ rõ qua ví dụ cụ thể.
* Cài đặt thuật toán:
int tknp(int a[max],int x,int l, int r)
{
int mid;
if( l > r) return 0;
mid = (l+r)/2
if ( x == a[mid] ) return 1;
if ( x > a[mid] ) return tknp(a,x,mid+1,r);
return tknp(a,x,l,mid-1);
}
* Đánh giá độ phức tạp thuật toán:
a) Trường hợp tốt nhất: Tương ứng với sự tìm được y trong lần so sánh đầu tiên, tức là y= x[Middle] (y nằm ở vị trí giữa mảng)
=> Ta coù : Ttoát (n) = O(1)
b) Trường hợp xấu nhất: Độ phức tạp là O(log n)
Thật vậy, Nếu gọi T(n) là độ phức tạp của thuật toán , thì sau khi kiểm tra điều kiện ( x == a[giữa]) và sai thì gọi đệ qui thuật toán này với dữ liệu giảm nửa, nên thỏa mãn công thức truy hồi :
T(n) = 1 + T(n/2) với n>=2 và T(1) = 0
Bài toán mảng con lớn nhất
- Phát biểu bài toán
- Tư tưởng giải thuật
- Cài đặt
- Đánh giá độ phức tạp thuật toán
Thuật toán nhân 2 ma trận
- Phát biểu bài toán
- Tư tưởng giải thuật
- Cài đặt
- Đánh giá độ phức tạp thuật toán
Thuật toán sắp xếp
- Phát biểu bài toán
- Tư tưởng giải thuật
- Cài đặt
- Đánh giá độ phức tạp thuật toán
Bài toán hoán đổi
- Phát biểu bài toán
- Tư tưởng giải thuật
- Cài đặt
- Đánh giá độ phức tạp thuật toán
Nhắc lại các thuật toán khác và các bài toán
Trên cơ sở lý thuyết máy Turing, ta chia được các bài toán thành 2 lớp không giao nhau : Lớp giải được bằng thuật toán , và lớp không giải được bằng thuật toán.
Đối với lớp các bài toán giải được bằng thuật toán, dựa vào các đặc trưng của quá trình thiết kế của thuật toán, ta có thể chỉ ra một số các phương pháp thiết kế thuật toán cơ bản sau đây :
a) Phương pháp chia để trị. ( Divide-and-Conquer method ).
Ý tưởng là : Chia dữ liệu thành từng miền đủ nhỏ, giải bài toán trên các miền đã chia rồi tổng hợp kết quả lại .
Chẳng hạn như thuật toán Quicksort.
b) Phương pháp quay lui ( BackTracking method ).
Ý tưởng là: Tìm kiếm theo ưu tiên. Đối với mỗi bước thuật toán, ưu tiên theo độ rộng hay chiều sâu để tìm kiếm.
Chẳng hạn thuật toán giải bài toán 8 hậu.
c) Phương pháp tham lam ( Greedy Method ).
Ý tưởng là : Xác định trật tự xử lý để có lợi nhất, Sắp xếp dữ liệu theo trật tự
đó, rồi xử lý dữ liệu theo trật tự đã nêu. Công sức bỏ ra là tìm ra trật tự đó.
Chẳng hạn thuật toán tìm cây bao trùm nhỏ nhất (Shortest spanning Trees).
d) Phương pháp Quy hoạch động (Dynamic Programming method).
Phương pháp quy hoạch động dựa vào một nguyên lý, gọi là nguyên lý tối ưu của Bellman :
- Nếu lời giải của bài toán là tối ưu thì lời giải của các bài toán con cũng tối ưu. Phương pháp này tổ chức tìm kiếm lời giải theo kiểu từ dưới lên. Xuất phát từ các bài toán con nhỏ và đơn giản nhất, tổ hợp các lời giải của chúng để có lời giải của bài toán con lớn hơn...và cứ như thế cuối cùng được lời giải của bài toán ban đầu.
Chẳng hạn thuật toán “chiếc túi xách” (Knapsack).
Các bài tập
Viết chương trình cài đặt thuật toán tìm kiếm nhị phân
- Bài toán : Cho mảng a[1..n] được sắp xếp theo thứ tự không giảm và x. Tìm x trong mảng a, nếu có trả về giá trị 1, nếu không có trả về giá trị 0
- Phân t ích thuật toán :
Số x cho trước
+ Hoặc là bằng phần tử nằm ở vị trí giữa mảng a
+ Hoặc là nằm ở nửa bên trái (x < phần tử ở giữa mảng a )
+ Hoặc là nằm ở nửa bên phải (x > phần tử ở giữa mảng xa)
- Cài đặt thuật toán:
int tknp(int a[max],int x,int l, int r)
{
int mid;
if( l > r) return 0;
mid = (l+r)/2
if ( x == a[mid] ) return 1;
if ( x > a[mid] ) return tknp(a,x,mid+1,r);
return tknp(a,x,l,mid-1);
- Mở rộng:
Sửa đổi đoạn chương trình trên với yêu cầu trả về vị trí tìm được của x trong mảng a, nếu không tìm thấy trả về giá trị -1
Viết chương trình cài đặt thuật toán mảng con lớn nhất
- Bài toán:
Tìm giá trị Min, Max trong đoạn a[l..r] của mảng a[1..n].
- Phân tích thuật toán:
+ Tại mỗi bước, chia đôi đoạn cần tìm rồi tìm Min, Max của từng đoạn, sau đó tổng hợp lại kết quả.
+ Nếu đoạn chia chỉ có 1 phần tử thì Min =Max và bằng phần tử đó
Ví dụ:
MinMax(a,2,6,Min,Max) cho Min = 0, Max = 9 trong đoạn a[2..6]
- Cài đặt thuật toán:
Input : a[l..r], ( l <= r )
Output: Min = Min(a[l]..a[r])
Max = Max(a[l]..a[r])
Bài 3. Viết chương trình cài đặt thuật toán sắp xếp QuickSort
- Bài toán:
Dùng thuật toán QuickSort (QS) để sắp xếp các giá trị trong một mảng các số theo thứ tự,chẳng hạn tăng dần.
- Phân tích thuật toán:
Chọn ngẫu nhiên một phần tử x.
Duyệt dãy từ bên trái ( theo chỉ số i ) trong khi còn ai < x.
Duyệt dãy từ bên phải ( theo chỉ số j ) trong khi còn aj > x.
Đổi chỗ ai và aj nếu hai phía chưa vượt qua nhau.
. . . tiếp tục qúa trình duyệt và đổi chỗ như trên trong khi hai phía còn chưa vượt qua nhau ( tức là còn có i = j).
Kết qủa phân hoạch dãy thành 3 phần :
+ ak <= x với k = 1, .., j (Dãy con thấp);
+ am >= x với với m = i, ...,n (Dãy con cao);
+ ah = x với h = j+1, …, i+1
(Vì thế phương pháp này còn gọi là phương pháp sắp xếp bằng phân hoạch)
Tiếp tục phân hoạch cho phần trái (dãy con thấp nhỏ hơn x), cho phần phải ( lớn hơn x) . . . cho đến khi các phân hoạch chỉ còn lại một phần tử, là sắp xếp xong.
Thuật toán thể hiện ý tưởng đệ qui và cách thiết kế chia để trị.
- Thuật toán QuickSort
Input : a[1..n]
Output : a[1..n] không giảm.
BÀI TOÁN THUẬT TOÁN NHÁNH CẬN
Bài 1 :
Có n đồ vật, mỗi vật i đặc trưng bởi trọng lượng wi và giá trị sử dụng vi, với mọi i thuộc {1,..,n}. Cần chọn các vật này đặt vào một chiếc túi xách có giới hạn trọng lượng m, sao cho tổng giá trị sử dụng các vật được chọn là lớn nhất.
Bài 2 :
Cho 3 ký tự A, B, C và n là một số nguyên dương.
Xác định chuỗi tạo ra từ 3 ký tự trên, với chiều dài n, thỏa điều kiện không có 2 chuỗi con liên tiếp nào giống nhau và sao cho số ký tự B là ít nhất.
Bài 3:
Tìm lời giải tối ưu cho bài toán:
Bài 4:
Giả sử có n công việc và n thợ. Chi phí trả cho người thợ i để làm công việc
j là Cij . Mỗi công việc chỉ do một thợ thực hiện và ngược lại.
Tìm cách thuê các thợ làm việc sao cho tổng chi phí là nhỏ nhất.
- Thiết kế và đánh giá thuật toán
- Lời nói đầu
- Bài 1: Thuật toán và độ phức tạp
- Bài 2:Phân tích thuật toán
- Bài 3: Cơ bản về thuật toán chia để trị
- Bài 4: Các bài toán sử dụng thuật toán chia để trị ( Divid and Conquer )
- Bài 5: Cơ bản về thuật toán Quay Lui (Back Tracking)
- Bài 6: Cơ bản về thuật toán nhánh cận và các bài toán
- Bài 7: Cơ bản về thuật toán Tham Lam
- Bài 8: Cơ bản về thuật toán Quy hoạch động
- Bài 9: Các bài toán sử dụng thuật toán Quy hoạch động
- Bài 10: Bài tập và tổng kết
- Tài liệu tham khảo
