Bài giảng Phân tích và Thiết kế giải thuật nâng cao: Phần 1 - PGS.TS. Trần Cao Đệ

Bài giảng Phân tích và Thiết kế giải thuật nâng cao: Phần 1 trình bày các nội dung vềKT phân tích và thiết kế giải thuật,kỹ thuật thiết kế giải thuật. Tham khảo nội dung bài giảng để nắm bắt nội dung chi tiết.
Nội dung trích xuất từ tài liệu:
Bài giảng Phân tích và Thiết kế giải thuật nâng cao: Phần 1 - PGS.TS. Trần Cao Đệ Phân tích & Thiết kế Giải thuật nâng cao Advanced Algorithm Analysis and Design Bài giảng cho Thạc sĩ Ngành HTTT PGS. TS. TRẦN CAO ĐỆ Đại Học Cần Thơ1 2014 Phần 1: KT phân tích và thiết kế giải thuật PGS. TS. TRẦN CAO ĐỆ Đại Học Cần Thơ 20142 Chương 1: KỸ THUẬT PHÂN TÍCH GIẢI THUẬT PGS. TS. TRẦN CAO ĐỆ Đại Học Cần Thơ 20143 Thuật toán  Giải thuật / Thuật toán (algorithm) – Xuất phát từ nhà toán học Arập Al-Khowarizmi (khoảng năm 825). – Giải thuật 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 ... để cho ta lời giải của bài toán.  Ví dụ thuật toán Euclid . – Input: m, n nguyên dương – Output: g (ước chung lớn nhất của m và n) – Thuật toán : – Bước 1: Tìm r, phần dư của m cho n – Bước 2:  Nếu r = 0, thì g:=n và dừng lại.  Ngược lại (r 0) ,thì m:=n; n:=r và quay lại bước 1.4 Tính chất của thuật toán  Input: Mỗi thuật toán đều có một tập các giá trị đầu vào (có thể rỗng)  Output: Mỗi thuật toán có một tập dữ liệu ra đầu ra (output), tương ứng với input.  Tính xác định: các bước của thuật toán phải xác định (các thao tác phải rõ ràng, không gây nên sự nhập nhằng).  Tính chính xác: Thuật toán phải tạo ra các giá trị đầu ra chính xác tương ứng với giá trị đầu vào. Trong cùng một điều kiện hai bộ xử lý cùng thực hiện một thuật toán phải cho cùng một kết quả như nhau.  Tính hữu hạn: Với mọi bộ dữ liệu vào (hợp lệ), thuật toán phải dừng lại sau một số hữu hạn bước thực hiện.  Tính khả thi: Các phép toán có mặt trong thuật toán phải đủ đơn giản, có thể thực hiện được trong một lượng thời gian hữu hạn (có thể thực hiện bởi con người với giấy, bút trong một khoảng thời gian hữu hạn).  Tính tổng quát: phải áp dụng được cho một lớp bài toán.5 Vấn đề giải được & không giải được  Một bài toán: – Có một hoặc nhiều thuật toán giải.  Giải được  Lựa chọn thuật toá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).  Vd: – KHÔNG CÓ Thuật toán chắc thắng cho người thứ hai của cờ ca rô. – KHÔNG CÓ Thuật toán xem một máy Turing có dừng lại sau n bước hay không.6 Vấn đề chứng minh thuật toán  Tiếp cận khoa học – Tính đúng đắn của thuật toán  Thuật toán đúng đắn, chính xác  Thuật toán dừng – So sánh thuật toán: phân tích độ phức tạp thời gian.  Tiếp cận thực hành – Thuật toán đơn giản, dễ hiểu, dễ cài đặt (dễ viết chương trình) – Thuật toán sử dụng tiết kiệm nhất các nguồn tài nguyên của máy tính, và đặc biệt chạy nhanh nhất có thể được.7 Thời gian thực hiện chương trình  Tiếp cận 1: tính số giây,  Tiếp cận 2: theo số phép phút, giờ, ngày cần thiết để toán cơ bản mà chương chạy chương trình trình phải thực hiện – Không chính xác: – Phép toán cơ bản  Phụ thuộc tốc độ máy  Số phép +,-,*,/,=;  Phụ thuộc vào tập dữ liệu  Số chỉ thị cơ bản của máy vào: có input chạy nhanh, tính) có input chạy chậm – Độc lập tốc độ máy – Không khả thi – Vẫn phụ thuộc vào đặc tính  Chỉ thực hiện được trên của input một số input  Trường hợp xấu nhất  Không chỉ ra được sự biến  Trường hợp tốt nhất thiên của thời gian theo độ dài input  Trường hợp ngẫu nhiên8 Độ phức tạp thời gian của giải thuật  Độ phức tạp thời gian của giải  Kí hiệu O: tiệm cận trên thuật là một hàm theo kích O(g(n)) = {f(n)/ c,n0>0: thước của input, T(n). n>n0, 0 ≤ f(n) ≤ cg(n) }  So sánh độ phức tạp thời gian: so sánh theo tỷ suất tăng của Ta viết: f(n)= O(g(n)) thay cho hàm thời gian. f(n) O(g(n))  Kí hiệu : tiệm cận xấp xỉ  Kí hiệu : tiệm cận dưới ...