Bài giảng Cấu trúc dữ liệu và giải thuật - Chương 1: Một số khái niệm cơ bản về cấu trúc dữ liệu và giải thuật

Chia sẻ: Thanh Hoa | Ngày: | Loại File: PDF | Số trang:12

Thêm vào BST

Báo xấu

92
lượt xem 4
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Bài giảng "Cấu trúc dữ liệu và giải thuật - Chương 1: Một số khái niệm cơ bản về cấu trúc dữ liệu và giải thuật" cung cấp cho người học các kiến thức: Các khái niệm, quan hệ giữa giải thuật và cấu trúc DL, vị trí cấu trúc dữ liệu trong một áp dụng tin học, tìm hiểu tổ chức một số CTDL cơ bản. Mời các bạn cùng tham khảo nội dung chi tiết.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Bài giảng Cấu trúc dữ liệu và giải thuật - Chương 1: Một số khái niệm cơ bản về cấu trúc dữ liệu và giải thuật

Phân bổ thời gian  Giảng lý thuyết trên lớp: 70%  Thực hành : 30%  Tự học/ nghiên cứu : 200 % CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT Số tín chỉ: 3 1 2 Nội Dung Chƣơng Trình Tài Liệu Tham Khảo  Đỗ Xuân Lôi, Cấu trúc dữ liệu và giải thuật , Nxb  Chƣơng 1: Một số khái niệm cơ bản về cấu trúc Khoa học Kỹ thuật, 1995 . dữ liệu và giải thuật  Lê Xuân Trường, Cấu trúc dữ liệu bằng ngôn ngữ  Chƣơng 2: Danh sách đặc (condensed list) C++, Nxb Thống kê.  Deshpande, Kakde, C & data structures,  Chƣơng 3: Danh sách liên kết (linked list) Massachusetts, 2004 (pdf). CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT  Chƣơng 4: Cây (tree)  Introduction To Algorithms 2Nd Edition.  Chƣơng 5: Bảng băm  Bài soạn của giảng viên.  Chƣơng 6: Đồ thị (Graph)  Các tài liệu điện tử/ website. 3 4 1
Đánh giá học phần CHƢƠNG 1  Điểm chuyên cần : 10%  Kiểm tra/ thi giữa kỳ: 30%  Thi cuối kỳ : 60%  Tổng điểm: 10 điểm. MỘT SỐ KHÁI NIỆM CƠ BẢN VỀ CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT CTDL VÀ GIẢI THUẬT 5 6 Nội Dung 1.1. Các khái niệm  1.1. Các khái niệm  Môn học giới thiệu  1.2. Quan hệ giữa giải thuật và cấu trúc DL  Các cấu trúc dữ liệu cơ bản  1.3. Vị trí cấu trúc dữ liệu trong một áp dụng tin  Các giải thuật điển hình trên các cấu học trúc dữ liệu đó  1.4. Tìm hiểu tổ chức một số CTDL cơ bản CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT  Cấu trúc dữ liệu là một kết hợp nhiều thành phần dữ liệu khác nhau thành một thực thể thống nhất để thể hiện một kiểu dữ liệu 7 8 2
Cấu Trúc Dữ Liệu Vai Trò Của Cấu Trúc Dữ Liệu  Cách tổ chức lưu trữ dữ liệu.  Cấu trúc dữ liệu đóng vai trò quan trọng trong việc kết hợp và đưa ra cách giải quyết bài toán.  Các tiêu chuẩn của CTDL:  CTDL hỗ trợ cho các thuật toán thao tác trên đối  Phải biểu diễn đầy đủ thông tin. tượng được hiệu quả hơn  Phải phù hợp với các thao tác trên đó. CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT  Phù hợp với điều kiện cho phép của NNLT.  Tiết kiệm tài nguyên hệ thống. 9 10 Các kiểu cấu trúc dữ liệu cơ bản Thuật toán  Bản ghi (struct)  Thuật toán: Một dãy hữu hạn các chỉ thị có thể thi  Danh sách (array) hành để đạt mục tiêu đề ra nào đó.  Ví dụ: Thuật toán tính tổng tất cả các số nguyên  Danh sách liên kết (list) dương nhỏ hơn n gồm các bước sau:  Cây (tree) Bước 1: S=0, i=1;  Bảng băm (hash table) Bước 2: nếu i
Các Tiêu Chuẩn Của Thuật Toán Sự Cần Thiết Của Thuật Toán  Xác định rõ dữ liệu đầu vào  Tại sao sử dụng máy tính để xử lý dữ liệu?  Nhanh hơn.  Xác định rõ kết quả đầu ra  Nhiều hơn.  Tính xác định: cùng một dữ liệu đầu vào thì cùng  Giải quyết những bài toán mà con người không thể hoàn thành được. đưa đến một kết quả đầu ra  Làm sao đạt được những mục tiêu đó? CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT  Tính khả thi: đơn giản, làm được, thời gian hữu  Nhờ vào sự tiến bộ của kỹ thuật: tăng cấu hạn hình máy  chi phí cao   Nhờ vào các thuật toán hiệu quả: thông minh  Tính dừng: sau một số bước hữu hạn thực hiện và chi phí thấp  sẽ phải kết thúc “Một máy tính siêu hạng vẫn không thể cứu vãn một thuật toán tồi!” 13 14 Biễu Diễn Thuật Toán Biểu Diễn Bằng Ngôn Ngữ Tự Nhiên  Dạng ngôn ngữ tự nhiên  NN tự nhiên thông qua các bước được tuần tự liệt kê để biễu diễn thuật toán.  Dạng lưu đồ (sơ đồ khối)  Ưu điểm:  Dạng mã giả  Đơn giản, không cần kiến thức về về cách biểu diễn (mã giả, lưu đồ,...)  Ngôn ngữ lập trình CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT  Nhược điểm:  Dài dòng, không cấu trúc.  Đôi lúc khó hiểu, không diễn đạt được thuật toán. 15 16 4
Lƣu Đồ Biểu Diễn Bằng Lƣu Đồ  Là hệ thống các nút, cung hình dạng khác nhau Bắt đầu amax = a0 thể hiện các chức năng khác nhau. Tìm phần tử mang giá trị lớn nhất i= 1 trong mảng A A S amax là lớn nhất Kết thúc Thực hiện A Gọi hàm A Vào / Ra dữ liệu i
Biểu Diễn Bằng Mã Giả Biểu Diễn Bằng Mã Giả 5. Các cấu trúc:  Ví dụ: Tìm phần tử lớn nhất trong mảng một Cấu trúc chọn: chiều. if … then … [else …] Vòng lặp: amax=a0; while … do i=1; CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT do … while (…) while (i
Độ Phức Tạp Của Thuật Toán Phƣơng Pháp Thực Nghiệm  Một thuật toán hiệu quả:  Cài thuật toán rồi chọn các bộ dữ liệu thử nghiệm.  Chi phí cần sử dụng tài nguyên thấp: Bộ nhớ,  Thống kê các thông số nhận được khi chạy các thời gian sử dụng CPU, … bộ dữ liệu đó.  Phân tích độ phức tạp thuật toán:  Ưu điểm: Dễ thực hiện.  N là khối lượng dữ liệu cần xử lý.  Nhược điểm: CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT  Mô tả độ phức tạp thuật toán qua một hàm  Chịu sự hạn chế của ngôn ngữ lập trình. f(N).  Ảnh hưởng bởi trình độ của người lập trình.  Hai phương pháp đánh giá độ phức tạp của  Chọn được các bộ dữ liệu thử đặc trưng cho thuật toán: tất cả tập các dữ liệu vào của thuật toán: khó  Phương pháp thực nghiệm. khăn và tốn nhiều chi phí.  Phương pháp xấp xỉ toán học.  Phụ thuộc vào phần cứng. 25 26 Phƣơng Pháp Xấp Xỉ Phƣơng Pháp Xấp Xỉ  Đánh giá giá thuật toán theo hướng tiệm xấp xỉ tiệm cận qua các khái niệm O(). Ký pháp Giả sử T(n) là thời gian thực hiện TT và f(n), g(n),  Ưu điểm: Ít phụ thuộc môi trường cũng như phần h(n) là các hàm xác định dương. cứng hơn.  Hàm Theta lớn:  Nhược điểm: Phức tạp. T(n) là hàm Theta lớn của g(n): T(n) =Θ(g(n)) nếu  các hằng số dương c1 ,c2 ,n0 sao cho với mọi CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT  Các trường hợp độ phức tạp quan tâm: n>= n0 : c1 g(n)
Phƣơng Pháp Xấp Xỉ Phƣơng Pháp Xấp Xỉ  Hàm Omega lớn:  Hàm O lớn:  T(n) hàm Omega lớn của g(n), T(n) =O (g(n)) T(n) hàm Omega lớn của g(n): nếu  c và n0 sao cho với mọi n>= n0 : T(n)=Ω(g(n)) nếu  c và n0 sao cho với mọi n>= n0 T(n) = c.g(n)  g(n) giới hạn trên của T(n). 29 30 Phƣơng Pháp Xấp Xỉ Các tính chất Ví dụ, nếu T(n) = n2 + 1 thì T(n) = O(n2). (i) Tính bắc cầu: nếu f(n)= O(g(n)) và g(n)= Chọn c=2 và n0 =1, khi đó với mọi n>=1, ta O(h(n)) thì f(n)= O(h(n)) có T(n)= n2+1
Xác định độ phức tạp Xác định độ phức tạp Quy tắc hằng số  Quy tắc lấy Max Nếu P có T(n)= O(c1f(n)) P có độ Nếu P có T(n)= O( f(n)+g(n)) thì P có độ phức tạp O(f(n)). phức tạp là O( max ( f(n), g(n))). CM: T(n)= O(c1f(n)) nên tồn tại c0>0 và n0 >0 CM: T(n) = O( f(n)+g(n)) nên tồn tại n0>0 và c>0 để CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT để T(n) = n0. T(n) = n0 Đặt c=c0.c1 ta có điều cần CM vậy T(n) =0 và nk >0 để k(n) = nk cho T(n) = n2  cT>=0 và nT >0 để T(n) = nT Chọn c= max (c1,c2) và n0 = max(n1,n2) ta có n: Vậy với mọi n >= max(nT,nk) ta có k(n)T(n) = n0: ckcT(f(n)g(n)). T(n) = T1(n) + T2(n)
4. Bài toán và thuật toán Ví dụ 1 e) Áp dụng đánh giá chương trình Analysing an Algorithm  Câu lệnh đơn thực hiện một thao tác QT hằng số • Simple statement sequence  Câu lệnh hợp thành là dãy các câu lệnh s1; s2; …. ; sk • O(1) as long as k is constant QT tổng  Câu lệnh rẽ nhánh dạng If ..then..else. • Simple loops for(i=0;i
Một số dạng hàm  Đa thức bậc k: P(n), O (nk). 4. Bài toán và thuật toán  logaf(n), O(log f(n)).  Hằng số, O(1) Lgn n nlgn n2 n3 2n 0 1 0 1 1 2  Hàm mũ O(2n.) CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT 1 2 2 4 8 4 2 4 8 16 64 16 3 8 24 64 512 256 4 16 64 256 4096 65536 5 32 160 1024 32768 214748364 8 41 42 Sự Phân Lớp Theo Độ Phức Tạp Của Thuật Toán  Sử dụng ký hiệu BigO  Hằng số : O(c)  logN : O(logN) N : O(N)  NlogN : O(NlogN) Độ phức tạp tăng dần CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT N 2 : O(N2)  N3 : O(N3)  2N : O(2N)  N! :O(N!) 43 44 11
1.2. Quan hệ giữa giải thuật và cấu trúc DL 1.3. Vị trí CTDL trong tin học  Niklaus Wirth:  Thiết kế chương trình  Đặc tả vấn đề CTDL + Thuật toán = Chương trình  Thiết kế cấu trúc dữ liệu và giải thuật Data structures + Algorithms =Program  Cài đặt (C++, Java…)  Thử nghiệm và sửa lỗi  Cần nghiên cứu về thuật toán và CTDL! CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT  Cấu trúc dữ liệu cụ thể: chọn giải thuật  Giải thuật cụ thể: chọn cấu trúc dữ liệu 45 46 1.4. Tìm hiểu tổ chức một số CTDL cơ bản CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT 47 48 12