Tóm tắt

Nội dung của cuốn sách được tổ chức thành ba phần. Phần 1 sẽ nghiên cứu các CTDL cơ bản được sử dụng để cài đặt các KDLTT, đó là danh sách liên kết (DSLK), cây tìm kiếm nhị phân (TKNP), cây thứ tự bộ phận (heap), bảng băm. Danh sách, ngăn xếp, hàng đợi sẽ được cài đặt bởi mảng hoặc bởi DSLK. Cây TKNP được sử dụng để cài đặt tập động. Hàng ưu tiên được cài đặt hiệu quả bởi heap. Bảng băm là CTDL rất thích hợp để cài đặt từ điển. Trong phần 2 chúng ta sẽ nghiên cứu các CTDL cao cấp. Các CTDL này có đặc điểm chung là sự tổ chức dữ liệu và các phép toán trên các CTDL này là khá phức tạp, song bù lại thời gian thực hiện các phép toán lại hiệu quả hơn. Chúng ta sẽ nghiên cứu các loại cây tìm kiếm cân bằng, các CTDL tựđiều chỉnh, các CTDL đa chiều, ... Đặc biệt, chúng ta sẽđưa vào kỹ thuật phân tích trả góp, đây là kỹ thuật phân tích hoàn toàn mới, được sử dụng để đánh giá thời gian chạy của một dãy phép toán trên các CTDL tự điều chỉnh. Phần 3 dành để nói về thuật toán. Chúng ta sẽ trình bày phương pháp đánh giá thời gian chạy của thuật toán bằng ký hiệu ô lớn, và các kỹ thuật để phân tích, đánh giá thời gian chạy của thuật toán. Một nội dung quan trọng của phần này là nghiên cứu các chiến lược thiết kế thuật toán. Chúng ta sẽ trình bày các chiến lược thiết kế thuật toán hay được sử dụng là : chia - để - trị, quy hoạch động, quay lui, ... Các thuật toán sắp xếp, các thuật toán đồ thị cũng sẽ được nghiên cứu. Cuối cùng chúng ta trình bày một vấn đề có tính chất lý thuyết, đó là các bài toán NP – khó và NP - đầy đủ.