Thuật Toán và Thuật Giải

Thuật Toán và Thuật Giải– Khoa Toán Tin ĐHKHTN

Nội Dung

• THUẬT TOÁN

• CÁC PHƯƠNG PHÁP BIỂU DIỄN THUẬT TOÁN

• ĐỘ PHỨC TẠP CỦA THUẬT TOÁN

• PHÂN LOẠI VẤN ĐỀ

• THUẬT GIẢI

Thuật Toán
• Một thuật toán (hay giải thuật) là một thủ tục để giải quyết một bài toán hay một vấn đề, bằng cách thực thi một dãy hữu hạn thao tác.
• Thuật toán có thể thực hiện các công việc như tính toán, xử lý dữ liệu, suy luận logic tự động…
• Ví dụ: Tính ước số chung lớn nhất của 2 số nguyên.

Đặc trưng của thuật toán
• Tính chính xác: Các bước thực thi phải được phát biểu chính xác, chặt chẽ.
• Tính duy nhất: Kết quả của mỗi bước được định nghĩa một cách duy nhất và chỉ phụ thuộc vào nhập liệu và kết quả của các bước trước đó.
• Tính hữu hạn: Thuật toán ngừng sau một khi một số hữu hạn các chỉ thị lệnh được thực hiện .
• Nhập liệu: – thuật toán nhận nhập liệu (có thể trống).

• Nhập liệu: – thuật toán nhận nhập liệu (có thể trống).
• Xuất liệu – thuật toán tạo ra xuất liệu.
• Tính tổng quát – thuật toán có thể được vận dụng cho một tập hợp nhập liệu.

Các phương pháp biểu diễn thuật toán
• Bằng ngôn ngữ tự nhiên.
• Bằng lưu đồ (flowchart).
• Bằng mã giả (pseudo code).

• Bằng ngôn ngữ tự nhiên.
– Dùng ngôn ngữ thường ngày để liệt kê các bước của thuật toán.
– Dài dòng, có thể nhập nhằng khó hiểu
– Không thể hiện rõ cấu trúc của thuật toán
– Không có một quy tắc cố định.
– Có thể viết thụt lùi vào bên phải để phân cấp cho dễ đọc.

• Bằng lưu đồ (flowchart)
– Xử dụng các ký hiệu đồ hoạ có ý nghĩa để biểu diễn các thành phần của thuật toán.
– Dễ đọc, dễ hiểu.
– Thấy được quá trình xử lý, sự phân cấp của thuật toán. Nhờ đó thấy được cấu trúc của thuật toán.

Biểu diễn thuật toán bằng lưu đồ

• Chọn lựa theo một điều kiện nào đó:
– Biểu diễn bằng một hình thoi, bên trong chứa biểu thức điều kiện.
– Ví dụ: thao tác “nếu X > Y thì thực hiện thao tác in X, ngược lại thực hiện thao tác in Y” là thao tác chọn lựa
• Thao tác chọn lựa: có thể có hai hướng đi
– một hướng ứng với điều kiện thỏa
– một hướng ứng với điều kiện không thỏa.
– 2 cung có nhãn
• Đ/Đúng,Y/Yes
• S/Sai,N/No
• Xử lý, hành động:
– Biểu diễn bằng một hình chữ nhật, bên trong chứa nội dung xử lý.

– Đường đi – route
– Biểu diễn bằng cung có hướng
• nối giữa 2 thao tác: thực hiện lần lượt

– Biểu diễn bằng hình ovan
– Điểm khởi đầu
• chỉ có cung đi ra
• bên trong ovan ghi chữ: bắt đầu/start/begin
– Điểm kết thúc
• Chỉ có cung đi vào
• bên trong ovan ghi chữ: kết thúc/end
• Mỗi lưu đồ chỉ có 1 điểm bắt đầu và 1 điểm kết thúc.

• Xử lý, hành động:– Biểu diễn bằng một hình chữ nhật, bên trong chứa nội dung xử lý.• Quá trình thực hiện các thao tác:– Đường đi – route– Biểu diễn bằng cung có hướng• nối giữa 2 thao tác: thực hiện lần lượt• Ðiểm cuối (terminator)– Biểu diễn bằng hình ovan– Điểm khởi đầu• chỉ có cung đi ra• bên trong ovan ghi chữ: bắt đầu/start/begin– Điểm kết thúc• Chỉ có cung đi vào• bên trong ovan ghi chữ: kết thúc/end• Mỗi lưu đồ chỉ có 1 điểm bắt đầu và 1 điểm kết thúc.

• Thao tác chọn lựa: có thể có hai hướng đi– một hướng ứng với điều kiện thỏa– một hướng ứng với điều kiện không thỏa.– 2 cung có nhãn• Đ/Đúng,Y/Yes• S/Sai,N/No

– Nối các phần khác nhau của một lưu đồ
– Nối sang trang
– Sử dụng với lưu đồ phức tạp
• Giảm độ rắc rối
• Đặt ký hiệu liên hệ giữa các điểm nối

Ví dụ: Thuật toán tính USCLN của 2 số

Độ phức tạp thuật toán

• Độ phức tạp của thuật toán là hàm đánh giá tính hiệu quả của một thuật toán.
• Để đánh giá hiệu quả của một thuật toán, có thể xét số các phép tính phải thực hiện khi thực hiện thuật toán này.
• Thông thường số các phép tính được thực hiện phụ thuộc vào cỡ của bài toán, tức là độ lớn của đầu vào.

• Độ phức tạp của thuật toán là hàm đánh giá tính hiệu quả của một thuật toán.• Để đánh giá hiệu quả của một thuật toán, có thể xét số các phép tính phải thực hiện khi thực hiện thuật toán này.• Thông thường số các phép tính được thực hiện phụ thuộc vào cỡ của bài toán, tức là độ lớn của đầu vào.

• Để ước lượng độ phức tạp của một thuật toán ta thường dùng khái niệm bậc O-lớn và bậc Θ (bậc Theta).

• Chọn lựa theo một điều kiện nào đó:– Biểu diễn bằng một hình thoi, bên trong chứa biểu thức điều kiện.– Ví dụ: thao tác “nếu X > Y thì thực hiện thao tác in X, ngược lại thực hiện thao tác in Y” là thao tác chọn lựa• Điểm nối (connector)– Nối các phần khác nhau của một lưu đồ– Nối sang trang– Sử dụng với lưu đồ phức tạp• Giảm độ rắc rối• Đặt ký hiệu liên hệ giữa các điểm nối• Độ phức tạp thuật toán là một hàm phụ thuộc đầu vào. Tuy nhiên trong những ứng dụng thực tiễn, chúng ta không cần biết chính xác hàm này mà chỉ cần biết một ước lượng đủ tốt của chúng.• Để ước lượng độ phức tạp của một thuật toán ta thường dùng khái niệm bậc O-lớn và bậc Θ (bậc Theta).

• Gọi n là kích thước bài toán, R(n) là tổng tài nguyên cần dung, giả sử tìm được hàm g(n) và có hằng số C sao cho: R(n) ≤ C.g(n)
Thì ta nói thuật toán có độ phức tạp O(g(n)).

O(1): Độ phức tạp hằng số.
O(n): Độ phức tạp tuyến tính
O(P(n)): Độ phức tạp đa thức.
O(logn): Độ phức tạp logarit.
O(2 n ): Độ phức tạp hàm mũ.

• Gọi n là kích thước bài toán, R(n) là tổng tài nguyên cần dung, giả sử tìm được hàm h(n) và các hằng số C 1 , c 2 sao cho: C 1 .h(n) ≤ R(n) ≤ C 2 .h(n)
Thì ta nói thuật toán có độ phức tạp đúng bằng θ(h(n)).

Thuật giải

• Có nhiều bài toán cho đến nay vẫn chưa tìm ra một cách giải theo kiểu thuật toán và cũng không biết là có tồn tại thuật toán hay không.
• Có nhiều bài toán đã có thuật toán để giải nhưng không chấp nhận được vì thời gian giải theo thuật toán đó quá lớn hoặc các điều kiện cho thuật toán khó đáp ứng.

• Có những bài toán được giải theo những cách giải vi phạm thuật toán nhưng vẫn chấp nhận được.
• Tính đúng của thuật toán bây giờ không còn bắt buộc đối với một số cách giải bài toán, nhất là các cách giải gần đúng.

• Trong thực tiễn có nhiều trường hợp người ta chấp nhận các cách giải thường cho kết quả tốt nhưng ít phức tạp và hiệu quả.
• Khái niệm thuật toán được mở rộng như trên gọi là thuật giải.
• Thuật giải thường được dùng nhiều trong trí tuệ nhân tạo.

Tóm tắt

• Một thuật toán là một dãy hữu hạn các thao tác cần thực thi để đi đến lời giải cho một bài toán hay một vấn đề nào đó.
• Thuật toán phải có tính chính xác, tính duy nhất, tính hữu hạn, tính tổng quát.
• Ta có thể biểu diễn thuật toán bằng ngôn ngữ tự nhiên, bằng mã giả hoặc bằng lưu đồ.

• Độ phức tạp của thuật toán là một hàm theo kích thước của bài toán, nó cho biết tính hiệu quả khi thực hiện bài toán.
• Độ phức tạp của thuật toán được ký hiệu là O(h(n)) hoặc θ(h(n)).
• Thuật giải là khái niệm thuật toán được mở rộng để có thể đi đến lời giải chấp nhận được nhưng có độ phức tạp tốt hơn (nhiều) so với thuật toán (nếu tồn tại).

• Biểu diễn thuật toán tính ước số chung lớn nhất của số nguyên dương.
• Biểu diễn thuật toán giải phương trình bậc 2.
• Biểu diễn thuật toán tính giá trị lớn nhất của một dãy các số thực.
• Biểu diễn thuật toán tính căn bậc hai của một số thực A với sai số không quá epsilon.

Các ví dụ

• Viết thuật toán tìm tổng bình phương của một dãy. Xác định độ phức tạp của thuật toán.
• Viết thuật toán tìm giá trị của phần tử lớn nhất của một dãy các số thực. Xác định độ phức tạp của thuật toán.
• Viết thuật toán Euclide tìm ước số chung lớn nhất của 2 số nguyên.
• Viết thuật toán tính gần đúng giá trị của sin(x).