LỜI NÓI ĐẦU

N. Wirth, một nhà khoa học máy tính nổi tiếng, tác giả của ngôn ngữ lập trình Pascal, đã đặt tên cho một cuốn sách của ông là “Cấu trúc dữ liệu + Giải thuật = Chương trình”. Điều đó nói lên tầm quan trọng của giải thuật trong lập trình nói riêng và trong khoa học máy tính nói
chung. Vì lẽ đó giải thuật, với tư cách là một môn học, cần phải được sinh viên chuyên ngành
tin học nghiên cứu một cách có hệ thống.
             Môn học “Giải thuật” được bố trí sau môn “Cấu trúc dữ liệu” trong chương trình đào tạo kỹ sư tin học nhằm giới thiệu cho sinh viên những kiến thức cơ bản nhất, những kỹ thuật chủ yếu nhất của giải thuật. Các kỹ thuật được trình bày ở đây đã được các nhà khoa học tin học tổng kết và vận dụng trong cài đặt các chương trình. Việc nắm vững các kỹ thuật đó sẽ rất bổ ích cho sinh viên khi phải giải quyết một vấn đề thực tế. Trong khuôn khổ 45 tiết, giáo trình
được cấu trúc thành 4 chương.

Chương 1: Kỹ thuật phân tích giải thuật, trình bày một số kỹ thuật dùng để phân tích, đánh giá tính hiệu quả về thời gian thực hiện của chương trình dựa vào khái niệm độ phức tạp của giải thuật, trong đó sẽ tập trung phân tích các giải thuật đệ quy. Phân tích giải thuật cho phép chúng ta lựa chọn một giải thuật hiệu quả để giải quyết vấn đề.            
Chương 2: Sắp xếp. Sắp thứ tự là một thao tác được sử dụng trong rất nhiều ứng dụng tin học. Chương này trình bày một số giải thuật sắp xếp đơn giản, dễ cài đặt và một số giải thuật có hiệu quả cao về mặt thời gian thực hiện. Với mỗi giải thuật sắp xếp, chúng tôi đều nêu ý tưởng, ví dụ minh họa, chương trình viết bằng ngôn ngữ Pascal và cuối cùng là phân tích đánh giá giải thuật đó.
           
Chương 3: Kỹ thuật thiết kế giải thuật. Khi gặp một bài toán, cần phải xoay xở như thế nào?. Chương này trình bày một số kỹ thuật thiết kế giải thuật có thể lựa chọn vận dụng để trả lời cho câu hỏi đó. Các kỹ thuật ở đây được mô tả ở mức ý tưởng, và được minh họa giải quyết một số bài toán có nhiều ứng dụng trong thực tiễn. Việc cài đặt các giải thuật này cho từng bài toán cụ thể đòi hỏi phải lựa chọn một cấu trúc dữ liệu thích hợp và sự chi tiết hóa công phu, do đó chúng tôi không trình bày trong giáo trình này mà dành cho sinh viên thực hiện ở khuôn khổ niên luận. Cũng cần nói thêm rằng, một số kỹ thuật ở đây sẽ được vận dụng trong các môn học khác đặc biệt là môn “ Trí tuệ nhân tạo “.
           
Chương 4: Cấu trúc dữ liệu và giải thuật cho lưu trữ ngoài. Chương này tập trung vào hai vấn đề chính là sắp xếp dữ liệu lưu trong bộ nhớ ngoài và các chiến lược lựa chọn cấu trúc dữ liệu và giải thuật cho việc lưu trữ thông tin trong tập tin.
             Giáo trình này được hình thành trên cơ sở tham khảo cuốn sách “Data Structure and Algorithms” của A.V Aho, những kinh nghiệm giảng dạy của bản thân và các bạn đồng nghiệp. Mặc dù đã có nhiều cố gắng trong quá trình biên soạn nhưng chắc chắn còn nhiều thiếu sót, rất mong nhận được sự đóng góp của quý bạn đọc.
Cần thơ, ngày 19 tháng 12 năm 2001







1.Mục tiêu :
Tại sao cần phân tích đánh giá giải thuật ?
·Tiêu chuẩn nào để đánh giá một giải thuật là tốt? · Phương pháp đánh giá như thế nào? (đánh giá chương trình không gọi chương trình con, đánh giá một chương trình có gọi các chương trình con không đệ quy và đánh giá chương trình đệ quy).

2.Kiến thức cơ bản :
· Kiến thức toán học: Công thức tính tổng n số tự nhiên đầu tiên, công thức tính tổng n số hạng đầu tiên của một cấp số nhân, phương pháp chứng minh quy nạp và các kiến thức liên quan đến logarit (biến đổi logarit, tính chất đồng biến của hàm số logarit).
· Kỹ thuật lập trình và lập trình đệ quy.
3. Tài liệu tham khảo có liên quan đến chương
· A.V. Aho, J.E. Hopcroft, J.D. Ullman; Data Structures and Algorithms; Addison-Wesley; 1983. (Chapters 1, 9).
· Đinh Mạnh Tường; Cấu trúc dữ liệu & Thuật toán; Nhà xuất bản khoa học và kỹ thuật; Hà nội-2001. (Chương 1).

4. Nội dung:
CHƯƠNG I KỸ THUẬT PHÂN TÍCH GIẢI THUẬT
CHƯƠNG II SẮP XẾP
CHƯƠNG III KỸ THUẬT THIẾT KẾ GIẢI THUẬT