CS112.L21---Algorithm-analysis-design

1. Thành viên nhóm:

STT	Họ tên	MSSV	GitHub	Email
1	Trương Thế Tấn	19522180	The Tan	19522180@gm.uit.edu.vn
2	Nông Thanh Hồng	19521551	Thanh Hong	19521551@gm.uit.edu.vn
3	Nguyễn Thành Luân	19521809	Thanh Luan	19521809@gm.uit.edu.vn
4	Đinh Trọng Tùng Sơn	19522132	Tung Son	19522132@gm.uit.edu.vn

2. Bài tập Thực hành

1. Bài tập 1 ngày 19/3/2021: link1
2. Bài tập 2 ngày 28/3/2021: link2
3. Bài tập 3 ngày 19/4/2021: link3
4. Bài tập 4 ngày 17/5/2021: link4

3. Đề tài Seminar

1. Nội dung: Giới thiệu phương pháp thiết kế thuật toán: Greedy approach.
2. Giới thiệu:

1. Một số kỹ thuật thường được sử dụng khi giải quyết các vấn đề:\

• Trong thiết kế thuật toán, không có một 'viên đạn bạc' nào có thể xuyên phá được tất cả các vấn đề tính toán. Các vấn đề khác nhau đòi hỏi sử dụng các loại kỹ thuật khác nhau. Một số kỹ thuật thường được sử dụng là:

  • Divide and Conquer (Chia để trị)
  • Randomized algorithms (các thuật toán ngẫu nhiên)
  • Greedy algorithms (Các thuật toán tham lam)
  • Dynamic programming (Quy hoạch động)

• Trong môn CS112, chủ đề Seminar của team sẽ là trình bày về Greedy algorithms. Cụ thể các bạn theo dõi file báo cáo Seminar_Greedy's Algorithm.ipynb. Báo cáo sẽ được cập nhật thường xuyên các vấn đề liên quan đến Greedy Algorithm.

2. Sơ lược lịch sử của các thuật toán tham lam:

   • Các thuật toán tham lam đã đươc hình thành cho nhiều thuật toán đi bộ vào những năm 1950.

   • Edsger Dijkstra đã khái niệm thuật toán để tạo ra cây khung tối thiểu. Ông nhắm đến việc rút ngắn khoảng cách của các tuyến đường trong thủ đô Amsterdam của Hà Lan.

     • Dijkstra's Algorithm

   • Trong cùng một thập kỷ, Prim và Kruskal đã đạt được các chiến lược tối ưu hóa dựa trên việc giảm thiểu chi phí đường đi dọc theo các tuyến đường được cân nhắc.

     • Prim's Algorithm
     • Kruskal's Algorithm
     • Minimum Spanning Tree (MST)

   • Vào những năm 70, các nhà nghiên cứu người Mỹ, Cormen, Rivest và Stein đã đề xuất một cấu trúc con đệ quy của các giải pháp tham lam trong cuốn sách giới thiệu kinh điển về thuật toán của họ.

     • Introduction to Algorithms

   • Mô hình tìm kiếm Tham lam đã được đăng ký như một loại chiến lược tối ưu hóa khác trong hồ sơ NIST vào năm 2005.

   • Cho đến ngày nay, các giao thức chạy web, chẳng hạn như đường dẫn mở đầu tiên (OSPF) và nhiều giao thức chuyển mạch gói mạng khác sử dụng chiến lược tham lam để giảm thiểu thời gian dành cho mạng.