TAILIEUCHUNG - Toán rời rạc part 6

Tham khảo tài liệu 'toán rời rạc part 6', khoa học tự nhiên, toán học phục vụ nhu cầu học tập, nghiên cứu và làm việc hiệu quả | Phẩn ỉ. Lý thuyết tíỉ hợp IXị-t- 6-X2 4jr3 _r4 26 Xj 0 nguyên 1 2 3 4. Quá trình thực hiện thuật toán mô tả trên cây tìm kiếm lời giải. 3. Mô tả thuật toán quay lui dể giải bài toán sau Cho n số nguyên dương ứ 2 Tìm các sô í e -1 1 i - 1 2 n sao cho Í 1 là nhỏ nhất. 4. Bất đẳng thức sau đây có tên là bất đẳng thức hoán vị được sử dụng trong việc phát triển thuật toán giải nhiều bài toán lập lịch Cho hai dãy số thực at và bị b2 . ủ trong đó bị b2 . bn. Giả sử ơ 1 ơ 2 . ơ fl và y 1 y 2 .y n là các hoán vị của các số 1 thoả mãn ơi tl - ữơ l - ữ r 2 - - ứơ n Khi đó bất đảng thức ẺMí ỉ b i l i l l được thực hiện với mọi hoán vị 7i 1 71 2 .TtỌi của các số 1 2 . n. Như là ví dụ ứng dụng xét bài toán lạp lịch sau đây Có n khách hàng đến thuê thực hiện chương trình trên máy tính song song tại trung tâm máy tính hiệu năng cao. Biết rang thời gian cần thiết để chạy xong chương trình của khách hàng i là tị i 1 2 . n. Giả thiết là thời gian để máy chuyển từ việc thực hiện chương trình này sang thực hiên chương trình khác là bằng 0 hây tìm trình tự thực hiện các chương trình sao cho tổng thời gian chờ đợi của tắt cả n khách hàng là nhỏ nhất. Sử dụng bất đẳng thức hoán vị để chỉ ra rằng trình tự cần tìm là trình tự không giảm của thời gian thực hiện cấc chương trình. 144 20-TRR PHẦN II LÝ THUYẾT ĐỔ THỊ Phần 2 Lý thuyết đổ thị các máy tính và các kênh điện thoại gọi tất ỉà kênh thoại nối các máy tính này. Chúng ta có thể biểu diễn các vị trí đặt máy tính bởi các điểm và các kênh thoại nối chúng bởi các đoạn nối xem hình 1. Hình 1 Sơ đồ mạng máy tính Nhận thấy rằng trong mạng ở hình 1 giữa hai máy bất kỳ chỉ có nhiều nhất là một kênh thoại nối chúng kênh thoại này cho phép liên lạc cả hai chiều và không có máy tính nào lại được nối với chính nó. Sơ đổ mạng máy tính cho ưong hình ỉ được gọi là đơn đồ thị vô hướng. Ta đi đến định nghĩa sau Định nghĩa 1. Đơn đồ thị vổ hướng G V . bao gồm V là tập các đỉnh và E là tập các cặp không có thứ tự gồm hai phần tử khác nhau của V gọi

• Toán học
• Toán rời rạc
• tài liệu Toán rời rạc
• giáo trình Toán rời rạc
• bài giảng Toán rời rạc
• tìm hiểu Toán rời rạc
• Học toán rời rạc
• Lý thuyết về toán rời rạc
• Bài tập về toán rời rạc
• Ôn tập toán rời rạc
• Đề thi toán rời rạc