Tài liệu Công Nghệ Thông Tin

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: 438 | 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: 407 | 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: 375 | 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: 418 | 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: 353 | 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: 419 | Lượt tải: 0

Muốn thực hiện việc tạo bảng danh biểu cho chương trình con bị gọi, ta phải tạo các hàm như sau: 1. mktable (x) 2. enter (table, name, type, offset) 3. addwidth (table, width) 4. enterproc (table, name, newtable

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

1. Thông số nhập – xuất - Truyền bằng tham khảo - Truyền bằng trị2. Thông số chỉ nhập - Truyền bằng trị - Truyền bằng trị hằng 3. Thông số chỉ xuất - Truyền thông số bằng tên

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

3. Sự tương đương của biểu thức kiểu • Sự tương đương cấu trúc của biểu thức kiểu • Giải thuật kiểm tra tương đương cấu trúc của các biểu thức kiểu

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

Với mỗi luật sinh A Ỉ X1 Xn, sẽ có n ký hiệu không kết thúc đánh dấu M1 Mn, sẽ thay luật trên thành luật sinh A Ỉ M1X1 MnXn. Để nhận thấy các thuộc tính có thể được tính trong quá trình phân tích từ dưới lên, hãy xét hai trường hợp. Trường hợp thứ nhất nếu ta thu giảm về ký hiệu Mj ta phải biết luật sinh A → Mj X1 MnXn mà Mj có trong đó. Chúng...

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