Phân tích và đánh giá thuật toán năm 2024

Phân tích và thiết kế thuật toán

Tiếng Anh: Design and 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 sau đây để tiếp thu được tốt hơn.

- Nhập môn công nghệ 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à thiết kế thuật toán là học phần bắt buộc chuyên ngành Công nghệ thông tin. Học phần này giới thiệu các kỹ thuật phục vụ cho thiết kế và phân tích hiệu quả các thuật toán, nhấn mạnh vào các phương pháp hữu dụng trong thực tế. Thông qua việc tính toán độ phức tạp và đi sâu phân tích các phạm vi khác nhau của các lớp bài toán cơ bản sẽ giúp người học hiểu rõ về hoạt động này.

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

§ Tổng quan các khái niệm về thuật toán, tiệm cận, độ phức tạp thuật toán của các bài toán cơ bản và các lớp bài toán khó.

§ Trình bày và phân tích các kỹ thuật Sắp xếp, cây tìm kiếm, vun đống, hàm băm, chia để trị, quy hoạch động, thuật toán tham lam, các thuật toán đồ thị, và đường đi ngắn nhất…

§ Một số chủ đề nâng cao.

§ Tính toán độ phức tạp thuật toán cho các bài toán cơ bản và các lớp bài toán khó.

§ Các thuật toán Heuristic và thuật toán xấp xỉ

§ Một vài hướng nghiên cứu về độ phức tạp thuật toán.

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

Ø Về kiến thức:

Mục tiêu của học phần này là tìm hiểu làm thế nào để phát triển các thuật toán hiệu quả cho các nhiệm vụ tính toán cơ bản và lý luận về tính đúng đắn của chúng.

Sinh viên sau khi học xong học phần này sẽ:

o Hiểu được các ý tưởng cơ bản về các thuật toán.

o Hiểu các khái niệm cơ bản về độ phức tạp tính toán thời gian và không gian, trường hợp xấu nhất, tốt nhất và trung bình

o Nhận biết và phân loại các lớp bài toán và các kỹ thuật phân tích

o Hiểu, áp dụng được một số kỹ thuật thiết kế thuật toán như: Chia để trị, thuật toán tham lam, phương pháp quy hoạch động, các thuật toán đồ thị, các thuật toán song song, các thuật toán dựa trên xác suất.

o Hiểu và tính toán được độ phức tạp của thuật toán cho các lớp bài toán P, NP và NP - đầy đủ, phân tích các bài toán NP - đầy đủ, các bài toán NP – khó, các thuật toán không xác định.

o Hiểu và biết cách áp dụng các thuật toán heuristic, các thuật toán xấp xỉ đối với bài toán NP – khó, các bài toán xấp xỉ NP – khó, các lược đồ xấp xỉ.

o Biết được một số hướng nghiên cứu thuật toán và độ phức tạp thuật toán.

Ø Kỹ năng:

Trang bị cho sinh viên kỹ năng:

o Kỹ năng phân tích hiệu quả của thuật toán trong một số nhiệm vụ cơ bản.

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

o Kỹ năng thuyết trình

Ø Thái độ:

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

o Kỹ năng làm việc khoa học nghiêm túc và chính xá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 phò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 giải thích vai trò của thuật toán, cung cấp các khái niệm bài toán và mô hình tính toán; Các kiến thức căn bản về thuật toán, độ phức tạp thuật toán; Các phép toán cơ bản, ký hiệu tiệm cận; Bài toán đệ quy và các phương pháp giải công thức đệ quy như: Phương pháp đoán nhận; Phương pháp lặp, Phương pháp 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 pháp thiết kế thuật toán trên một số lớp bài toán cơ bản như: Chia để trị, Thuật toán tham lam, Phương pháp quy hoạch động, Các thuật toán đồ thị, Các thuật toán song song, Các thuật toán dựa trên 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 độ phức tạp tính toán, cách thức tính độ phức tạp tính toán của một số bài toán. Phân loại và cách thức tính toán độ phức tạp thuật toán cho các lớp bài toán P, NP và NP - đầy đủ.

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 Heuristic và thuật toán xấp xỉ đối với các bài toán NP-khó; Các bài toán xấp xỉ NP-Khó; Các lược đồ xấp xỉ

7. GIÁO TRÌNH:

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

[1]. Cormen T. H, Leiserson C. E, Rovest R. L (2009), Introduction to Algorithms, Third Edition, ISBN 978-0-262-03384-8 2009 by The Massachusetts Institute of Technology.

[2]. Anany Levitin (2012), Introduction to the Design and Analysis of Algorithms (3nd Edition).

[3]. Jon Kleinberg (2005) Algorithm Design, ISBN-13: 978-0321295354.

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