*
maxgate.vn.edu.vn
*

Giới ThiệuThông tin Khung chương trìnhĐào Tạo Chương trình huấn luyện và đào tạo cử nhân Chương thơm trình huấn luyện và giảng dạy 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ới kiến tạo thuật toán

Tiếng Anh:Design và 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 những học tập phần sau đây nhằm hấp thu được giỏi rộng.

Bạn đang xem: Phân tích và thiết kế thuật toán

-Nhập môn công nghệ thông tin.

-Cấu trúc tài liệu cùng giải thuật.

-Trung tâm lập trình

4.MÔ TẢ HỌC PHẦN:

Phân tích và kiến thiết thuật tân oán là học phần bắt buộc chăm ngành Công nghệ đọc tin. Học phần này reviews những kỹ thuật Giao hàng đến thiết kế và so với tác dụng những thuật toán, thừa nhận rất mạnh tay vào các phương pháp hữu dụng vào thực tiễn. Thông qua câu hỏi tính tân oán độ phức tạp cùng đi sâu so với các phạm vi khác nhau của các lớp bài bác tân oán cơ phiên bản sẽ giúp người học tập làm rõ về chuyển động này.

* Nội dung học phần bao gồm:

§Tổng quan các có mang về thuật tân oán, tiệm cận, độ phức tạp thuật toán thù của những bài bác toán thù cơ phiên bản và những lớp bài xích tân oán cạnh tranh.

§Trình bày cùng phân tích các chuyên môn Sắp xếp, cây tra cứu kiếm, vun gò, hàm băm, phân tách nhằm trị, quy hướng động, thuật toán tham lam, những thuật toán thứ thị, cùng đường đi nlắp nhất…

§Một số chủ đề cải thiện.

§Tính toán thù độ phức hợp thuật toán thù cho các bài xích toán cơ bạn dạng cùng những lớp bài toán cạnh tranh.

§Các thuật tân oán Heuristic với thuật tân oán xấp xỉ

§Một vài hướng nghiên cứu và phân tích về độ tinh vi thuật toán.

5.MỤC TIÊU HỌC PHẦN:

ØVề con kiến thức:

Mục tiêu của học tập phần này là khám phá làm gắng như thế nào nhằm cải cách và phát triển các thuật toán kết quả cho các trọng trách tính tân oán cơ bạn dạng với giải thích về tính chất đúng mực của chúng.

Sinc viên sau thời điểm học hoàn thành học tập phần này sẽ:

oHiểu được các ý tưởng cơ bạn dạng về các thuật tân oán.

oHiểu các tư tưởng cơ phiên bản về độ phức tạp tính toán thù thời gian cùng không khí, ngôi trường hòa hợp xấu nhất, tốt nhất cùng trung bình

oNhận biết và phân một số loại các lớp bài xích tân oán và các nghệ thuật phân tích

oHiểu, vận dụng được một trong những chuyên môn kiến thiết thuật tân oán như: Chia nhằm trị, thuật tân oán tmê say lam, phương thức quy hướng đụng, các thuật tân oán đồ thị, các thuật toán thù tuy vậy tuy vậy, những thuật toán dựa trên xác suất.

oHiểu cùng tính toán thù được độ phức tạp của thuật toán thù cho các lớp bài bác toán P, NP.. với NPhường - vừa đủ, đối chiếu các bài bác toán thù NPhường - không thiếu, những bài xích tân oán NPhường – cực nhọc, các thuật tân oán ko xác minh.

oHiểu cùng biết cách vận dụng các thuật toán heuristic, các thuật tân oán xấp xỉ so với bài xích toán thù NP – nặng nề, những bài xích tân oán dao động NP – khó, các lược thiết bị xê dịch.

oBiết được một số hướng phân tích thuật tân oán với độ phức hợp thuật toán thù.

ØKỹ năng:

Trang bị mang lại sinch viên kỹ năng:

oKỹ năng phân tích hiệu quả của thuật toán thù trong một vài trách nhiệm cơ bạn dạng.

oNhận dạng lớp bài toán

oKỹ năng thuyết trình

ØThái độ:

Góp phần rèn luyện đến sinh viên:

oKỹ năng thao tác kỹ thuật tráng lệ và trang nghiêm với đú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

các bài luyện tập, bàn luận, kiểm tra

1

Chương thơm I

9

6

3

Học vào phòng máy

2

Chương thơm II

24

12

12

3

Chương III

6

3

3

4

Chương thơm IV

6

3

3

Cộng

45

24

21

CHƯƠNG I - CÁC KHÁI NIỆM CĂN BẢN

Cmùi hương I lý giải phương châm của thuật toán, cung ứng các có mang bài bác tân oán và quy mô tính toán; Các kỹ năng và kiến thức căn bản về thuật toán, độ tinh vi thuật toán; Các phxay toán thù cơ bản, cam kết hiệu tiệm cận; Bài toán đệ quy với các cách thức giải công thức đệ quy như: Pmùi hương pháp đoán nhận; Pmùi hương pháp lặp, Pmùi hương pháp thực hiện Đị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ố trong những cách thức xây đắp thuật tân oán bên trên một số lớp bài bác toán cơ bản như: Chia để trị, Thuật toán thù tmê mệt lam, Phương pháp quy hoạch rượu cồn, Các thuật toán thứ thị, Các thuật tân oán tuy vậy tuy vậy, Các thuật toán thù dựa trên Tỷ Lệ.

CHƯƠNG III -ĐỘ PHỨC TẠPhường THUẬT TOÁN

CÁC LỚPhường BÀI TOÁN Phường, NP.., NP ĐẦY ĐỦ

Trình bày khái niệm độ phức hợp tính toán thù, phương pháp tính độ tinh vi tính tân oán của một trong những bài tân oán. Phân các loại với phương pháp tính toán độ phức tạp thuật tân oán cho những lớp bài xích toán thù P, NP.. và NP - không thiếu thốn.

CHƯƠNG IV - CÁC THUẬT TOÁN HEURISTIC

VÀ THUẬT TOÁN XẤP. XỈ

Giới thiệu các thuật toán thù Heuristic với thuật tân oán dao động đối với những bài bác toán NP-khó; Các bài bác toán xê dịch NP-Khó; Các lược đồ dùng xấp xỉ

7. GIÁO TRÌNH:

8. TÀI LIỆU THAM KHẢO:

<2>. Anany Levitin (2012), Introduction to lớn the Design & Analysis of Algorithms (3nd Edition).

Xem thêm: Cách Chơi Đội Hình Thần Tài Dtcl Mùa 4, Cách Chơi Đội Hình Thần Tài Sát Thủ Dtcl Mùa 4

<4>. Sandeep Sen (2009) Lecture Notes for Algorithm Analysis and Design Department of Computer Science và Engineering, IIT Delhi, New Delhi 110016, India.