...

Bài giảng Cấu trúc dữ liệu và giải thuật

Tác giả: Đại học Hàng Hải

Thể loại: Lịch sử - Chiến tranh

Người đăng sách: namnx228@gmail.com

Ngôn ngữ: Việt Nam

Giới thiệu:
Ðể 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. Nhiều thời gian và công sức bỏ ra để xác định bài toán cần giải quyết, tức là phải trả lời rõ ràng câu hỏi "phải làm gì?" sau đó là "làm nhƣ thế nào?". Thông thƣờng, khi khởi đầu, hầu hết các bài toán là không đon 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ế, ta phải hình thức hóa nó, nghĩa là phát biểu lại bài toán thực tế thành một bài toán hình thức (hay còn gọi là mô hình toán). Có thể có rất nhiều bài toán thực tế có cùng một mô hình toán. Ví dụ : Tô màu bản đồ thế giới. 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. 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. Ðối với một bài toán đã đƣợc hình thức hoá, chúng ta có thể tìm kiếm cách giải trong thuật ngữ của mô hình đó và xác định có hay không một chƣong trình có sẵn để giải. Nếu không có một chƣơng trình nhƣ vậy thì ít nhất chúng ta cũng có thể tìm đƣợc những gì đã biết về mô hình và dùng các tính chất của mô hình để xây dựng một giải thuật tốt. Khi đã có mô hình thích hợp cho một bài toán ta cần cố gắng tìm cách giải quyết bài toán trong mô hình đó. Khởi đầu là tìm một giải thuật, đó là một chƣỗi hữu hạn các chỉ thị (instruction) mà mỗi chỉ thị có một ý nghĩa rõ ràng và thực hiện đƣợc trong một lƣợng thời gian hữu hạn. Nhƣng xét cho cùng, giải thuật chỉ phản ánh các phép xử lý, còn đói tƣợng để xử lý trong máy tính chính là dữ liệu (data ), chúng biểu diễn các thông tin cần thiết cho bài toán: các dữ liệu vào, các dữ liệu ra, dữ liệu trung gian, … Không thể nói tới giải thuật mà không nghĩ tới: giải thuật đó đƣợc tác động trên dữ liệu nào, còn xét tới dữ liệu thì phải biết dữ liệu ấy cần đƣợc giải thuật gì tác động để đƣa ra kết quả mong muốn.. Nhƣ vậy, giữa cấu trúc dữ liệu và giải thuật có mối liên quan mật thiết với nhau.

Không có sách nào