Bài toán thực tế Part B: Nén dữ liệu RLE

🎯 Run-Length Encoding (RLE)

Đây là bài toán rất hay gặp. Nén chuỗi ký tự liên tiếp.

Input: "AAABBBCCCC"

Output: "A3B3C4"

current_char = input[0]
count = 1
for i from 1 to len(input) - 1:
    if input[i] == current_char:
        count++
    else:
        print(current_char, count)
        current_char = input[i]
        count = 1
print(current_char, count) // In nốt nhóm cuối
                    

Câu hỏi đề thi: Nếu chuỗi là "ABC" (không lặp) thì nén xong thành "A1B1C1" (dài gấp đôi). Làm sao khắc phục?

🎯 Cây nhị phân (Binary Tree) - Khái niệm cốt lõi

• Pre-order (Tiền thứ tự): Root -> Trái -> Phải.
• In-order (Trung thứ tự): Trái -> Root -> Phải. (Dùng để duyệt cây BST theo thứ tự tăng dần).
• Post-order (Hậu thứ tự): Trái -> Phải -> Root. (Dùng để xóa cây).

🎯 Cây tìm kiếm nhị phân (Binary Search Tree - BST)

Quy tắc vàng: Node trái < Root < Node phải.

function insert(root, val):
    if root == null: return Node(val)
    if val < root.val:
        root.left = insert(root.left, val)
    else:
        root.right = insert(root.right, val)
    return root
                    

🎯 Độ tin cậy hệ thống (Availability Math)

Vd: MTBF = 900 giờ. MTTR = 100 giờ.

-> A = 900 / (900 + 100) = 0.9 (90%).

Hệ thống nối tiếp (Serial): A = A1 * A2 (Luôn nhỏ đi). (0.9 * 0.9 = 0.81).

Hệ thống song song (Parallel): A = 1 - (1-A1)*(1-A2) (Luôn tăng lên). (1 - 0.1*0.1 = 0.99).

🎯 Quản lý rủi ro (Risk Management)

4 chiến lược xử lý rủi ro:

1. Avoidance (Tránh): Không làm dự án đó nữa để khỏi gặp rủi ro.
2. Mitigation (Giảm thiểu): Cài đặt Firewall, Backup để giảm thiệt hại.
3. Transfer (Chuyển giao): Mua bảo hiểm hoặc thuê bên thứ 3 làm.
4. Acceptance (Chấp nhận): Chấp nhận rủi ro vì chi phí phòng chống quá đắt.

🎯 Phân tích độ phức tạp thời gian (Big O)

🎯 Kỹ thuật thiết kế thuật toán

• Greedy (Tham ăn): Luôn chọn lựa tốt nhất ở thời điểm hiện tại. (Vd: Dijkstra, Huffman).
• Divide and Conquer (Chia để trị): Chia bài toán to thành các bài toán nhỏ tương tự. (Vd: Merge Sort, Quick Sort).
• Dynamic Programming (Quy hoạch động): Giải các bài toán nhỏ và LƯU KẾT QUẢ lại để dùng sau. (Vd: Fibonacci tối ưu, Bài toán cái túi - Knapsack).

🎯 Thuật toán tìm kiếm A* (A-Star)

Nâng cấp của Dijkstra dùng trong Game (AI di chuyển).

Công thức: f(n) = g(n) + h(n)

• g(n): Chi phí thực tế từ Start đến Root hiện tại.
• h(n): Chi phí ƯỚC TÍNH (Heuristic) từ Root hiện tại đến ĐÍCH. (Vd: Khoảng cách chim bay).

👉 A* giúp máy tính tìm đường "thông minh" hơn bằng cách ưu tiên hướng về phía đích.

🎯 Đồ thị (Graph) - Các khái niệm bổ trợ

• Bậc của đỉnh (Degree): Số cạnh nối với đỉnh đó.
• Đồ thị có hướng (Directed Graph): Cạnh có mũi tên chỉ hướng.
• Đồ thị liên thông: Có đường đi giữa bất kỳ 2 đỉnh nào.