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

Trong ví dụ trên, sau một vài bước, mọi sinh viên trong lớp sẽ bị nhiễm cúm. Hãy chứng minh định lý sau đây. Định lý. Nếu tại thời điểm ban đầu trong lớp có ít hơn n sinh viên bị nhiễm cúm, thì không bao giờ xảy ra việc cả lớp đều bị nhiễm cúm. Gợi ý: Để hiểu hệ thống kiểu như trên “tiến triển" thế nào theo thời gian, một chiến lược là 1. xác ...

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

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: 308 | 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: 375 | 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: 386 | 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: 292 | 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: 420 | 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: 543 | 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: 345 | 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: 350 | 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: 285 | Lượt tải: 0