Một số ước lượng của số Frobenius

ĐẠI HỌC THÁI NGUYÊN

TRƯỜNG ĐẠI HỌC KHOA HỌC

TRẦN VĂN LỰC

MỘT SỐ ƯỚC LƯỢNG CỦA

SỐ FROBENIUS

LUẬN VĂN THẠC SỸ TOÁN HỌC

THÁI NGUYÊN - NĂM 2015

ĐẠI HỌC THÁI NGUYÊN

TRƯỜNG ĐẠI HỌC KHOA HỌC

TRẦN VĂN LỰC

MỘT SỐ ƯỚC LƯỢNG CỦA

SỐ FROBENIUS

LUẬN VĂN THẠC SỸ TOÁN HỌC

Chuyên ngành: PHƯƠNG PHÁP TOÁN SƠ CẤP

Mã số: 60 46 01 13

Người hướng dẫn khoa học

PGS.TS. ĐÀM VĂN NHỈ

THÁI NGUYÊN - NĂM 2015

i

Mục lục

Mở đầu 1

1 Một vài thuật toán 3

1.1 Vấn đề Frobenius . . . . . . . . . . . . . . . . . . . . . . 3

1.2 Thuật toán Euclide . . . . . . . . . . . . . . . . . . . . . 6

1.2.1 Xác định ước chung lớn nhất . . . . . . . . . . . . 6

1.2.2 Chương trình tìm ước số chung lớn nhất . . . . . . 7

1.2.3 Giải phương trình ax + by = c . . . . . . . . . . . 8

1.3 Thuật toán xác định g(a1, a2, a3) . . . . . . . . . . . . . . 8

1.3.1 Thuật toán Rodseth . . . . . . . . . . . . . . . . . 8

1.3.2 Thuật toán Davison . . . . . . . . . . . . . . . . . 9

1.3.3 Thuật toán Killingbergtro . . . . . . . . . . . . . . 11

1.3.4 Thuật toán Greenberg . . . . . . . . . . . . . . . . 12

1.4 Độ phức tạp về phương diện tính số Frobenius . . . . . . 13

1.4.1 Độ phức tạp . . . . . . . . . . . . . . . . . . . . . 13

1.4.2 Một vài số chặn trên hoặc chặn dưới của số Frobenius 14

2 Số Frobenius 15

2.1 Số Frobenius cho n = 2, n = 3 . . . . . . . . . . . . . . . 15

2.1.1 Số Frobenius g(a, b) . . . . . . . . . . . . . . . . . 15

2.1.2 Tiếp cận số Frobenius qua hàm sinh . . . . . . . . 18

2.1.3 Về Số Frobenius g(a, b, c) . . . . . . . . . . . . . . 20

2.1.4 Một vài công thức chặn trên . . . . . . . . . . . . 21

2.2 Về Số Frobenius g(a1, a2, a3, a4) . . . . . . . . . . . . . . 24

2.2.1 Một vài kết quả về g(a1, a2, a3, a4) . . . . . . . . . 24

2.2.2 Một số ví dụ bổ sung . . . . . . . . . . . . . . . . 28