Bài giảng Cấu trúc dữ liệu và giải thuật – Bài 1: Giới thiệu chung

"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.
Nội dung trích xuất từ tài liệu:
Bài giảng Cấu trúc dữ liệu và giải thuật – Bài 1: Giới thiệu chung 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@gmail.com1 @Copyrights by Dr. Ngo Huu Phuc, Le Quy Don Technical UniversityTà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 UniversityBài 1. Giới thiệuNội dung: 1.0. Đôi nét về khái niệm. 1.1. Giải thuật. 1.2. Dữ liệu và các cấu trúc dữ liệu. 1.3. Biểu diễn giải thuật. 1.4. Độ phức tạp của giải thuật.Tham khảo: Elliz Horowitz - Fundamentals of data structures, Chapter 1: Introduction3 @Copyrights by Dr. Ngo Huu Phuc, Le Quy Don Technical University1.0. Đô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 University1.0.1. 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 University1.0.2. 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ở 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. 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.6 @Copyrights by Dr. Ngo Huu Phuc, Le Quy Don Technical University1.0.3. Một số ví dụ (3) Ví dụ 2: Đèn giao thông Cho một ngã năm như hình 1. 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ý: sao cho:  Phân chia các lối đi tại ngã năm này thành các nhóm  Mỗi nhóm gồm các lối đi có thể cùng đi đồng thời nhưng không xảy ra tai nạn giao thông (các hướng đi không cắt nhau),  Và số lượng nhóm là ít nhất có thể được.7 @Copyrights by Dr. Ngo Huu Phuc, Le Quy Don Technical University1.0.4. Hướng giải quyết (VD2) Ta có thể xem đầu vào (input) của bài toán là tất cả các lối đi tại ngã năm này. Đầu ra (output) của bài toán là các nhóm lối đi có thể đi đồng thời mà không xảy ra tai nạn giao thông. Mỗi nhóm sẽ tương ứng với một pha điều khiển của đèn hiệu, vì vậy ta phải tìm kiếm lời giải với số nhóm là ít nhất để giao thông không bị tắc nghẽn vì phải chờ đợi quá lâu.8 @Copyrights by Dr. Ngo Huu Phuc, Le Quy Don Technical University1.0.4. Hướng giải quyết (VD2) (t) Trước hết ta nhận thấy rằng tại ngã năm này có 13 lối đi: AB, AC, AD, BA, BC, BD, DA, DB, DC, EA, EB, EC, ED. Thể hiện các lối có thể đi đồng thời. Ví dụ cặp AB và EC có thể đi đồng thời, nhưng AD và EB thì không, vì các hướng giao thông cắt nhau. Sử dụng sơ đồ trực quan:  Tên của 13 lối đi được viết lên mặt phẳng,  Hai lối đi nào nếu đi đồng thời sẽ xảy ra đụng nhau (tức là hai hướng đi cắt qua nhau) ta nối lại bằng một đoạn thẳng.  Ta sẽ có một sơ đồ như hình 2. Như vậy, trên sơ đồ này, hai lối đi có cạnh nối lại với nhau là hai lối đi không thể cho đi đồng thời.9 @Copyrights by Dr. Ngo Huu Phuc, Le Quy Don Technical UniversityHình 210 @Copyrights by Dr. Ngo Huu Phuc, Le Quy Don Technical University1.0.4. Hướng giải quyết (VD2) (t) Với cách biểu diễn như vậy ta đã có một đồ thị (Graph), tức là ta đã mô hình hoá bài toán giao thông ở trên theo mô hình toán là đồ thị. Mỗi lối đi trở thành mộ ...