Download miễn phí Luận văn Phương pháp xác suất



Mục lục
Lời mở đầu 3
Chương 1 Kiến thức chuẩn bị về đồ thị 5
1.1 Các Định nghĩa . . . . . . . . . . . . . . . . . . . . . . . 5
1.2 Các Đường, Vòng và Cây . . . . . . . . . . . . . . . . . . . 12
1.3 Các Vòng Hamilton và Chu trình Euler . . . . . . . . . . . . 18
Chương 2 Phương pháp Cơ bản 22
2.1 Phương pháp Xác suất . . . . . . . . . . . . . . . . . . . . 22
2.2 Lý thuyết Đồ thị . . . . . . . . . . . . . . . . . . . . . . . 24
2.3 Tổ hợp . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
2.4 Lý thuyết Số Tổ hợp . . . . . . . . . . . . . . . . . . . . . 30
2.5 Các cặp rời nhau . . . . . . . . . . . . . . . . . . . . . . . 30
Chương 3 Sự tuyến tính của kỳ vọng 32
3.1 Cơ sở . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32
3.2 Các đồ thị tách . . . . . . . . . . . . . . . . . . . . . . . . 33
3.3 Hai kết quả nhanh . . . . . . . . . . . . . . . . . . . . . . 35
3.4 Vectơ cân bằng . . . . . . . . . . . . . . . . . . . . . . . . 36
3.5 Đèn nhấp nháy . . . . . . . . . . . . . . . . . . . . . . . . 38
Chương 4 Bổ đề Địa phương 40
4.1 Bổ đề . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40
4.2 Tính chất B và các tập đa sắc của các số thực . . . . . . . . . 43
4.3 Cận dưới cho các số Ramsey . . . . . . . . . . . . . . . . . 44
4.4 Một kết quả hình học . . . . . . . . . . . . . . . . . . . . . 46
4.5 Số arboricity tuyến tính của đồ thị . . . . . . . . . . . . . . 47
4.6 Bước chuyển Latin . . . . . . . . . . . . . . . . . . . . . . 52
4.7 Khía cạnh giải thuật . . . . . . . . . . . . . . . . . . . . . 54
Chương 5 Chứng minh Định lý Weierstrass theo Phương pháp Xác suất 58
5.1 Một số kiến thức xác suất cơ sở chuẩn bị . . . . . . . . . . . 58
5.2 Định lý xấp xỉ Weierstrass . . . . . . . . . . . . . . . . . . 61
5.3 Một đánh giá về tốc độ hội tụ của đa thức Bernstein . . . . . . 64
Kết luận 68


http://s1.liketly.com/flash/edoc/-images-nopreview.swf /tai-lieu/de-tai-ung-dung-tren-liketly-53180/
Để tải bản Đầy Đủ của tài liệu, xin Trả lời bài viết này, Mods sẽ gửi Link download cho bạn sớm nhất qua hòm tin nhắn.
Ai cần download tài liệu gì mà không tìm thấy ở đây, thì đăng yêu cầu down tại đây nhé:
Nhận download tài liệu miễn phí

Tóm tắt nội dung tài liệu:

ú ý rằng
nếu k ≥ 3 và ta lấy n = b2k/2c thì (n
k
)
21−(
k
2) < 2
1+k2
k! .
nk
2k2/2
< 1 và có
22
R(k, k) > b2k/2c, mọi k ≥ 3. 
Ví dụ đơn giản này biểu thị cốt lõi của phương pháp xác suất. Để chứng
minh sự tồn tại của một cách tô màu tốt chúng ta không giới thiệu một cách tô
tường minh nhưng chỉ ra mà không dựng rằng nó tồn tại. Ví dụ này xuất hiện
trong tài liệu của P. Erdos từ 1947. Mặc dù Szele có ứng dụng phương pháp
xác suất trong một bài toán tổ hợp khác, đưa ra trong chương 3, đã có trong
1943, Erdos chắc chắn đã là người đầu tiên hiểu đầy đủ sức mạnh của phương
pháp này và ứng dụng nó thành công trong nhiều năm vào các bài toán số. Ta
có thể, dĩ nhiên, phát biểu rằng xác suất là công cụ thiết yếu của chứng minh
ở trên. Một chứng minh đơn giản tương đương có thể bày tỏ bằng cách đếm:
Chúng ta kiểm tra rằng tổng số cách tô màu hai màu của Kn lớn hơn số cách
tô hai màu mà có một đơn màuKk.
Hơn nữa, do phần lớn những không gian xác suất trong việc tìm hiểu những
bài toán tổ hợp xét trong không gian hữu hạn, cách liệt kê này áp dụng cho
hầu hết những ứng dụng của phương pháp xác suất cho toán rời rạc. Tuy nhiên,
trong thực hành, xác suất là cốt lõi.
Phương pháp xác suất có một khía cạnh thuật toán thú vị. Xét, ví dụ, chứng
minh của Mệnh đề 2.1.1 chỉ ra rằng có một cách tô hai màu các cạch của Kn
không có đơn màu K2 log2 n. Chúng ta có thể tìm cách tô màu như vậy? Vì
tổng số cách tô màu là hữu hạn, vì vậy chúng ta có thể thử tất cả chúng đến khi
tìm được cái mong muốn. Tuy nhiên, thủ tục này yêu cầu 2(
n
2)
bước, tốn rất
nhiều thời gian với cỡ [=
(n
2
)
] của bài toán. Chứng minh của bài toán chỉ ra
một cách tô màu dường như tốt, hiệu quả. Đó là vì với k lớn, nếu n = b2k/2c
thì (
n
k
)
.21−(
k
2) <
21+k/2
k!
.(
n
2k/2
)k ≤ 2
1+k/2
k!
 1.
Thế nên, một cách tô màu bất kỳ của Kn dường như không chứa đơn màu
K2 log2 n. Điều đó có nghĩa là, vì một lý do nào đó, chúng ta phải giới thiệu
một cách tô hai màu cho các cạnh của K1024 mà không chứa đơn màu K20
nào, chúng ta có thể đơn giản tạo một cách tô màu ngẫu nhiên bằng cách tung
đồng xu hai mặt
(1024
2
)
lần. Chúng ta sẽ nhận được một cách tô màu đáng tin:
xác suất để có một đơn màu K20 nhỏ hơn
211
20! . Do đó, trong một vài trường
hợp, phương pháp xác suất không xây dựng đưa ra một giải thuật hiệu quả.
23
Phương pháp xác suất là một công cụ mạnh và hiệu quả của lý thuyết Đồ
thị và Tổ hợp. Nó cũng là ứng dụng hàng đầu trong Lý thuyết Số và trong Hình
học Tổ hợp. Gần đây nó được ứng dụng nhiều hơn trong việc phát triển kĩ thuật
giải thuật hiệu quả và trong việc tìm hiểu những bài toán máy tính khác nhau.
2.2 Lý thuyết Đồ thị
Một giải đấu trên tập V của n người chơi là một sự định hướng T = (V,E)
của các cạnh của đồ thị đầy đủ trên tập n đỉnh của V . Vì vậy, với mọi hai phần
tử x, y của V thì hay (x, y) thuộc E, hay (y, x) thuộc E nhưng không cả
hai. Cái tên "giải đấu" là tự nhiên, vì mỗi cặp tham gia đấu tay đôi và (x, y)
thuộc E nếu x thắng y.
Chúng ta nói T có tính chất Sk nếu mỗi tập k người chơi có một người (của
V ) đánh bại tất cả k người này. Ví dụ, tam giác liên thông T3 = (V,E), ở
đây V = {1, 2, 3} và E = {(1, 2), (2, 3), (3, 1)} có tính chất S1. Liệu
rằng mỗi số nguyên k sẽ có giải đấu T (nhiều hơn k người chơi) có tính chất
Sk? ý tưởng cơ bản (và tự nhiên) là nếu n đủ lớn như một hàm của k thì giải
đấu ngẫu nhiên trên tập n người chơi của V sẽ có tính chất Sk.Một giải đấu
ngẫu nhiên là như sau. Chúng ta đưa ra một giải đấu T trên V bằng cách chọn,
với mỗi 1 ≤ i < j ≤ n, hay cạnh (i, j) hay cạnh (j, i), ở đây mỗi một
trong hai cách chọn là tương đương. Giả sử rằng theo cách này, mỗi một trong
các giải đấu trên V là bình đẳng, không gian xác suất được xét là đối xứng.
Rất đáng chú ý rằng chúng ta thường dùng trong ứng dụng những không gian
xác suất đối xứng. Trong trường hợp này, chúng ta đôi khi coi những phần tử
của không gian như những phần tử ngẫu nhiên, mà không mô tả cụ thể phân
phối xác suất. Vì vậy, ví dụ, trong chứng minh của Mệnh đề 2.1.1, những cách
tô hai màu củaKn được xét thì mỗi cách tô màu là bình đẳng với nhau. Tương
tự, trong chứng minh của kết quả đơn giản sau đây chúng ta tìm hiểu về giải
đấu ngẫu nhiên trên V .
Định lý 2.2.1 Nếu
(n
k
)
(1 − 2−k)n−k < 1 thì có một giải đấu n đỉnh có tính
chất Sk.
Chứng minh. Xét một giải đấu ngẫu nhiên của tập V = {1, 2, . . . , n}.
24
Với mỗi tập conK cố định có k đỉnh của V , đặtAK là sự kiện không có đỉnh
nào đánh bại mọi thành viên củaK. Rõ ràng Pr(AK) = (1−2−k)n−k. Đây
là vì mỗi đỉnh cố định v ∈ V −K, xác suất để v không đánh bại mọi thành
viên của K là 1− 2−k, và tất cả n− k cách chọn khác nhau có thể của v là
độc lập. Kéo theo
Pr(
∨
K⊂V
|K|=k
AK) ≤
∑
K⊂V
|K|=k
Pr(AK) =
(
n
k
)
(1− 2−k)n−k < 1.
Từ đó, với xác suất dương không sự kiện AK nào xảy ra, tức là có một giải
đấu n đỉnh có tính chất Sk.
Gọi f(k) kí hiệu số nhỏ nhất có thể của các đỉnh của giải đấu mà có tính
chất Sk. Do
(n
k
)
< (en
k
)k và (1 − 2−k)n−k < e−(n−k)/2k, Định lý 1.2.1
chứng tỏ rằng f(k) ≤ k22k(ln 2)(1 +o(1)). Không khó khăn kiểm tra rằng
f(1) = 3 và f(2) = 7. Theo chứng minh của Szekeres, f(k) ≥ c1k2k. 
Một tập trội của đồ thị không liên thông G = (V,E) là tập U ⊆ V sao
cho mọi v ∈ V − U có ít nhất một đỉnh kề trong U .
Định lý 2.2.2 Cho G = (V,E) là đồ thị n đỉnh, bậc nhỏ nhất δ > 1. Thế thì
G có tập trội với nhiều nhất n1+ln(δ+1)
δ+1 đỉnh.
Chứng minh. Lấy p ∈ [0, 1] là số tuỳ ý. Chọn một cách ngẫu nhiên và
độc lập mỗi đỉnh của V với xác suất p . Lấy X là tập (ngẫu nhiên) tất cả
các đỉnh được chọn và đặt Y = YX là tập mà mọi đỉnh thuộc V − X mà
không có đỉnh kề trongX . Giá trị kỳ vọng củaX rõ ràng là np. Với mỗi đỉnh
v ∈ V,Pr(v ∈ Y ) = Pr(v và các đỉnh kề không trongX) ≤ (1− p)δ+1.
Do kỳ vọng của tổng các biến ngẫu nhiên bằng tổng các kỳ vọng (thậm chí
nếu chúng không độc lập) và do biến ngẫu nhiên |Y | có thể viết như tổng
các biến ngẫu nhiên chỉ số χv(v ∈ V ), với χv = 1 nếu v ∈ V và
χv = 0 nếu khác, chúng ta kết luận rằng kì vọng của |X| + |Y | nhiều
nhất là np+n(1− p)δ+1. Suy ra, có ít nhất một cách chọn củaX ⊆ V sao
cho |X| + |YX| ≤ np + n(1 − p)δ+1. Tập U = X ∪ YX rõ ràng là tập
trội mà lực lượng của nó nhiều nhất là số này.
Các lập luận trên đúng với p ∈ [0, 1] tuỳ ý. Để nhận kết quả chúng ta
25
dùng tính toán sơ cấp. Để tiện ta đánh giá 1 − p ≤ e−p (điều này đúng mọi
p không âm và xấp xỉ tốt khi p nhỏ) để có đánh giá đơn giản hơn |U | ≤
np+ ne−p(δ+1).
Lấy đạo hàm về phải theo p và cho bằng không, giá trị nhỏ nhất của vế phải
đạt tại p = ln(δ + 1)/(δ + 1).
Lấy p là giá trị này trong dòng đầu của chứng minh, ta có |U | ≤ n1+ln(δ+1)
δ+1
như đã nêu. 
Ba ý tưởng đơn giản nhưng quan trọng được thể hiện trong chứng minh cuối.
Thứ nhất là sự tuy

---