"Bài giảng Mạng và hệ thống thông tin – Chương 1: Mở đầu về thuật toán và độ phức tạp" thuật toán và độ phức tạp; đánh giá độ phức tạp thuật toán như thế nào; dùng o(f(n)) để đánh giá độ phức tạp của thuật toán; các quy tắc để đánh giá độ phức tạp thuật toán; các thuật toán cơ bản và độ phức tạp . | Chương 1 Mở đầu về thuật toán và độ phức tạp Nguyễn Văn Hạnh Bộ môn Mạng và hệ thống thông tin Email nvhanh@ Webpage http nvhanh Nội dung 1. Thuật toán và độ phức tạp 2. Đánh giá độ phức tạp thuật toán như thế nào 3. Dùng O f n để đánh giá độ phức tạp của thuật toán 4. Các quy tắc để đánh giá độ phức tạp thuật toán 5. Các thuật toán cơ bản và độ phức tạp Định nghĩa thuật toán 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 để cho ta lời giải của bài toán. Ví dụ Thuật toán Euclid Tìm UCLN của hai số nguyên dương. 1. Input m n là 2 số nguyên dương 2. Output g UCLN của m và n 3. Phương pháp Bước 1 Tìm r phân dư của phép chia m cho n. Bước 2 Nếu r 0 thì g n gán giá trị của n cho g và dừng lại. Ngược lại r 0 thì m n n r và quay lại bước 1. Các yêu cầu về thuật toán 1. Input là các giá trị cần đưa vào khi thuật toán bắt đầu làm việc. Ví dụ trong thuật toán Euclid input là 2 số nguyên dương m n . 2. Output là các giá trị có quan hệ hoàn toàn xác định với các dữ liệu input và là kết quả của sự thực hiện thuật toán. Ví dụ trong thuật toán Euclid output là UCLN g . 3. Tính xác định Ở mỗi bước các thao tác phải rõ ràng không gây nên sự nhập nhằng. Thuật toán cần được mô tả trong các ngôn ngữ lập trình các mệnh đề được tạo theo các quy tắc cú pháp nghiêm ngặt và chỉ có một nghĩa duy nhất. 4. Tính khả thi các phép toán có thể được thực hiện trực tiếp. 5. Tính dừng thuật toán phải dừng sau một số hữu hạn bước thực hiện. Vấn đề giải được và không giải được 1. Vấn đề giải được là vấn đề có thuật toán giải. Ví dụ tìm nghiệm của hệ phương trình tuyến tính là vấn đề giải được. 2. Vấn đề không giải được là vấn đề không tồn tại thuật toán giải. Ví dụ thuật toán chắc thắng cho người thứ 2 của cờ ca rô thuật toán xác định xem một máy Turing có dừng lại sau n bước hay không. Các vấn đề liên quan đến thuật toán 1. Thiết kế thuật toán một số kỹ thuật thiết kế thuật toán Phương pháp chia để trị .
