"Bài giảng Cấu trúc dữ liệu và giải thuật – Bài 1: Giới thiệu chung" trình bày đôi nét về khái niệm về cấu trúc dữ liệu và giải thuật, giải thuật, dữ liệu và các cấu trúc dữ liệu, biểu diễn giải thuật, độ phức tạp của giải thuật. | Cấu trúc dữ liệu và giải thuật Bài 1. Giới thiệu chung Lecturer Dr. Ngo Huu Phuc Tel 0438 326 077 Mob 098 5696 580 Email ngohuuphuc76@ 1 @Copyrights by Dr. Ngo Huu Phuc Le Quy Don Technical University Tài liệu tham khảo Mastering Algorithms with C Kyle Loudon 1999. Introduction to Algorithms Thomas H. Cormen Charles E. Leiserson Ronald L. Rivest and Clifford Stein The MIT Press 2001. Data Structures Algorithms and Object-Oriented Programming. NXB McGraw Hill Tác giả Gregory Heilleman -1996 Cấu trúc dữ liệu và giải thuật Đỗ Xuân Lôi. 2 @Copyrights by Dr. Ngo Huu Phuc Le Quy Don Technical University Bài 1. Giới thiệu Nội dung . Đôi nét về khái niệm. . Giải thuật. . Dữ liệu và các cấu trúc dữ liệu. . Biểu diễn giải thuật. . Độ phức tạp của giải thuật. Tham khảo Elliz Horowitz - Fundamentals of data structures Chapter 1 Introduction 3 @Copyrights by Dr. Ngo Huu Phuc Le Quy Don Technical University . Đôi nét về khái niệm Để giải một bài toán bắt đầu từ câu hỏi phải làm gì sau đó trả lời câu hỏi làm như thế nào đó là cách tiếp cận đến giải thuật và cấu trúc dữ liệu. Các bài toán trong thực tế không dễ giải bằng cách hiểu thông thường và để giảm độ phức tạp trong nhiều trường hợp có thể mô hình hóa bài toán. Từ việc mô hình hóa trong thực tế thấy rằng có nhiều bài toán có cùng một mô hình hóa. 4 @Copyrights by Dr. Ngo Huu Phuc Le Quy Don Technical University . Một số ví dụ 1 Ví dụ 1 Tô màu bản đồ thế giới. Yêu cầ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. 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. 5 @Copyrights by Dr. Ngo Huu Phuc Le Quy Don Technical University . Một số ví dụ 2 Hướng giải quyết bằng 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ở .
