Định lý Pick, dãy Farey, vòng tròn Ford và ứng dụng

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

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

LẠI THẾ HANH

ĐỊNH LÝ PICK, DÃY FAREY, VÒNG TRÒN

FORD VÀ ỨNG DỤNG

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

THÁI NGUYÊN - NĂM 2017

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

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

LẠI THẾ HANH

ĐỊNH LÝ PICK, DÃY FAREY, VÒNG TRÒN

FORD VÀ ỨNG DỤNG

Chuyên ngành: Phương pháp toán sơ cấp

Mã số: 60 46 01 13

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

NGƯỜI HƯỚNG DẪN KHOA HỌC

TS. Nguyễn Văn Hoàng

THÁI NGUYÊN - NĂM 2017

i

Mục lục

Lời mở đầu 1

1 Định lý Pick 3

1.1 Ví dụ về định lý Pick . . . . . . . . . . . . . . . . . . . . . . 3

1.2 Định lý Pick cho hình chữ nhật . . . . . . . . . . . . . . . . . 5

1.3 Tam giác vuông canh bên phải . . . . . . . . . . . . . . . . . 6

1.4 Định lý Pick cho tam giác bất kỳ . . . . . . . . . . . . . . . . 8

1.5 Định lý Pick cho trường hợp tổng quát . . . . . . . . . . . . . 10

1.5.1 Tổng quan về chứng minh . . . . . . . . . . . . . . . . 10

1.5.2 Ghép nối hai đa giác lưới . . . . . . . . . . . . . . . . . 12

1.5.3 Các đường chéo bên trong . . . . . . . . . . . . . . . . 13

1.5.4 Đa giác có lỗ thủng . . . . . . . . . . . . . . . . . . . . 14

2 Dãy Farey 17

2.1 Khái niệm và tính chất . . . . . . . . . . . . . . . . . . . . . . 17

2.2 Tìm kiếm phân số gần nhất trong dãy Farey Fn . . . . . . . . 22

2.2.1 Thuật toán tìm kiếm cải tiến . . . . . . . . . . . . . . 26

2.2.2 Phân tích hiệu suất . . . . . . . . . . . . . . . . . . . . 26

2.3 Một số ứng dụng có liên quan đến hình ảnh . . . . . . . . . . . 26

2.3.1 Đa giác mô phỏng gần đúng . . . . . . . . . . . . . . . 26

2.3.2 Phân tích hình ảnh . . . . . . . . . . . . . . . . . . . . 29

3 Vòng tròn Ford và liên hệ với định lý Pick, dãy Farey 32

3.1 Giới thiệu vòng tròn Ford . . . . . . . . . . . . . . . . . . . . 32

3.2 Mối liên hệ giữa định lý Pick và dãy Farey . . . . . . . . . . . 38

3.3 Mối liên hệ giữa dãy Farey và vòng tròn Ford . . . . . . . . . . 39

Kết luận 42

Tài liệu tham khảo 43

ii

Danh sách các kí hiệu

Kí hiệu Tên