Bài tập Nhập môn Thuật toán

PHẦN 1. CÁC KHÁI NIỆM CƠ BẢN $1. THUẬT TOÁN VÀ ĐỘ PHỨC TẠP THUẬT TOÁN Bài 1. Xác định số phép tính so sánh nhiều nhất có thể trong thuật toán tìm phần tử lớn nhất của một dãy n số thực cho trước. Bài 2. Xác định số phép tính so sánh nhiều nhất có thể trong thuật toán để xếp lại một dãy có n số thực theo thứ tự tăng dần. Bài 3. Mô tả các thuật toán dưới đây bằng ngôn ngữ tự nhiên: a) Thuật toán tìm phần tử lớn nhất của một dãy hữu hạn số thực. b) Thuật toán tìm phần tử bé nhất của một dãy hữu hạn số thực.. c) Thuật toán xếp lại một dãy theo thứ tự tăng dần. Bài 4. Viết các thuật toán bằng ngôn ngữ tựa Pascal: a) Thuật toán tìm phần tử lớn nhất của một dãy hữu hạn số thực. b) Thuật toán tìm phần tử bé nhất của một dãy hữu hạn số thực. c) Thuật toán xếp lại một dãy theo thứ tự tăng dần. Bài 5. Tính thời gian thực hiện của các đoạn chương trình sau: a) Tính tổng của các số {1} Sum := 0; {2} for i:=1 to n do begin {3} readln(x); {4} Sum := Sum + x; end; b) Tính tích hai ma trận vuông cấp n C = A*B: {1} for i := 1 to n do {2} for j := 1 to n do begin {3} c[i,j] := 0; {4} for k := 1 to n do {5} c[i,j] := c[i,j] + a[i,k] * b[k,j]; end; Bài tập khác: 1-2 trang 14,15 (Giáo trình Nhập môn thuật toán) $2. MỘT SỐ THUẬT TOÁN CƠ BẢN Bài 6. Cho một mảng n số nguyên được sắp thứ tự tăng. Viết hàm tìm một số nguyên trong mảng đó theo phương pháp tìm kiếm nhị phân, nếu tìm thấy thì trả về TRUE, ngược lại trả về FALSE. Sử dụng hai kĩ thuật là đệ quy và vòng lặp. Với mỗi kĩ thuật hãy viết một hàm tìm và tính thời gian thực hiện của hàm đó. Bài 7. Xét công thức truy toán để tính số tổ hợp chập k của n như sau: a) Viết một hàm đệ quy để tính số tổ hợp chập k của n. b) Tính thời gian thực hiện của giải thuật nói trên. Bài tập khác: 1-4 trang 22 (Giáo trình Nhập môn thuật toán) 1-4 trang 27 (Giáo trình Nhập môn thuật toán) PHẦN 2. CÁC CHIẾN LƯỢC THIẾT KẾ THUẬT TOÁN $1. CHIA ĐỂ TRỊ Bài 8. Sơ đồ chung của các thuật toán chia để trị. Phân tích sự hoạt động của sơ đồ này với thuật toán tìm kiếm nhị phân. Bài 9. Trình bày thuật toán chia để trị với các bài toán “Cho mảng A cỡ n, chúng ta cần tìm giá trị lớn nhât (max) và nhỏ nhất (min) của mảng này”: Yêu cầu: Bài toán con cơ sở. Viết mã giả cho các thủ tục chính. Độ phức tạp tính toán. Phân tích trên các ví dụ cụ thể Bài 10. Phân tích giải thuật MergeSort, QuickSort theo tư tưởng chia để trị: Yêu cầu: Mô tả bằng ngôn ngữ tự nhiên. Các bước của thuật toán Cách phân chia bài toàn thành các bài toán con Tổng hợp lời giải bằng đệ quy. Minh họa trên các ví dụ. Độ phức tính toán. Bài 11. Xếp lịch thi đấu thể thao. Sắp xếp lịch thi đấu thể thao theo thể thức đấu vòng tròn 1 lượt cho n cầu thủ. Mỗi cầu thủ phải đấu với các cầu thủ khác, và mỗi cầu thủ chỉ đấu nhiều nhất một trận mỗi ngày. Yêu cầu là xếp một lịch thi đấu sao cho số ngày thi đấu là ít nhất. Bài tập khác: 1-3 trang 46, 10 trang 48 (Giáo trình Nhập môn thuật toán) $2. QUY HOẠCH ĐỘNG Bài 12. Sơ đồ chung của các giải thuật quy hoạch động Bài toán con cơ sở. Phân chia thành các bài toán con tối ưu. Giải các bài toán con và lưu lại kết quả. Phân tích sự giống khác nhau giữa các giải thuật đệ quy và giải thuật quy hoach động, từ đó nêu ra hiệu quả của quy hoạch động trên một ví dụ cụ thể (Chẳng hạn so sánh giải thuật đệ quy thông thường và giải thuật quy hoạch động tính số Fibonaci thứ n với n=5). Bài 13. Trình bày các giải thuật quy hoạch động giải các bài toán sau: Phát biểu bài toán (INPUT, OUTPUT) Cơ sở của quy hoạch động (Các bài toán con cơ sở) Công thức truy hồi (xây dựng công thức) Giải thuật (mã giả). Phương pháp truy vết (lưu vết trong quá trình tìm lời giải tối ưu). Đánh giá độ phức tạp. Giải và phân tích trên một ví dụ cụ thể. 13.1. Dãy con đơn điệu tăng dài nhất. Cho dãy số nguyên A = a1, a2, ..., an. (n <=10000, -10000 < ai < 10000). Một dãy con của A là một cách chọn ra trong A một số phần tử giữ nguyên thứ tự. Như vậy A có 2n dãy con. Yêu cầu: Tìm dãy con đơn điệu tăng của A có dộ dài lớn nhất. Ví dụ: A = (1, 2, 3, 4, 9, 10, 5, 6, 7, 8). Dãy con đơn điệu tăng dài nhất là: (1, 2, 3, 4, 5, 6, 7, 8). 13.2. Tìm dãy con chung của hai dãy số. Xét bài toán sau: Cho hai dãy số nguyên a = (a1,, am) và b = (b1,bn), ta cần tìm dãy số nguyên c = (c1,, ck) sao cho c là dãy con của cả a và b, và c là dài nhất có thể được. Ví dụ, nếu a = (3, 5, 1, 3, 5, 5, 3) và b = (1,5,3,5,3,1) thì dãy con chung dài nhất là c = (5,3,5,3) hoặc c = (1,3,5,3) hoặc c = (1,5,5,3). 13.3. Biến đổi xâu. Cho xâu ký tự X, xét 3 phép biến dổi: Insert(i, C): i là số, C là ký tự: Phép Insert chèn ký tự C vào sau vị trí i của xâu X. Replace(i, C): i là số, C là ký tự: Phép Replace thay ký tự tại vị trí i của xâu X bởi ký tự C. Delete(i): i là số, Phép Delete xoá ký tự tại vị trí i của xâu X. Yêu cầu: Cho truớc xâu Y, hãy tìm một số ít nhất các phép biến dổi trên dể biến xâu X thành xâu Y. 13.4. Đường đi dài nhất. Cho một bảng A kích thuớc m x n, trên dó ghi các số nguyên. Một nguời xuất phát tại ô nào dó của cột 1, cần sang cột n (tại ô nào cung duợc). Quy tắc: Từ ô A[i, j] chỉ duợc quyền sang một trong 3 ô A[i, j + 1]; A[i - 1, j + 1]; A[i + 1, j + 1]. Hãy tìm vị trí ô xuất phát và hành trình di từ cột 1 sang cột n sao cho tổng các số ghi trên duờng di là lớn nhất. A 1 2 6 7 9 7 6 5 6 7 1 2 3 4 2 4 7 8 7 6 13.5. Tam giác số. 13.6. Dãy con có tổng chia hết cho k. Cho một dãy gồm n ( n = 1000) số nguyên duong A1, A2, ..., An và số nguyên duong k (k = 50). Hãy tìm dãy con gồm nhiều phần tử nhất của dãy dã cho sao cho tổng các phần tử của dãy con này chia hết cho k. $3. THUẬT TOÁN THAM LAM Bài 1. Sơ đồ chung của thuật toán Dạng chung của các bài toán có thể chọn cho giải thuật tham lam (một phương án của bài toán gồm nhiều thành phần) Tiêu chuẩn để lựa chọn một thành phần trong mỗi bước của giải thuật tham lam là gì? Bài 2. Trình bày giải thuật tham lam giải các bài toán : 2.1. Tô màu đồ thị. 2.2. Ghi dữ liệu vào 2 đĩa. Có 2 đĩa cùng dung lượng L đơn vị nhớ và n chương trình cần tương ứng d1, d2,, dn đơn vị nhớ để lưu trữ. Hãy tìm cách (thuật toán) ghi những chương trình trên vào 2 đĩa sao cho số lượng chương trình được ghi là nhiều nhất. 2.3. Tổng các phần tử lớn nhất trên ma trận. Cho ma trận vuông A bậc n với các hệ số không âm. Cần tìm tập con các phần 2.4. Tổ chức lịch thi công công việc trên các máy. 2.5. Cây khung nhỏ nhất trên đồ thị G= theo Prim và Kruskal. 2.6. Bài toán về các đoạn thẳng không giao nhau. Đầu vào : Cho họ các đoạn thẳng mở C={(a1,b1),,(an,bn)} Đầu ra : Tập các đoạn thẳng không giao nhau có lực lượng lớn nhất. Ứng dụng thực tế : Bài toán xếp thời gian biểu cho các hội thảo, bài toán phục vụ khách hành trên một máy, bài toán lựa chọn hành động (Ví dụ có n lời mời dự tiệc bắt đầu bởi ai kết thúc bởi bi, hãy lựa chọn sao cho đi được nhiều tiệc nhất).