Bài giảng Cấu trúc dữ liệu và thuật toán: Chương 2

Bài giảng Cấu trúc dữ liệu và thuật toán: Chương 2 Thuật toán đệ quy với các nội dung chính như: Khái niệm đệ quy, thuật toán đệ quy, phân tích thuật toán đệ qui, chứng minh tính đúng đắn của thuật toán đệ qui
Nội dung trích xuất từ tài liệu:
Bài giảng Cấu trúc dữ liệu và thuật toán: Chương 2Chương 2: Thuật toán đệ quyTrịnh Anh Phúc, Nguyễn Đức Nghĩa1 Bộ1môn Khoa Học Máy Tính, Viện CNTT & TT,Trường Đại Học Bách Khoa Hà Nội.Ngày 14 tháng 7 năm 2015Trịnh Anh Phúc ( Bộ môn Khoa Học Máy Tính, Viện CNTT & TT, Trường thuậtCấu trúc dữ liệu và giải Đại Học Bách Khoa Hà Nội. ) 7 năm 2015Ngày 14 tháng1 / 67Giới thiệu1Khái niệm đệ quyHàm đệ quiTập hợp được xác định đệ qui2Thuật toán đệ qui3Một số ví dụ minh họa4Phân tích thuật toán đệ qui5Chứng minh tính đúng đắn của thuật toán đệ qui6Thuật toán quay luiBài toán xếp hậuBài toán mã tuầnTrịnh Anh Phúc ( Bộ môn Khoa Học Máy Tính, Viện CNTT & TT, Trường thuậtCấu trúc dữ liệu và giải Đại Học Bách Khoa Hà Nội. ) 7 năm 2015Ngày 14 tháng2 / 67Khái niệm đệ quyThuật toán đệ quiKhái niệm đệ quiTrong thực tế chúng ta thường gặp những đối tượng đệ quy bao gồmchính nó hoặc được định nghĩa bởi chính nó. Ta nói các đối tượng đó đượcxác định một cách đệ quiĐiểm quân sốCác hàm được định nghĩa đệ quiTập hợp được định nghĩa đệ quiĐịnh nghĩa đệ qui về câyFractal ....Trịnh Anh Phúc ( Bộ môn Khoa Học Máy Tính, Viện CNTT & TT, Trường thuậtCấu trúc dữ liệu và giải Đại Học Bách Khoa Hà Nội. ) 7 năm 2015Ngày 14 tháng3 / 67Khái niệm đệ quyHàm đệ quiHàm đệ qui (resursive functions)Định nghĩaCác hàm đệ qui được xác định bởi số nguyên không âm n theo sơ đồBước cơ sở (Basic step) : Xác định giá trị hàm tại thời điểm n = 0hay f (0)Bước đệ qui (Recursive step) : Cho giá trị của hàm f (k) tại k ≤ nđưa ra qui tắc tính giá trị của f (n + 1).Trịnh Anh Phúc ( Bộ môn Khoa Học Máy Tính, Viện CNTT & TT, Trường thuậtCấu trúc dữ liệu và giải Đại Học Bách Khoa Hà Nội. ) 7 năm 2015Ngày 14 tháng4 / 67Khái niệm đệ quyHàm đệ quiHàm đệ qui (resursive functions)VD1 :f (0) = 3 n = 0f (n + 1) = 2f (n) + 3 n > 0VD2 :f (0) = 1f (n + 1) = f (n) × (n + 1)VD3 : Định nghĩa đệ qui tổng sn =ni=1 ais 1 = a1sn = sn−1 + anTrịnh Anh Phúc ( Bộ môn Khoa Học Máy Tính, Viện CNTT & TT, Trường thuậtCấu trúc dữ liệu và giải Đại Học Bách Khoa Hà Nội. ) 7 năm 2015Ngày 14 tháng5 / 67