tailieunhanh - Bài giảng Phân tích và thiết kế thuật toán: Chia để trị - Phạm Thế Bảo

Trong phân tích thuật toán, để giải quyết một bài toán kích thước n, ta chia bài toán này thành một số bài toán con có kích thước nhỏ hơn. Giải các bài toán con này rồi tổng hợp kết quả lại để được lời giải ban đầu. Trong bài giảng này sẽ trình bày một số bài toán chia để trị tiêu biểu như: MergeSort và QuickSort, nhân số nguyên lớn, xếp lịch thi đấu thể thao, bài toán con cân bằng. . | 14 04 2008 CHIA ĐỂ TRỊ DIVIDE AND CONQUER Phạm Thế Bảo Khoa Toán - Tin học Trường Đại học Khoa học Tự nhiên Nội dung Kỹ thuật quan trọng được áp dụng rộng rãi để thiết kế các giải thuật có hiệu quả. Để giải quyết một bài toán kích thước n ta chia bài toán này thành một số bài toán con có kích thước nhỏ hơn. Giải các bài toán connày rồi tổng hợp kết quả lại để được lời giải ban đầu. Những bài toán con này cũng có thể được chia thành các bài toán có kích thước nhỏ hơn nữa để giải quyết. Quá trình này sẽ đưa đến những bài toán mà lời giải là hiển nhiên hay dễ dàng thực hiện. Ta gọi những bài toán này là bài toán cơ sở. Phạm Thế Bảo 1 14 04 2008 K K X J Ấ j X . r J X 1 Ẳ Một sô bài toán tiêu biêu MergeSort và Quicksort Nhân sô nguyên lớn Xếp lịch thi đấu thê thao Bài toán con cân bằng Phạm Thế Bảo MergeSort và QuickSort Chia tập dữ liệu làm 2 tập con quá trình chia đến khi chỉ còn 01 phần tử - dừng bài toán cơ sở tổng hợp 2 tập con bằng cách trộn có thứ tự - tập dữ liệu được sắp xếp. Giông MergeSort nhưng cần phần tử cầm canh đứng giữa đê chia thành 2 tập con một tập sẽ có các phần tử có giá trị nhỏ hơn hay bằng tập còn lại sẽ có các phần tử có giá trị lớn hơn. Phạm Thế Bảo 2 14 04 2008 Bài toán nhân hai số nguyên lớn Trong các ngôn ngữ lập trình kiểu dữ liệu số nguyên đều có miền giá trị hạn chế ví dụ Pascal C số nguyên từ -32768 đến 32767 Khi gặp ứng dụng cần số nguyên lớn hơn hàng chục hay hàng trăm chữ số chúng ta phải đi xây dựng cấu trúc dữ liệu số nguyên lớn. Các thao tác đi kèm là cộng trừ nhân . Chúng ta xem xét cách nhân 02 số nguyên lớn có n chữ số sao cho hiệu quả. Phạm Thế Bảo Nếu chúng ta dùng cách nhân thông thường nghĩa là từng chữ số nhân với nhau rồi cộng lại thì chi phí là O n2 . Áp dụng kỹ thuật chia để trị. Ta chia 02 số nguyên X Y thành các số nguyên lớn có n 2 chữ số X A10n 2 B và Y C10n 2 D Ví dụ A 1234 thì A 12x102 34 Khi đó AC10n AD BC 10n 2 BD. Giống như trên ta lại chia tiếp tục để có bài toán cơ sở dễ dàng thực hiện. Phạm Thế Bảo