Ngoài lề

Sưu tầm 1

Nguồn: https://vk.com/po_matematike

Tiêu đề gốc. Метод сопряжённых градиентов: линейная алгебра с ускорением.

Tiêu đề. Phương pháp gradient liên hợp: đại số tuyến tính với tốc độ cao.

Khi hệ phương trình tuyến tính \(\bm{A} \bm{x} = \bm{b}\) có quy mô cực lớn (hàng triệu biến), việc lưu trữ toàn bộ ma trận \(\bm{A}\) và sử dụng các phương pháp trực tiếp như phân tích LU trở nên bất khả thi. Đặc biệt khi \(\bm{A}\) là ma trận thưa, đối xứng và xác định dương (định thức dương?). Trong trường hợp này, phương pháp Gradient liên hợp (Conjugate Gradients - CG) là một trong những thuật toán lặp hiệu quả nhất.

Khác với phương pháp Gradient Descent, CG không chỉ “tiến dần” về cực tiểu của hàm bậc hai:

\[f(\bm{x}) = \frac{1}{2} \cdot \bm{x}^\top \bm{A} \bm{x} - \bm{b}^\top \bm{x}\]

mà di chuyển theo các hướng liên hợp với nhau, giúp tránh lãng phí bước đi. Về lý thuyết, sau đúng \(n\) bước, CG tìm được nghiệm chính xác, nhưng trên thực tế, quá trình hội tụ thường đạt được sớm hơn nhiều.

Ý tưởng chính. Thay vì chọn hướng gradient \(\bm{r}_k = \bm{b} - \bm{A} \bm{x}_k\) ở mỗi bước, CG chọn hướng \(\bm{p}_k\) liên hợp với các hướng trước đó theo \(\bm{A}\):

\[\bm{p}_{k+1} = \bm{r}_{k+1} + \beta_k \bm{p}_k, \quad \beta_k = \frac{\bm{r}_{k+1}^\top \bm{r}_{k+1}}{\bm{r}_k^\top \bm{r}_k}.\]

Cập nhật nghiệm. Nghiệm mới được tính bằng:

\[\bm{x}_{k+1} = \bm{x}_k + \alpha_k \bm{p}_k, \quad \alpha_k = \frac{\bm{r}_k^\top \bm{r}_k}{\bm{p}_k^\top \bm{A} \bm{p}_k}.\]

Ưu điểm quan trọng. Không cần lưu trữ toàn bộ ma trận \(\bm{A}\), chỉ cần khả năng tính nhanh \(\bm{A} \bm{x}\).

Ứng dụng rộng rãi trong:

  • phương pháp tính;

  • học máy;

  • đồ họa máy tính;

  • giải phương trình đạo hàm riêng.

Phương pháp này minh họa cách lựa chọn hình học thông minh (liên hợp thay vì trực giao) giúp tăng tốc đáng kể tính toán.

Sưu tầm 3

Một số mô hình mật mã

Chaum, Undeniable signature

Казарин О.В. Конвертируемые и селективно конвертируемые схемы подписи с верификацией по запросу

Мультиподпись: \((n, t)\)-пороговые схемы

Giao thức mật mã trong ngân hàng

Банк. крип. протоколы:

  • электронная монета

  • электронный бумажник

  • схемы Чома (Chaum, Online cash checkers)

  • проблемы арбитража, процедуры разрешения спросов (процедур арбитража)

  • Handbook of Applied Cryptography

Tài liệu luật

Нормативные документы:

  • указ Президента “О мерах по соблюдению …” 03.04.1995 N 334

  • постановление Правительства 16.04.2012 № 313

  • постановление Правительства 09.02.2012 № 111

  • концепция введения … оформляемого в виде пластической карты с электронным носителем

  • положение о разработке, … (ПК3-2025)

  • 40-ФЗ о ФСБ

  • положение о ФСБ, утв. указом Президента 11.08.2003 № 906