Deploy FMath nhưng với theme cũ của TMATH

Truy cập tại đây

Dữ liệu database được đồng bộ nên các tài khoản, bài nộp, bảng xếp hạng đều được giữ lại ở trang có tiền tố old.

• ở trang mới này vẫn còn một chút lỗi về trang /about chưa được đồng bộ, vẫn còn tên TMath trên NavBar và các khu vực khác
• các tính năng cũ được giữ nguyên (một số có thể không hoạt động vì sự khác biệt giữa 2 database được sử dụng trong 2 phiên bản)
• những superuser, admin, staff vẫn có thể truy cập trang /admin và sử dụng như phiên bản mới

NHẬP MÔN QUY HOẠCH ĐỘNG

1. Quy hoạch động là gì và được mô tả như thế nào?

Quy hoạch động (Dynamic Programming - DP) là một kỹ thuật thuật toán thường dựa trên một công thức truy hồi và một (hoặc một vài) trạng thái khởi đầu. Một lời giải con của bài toán được xây dựng từ các lời giải con trước đó.

Các thuật toán DP thường có độ phức tạp đa thức, giúp đảm bảo thời gian chạy tối ưu hơn rất nhiều so với các kỹ thuật vét cạn (brute-force) hay quay lui (backtracking).

2. Ví dụ 1: Bài toán Đổi tiền (Coin Change)

Đề bài:

Cho danh sách \(N\) đồng xu có giá trị \(V_1, V_2, \dots, V_N\) và tổng số tiền cần đạt được là \(S\). Hãy tìm số lượng đồng xu ít nhất để tổng giá trị đúng bằng \(S\) (mỗi đồng xu có thể sử dụng nhiều lần), hoặc kết luận không thể đổi được.

Xây dựng lời giải

• Trạng thái (State): Trạng thái là cách mô tả một bài toán con. Ta gọi trạng thái \(i\) (\(i \le S\)) là số lượng đồng xu ít nhất để tạo ra tổng giá trị \(i\). Để tính trạng thái \(i\), ta cần biết kết quả của các trạng thái nhỏ hơn \(j\) (\(j < i\)).
• Cách tìm trạng thái:
• Với mỗi đồng xu \(j\) thỏa mãn \(V_j \le i\), ta xét số lượng đồng xu tối thiểu để tạo ra tổng \(i - V_j\).
• Giả sử số lượng đồng xu tối thiểu cho tổng \(i - V_j\) là \(m\). Nếu \(m + 1\) nhỏ hơn số lượng đồng xu tối thiểu hiện tại của tổng \(i\), ta cập nhật lại giá trị tối ưu cho \(i\).

Ví dụ minh họa

• Các đồng xu: \(1, 3, 5\).
• Tổng cần đạt: \(S = 11\).

Khởi tạo:

• Với tổng \(0\): Cần \(0\) đồng xu (\(\text{Min}[0] = 0\)).
• Với các tổng khác: Gán giá trị ban đầu là \(\infty\).

Quá trình tính toán:

• Tổng \(S = 1\): Chỉ có đồng xu \(1 \le 1\). Xét \(1 - 1 = 0 \rightarrow \text{Min}[1] = \text{Min}[0] + 1 = 1\).
• Tổng \(S = 2\): Chỉ có đồng xu \(1 \le 2\). Xét \(2 - 1 = 1 \rightarrow \text{Min}[2] = \text{Min}[1] + 1 = 2\).
• Tổng \(S = 3\): Có 2 đồng xu khả dụng (\(1, 3\)):
• Dùng đồng \(1\): Tổng \(3 - 1 = 2\) cần \(2\) đồng \(\rightarrow 2 + 1 = 3\) đồng.
• Dùng đồng \(3\): Tổng \(3 - 3 = 0\) cần \(0\) đồng \(\rightarrow 0 + 1 = 1\) đồng.

• Chọn tối ưu: \(\text{Min}[3] = 1\).

• Tổng \(S = 4\):

• Dùng đồng \(1\): Tổng \(4 - 1 = 3\) cần \(1\) đồng \(\rightarrow 1 + 1 = 2\) đồng.
• Dùng đồng \(3\): Tổng \(4 - 3 = 1\) cần \(1\) đồng \(\rightarrow 1 + 1 = 2\) đồng.

• Chọn tối ưu: \(\text{Min}[4] = 2\).

• Tổng \(S = 5\):

• Dùng đồng \(1\): Cần \(1 + \text{Min}[4] = 3\) đồng.
• Dùng đồng \(3\): Cần \(1 + \text{Min}[2] = 3\) đồng.
• Dùng đồng \(5\): Cần \(1 + \text{Min}[0] = 1\) đồng.

• Chọn tối ưu: \(\text{Min}[5] = 1\).

• Tiếp tục lần lượt cho các tổng \(6, 7, \dots, 11\).

Kết quả: Số đồng xu ít nhất để tạo thành tổng \(11\) là 3 đồng xu (\(5 + 5 + 1\)).

3. Ví dụ 2: Dãy con không giảm dài nhất (Longest Non-Decreasing Subsequence)

Đề bài:

Cho dãy gồm \(N\) số: \(A[1], A[2], \dots, A[N]\). Hãy tìm độ dài lớn nhất của dãy con không giảm.

Bước 1: Xác định trạng thái

• Định nghĩa trạng thái \(S[i]\) là độ dài của dãy con không giảm dài nhất kết thúc tại phần tử \(A[i]\).
• \(S[i]\) chỉ phụ thuộc vào các phần tử đứng trước nó (\(j < i\)) và không bị thay đổi bởi các phần tử phía sau.

Bước 2: Công thức truy hồi

• Khởi tạo: Mỗi phần tử đứng một mình tạo thành dãy con độ dài 1: $\(S[i] = 1 \quad (\forall i = 1 \dots N)\)$

• Chuyển trạng thái: Với mỗi \(j < i\), nếu \(A[j] \le A[i]\) và \(S[j] + 1 > S[i]\), ta cập nhật: $\(S[i] = S[j] + 1\)$

Ví dụ minh họa

Xét dãy số: \(5, 3, 4, 8, 6, 7\)

Kết quả: Độ dài dãy con không giảm dài nhất là 4.

4. Một số bài tập vận dụng đề xuất

• Bài toán chiếc balo 5 (Unbounded Knapsack)
• Bài toán xâu con chung dài nhất (LCS)

TIÊU CHUẨN ĐẶT TÊN TRONG LẬP TRÌNH

Tác giả: Pham Anh Tu

Trong lập trình chuyên nghiệp, việc đặt tên cho biến, hàm, và lớp là rất quan trọng để đảm bảo mã nguồn dễ đọc, dễ hiểu và dễ bảo trì. Dưới đây là một số tiêu chuẩn chung cho việc đặt tên:

1. Biến (Variables)

• Camel Case: Sử dụng cho biến cục bộ hoặc biến trong phương thức. Từ đầu tiên viết thường, các từ tiếp theo viết hoa chữ cái đầu.

• Ví dụ: studentName, totalAmount, isActive.

• Snake Case: Thường dùng cho các biến toàn cục hoặc biến hằng (viết hoa toàn bộ đối với hằng số).

• Ví dụ: MAX_HEIGHT, MIN_WIDTH, global_variable.

2. Hàm (Functions/Methods)

• Camel Case: Tương tự như biến, các hàm thường dùng Camel Case với chữ cái đầu của từ đầu tiên viết thường và các từ tiếp theo viết hoa chữ cái đầu.

• Ví dụ: calculateTotal(), getUserInfo(), processData().

• Mô tả hành động: Tên hàm nên miêu tả hành động hoặc chức năng mà hàm thực hiện (thường bắt đầu bằng động từ).

• Ví dụ: sendEmail(), validateInput(), fetchData().

3. Lớp (Classes)

• Pascal Case: Viết hoa chữ cái đầu của tất cả các từ.

• Ví dụ: Student, OrderManager, UserProfile.

• Danh từ: Tên lớp nên là một danh từ hoặc một cụm danh từ vì lớp thường đại diện cho một thực thể.

• Ví dụ: Invoice, Car, DatabaseConnection.

4. Giao diện (Interfaces)

• Pascal Case: Tương tự như lớp, nhưng thường có tiền tố bắt đầu bằng chữ “I”.
• Ví dụ: IUserService, IDatabaseConnection, IShape.

5. Module và File

• Snake Case hoặc Kebab Case: Thường dùng cho tên file và module.
• Ví dụ: user_profile.py, order_manager.js, data-processing.go.

6. Quy tắc chung

• Ngắn gọn và mô tả: Tên nên ngắn gọn nhưng đủ mô tả để người đọc có thể hiểu được ý nghĩa mà không cần đọc chi tiết bên trong.
• Tránh viết tắt không cần thiết: Chỉ sử dụng viết tắt khi chúng thực sự phổ biến và dễ hiểu.
• Tuân thủ quy ước của ngôn ngữ: Mỗi ngôn ngữ lập trình có những quy ước riêng (naming conventions), vì vậy nên tuân thủ theo các quy ước đó.

Ví dụ tổng quát

Python:

class Student:
    def __init__(self, student_name, student_id):
        self.student_name = student_name
        self.student_id = student_id

    def get_full_name(self):
        return f"{self.student_name} (ID: {self.student_id})"

MAX_AGE = 100
min_height = 150

def calculate_average(grades):
    total = sum(grades)
    return total / len(grades)

Java:

public class Student {
    private String studentName;
    private int studentId;

    public Student(String studentName, int studentId) {
        this.studentName = studentName;
        this.studentId = studentId;
    }

    public String getFullName() {
        return studentName + " (ID: " + studentId + ")";
    }
}

public interface IUserService {
    void createUser(User user);
    User getUserById(int userId);
}

Lưu ý: Những quy tắc này không phải là cố định và có thể thay đổi tùy theo ngôn ngữ và phong cách của từng dự án. Tuy nhiên, việc tuân thủ các tiêu chuẩn này giúp mã nguồn trở nên nhất quán và dễ quản lý hơn.

Ứng tuyển nhân viên vào công ty Bug (chuyên về một số lĩnh vực tin học)

Yêu cầu:

• Nạp CV cho chủ tịch adminduc (thông qua ai đó bạn quen)
• Kiểm tra bài tập tin học đầu vào
• Có thể có chỉ số ẩn (càng tốt)
• Có thể chịu đựng được hàng loạt thông báo mỗi phút
• Biết và được các thành viên trong công ty chấp nhận

Lợi ích:

• Học tập được nhiều điều, tương tác với các đồng nghiệp chuyên gia

Mẫu CV (của adminbao):

https://www.canva.com/design/DAHQWvOg6gg/bbaxm_QGbB4X_2cW88lu9w/edit

Hạn: 1/9/2026