TAILIEUCHUNG - Bài giảng Cấu trúc dữ liệu và giải thuật: Bài 11 - Hoàng Thị Điệp

Bài giảng "Cấu trúc dữ liệu và giải thuật - Bài 11: Thiết kế thuật toán" cung cấp cho người học các kiến thức: Các chiến lược thiết kế thuật toán, thuật toán tiêu biểu, tìm dãy con tăng dài nhất, bài toán ba lô,. . | HK I, 2012-2013 Bài 11: Thiết kế thuật toán Giảng viên: Hoàng Thị Điệp Khoa Công nghệ Thông tin – Đại học Công Nghệ Các chiến lược thiết kế thuật toán • Chia-để-trị (Divide-and-conquer) • – Thực hiện từng bước một. Tại mỗi bước, chọn phương án được xem là tốt lúc đó. – Không phải tất cả các thuật toán tham ăn đều cho kết quả tối ưu toàn cục – Chia bài toán thành các bài toán kích thước nhỏ có thể giải quyết độc lập. Sau đó kết hợp nghiệm các bài toán kích thước nhỏ thành nghiệm bài toán gốc – Thuật toán đệ quy • Quy hoạch động (Dynamic programming) • – Giải bài toán lớn dựa vào kết quả bài toán con. Tránh lặp lại việc giải cùng một bài toán con bằng cách lưu nghiệm các bài toán con trong một bảng – Thuật toán lặp diepht@vnu Tham ăn (Greedy method) INT2203/w12 Các chiến lược khác – Quay lui – Thuật toán ngẫu nhiên 2 Thuật toán tiêu biểu – Tìm dãy con chung của hai dãy số (longest common subsequence) • Chia-để-trị – Tìm kiếm nhị phân (binary search) – Sắp xếp trộn (merge sort) – Sắp xếp nhanh (quick sort) • Tham ăn – Xây dựng mã Huffman (Huffman encoding) – Tìm cây bao trùm nhỏ nhất (minimum spanning tree) • Quy hoạch động – Tìm dãy con tăng dài nhất (longest increasing subsequence) – Bài toán ba lô (backpacker/knapsack) – Bài toán người bán hàng (traveling salesman) diepht@vnu INT2203/w12 3 1. Fibonacci(n) diepht@vnu INT2203/w12 4 Tìm số Fibonacci thứ n đệ quy • • Algorithm Fib(n) Input n Output số Fibonacci thứ n if n = 0 then return 0 else if n = 1 then return 1 else return Fib(n – 2) + Fib(n – 1) Fn= Fn-1+ Fn-2 F0 =0, F1 =1 – 0, 1, 1, 2, 3, 5, 8, 13, 21, 34 • Thủ tục tính đệ quy trực tiếp thực hiện chậm do tính lặp nhiều lần. F(6) = 8 F(5) F(4) F(4) F(3) F(2) F(1) diepht@vnu F(3) F(2) F(1) F(1) F(3) F(2) F(1) F(0) F(1) F(0) F(2) F(1) F(2) F(1) .

• Cơ sở dữ liệu
• Bài giảng Cấu trúc dữ liệu
• Cấu trúc dữ liệu
• Cấu trúc dữ liệu và giải thuật
• Thiết kế thuật toán
• Thuật toán tiêu biểu
• Bài toán ba lô
• 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
• Bài giảng Cấu trúc dữ liệu và giải thuật
• Cấu trúc dữ liệu cơ bản
• Kiểu dữ liệu trừu tượng
• 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
• Cơ sở dữ liệu
• Đánh giá thuật toán
• Thiết kế cấu trúc dữ liệu
• Đá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
• Kiểu dữ liệu cây
• Phân loại cây
• Bài giảng Maple
• Cấu trúc dữ liệu trong maple
• Cấu trúc dữ liệu dãy
• Cấu trúc dữ liệu tập hợp
• Cấu trúc dữ liệu mảng
• Cấu trúc dữ liệu bảng
• 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
• 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
• Cấu trúc dữ liệu cây AA
• Cây AA
• Biến đổi hiệu chỉnh cây AA
• Danh sách liên kết
• Thao tác duyệt cây
• Cấu trúc dữ liệu ngăn xếp
• Hàng đợi
• Biểu thức toán học
• Cây nhị phân
• Cấu trúc dữ liệu nâng cao
• Vị trí cấu trúc dữ liệu
• Áp dụng tin học
• Quan hệ giải thuật
• Cấu trúc dữ liệu tuyến tính
• Cách dùng con trỏ
• Cài đặt danh sách
• Các kiểu dữ liệu cơ bản
• Giải thuật tìm tuyến tính