46.01.104.206 2-đã chuyển đổi PDF

Preview

Summary

BỘ GIÁO DỤC VÀ ĐÀO TẠOTRƯỜNG ĐẠI HỌC SƯ PHẠM THÀNH PHỐ HỒ CHÍ MINHKHOA CÔNG NGHỆ THÔNG TIN---  ---TIỂU LUẬNMôn : Toán Rời Rạc Sinh viên thực hiện: Bùi Hoàng Tú MSSV :46.01. Lớp :CNTT-A Mã học phần : MATHLời Cảm ƠnĐầu tiên, em xin gửi lời cảm ơn chân thành đến Trường Đại học Sư Phạm TP đã đưa môn ...

Description

BỘ GIÁO DỤC VÀ ĐÀO TẠO TRƯỜNG ĐẠI HỌC SƯ PHẠM THÀNH PHỐ HỒ CHÍ MINH KHOA CÔNG NGHỆ THÔNG TIN

------

TIỂU LUẬN

Môn

: Toán Rời Rạc

Sinh viên thực hiện: Bùi Hoàng Tú MSSV

:46.01.104.206

Lớp

:CNTT-A

Mã học phần

: MATH101001

1

Lời Cảm Ơn Đầu tiên, em xin gửi lời cảm ơn chân thành đến Trường Đại học Sư Phạm TP.HCM đã đưa môn học Toán Rời Rạc vào giảng dạy. Đặc biệt, em xin gửi lời cảm ơn sâu sắc đến giảng viên bộ môn – Cô Nguyễn Thị Huỳnh Trâm đã dạy dỗ, truyền đạt những kiến thức quý báu cho em trong suốt thời gian học tập vừa qua. Trong thời gian tham gia lớp học Toán Rời Rạc của Cô, em đã có thêm cho mình nhiều kiến thức bổ ích, tinh thần học tập hiệu quả, nghiêm túc. Đây chắc chắn sẽ là những kiến thức quý báu, là hành trang để em có thể vững bước sau này. Bài thi tiểu luận lần này là một trải nghiệm vô cùng bổ ích và có tính thực tế cao. Đảm bảo cung cấp đủ kiến thức, gắn liền với nhu cầu thực tiễn của sinh viên. Tuy nhiên, do vốn kiến thức còn nhiều hạn chế và khả năng tiếp thu thực tế còn nhiều bỡ ngỡ. Mặc dù em đã cố gắng hết sức nhưng chắc chắn bài tiểu luận khó có thể tránh khỏi những thiếu sót và nhiều chỗ còn chưa chính xác, kính mong thầy xem xét và góp ý để bài tiểu luận của em được hoàn thiện hơn. Em xin chân thành cảm ơn!

2

m=06 1=1 2=4 3=2 4=6 Câu 1(3 điểm): m=6 a) Dùng thuật toán Euclid để tính gcd (293, m+99) and lcm (293, m+99). Ví dụ m = 10 thì bạn cần tính gcd (293, 109) and lcm(293,109). b) Xác định 3 cặp nghiệm nguyên của phương trình: 293 x + (m+99)y =1 Ví dụ m = 10 thì phương trình là 293 x + 109 y = 1 a) m=6  gcd(293,105) Sử dụng thuật toán Euclid để tính gcd(293,105) 293=105×2+83

gcd(105,8 3)

105=83×1+22

gcd(83,22 )

83=22×3+17

gcd(22,17 )

22=17×1+5

gcd(17,5)

17=5×3+2

gcd(5,2)

5=2×2+1

gcd(2,1)

2=1×2+0

gcd(1,0)

gcd(293,105)= 1 lmc(293,105) Ta có:293=293 105 = 105 Mà gcd(293,105)=1 Nên lcm(293,105)=293×105=30765 3

Tính chất : Cho a, b là 2 số nguyên mà a hoặc b khác không, d =gcd(a;b).

4

-

gcd(a,0) = a gcd(a,b) = gcd(b,r), với r là số dư của a chia b.(a%b)

 Luôn tồn tại một số nguyên x, y sao cho ax + by = d b) Xét 3 cặp nghiệm nguyên : 293x+105y=1  Ta có gcd(293,105)=1 Vì vậy: 1= 5–2×2 =5 +2×(–2) =5+(17–5×3) × (–2) =17×(–2)+5×7 =17×(–2)+(22–17)×7 =22×7+17×(–9) =22×7+(83– (22×3))×( –9) =83×(–9)+22×34 =83×(–9)+(105–83)×34 =105×34+83×(–43) =105×34+(293– (105×2)) ×(–43) =293×(–43)+105×120 Vậy  1=293×(–43)+105×120 Qua đó ta có thể biết được cặp nghiệm thứ nhất (x,y)=( –43,120) Tính chất 2:Có nhiều cặp nghiệm x,y thoả mãn phương trình ax+by=d.Khi cặp nghiệm x,y được tìm thấy thì các cặp nghiệm khác được tính như sau(� + là một số nguyên tố bất kỳ Qua tính chất 2:

a=293; b=105; x= –43; y=120; d=1. 5

��

,�−

�

��

)trong đó k

�

Họ nghiệm của phương trình là ( –43 +105k , 120 – 293k)

6

Đặt k = 1 thì ta có cặp nghiệm thứ 2 là (–43 + 105 × 1 , 120 – 293 × 1) = (62 , –173) Đặt k = 2 thì ta có cặp nghiệm thứ 3 là (–43 + 105 × 2 , 120 – 293 × 2) = (163,–466) (– 43 , 120) Ta có 3 cặp nghiệm nguyên sau :{ (62 , – 173) (163, – 466)

Câu 2(3 điểm): Giải hệ thức truy hồi có dạng �� = � . ��−1 + � . ��−2 với A=�1,= =B =2, �0 = �3và 1 = �4Phương trình kết quả viết ở dạng rút gọn. Không thực hiện phép tính nếu kết quả ra số thập phân. Ví dụ � 1 = 1, 2 = 7, 3 = 3, 4 = 5 thì cần giải hệ thức truy hồi có dạng �= ��−1 + 7��−2với 0 = 3 và 1 = 5 �� = . �

�−1+

.�

�−2 với A=1,

B=4, 0= 2và 1= 6

�2 = � + 4 � =

2

� − �−4=0 {

2

(2) nghiệm của phương trình là:

{ �=

Khi đó :: : �= � (

1+ √17

1− √17 2

� 1+√17 2 )

�0= 2 = � (

+� (

1+√17 2 )

1+√17

�1 = 6 = � (

2

0+

� (3) 1−√17 2 )

�

(

1

)+ �(

1−√17 2 )

1−√17 2

0 =C+D

1

) (5)

Nghiệm của hệ phương trình(4) và (5) là: C=

17+5 √17 17

√17−5

;� =

√17

Thay C và D vào phương trình(3): 7

(4)

�=

1+√17 2

�=

1−√17 2

an = C (

1+√17 2 )

n+

(

D

n (3) 1−√17 ) 2

8

��= (

1 + √17 √17 + 5 ) ( √17 2

�

� ) + ( √17 − 5 1 − √17 ) 2 √17 ) (

Diễn giải: Hệ thức truy hồi tuyến tính thuần nhất bậc 2 với hệ số hằng là hệ thứ truy hồi có dạng: �� = ���−1 + ���−2 (1) Với k là số nguyên A , B là hằng số thực với B≠0: “Bậc 2” nghĩa là biểu thức

� phụ

“Tuyến tính” nghĩa là 2 số hạng hồi và ở dạng luỹ thừa bậc 1

thuộc vào 2 số hạng

�−1 và �−2 xuất

�−1 và �−2,

hiện riêng biệt trong hệ thức truy

“Thuần nhất” nghĩa là tổng bậc của mỗi thứ hạng là giống nhau (không có số hạng bằng) “Hệ số hằng” nghĩa là A và B là hai số thực cố định, không phụ thuộc vào hệ số k Câu 3 (1 điểm): Hãy tạo ra dãy số giả ngẫu nhiên {��} với 0 < �� < m bằng cách dùng liên tiếp phép đồng dư ��+1 a =(a�+c) mod m. Với m = 9; a = �2; = c==4, �0 = =3. Ví dụ �1=1, 2=7, 3=3, 4=5 thì cần tạo ra dãy số từ �+1 7 =(7�+5) mod 9 với 0 =3 m=9 a=4    

c=6

�0 = 2

�1= 40 + 6 = 4×2 + 6 = 14 mod 9 =5 �2= 41 + 6 = 4×5 + 6 = 26 mod 9 =8 �3= 42 + 6 = 4×8 + 6 = 38 mod 9 =2 �4= 43 + 6 = 4×2 + 6 = 14 mod 9 =5

Vì �0 = �3 và vì mỗi số hạng chỉ phụ thuộc vào số hạng trước nó nên dãy sau sinh ra: 2 , 5 , 8 , 2 , 5. Vì các số được sinh ra bởi các phương pháp có hệ thống thực sự không ngẫu nhiên, nên chúng được gọi là các số giả ngẫu nhiên . -

Thủ tục thường dùng nhất để tạo các số giả ngẫu nhiên đó là phương pháp đồng dư tuyến tính. 9

-

Ta chọn 4 số nguyên , đó là mô đun m, nhân tử a, số gia c và số hạt giống 0, với 2 ≤ � ≤ � , 0 ≤ � < � và 0 < �� < �.

10

-

Chúng ta sẽ tạo ra dãy các số giả ngẫu nhiên {��} với 0 < �� < � với mọi n bằng cách dùng liên tiếp phép đồng dư.

Câu 4(3 điểm): Trình bày cách mã hóa và giải mã của Caesar cho nội dung sau “Discrete Mathematics course teach students how to think logically and mathematically ” với f(p)= (p + k) mod 26. trong đó k = 4. Ví dụ �4=5 thì f(p)= (p + 5) mod 26 Phương pháp mã hóa của Caesar và tổng quát hóa của phương pháp đó tiến hành bằng cách thay mỗi chữ trong bảng chữ cái bảng một chữ cái khác thuộc bảng đó. Các phương pháp mã hóa thuộc loại này đều dễ bị khám phá bàng cách dựa vào tần xuất xuất hiện của các chữ cái trong bức thư. Các phương pháp mà hóa tinh xảo hơn dựa trên viêc thay một khối chừ cái này hàng một khối chữ cái khác. Có một số kỹ thuật dựa trên số học đồng dư để mã hóa một khối các chữ cái. Đối với bảng mã tiếng anh (ABCDEFGHI...), nếu độ dịch là 3, A sẽ được thay bằng D, B sẽ được thay bằng E, ..., W sẽ thay bằng Z, X sẽ thay bằng A, Y sẽ thay bằng B và Z thay bằng C. Phương pháp được đặt tên theo Caesar, vị hoàng đế đã sử dụng nó thường xuyên trong công việc. Không gian bản rõ P là các từ cần được mà hóa được tạo từ bảng chữ cái A. Không gian bản rỏ C là các từ đã được mã hóa. Mã hoá cũng có thể được biểu diễn thông qua số học mô-đun. Mã hoá 1 chữ cái x bằng phép dịch chuyển n vị trí có thể được mô tả bằng biểu thức toán học sau: ��(�) = (� + �)mod 26 (1) Vậy (1) với f(p)=(p+k)mod 26  k = n mà k = 6 nên dịch bảng chữ cái qua 6 vị trí. Bảng chữ cái:

A,B,C,D,E,F,G,H,I,J,K,L,M,N,O,P,Q,R,S,T,U,V,W,X,Y,Z

Bảng chữ cái đã được mã hoá:G,H,I,J,K,L,M,N,O,P,Q,R,S,T,U,V,W,X,Y,Z, A,B,C,D,E,F “Discrete Mathematics course teach students how to think logically and mathematically ” thành“Joyixkzk Sgznksgzoiy iuaxyk zkgin yzajktzy nuc zu znotq rumoigrre gtj sgznksgzoigrre”

11...