Bài giảng Cấu trúc dữ liệu và giải thuật - Bài 1: Giới thiệu chung - Ngô Hữu Phước

Lecturer: Dr. Ngo Huu Phuc Tel: 0438 326 077 Mob: 098 5696 580 Email: ngohuuphuc76@gmail.com Cấu trúc dữ liệu và giải thuật Bài 1. Giới thiệu chung 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: 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: Introduction 3 @Copyrights by Dr. Ngo Huu Phuc, Le Quy Don Technical University 1.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 University 1.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 University 1.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 University 1.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 University 1.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 University 1.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 University Hình 2 10 @Copyrights by Dr. Ngo Huu Phuc, Le Quy Don Technical University 1.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ột đỉnh của đồ thị, hai lối đi không thể cùng đi đồng thời được nối nhau bằng một đoạn ta gọi là cạnh của đồ thị.  Bây giờ ta phải xác định các nhóm, với số nhóm ít nhất, mỗi nhóm gồm các lối đi có thể đi đồng thời, nó ứng với một pha của đèn hiệu điều khiển giao thông.  Giả sử rằng, ta dùng màu để tô lên các đỉnh của đồ thị này sao cho:  Các lối đi cho phép cùng đi đồng thời sẽ có cùng một màu: Dễ dàng nhận thấy rằng hai đỉnh có cạnh nối nhau sẽ không được tô cùng màu.  Số nhóm là ít nhất: ta phải tính toán sao cho số màu được dùng là ít nhất. 11 @Copyrights by Dr. Ngo Huu Phuc, Le Quy Don Technical University 1.0.4. Hướng giải quyết (VD2) (t)  "Tô màu cho đồ thị ở hình 2 sao cho:  Hai đỉnh có cạnh nối với nhau (hai còn gọi là hai đỉnh kề nhau) không cùng màu.  Số màu được dùng là ít nhất." Nhận xét:  Hai bài toán thực tế “tô màu bản đồ thế giới” và “đèn giao thông” xem ra rất khác biệt nhau nhưng sau khi mô hình hóa, chúng thực chất chỉ là một, đó là bài toán “tô màu đồ thị”. 12 @Copyrights by Dr. Ngo Huu Phuc, Le Quy Don Technical University 1.0.5. Thiết kế giải thuật để giải bài toán “ tô màu đồ thị”  Bài toán “tô màu đồ thị không có giải thuật tối ưu.  Để có kết quả tối ưu, cần sử dụng phương pháp vét cạn. Phương pháp này tốt khi số phép thử là nhỏ.  Thông thường, để đơn giản hóa, có thể:  Thêm thông tin vào bài toán để đồ thị có một số tính chất đặc biệt và dùng các tính chất đặc biệt này ta có thể dễ dàng tìm lời giải, hoặc  Thay đổi yêu cầu bài toán một ít cho dễ giải quyết, nhưng lời giải tìm được chưa chắc là lời giải tối ưu.  Cách này được xem là "Cố gắng tô màu cho đồ thị bằng ít màu nhất một cách nhanh chóng".  Một giải pháp như thế gọi là một HEURISTIC. 13 @Copyrights by Dr. Ngo Huu Phuc, Le Quy Don Technical University 1.0.6. Giải thuật HEURISTIC  HEURISTIC cho bài toán tô màu đồ thị, thường gọi là giải thuật "háu ăn" (GREEDY) là:  Chọn một đỉnh chưa tô màu và tô nó bằng một màu mới C nào đó.  Duyệt danh sách các đỉnh chưa tô màu. Đối với một đỉnh chưa tô màu, xác định xem nó có kề với một đỉnh nào được tô bằng màu C đó không. Nếu không có, tô nó bằng màu C đó.  Ý tưởng của Heuristic này là hết sức đơn giản: dùng một màu để tô cho nhiều đỉnh nhất có thể được (các đỉnh được xét theo một thứ tự nào đó), khi không thể tô được nữa với màu đang dùng thì dùng một màu khác. Như vậy ta có thể "hi vọng" là số màu cần dùng sẽ ít nhất 14 @Copyrights by Dr. Ngo Huu Phuc, Le Quy Don Technical University Ví dụ về HEURISTIC Ví dụ: Tô mầu đồ thị hình 3 Tô theo GREEDY (xét lần lượt theo số thứ tự các đỉnh) 1: đỏ; 2: đỏ; 3: xanh;4: xanh; 5: vàng Tối ưu (thử tất cả các khả năng) 1,3,4 : đỏ; 2,5 : xanh 15 @Copyrights by Dr. Ngo Huu Phuc, Le Quy Don Technical University Giải bài toán giao thông bằng HEURISTIC Trở lại bài toán giao thông ở trên và áp dụng HEURISTIC Greedy cho đồ thị trong hình 2 (theo thứ tự các đỉnh đã liệt kê ở trên), ta có kết quả:  Tô màu xanh cho các đỉnh: AB,AC,AD,BA,DC,ED  Tô màu đỏ cho các đỉnh: BC,BD,EA  Tô màu tím cho các đỉnh: DA,DB  Tô màu vàng cho các đỉnh: EB,EC Chú ý: 4 màu là 1 lời giải, nhưng chưa kết luận được có tối ưu hay không. 16 @Copyrights by Dr. Ngo Huu Phuc, Le Quy Don Technical University Chứng minh về số mầu cần thiết để tô là 4?  Định lý: Một đồ thị trong đó có k đỉnh mà mỗi cặp đỉnh bất kỳ trong k đỉnh này đều được nối nhau thì không thể dùng ít hơn k màu để tô cho đồ thị.  Chứng minh: Đồ thị trong hình I.2 có 4 đỉnh: AC,DA,BD,EB mà mỗi cặp đỉnh bất kỳ đều được nối nhau vậy đồ thị hình I.2 không thể tô với ít hơn 4 màu. Điều này khẳng định rằng lời giải vừa tìm được ở trên trùng với lời giải tối ưu. 17 @Copyrights by Dr. Ngo Huu Phuc, Le Quy Don Technical University 1.1. Các giải thuật 1.1.1. Thế nào là giải thuật. 1.1.2. Ví dụ về giải thuật: Sắp xếp một dãy. 1.1.3. Định nghĩa giải thuật. 18 @Copyrights by Dr. Ngo Huu Phuc, Le Quy Don Technical University  Giải thuật là các ý tưởng đằng sau chương trình trên máy tính.  Giải thuật không thay đổi khi viết trên các ngôn ngữ khác nhau.  Giải thuật phải giải quyết được các vấn đề tổng quát cũng như các vấn đề riêng của một bài toán.  Giải thuật cần có đầu vào và đầu ra rõ ràng. 1.1.1. Thế nào là giải thuật? 19 @Copyrights by Dr. Ngo Huu Phuc, Le Quy Don Technical University  Input: Một dãy số gồm N phần tử. a[1], a[2], , a[n].  Output: Sắp xếp lại dãy số trên dãy số trên có dạng: a[1] <= a[2] <= <= a[n] . • Cần tìm giải thuật chính xác và hiệu quả. 1.1.2. Ví dụ về giải thuật: Sorting 20 @Copyrights by Dr. Ngo Huu Phuc, Le Quy Don Technical University 1.1.3. Nghiên cứu giải thuật cần gì? 1. Máy tính để thực hiện giải thuật. 2. Ngôn ngữ lập trình để diễn tả giải thuật. 3. Cơ sở của giải thuật. 4. Phân tích giải thuật. 21 @Copyrights by Dr. Ngo Huu Phuc, Le Quy Don Technical University 1.1.4. Định nghĩa giải thuật. Knuth (1973) định nghĩa giải thuật là một chuỗi hữu hạn các thao tác để giải một bài toán nào đó. Các tính chất quan trọng của giải thuật là : 1. Input: Không có hoặc có một số, được đưa từ ngoài vào. 2. Output: Có ít nhất một đầu ra. 3. Xác định (Definiteness): mỗi bước của giải thuật phải được xác định rõ ràng và phải được thực hiện chính xác, nhất quán. 4. Hữu hạn (Finiteness): giải thuật phải luôn luôn kết thúc sau một số hữu hạn bước. 5. Hiệu quả (Effectiveness): các thao tác trong giải thuật phải được thực hiện trong một lượng thời gian hữu hạn. 22 @Copyrights by Dr. Ngo Huu Phuc, Le Quy Don Technical University 1.2. Cấu trúc dữ liệu? 1.2.1. Là ngành khoa học máy tính – nghiên cứu về dữ liệu. 1.2.2. Các kiểu dữ liệu. 1.2.3. Miền xác định của dữ liệu. 1.2.4. Các cấu trúc dữ liệu. 1.2.5. Sự thực thi dữ liệu. 23 @Copyrights by Dr. Ngo Huu Phuc, Le Quy Don Technical University 1.2.1. Là ngành khoa học máy tính – nghiên cứu về dữ liệu 1. Máy tính lưu trữ dữ liệu. 2. Ngôn ngữ được sử dụng để thao tác với dữ liệu. 3. Dữ liệu được hiệu chỉnh, diễn tả hợp lý từ dữ liệu gốc. 4. Cấu trúc để biểu diễn dữ liệu. 24 @Copyrights by Dr. Ngo Huu Phuc, Le Quy Don Technical University 1.2.2. Các kiểu dữ liệu.  Kiểu dữ liệu là khái niệm về loại của dữ liệu cho biến trong chương trình.  Trong ngôn ngữ C kiểu dữ liệu có sẵn như: int, float, char, double  Trong ngôn ngữ FORTRAN kiểu dữ liệu có sẵn như: INTEGER, REAL, LOGICAL, COMPLEX, DOUBLE PRECISION 25 @Copyrights by Dr. Ngo Huu Phuc, Le Quy Don Technical University 1.2.3. Miền xác định của dữ liệu • Miền xác định của dữ liệu thường ký hiệu D. • Ví dụ: Với kiểu bool, D = {0, 1}. • Ví dụ: Với kiểu int , D = {0, 1, 2, ...}. • Với các ký tự hoặc xâu ký tự, D = {' ','A','B', ...,'Z',”AA”...}. • Như vậy, D có thể là hữu hạn hoặc vô hạn, cần xác định kiểu dữ liệu phù hợp với giải thuật. 26 @Copyrights by Dr. Ngo Huu Phuc, Le Quy Don Technical University 1.2.4. Các cấu trúc dữ liệu  Một cấu trúc dữ liệu là: Miền D, xác định rõ, Tập các hàm F, Tập “tiên đề” X.  Như vậy, một bộ (D, F, X) xác định cấu trúc dữ liệu d. 27 @Copyrights by Dr. Ngo Huu Phuc, Le Quy Don Technical University 1.2.5. Sự thực thi dữ liệu.  Sự thực thi của cấu trúc dữ liệu là ánh xạ cấu trúc dữ liệu d vào cấu trúc dữ liệu đã có trước đó.  Ví dụ: số nguyên được biểu diễn bởi chuỗi bít.  Ví dụ: kiểu boolean được định nghĩa bởi số 0 hoặc 1.  Ví dụ: mảng được định nghĩa các ô nhớ liên tục trong bộ nhớ 28 @Copyrights by Dr. Ngo Huu Phuc, Le Quy Don Technical University 1.3. Biểu diễn thuật toán Có nhiều cách khác nhau để biểu diễn một giải thuật, thông thường, có 3 cách: 1.3.1. Biểu diễn bằng cách liệt kê các bước; 1.3.2. Biểu diễn bằng sơ đồ khối; 1.3.3. Biểu diễn bằng giả mã lệnh. 29 @Copyrights by Dr. Ngo Huu Phuc, Le Quy Don Technical University 1.3.1. Biểu diễn giải thuật bằng liệt kê các bước Liệt kê ra các bước cần phải thực hiện bằng ngôn ngữ tự nhiên. VD 1: Thuật toán tìm số lớn nhất trong 3 số a,b,c  Giả thiết số lớn nhất là a: Max=a  Nếu Max<b thì Max=b  Nếu Max<c thì Max=c  Ghi giá trị của Max. 30 @Copyrights by Dr. Ngo Huu Phuc, Le Quy Don Technical University 1.3.2. Biểu diễn giải thuật bằng sơ đồ khối Sơ đồ khối là một ngôn ngữ dùng để biểu diễn thuật toán.  Hai loại nút giới hạn Bắt đầu và Kết thúc thường có hình dạng elip: 31 @Copyrights by Dr. Ngo Huu Phuc, Le Quy Don Technical University 1.3.2. Biểu diễn giải thuật bằng sơ đồ khối (tiếp)  Khối nhập/xuất có dạng hình chữ nhật bị cắt vát.  Nút chỉ các thao tác, công việc có dạng hình chữ nhật:  Nút chỉ các điều kiện có dạng hình thoi. Trong các đường nối với nút điều kiện này có hai đường đi ra ứng với hai trường hợp điều kiện đúng hoặc điều kiện sai.  Khối hình bình hành để in các giá trị.  Các đường nối các nút với nhau. 32 @Copyrights by Dr. Ngo Huu Phuc, Le Quy Don Technical University 1.3.2. Ví dụ về sơ đồ khối 33 @Copyrights by Dr. Ngo Huu Phuc, Le Quy Don Technical University 1.3.3. Biểu diễn giải thuật bằng giả mã lệnh Trong các trường hợp biểu diễn bằng sơ đồ khối quá phức tạp, hay quá dài, có thể sử dụng giả mã lệnh để biểu diễn giải thuật. Một số cú pháp cơ bản trong giả mã lệnh:  Cấu trúc tuần tự: Liệt kê các công việc, các thao tác theo thứ tự. Để hỗ trợ cho việc theo dõi được thuận tiện cũng có thể thêm số thứ tự.  Cấu trúc rẽ nhánh:  If (điều kiện) Then (công việc);  If (điều kiện) Then (công việc 1) Else (công việc 2); 34 @Copyrights by Dr. Ngo Huu Phuc, Le Quy Don Technical University 1.3.3. Biểu diễn giải thuật bằng giả mã lệnh (tiếp)  Cấu trúc lặp:  For (biến):= (giá trị đầu) to (giá trị cuối) do (công việc);  For (biến):= (giá trị đầu) downto (giá trị cuối) do (công việc);  While (điều kiện) do (công việc);  Repeat  - (công việc 1);  - (công việc 2);  - ....  - (công việc k);  Until (điều kiện);  VD: Thuật toán tìm số lớn nhất trong 3 số a,b,c  Max:=a;  If Max<b then Max:=b;  If Max<c then Max:=c;  println(‘Max=’, max); 35 @Copyrights by Dr. Ngo Huu Phuc, Le Quy Don Technical University 1.3.3. Ví dụ về giả mã lệnh cho thuật toán HEURISTIC void GREEDY ( GRAPH *G, SET *Newclr ) { /*1*/ Newclr = ∅; /*2*/ for (mỗi đỉnh v chưa tô màu của G) /*3*/ if (v không được nối với một đỉnh nào trong Newclr) { /*4*/ đánh dấu v đã được tô màu; /*5*/ thêm v vào Newclr; } } 36 @Copyrights by Dr. Ngo Huu Phuc, Le Quy Don Technical University 1.4. Độ phức tạp của thuật toán Khi đề xuất một thuật toán ngoài việc quan tâm đến tính đúng đắn của thuật toán, người ta còn phải quan tâm đến một số vấn đề:  Tính phổ dụng;  Độ phức tạp thuật toán - thời gian tính toán của thuật toán phụ thuộc vào dữ liệu đầu vào như thế nào, Trước khi nghiên cứu độ phức tạp thuật toán, ta xem xét một số khái niệm về cách xác định độ phức tạp cho thuật toán. 37 @Copyrights by Dr. Ngo Huu Phuc, Le Quy Don Technical University 1.4. Độ phức tạp của thuật toán (tiếp) Một số khái niệm:  Khái niệm về độ tăng của hàm: Một trong các khái niệm thường được dùng để phân tích độ tăng của hàm là khái niệm O (ô lớn) được định nghĩa như sau:  Cho f(x) và g(x), ta nói f(x) là O(g(x)) nếu tồn tại một hằng số C và k sao cho  |f(x)|k;  Độ tăng của tổ hợp các hàm:  Xét f1(x) là O(g1(x) và f2(x) là O(g2(x)), CMR: (f1(x)+f2(x)) là O(max{g1(x),g2(x)}) 38 @Copyrights by Dr. Ngo Huu Phuc, Le Quy Don Technical University 1.4. Độ phức tạp của thuật toán (tiếp) Độ phức tạp của thuật toán  Các thuật ngữ O(1)-độ phức tạp hằng số; O(n) độ phức tạp tuyến tính; O(nb) – độ phức tạp hàm mũ.  Độ phức tạp tính toán sẽ được tính theo số lần thực hiện các phép toán sơ cấp:cộng, trừ, nhân, chia, phép gán,.. VD: Xét đoạn chương trình sau: For (int i=1; i<n;i++) { {có phép tính sơ cấp; ko có vòng lặp ở đây nữa} } => số lần lặp sẽ là n=> O(n) 39 @Copyrights by Dr. Ngo Huu Phuc, Le Quy Don Technical University Tóm tắt chương 1 40 @Copyrights by Dr. Ngo Huu Phuc, Le Quy Don Technical University