Thuật toán và độ phức tạp thuật toán

NHẬP MÔN THUẬT TOÁNTrình bày : Lê Quang HùngKhoa Tin học, Đại học Quy Nhơn.Mob. 0983.444.056.11/16/20201 Giới thiệuThời lượng: 60 tiết LTMục tiêu:- Làm quen với việc diễn đạt thuật toán;- Đánh giá thuật toán;- Một số KT thiết kế TT;- Vận dụng các yếu tố này vào việc viết CT;- Giải đáp thắc mắc của học viên. 11/16/20202Tài liệu tham khảoGiáo trình Nhập môn thuật toán (Hồ Anh Minh, ĐH Quy Nhơn).Hồ Sĩ Đàm, Nguyễn Việt, Hà Bùi Thế DuyĐinh Mạnh Tường, Đỗ Xuân Lôi.R. Sedgevick,Algorithms Addison- Wesley, Bản dịch tiếng Việt: Cẩm nang thuật toán ( tập 1, 2).Thomas H. Cormen, Introduction to Algorithms, MIT Press, 199011/16/20203 Nội dungPhần I. Các khái niệm cơ bản.Phần II. Các chiến lược thiết kế thuật toán.11/16/20204CHƯƠNG I: THUẬT TOÁN VÀ ĐỘ PHỨC TẠP THUẬT TOÁNThuật toán. Các đặc trưng của thuật toán. Mô tả thuật toán.Độ phức tạp thuật toán và phân tích TT.Vấn đề lựa chọn thuật toán để cài đặt.11/16/20205Thuật toán (1)ThuËt to¸n (algorithm) lµ mét trong những kh¸i niÖm quan träng nhÊt trong tin häc. ThuËt ngữ thuËt to¸n xuÊt ph¸t tõ nhµ to¸n häc A rËp Abu Ja'far Mohammed ibn Musa al Khowarizmi (kho¶ng năm 825). 11/16/20206Thuật toán (2)ThuËt to¸n lµ mét d·y hữu h¹n c¸c b­íc, 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 sè vÊn ®Ò. (Tõ ®iÓn Oxford Dictionary ®Þnh nghÜa, Algorithm: set of well - defined rules for solving a problem in a finite number of steps.)11/16/20207Thuật toán (3)Víi mét vÊn ®Ò ®Æt ra, cã thÓ cã mét hoÆc nhiÒu thuËt to¸n gi¶i. Mét vÊn ®Ò cã thuËt to¸n gi¶i gäi lµ vÊn ®Ò gi¶i ®­îc (b»ng thuËt to¸n). Mét vÊn ®Ò kh«ng tån t¹i thuËt to¸n gi¶i gäi lµ vÊn ®Ò kh«ng gi¶i ®­îc (b»ng thuËt to¸n). 11/16/20208Các đặc trưng của thuật toán (1)1. Input. Mçi thuËt to¸n cÇn cã mét sè (cã thÓ b»ng kh«ng) dữ liÖu vµo (input). Đã lµ c¸c gi¸ trÞ cÇn ®­a vµo khi thuËt to¸n b¾t ®Çu lµm viÖc. 2. Output. Mçi thuËt to¸n cÇn cã mét hoÆc nhiÒu dữ liÖu ra (output). Đã lµ c¸c gi¸ trÞ cã quan hÖ hoµn toµn x¸c ®Þnh víi c¸c dữ liÖu vµo vµ lµ kÕt qu¶ cña sù thùc hiÖn thuËt to¸n. 11/16/20209Các đặc trưng của thuật toán (2)3. TÝnh x¸c ®Þnh. Mçi b­íc cña thuËt to¸n cÇn ph¶i ®­îc m« t¶ mét c¸ch chÝnh x¸c, chØ cã mét c¸ch hiÓu duy nhÊt. 4. TÝnh dõng. Víi mäi bé dữ liÖu vµo tho¶ m·n c¸c ®iÒu kiÖn cña dữ liÖu vµo (tøc lµ ®­îc lÊy ra tõ c¸c tËp gi¸ trÞ cña c¸c dữ liÖu vµo), thuËt to¸n ph¶i dõng l¹i sau mét sè hữu h¹n b­íc thùc hiÖn. 11/16/202010Các đặc trưng của thuật toán (3)5. TÝnh ®¬n trÞ. KÕt qu¶ cña mçi hµnh ®éng chØ phô thuéc vµo kÕt qu¶ cña c¸c hµnh ®éng ®­îc thùc hiÖn tr­íc ®ã vµ dữ liÖu vµo. Víi ®Çu vµo nh­ nhau, thuËt to¸n sÏ cho ®Çu ra nh­ nhau.6. TÝnh tæng qu¸t. ThuËt to¸n ph¶i ¸p dông ®­îc cho mét líp c¸c bµi to¸n cïng lo¹i hoÆc mét bµi to¸n víi c¸c ®Çu vµo cô thÓ kh¸c nhau. 11/16/202011Mô tả thuật toán (1)Mô tả thuật toán là việc nêu ra các bước hành động cũng như trình tự thực hiện các bước.Cã nhiÒu ph­¬ng ph¸p biÓu diÔn thuËt to¸n: Dïng ng«n ngữ tù nhiªn. Dïng m· gi¶ (tùa ng«n ngữ lập trình). Dïng s¬ ®å khèi. Dïng ng«n ngữ lập trình (Mét ch­¬ng trình lµ sù biÓu diÔn cña mét thuËt to¸n trong Ng«n ngữ lập trình). KÕt hîp m· gi¶ víi NNTN.11/16/202012Ví dụ 1: Cho 2 số nguyên dương a và b, tìm 2 số q và r sao cho a= bq+r. 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 Max thì thay giá trị Max= ai.Mô tả thuật toán (4)11/16/202015Mô tả thuật toán (5)2 cách mô tả thuật toán: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. 11/16/202016Mô tả thuật toán (6)Ví dụ 3: Thuật toán giải phương trình bậc hai ?Ví dụ 4: Thuật toán kiểm tra số tự nhiên n (n>2) có phải là số nguyên tố không ?Dùng ngôn ngữ tự nhiên,Dùng mã giả,Dùng ngôn ngữ lập trình.11/16/202017Sự cần thiết phải phân tích, đánh giá giải thuậtCần phải phân tích, đánh giá giải thuật để:Lựa chọn một giải thuật tốt nhất trong các giải thuật để cài đặt chương trình giải quyết bài toán đặt ra.Cải tiến giải thuật hiện có để được một giải thuật tốt hơn. 11/16/202018Tiêu chuẩn đánh giá một giải thuật là tốtMột giải thuật được xem là tốt nếu nó đạt các tiêu chuẩn sau:Thực hiện đúng.Tốn ít bộ nhớ.Thực hiện nhanh.Trong khuôn khổ môn học này, chúng ta chỉ quan tâm đến tiêu chuẩn thực hiện nhanh. 11/16/202019Thời gian thực hiện của chương trìnhThời gian thực hiện một chương trình là một hàm của kích thước dữ liệu vào, ký hiệu T(n) trong đó n là kích thước (độ lớn) của dữ liệu vào.Ví dụ : Chương trình tính tổng của n số có thời gian thực hiện là T(n) = cn trong đó c là một hằng số. Thời gian thực hiện chương trình là một hàm không âm, tức là T(n)  0  n  0. 11/16/202020Ðơn vị đo thời gian thực hiệnÐơn vị của T(n) không phải là đơn vị đo thời gian bình thường như giờ, phút giây... mà thường được xác định bởi số các lệnh được thực hiện trong một máy tính lý tưởng.Ví dụ: Khi ta nói thời gian thực hiện của một chương trình là T(n) = Cn thì có nghĩa là chương trình ấy cần Cn chỉ thị thực thi. 11/16/202021Thời gian thực hiện trong trường hợp xấu nhất Nói chung thì thời gian thực hiện chương trình không chỉ phụ thuộc vào kích thước mà còn phụ thuộc vào tính chất của dữ liệu vào. Vì vậy thường ta coi T(n) là thời gian thực hiện chương trình trong trường hợp xấu nhất trên dữ liệu vào có kích thước n, tức là: T(n) là thời gian lớn nhất để thực hiện chương trình đối với mọi dữ liệu vào có cùng kích thước n. 11/16/202022Tỷ suất tăng (1)Ta nói rằng hàm không âm T(n) có tỷ suất tăng (growth rate) f(n) nếu tồn tại các hằng số C và n0 sao cho T(n) ≤ Cf(n) với mọi n ≥ n0. Ta có thể chứng minh được rằng “Cho một hàm không âm T(n) bất kỳ, ta luôn tìm được tỷ suất tăng f(n) của nó”.11/16/202023Tỷ suất tăng (2)Ví dụ 1: Giả sử T(0) = 1, T(1) = 4 và tổng quát T(n) = (n+1)2. Ðặt N0 = 1 và C = 4 thì với mọi n ≥1 chúng ta dễ dàng chứng minh được rằng T(n) = (n+1)2 ≤ 4n2 với mọi n ≥ 1, tức là tỷ suất tăng của T(n) là n2.Ví dụ 2: Tỷ suất tăng của hàm T(n) = 3n3 + 2n2 là n3. Thực vậy, cho N0 = 0 và C = 5 ta dễ dàng chứng minh rằng với mọi n ≥ 0 thì 3n3 + 2n2 ≤ 5n3 11/16/202024Khái niệm độ phức tạp của giải thuật (1)Giả sử ta có hai giải thuật P1 và P2 với thời gian thực hiện tương ứng là T1(n) = 100n2 (với tỷ suất tăng là n2) và T2(n) = 5n3 (với tỷ suất tăng là n3). Khi n>20 thì T1 =i+1;j--)/*3*/ if (a[j].key a[j] cũng tốn O(1) thời gian, do đó lệnh {3} tốn O(1) thời gian.Vòng lặp {2} thực hiện (n-i) lần, mỗi lần O(1) do đó vòng lặp {2} tốn O((n-i).1) = O(n-i).Vòng lặp {1} có i chạy từ 1 đến n-1 nên thời gian thực hiện của vòng lặp {1} và cũng là độ phức tạp của giải thuật là 11/16/202038Tìm kiếm tuần tự Hàm tìm kiếm Search nhận vào một mảng a có n số nguyên và một số nguyên x, hàm sẽ trả về giá trị logic TRUE nếu tồn tại một phần tử a[i] = x, ngược lại hàm trả về FALSE.Giải thuật tìm kiếm tuần tự là lần lượt so sánh x với các phần tử của mảng a, bắt đầu từ a[1], nếu tồn tại a[i] = x thì dừng và trả về TRUE, ngược lại nếu tất cả các phần tử của a đều khác X thì trả về FALSE.11/16/202039Tìm kiếm tuần tự (tt)FUNCTION Search(a:ARRAY[1..n] OF Integer; x:Integer): Boolean; VAR i:Integer; Found:Boolean;BEGIN{1} i:=1;{2} Found:=FALSE;{3} WHILE(i<=n) AND (not Found) DO{4} IF A[i]=X THEN Found := TRUE ELSE I := i+1;{5} Search := Found;END;11/16/202040Tính độ phức tạp của hàm tìm kiếm tuần tựTa thấy các lệnh {1}, {2}, {3} và {5} nối tiếp nhau, do đó độ phức tạp của hàm Search chính là độ phức tạp lớn nhất trong 4 lệnh này. Dễ dàng thấy rằng ba lệnh {1}, {2} và {5} đều có độ phức tạp O(1) do đó độ phức tạp của hàm Search chính là độ phức tạp của lệnh {3}. Lồng trong lệnh {3} là lệnh {4}. Lệnh {4} có độ phức tạp O(1).Lệnh {3} là một vòng lặp không xác định, nên ta không biết nó sẽ lặp bao nhiêu lần, nhưng trong trường hợp xấu nhất (tất cả các phần tử của mảng a đều khác x, ta phải xét hết tất cả các a[i], i có các giá trị từ 1 đến n) thì vòng lặp {3} thực hiện n lần, do đó lệnh {3} tốn O(n). Vậy ta có T(n) = O(n). 11/16/202041Vấn đề lựa chọn thuật toán để cài đặt.Có 2 tiêu chuẩn quan trọng để lựa chọn một thuật toán:Đơn giản: dễ hiểu, dễ cài đặt và dễ ghi chép ? Hiệu quả: sử dụng các tài nguyên hiệu quả ? Tùy đặc tính của bài toán. 11/16/202042Bài tập11/16/202043