Mối quan hệ giữa đa thức đối xứng (symmetric polinomial) và nghiệm (root) của phương trình đa thức

Du Mã đăng ngày 2024-Oct-18 trong Symmetric-Polinomials

Các đa thức đối xứng (symmetric polinomials) đóng vai trò quan trọng trong việc hiểu mối quan hệ giữa các nghiệm (root) của các phương trình đa thức và các hệ số (coefficient) của chúng. Trong bài viết này, chúng ta sẽ khám phá sâu hơn về mối liên hệ này, từ định nghĩa cơ bản đến các ứng dụng thực tiễn.

1. Đa thức đối xứng:

Định nghĩa cơ bản

Đa thức đối xứng với các biến $x_1, x_2, \ldots, x_n$ là một đa thức không thay đổi dưới bất kì phép hoán vị (permutation) nào của các biến. Cụ thể, với bất kì phép hoán vị $\sigma$ nào của các chỉ số ${1, 2, \ldots, n}$:

Bài toán Quy Hoạch Tuyến Tính - Dạng chuẩn (standard form)

Du Mã đăng ngày 2024-Sep-28 trong Linear Programming

Mục tiêu

Chúng ta cần chuyển bài toán quy hoạch tuyến tính từ dạng tổng quát (general form) sang dạng chuẩn (standard form). Tức là:

Tất cả các biến đều không âm.
Tất cả các ràng buộc là đẳng thức.
Hàm mục tiêu được biểu diễn theo các biến không âm mới.
Tất cả hệ số tự do đều không âm.
Hàm mục tiêu là cực tiểu hóa (Min).

Trong đó, (1),(2) và (3) là các yêu cầu bắt buộc. (4) và (5) không bắt buộc phải đảm bảo trong dạng chuẩn, nhưng đó sẽ là điều kiện bắt buộc khi giải bài toán tối ưu bằng phương pháp đơn hình về sau.

Phân hoạch (partition)

Du Mã đăng ngày 2024-Aug-25 trong Combinatorics

Các phân hoạch (partitions)

Tham khảo chủ yếu từ https://docs.oscar-system.org/stable/Combinatorics/EnumerativeCombinatorics/partitions/#partition

$$\lambda_1 \geq \lambda_2 \geq \dots \geq \lambda_r$$$$ n = \lambda_1 + \dots + \lambda_r .$$

Các $\lambda_i$ được gọi là các phần tử (part) của phân hoạch và $r$ được gọi là độ dài (length). Tham khảo thêm tại Ful97 và Knu11, Mục 7.2.1.4.

Một phân hoạch có thể được mã hóa (encoded) dưới dạng một mảng (array) với các phần tử (element) là $\lambda_i$. OSCAR cung cấp kiểu tham số (parametric type) Partition{T} và đây là một kiểu con (subtype) của AbstractVector{T}. Ở đây, T có thể là bất kì kiểu con nào của IntegerUnion. Hiệu suất không bị hảnh hưởng khi sử dụng kiểu riêng cho phân hoạch thay vì chỉ sử dụng mảng. Kiểu tham số này cho phép tăng hiệu suất bằng cách sử dụng các kiểu số nguyên nhỏ hơn.