Đề thi cuối kì môn Toán rời rạc| Môn Toán rời rạc| Trường Đại học Bách Khoa Hà Nội

Bài 1:
1a) Trong không gian 3 chiều có bao nhiêu đường đi từ điểm (0,0,0) đến điểm (25, 35, 55) nếu mỗi bước đi có một trong ba toạ độ tăng lên 1, hai toạ độ còn lại giữ nguyên.
1b) Có bao nhiêu đơn đồ thị vô hướng với n đỉnh ?

Đề thi môn: TOÁN RI RC K56
Thi gian: 90 phút
(Không s dng tài liu, np lại đề)
Bài 1:
1a) Trong không gian 3 chiều có bao nhiêu đưng đi từ điểm (0,0,0) đến điểm
(25, 35, 55) nếu mỗi bước đi có một trong ba to độ tăng lên 1, hai to độn li
gi nguyên.
1b) Có bao nhiêu đơn đồ th vô hướng với n đỉnh ?
Bài 2: Xét hai mệnh đ
(P1): Vi mi s nguyên dương lẻ m, luônm được s nguyên dương n sao cho
2
n
– 1 chia hết cho m.
(P2): Vi mi s nguyên dương m, n, đồ th hai phía đầy đ K
m,n
luôn cha chu
trình Hamilton.
Hãy chứng minhnh đúng đắn hoặc đưa ra phn ví d cho mi mệnh đề.
Bài 3: Trình din thut toán nhánh cn gii bài toán cái túi biến nguyên sau:
10
+ 17
+ 30
+ 40

3
+ 5
+ 7
+ 8
28
0,
, =1,2,3,4
Bài 4: Cho G=(V,E) là đồ th có hướng mà giữa hai đỉnh bt kì u,v ca nó luôn
có hoc là cnh (u,v), hoc là cnh (v,u), nhưng không đồng thi có c hai. Kí
hiu deg
+
(v) và deg
-
(v) tương ứng là bán bc ra và bán bc vào ca đỉnh v. Chng
minh rng với đồ th G đã cho, đẳng thức sau đây luôn đúng:
[deg
()]
∈
=[deg
()]
∈
Bài 5: Xét đồ th có hướng có trng s như dưới đây, trình din thut toán
Dijkstra tìm đường đi ngn nht t đỉnh A đến các đỉnh còn li:
Đề thi môn: TOÁN RI RC K56
Thi gian: 90 phút
(Không s dng tài liu, np lại đề)
Bài 1:
1a) Trong không gian 3 chiều có bao nhiêu đưng đi từ điểm (0,0,0) đến điểm
(30, 40, 50) nếu mỗi bước đi có một trong ba to độ tăng lên 1, hai to độn li
gi nguyên.
1b) Tính tng s bc của đơn đồ th đủ K
n
.
Bài 2: Xét hai mệnh đ
(P1): Vi mi s nguyên dương lẻ m, luônm được s nguyên dương n sao cho
2
n
– 1 chia hết cho m.
(P2): Vi mi s nguyên dương m, n, đồ th hai phía đầy đ K
m,n
luôn cha chu
trình Hamilton.
Hãy chứng minhnh đúng đắn hoặc đưa ra phn ví d cho mi mệnh đề.
Bài 3: Trình din thut toán nhánh cn gii bài toán cái túi biến nguyên sau:
11
+ 18
+ 31
+ 41

3
+ 5
+ 7
+ 8
29
0,
, =1,2,3,4
Bài 4: Cho G=(V,E) là đồ th có hướng mà giữa hai đỉnh bt kì u,v ca nó luôn
có hoc là cnh (u,v), hoc là cnh (v,u), nhưng không đồng thi có c hai. Kí
hiu deg
+
(v) và deg
-
(v) tương ứng là bán bc ra và bán bc vào ca đỉnh v. Chng
minh rng với đồ th G đã cho, đẳng thức sau đây luôn đúng:
[deg
()]
∈
=[deg
()]
∈
Bài 5: Xét đồ th có hướng có trng s như dưới đây, trình din thut toán
Dijkstra tìm đường đi ngn nht t đỉnh B đến các đỉnh còn li:
1
2
Đề thi môn: TOÁN RI RC K55
Thi gian: 90 phút
(Không s dng tài liu, np lại đề)
Bài 1:
1a) Tìm s nghim nguyên (x,y) ca bất phương trình:
3
|
|
+
|
|
, vi n là s nguyên dương.
1b) Mt hình lập phương có cnh bng 15 chứa 11000 điểm. Chng minh rng
tn ti mt hình cu bán kính bng 1 cha ít nhất 6 điểm trong s 11000 điểm đã
cho.
Bài 2: Xét hai mệnh đ
(P1): Trong một đơn đồ th luôn có ít nhất 2 đỉnh cùng bc.
(P2): Trong mt phẳng cho 5 điểm phân bit có to độ nguyên, luôn tìm được ít
nht 2 điểm mà trung điểm đoạn thng ni chúng có to độ nguyên.
Hãy chứng minhnh đúng đắn hoặc đưa ra phn ví d cho mi mệnh đề.
Bài 3: S dng hàm sinh gii công thc đệ quy:
=4,
=12
=

+ 2

+ 2
( 2)
Bài 4: Cho G=(V,E) là đồ thv đỉnh và e cnh. còn mM tươngng là bc
nh nht và bc ln nht của các đỉnh ca G. Chng minh h bất đẳng thc:
2
Bài 5: Xét đồ th vô hướng có trng s như dưới đây, trình din thut toán Prim
tìm cây khung ln nht của đồ th:
Đề thi môn: TOÁN RI RC K55
Thi gian: 90 phút
(Không s dng tài liu, np lại đề)
Bài 1:
1a) Tìm s nghim nguyên ca bất phương trình:
+ + 25, vi điều kin , 2,0< <6
1b) Mt hình vuông có cnh bng 1 chứa 101 điểm. Chng minh rng có ít nht 5
điểm trong s 101 đim nói tn nm trong mt hình tròn bán kính bng 1/7.
Bài 2: Xét hai mệnh đ
(P1): Trong s 10 người bt kì bao gi cũng tìm được 2 người có tng s tui chia
hết cho 16, hoc hiu s tui chia hết cho 16.
(P2): Trong không gian cho 9 điểm có to độ nguyên, luôn tìm được ít nht 2
điểm mà đoạn thng nối chúng đi qua điểm có to độ nguyên.
Hãy chứng minhnh đúng đắn hoặc đưa ra phn ví d cho mi mệnh đề.
Bài 3: S dng hàm sinh gii công thức đệ quy:
=2,
=5
=4

4

+
( 2)
Bài 4: Cho G=(V,E)đơn đồ th hai phía có v đỉnh và e cnh. Chng minh bt
đẳng thc sau:
4
Bài 5: Xét đồ th có hướng có trng s như dưới đây, trình din thut toán
Kruskal tìm cây khung ln nht của đồ th:
1
2
Đề thi môn: TOÁN RI RC K54
Thi gian: 90 phút
(Không s dng tài liu, np lại đề)
Bài 1:
1a) Trong tng s 2504 sinh vn ca khoa công ngh thông tin, có 1876 theo hc
ngôn ng Pascal, 999 hc môn ngôn ng Fortran và 345 hc môn ngôn ng C.
Ngoài ra còn biết 876 sinh viên hc c Pascal và Fortran, 232 hc c Fortran và C,
290 hc c Pascal và C. Nếu 189 sinh viên hc c ba ngôn ng Pascal, Fortran và
C thì trong trường hợp đó có bao nhu sinh viên không học môn nào trong c 3
ngôn ng nói trên.
1b) Một đô vật tham gia thi đấu giành chức vô địch trong 75 gi. Mi gi anh ta
thi đấu ít nht mt trn, nhưng toàn bộ anh ta không thi đu quá 125 trn. Chng
t rng, có nhng gi liên tiếp anh ta thi đấu 24 trn.
Bài 2: Xét mệnh đề sau: “Trong n+1 s nguyên dương, mi s không vượt q
2n, tn ti ít nht mt s chia hết cho mt s khác”.
Hãy chứng minhnh đúng đắn hoặc đưa ra phn ví d cho mệnh đề trên.
Bài 3: Trình din thut toán nhánh cn giải bài toán người du lch vi ma trn chi
phí như dưới đây (giả s xut phát t A):
A B C D E
A 0 55 87 70 76
B 91 0 81 57 39
C 80 77 0 81 58
D 99 83 64 0 89
E 56 91 82 88 0
Bài 4: Mt ngôi chùa linh thiêng có 5 tr bằng kim cương. Ngưi ta đúc các
dây xích bằng vàng để ni các tr li vi nhau, với điều kin mi tr ch được
ni vi đúng 3 tr khác. Chng minh rng không th tìm được cách ni tho
mãn điều kin trên.
Bài 5: Trình din thut toán Ford-Fulkerson tìm lung cực đại và lát ct hp nht
trong mng sau:
Đề thi môn: TOÁN RI RC K54
Thi gian: 90 phút
(Không s dng tài liu, np lại đề)
Bài 1:
1a) Hiệu trưởng mi 2n ( 2) sinh viên gii đến d tic. Mi sinh viên gii
quen ít nht n sinh viên giỏi khác đến d tic. Chng minh rng luôn luôn có th
xếp tt c các sinh viên gii ngi xung quanh mt bàn tròn, để mỗi người ngi
giữa hai người mà sinh viên đó quen.
1b) Đếm s xâu nh phân 13 bit cha hai s 0 ln tiếp.
Bài 2: Xét mệnh đề sau: “Trong 102 người có chiều cao khác nhau đứng thành
mt hàng luôn tìm được 11 người có chiều cao tăng dần hoc gim dn mà không
cần thay đi th t ca h trong hàng”.
Hãy chứng minhnh đúng đắn hoặc đưa ra phn ví d cho mệnh đề trên.
Bài 3: Trình din thut toán nhánh cn giải bài toán người du lch vi ma trn chi
phí như dưới đây (giả s xut phát t A):
A B C D E
A 0 43 80 69 72
B 81 0 92 58 39
C 70 77 0 82 43
D 95 73 17 0 89
E 26 91 82 78 0
Bài 4: Gi s đơn đồ th phẳng liên thông có 6 đỉnh, mỗi đỉnh đều có bc là 4.
Biu din phng của đồ th này chia mt phng thành bao nhiêu min ?
Bài 5: Trình din thut toán Ford-Fulkerson tìm lung cực đại và lát ct hp nht
trong mng sau:
1
2
Đề thi môn: TOÁN RI RC K53
Thi gian: 90 phút
(Không s dng tài liu, np lại đề)
Bài 1:
a) Trong tp 2009 s nguyên dương đầu tiên có bao nhiêu s không chia hết cho
bt kì s nào trong các s 11, 13, 15, 17.
b) Trên một lưới ô vuông các s nguyên cho hai điểm A(3,2) và B(100, 99). Hi
có bao nhiêu đường đi khác nhau từ A đến B mà không ct đường thng y=x (ch
cho phép đi trên cnh các ô vuông theo chiu sang phi hoc lên trên) ?
Bài 2: Cho G=(V,E) là một đơn đồ th vô hướng liên thông. Chng minh rng:
a) Nếu tt c các đỉnh ca G đều có bc là 2 thì G là đồ th Euler.
b) Nếu tt c các cnh ca G là cu thì G là mt cây.
Bài 3: Trình din thut toán nhánh cn gii bài toán cái túi:
7
+ 15
+ 26
+ 34

3
+ 4
+ 8
+ 9
25
0,
, =1,2,3,4
Bài 4: Gii công thức đ quy:
=6,
=42
=

+ 6

+ 6( 3)
Bài 5: Trong mng G=(V,E) cho lung f như sau:
a) Xây dng đ th tăng luồng G
f
.
b) Cho biết lung f có cực đại không ? Nếu không, hãy thc hin tìm lung
cực đại và lát ct hp nht ca mng trên.
Đề thi môn: TOÁN RI RC K53
Thi gian: 90 phút
(Không s dng tài liu, np lại đề)
Bài 1:
a) T các ch s 1,2,3,4,5,6,7, người ta lp tt c các s có 5 ch s (5 ch s này
đôi một khác nhau). Tính tng ca tt c các s này.
b) Trong tp A = {1,2,…,30000} có bao nhiêu s không chia hết cho bt c s
nào trong các s 6, 8, 9 ?
Bài 2:
a) Có 20 đội bóng thi đấu trong mt gii. Mỗi đi phải đấu mt trn với các đi
còn li. Chng minh rằng luôn có hai đội bóng có s trận đã đấu là như nhau (tính
c trường hợp chưa đấu trn nào).
b) Chng minh rằng cây là đồ th hai phía.
Bài 3: Trình din thut toán nhánh cn gii bài toán cái túi:
16
+ 9
+ 7
+ 5

6
+ 5
+ 3
+ 2
17
0,
, =1,2,3,4
Bài 4: Gii công thức đ quy:
=1,
=2
=8

16

+ 6 + 2( 2)
Bài 5: Trong mng G=(V,E) cho luồng f như sau:
a) Xây dng đ th tăng luồng G
f
. T đó chng minh f là lung cực đại.
b) Đưa ra giá tr lung cực đại và lát ct hp nht.
1
2
Đề thi môn: TOÁN RI RC K52
Thi gian: 90 phút
(Không s dng tài liu, np lại đề)
Bài 1:
a) Trường ĐHBKHN tiến hành phát hc bng cho sinh viên. Biết rng có ba loi
hc bng, hi cn trao hc bng cho ít nhất bao nhiêu sinh viên đ chc chn rng
trong s h có ít nhất 13 người nhn hc bng cùng loi ?
b) Tìm s cách đặt các du ngoặc đơn vào tích của n + 1 s
để xác định
th t ca phép nhân. Ví d có 5 cách đặt du ngoặc đơn cho tích
để
các định th t phép nhân:
(
)

,
(
)

,
(
)(
)
,
(
)
,
(
(
)
).
Bài 2: Cho đồ th có hướng G được biu din dưới dng ma trn trng s:
A
B
C
D
E
A
0
3
3
B
0
3
4
1
C
0
3
1
D
1
0
2
E
0
1
0
a) Thc hin thut toán Dijkstra tìm đường đi ngắn nht t đỉnh C đến các đỉnh
còn li của đồ th G.
b) Chng minh G là mt mng. Thc hin thut toán Ford – Fulkerson tìm lung
cực đi và lát ct nh nht ca mng G.
c) Gi G’ là phiên bản vô hướng ca G (tc là không xét tới hướng ca các cung
trên G). Thc hin thut toán Primm cây khung nh nht của đồ th G’.
Bài 3: Gii công thức đ quy sau:
=1,
=4
=4

3

+ 2
+ + 3( 2)
Đề thi môn: TOÁN RI RC – K52
Thi gian: 90 phút
(Không s dng tài liu, np lại đề)
Bài 1:
a) Trường ĐHBKHN tiến hành phát hc bng cho sinh viên. Biết rằng có năm
loi hc bng, hi cn trao hc bng cho ít nhất bao nhiêu sinh viên để chc chn
rng trong s h có ít nht 28 người nhn hc bng cùng loi ?
b) Mt máy bán tem t đng ch nhn loi tin xu 1$, tin giy 1$ và tin giy 5$.
Tìm s cách đưa 30 $ vào máy (có chú ý đến th t ca xu và giy b vào).
Bài 2: Cho đồ th có hướng G được biu din dưới dng ma trn trng s:
A
B
C
D
E
A
0
5
3
B
0
4
6
C
0
4
3
D
2
0
2
E
1
0
2
0
a) Thc hin thut toán Dijkstra tìm đường đi ngắn nht t đỉnh E đến các đỉnh
còn li của đồ th G.
b) Chng minh G là mt mng. Thc hin thut toán Ford – Fulkerson tìm lung
cực đi và lát ct nh nht ca mng G.
c) Gi G’ là phiên bản vô hướng ca G (tc là không xét tới hướng ca các cung
trên G). Thc hin thut toán Kruskal tìm cây khung nh nht của đồ th G’.
Bài 3: Gii công thức đ quy sau:
=2,
=0,
=5
=7

16

+ 12

+ 4
( 3)
1
2
| 1/5

Preview text:


Đề thi môn: TOÁN RỜI RẠC – K56
Đề thi môn: TOÁN RỜI RẠC – K56 1 Thời gian: 90 phút 2 Thời gian: 90 phút
(Không sử dụng tài liệu, nộp lại đề)
(Không sử dụng tài liệu, nộp lại đề) Bài 1: Bài 1:
1a) Trong không gian 3 chiều có bao nhiêu đường đi từ điểm (0,0,0) đến điểm
1a) Trong không gian 3 chiều có bao nhiêu đường đi từ điểm (0,0,0) đến điểm
(25, 35, 55) nếu mỗi bước đi có một trong ba toạ độ tăng lên 1, hai toạ độ còn lại
(30, 40, 50) nếu mỗi bước đi có một trong ba toạ độ tăng lên 1, hai toạ độ còn lại giữ nguyên. giữ nguyên.
1b) Có bao nhiêu đơn đồ thị vô hướng với n đỉnh ?
1b) Tính tổng số bậc của đơn đồ thị đủ Kn. Bài 2: Xét hai mệnh đề Bài 2: Xét hai mệnh đề
(P1): Với mọi số nguyên dương lẻ m, luôn tìm được số nguyên dương n sao cho
(P1): Với mọi số nguyên dương lẻ m, luôn tìm được số nguyên dương n sao cho 2n – 1 chia hết cho m. 2n – 1 chia hết cho m.
(P2): Với mọi số nguyên dương m, n, đồ thị hai phía đầy đủ Km,n luôn chứa chu
(P2): Với mọi số nguyên dương m, n, đồ thị hai phía đầy đủ Km,n luôn chứa chu trình Hamilton. trình Hamilton.
Hãy chứng minh tính đúng đắn hoặc đưa ra phản ví dụ cho mỗi mệnh đề.
Hãy chứng minh tính đúng đắn hoặc đưa ra phản ví dụ cho mỗi mệnh đề.
Bài 3: Trình diễn thuật toán nhánh cận giải bài toán cái túi biến nguyên sau:
Bài 3: Trình diễn thuật toán nhánh cận giải bài toán cái túi biến nguyên sau: 10 + 17 + 30 + 40 → 11 + 18 + 31 + 41 → 3 + 5 + 7 + 8 ≤ 28 3 + 5 + 7 + 8 ≤ 29 ≥ 0, ∈ ℤ, = 1,2,3,4 ≥ 0, ∈ ℤ, = 1,2,3,4
Bài 4: Cho G=(V,E) là đồ thị có hướng mà giữa hai đỉnh bất kì u,v của nó luôn
Bài 4: Cho G=(V,E) là đồ thị có hướng mà giữa hai đỉnh bất kì u,v của nó luôn
có hoặc là cạnh (u,v), hoặc là cạnh (v,u), nhưng không đồng thời có cả hai. Kí
có hoặc là cạnh (u,v), hoặc là cạnh (v,u), nhưng không đồng thời có cả hai. Kí
hiệu deg+(v) và deg-(v) tương ứng là bán bậc ra và bán bậc vào của đỉnh v. Chứng
hiệu deg+(v) và deg-(v) tương ứng là bán bậc ra và bán bậc vào của đỉnh v. Chứng
minh rằng với đồ thị G đã cho, đẳng thức sau đây luôn đúng:
minh rằng với đồ thị G đã cho, đẳng thức sau đây luôn đúng: [deg ( )] = [deg ( )] [deg ( )] = [deg ( )] ∈ ∈ ∈ ∈
Bài 5: Xét đồ thị có hướng có trọng số như dưới đây, trình diễn thuật toán
Bài 5: Xét đồ thị có hướng có trọng số như dưới đây, trình diễn thuật toán
Dijkstra tìm đường đi ngắn nhất từ đỉnh A đến các đỉnh còn lại:
Dijkstra tìm đường đi ngắn nhất từ đỉnh B đến các đỉnh còn lại:
Đề thi môn: TOÁN RỜI RẠC – K55
Đề thi môn: TOÁN RỜI RẠC – K55 Thời gian: 90 phút Thời gian: 90 phút 1 2
(Không sử dụng tài liệu, nộp lại đề)
(Không sử dụng tài liệu, nộp lại đề) Bài 1: Bài 1:
1a) Tìm số nghiệm nguyên (x,y) của bất phương trình:
1a) Tìm số nghiệm nguyên của bất phương trình:
3| | + | | ≤ , với n là số nguyên dương. +
+ ≤ 25 , với điều kiện , ≥ 2, 0 < < 6
1b) Một hình lập phương có cạnh bằng 15 chứa 11000 điểm. Chứng minh rằng
1b) Một hình vuông có cạnh bằng 1 chứa 101 điểm. Chứng minh rằng có ít nhất 5
tồn tại một hình cầu bán kính bằng 1 chứa ít nhất 6 điểm trong số 11000 điểm đã
điểm trong số 101 điểm nói trên nằm trong một hình tròn bán kính bằng 1/7. cho. Bài 2: Xét hai mệnh đề Bài 2: Xét hai mệnh đề
(P1): Trong số 10 người bất kì bao giờ cũng tìm được 2 người có tổng số tuổi chia
(P1): Trong một đơn đồ thị luôn có ít nhất 2 đỉnh cùng bậc.
hết cho 16, hoặc hiệu số tuổi chia hết cho 16.
(P2): Trong mặt phẳng cho 5 điểm phân biệt có toạ độ nguyên, luôn tìm được ít
(P2): Trong không gian cho 9 điểm có toạ độ nguyên, luôn tìm được ít nhất 2
nhất 2 điểm mà trung điểm đoạn thẳng nối chúng có toạ độ nguyên.
điểm mà đoạn thẳng nối chúng đi qua điểm có toạ độ nguyên.
Hãy chứng minh tính đúng đắn hoặc đưa ra phản ví dụ cho mỗi mệnh đề.
Hãy chứng minh tính đúng đắn hoặc đưa ra phản ví dụ cho mỗi mệnh đề.
Bài 3: Sử dụng hàm sinh giải công thức đệ quy:
Bài 3: Sử dụng hàm sinh giải công thức đệ quy: = 4, = 12 = 2, = 5 = + 2 + 2 ( ≥ 2) = 4 − 4 + ( ≥ 2)
Bài 4: Cho G=(V,E) là đồ thị có v đỉnh và e cạnh. còn mM tương ứng là bậc
Bài 4: Cho G=(V,E) là đơn đồ thị hai phía có v đỉnh và e cạnh. Chứng minh bất
nhỏ nhất và bậc lớn nhất của các đỉnh của G. Chứng minh hệ bất đẳng thức: đẳng thức sau: 2 ≤ ≤ ≤ 4 Bài 5: Bài 5:
Xét đồ thị có hướng có trọng số như dưới đây, trình diễn thuật toán
Xét đồ thị vô hướng có trọng số như dưới đây, trình diễn thuật toán Prim
Kruskal tìm cây khung lớn nhất của đồ thị:
tìm cây khung lớn nhất của đồ thị:
Đề thi môn: TOÁN RỜI RẠC – K54
Đề thi môn: TOÁN RỜI RẠC – K54 Thời gian: 90 phút Thời gian: 90 phút 1 2
(Không sử dụng tài liệu, nộp lại đề)
(Không sử dụng tài liệu, nộp lại đề) Bài 1: Bài 1:
1a) Trong tổng số 2504 sinh viên của khoa công nghệ thông tin, có 1876 theo học
1a) Hiệu trưởng mời 2n ( ≥ 2) sinh viên giỏi đến dự tiệc. Mỗi sinh viên giỏi
ngôn ngữ Pascal, 999 học môn ngôn ngữ Fortran và 345 học môn ngôn ngữ C.
quen ít nhất n sinh viên giỏi khác đến dự tiệc. Chứng minh rằng luôn luôn có thể
Ngoài ra còn biết 876 sinh viên học cả Pascal và Fortran, 232 học cả Fortran và C,
xếp tất cả các sinh viên giỏi ngồi xung quanh một bàn tròn, để mỗi người ngồi
290 học cả Pascal và C. Nếu 189 sinh viên học cả ba ngôn ngữ Pascal, Fortran và
giữa hai người mà sinh viên đó quen.
C thì trong trường hợp đó có bao nhiêu sinh viên không học môn nào trong cả 3 ngôn ngữ nói trên.
1b) Đếm số xâu nhị phân 13 bit chứa hai số 0 liên tiếp.
1b) Một đô vật tham gia thi đấu giành chức vô địch trong 75 giờ. Mỗi giờ anh ta
thi đấu ít nhất một trận, nhưng toàn bộ anh ta không thi đấu quá 125 trận. Chứng
Bài 2: Xét mệnh đề sau: “Trong 102 người có chiều cao khác nhau đứng thành
tỏ rằng, có những giờ liên tiếp anh ta thi đấu 24 trận.
một hàng luôn tìm được 11 người có chiều cao tăng dần hoặc giảm dần mà không
cần thay đổi thứ tự của họ trong hàng”.
Bài 2: Xét mệnh đề sau: “Trong n+1 số nguyên dương, mỗi số không vượt quá
2n, tồn tại ít nhất một số chia hết cho một số khác”.
Hãy chứng minh tính đúng đắn hoặc đưa ra phản ví dụ cho mệnh đề trên.
Hãy chứng minh tính đúng đắn hoặc đưa ra phản ví dụ cho mệnh đề trên.
Bài 3: Trình diễn thuật toán nhánh cận giải bài toán người du lịch với ma trận chi
Bài 3: Trình diễn thuật toán nhánh cận giải bài toán người du lịch với ma trận chi
phí như dưới đây (giả sử xuất phát từ A):
phí như dưới đây (giả sử xuất phát từ A): A B C D E A B C D E A 0 55 87 70 76 A 0 43 80 69 72 B 91 0 81 57 39 B 81 0 92 58 39 C 80 77 0 81 58 C 70 77 0 82 43 D 99 83 64 0 89 D 95 73 17 0 89 E 56 91 82 88 0 E 26 91 82 78 0
Bài 4: Một ngôi chùa linh thiêng có 5 trụ bằng kim cương. Người ta đúc các
Bài 4: Giả sử đơn đồ thị phẳng liên thông có 6 đỉnh, mỗi đỉnh đều có bậc là 4.
dây xích bằng vàng để nối các trụ lại với nhau, với điều kiện mỗi trụ chỉ được
Biểu diễn phẳng của đồ thị này chia mặt phẳng thành bao nhiêu miền ?
nối với đúng 3 trụ khác. Chứng minh rằng không thể tìm được cách nối thoả
Bài 5: Trình diễn thuật toán Ford-Fulkerson tìm luồng cực đại và lát cắt hẹp nhất mãn điều kiện trên. trong mạng sau:
Bài 5: Trình diễn thuật toán Ford-Fulkerson tìm luồng cực đại và lát cắt hẹp nhất trong mạng sau:
Đề thi môn: TOÁN RỜI RẠC – K53
Đề thi môn: TOÁN RỜI RẠC – K53 Thời gian: 90 phút Thời gian: 90 phút 1 2
(Không sử dụng tài liệu, nộp lại đề)
(Không sử dụng tài liệu, nộp lại đề) Bài 1: Bài 1:
a) Trong tập 2009 số nguyên dương đầu tiên có bao nhiêu số không chia hết cho
a) Từ các chữ số 1,2,3,4,5,6,7, người ta lập tất cả các số có 5 chữ số (5 chữ số này
bất kì số nào trong các số 11, 13, 15, 17.
đôi một khác nhau). Tính tổng của tất cả các số này.
b) Trên một lưới ô vuông các số nguyên cho hai điểm A(3,2) và B(100, 99). Hỏi
b) Trong tập A = {1,2,…,30000} có bao nhiêu số không chia hết cho bất cứ số
có bao nhiêu đường đi khác nhau từ A đến B mà không cắt đường thẳng y=x (chỉ
nào trong các số 6, 8, 9 ?
cho phép đi trên cạnh các ô vuông theo chiều sang phải hoặc lên trên) ? Bài 2:
Bài 2: Cho G=(V,E) là một đơn đồ thị vô hướng liên thông. Chứng minh rằng:
a) Có 20 đội bóng thi đấu trong một giải. Mỗi đội phải đấu một trận với các đội
a) Nếu tất cả các đỉnh của G đều có bậc là 2 thì G là đồ thị Euler.
còn lại. Chứng minh rằng luôn có hai đội bóng có số trận đã đấu là như nhau (tính
b) Nếu tất cả các cạnh của G là cầu thì G là một cây.
cả trường hợp chưa đấu trận nào).
b) Chứng minh rằng cây là đồ thị hai phía.
Bài 3: Trình diễn thuật toán nhánh cận giải bài toán cái túi: 7 + 15 + 26 + 34 →
Bài 3: Trình diễn thuật toán nhánh cận giải bài toán cái túi: 3 + 4 + 8 + 9 ≤ 25 16 + 9 + 7 + 5 → ≥ 0, ∈ ℤ, = 1,2,3,4 6 + 5 + 3 + 2 ≤ 17 ≥ 0, ∈ ℤ, = 1,2,3,4
Bài 4: Giải công thức đệ quy: = 6, = 42
Bài 4: Giải công thức đệ quy: = + 6 + 6 ( ≥ 3) = 1, = 2 = 8 − 16 + 6 + 2 ( ≥ 2)
Bài 5: Trong mạng G=(V,E) cho luồng f như sau:
Bài 5: Trong mạng G=(V,E) cho luồng f như sau:
a) Xây dựng đồ thị tăng luồng Gf.
b) Cho biết luồng f có cực đại không ? Nếu không, hãy thực hiện tìm luồng
a) Xây dựng đồ thị tăng luồng Gf. Từ đó chứng minh f là luồng cực đại.
cực đại và lát cắt hẹp nhất của mạng trên.
b) Đưa ra giá trị luồng cực đại và lát cắt hẹp nhất.
Đề thi môn: TOÁN RỜI RẠC – K52
Đề thi môn: TOÁN RỜI RẠC – K52 Thời gian: 90 phút Thời gian: 90 phút 1 2
(Không sử dụng tài liệu, nộp lại đề)
(Không sử dụng tài liệu, nộp lại đề) Bài 1: Bài 1:
a) Trường ĐHBKHN tiến hành phát học bổng cho sinh viên. Biết rằng có ba loại
a) Trường ĐHBKHN tiến hành phát học bổng cho sinh viên. Biết rằng có năm
học bổng, hỏi cần trao học bổng cho ít nhất bao nhiêu sinh viên để chắc chắn rằng
loại học bổng, hỏi cần trao học bổng cho ít nhất bao nhiêu sinh viên để chắc chắn
trong số họ có ít nhất 13 người nhận học bổng cùng loại ?
rằng trong số họ có ít nhất 28 người nhận học bổng cùng loại ?
b) Tìm số cách đặt các dấu ngoặc đơn vào tích của n + 1 số … để xác định
b) Một máy bán tem tự động chỉ nhận loại tiền xu 1$, tiền giấy 1$ và tiền giấy 5$.
thứ tự của phép nhân. Ví dụ có 5 cách đặt dấu ngoặc đơn cho tích để
Tìm số cách đưa 30 $ vào máy (có chú ý đến thứ tự của xu và giấy bỏ vào).
các định thứ tự phép nhân: ( ) , ( ) , ( )( ),
Bài 2: Cho đồ thị có hướng G được biểu diễn dưới dạng ma trận trọng số: ( ) , ( ( )). A B C D E F
Bài 2: Cho đồ thị có hướng G được biểu diễn dưới dạng ma trận trọng số: A 0 5 ∞ 3 ∞ ∞ B ∞ 0 4 6 ∞ ∞ A B C D E F C ∞ ∞ 0 ∞ 4 3 A 0 3 ∞ 3 ∞ ∞ D ∞ ∞ 2 0 2 ∞ B ∞ 0 3 4 1 ∞ E ∞ 1 ∞ ∞ 0 2 C ∞ ∞ 0 ∞ 3 1 F ∞ ∞ ∞ ∞ ∞ 0 D ∞ ∞ 1 0 2 ∞ E ∞ ∞ ∞ ∞ 0 1
a) Thực hiện thuật toán Dijkstra tìm đường đi ngắn nhất từ đỉnh E đến các đỉnh F ∞ ∞ ∞ ∞ ∞ 0
còn lại của đồ thị G.
b) Chứng minh G là một mạng. Thực hiện thuật toán Ford – Fulkerson tìm luồng
a) Thực hiện thuật toán Dijkstra tìm đường đi ngắn nhất từ đỉnh C đến các đỉnh
cực đại và lát cắt nhỏ nhất của mạng G.
còn lại của đồ thị G.
c) Gọi G’ là phiên bản vô hướng của G (tức là không xét tới hướng của các cung
b) Chứng minh G là một mạng. Thực hiện thuật toán Ford – Fulkerson tìm luồng
trên G). Thực hiện thuật toán Kruskal tìm cây khung nhỏ nhất của đồ thị G’.
cực đại và lát cắt nhỏ nhất của mạng G.
c) Gọi G’ là phiên bản vô hướng của G (tức là không xét tới hướng của các cung
Bài 3: Giải công thức đệ quy sau:
trên G). Thực hiện thuật toán Prim tìm cây khung nhỏ nhất của đồ thị G’.
Bài 3: Giải công thức đệ quy sau: = −2, = 0, = 5 = 7 − 16 + 12 + 4 ( ≥ 3) = 1, = 4 = 4 − 3 + 2 + + 3 ( ≥ 2)