Data structure and Algorithm

- 3 mins

Nguồn: giaithuatlaptrinh.com

Các kĩ thuật thiết kế thuật toán cơ bản

  1. Phương pháp quay lui
  2. Chia để trị: cơ bản, quick sort và merge sort, chọn median.
  3. Quy hoạch động: I, II, III, IV, V
  4. Các kĩ thuật cải tiến: I, II, III, IV
  5. Quy hoạch động trên cây.
  6. Thuật toán tham lam.
  7. Lý thuyết matroid.

Thuật toán ngẫu nhiên

  1. Xác suất cơ bản.
  2. Quicksort ngẫu nhiên và chọn median.
  3. Phép băm
  4. Thuật toán Miller-Rabin kiểm tra tính nguyên tố
  5. Phân tích ra thừa số: thuật toán vét cạn, thuật toán Pollard-Rho

Lý thuyết đồ thị

  1. Cơ bản về đồ thị
  2. Đường đi ngắn nhất
    • Thuật toán Bellman-Ford cho đồ thị có trọng số âm.
    • Thuật toán Floyd-Warshall cho đồ thị dầy.
    • Thuật toán Johnson cho đồ thị thưa.
  3. Cây khung nhỏ nhất
  4. Luồng trong mạng
  5. Lát cắt cực tiểu
  6. Cặp ghép
  7. Lý thuyết phổ đồ thị
    • Bài I – Introduction.
    • Bài II – Rayleigh quotient and Cheeger Inequality.
    • Bài III – Phổ của đồ thị đặc biệt.
    • Bài IV – Phổ của ma trậ kề và bài toán tô màu.

Phương pháp MWU

  1. Bài toán tham khảo chuyên gia - phần I.
  2. Bài toán tham khảo chuyên gia - phần II.
  3. Ứng dụng MWU trong các zero-sum game.
  4. Ứng dụng MWU trong thuật toán Winnow.

Tìm kiếm chuỗi

  1. Thuật toán Knuth-Morris-Pratt.
  2. Máy trạng thái hữu hạn và thuật toán KMP.
  3. Z algorithm
  4. Thuật toán Boyer-Moore
  5. Thuật toán Rabin-Karp
  6. Thuật toán Aho-Corasick tìm kiếm đa mẫu.
  7. Cây hậu tố: cơ bản, thuật toán Mccreight,
  8. Mảng hậu tố: cơ bản, thuật toán SA-IS.

Big Data

  1. 5 công cụ xác suất.
  2. Hệ thống gợi ý.
  3. Bloom filter.
  4. Locality sensitive hashing.

Phương pháp first-order

  1. Giới thiệu về tối ưu lồi.
  2. Phân tích tính hội tụ của GD.

Special Topics

  1. Tính chất Monge và thuật toán SMAWK
  2. Thuật toán Sweep Line
  3. Các kĩ thuật xử lí bít
  4. Tính tổng, tích và bán tổng.

Cấu trúc dữ liệu

  1. Danh sách liên kết đơn và các biến thể.
  2. Tổng quan về cây nhị phân cân bằng.
  3. Cây AVL: bài 1, bài 2.
  4. Heap nhị phân và thuật toán Heapsort.
  5. Cây Splay Tree.
  6. Cấu trúc Union-Find
  7. Cấu trúc mảng tự mở rộng
  8. Cây tìm kiếm ưu tiên - Priority Search Tree

NP-completeness**

  1. P vs NP.
  2. NP-complete.
  3. NP-complete trên đồ thị.
  4. Các bài toán Weakly NP-complete.

Appendix

Algorithm Data Structure Big Data Computer Science