Tài liệu Khoa Học Tự Nhiên

Bài 5 Mục đích của bài tập này là kiểm tra xem những đặc tả sau đây có thỏa được không: 1. Nếu hệ thống file không bị khóa, thì (a) các thông điệp mới sẽ được đặt trong hàng đợi. (b) các thông điệp mới sẽ được gửi tới bộ đệm thông điệp. (c) hệ thống đang hoạt động bình thường, và ngược lại, nếu hệ thông đang hoạt động bình thường, thì hệ thốn...

2 trang | Chia sẻ: hachi492 | Ngày: 08/01/2022 | Lượt xem: 676 | Lượt tải: 0

Bài 3 Với n = 40 giá trị của đa thức p(n) ::= n2 + n + 41 không phải là số nguyên tố. Ta dự đoán rằng, ngoại trừ các đa thức hằng số, không có đa thức nào chỉ sinh ra các giá trị là các số nguyên tố. Cụ thể, xét đa thức q(n) với hệ số nguyên dương, và xét c ::= q(0) là số hạng hằng số của q(n). (a) Chứng minh rằng q(cm) là bội của c với mọi m...

1 trang | Chia sẻ: hachi492 | Ngày: 08/01/2022 | Lượt xem: 752 | Lượt tải: 0

Algorithm 1: Thuật toán Gale-Shapley Khởi tạo mọi chàng trai m 2 M và mọi cô gái w 2 W là độc thân; while có một chàng trai m độc thân và vẫn chưa đính hôn với cô gái nào do Chọn chàng trai m này; Xét w là cô gái m thích nhất trong danh sách những cô mà m chưa đề nghị cưới; if w là độc thân then (m; w) đính hôn; else /* w hiện tại đang đính ...

3 trang | Chia sẻ: hachi492 | Ngày: 08/01/2022 | Lượt xem: 954 | Lượt tải: 0

Tìm đường tăng function FoundIncPath: boolean; var dq, cq, v, w: integer; begin fillchar(q,sizeof(q),0); dq:=1; cq:=1; queue[dq]:=u; q[u]:=u; while dq<=cq do begin v:=queue[dq]; inc(dq); if v<=n then begin for w:=n+1 to n2 do if (f[v]+f[w]=c(v,w-n)) and (q[w]=0) then begin inc(cq); queue[cq]:=w; q[w]:=v; end; end else if...

43 trang | Chia sẻ: hachi492 | Ngày: 08/01/2022 | Lượt xem: 749 | Lượt tải: 0

Đường tăng ngắn nhất: Các kết quả 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. 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. Đị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). O(m+n) thời gian để tìm đường ngắn nhất nhờ sử dụng BFS. O(...

83 trang | Chia sẻ: hachi492 | Ngày: 08/01/2022 | Lượt xem: 1047 | Lượt tải: 0

Bài toán Cho đồ thị G = (V, E), với trọng số trên cạnh e là w(e), đối với mỗi cặp đỉnh u, v trong V, tìm đường đi ngắn nhất từ u đến v. Đầu vào: ma trận trọng số. Đầu ra ma trận: phần tử ở dòng u cột v là độ dài đường đi ngắn nhất từ u đến v. Cho phép có trọng số âm Giả thiết: Đồ thị không có chu trình âm.

78 trang | Chia sẻ: hachi492 | Ngày: 08/01/2022 | Lượt xem: 1161 | Lượt tải: 0

Mô tả thuật toán Prim procedure Prim(G, c) begin Chọn đỉnh tuỳ ý r V; Khởi tạo cây T=(V(T), E(T)) với V(T)={ r }và E(T)=; while T có < n đỉnh do begin Gọi (u, v) là cạnh nhẹ nhất với u  V(T) và vV(G) – V(T) E(T)  E(T)  { (u, v) }; V(T)  V(T)  { v } end end; Tính đúng đắn suy từ hệ quả đã chứng minh: Giả sử A là tập co...

60 trang | Chia sẻ: hachi492 | Ngày: 08/01/2022 | Lượt xem: 1016 | Lượt tải: 0

Finding Sweden Tour The Concorde solver can accept as an input parameter the value of the best known tour for a TSP instance if one is available.  As a full (exact) TSP solver, Concorde is designed to find optimal solutions regardless of the quality of the estimate, but knowledge of a good tour allows for better tuning of parameters that are set i...

93 trang | Chia sẻ: hachi492 | Ngày: 08/01/2022 | Lượt xem: 911 | Lượt tải: 0

Hàm nhận biết ứng cử viên int UCVh(int j, int k) { // UCVh nhận giá trị 1 // khi và chỉ khi j  Sk int i; for (i=1; i

142 trang | Chia sẻ: hachi492 | Ngày: 08/01/2022 | Lượt xem: 776 | Lượt tải: 0

Cỏc số Ramsey Xét một cách tô màu (tuỳ ý) các cạnh của K7. Rõ ràng hoặc là tìm đợc ít nhất một cạnh của K7 đợc tô màu đỏ, hoặc là tất cả các cạnh của nó đều đợc tô bởi màu xanh. Nếu có cạnh tô màu đỏ thì rõ ràng ta có K2 đỏ. Còn nếu tất cả các cạnh đều tô bởi màu xanh thì ta có K7 xanh. Vậy số 7 có tính chất (2,7)-Ramsey, và vì thế R(2,7) ? 7. Nh...

108 trang | Chia sẻ: hachi492 | Ngày: 08/01/2022 | Lượt xem: 658 | Lượt tải: 0