tailieunhanh - Giáo trình - Một số vấn đề về thuật toán - chương 4

Chương 4: Phương pháp chia để trị Từ thời Đế chế La Mã đã áp dụng hiệu quả một nguyên lí chia để trị. Với tư tưởng bành trướng rộng lớn về đất đai và lãnh thổ, những nhà chính trị thời đó đã chia đất đai chiếm được thành những miền nhỏ và áp đặt ách cai trị một cách dễ dàng tại các miền nhỏ ấy | ChtftMq 4 PHƯƠNG PHÁP CHIA ĐỂ TRỊ . Thuật toán sắp xếp trộn .91 . Thiết kế thuật toan .92 . Phân tích thuật toán . 95 . Thuật toản nhân hai ma . Cách tiếp cận chia để trị . 99 . Cách nhân hai ma trận của . Những thuật toán dựa trên phương pháp Strassenlơ4 . Nhân nhũng số nguyên lởn .107 . Phương pháp nhân nhanh hai số nguyên . 107 . Thuật toán nhân hai số . Tính toán kí hiệu trên những đa . Nhân hai đa thức cùng . Nhân hai đa thức khác . Chọn phẩn tử rihô bất . Thuật toán lựa . Thuật toán chọn với trục điểm . Một ứng dụng cho xếp lịch thỉ đấu thế . Bài tập . . . . .130 Từ thời Đế chế La Mã đã áp dụng hiệu quạ một nguyên lí chia để trị. Với tư tưởng bành trướng rông lớn về đất đai và lãnh thổ những nhà chính trị thời đó đà chia đất đai chiếm được thành những miền nhỏ và áp đặt ách cai trị một cách dễ dàng tại các miền nhỏ này Ngày nay phương pháp này vẫn còn được áp dụng trong nhiều lữih vực của đời sống Phương pháp này cũng rất hiệu quả khi ta đi thiết kê thuật toán cho những bài toán cỡ lớn phúc tạp. Từ những bài toán cỏ đầu vào râ t lớn ta chia ra thành những phần nhỏ hơn và dí tìm lời giải cho các bài toán nhỏ riêng biệt này rồi sau đó tổng hợp những nghiêm bài toán nhồ thảnh nghiêm bài toán toàn cục. Với tư tưởng như vậy một bài toán ta có thể phải chia nhỏ nhiều lần chia cho đến khi bài toán được . Thuật toán sắp xếp trộn 91 chia nhỏ chỉ còn lại rất nhỏ và lời giầi khi đó là hiển nhiên. Tóm lạt những yếu tố chính của phương pháp giải chia đểtrị gồm 1. Chia bài toán Chia bài toán thành những bàỉ toán nhỏ hơn. 2. Trị bài toán nhỏ Giải những bài toán nhỏ này. 3. Kết hợp các nghiệm Kết hợp những nghiệm của bài toán nhỏ cho nghiêm của bài toán lớn. Có rất nhiều bài toán tính toán có thể giải hiệu quả bằng phương pháp chia để trị. Phương pháp này râ t mạnh khi thiết kế thuật toán thậm chí có người .