Vài Phút Quảng Cáo Sản Phẩm
Mọi ý kiến đóng góp xin gửi vào hòm thư: [email protected]
Tổng hợp các đề cương đại học hiện có của Đại Học Hàng Hải: Đề Cương VIMARU
Kéo xuống để Tải ngay đề cương bản PDF đầy đủ: Sau “mục lục” và “bản xem trước”
(Nếu là đề cương nhiều công thức nên mọi người nên tải về để xem tránh mất công thức)
Đề cương liên quan:BÀI TẬP LỚN THỦY VĂN
Mục Lục
Tải ngay đề cương bản PDF tại đây: Bài tập lớn toán rời rạc
BÀI TẬP LỚN
Môn: Toán rời rạc
Lớp: Công nghệ thông tin 15 (BTLTĐ)
I. Yêu cầu:
1. Trình bày:
- Câu 1, câu 3, câu 4.B, câu 4.C : trình bày trong file word (giấy khổ A4,
phông chữ: Times new roman 14, công thức toán học viết bằng Equation hoặc MathType). Ghi tên file là baitap<STT>.doc.
- Câu 2, câu 4.A: sinh viên sử dụng một ngôn ngữ lập trình để thực hiện.
Chương trình để trong thư mục chuongtrinh<STT>.
- Tất cả ghi lại trong thư mục <STT><Họ tên>.
VD: 1. Nguyễn Thị Vân Anh => Bài làm lưu trong thư mục 1.NguyenThiVanAnh gồm file baitap1.doc và thư mục chuongtrinh1.
- Cách thức và thời gian nộp bài:
Lớp trưởng tập hợp bài của tất cả sinh viên vào đĩa CD nộp cho giáo viên trước ngày
II. Nội dung bài tập:
Câu 1. Sử dụng phương pháp quy nạp, chứng minh:
- Giả sử rằng: A = é a 0ù Trong đó a và b là các số thực. Chứng minh rằng:
êë 0 búû
| é a n | 0 ù | ||
| An = ê | 0 | b | n ú |
| ë | û | ||
- Giả sử A và B là các ma trận vuông thỏa mãn: AB = BA. Chỉ ra rằng ABn = BnA với n là số nguyên dương tùy ý.
- Chứng minh công thức Demorgan tổng quát:
| æ | n | ö | = | n | (X \ Ai ) |
| X \ ç | Ai ÷ | ||||
| è i =1 | ø | i=1 | |||
n
- Với n nguyên dương chứng minh: n! ≤ n
- Với n nguyên dương chứng minh: 1 + 1/4 + 1/9 + … + 1/n2 < 2 – 1/n
Câu 2.
- Viết chương trình minh họa:
- Giải thuật quay lui để liệt kê tất cả xâu nhị phân có độ dài n.
- Giải thuật quay lui để liệt kê tất cả hoán vị của tập A = {1,2,..,n}.
- Giải thuật quay lui để liệt kê tất cả các tổ hợp chập k của n phần tử.
- Viết chương trình minh họa:
- Liệt kê tất cả các xâu nhị phân có độ dài n sử dụng phương pháp sinh.
- Liệt kê tất cả hoán vị của tập A = {1,2,..,n} sử dụng phương pháp sinh.
- Liệt kê tất cả các tổ hợp chập k của n phần tử sử dụng phương pháp sinh.
Câu 3. Tìm dạng tuyển chuẩn tắc tối thiểu của các hàm:
- f (x , y , z ) = x ® ( y ® z ) + éë ( x + z ) ® ( y + z )ùû
- f (x , y , z ) = ( x + y ). (x ® z ).(x + z )
- f (x , y , z ) = x. z. ( y + t ) + x.t . (y + z )+ x. (y . z + y .t )
- f (x , y , z ) = x. z. (y + t )+ x. y . z + x. (y .t + z .t )
- Viết chương trình minh họa
- Thuật toán Kruskal tìm cây khung tối thiểu của một đồ thị.
- Thuật toán Dijkstra tìm đường đi ngắn nhất giữa hai đỉnh bất kỳ của một đồ thị.
- Thuật toán Prim tìm cây khung tối thiểu của một đồ thị.
- Thuật toán tìm chu trình Euler của một đồ thị.
- Thuật toán tìm đường đi Hamilton của một đồ thị.
- Thuật toán tìm đường đi Euler của một đồ thị.
- Thuật toán tìm chu trình Hamilton của một đồ thị.
- Thuật toán đếm số thành phần liên thông của đồ thị
- Thuật toán tìm cây khung bao trùm của đồ thị.
B.
- Sử dụng thuật toán Kruskal để tìm cây khung tối thiểu của đồ thị 1.
- Sử dụng thuật toán Kruskal để tìm cây khung tối thiểu của đồ thị 2.
- Sử dụng thuật toán Kruskal để tìm cây khung tối thiểu của đồ thị 3.
- Sử dụng thuật toán Kruskal để tìm cây khung tối thiểu của đồ thị 4.
- Sử dụng thuật toán Prim để tìm cây khung tối thiểu của đồ thị 1.
- Sử dụng thuật toán Prim để tìm cây khung tối thiểu của đồ thị 2.
- Sử dụng thuật toán Prim để tìm cây khung tối thiểu của đồ thị 3.
- Sử dụng thuật toán Prim để tìm cây khung tối thiểu của đồ thị 4.
- Sử dụng thuật toán Dijkstra để tìm đường đi ngắn nhất từ đỉnh 1 đến tất cả các đỉnh còn lại của đồ thị 1.
- Sử dụng thuật toán Dijkstra để tìm đường đi ngắn nhất từ đỉnh 1 đến tất cả các đỉnh còn lại của đồ thị 2.
- Sử dụng thuật toán Dijkstra để tìm đường đi ngắn nhất từ đỉnh 1 đến tất cả các đỉnh còn lại của đồ thị 3.
- Sử dụng thuật toán Dijkstra để tìm đường đi ngắn nhất từ đỉnh 1 đến tất cả các đỉnh còn lại của đồ thị 4.
(Đồ thị ở trang bên)
`
| (3) | (4) | |
2
21
1
3
14 18 14
6
10
14 11
3 11 11
7
5
20
4
(1)
| 2 | |||||
| 14 | |||||
| 1 | 13 | 7 | |||
| 4 | 8 | 11 | |||
| 14 | 12 | 3 | |||
| 18 | 19 | 14 | |||
| 11 11 | |||||
| 8 | |||||
| 12 | 10 | 5 | |||
| 4 | 14 | 12 | |||
- 6
