6 trang 1 lượt tải

Nội Dung Ôn Tập Toán Rời Rạc | Đại học Kinh tế kỹ thuật công nghiệp

2

Có bao nhiêu cách khác nhau để sắp xếp 5 bạn Amy, Bella, Cindy, Darcy và Ellen  thành một hàng sao cho bạn Amy không được đứng đầu hàng hoặc cuối hàng? Dùng thuật toán Dijkstra tìm đường đi ngắn nhất từ đỉnh a đến các đỉnh còn lại trong đồ thị. Tài liệu giúp bạn tham khảo, ôn tập và đạt kết quả cao. Mời đọc đón xem!

Môn: Toán rời rạc (KTKTCN) 4 tài liệu

Trường: Đại học Kinh tế kỹ thuật công nghiệp 1.1 K tài liệu

Tác giả:

Profile

Mỹ Châu

3 giờ trước
Danh sách Quiz
/6
lOMoARcPSD| 45315597
MỘT SỐ NỘI DUNG ÔN TẬP HỌC PHẦN TOÁN RỜI RẠC
Bài 1
Câu 1:
Có bao nhiêu cách khác nhau ể sắp xếp 5 bạn Amy, Bella, Cindy, Darcy và
Ellen thành một hàng sao cho bạn Amy không ược ứng ầu hàng hoặc cuối hàng?
Câu 2 :
Áp dụng thuật toán nhánh cận giải bài toán cái túi sau:
5x
1
+ x
2
+ 9 x
3
-> max,
4 x
1
+ 2 x
2
+ 6 x
3
≤ 10, Với x
j
>=0 nguyên, j = 1,2,3 Câu 3:
Cho ồ thị sau:
Tìm cây khung nhỏ nhất của ồ thị theo thuật toán Prim
Câu 4: Cho ồ thị sau
lOMoARcPSD| 45315597
1. Duyệt ồ thị trên theo phương pháp Duyệt theo chiều rộng - DFS
2. Dùng thuật toán Dijkstra m ường i ngắn nhất từ ỉnh a ến các ỉnh còn lại
trong ồ thị.
4
4
3
2
2
1
2
7
5
4
3
7
5
lOMoARcPSD| 45315597
Bài 2
Câu 1:
Chọn 4 chữ số, không lặp lại, từ 0, 2, 6, 5, 7, 9 ể tạo thành số có 4 chữ số. Trong
các số có 4 chữ số ó, có bao nhiêu số lẻ?
Câu 2:
Áp dụng thuật toán nhánh cận ể giải bài toán cái túi sau ây, chỉ rõ kết quả mỗi
bước:
9x
1
+ 3x
2
+ x
3
+ 2x
4
->
max 7x
1
+ 2x
2
+ x
3
+ 4x
4
≤ 8
x
1
, x
2
, x
3
, x
4
là các số nguyên nhận giá trị 0 hoặc 1
Câu 3:
Cho ồ thị sau:
Tìm cây khung nhỏ nhất của ồ thị theo thuật toán Prim
Câu 4:
Cho ơn ồ thị sau:
lOMoARcPSD| 45315597
1. Duyệt ồ thị trên theo phương pháp Duyệt theo chiều rộng - DFS
2. Dùng thuật toán Dijkstra m ường i ngắn nhất từ ỉnh a ến các ỉnh còn lại
trong ồ thị.
lOMoARcPSD| 45315597
Bài 3
Câu 1:
Giải các hệ thức truy hồi với các iều kiện ầu sau:
a
n
= 7a
n-1
- 6a
n-2
với n ≥ 2, a
0
= 2, a
1
= 1.
Câu 2 :
Cho thời gian gia công các chi ết trên 2 máy A và B trong bảng sau. Hãy lập lịch gia
công cho các chi ết này sao cho thời gian gia công là ít nhất. Vẽ sơ ồ Gan cho lịch
gia công tối ưu.
Câu 3:
Cho ơn ồ thị sau:
1. Định nghĩa ồ thị Euler.
2. Đồ thị trên có chu trình Euler không? Vì sao? Nếu có hãy m chu trình
Euler ó?
9
1
2
3
6
8
4
5
7
lOMoARcPSD| 45315597
Câu 4:
Cho ơn ồ thị sau:
1. Duyệt ồ thị trên theo phương pháp Duyệt theo chiều rộng - DFS
2. Dùng thuật toán Dijkstra m ường i ngắn nhất từ ỉnh a ến các ỉnh còn lại
trong ồ thị.

Tài liệu khác của Đại học Kinh tế kỹ thuật công nghiệp

Preview text:

lOMoAR cPSD| 45315597
MỘT SỐ NỘI DUNG ÔN TẬP HỌC PHẦN TOÁN RỜI RẠC Bài 1 Câu 1:
Có bao nhiêu cách khác nhau ể sắp xếp 5 bạn Amy, Bella, Cindy, Darcy và
Ellen thành một hàng sao cho bạn Amy không ược ứng ầu hàng hoặc cuối hàng? Câu 2 :
Áp dụng thuật toán nhánh cận giải bài toán cái túi sau: 5x1 + x2 + 9 x3 -> max,
4 x1 + 2 x2 + 6 x3 ≤ 10, Với xj
>=0 nguyên, j = 1,2,3 Câu 3: Cho ồ thị sau:
Tìm cây khung nhỏ nhất của ồ thị theo thuật toán Prim Câu 4: Cho ồ thị sau lOMoAR cPSD| 45315597 4 2 2 3 7 4 1 5 4 3 5 2 7 10
1. Duyệt ồ thị trên theo phương pháp Duyệt theo chiều rộng - DFS
2. Dùng thuật toán Dijkstra tìm ường i ngắn nhất từ ỉnh a ến các ỉnh còn lại trong ồ thị. lOMoAR cPSD| 45315597 Bài 2 Câu 1:
Chọn 4 chữ số, không lặp lại, từ 0, 2, 6, 5, 7, 9 ể tạo thành số có 4 chữ số. Trong
các số có 4 chữ số ó, có bao nhiêu số lẻ? Câu 2:
Áp dụng thuật toán nhánh cận ể giải bài toán cái túi sau ây, chỉ rõ kết quả mỗi bước: 9x1 + 3x2 + x3 + 2x4 -> max 7x1 + 2x2 + x3 + 4x4 ≤ 8
x1, x2, x3, x4 là các số nguyên nhận giá trị 0 hoặc 1 Câu 3: Cho ồ thị sau:
Tìm cây khung nhỏ nhất của ồ thị theo thuật toán Prim Câu 4: Cho ơn ồ thị sau: lOMoAR cPSD| 45315597
1. Duyệt ồ thị trên theo phương pháp Duyệt theo chiều rộng - DFS
2. Dùng thuật toán Dijkstra tìm ường i ngắn nhất từ ỉnh a ến các ỉnh còn lại trong ồ thị. lOMoAR cPSD| 45315597 Bài 3 Câu 1:
Giải các hệ thức truy hồi với các iều kiện ầu sau: an = 7an-1 - 6an-2
với n ≥ 2, a0 = 2, a1 = 1. Câu 2 :
Cho thời gian gia công các chi tiết trên 2 máy A và B trong bảng sau. Hãy lập lịch gia
công cho các chi tiết này sao cho thời gian gia công là ít nhất. Vẽ sơ ồ Gantt cho lịch gia công tối ưu. Câu 3: Cho ơn ồ thị sau: 9 1 2 3 4 6 5 7 8
1. Định nghĩa ồ thị Euler.
2. Đồ thị trên có chu trình Euler không? Vì sao? Nếu có hãy tìm chu trình Euler ó? lOMoAR cPSD| 45315597 Câu 4: Cho ơn ồ thị sau:
1. Duyệt ồ thị trên theo phương pháp Duyệt theo chiều rộng - DFS
2. Dùng thuật toán Dijkstra tìm ường i ngắn nhất từ ỉnh a ến các ỉnh còn lại trong ồ thị.

Tài liệu liên quan: