TIN TỨC CẬP NHẬT

Đề cương ôn tập môn toán rời rạc.

Xem chủ đề cũ hơn Xem chủ đề mới hơn Go down

Đề cương ôn tập môn toán rời rạc.

Bài gửi by pkt_zz on 8/6/2010, 10:16 pm

1. Lôgic và mệnh đề
1. Hãy tìm một ví dụ để khi thực hiện biểu thị bằng mệnh đề ta được biểu thức mệnh đề:
a.với mọixvới moiyP(x,y)
b.với mọi x tồn tại y P(x,y)
c. tồn tại xvới mọi yyP(x,y)
d.tồn tại xtồn tạiyP(x,y)
3. P(x,y) là mệnh đề "x là bạn thân y" trong đó x,y là các phần tử thuộc tập hợp Người trên thế giới. Hãy biểu diễn bằng mệnh đề các câu sau:
a. Lan chỉ có một người bạn thân duy nhất.
b. Ngoài việc Lan đã coi bố mẹ mình như là 2 người bạn thân, còn chưa ai có thể được coi là bạn thân với Lan
2. Kỹ thuật đếm
1. Trong một tháng gồm 30 ngày, một đội bóng chuyền thi đấu mỗi ngày ít nhất 1 trận nhưng chơi không quá 45 trận. Chứng minh rằng tìm được một giai đoạn gồm một số ngày liên tục nào đó trong tháng sao cho trong giai đoạn đó đội chơi đúng 14 trận.
2. Trong một phòng họp có n người, bao giờ cũng tìm được 2 người có số người quen trong số những người dự họp là như nhau.
3. Có bao nhiêu cách chọn 5 tờ giấy bạc từ một két đựng tiền gồm những tờ 1000đ, 2000đ, 5000đ, 10.000đ, 20.000đ, 50.000đ, 100.000đ. Giả sử thứ tự mà các tờ tiền được chọn là không quan trọng, các tờ tiền cùng loại là không phân biệt và mỗi loại có ít nhất 5 tờ.()
4. Có bao nhiêu cách chia những xấp bài 5 quân cho mỗi một trong 4 người chơi từ một cỗ bài chuẩn 52 quân?
5. Giả sử một người gửi 10.000 đô la vào tài khoản của mình tại một ngân hàng với lãi suất 7% mỗi năm. Sau 30 năm anh ta có bao nhiêu tiền trong tài khoản của mình?
6. Trong tổng số 2504 sinh viên của một khoa công nghệ thông tin, có 1876 theo học môn ngôn ngữ lập trình Pascal, 999 học môn ngôn ngữ Fortran và 345 học ngôn ngữ C. Ngoài ra còn biết 876 sinh viên học cả Pascal và Fortran, 232 học cả Fortran và C, 290 học cả Pascal và C. Nếu 189 sinh viên học cả 3 môn Pascal, Fortran và C thì trong trường hợp đó có bao nhiêu sinh viên không học môn nào trong 3 môn ngôn ngữ lập trình kể trên.(530)
7. Một cuộc họp gồm 12 người tham dự để bàn về 3 vấn đề. Có 8 người phát biểu về vấn đề I, 5 người phát biểu về vấn đề II và 7 người phát biểu về vấn đề III. Ngoài ra, có đúng 1 người không phát biểu vấn đề nào. Hỏi nhiều lắm là có bao nhiêu người phát biểu cả 3 vấn đề. (5)
8. Chỉ ra rằng có ít nhất 4 người trong số 25 triệu người có cùng tên họ viết tắt bằng 3 chữ cái sinh cùng ngày trong năm (không nhất thiết trong cùng một năm).
(bảng chữ cái có 26 chữ --> có 17576 tên viết tắt có thể của một người --> có 25 triệu/17576=1422 người cùng tên. --> có 1422/365=4 người cùng tên sinh cùng ngày)
9. Một tay đô vật tham gia thi đấu giành chức vô địch trong 75 giờ. Mỗi giờ anh ta có ít nhất một trận đấu, nhưng toàn bộ anh ta có không quá 125 trận. Chứng tỏ rằng có những giờ liên tiếp anh ta đã đấu đúng 24 trận.
10. Cho n là số nguyên dương bất kỳ. Chứng minh rằng luôn lấy ra được từ n số đã cho một số số hạng thích hợp sao cho tổng của chúng chia hết cho n.
11.Trong một cuộc lấy ý kiến về 7 vấn đề, người được hỏi ghi vào một phiếu trả lời sẵn bằng cách để nguyên hoặc phủ định các câu trả lời tương ứng với 7 vấn đề đã nêu.
Chứng minh rằng với 1153 người được hỏi luôn tìm được 10 người trả lời giống hệt nhau.(1153/128)
12. Có 17 nhà bác học viết thư cho nhau trao đổi 3 vấn đề. Chứng minh rằng luôn tìm được 3 người cùng trao đổi một vấn đề.
13. Trong kỳ thi kết thúc học phần toán học rời rạc có 10 câu hỏi. Có bao nhiêu cách gán điểm cho các câu hỏi nếu tổng số điểm bằng 100 và mỗi câu ít nhất được 5 điểm.
14. Phương trình x1 + x2 + x3 + x4 + x5 = 21 có bao nhiêu nghiệm nguyên không âm?
15. Có bao nhiêu xâu khác nhau có thể lập được từ khác nhau, từ các chữ cái trong từ MISSISSIPI, yêu cầu phải dùng tất cả các chữ cái?
3. Quan hệ
1. Tìm một ví dụ về quan hệ chỉ có tính chất phản xạ
2. Tìm một ví dụ về quan hệ chỉ có tính chất đối xứng
3. Tìm một ví dụ về quan hệ chỉ có tính chất bắc cầu
4. Tìm một ví dụ về quan hệ chỉ có tính chất phản xạ và bắc cầu
5. Tìm một ví dụ về quan hệ chỉ có tính chất đối xừng và bắc cầu
6. Tìm một ví dụ về quan hệ chỉ có tính chất phản xạ và đối xứng
7. Tìm một ví dụ về quan hệ là quan hệ tương đương
8. Tìm một ví dụ về quan hệ là quan hệ không có tính chất bắc cầu, sau đó hãy tìm bao đóng bắc cầu của quan hệ đó.

pkt_zz
THƯỢNG TƯỚNG V
THƯỢNG TƯỚNG V

Tổng số bài gửi : 1029
Join date : 15/12/2009
Age : 25
Đến từ : MẠC XÁ-QUANG PHỤC

Xem lý lịch thành viên http://lop12a5thpttk-0609.forumotion.net

Về Đầu Trang Go down

Re: Đề cương ôn tập môn toán rời rạc.

Bài gửi by pkt_zz on 8/6/2010, 10:19 pm

Phần lập trình:
1. Lập trình thực hiện đếm số đường đi có độ dài k trên một đố thị đơn vô hướng, không trọng số.
Thông tin đầu vào: dữ liệu đặt trong file TEXT có tên là "DOTHI1.INP"
- Dòng đâu ghi 4 số n, k, p, q (n là số đỉnh, n<50, các đỉnh được đánh số từ 1,2,..., n; k là độ dài đường đi từ đỉnh p đến đỉnh q)
- Các dòng tiếp theo, mỗi ma trận kề của đồ thị
Thông tin đầu ra: Kết quả đặt trong file TEXT có tên là "DOTHI1.OUT" ghi số x duy nhất là số đưòng đi độ dài k từ đỉnh p đến đỉnh q.
2. Lập trình kiểm tra một đồ thị có liên thông hay không.
Thông tin đầu vào: dữ liệu đặt trong file TEXT có tên là "DOTHI2.INP"
- Dòng đâu ghi 1 số n (n là số đỉnh, n<50, các đỉnh được đánh số từ 1,2,..., n)
- Các dòng tiếp theo, mỗi ma trận kề của đồ thị
Thông tin đầu ra: Kết quả đặt trong file TEXT có tên là "DOTHI2.OUT" ghi số 1 hoặc số 0 duy nhất tương ứng với đồ thị liên thông hoặc không liên thông.
3. Lập trình tìm đường đi ngắn nhất giữa 2 đỉnh của một đồ thị
Thông tin đầu vào: dữ liệu đặt trong file TEXT có tên là "DOTHI3.INP"
- Dòng đâu ghi 3 số n, p, q (n là số đỉnh, n<50, các đỉnh được đánh số từ 1,2,..., n; p và q là số hiệu 2 đỉnh, pq)
- Các dòng tiếp theo, mỗi ma trận kề của đồ thị
Thông tin đầu ra: Kết quả đặt trong file TEXT có tên là "DOTHI3.OUT" ghi số k hoặc số 0 duy nhất tương ứng với k là độ dài đường đi ngắn nhắt từ đỉnh p đến đỉnh q.
(các bài 1,2,3 yêu cầu sử dụng định lý đếm số đường đi độ dài k trên đồ thì đơn vô hướng không trọng số).
4. Lập trình tìm đường chu trình Euler trong đồ thị đơn, vô hướng, không trọng số
Thông tin đầu vào: dữ liệu đặt trong file TEXT có tên là "DOTHI4.INP"
- Dòng đâu ghi số n, (n là số đỉnh, n<50, các đỉnh được đánh số từ 1,2,..., n)
- Các dòng tiếp theo, mỗi ma trận kề của đồ thị
Thông tin đầu ra: Kết quả đặt trong file TEXT có tên là "DOTHI4.OUT" ghi số 1 và dãy chỉ số các đỉnh tạo nên chu trình Euler (nếu có). Nếu không có chu trình Euler thì ghi số 2 và dãy chỉ số các đỉnh tạo nên đường đi Euler (nếu có). Nếu không có cả đường đi Euler nữa thì ghi duy nhất số 0.
5. Lập trình tìm cây khung nhỏ nhất trong đồ thị đơn, vô hướng, có trọng số bằng thuật toán Kruskal
Thông tin đầu vào: dữ liệu đặt trong file TEXT có tên là "DOTHI5.INP"
- Dòng đâu ghi số n, (n là số đỉnh, n<50, các đỉnh được đánh số từ 1,2,..., n)
- Các dòng tiếp theo, mỗi ma trận trọng số của đồ thị
Thông tin đầu ra: Kết quả đặt trong file TEXT có tên là "DOTHI5.OUT" ghi dãy các cạnh, mỗi cạnh ghi ở dạng (p,q) nếu cạnh (p,q) nằm trong cây khung nhỏ nhất tìm được
6. Lập trình tìm cây khung nhỏ nhất trong đồ thị đơn, vô hướng, có trọng số bằng thuật toán Prim
Thông tin đầu vào: dữ liệu đặt trong file TEXT có tên là "DOTHI6.INP"
- Dòng đâu ghi số n, (n là số đỉnh, n<50, các đỉnh được đánh số từ 1,2,..., n)
- Các dòng tiếp theo, mỗi ma trận trọng số của đồ thị
Thông tin đầu ra: Kết quả đặt trong file TEXT có tên là "DOTHI6.OUT" ghi dãy các cạnh, mỗi cạnh ghi ở dạng (p,q) nếu cạnh (p,q) nằm trong cây khung nhỏ nhất tìm được
7. Lập trình tìm đường đi ngắn nhất trong đồ thị đơn, vô hướng, có trọng số bằng thuật toán Dijsktra
Thông tin đầu vào: dữ liệu đặt trong file TEXT có tên là "DOTHI7.INP"
- Dòng đâu ghi số n, p,q (n là số đỉnh, n<50, các đỉnh được đánh số từ 1,2,..., n; p và q là chỉ số các đỉnh cần tìm đường đi ngắn nhất)
- Các dòng tiếp theo, mỗi ma trận trọng số của đồ thị
Thông tin đầu ra: Kết quả đặt trong file TEXT có tên là "DOTHI7.OUT" ghi độ dài đường đi ngắn nhất từ đỉnh p đến đỉnh q và dãy các đỉnh của đường đi tìm được hoặc ghi số duy nhất số 0 nếu không có đường đi từ p đến q.
8. Lập trình tìm đường đi ngắn nhất trong đồ thị đơn, vô hướng, có trọng số bằng thuật toán Floyd
Thông tin đầu vào: dữ liệu đặt trong file TEXT có tên là "DOTHI8.INP"
- Dòng đâu ghi số n, p,q (n là số đỉnh, n<50, các đỉnh được đánh số từ 1,2,..., n; p và q là chỉ số các đỉnh cần tìm đường đi ngắn nhất)
- Các dòng tiếp theo, mỗi ma trận trọng số của đồ thị
Thông tin đầu ra: Kết quả đặt trong file TEXT có tên là "DOTHI8.OUT" ghi độ dài đường đi ngắn nhất từ đỉnh p đến đỉnh q và dãy các đỉnh của đường đi tìm được hoặc ghi số duy nhất số 0 nếu không có đường đi từ p đến q.
9. Lập trình tìm số màu của đồ thị đơn, vô hướng, không trọng số
Thông tin đầu vào: dữ liệu đặt trong file TEXT có tên là "DOTHI9.INP"
- Dòng đâu ghi số n, (n là số đỉnh, n<50, các đỉnh được đánh số từ 1,2,..., n)
- Các dòng tiếp theo, mỗi ma trận trọng số của đồ thị
Thông tin đầu ra: Kết quả đặt trong file TEXT có tên là "DOTHI9.OUT"
Dòng đầu ghi số màu M của đồ thị
M dòng tiếp theo, mỗi dòng thứ i ghi các đỉnh được tô bởi màu i
10. Lập trình tìm số Fibonaci thứ n (dãy số Fibonaci là dãy số có công thức đệ quy như sau: f1=1; f2=1; fn=fn-1+fn-2 với n>2)
Yêu cầu: Nhập vào số n từ bàn phím, đưa ra màn hình giá trị của fn.
Thử thách: có thể lập trình để tìm số Fibonaci thứ n với n có giá trị đến 1000 không?

pkt_zz
THƯỢNG TƯỚNG V
THƯỢNG TƯỚNG V

Tổng số bài gửi : 1029
Join date : 15/12/2009
Age : 25
Đến từ : MẠC XÁ-QUANG PHỤC

Xem lý lịch thành viên http://lop12a5thpttk-0609.forumotion.net

Về Đầu Trang Go down

Re: Đề cương ôn tập môn toán rời rạc.

Bài gửi by pkt_zz on 8/6/2010, 10:24 pm

Có thể download file .doc tại đây:

[You must be registered and logged in to see this link.]

pkt_zz
THƯỢNG TƯỚNG V
THƯỢNG TƯỚNG V

Tổng số bài gửi : 1029
Join date : 15/12/2009
Age : 25
Đến từ : MẠC XÁ-QUANG PHỤC

Xem lý lịch thành viên http://lop12a5thpttk-0609.forumotion.net

Về Đầu Trang Go down

Re: Đề cương ôn tập môn toán rời rạc.

Bài gửi by Sponsored content Today at 1:06 pm


Sponsored content


Về Đầu Trang Go down

Xem chủ đề cũ hơn Xem chủ đề mới hơn Về Đầu Trang


 
Permissions in this forum:
Bạn không có quyền trả lời bài viết