TAILIEUCHUNG - Bài giảng Cấu trúc dữ liệu và giải thuật: Thuật toán đệ quy

Bài giảng Cấu trúc dữ liệu và giải thuật - Thuật toán đệ quy gồm có những nội dung chính sau đây: Định nghĩa đệ quy, thuật toán đệ quy, phân tích thuật toán đệ quy, đệ quy có nhớ, thuật toán quay lui (backtracking algorithm). . | REVIEW Xác định mối quan hệ giữa các cặp hàm f ĩì và g ĩì sau đây a n n2 5 3 n 1 g n 6n b f ji n2 3-ựn 1 g n n3 c n 2n2 5 n g n Nội dung Định nghĩa đệ quy Thuật toán đệ quy Phân tích thuật toán đệ quy Đệ quy có nhớ Thuật toán quay lui backtracking algorithm 1 10 2011 THUẬTTOÁN ĐÊ QUY Định nghĩa đệ quy Đôi tượng bao gồm chính nó hoặc được định nghĩa dưới dạng chính nó. VD. Định nghĩa một công thức hợp lệ của các biến số và các phép toán A X là công thức hợp lệ nếu X là biến hoặc số Nếu f g là công thức hợp lệ thì Ư 3 Ư-3 Ư 3 ừ 3 cũng là công thức hợp lệ Elena Filippova. Recursion. 2003 Acrylic on Canvas 160 cm X 160 cm 63 X 63 1 Hàm được định nghĩa đệ quy . 1 nếu n 0 n 1 f . X. Z n X n 1 nếu n 0 _ 1 nếu n 1 2 1 w pib n 1 Fib n 2 nếu n 2 Ío nếu n 0 1 nếu n 1 2P n 1 p n 2 nếu n 1 Thuật toán đệ quy Thuật toán có chứa lời gọi đệ quy đến chính nó với đầu vào kích thước nhỏ hơn. VD. Sắp xếp trộn - MergeSort_________________ MergeSort int A int start int end if start end int mid start end 2 MergeSort A start mid MergeSort A mid 1 end Merge A start mid end 1 10 2011 Định nghĩa đệ quy Mọi định nghĩa đệ quy đều gồm 2 phần Một trường hợp cơ sở nhỏ nhất có thể xử lý trực tiếp mà không cần đệ quy và Một phương thức tổng quát mà biến đổi một trường hợp cụ thể về các trường hợp nhỏ hơn. Do đó biến đổi các trường hợp cho đến khi về trường hợp cơ sở. 2 Thuật toán đệ quy Mô tả thời gian thực hiện của thuật toán đệ quy bằng công thức đệ quy VD. MergeSort có í 0 1 nếun l 2T 0 n nếu n 1 Bỏ qua Tin với các giá trị n nhỏ coi là hằng . Ta có thể viết lại T n là T ịì 2T 0 n 1 10 2011 Phân tích thuật toán đệ quy Giải công thức đệ quy để tìm 0 hoặc 0 bằng Phương pháp thay thế Phương pháp cây đệ quy Dùng định lý thợ Phương pháp thay thế Gồm 2 bước Đoán dạng của lời giải Sử dụng quy nạp toán học để tìm ra các hằng và chứng minh lời giải Xác định cận trên của công thức đệ quy T n 2T P 2J n Đoán T n O nlogn Cần chứng minh Tin cnìogn với hằng sốn 0 được chọn phù hợp

• Cơ sở dữ liệu
• Cấu trúc dữ liệu
• Thuật toán đệ quy
• Phân tích thuật toán đệ quy
• Đệ quy có nhớ
• Thuật toán quay lui
• Backtracking algorithm
• cấu trúc dữ liệu và giải thuât
• bài giảng cấu trúc dữ liệu và giải thuât
• tài liệu cấu trúc dữ liệu và giải thuât
• giáo trình cấu trúc dữ liệu và giải thuât
• bài tập cấu trúc dữ liệu và giải thuât
• Bài giảng Cấu trúc dữ liệu
• Cấu trúc dữ liệu và giải thuật
• Cấu trúc dữ liệu cây AVL
• Cấu trúc dữ liệu cây
• Thuật toán DSW
• Cây nhị phân tìm kiếm
• Cấu trúc dữ liệu cây đỏ đen
• Cấu trúc dữ liệu cho nút cây đỏ đen
• Phép biến đổi cây đỏ đen cân bằng
• giáo trình cấu trúc dữ liệu
• bài tập cấu trúc dữ liệu
• đề cương cấu trúc dữ liệu
• lập trình dữ liệu
• Vị trí cấu trúc dữ liệu
• Áp dụng tin học
• Cơ sở dữ liệu
• Quan hệ giải thuật
• Cấu trúc dữ liệu cơ bản
• Đánh giá cấu trúc dữ liệu
• Định nghĩa kiểu dữ liệu
• Kiểu dữ liệu có cấu trúc
• Đánh giá thuật toán
• Thiết kế cấu trúc dữ liệu
• Bài giảng Cấu trúc dữ liệu và giải thuật
• Kiểu dữ liệu trừu tượng
• Kiểu dữ liệu cây
• Phân loại cây
• Cấu trúc dữ liệu giải thuật
• Bài giảng Cấu trúc dữ liệu giải thuật
• Ngôn ngữ lập trình
• Cấu trúc chương trình
• Cấu trúc điều khiển
• Tài liệu Cấu trúc dữ liệu
• Cấu trúc dữ liệu căn bản
• Khái niệm cấu trúc dữ liệu
• Độ phức tạp thuật toán
• tiếp cận lập trình
• thuật toán
• thuật toán trong cấu trúc dữ liệu
• cấu trúc dữ liệu động
• kỹ thuật sắp xếp