Bài giảng Cấu trúc dữ liệu và giải thuật - Chương 1: Giới thiệu - Thuật toán - Đào Nam Anh

Data Structure and Algorithm 1 DATA STRUCTURE AND ALGORITHM 1. INTRODUCTION CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT 1. GIỚI THIỆU Dr. Dao Nam Anh Data Structure and Algorithm 2 Outline – Nội dung • Giải thuật • Dữ liệu • Quan hệ Dữ liệu – Giải thuật • Đánh giá độ phức tạp của giải thuật • Đánh giá độ phức tạp dữ liệu • Ký hiệu độ phức tạp Data Structure and Algorithm 3 Resource - Reference Slides of Simonas Šaltenis, modified by Dao Nam Anh, “Algorithms and Data Structures”. Nykredit Center for Database Research, Aalborg University Major Reference: • Robert Sedgewick, and Kevin Wayne, “Algorithms” Princeton University, 2011, Addison Wesley • Giải thuật và lập trình, Lê Minh Hoàng, Đại Học Sư Phạm, 2002 • Cấu trúc dữ liệu và giải thuật, Đinh Mạnh Tường. Data Structure and Algorithm 4 Algorithm – Giải thuật Dữ liệu đầu vào Algorithm Kết quả phụ thuộc dữ liệu đầu vào Simonas Šaltenis slide Data Structure and Algorithm 5 Algorithm – Giải thuật Wiki: • Thuật toán, còn gọi là giải thuật, là một tập hợp hữu hạn của các chỉ thị hay phương cách được định nghĩa rõ ràng cho việc hoàn tất một số sự việc từ một trạng thái ban đầu cho trước; khi các chỉ thị này được áp dụng triệt để thì sẽ dẫn đến kết quả sau cùng như đã dự đoán. • Thuật toán là một bộ các qui tắc hay qui trình cụ thể nhằm giải quyết một vấn đề trong một số bước hữu hạn, hoặc nhằm cung cấp một kết quả từ một tập hợp của các dữ kiện đưa vào. Data Structure and Algorithm 6 Algorithm – Giải thuật • Việc nghiên cứu về thuật toán có vai trò rất quan trọng trong khoa học máy tính vì máy tính chỉ giải quyết được vấn đề khi đã có hướng dẫn giải rõ ràng và đúng. Nếu hướng dẫn giải sai hoặc không rõ ràng thì máy tính không thể giải đúng được bài toán. • Trong khoa học máy tính, thuật toán được định nghĩa là một dãy hữu hạn các bước không mập mờ và có thể thực thi được, quá trình hành động theo các bước này phải dừng và cho được kết quả như mong muốn. Data Structure and Algorithm 7 Algorithm – Giải thuật Ví dụ: thuật toán để giải phương trình bậc nhất P(x): ax + b = c, (a, b, c là các số thực), trong tập hợp các số thực có thể là một bộ các bước sau đây: Nếu a = 0 b = c thì P(x) có nghiệm bất kì b ≠ c thì P(c) vô nghiệm Nếu a ≠ 0 P(x) có duy nhất một nghiệm x = (c - b)/a Data Structure and Algorithm 8 Simonas Šaltenis slide Algorithm – Giải thuật Mục đích thiết kế Giải thuật Mục đích triển khai Hiệu quả Chạy được cả khi đầu vào có lỗi Thích ứng Tái sử dụng Đúng Data Structure and Algorithm 9 Algorithm – Giải thuật Lịch sử • Nhà toán học Batư Mohammed al-Khowarizmi, (850-780BC) đưa ra một các hệ thống giải phương trình tuyến tính và phương trình bậc 2, tên của ông trong tiếng latin dịch là Algorismus • Thuật toán đầu tiên: Euclidean Algorithm, tìm ước số chung lớn nhất của 2 số nguyên, 400-300 B.C. • Thế kỷ 19 – Charles Babbage, Ada Lovelace. • Thế kỷ 20 – Alan Turing, Alonzo Church, John von Neumann Simonas Šaltenis slide Data Structure and Algorithm 10 Sort Algorithm – Giải thuật Ví dụ: Sắp xếp Đầu vào Dãy số nguyên a1, a2, a3,.,an b1,b2,b3,.,bn Kết quả Dãy số theo thứ tự lớn dần 2 5 4 10 7 2 4 5 7 10 Tính đúng đắn: • b1 < b2 < b3 < . < bn Thời gian chạy Phụ thuộc •Số phần tử (n) • Cách sắp xếp (Giải thuật) Simonas Šaltenis slide Data Structure and Algorithm 11 Algorithm – Giải thuật Insertion Sort A 1 nj 3 6 84 9 7 2 5 1 i Chiến lược • Bắt đầu từ phần bên đã xếp bên trái trống” • Chèn vào bên phải phần đã xếp • Thực hiện đến khi đúng thứ tự for j=2 to length(A) do key=A[j] “chèn A[j] vào phần đã sắp xếp A[1..j-1]” i=j-1 while i>0 and A[i]>key do A[i+1]=A[i] i-- A[i+1]:=key Data Structure and Algorithm 12 Algorithm – Giải thuật Insertion Sort A 1 nj 3 6 84 9 7 2 5 1 i Chiến lược • Bắt đầu từ phần bên đã xếp bên trái trống” • Chèn vào bên phải phần đã xếp • Thực hiện đến khi đúng thứ tự for j=2 to length(A) do key=A[j] “chèn A[j] vào phần đã sắp xếp A[1..j-1]” i=j-1 while i>0 and A[i]>key do A[i+1]=A[i] i-- A[i+1]:=key Data Structure and Algorithm 13 Algorithm – Giải thuật Insertion Sort A 1 nj 3 6 84 9 7 2 5 1 i Chiến lược • Bắt đầu từ phần bên đã xếp bên trái trống” • Chèn vào bên phải phần đã xếp • Thực hiện đến khi đúng thứ tự for j=2 to length(A) do key=A[j] “chèn A[j] vào phần đã sắp xếp A[1..j-1]” i=j-1 while i>0 and A[i]>key do A[i+1]=A[i] i-- A[i+1]:=key Data Structure and Algorithm 14 Algorithm – Giải thuật Insertion Sort A 1 nj 3 6 84 7 9 2 5 1 i Chiến lược • Bắt đầu từ phần bên đã xếp bên trái trống” • Chèn vào bên phải phần đã xếp • Thực hiện đến khi đúng thứ tự for j=2 to length(A) do key=A[j] “chèn A[j] vào phần đã sắp xếp A[1..j-1]” i=j-1 while i>0 and A[i]>key do A[i+1]=A[i] i-- A[i+1]:=key Data Structure and Algorithm 15 Algorithm – Giải thuật Insertion Sort A 1 nj 3 6 84 7 9 2 5 1 i Chiến lược • Bắt đầu từ phần bên đã xếp bên trái trống” • Chèn vào bên phải phần đã xếp • Thực hiện đến khi đúng thứ tự for j=2 to length(A) do key=A[j] “chèn A[j] vào phần đã sắp xếp A[1..j-1]” i=j-1 while i>0 and A[i]>key do A[i+1]=A[i] i-- A[i+1]:=key Data Structure and Algorithm 16 Algorithm – Giải thuật Insertion Sort A 1 nj 3 6 84 7 9 2 5 1 i Chiến lược • Bắt đầu từ phần bên đã xếp bên trái trống” • Chèn vào bên phải phần đã xếp • Thực hiện đến khi đúng thứ tự for j=2 to length(A) do key=A[j] “chèn A[j] vào phần đã sắp xếp A[1..j-1]” i=j-1 while i>0 and A[i]>key do A[i+1]=A[i] i-- A[i+1]:=key Data Structure and Algorithm 17 Algorithm – Giải thuật Insertion Sort A 1 nj 3 6 74 8 9 2 5 1 i Chiến lược • Bắt đầu từ phần bên đã xếp bên trái trống” • Chèn vào bên phải phần đã xếp • Thực hiện đến khi đúng thứ tự for j=2 to length(A) do key=A[j] “chèn A[j] vào phần đã sắp xếp A[1..j-1]” i=j-1 while i>0 and A[i]>key do A[i+1]=A[i] i-- A[i+1]:=key Data Structure and Algorithm 18 Algorithm – Giải thuật Insertion Sort A 1 nj 3 6 74 8 9 2 5 1 i Chiến lược • Bắt đầu từ phần bên đã xếp bên trái trống” • Chèn vào bên phải phần đã xếp • Thực hiện đến khi đúng thứ tự for j=2 to length(A) do key=A[j] “chèn A[j] vào phần đã sắp xếp A[1..j-1]” i=j-1 while i>0 and A[i]>key do A[i+1]=A[i] i-- A[i+1]:=key Data Structure and Algorithm 19 Algorithm – Giải thuật Insertion Sort A 3 6 74 8 9 2 5 1 3 6 74 8 9 2 5 1 3 6 74 8 9 2 5 1 3 6 74 8 2 9 5 1 3 6 74 8 2 9 5 1 3 6 74 2 8 9 5 1 2 4 63 7 8 9 5 1 Data Structure and Algorithm 20 Cấu trúc dữ liệu • Khi giải một bài toán, ta cần phải định nghĩa tập hợp dữ liệu để biểu diễn tình trạng cụ thể. Việc lựa chọn này tuỳ thuộc vào vấn đề cần giải quyết và những thao tác sẽ tiến hành trên dữ liệu vào. • Có những thuật toán chỉ thích ứng với một cách tổ chức dữ liệu nhất định, đối với những cách tổ chức dữ liệu khác thì sẽ kém hiệu quả hoặc không thể thực hiện được. Chính vì vậy nên bước xây dựng cấu trúc dữ liệu không thể tách rời bước tìm kiếm thuật toán giải quyết vấn đề. Data Structure and Algorithm 21 Các tiêu chuẩn khi lựa chọn cấu trúc dữ liệu • Cấu trúc dữ liệu trước hết phải biểu diễn được đầy đủ các thông tin nhập và xuất của bài toán • Cấu trúc dữ liệu phải phù hợp với các thao tác của thuật toán mà ta lựa chọn để giải quyết bài toán. • Cấu trúc dữ liệu phải cài đặt được trên máy tính với ngôn ngữ lập trình đang sử dụng • Đối với một số bài toán, trước khi tổ chức dữ liệu ta phải viết một đoạn chương trình nhỏ để khảo sát xem dữ liệu cần lưu trữ lớn tới mức độ nào. Data Structure and Algorithm 22 Cấu trúc dữ liệu • Hạt nhân của các chương trình máy tính là sự lưu trữ và xử lý thông tin. • Việc tổ chức dữ liệu như thế nào có ảnh hưởng rất lớn đến cách thức xử lý dữ liệu đó cũng như tốc độ thực thi và sự chiếm dụng bộ nhớ của chương trình. Data Structure and Algorithm 23 Cấu trúc dữ liệu • Việc đặc tả bằng các cấu trúc tổng quát (generic structures) và các kiểu dữ liệu trừu tượng (abstract data types) còn cho phép người lập trình có thể dễ dàng hình dung ra các công việc cụ thể và giảm bớt công sức trong việc chỉnh sửa, nâng cấp và sử dụng lại các thiết kế đã có. Data Structure and Algorithm 24 Kiểu dữ liệu cơ bản • C++
Boolean – bool
Liệt kê – enum
Chữ - char
Số nguyên – short, int, long
Thập phân – float, double Nor Bahiah Hj Ahmad, Software Engineering Department, FSKSM, UTM Data Structure and Algorithm 25 Structured Data Types Storage Structure Linked Structure State Structure •Array •Structure (struct) •Unsorted Linked List •Sorted Linked List •Binary Tree •Graph •Network •Stack •Queue Nor Bahiah Hj Ahmad, Software Engineering Department, FSKSM, UTM Data Structure and Algorithm 26 Lưu đồ giải thuật (Flowchart) Data Structure and Algorithm 27 Đánh giá giải thuật • Hiệu quả:
Thời gian chạy
Sử dụng bộ nhớ • Đánh giá dựa và độ lớn của dữ liệu đầu vào:
Số lượng dữ liệu (các con số, các điểm)
Số lượng các bit biểu diễn con số Data Structure and Algorithm 28 Đánh giá giải thuật Insertion Sort for j=2 to length(A) do key=A[j] “chèn A[j] vào phần đã sắp xếp A[1..j-1]” i=j-1 while i>0 and A[i]>key do A[i+1]=A[i] i-- A[i+1]:=key cost c1 c2 0 c3 c4 c5 c6 c7 times n n-1 n-1 n-1 n-1 2 n jj t =∑ 2 ( 1) n jj t = −∑ 2 ( 1) n jj t = −∑ • Thời gian thực hiện là hàm số phụ thuộc độ lớn của dữ liệu đầu vào Simonas Šaltenis slide Data Structure and Algorithm 29 Đánh giá giải thuật Insertion Sort • Trường hợp tốt nhất: mọi phần tử đã được sắp xếp → tj=1, thời gian thực hiện = f(n), tuyến tính. • Trường hợp xấu nhất : các phần tử trong thứ tự ngược lại → tj=j, thời gian thực hiện = f(n2), • Trường hợp trung bình: → tj=j/2, thời gian thực hiện = f(n2), )(1 2 *)1( 2 2 2 nf nn jt n j n j j ≈− + ==∑∑ = = Data Structure and Algorithm 30 Đánh giá giải thuật
Tùy vào độ lớn của n, phân tích thời gian thực hiện : 1n 2n 3n 4n 5n 6n Simonas Šaltenis slide Data Structure and Algorithm 31 Đánh giá giải thuật
Với mọi giá trị n: 1n 2n 3n 4n 5n 6n Input instance size R u n n i n g t i m e 1 2 3 4 5 6 7 8 9 10 11 12 .. best-case average-case worst-case Data Structure and Algorithm 32 Đánh giá giải thuật • Trường hợp xấu nhất thường được sử dụng:
Rất cần thiết phải biết khi trường hợp xấu nhất xảy ra để phòng ngừa (điều hành không lưu, phẫu thuật)
Trường hợp xấu nhất xảy ra thường xuyên cho một số thuật toán
Trường hợp trung bình cũng cần được xem xét
Tuy nhiên thường khó tìm trường hợp trung bình Data Structure and Algorithm 33 Đánh giá giải thuật 1,00E-01 1,00E+00 1,00E+01 1,00E+02 1,00E+03 1,00E+04 1,00E+05 1,00E+06 1,00E+07 1,00E+08 1,00E+09 1,00E+10 2 4 8 16 32 64 128 256 512 1024 n T ( n ) n log n sqrt n n log n 100n n^2 n^3 Data Structure and Algorithm 34 Đánh giá giải thuật 1,00E-01 1,00E+11 1,00E+23 1,00E+35 1,00E+47 1,00E+59 1,00E+71 1,00E+83 1,00E+95 1,00E+107 1,00E+119 1,00E+131 1,00E+143 1,00E+155 2 4 8 16 32 64 128 256 512 1024 n T ( n ) n log n sqrt n n log n 100n n^2 n^3 2^n Data Structure and Algorithm 35 Đánh giá giải thuật Insertion Sort • Thuật toán Insertion Sort có phải là thuật sẵp xếp tốt nhất? • Có chiến lược khác dựa trên chia nhóm • MergeSort
Bài toán sắp xếp được chia thành
Sắp xếp và sau đó
Ghép kết quả với nhau
Thời gian thực hiện f(n log n) Data Structure and Algorithm 36 Ký hiệu về độ phức tạp • Cho một giải thuật thực hiện trên dữ liệu với kích thước n. Giả sử T(n) là thời gian thực hiện một giải thuật đó, g(n) là một hàm xác định dương với mọi n. Khi đó ta nói độ phức tạp tính toán của giải thuật là: • Θ(g(n)) nếu tồn tại các hằng số dương c1, c2 và n0 sao cho c1.g(n) ≤ f(n) ≤ c2.g(n) với mọi n≥ n0. Ký pháp này được gọi là ký pháp Θ lớn (big-theta notation). Trong ký pháp Θ lớn, hàm g(.) được gọi là giới hạn chặt (asymptotically tight bound) của hàm T(.) Data Structure and Algorithm 37 Ký hiệu về độ phức tạp • O(g(n)) nếu tồn tại các hằng số dương c và n0 sao cho T(n) ≤ c.g(n) với mọi n ≥ n0. Ký pháp này được gọi là ký pháp chữ O lớn (big-oh notation). Trong ký pháp chữ O lớn, hàm g(.) được gọi là giới hạn trên (asymptotic upper bound) của hàm T(.) • Ω(g(n)) nếu tồn tại các hằng số dương c và n0 sao cho c.g(n) ≤ T(n) với mọi n ≥ n0. Ký hiệu này gọi là ký pháp Ω lớn (big-omega notation). Trong ký pháp Ω lớn, hàm g(.) được gọi là giới hạn dưới (asymptotic lower bound) của hàm T(.) Data Structure and Algorithm 38 Ký hiệu về độ phức tạp Ví dụ • O(n) • O(ln n) • O(n2) • O(nln n) Data Structure and Algorithm 39 Đánh giá độ phức tạp dữ liệu • Tìm xem thuật toán sử dụng bộ nhớ như thế nào, là hàm số phụ thuộc độ lớn dữ liệu đầu vào • Tương tự như đánh giá thuật toán Data Structure and Algorithm 40 Đánh giá giải thuật Insertion Sort for j=2 to length(A) do key=A[j] “chèn A[j] vào phần đã sắp xếp A[1..j-1]” i=j-1 while i>0 and A[i]>key do A[i+1]=A[i] i-- A[i+1]:=key • Thời gian tính toán : O(n2) • Không gian tính toán: O(n) Data Structure and Algorithm 41 Ví dụ 2: Tìm kiếm Đầu vào • Cho một dãy các con số (cơ sở dữ liệu) • 1 con số a1, a2, a3,.,an; q j Kết quả • Vị trí của con số trong dãy số hoặc NIL 2 5 4 10 7; 5 2 2 5 4 10 7; 9 NIL Data Structure and Algorithm 42 Ví dụ 2: Tìm kiếm j=1 while j<=length(A) and A[j]!=q do j++ if j<=length(A) then return j else return NIL  Trường hợp xấu nhất: f(n), Trường hợp trung bình: f(n/2)  Đây là giới hạn dưới của bài toán tìm kiếm trong dãy số. Data Structure and Algorithm 43 Ví dụ 3: Tìm kiếm Đầu vào • Một dãy số đã sắp xếp tăng dần (CSDL) • 1 con số a1, a2, a3,.,an; q j Kết quả • vị trí của con số trong dãy số hoặc NIL 2 4 5 7 10; 5 2 2 4 5 7 10; 9 NIL Data Structure and Algorithm 44 Tìm kiếm nhị phân left=1 right=length(A) do j=(left+right)/2 if A[j]==q then return j else if A[j]>q then right=j-1 else left=j+1 while left<=right return NIL  Ý tưởng: Chia và tìm – một trong các kỹ thuật cơ bản Data Structure and Algorithm 45 Tìm kiếm nhị phân • Vòng lặp chạy bao lần?
Sau mỗi lần lặp chiều dài giảm một nửa
Sau bao lần giảm nửa thì giá trị n trở thành 1?
lg n Data Structure and Algorithm 46 Discussion – Câu hỏi