TAILIEUCHUNG - Bài giảng môn học Phân tích và thiết kế thuật toán - Đại Học Phương Đông

Bài giảng trình bày nội dung về độ phức tạp thuật toán, đánh giá thuật toán, phương pháp tham lam, phương pháp chia để trị, quy hoạch động và thuật toán đồ thị cơ bản. Hi vọng tài liệu này sẽ giúp ích cho các bạn trong việc học môn "Phân tích và thiết kế thuật toán". . | Bài Giảng Môn Học Phân Tích Và Thiết Kế Thuật Toán Biên tập bởi: Đại Học Phương Đông Bài Giảng Môn Học Phân Tích Và Thiết Kế Thuật Toán Biên tập bởi: Đại Học Phương Đông Các tác giả: Đại Học Phương Đông Phiên bản trực tuyến: MỤC LỤC 1. Độ phức tạp tính toán và tính hiệu quả của thuật toán 2. Mở đầu về thiết kế, đánh giá thuật toán và kiến thức bổ trợ 3. Phương pháp tham lam 4. Phương pháp “chia để trị” 5. Quy hoạch động 6. Thuật toán đồ thị cơ bản Tham gia đóng góp 1/129 Độ phức tạp tính toán và tính hiệu quả của thuật toán Sự cần thiết phải phân tích thuật toán Trong khi giải một bài toán chúng ta có thể có một số giải thuật khác nhau, vấn đề là cần phải đánh giá các giải thuật đó để lựa chọn một giải thuật tốt (nhất). Thông thường thì ta sẽ căn cứ vào các tiêu chuẩn sau: 1. Giải thuật đúng đắn. 2. Giải thuật đơn giản. 3. Giải thuật thực hiện nhanh. Với yêu cầu (1), để kiểm tra tính đúng đắn của giải thuật chúng ta có thể cài đặt giải thuật đó và cho thực hiện trên máy với một số bộ dữ liệu mẫu rồi lấy kết quả thu được so sánh với kết quả đã biết. Thực ra thì cách làm này không chắc chắn bởi vì có thể giải thuật đúng với tất cả các bộ dữ liệu chúng ta đã thử nhưng lại sai với một bộ dữ liệu nào đó. Vả lại cách làm này chỉ phát hiện ra giải thuật sai chứ chưa chứng minh được là nó đúng. Tính đúng đắn của giải thuật cần phải được chứng minh bằng toán học. Tất nhiên điều này không đơn giản và do vậy chúng ta sẽ không đề cập đến ở đây. Khi chúng ta viết một chương trình để sử dụng một vài lần thì y ê u cầu (2) là quan trọng nhất. Chúng ta cần một giải thuật dễ viết chương trình để nhanh chóng có được kết quả, thời gian thực hiện chương trình không được đề cao vì dù sao thì chương trình đó cũng chỉ sử dụng một vài lần mà thôi. Tuy nhiên khi một chương trình được sử dụng nhiều lần thì thì yêu cầu tiết kiệm thời gian thực hiện chương trình lại rất quan trọng đặc biệt đối với những chương trình mà khi thực hiện cần dữ liệu nhập lớn do

• Cơ sở dữ liệu
• Phân tích và thiết kế thuật toán
• Độ phức tạp thuật toán
• Đánh giá thuật toán
• Phương pháp tham lam
• Phương pháp chia để trị
• Quy hoạch động
• Thuật toán đồ thị cơ bản
• Phân tích thiết kế 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
• Phân tích thiết kế giải thuật
• Thiết kế thuật toán
• Phương pháp thiết kế thuật toán
• Tối ưu thuật toán
• Bài giảng Phân tích và thiết kế thuật toán
• Phân tích thuật toán
• Phân tích Top down
• Bài giảng đánh giá thuật toán
• Bài giảng thiết kế thuật toán
• Phân tích đệ quy
• Thuật toán đệ quy
• Phân tích toán học
• Bài toán sắp xếp
• Sắp xếp chèn
• Bài giảng Phân tích thuật toán
• Tính chất cơ bản của thuật toán
• Độ phức tạp của thuật toán
• Ước lượng tiệm cận
• Ngôn ngữ lập trình
• Tự học lập trình
• Lập trình máy tính
• Tìm kiếm tuần tự
• Xem xét phân bố khóa
• Tìm kiếm nhị phân
• Kỹ thuật Greedy
• Bài toán tối ưu tổ hợp
• Bài toán trả tiền của ATM
• Phương pháp khử đệ quy
• Phương trình đệ quy
• Thuật toán hoán vị
• Số nghịch thế
• Bảng nghịch thế
• Đánh giá bằng công cụ toán học
• Công cụ toán học sơ cấp
• Đánh giá bằng thực nghiệm
• Bài toán quy hoạch động
• Bài toán con
• Phương pháp giải bài toán trên máy tính
• Phương pháp trực tiếp
• Phương pháp gián tiếp
• Tìm kiếm cục bộ
• Bài toán cây phủ tối thiểu
• Bài toán người giao hàng
• Chuỗi lũy thừa
• Dùng hàm sinh giải hệ thức truy hồi
• Hàm sinh của dãy xác suất
• Chia để trị
• Bài toán cơ sở
• Nhân số nguyên lớn
• Bài giảng Phân tích thiết kế
• Phân tích thiết kế dữ liệu
• Thiết kế giải thuật
• Định nghĩa B Tree
• Các phép toán trên B Tree
• Giải thuật nâng cao
• Kỹ thuật phân tích giải thuật
• Kỹ thuật thiết kế giải thuật
• Hệ thống thông tin
• Công nghệ thông tin
• Bài giảng Phân tích thuật toán Phần 1
• Khái niệm thuật toán
• Cấu trúc dữ liệu
• Sắp xếp dữ liệu
• Đề thi học kỳ
• Lược đồ giản thuật
• Ý tưởng chia để trị
• Bài toán tìm kiếm nhị phân
• Bài toán tô màu đồ thị
• Biểu diễn đồ thị
• Tổng quan đồ thị
• Bài toán đồ thị
• 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ị