COS157

Phân tích và Thiết kế Giải thuật

Học xong bạn chọn được chiến lược giải thuật phù hợp và ước lượng được chi phí.

16 video tiếng Việt có phụ đề, bám giáo trình Levitin (3rd), Buổi 2–9. Xem trước buổi học, thử câu hỏi neo, rồi làm mô phỏng.

16 bài · tổng 112:51

  1. Bài 1
  2. Bài 2
  3. Bài 3
  4. Bài 4
  5. Bài 5
  6. Bài 6
  7. Bài 7
  8. Bài 8
  9. Bài 9
  10. Bài 10
  11. Bài 11
  12. Bài 12
  13. Bài 13
  14. Bài 14
  15. Bài 15
  16. Bài 16
Video COS157
LoạiTênThông tinThời lượng
VideoPhân tích thuật toán không đệ quy từng bước: phép toán cơ bản và tỉ số T(2n)/T(n)Nếu dữ liệu gấp đôi, thuật toán chạy lâu gấp mấy lần?Buổi 2 · Nền tảng phân tích thuật toán8:14
VideoXếp 1 000 bài thi: từ 499 500 xuống 8 977 lần so nhờ Merge SortXếp 1 000 bài thi cần bao nhiêu lần so sánh?Buổi 3 · Chia để trị, hệ thức truy hồi, Định lý Tổng quát5:15
VideoTháp Hà Nội 64 đĩa xếp mất bao lâu? Giải hệ thức bằng thế ngượcTháp Hà Nội 64 đĩa phải chuyển bao nhiêu lần?Buổi 3 · Chia để trị, hệ thức truy hồi, Định lý Tổng quát8:14
VideoMaster Theorem trong 5 phút: phễu, cột hay kim tự tháp?Chia bài toán rồi gộp lại, công sức dồn về đâu: gốc, lá hay đều các tầng?Buổi 3 · Chia để trị, hệ thức truy hồi, Định lý Tổng quát5:21
VideoPhân hoạch Hoare — vì sao danh sách đã xếp sẵn lại làm Quicksort chậm nhất?Danh sách đã xếp sẵn mà Quicksort lại chậm nhất, vì sao?Buổi 4 · Chia để trị, hệ thức truy hồi, Định lý Tổng quát5:43
VideoNhân nhanh hơn cách ở trường: mẹo ba phép nhân của KaratsubaNhân hai số lớn, có cách nào ít phép nhân hơn cách học ở trường?Buổi 4 · Chia để trị, hệ thức truy hồi, Định lý Tổng quát5:51
VideoStrassen: nhân ma trận bằng bảy phép nhân thay cho támNhân hai ma trận cần tám phép nhân con, có bớt được một phép không?Buổi 4 · Chia để trị, hệ thức truy hồi, Định lý Tổng quát5:39
VideoFibonacci: một dòng ghi nhớ cắt 331 triệu lời gọi còn 79Vì sao tính Fibonacci bằng đệ quy lại tính đi tính lại cùng một giá trị?Buổi 5 · Quy hoạch động5:10
VideoBài toán đổi tiền: tham lam hay quy hoạch động?Đổi tiền: lấy tờ lớn nhất trước có luôn ra ít tờ nhất không?Buổi 5 · Tham lam8:15
VideoCái túi 0/1: một bảng 4 000 ô thay cho hơn một nghìn tỉ phép thửTúi chỉ chịu được một sức nặng, chọn đồ nào để giá trị lớn nhất mà không thử hết mọi cách?Buổi 6 · Quy hoạch động5:05
VideoChuỗi con chung dài nhất (LCS): Git biết bạn sửa dòng nàoLàm sao máy biết bạn đã sửa những dòng nào giữa hai phiên bản?Buổi 6 · Quy hoạch động8:28
VideoNén dữ liệu bằng cây: thuật toán Huffman từng bướcKý tự hay gặp thì mã ngắn, ký tự hiếm thì mã dài: xếp thế nào cho tổng ngắn nhất?Buổi 7 · Tham lam8:18
VideoBài toán tám quân hậu: vì sao quay lui nhanh hơn thử hết?Đặt tám quân hậu không ăn nhau: sao không thử hết mọi cách đặt?Buổi 8 · Quay lui và cắt nhánh8:13
VideoQuay lui và hai luật cắt: xét 281 nút trong cây hơn hai triệu nútKhi nào bỏ được cả một nhánh tìm kiếm mà không sợ mất đáp án?Buổi 8 · Quay lui và cắt nhánh8:28
VideoQuay lui và cắt nhánh cho bài toán Người bán hàng rong (TSP - Traveling Salesman Problem)Người bán hàng rong phải qua mọi thành phố, làm sao bỏ sớm những đường chắc chắn dài?Buổi 9 · Quay lui và cắt nhánh8:04
VideoP và NP: kiểm một đáp án dễ — vậy tìm có dễ không?Kiểm một đáp án thì dễ, vậy tìm ra đáp án có dễ không?Buổi 9 · Độ phức tạp tính toán (P và NP)8:33