Phân tích thiết kế thuật toán
Giới ThiệuThông tin khung chương trìnhĐào Tạo Chương trình đào tạo và huấn luyện cử nhân Chương trình huấn luyện và đào tạo cao họcNghiên CứuTuyển SinhVăn bản-Thủ tụcMạng lưới sinh viên
1.TÊN HỌC PHẦN:
Tiếng Việt:Phân tích và thi công thuật toán
Tiếng Anh:Design & Analysis of Algorithms
Mã học phần:CNTT1118 Số tín chỉ:03
2.BỘ MÔN PHỤ TRÁCH GIẢNG DẠY:
Bộ môn công nghệ thông tin
3.ĐIỀU KIỆN HỌC TRƯỚC:
Sinh viên cần được học trước các học phần tiếp sau đây để tiếp nhận được tốt hơn.
Bạn đang xem: Phân tích thiết kế thuật toán
-Nhập môn technology thông tin.
-Cấu trúc dữ liệu và giải thuật.
-Cơ sở lập trình
4.MÔ TẢ HỌC PHẦN:
Phân tích và xây dựng thuật toán là học tập phần nên chuyên ngành technology thông tin. Học phần này ra mắt các kỹ thuật ship hàng cho thiết kế và phân tích tác dụng các thuật toán, nhấn mạnh vấn đề vào những phương pháp có ích trong thực tế. Thông qua việc giám sát và đo lường độ tinh vi và đi sâu phân tích những phạm vi khác biệt của những lớp bài toán cơ bản sẽ giúp tín đồ học hiểu rõ về hoạt động này.
* nội dung học phần bao gồm:
§Tổng quan những khái niệm về thuật toán, tiệm cận, độ phức hợp thuật toán của những bài toán cơ phiên bản và các lớp bài toán khó.
§Trình bày với phân tích các kỹ thuật sắp đến xếp, cây search kiếm, vun đống, hàm băm, phân chia để trị, quy hoạch động, thuật toán tham lam, các thuật toán thứ thị, và lối đi ngắn nhất…
§Một số chủ thể nâng cao.
§Tính toán độ phức hợp thuật toán cho những bài toán cơ phiên bản và những lớp vấn đề khó.
§Các thuật toán Heuristic cùng thuật toán xấp xỉ
§Một vài hướng nghiên cứu về độ tinh vi thuật toán.
5.MỤC TIÊU HỌC PHẦN:
ØVề loài kiến thức:
Mục tiêu của học phần này là mày mò làm thay nào để cách tân và phát triển các thuật toán công dụng cho các nhiệm vụ đo lường và tính toán cơ bản và trình bày về tính đúng chuẩn của chúng.
Sinh viên sau khi học xong học phần này sẽ:
oHiểu được các phát minh cơ phiên bản về những thuật toán.
Xem thêm: Ghép Ảnh Đẹp Lung Linh Online, Ghép Ảnh Tình Yêu Khung Vải Thêu Đẹp Lung Linh
oHiểu những khái niệm cơ phiên bản về độ phức tạp giám sát thời gian và không gian, trường thích hợp xấu nhất, tốt nhất và trung bình
oNhận biết và phân loại những lớp câu hỏi và các kỹ thuật phân tích
oHiểu, áp dụng được một số trong những kỹ thuật kiến thiết thuật toán như: phân chia để trị, thuật toán tham lam, phương pháp quy hoạch động, các thuật toán trang bị thị, những thuật toán song song, những thuật toán dựa trên xác suất.
oHiểu và giám sát được độ tinh vi của thuật toán cho các lớp vấn đề P, NP và NP - đầy đủ, phân tích những bài toán NP - đầy đủ, các bài toán NP – khó, những thuật toán ko xác định.
oHiểu và biết cách áp dụng những thuật toán heuristic, các thuật toán xấp xỉ đối với bài toán NP – khó, những bài toán xê dịch NP – khó, những lược vật xấp xỉ.
oBiết được một vài hướng nghiên cứu và phân tích thuật toán và độ tinh vi thuật toán.
ØKỹ năng:
Trang bị mang đến sinh viên kỹ năng:
oKỹ năng phân tích hiệu quả của thuật toán trong một vài nhiệm vụ cơ bản.
oNhận dạng lớp bài bác toán
oKỹ năng thuyết trình
ØThái độ:
Góp phần rèn luyện cho sinh viên:
oKỹ năng thao tác khoa học tráng lệ và đúng mực cao
6.NỘI DUNG HỌC PHẦN:
PHÂN BỐ THỜI GIAN
| STT | Nội dung | Tổng số tiết | Trong đó | Ghi chú | |
| Lý thuyết | Bài tập, thảo luận, kiểm tra |
| |||
| 1 | Chương I | 9 | 6 | 3 | Học trong chống máy |
| 2 | Chương II | 24 | 12 | 12 | |
| 3 | Chương III | 6 | 3 | 3 | |
| 4 | Chương IV | 6 | 3 | 3 | |
| Cộng | 45 | 24 | 21 |
CHƯƠNG I - CÁC KHÁI NIỆM CĂN BẢN
Chương I phân tích và lý giải vai trò của thuật toán, cung cấp các khái niệm câu hỏi và quy mô tính toán; những kiến thức căn bản về thuật toán, độ tinh vi thuật toán; những phép toán cơ bản, cam kết hiệu tiệm cận; việc đệ quy và các phương thức giải bí quyết đệ quy như: cách thức đoán nhận; cách thức lặp, cách thức sử dụng Định lý Master Theory
CHƯƠNG II - CÁC PHƯƠNG PHÁP THIẾT KẾ THUẬT TOÁN
Phân tích một số phương thức thiết kế thuật toán trên một trong những lớp vấn đề cơ bạn dạng như: phân chia để trị, Thuật toán tham lam, cách thức quy hoạch động, những thuật toán đồ gia dụng thị, những thuật toán song song, những thuật toán dựa vào xác suất.
CHƯƠNG III -ĐỘ PHỨC TẠP THUẬT TOÁN
CÁC LỚP BÀI TOÁN P, NP, NP ĐẦY ĐỦ
Trình bày khái niệm độ tinh vi tính toán, cách thức tính độ phức tạp đo lường của một số bài toán. Phân các loại và cách thức tính toán độ phức hợp thuật toán cho các lớp việc P, NP cùng NP - đầy đủ.
CHƯƠNG IV - CÁC THUẬT TOÁN HEURISTIC
VÀ THUẬT TOÁN XẤP XỈ
Giới thiệu những thuật toán Heuristic với thuật toán xấp xỉ so với các việc NP-khó; những bài toán xê dịch NP-Khó; các lược thiết bị xấp xỉ
7. GIÁO TRÌNH:
8. TÀI LIỆU THAM KHẢO:
<2>. Anany Levitin (2012), Introduction khổng lồ the Design và Analysis of Algorithms (3nd Edition).
<4>. Sandeep Sen (2009) Lecture Notes for Algorithm Analysis and Design Department of Computer Science & Engineering, IIT Delhi, New Delhi 110016, India.
