Bài giảng Cấu trúc dữ liệu và giải thuật - Hồ sĩ đàm

CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬTGiảng viên : Hồ Sĩ Đàm Email damhs@vnu.edu.vn Giới thiệu Thời lượng: 4 buổiMục tiêu: - Giới thiệu đề cương phần cấu trúc dữ liệu và thuật toán ( môn Tin học cơ sở); - Giải đáp thắc mắc của thi sinh. Tài liệu tham khảoThomas H. Cormen, Introduction to Algorithms, MIT Press, 1990R. Sedgevick,Algorithms Addison- Wesley, Bản dịch tiếng Việt: Cẩm nang thuật toán ( tập 1, 2).Hồ Sĩ Đàm, Nguyễn Việt, Hà Bùi Thế DuyĐinh Mạnh Tường, Đỗ Xuân Lôi Nội dungChương I : Thuật toán và phân tích thuật toánChương II : Đệ quyChương III : Các dữ liệu có cấu trúc Chương IV : Danh sáchChương V : CâyChương VI : Bảng bămChương VII : Sắp xếpChương VIII : Tìm kiếmChương IX : Đồ thịChương X : Các kỹ thuật thiết kế thuậ toánCHƯƠNG I: THUẬT TOÁN VÀ PHÂN TÍCH THUẬT TOÁNGiải bài toán trên máy tínhMô hình dữ liệuCấu trúc dữ liệuBài toán và thuật toán CHƯƠNG I: THUẬT TOÁN VÀ PHÂN TÍCH THUẬT TOÁN 1. Giải bài toán trên máy tínhBước 1. Xác định bài toán: Xác định tập Input và OutputBước 2. Lựa chọn hoặc thiết kế thuật toána) Lựa chọn hoặc thiết kế thuật toánGiải bài toán  nhiều thuật toánKhông gian ? Thời gian ?; Cài đặt ?	b) Mô tả thuật toán Input: Hai số nguyên dương a và b; Output: q và r : a= bq+r.  Ý tưởng: 	- Nếu a b thì a giảm đi b và q tăng lên 1. Lặp cho đến khi a = b DoBegin	Dec(a,b);	Inc(q);End;r:= a;Writeln (‘Thuong q = ’, q);Writeln (‘Phan du r = ’, r);Readln;End.CHƯƠNG I: THUẬT TOÁN VÀ PHÂN TÍCH THUẬT TOÁN 1. Giải bài toán trên máy tínhBước 5. Viết tài liệu:Hướng dẫn sử dụng;Thuật toán, Cấu trúc dữ liệu; . CHƯƠNG I: THUẬT TOÁN VÀ PHÂN TÍCH THUẬT TOÁN 2. Mô hình dữ liệu (Data model)Là các trừu tượng :đồ thị, tập hợp, danh sách, cây... Hai khía cạnh:Giá trị (kiểu dữ liệu) Các phép toán ( operation) Chương trình có thể truy xuất đến các vùng lưu trữ.CHƯƠNG I: THUẬT TOÁN VÀ PHÂN TÍCH THUẬT TOÁN 3. Cấu trúc dữ liệu (Data structures)Là các đơn vị cấu trúc (construct) của NNLT dùng để biểu diễn các mô hình dữ liệuVí dụ: mảng, bản gi, file,xâu,.. CHƯƠNG I: THUẬT TOÁN VÀ PHÂN TÍCH THUẬT TOÁN 4. Bài toán và thuật toán4.1. Bài toán Xác định rõ Input và OutputVí dụ: Kiểm tra xem N có phải là số nguyên tố hay không?- Input 	: Số nguyên dương N- Output 	: Trả lời N là số nguyên tố hay không?CHƯƠNG I: THUẬT TOÁN VÀ PHÂN TÍCH THUẬT TOÁN 4. Bài toán và thuật toán4.2. Thuật toán Thuật toán để giải một bài toán là một dãy hữu hạn các thao tác đươc sắp xếp theo một trật tự xác định sao cho sau khi thực hiện dãy thao tác đó, từ Input của bài toán này, ta nhận được Output cần tìm.Ví dụ: Tìm giá trị lớn nhất của dãy số a1, a2,..,aN, Input : Số nguyên dương N và dãy a1, a2, ,..., aN.Output : Tìm Max là giá trị lớn nhất của dãy đã cho.Ý tưởng: Khởi tạo Max=a1. Với mỗi i, nếu ai > Max thì thay giá trị Max= ai.CHƯƠNG I: THUẬT TOÁN VÀ PHÂN TÍCH THUẬT TOÁN 4. Bài toán và thuật toánCHƯƠNG I: THUẬT TOÁN VÀ PHÂN TÍCH THUẬT TOÁN 4. Bài toán và thuật toán4.3. Mô tả thuật toán a) Cách liệt kêB1. Nhập N và dãy a1, ..., aNB2. Đặt Max = a1, i = 2.B3. Nếu i > N thì đến b. 5.B4.	4.1. N ếu ai > Max thì Max = ai.	4.2. Đặt i=i+1 rồi quay b.3.B5. Đưa ra Max rồi kết thúc. CHƯƠNG I: THUẬT TOÁN VÀ PHÂN TÍCH THUẬT TOÁN 4. Bài toán và thuật toánb) Sơ đồ khốiDùng: Ovan, Chữ nhật, Hình thoi,Mũi tên,CHƯƠNG I: THUẬT TOÁN VÀ PHÂN TÍCH THUẬT TOÁN 4. Bài toán và thuật toánc) Ngôn ngữ điều khiểnDùng các ký hiệu và quy tắcCách thiết lập thứ tự các thao tác cấu trúc điều khiển. CHƯƠNG I: THUẬT TOÁN VÀ PHÂN TÍCH THUẬT TOÁN 4. Bài toán và thuật toán4.4. Các đặc trưng chính a)Tính kết thúc (tính đóng)b)Tính xác định (đơn nghĩa)	Có đúng một thao tác để được thực hiện hoặc dừng.CHƯƠNG I: THUẬT TOÁN VÀ PHÂN TÍCH THUẬT TOÁN 4. Bài toán và thuật toánc)Tính chi tiếtPhụ thuộc vào đối tượng thực hiệnd)Tính phổ dụng	với input thay đổie) Đại lượng vào f) Đại lượng raCHƯƠNG I: THUẬT TOÁN VÀ PHÂN TÍCH THUẬT TOÁN 4. Bài toán và thuật toáng) Tính hiệu quảThời gian: Tốc độ xử lý Không gian: Dung lượng cần để lưu trữCHƯƠNG I: THUẬT TOÁN VÀ PHÂN TÍCH THUẬT TOÁN 4. Bài toán và thuật toán4.5. Độ phức tạp thuật toánLựa chọn thuật toán Dễ hiểu, dễ cài đặt và dễ ghi chép ? Sử dụng các tài nguyên hiệu quả? Tùy đặc tính của bài toán Phân tích theo kinh nghiệmThực hiện và kết luận  dễ mắc lỗi Kích thước dữ liệu đầu vào là quan trọng: T(n)CHƯƠNG I: THUẬT TOÁN VÀ PHÂN TÍCH THUẬT TOÁN 4. Bài toán và thuật toánb) Ký pháp	Giả sử T(n) là thời gian thực hiện TT và f(n), g(n), h(n) là các hàm xác định dương Hàm O lớn: O(g(n)) nếu  c và n0 sao cho T(n) = n0 g(n) là giới hạn trên của T(n).	Ví dụ, nếu T(n) = n2 + 1 thì T(n) = O(n2).	Chọn c=2 và n0 =1, khi đó với mọi n>=1, ta có T(n)= n2+1 0 và n0 >0 để T(n) = n0.	Đặt c=c0.c1 ta có điều cần CM CHƯƠNG I: THUẬT TOÁN VÀ PHÂN TÍCH THUẬT TOÁN 4. Bài toán và thuật toánQuy tắc lấy Max	Nếu P có T(n)= O( f(n)+g(n)) thì P có độ phức tạp là O( max ( f(n), g(n))).CM: T(n) = O( f(n)+g(n)) nên tồn tại n0>0 và c>0 để T(n) = n0 vậy T(n) =n0.	Từ đó suy điều cần CM. CHƯƠNG I: THUẬT TOÁN VÀ PHÂN TÍCH THUẬT TOÁN 4. Bài toán và thuật toánQuy tắc cộng	Nếu P1 có T1 (n) = O( f(n) và P2 có T2(n)= O(g(n)), khi đó: T1(n) +T2(n) = O(f(n) +g(n)).CM: Vì T1(n)= O(f(n)) nên  các hàng số c1 và n1 sao cho T(n) = n1.	Vì T2(n) =O(g(n)) nên  các hàng số c2 và n2 sao cho T(n) = n2	Chọn c= max (c1,c2) và n0 = max(n1,n2) ta có n: n n>= n0:	T(n) = T1(n) + T2(n) =0 và nk >0 để k(n) = nkcT>=0 và nT >0 để T(n) = nT	Vậy với mọi n >= max(nT,nk) ta có k(n)T(n) Rear thì EmptyQueueCHƯƠNG IV: DANH SÁCH (LIST)2. Biểu diễn danh sách trong máy tínhQueue vòng trònCác phần tử xếp quanh vòng tròn theo một hướng. Các phần tử nằm trên cung tròn từ vị trí Front đến Rear là thuộc Queue. CHƯƠNG IV: DANH SÁCH (LIST)2. Biểu diễn danh sách trong máy tínhKhi thêm :dịch chuyển chỉ số Rear theo vòng tròn 1 ví trí rồi đặt giá trị cần thêm vào đó.- Khi lấy ra : lấy phần tử có chỉ số là Front rồi dịch chuyển chỉ số Front theo vòng tròn 1 vị trí. VnVn-1V2V1CHƯƠNG IV: DANH SÁCH (LIST)2. Biểu diễn danh sách trong máy tínhĐể cài đặt : 	(i) Một phương tiện để chia bộ nhớ thành các nút, mỗi nút có phần lưu trữ data, phần lưu trữ các liên kết (con trỏ) và cách cài đặt cho con trỏ 	(ii) Cài đặt các thao tác để truy nhập giá trị (cả data và pointer). 	(iii) Một phương tiện nào đó để “đánh dấu” vùng bộ nhớCHƯƠNG IV: DANH SÁCH (LIST)3. Một số nhận xétCài đặt danh sách bằng mảng tạo ra hạn chế:Độ dài của danh sách.Kiểm tra “tràn” và “rỗng” khi thực hiện chèn và xóa.Khi thực hiện “chèn“ và “Xóa” đều phải thực hiện phép “dịch chuyển”.CHƯƠNG IV: DANH SÁCH (LIST)3. Một số nhận xétTrong các cấu trúc DS, để thực hiện các thao tác cơ bản cần các thao tác tối thiểu:Định vị phần tử đầu tiên của DSCho trước vị trí của một phần tử bất kì trong DS, xác định được phần tử tiếp theo.CHƯƠNG IV: DANH SÁCH (LIST)4. Kiểu dữ liệu con trỏ và việc cấp phát/thu hồi bộ nhớ độngĐể khắc phục, cầnMột thủ tục tiền định để cấp phát bộ nhớ (thủ tục New (p) trong TP) và một thủ tục để giải phóng bộ nhớ (thủ tục Dispose(p) trong Tp).Dùng biến con trỏ để truy cập đến vùng nhớ này. Kiểu của biến con trỏ đã có đặc tả kiểu dữ liệu của nó. Khi không quan tâm tới kiểu dữ liệu của dữ liệu chứa trong vùng nhớ sử dụng con trỏ không định kiểu. CHƯƠNG V BĂMBảng băm mở	1.1. Bảng băm	1.2. Hàm băm	1.3. Xung đột	1.4. Một số hàm băm thông dụngBảng băm đóng	2.1. Băm lại tuyến tính.	2.2. Băm lại bình phương	2.3. Băm lại bằng cách tạo vùng mớiCHƯƠNG VI: BĂM1. Bảng băm mởBảng băm (Hash Table): - Mảng B gồm m phần tử -Lưu trữ chỉ số định vị phần tử dữ liệu có khóa phân biệt thuộc tập số nguyên { 0,1,2m-1}CHƯƠNG VI: BĂM1. Bảng băm mởHàm băm (Hash function): H(x) cho giá trị là một chỉ số phần tử của BCHƯƠNG VI: BĂM1. Bảng băm mởXung đột (collision): x1x2 nhưng H(x1)=H(x2)CHƯƠNG VI: BĂM1. Bảng băm mởXung đột:CHƯƠNG VI: BĂM1. Bảng băm mởXung đột:Giải quyết: liên kết các danh sách có các khóa khác nhau nhưng có cùng giá trị hàm băm thành một danh sáchliên kết trong bẳng băm B sẽ trỏ tới danh sách đầu tiên. CHƯƠNG VI: BĂM1. Bảng băm mởMột số hàm băm thông dụng:Hàm cắt bỏ bỏ bớt một phần nào đó của khóa.Ví dụ: x=842615, bỏ bớt chẳng hạn các chữ số hàng lẻ (1,3,5), số còn lại sẽ là 821. Vậy H(x) = H(842615) = 821.Nhận xét: khó có phân bố đều.CHƯƠNG VI: BĂM1. Bảng băm mởHàm phần dư của phép chia x/mNên chọn m là số nguyên tố. Nhận xét: Các cách lấy phần dư cho khả năng tránh hiện tượng xung độtCHƯƠNG VI: BĂM1. Bảng băm mởMột số hàm băm thông dụngHàm gấp chia số nguyên đó thành một số đoạn tùy chọn, sau đó kết hợp Ví dụ: Số các hàng lẻ: 465 và số các hàng chẵn: 821, vậy H(x)=465+821=1286.Nhận xét: Tính chất thứ hai có thể thỏa mãn tốt hơnCHƯƠNG VI: BĂM1. Bảng băm mởCHƯƠNG VI: BĂM2. Bảng băm đóngBảng băm mở: lưu trữ các liên kết trỏ đến các thành phần dữ liệu. Bảng băm đóng: lưu trữ chính dữ liệu. CHƯƠNG VI: BĂM2. Bảng băm đóngCác phương pháp xử lý:a) Băm lại tuyến tínhHi (x) = (H(x)+i) mod mNhận xét Các giá trị hàm băm xếp thành từng đoạn con, nên việc tìm kiếm ví trí rỗng sẽ rất chậm. CHƯƠNG VI: BĂM2. Bảng băm đóngCHƯƠNG VI: BĂM2. Bảng băm đóngb) Băm lại bình phương	Hi(x) = ( H(x)+i2) mod m CHƯƠNG VI: BĂM2. Bảng băm đóngc) Băm lại bằng cách tạo vùng mớiNgoài bảng B cần tạo ra một vùng không gian mới