TAILIEUCHUNG - Giáo trình cấu trúc dữ liệu và giải thuât part 9

Tham khảo tài liệu 'giáo trình cấu trúc dữ liệu và giải thuât part 9', công nghệ thông tin, cơ sở dữ liệu phục vụ nhu cầu học tập, nghiên cứu và làm việc hiệu quả | . Một đội thợ phải thực hiện lẩn lượt 6 công việc khác nhau. Các công việc này được đánh số từ 1 đến 6 và giữa chúng có quan hê làm trước kí hiệu bỏi dấu . Biết rằng 1 2 2 3 2 5 4 2 4 6 6 3 6 5 a Hãy biểu diễn tập các công việc này với quan hê đã nêu trên bằng một đồ thị định hướng. Vẽ đồ thị đó. b Minh họa dạng của đổ thị với các đỉnh được xét trong quá trình sắp xếp tô pô theo quy tắc chung. Nêu cụ thể 2 thứ tự tò pô khác nhau. c Nêu áp dụng giải thuật TOPO - ORDER thì đồ thị nêu ở câu a được cài đặt trong máy có dạng như thế nào trước khi thực hiện giải thuật. d Sau khi thực hiện giải thuật TOPO - ORDER thì thứ tự Tôpô nhận được có dạng thể nào . Một tập s gồm 7 công việc được đánh số từ 1 đến 7 với quan hệ làm trước thỏa mãn các điều kiện sau 7 5 3 6 2 1 4 2 5 3 5 6 2 6 a Hãy vẽ đồ thị biểu diễn s. b Hãy minh họa cấu trúc lưu trữ của đồ thị đó trước khi thực hiện giải thuật TOPO - ORDER. c Nêu kết quả sau khi thực hiện giải thuật TOPO - ORDER. 128 HƯỚNG DÃN GIẢI bai TÂP ở đây sẽ nêu lên phần hướng dẫn giải hoặc lời giải cũa một số bài tập trong từng chương. CHƯƠNG 1 . Giải thuật mà độ phức tạp về thời gian của nó là 0 1 nếu thời gian thực hiện nó chỉ bằng một hằng số. Ví dụ giải thuật tính và in X2 Program BINH - PHUONG Read X Y X X write Y retu rn . a T n n3 100 nlog2n 5000 Ta thấy nếu n 32 thì n3 32768 log2n 5 100 nlog2n 16000 n3 Do đó T n n3 n3 n3 3n3 nếu n 32. Rõ ràng tồn tại một hằng sô c 3 và một giá trị n0 32 để khi n n0 ta luôn có T n Cn3 Vậy ta có thể viết T n O n3 Tương tự ta cũng xác nhận được b T n O 2n c T n O n2 d T n O log2n . . a Ta chọn phép toán A ij B i j C i j làm phép tích cực. Với mỗi giá trị của i phép này đểu thực hiện n lần mà i lấy giá trị từ 1 đến n nên phép toán trên thực hiện tổng cộng n X n lẩn. o gtdl vgt 129 Do đó có thể viết T n Cn2 hay T- n O n2 b T2 n O n c T3 n O n3 d T4 n O n . . a Tiêu chuẩn gốc ỏ đây là m 0 nểu m 0 thì Acker m n n 1 b Ta có Acker 1 3 Acker 0 Acker 1. 2 mà Acker 1 2 Acker 0 Acker 1 1 .

• Cơ sở dữ liệu
• cấu trúc dữ liệu và giải thuât
• bài giảng cấu trúc dữ liệu và giải thuât
• tài liệu cấu trúc dữ liệu và giải thuât
• giáo trình cấu trúc dữ liệu và giải thuât
• bài tập cấu trúc dữ liệu và giải thuât
• phân tích thiết kế
• thiết kế hướng đối tượng
• Data Structures and Algorithms