tailieunhanh - Bài giảng Cấu trúc dữ liệu: Chương 10 - Nguyễn Xuân Vinh

Bài giảng Cấu trúc dữ liệu - Chương 10: Phân tích thiết kế giải thuật trình bày cách tiếp cận từ bài toán đến chương trình, kiểu dữ liệu trừu tượng (abstract data types), kiểu dữ liệu - kiểu dữ liệu trừu tượng - cấu trúc dữ liệu. | PHÂN TÍCH THIẾT KẾ GIẢI THUẬT (Analisys & Design Algorithm) Nguyễn Xuân Vinh nguyenxuanvinh@ CẤU TRÚC DỮ LIỆU DATA STRUCTURES [214331] Nội dung Cách tiếp cận từ bài toán đến chương trình Kiểu dữ liệu trừu tượng (Abstract Data Type). Kiểu dữ liệu – Kiểu dữ liệu trừu tượng – Cấu trúc dữ liệu. 1. Mô hình hóa các bài toán Để giải một bài toán trong thực tế bằng máy tính ta phải bắt đầu từ việc xác định bài toán. "phải làm gì?" "làm như thế nào?" Hầu hết các bài toán là không đơn giản, không rõ ràng. Để giảm bớt sự phức tạp của bài toán thực tế hình thức hóa nó Bài toán thực tế Dữ liệu + Giải thuật Dữ kiện Kết quả Mô hình hóa Input Output Ví dụ: chọn lớp trưởng Yêu cầu: chọn người có điểm cao nhất làm lớp trưởng Đánh giá: Lập danh sách tất cả các học sinh trong lớp theo họ tên và điểm trung bình. Sắp thứ tự các học viên giảm dần theo điểm trung bình (học viên có ĐTB bằng nhau thì có cùng hạng). Chọn lọc lớp trưởng: Nếu chỉ có 1 người đứng đầu thì người đó làm lớp trưởng. Nếu | PHÂN TÍCH THIẾT KẾ GIẢI THUẬT (Analisys & Design Algorithm) Nguyễn Xuân Vinh nguyenxuanvinh@ CẤU TRÚC DỮ LIỆU DATA STRUCTURES [214331] Nội dung Cách tiếp cận từ bài toán đến chương trình Kiểu dữ liệu trừu tượng (Abstract Data Type). Kiểu dữ liệu – Kiểu dữ liệu trừu tượng – Cấu trúc dữ liệu. 1. Mô hình hóa các bài toán Để giải một bài toán trong thực tế bằng máy tính ta phải bắt đầu từ việc xác định bài toán. "phải làm gì?" "làm như thế nào?" Hầu hết các bài toán là không đơn giản, không rõ ràng. Để giảm bớt sự phức tạp của bài toán thực tế hình thức hóa nó Bài toán thực tế Dữ liệu + Giải thuật Dữ kiện Kết quả Mô hình hóa Input Output Ví dụ: chọn lớp trưởng Yêu cầu: chọn người có điểm cao nhất làm lớp trưởng Đánh giá: Lập danh sách tất cả các học sinh trong lớp theo họ tên và điểm trung bình. Sắp thứ tự các học viên giảm dần theo điểm trung bình (học viên có ĐTB bằng nhau thì có cùng hạng). Chọn lọc lớp trưởng: Nếu chỉ có 1 người đứng đầu thì người đó làm lớp trưởng. Nếu hơn 1 người tiến hành bốc thăm. Dữ liệu + Giải thuật Input Output Ví dụ: Tô màu bản đồ thế giới Phát biểu: Ta cần phải tô màu cho các nước trên bản đồ thế giới. Trong đó mỗi nước đều được tô một màu và hai nước láng giềng (cùng biên giới) thì phải được tô bằng hai màu khác nhau. Hãy tìm một phương án tô màu sao cho số màu sử dụng là ít nhất. Giải pháp mô hình hóa: Ta có thể xem mỗi nước trên bản đồ thế giới là một đỉnh của đồ thị, hai nước láng giềng của nhau thì hai đỉnh ứng với nó được nối với nhau bằng một cạnh. Bài toán lúc này trở thành bài toán tô màu cho đồ thị như sau: Mỗi đỉnh đều phải được tô màu, hai đỉnh có cạnh nối thì phải tô bằng hai màu khác nhau và ta cần tìm một phương án tô màu sao cho số màu được sử dụng là ít nhất. Ví dụ: Đèn giao thông Phát biểu: Cho một ngã năm trong đó: C và E là các đường một chiều theo chiều mũi tên Các đường khác là hai chiều. Hãy thiết kế một bảng đèn hiệu điều khiển giao thông tại ngã năm này một cách hợp lý Nghĩa là: phân chia các lối đi