Thư viện tài liệu, ebook tham khảo dành cho học sinh, sinh viên

Các số R(i,j) vừa trình bày ở trên chỉ là một trong số nhiều dòng số Ramsey đã được nghiên cứu. Việc xác định R(i,j) với những giá trị i, j cụ thể luôn là các bài toán tổ hợp không tầm thường. Hiện nay người ta mới biết giá trị của R(i, j) với rất ít giá trị của (i,j).

108 trang | Chia sẻ: huongthu9 | Ngày: 18/08/2021 | Lượt xem: 1025 | Lượt tải: 0

Các tính chất cơ bản sau đây của số Ramsey R(i,j) có thể chứng minh bằng các lập luận tơng tự nh trong các ví dụ đã trình bày: R(i,j) = R(j,i); Nếu m có tính chất (i,j)-Ramsey, thì mọi số n > m cũng có tính chất này; Nếu m không có tính chất (i,j)-Ramsey, thì mọi số n < m cũng không có tính chất này; Nếu i1 ? i2 thì R(i1,j) ? R(i2,j).

103 trang | Chia sẻ: huongthu9 | Ngày: 18/08/2021 | Lượt xem: 927 | Lượt tải: 0

If the extra terms F(n) are a degree-t polynomial in n, you should try a general degree-t polynomial as the particular solution p(n). This case: F(n) is linear so try an = cn + d. cn+d = 3(c(n−1)+d) + 2n (for all n) (2c+2)n + (2d−3c) = 0 (collect terms) So c = −1 and d = −3/2. So an = −n − 3/2 is a solution. Check: an≥1 = {−5/2, −7/2, −9...

178 trang | Chia sẻ: huongthu9 | Ngày: 18/08/2021 | Lượt xem: 751 | Lượt tải: 0

Hỏi có bao nhiêu số có 5 chữ số mà mỗi chữ số đứng sau lại lớn hơn chữ số đứng trước? Giải: Mỗi một số cần đếm tương ứng với một cách chọn ra 5 chữ số từ 9 chữ số 1, 2, ., 9, và ngược lại mỗi một cách lấy ra 5 chữ số từ 1, 2, ., 9 sau khi sắp xếp theo thứ tự tăng dần cho ta đúng một số cần đếm. Vậy số lượng số cần đếm là C(9, 5). Lập luận tương t...

91 trang | Chia sẻ: huongthu9 | Ngày: 18/08/2021 | Lượt xem: 906 | Lượt tải: 0

Bổ đề 1. Trong suốt thuật toán, độ dài đường tăng ngắn nhất không khi nào bị giảm. CM sau. Bổ đề 2. Sau nhiều nhất m đường tăng ngắn nhất, độ dài đường tăng ngắn nhất sẽ tăng ngặt. CM sau. Định lý. Thuật toán đường tăng luồng ngắn nhất đòi hỏi thời gian tính O(m2n). CM O(m+n) thời gian để tìm đường ngắn nhất nhờ sử dụng BFS. O(m) lần tăng đố...

83 trang | Chia sẻ: huongthu9 | Ngày: 18/08/2021 | Lượt xem: 1180 | Lượt tải: 0

1935 – 2006 Proving the correctness of the transitive closure algorithm for boolean circuit. (Wikipedia) There is an interesting anecdote about his proof that the transitive closure algorithm, now known as Warshall's algorithm, is correct. He and a colleague at Technical Operations bet a bottle of rum on who first could determine whether this al...

78 trang | Chia sẻ: huongthu9 | Ngày: 18/08/2021 | Lượt xem: 929 | Lượt tải: 1

Nhà khoa học Séc (Czech) Người đề xuất bài toán Đề xuất thuật toán thời gian O(m log n) Bài báo được xuất bản ở Séc từ năm 1926. Ứng dụng vào việc phát triển hệ thống mạng điện ở Bohemia.

60 trang | Chia sẻ: huongthu9 | Ngày: 18/08/2021 | Lượt xem: 780 | Lượt tải: 0

Bài toán: Cho đồ thị vô hớng liên thông G= (V, E). Hãy tìm cách định hớng các cạnh của nó để thu đợc đồ thị có hớng liên thông mạnh hoặc trả lời G là không định hớng đợc. Thuật toán định hớng ?: Trong quá trình thực hiện DFS(G) định hớng các cạnh của cây DFS theo chiều từ tổ tiên đến con cháu, các cạnh ngợc theo hớng từ con cháu đến tổ tiên. Ký hi...

275 trang | Chia sẻ: huongthu9 | Ngày: 18/08/2021 | Lượt xem: 937 | Lượt tải: 0

10.5. Tối ưu vòng lặp Trong phần này chúng ta sẽ trình bày giải thuật tối ưu vòng lặp là strength reduction. Mục đích của giải thuật này là thay thế các câu lệnh đắt tiền bằng câu lệnh rẻ tiền hơn. 10.5.1. Biến thay đổi (Induction variable) Biến thay đổi trong vòng lặp L là x nếu mỗi lần thay đổi nó tăng hoặc giảm một hằng số nhất định. 10.5...

53 trang | Chia sẻ: huongthu9 | Ngày: 18/08/2021 | Lượt xem: 751 | Lượt tải: 0

if n là lá bên trái biểu thị cho toán hạng name and n là con tận cùng bên trái của nút cha của nó then print ‘MOV’ || name || ‘,’ || top (rstack) else if n là nút trung gian với toán tử là op, con bên trái là n1 và con bên phải là n2 then /* trường hợp thứ nhất */ if label (n2) = 0 then begin đặt name là toán hạng được biểu thị bằng n2. genc...

44 trang | Chia sẻ: huongthu9 | Ngày: 18/08/2021 | Lượt xem: 870 | Lượt tải: 0