tailieunhanh - Bài giảng Phân tích thiết kế và đánh giá thuật toán: Phần 2 - Nguyễn Hữu Tuân

Bài giảng Phân tích thiết kế và đánh giá thuật toán có mục đích cung cấp các kiến thức cơ bản về thuật toán, kiến trúc dữ liệu, cung cấp các kiến thức về chiến lược xây dựng và đánh giá thuật toán, rèn luyện tư duy khoa học. Phần 2 của tài liệu gồm 4 chương cuối của bài giảng. | Bài giảng môn học Phân tích thiết kế và đánh giá giải thuật CHƯƠNG III ĐỆ QUI VÀ CHIẾN LƯỢC VÉT CẠN 1. Khái niệm đệ qui Đệ qui là một kỹ thuật được sử dụng trong các ngôn ngừ lập trình cao cấp như C C ngày nay hầu hết các ngôn ngừ lập trình đều hỗ trợ kỹ thuật này. về b ản chất đệ qU là c ách định nghĩa một đối tượng dựa trên chính nó hay cụ thể hon là trên các thể hiện cụ thể đon giản của nó. Ta có thể định nghĩa một bứ c tranh picture như thế này Một điểm ảnh pixel là một bứ c tranh N ếu p1 và p2 là hai b ứ c tranh thì việ c ghép p1 với p2 sẽ cho ta một b ứ c tranh mới. Trong toán học người ta hay sử dụng phưong pháp chứ ng minh qui nạp chính là một nguyên lý đệ qui. Trong lập trình ta định nghĩa một hàm đệ qui là một hàm mà trong thân hàm c ài đặt c ó lờ gọi tớ chính nó số lượng và vị trí không hạn chế . Ví dụ ta có thể định nghĩa hàm tính giai thừa factorial của một số nguyên như sau Gt 0 1. Gt n n Gt n-1 vớ mọi n 0. Giải thuật đệ qui là giải thuật dựa trên các quan hệ đệ qui và được cài đặt cụ thể b ằng các hàm đệ qui. 2. Chiến lược vét cạn Brute force Đây là chiến lược đon giản nhất nhưng cũng là không hiệu quả nhất. Chiến lược vét cạn đon giản thử tất cả c ác khả năng xem khả năng nào là nghiệm đúng của b ài to án cần giải quyết. Ví dụ thuật toán duyệt qua mảng để tìm phần tử có giá trị lớn nhất chính là áp dụng chiến lược vét c ạn. Ho ặc b ài to án kiểm tra và in ra tất cả c ác số nguyên tố c ó 4 chữ số ab c d sa a số số ượ ự ư sa for a 1 a 9 a for b 0 b 9 b for c 0 c 9 c for d 0 d 9 d if ktnguyento a 1000 b 100 c 10 d 10 a b 10 c d printf d d d d a b c d H m ye m a xem mộ số yê p ả l số yê ố ay ô . C p ụ lượ ộ l m ả m . về mặt lý thuyết chiến lược này có thể áp dụng cho mọi loại b ài toán nhưng có một hạn chế khiến nó không phải là chìa khóa vạn năng về mặt thự c tế d o cần phải thử tất cả c ác khả năng 34 Bài giảng môn học Phân tích thiết kế và đánh giá giải thuật nên số trường hợp cần phải thử của b ài to án thường lên tới c on số rất lớn và thường quá .

• Cơ sở dữ liệu
• Thiết kế thuật toán
• Đánh giá thuật toán
• Bài giảng Phân tích thuật toán Phần 2
• Chiến lược vét cạn
• Chiến lược chia để trị
• Cấu trúc dữ liệu
• Phân tích thiết kế thuật toán
• Phân tích thuật toán
• Bài giảng Phân tích thiết kế thuật toán
• Kỹ thuật thiết kế giải thuật
• Thiết kế giải thuật
• Phân tích thiết kế giải thuật
• Phương pháp thiết kế thuật toán
• Tối ưu thuật toán
• Đề thi Phân tích thiết kế thuật toán
• Câu hỏi Phân tích thiết kế thuật toán
• Ôn tập Phân tích thiết kế thuật toán
• Thuật toán tham lam
• Trình diễn thuật toán
• Đề thi học kỳ
• Thiết kế và đánh giá thuật toán
• Đề thi Thiết kế và đánh giá thuật toán
• Bài tập Thiết kế và đánh giá thuật toán
• Kỹ thuật phân tích thuật toán
• Đánh giá một giải thuật
• Đề thi Đánh giá thuật toán
• Bài giảng đánh giá thuật toán
• Bài giảng thiết kế thuật toán
• Bài toán sắp xếp
• Sắp xếp chèn
• Năng lực sáng tạo kĩ thuật của sinh viên
• Bài toán thiết kế kĩ thuật
• Dạy học kĩ thuật
• Đặc điểm bài toán thiết kế kĩ thuật
• Nguyên tắc xây dựng bài toán thiết kế kĩ thuật
• Tự động hóa tính toán thiết kế tàu
• Thiết kế tàu thủy
• Kỹ thuật thiết kế tàu
• Tính toán thiết kế tàu
• Thiết kế tối ưu tàu thủy
• Thiết kế chân vịt tàu thủy
• Giải thuật sắp xếp
• Chương trình sắp xếp
• Giải thuật lưu trữ ngoài
• Lập trình động
• Kỹ thuật thiết kế dưới lên
• Giáo trình Phương pháp thiết kế kỹ thuật
• Phương pháp thiết kế kỹ thuật
• Kỹ thuật xây dựng
• Bài toán thiết kế
• Xây dựng ý tưởng thiết kế
• Kế hoạch thiết kế kỹ thuật
• Bài giảng Phân tích thiết kế giải thuật
• Phương pháp thiết kế thuật giải
• Thuật toán chính xác
• Thuật toán gần đúng
• Bước thiết kế một thuật giải
• Chiến lược thiết kế thuật toán
• Thuật toán tiêu biểu
• Số Fibonacci thứ n đệ quy
• Fibonacci quy hoạch động
• Phân tích đệ quy
• Thuật toán đệ quy
• Phân tích toán học
• Bài toán trả tiền thừa
• Chiến lược tham ăn
• Chia để trị
• Bài tập Chia để trị
• Đánh giá độ phức tạp thuật toán
• Phân tích thiết kế thuật toán
• Kỹ thuật phân tích thiết kế giải thuật
• Phương pháp phân tích thuật toán
• Vai trò của phân tích thuật toán
• Quá trình phân tích thuật toán
• Thuật toán sắp xếp
• Phân tích thuật toán sắp xếp
• Thuật toán tìm kiếm
• Phân tích thuật toán tìm kiếm
• Bài giảng Thiết kế và đánh giá thuật toán
• Kỹ thuật chia để trị
• Kỹ thuật tham lam
• Kỹ thuật quy hoạch động
• Kỹ thuật quay lui
• Khái niệm tiệm cận
• Ký hiệu tiệm cận