tailieunhanh - Bài giảng Cấu trúc dữ liệu và giải thuật: Chương 2 - Ths. Phạm Thanh An (2018)

Bài giảng "Cấu trúc dữ liệu và giải thuật - Chương 2: Đệ quy và giải thuật đệ quy" cung cấp cho người học các kiến thức: Khái niệm đệ quy, giải thuật và chương trình đệ quy, thiết kế giải thuật đệ quy, ưu nhược điểm của đệ quy, một số dạng giải thuật đệ quy thường gặp,. . | Ths. Phạm Thanh An Bộ môn Khoa học máy tính- Khoa CNTT Trường Đại học Ngân hàng Chương 2 Đệ quy và giải thuật đệ quy Nội dung Khái niệm đệ quy Giải thuật và chương trình đệ quy Thiết kế giải thuật đệ quy Ưu nhược điểm của đệ quy Một số dạng giải thuật đệ quy thường gặp Giải thuật đệ qui quay lui (backtracking) Một số bài toán giải bằng giải thuật đệ quy điển hình Đệ quy và quy nạp toán học Mục tiêu Trang bị cho sinh viên các khái niệm và cách thiết kế giải thuật đệ qui, giải thuật đệ qui quay lui. Giới thiệu một số bài toán điển hình được giải bằng giải thuật đệ qui. Phân tích ưu và nhược điểm khi sử dụng giải thuật đệ qui Khái niệm về đệ qui Đệ quy: Đưa ra 1 định nghĩa có sử dụng chính khái niệm đang cần định nghĩa( quay về). Ví dụ Người = con của hai người khác. Trong toán học: Số tự nhiên: 0 là số tự nhiên, n là số tự nhiên nếu n- 1 là số tự nhiên Hàm n! Khái niệm về đệ Một đối tượng là đệ quy (recusive) nêu nó bao gồm chính nó như một bộ phận hoặc nó được định nghĩa dưới dạng chính nó. Đệ qui là một khái niệm tồn tại trong cuộc sống, trong toán học, lập trình Số tự nhiên: 0 là một số tự nhiên n là sô tự nhiên, nếu n–1 là số tự nhiên Hàm n! 0!=1 Nêu n>0 thì n!=n(n-1)! Giải thuật và hàm đệ quy Giải thuật đệ quy Nếu bài toán T được thực hiện bằng lời giải của bài toán T ’ có dạng giống T là lời giải đệ quy Giải thuật tương ứng với lời giải như vậy gọi là giải thuật đệ quy. Hàm đệ quy T’ có dạng giống T, nhưng tham số của T’ có kích thước nhỏ hơn Hàm đệ qui đệ quy : Một hàm được gọi là đệ quy, nếu trong quá trình thực hiện có phần gọi lại chính nó Hàm đệ qui là điều kiện cần và đủ để hiện thực hóa giải thuật đệ qui Thuật toán đệ quy được biểu diễn trong các ngôn ngữ lập trình bậc cao (chẳng hạn Pascal, C/C++) bởi các hàm đệ quy Có những vấn đề rất phức tạp, nhưng chúng ta có thể đưa ra thuật toán đệ quy rất đơn giản, sáng sủa và dễ hiểu Giải thuật đệ quy Ví dụ: Xét bài toán tìm một từ trong quyển từ điển: If (từ điển là một trang) tìm từ trong trang | Ths. Phạm Thanh An Bộ môn Khoa học máy tính- Khoa CNTT Trường Đại học Ngân hàng Chương 2 Đệ quy và giải thuật đệ quy Nội dung Khái niệm đệ quy Giải thuật và chương trình đệ quy Thiết kế giải thuật đệ quy Ưu nhược điểm của đệ quy Một số dạng giải thuật đệ quy thường gặp Giải thuật đệ qui quay lui (backtracking) Một số bài toán giải bằng giải thuật đệ quy điển hình Đệ quy và quy nạp toán học Mục tiêu Trang bị cho sinh viên các khái niệm và cách thiết kế giải thuật đệ qui, giải thuật đệ qui quay lui. Giới thiệu một số bài toán điển hình được giải bằng giải thuật đệ qui. Phân tích ưu và nhược điểm khi sử dụng giải thuật đệ qui Khái niệm về đệ qui Đệ quy: Đưa ra 1 định nghĩa có sử dụng chính khái niệm đang cần định nghĩa( quay về). Ví dụ Người = con của hai người khác. Trong toán học: Số tự nhiên: 0 là số tự nhiên, n là số tự nhiên nếu n- 1 là số tự nhiên Hàm n! Khái niệm về đệ Một đối tượng là đệ quy (recusive) nêu nó bao gồm chính nó như một bộ phận hoặc nó được định nghĩa .

• 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
• Giải thuật đệ quy
• Chương trình đệ quy
• Thiết kế giải thuật đệ quy
• 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