1. Trang Chủ
  2. Cơ sở dữ liệu
  3. Bài giảng Cấu trúc dữ liệu và giải thuật - Chương 1: Các khái niệm cơ bản về Cấu trúc dữ liệu và giải thuật

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

Bài giảng Cấu trúc dữ liệu và giải thuật - Chương 1: Các khái niệm cơ bản về Cấu trúc dữ liệu và giải thuật. Chương này có nội dung trình bày về: khái niệm, các vấn đề liên quan của cấu trúc dữ liệu và giải thuật; một số cấu trúc dữ liệu cơ bản; ngôn ngữ diễn đạt giải thuật; thiết kế và phân tích giải thuật;... Mời các bạn cùng tham khảo! 8/4/2020 BÀI GIẢNG ĐIỆN TỬ HP:CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT Số TC: 3 Bộ môn: Tin học Cấu trúc dữ liệu và giải thuật 1 Giới thiệu học phần Số tín chỉ: 3 (36,9)

Thể loại Tài liệu miễn phí Cơ sở dữ liệu

Số trang 20

Ngày tạo 4/8/2023 8:59:25 PM +00:00

Loại tệp PDF

Kích thước 0.71 M

Tên tệp

Tải Bài giảng Cấu trúc dữ liệu và giải thuật - Chương ... (.pdf)

Xem mẫu

  1. 8/4/2020 BÀI GIẢNG ĐIỆN TỬ HP:CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT Số TC: 3 Bộ môn: Tin học Cấu trúc dữ liệu và giải thuật 1 Giới thiệu học phần Số tín chỉ: 3 (36,9) Mục tiêu: Cung cấp: ▪ Một số khái niệm cơ bản về giải thuật và cấu trúc dữ liệu; vai trò của cấu trúc dữ liệu và giải thuật (CTDL và GT) trong hệ thống thông tin (HTTT); Một số cấu trúc dữ liệu cơ bản bao gồm: Mảng (Array), Danh sách (List), Danh sách liên kết (Linked List), Ngăn xếp (Stack) và Hàng đợi (Queue), và Cây (Tree) Cấu trúc dữ liệu và giải thuật 2 1
  2. 8/4/2020 Giới thiệu học phần Nội dung chính: Chương 1: Các khái niệm cơ bản về CTDL & GT (6t) Chương 2: Mảng và danh sách (12t) Chương 3: Cây (12t) Chương 4: Một số giải thuật sắp xếp và tìm kiếm (15t) Cấu trúc dữ liệu và giải thuật 3 Tài liệu tham khảo ❖Đỗ Xuân Lôi, Cấu trúc dữ liệu và giải thuật, NXB ĐHQGHN, 2008 ❖Nguyễn ĐÌnh Hóa, Cấu trúc dữ liệu và giải thuật, 2008, NXB ĐHQGHN ❖Lê Minh Hoàng, Bài giảng chuyên đề ❖https://www.tutorialspoint.com/data_structures_algorit hms/ ❖https://www.e- reading.club/bookreader.php/138793/Advanced_C.pdf. Cấu trúc dữ liệu và giải thuật 4 2
  3. 8/4/2020 Chương 1. Các khái niệm cơ bản về CTDL & GT 1.1 Cấu trúc dữ liệu 1.2 Giải thuật Cấu trúc dữ liệu và giải thuật 5 1.1 Cấu trúc dữ liệu (Data Structures) 1.1.1 Khái niệm chung 1.1.2 Các vấn đề liên quan 1.1.3 Một số cấu trúc dữ liệu cơ bản Cấu trúc dữ liệu và giải thuật 6 3
  4. 8/4/2020 1.1.1 Khái niệm chung ❖Mục tiêu của tin học? ❖Dữ liệu là gì? →Kiểu dữ liệu ? (kiểu cơ sở/ kiểu có cấu trúc phức tạp) ❖Khái niệm chung: CTDL là một cách thể hiện và tổ chức dữ liệu trong máy tính sao cho nó được sử dụng một cách có hiệu quả nhất. ❖Khái niệm khác: CTDL là một dữ liệu phức hợp, gồm nhiều thành phần dữ liệu, mỗi thành phần hoặc là dữ liệu cơ sở hoặc là một CTDL đã được xây dựng. Các thành phần dữ liệu tạo nên một CTDL được liên kết với nhau theo một cách nào đó. Cấu trúc dữ liệu và giải thuật 7 1.1.2 Các vấn đề liên quan Tầm quan trọng của việc lựa chọn CTDL ▪ Tổ chức dữ liệu : dl vào/ra/trung gian ▪ Xây dựng giải thuật →Các cách cài đặt khác nhau →Thực hiện thao tác thuận lợi/khôngthuận lợi →CTDL thay đổi → Thuật toán thay đổi Cấu trúc dữ liệu và giải thuật 8 4
  5. 8/4/2020 1.1.2 Các vấn đề liên quan Các tiêu chuẩn khi lựa chọn CTDL ▪ CTDL phải biểu diễn được đầy đủ các thông tin của bài toán. (in/out) → phản ánh đúng thực tế ▪ Cài đặt được trên máy tính và ngôn ngữ lập trình đang sử dụng ▪ Phù hợp với các thao tác của thuật toán (đặc biệt thao tác được sử dụng nhiều) → phát triển thuật toán đơn giản và đạt hiệu quả. ▪ Tiết kiệm tài nguyên Cấu trúc dữ liệu và giải thuật 9 1.1.3 Một số cấu trúc dữ liệu cơ bản ❖Mảng (array) ❖Bản ghi (record)/cấu trúc (struct) ❖Tập hợp (set) ❖Tệp (file) ❖Xâu (string) ❖….(bảng băm, danh sách liên kết) Cấu trúc dữ liệu và giải thuật 10 5
  6. 8/4/2020 1.2 Giải thuật (Algorithm) 1.2.1 Khái niệm chung 1.2.2 Ngôn ngữ diễn đạt giải thuật 1.2.3 Thiết kế và phân tích giải thuật 1.2.4 Giải thuật đệ quy Cấu trúc dữ liệu và giải thuật 11 1.2.1 Khái niệm chung ❖Thuật toán là một dãy hữu hạn các bước được sắp xếp theo một trật tự xác định, mỗi bước mô tả chính xác các phép toán hoặc hành động cần thực hiện, để giải quyết một vấn đề. ❖Thuật toán là một dãy hữu hạn các thao tác, sắp xếp theo một trật tự xác định, sau khi thực hiện, từ Input ta nhận được Output cần tìm. Cấu trúc dữ liệu và giải thuật 12 6
  7. 8/4/2020 1.2.1 Khái niệm chung ❖Các tính chất (đặc trưng) của thuật toán: ▪ Tính vào (input) ▪ Tính ra (output) ▪ Tính đơn định (xác định / đơn nghĩa) ▪ Tính đúng đắn ▪ Tính dừng (tính kết thúc / tính đóng) ▪ Tính phổ dụng ▪ Tính khả thi/hiệu quả Cấu trúc dữ liệu và giải thuật 13 1.2.2 Ngôn ngữ diễn đạt giải thuật ❖Cách liệt kê: liệt kê các bước cần thực hiện ❖Sơ đồ khối: sử dụng các hình khối oval, chữ nhật, hình thoi và mũi tên,… ❖Ngôn ngữ lập trình: dùng các ký hiệu và các quy tắc của ngôn ngữ lập trình Cấu trúc dữ liệu và giải thuật 14 7
  8. 8/4/2020 1.2.2 Ngôn ngữ diễn đạt giải thuật Ví dụ: - Input:N nguyên dương, dãy a 1,..., an. - Output : Tìm Max của dãy đã cho. Ý tưởng: ❖Giả thiết Max = a1. Với mỗi i, nếu ai > Max thì thay giá trị Max= ai. Cấu trúc dữ liệu và giải thuật 15 1.2.2 Ngôn ngữ diễn đạt giải thuật ❖Cách liệt kê Bước 1. Nhập N và dãy a1, ..., an Bước 2. Đặt Max = a1, i = 2; Bước 3. Nếu i > N thì đến Bước 5; Bước 4. 4.1. N ếu ai > Max thì Max = ai. 4.2. Đặt i=i+1 rồi quay B.3; Bước 5. Đưa ra Max rồi kết thúc. Cấu trúc dữ liệu và giải thuật 16 8
  9. 8/4/2020 1.2.2 Ngôn ngữ diễn đạt giải thuật Bắt đầu Nhập N, a1,a2, …an Max=a1,i=2 i=i+1 i>N Xuất Max Max= ai ai>Max Kết thúc Cấu trúc dữ liệu và giải thuật 17 1.2.2 Ngôn ngữ diễn đạt giải thuật ❖Dùng ngôn ngữ lập trình int max(int *x,int n) //hàm tìm max { int result; result=x[0]; for (int i=1;i
  10. 8/4/2020 1.2.3 Thiết kế và phân tích giải thuật ❖Thiết kế giải thuật ▪ Ý nghĩa: Sự đa dạng và phức tạp của các bài toán →cần sử dụng nguồn nhân lực lớn hơn →Thời gian để thử nghiệm, bảo trì và mở rộng hệ thống chiềm phần đáng kể so với thời gian xây dựng CT. Cấu trúc dữ liệu và giải thuật 19 1.2.3 Thiết kế và phân tích giải thuật ❖Module hóa và việc giải quyết bài toán ▪ Chiến thuật “chia để trị” (divide and conquer) ▪ Cách thiết kế “từ đỉnh xuống”(top-down) ❖Phương pháp tinh chỉnh từng bước (stepwise refinement): là phương pháp thiết kế giải thuật gắn liền với lập trình →Phản ánh: quá trình modun hóa bài toán và thiết kế kiểu top-down (từ bài toán đến chương trình) Cấu trúc dữ liệu và giải thuật 20 10
  11. 8/4/2020 Ví dụ ❖ Quản lý học bổng của sinh viên, lập báo cáo tổng kết theo kỳ ❖ Thiết kế: ❖ B1: xác định input/ouput ▪ Input: file chứa thông tin HB của SV: mã SV, ĐTB, Mức HB ▪ Output: Tìm kiếm, cập nhập, hiển thị thông tin của SV, In bảng tổng kết ❖ B2: Xác định các công việc chủ yếu ▪ Đọc file vào bộ nhớ trong → lấy thông tin của SV ▪ Xử lý thông tin đọc được ▪ Ghi file → Lưu thông tin cập nhật vào file ❖ B3: Giải quyết từng công việc một cách chi tiết bằng cách lặp lại B1 và B2 Cấu trúc dữ liệu và giải thuật 21 Ví dụ Cấu trúc dữ liệu và giải thuật 22 11
  12. 8/4/2020 Ví dụ ❖ Đọc file: ▪ Input: file thông tin trên đĩa ▪ Output: đọc file và lưu vào mảng (mỗi ptử lưu thông tin một sinh viên) ❖ Ghi file ▪ Input: Mảng lưu thông tin các sinh viên ▪ Output: Lưu trở lại file ❖ Xử lý thông tin ▪ Input: Mảng lưu thông tin của các sinh viên ▪ Output: • Tìm một sinh viên cho trước • Hiển thị thông tin của sinh viên • Cập nhật thông tin của sinh viên • In bản tổng kết Cấu trúc dữ liệu và giải thuật 23 Ví dụ Cấu trúc dữ liệu và giải thuật 24 12
  13. 8/4/2020 1.2.3 Thiết kế và phân tích giải thuật ❖Các chiến lược thiết kế giải thuật: ▪ Module hóa→Chia để trị (divide and conquer/top-down) ▪ Phương pháp tham lam (greedy) ▪ Phương pháp quy hoạch động ▪ Phương pháp nhánh cận ▪ Phương pháp quay lui Cấu trúc dữ liệu và giải thuật 25 1.2.3 Thiết kế và phân tích giải thuật ❖Phân tích giải thuật ▪ Tại sao cần phân tích giải thuật? ▪ Chương trình chạy đúng chưa đủ, cần xét tính hiệu quả (kg/tg) với các tập dữ liệu khác nhau ▪ Lưu ý: chỉ phân tích các giải thuật đúng – là thuật toán mà với một bộ dữ liệu vào bất kỳ thì thuật toán dừng và cho kết quả đúng Cấu trúc dữ liệu và giải thuật 26 13
  14. 8/4/2020 1.2.3 Thiết kế và phân tích giải thuật ❖Các lưu ý khi phân tích giải thuật ▪ Tính đúng đắn của giải thuật ▪ Tính đơn giản của giải thuật ▪ Tốc độ thực hiện (hoặc thời gian thực hiện) và dung lượng bộ nhớ cần chiếm dụng của giải thuật (còn gọi là tính hiệu quả của giải thuật ) → chỉ đánh giá thời gian thực hiện giải thuật Cấu trúc dữ liệu và giải thuật 27 1.2.3 Thiết kế và phân tích giải thuật ❖Đánh giá thời gian thực hiện giải thuật ▪ Thử nghiệm: không chính xác (vì phụ thuộc vào nhiều yếu tố) ▪ Lý thuyết: Coi thời gian thực hiện giải thuật là một hàm của cỡ dữ liệu vào. T(n)→ gọi là “độ phức tạp của giải thuật” ▪ Cách xác định: tính số các phép toán sơ cấp mà giải thuật cần dùng (lưu ý thao tác đặc trưng của giải thuật) Cấu trúc dữ liệu và giải thuật 28 14
  15. 8/4/2020 1.2.3 Thiết kế và phân tích giải thuật ❖Khái niệm hàm O lớn: Hàm T(n) được gọi là Omega lớn của g(n), ký hiệu T(n) =O (g(n)) nếu  c>0 và n0 sao cho với mọi n  n0 : T(n)  c g(n) Trong đó: g(n) là giới hạn trên của T(n). Cấu trúc dữ liệu và giải thuật 29 1.2.3 Thiết kế và phân tích giải thuật ❖Quy tắc xác định độ phức tạp của giải thuật ▪ Quy tắc hằng số: Nếu P có T(n)= O(c1f(n)) →P có độ phức tạp O(f(n)). ▪ Quy 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))). ▪ Quy 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)). ▪ Quy tắc nhân: Nếu P có T(n)= O(f(n)). Khi đó nếu thực hiện k(n) lần P với k(n)=O(g(n)) thì độ phức tạp là O(f(n) g(n)). Cấu trúc dữ liệu và giải thuật 30 15
  16. 8/4/2020 1.2.3 Thiết kế và phân tích giải thuật Áp dụng đánh giá chương trình ❖ Câu lệnh đơn thực hiện một thao tác →QT hằng số ❖Câu lệnh hợp thành là một dãy các câu lệnh →QT tổng ❖Câu lệnh rẽ nhánh dạng If ...else. →QT Max ❖ Các câu lệnh lặp: while, do …while, for →QT Nhân Cấu trúc dữ liệu và giải thuật 31 1.2.3 Thiết kế và phân tích giải thuật ❖Ví dụ: chương trình lấy max ở trên Cấu trúc dữ liệu và giải thuật 32 16
  17. 8/4/2020 1.2.4 Giải thuật đệ quy ❖Khái niệm: Ta nói một đối tượng là đệ quy nếu nó được định nghĩa qua chính nó hoặc một đối tượng khác cùng dạng với nó bằng quy nạp. ❖Ví dụ: Tính giai thừa/ tính tổ hợp ❖Giải thuật đệ quy: Nếu lời giải một bài toán P được thực hiện bằng lời giải của bài toán P’ có dạng giống như P thì đố là một lời giải đệ quy. Giải thuật tương ứng với lời giải như vậy gọi là giải thuật đệ quy Cấu trúc dữ liệu và giải thuật 33 1.2.4 Giải thuật đệ quy ❖Điều kiện: ▪ Có điểm dừng (trường hợp suy biến không cần đệ quy/ phần neo) ▪ Làm cho kích thước bài toán nhỏ hơn (để về gần TH suy biến/ phần đệ quy) ❖Chú ý: ▪ P’ giống P ▪ P’ “nhỏ hơn” P theo nghĩa nào đó Cấu trúc dữ liệu và giải thuật 34 17
  18. 8/4/2020 1.2.4 Giải thuật đệ quy ❖Thiết kế giải thuật đệ quy: 3bước ▪ Thông số hóa bài toán ▪ Tìm điều kiện dừng ▪ Phân rã bài toán Cấu trúc dữ liệu và giải thuật 35 1.2.4 Giải thuật đệ quy ❖Ví dụ: ▪ Tìm từ trong từ điển ▪ Tìm tệp trong tệp trên máy tính Cấu trúc dữ liệu và giải thuật 36 18
  19. 8/4/2020 1.2.4 Giải thuật đệ quy ❖Ưu điểm: ▪ Mạnh, rõ ràng, chặt chẽ ▪ Thiết kế TT đơn giản, ngắn gọn ▪ Trong một số giải thuật đệ quy cũng có hiệu quả cao (quick sort) ❖Nhược điểm: ▪ Lời gọi hàm tốn rất nhiều thời gian, không gian nhớ. ▪ Tốc độ chậm ▪ Thận trọng đừng để chạy vô hạn ❖Lưu ý: mọi giải thuật đệ quy đều có thể thay bằng một giải thuật không đệ quy → khử đệ quy Cấu trúc dữ liệu và giải thuật 37 1.2.4 Giải thuật đệ quy ❖Khử đệ quy (tự học) Cấu trúc dữ liệu và giải thuật 38 19
  20. 8/4/2020 1.2.2 Ngôn ngữ diễn đạt giải thuật #include void main() #include { #include int n,*a; printf("nhap so phan tu:"); scanf("%d", int max(int *x,int n) &n); { int result = x[0]; a=(int*)malloc(n*sizeof(int)); for (int i=1;i
nguon tai.lieu . vn
Tin học văn phòng Đồ họa - Thiết kế - Flash Quản trị Web Cơ sở dữ liệu Quản trị mạng Kỹ thuật lập trình Hệ điều hành Phần cứng An ninh - Bảo mật Chứng chỉ quốc tế Thủ thuật máy tính Điện - Điện tử Kinh tế học Hoá học Xã hội học Môi trường