Bài giảng Thiết kế và đánh giá thuật toán: Chia để trị - TS. Lê Nguyên Khôi

Bài giảng "Thiết kế và đánh giá thuật toán: Chia để trị" trình bày các nội dung: Kỹ thuật thiết kế, sắp xếp gộp, tính lũy thừa, tìm kiếm nhị phân, tính số Fibonacci, tháp Hanoi, nhân ma trận, thuật toán Strassen. Mời các bạn cùng tham khảo.
Nội dung trích xuất từ tài liệu:
Bài giảng Thiết kế và đánh giá thuật toán: Chia để trị - TS. Lê Nguyên KhôiThiết Kế & Đánh Giá Thuật ToánChia Để TrịTS. Lê Nguyên KhôiTrường Đại Học Công Nghệ - ĐHQGHNNội DungKỹ thuật thiết kế Sắp xếp gộp Tính lũy thừa Tìm kiếm nhị phân Tính số Fibonacci Tháp Hanoi Nhân ma trận Thuật toán Strassen1Kỹ Thuật Thiết Kế Chia Để TrịChia bài toán lớn thành các bài toán nhỏBài toán nhỏ đơn giản, giải trực tiếp Nếu không tiếp tục chia nhỏ bài toán conGộp lời giải của các bài toán con2Sắp Xếp Gộp (Merge Sort)Chia: chia đôi mảngTrị: Sử dụng đệ quy sắp xếp 2 mảng conGộp: gộp 2 mảng với thời gian tuyến tínhMergeSort (, 1, )1if = 1 return2MergeSort (, 1, /2 )3MergeSort (, /2 + 1, )4Merge (, 1, /2 , /2 + 1, )() = 2(/2) + Θ()chia và gộp# bài toán conđộ lớn bài toán con3Định Lý Tổng Quát – (nhắc lại) = / + ()Nếu ∈ ( ) với hằng số > 0 ∈ ( )2. Nếu ∈ ( ) ∈ ( log )3. Nếu ∈ ( # ) với hằng số > 0và thỏa mãn / ≤ %() với % < 1 ∈ (())Sắp xếp gộp: = 2, = 2 ⇒ = ( ) = ⇒ trường hợp 2 ⇒ () ∈ ( log )1.4