Báo cáo nghiên cứu khoa học GVHD: PGS.TS Vũ Đình Hoà
TRƯỜNG ĐẠI HỌC SƯ PHẠM HÀ NỘI
KHOA CÔNG NGHỆ THÔNG TIN
BÁO CÁO KHOA HỌC
ĐỀ TÀI:
LÝ THUYẾT ĐỘ PHỨC TẠP VÀ ỨNG DỤNG
Chuyên ngành : Khoa học máy tính
Giáo viên hướng dẫn : PGS.TSKH.Vũ Đình Hòa.
Sinh viên thực hiện: Lưu Thị Lan Hương
Lớp _K54A.
Hà Nội , 4/2008.
Sinh viên thực hiện: Lưu Thị Lan Hương K54A-CNTT-DHSPHN
1
Báo cáo nghiên cứu khoa học GVHD: PGS.TS Vũ Đình Hoà
CHƯƠNG MỞ ĐẦU
1. Tên đề tài
2. Lý do chọn đề tài
3. Mục đích, nhiệm vụ của đề tài
CHƯƠNG I. TỔNG QUAN VỀ THUẬT TOÁN
1.1 Định nghĩa thuật toán
1.2 Các đặc trưng của thuật toán
1.3 Phân tích thuật toán và đánh giá thời gian thực hiện thuật toán
1.3.1 Phân tích thuật toán
1.3.2 Tại sao lại cần có thuật toán hiệu quả
1.3.3 Các bước phân tích thuật toán
1.3.4 Tính hiệu quả của thuật toán
1.3.5 Đánh giá thời gian thực hiện thuật toán
1.4 Các vấn đề liên quan đến thuật toán
1.4.1 Thiết kế thuật toán
1.4.2 Tính đúng đắn của thuật toán
1.4.3 Biểu diễn thuật toán

CHƯƠNG III. MẬT MÃ VÀ MẬT MÃ KHOÁ CÔNG KHAI RSA
I. Mật mã
1. Định nghĩa về mật mã và hệ mật mã
1.1 Một số khái niệm trong mật mã
1.2 Định nghĩa về hệ mật mã
2.Một số yêu cầu đối với hệ mật mã
II. Mật mã khoá công khai RSA
1. Đặt vấn đề
2. Giải thuật RSA
2.1 Chọn khoá
2.2 Mã hoá
2.3 Giải mã
2.4 Ví dụ minh hoạ
3. Ðộ an toàn của hệ RSA
4. Ứng dụng của hệ mật mã RSA
5. Chữ ký điện tử
5.1 Giới thiệu về chữ ký điện tử và vấn đề xác nhận
5.2 Sơ đồ chữ ký RSA
5.3 Tấn công chữ ký điện tử
CHƯƠNG IV. DEMO VỚI RSA
Sinh viên thực hiện: Lưu Thị Lan Hương K54A-CNTT-DHSPHN
3
Báo cáo nghiên cứu khoa học GVHD: PGS.TS Vũ Đình Hoà
CHƯƠNG MỞ ĐẦU
1.Tên đề tài:
LÝ THUYẾT ĐỘ PHỨC TẠP VÀ ỨNG DỤNG
2.Lý do chọn đề tài
Trong mọi thời đại thông tin đều có ý nghĩa không thể thiếu đối với con
người cùng với các hoạt động kinh tế, chính trị và xã hội. Đặc biệt ở thế kỷ 21, thế
kỷ công nghệ thông tin, thông tin được khai thác triệt để, nó đóng vai trò ngày càng

hoặc hành động cần thực hiện… để cho ta lời giải của bài toán
1.2 Các đặc trưng của thuật toán
1.2.1 Đầu vào (Input)
Đầu vào của thuật toán chính là các giá trị cần đưa vào khi thuật toán bắt đầu làm
việc. Các giá trị này cần được lấy từ các tập hợp giá trị cụ thể nào đó.
1.2.2 Đầu ra (Output)
Mỗi thuật toán có một hoặc nhiều dữ liệu ra. Đó là các dữ liệu có quan hệ hoàn
toàn xác định với các dữ liệu vào, và là kết quả của sự thực hiện thuật toán.
1.2.3 Tính xác định
Ở mỗi bước, các thao tác phải rõ ràng, không gây nên sự nhập nhằng. Nói rõ hơn
là trong cùng một điều kiện, hai bộ xử lí cùng thực hiện một thuật toán phải cho cùng
một kết quả như nhau.
1.2.4 Tính khả thi
Tất cả các phép toán có mặt trong thuật toán phải đủ đơn giản. Điều đó có nghĩa
là, các phép toán có thể được thực hiện trực tiếp (bằng giấy và but).
1.2.5 Tính dừng
Với mọi bộ dữ liệu đầu vào(lấy từ các tập của dữ liệu vào), thuật toán phải dừng sau
một số hữu hạn bước thực hiên.
1.2.6 Tính đơn trị (uniqueness)
Các giá trị trung gian của thuật toán trong từng bước và kết quả thực hiện thuật
toán được xác định một cách đơn trị và chỉ phụ thuộc vào đầu vào và kết quả của các
bước trước.
1.2.7 Tính tổng quát (generality)-Tính phổ dụng
Với mọi tập đầu vào thuộc dạng của bài toán thuật toán đều có thể giải được. Tức
là thuật toán phải dùng để giải được một lớp các bài toán cùng loại.
1.3 Phân tích thuật toán và đánh giá thời gian thực hiện thuật toán
1.3.1 Phân tích thuật toán
Sinh viên thực hiện: Lưu Thị Lan Hương K54A-CNTT-DHSPHN
5
Báo cáo nghiên cứu khoa học GVHD: PGS.TS Vũ Đình Hoà

Sinh viên thực hiện: Lưu Thị Lan Hương K54A-CNTT-DHSPHN
6
Báo cáo nghiên cứu khoa học GVHD: PGS.TS Vũ Đình Hoà
Nếu thời gian thực hiện một giải thuật là T(n) = cn
2
(với c là hằng số) thì ta nói:
Độ phức tạp về thời gian của giải thuật này có cấp là n
2
(hay cấp độ lớn của thời gian
thực hiện giải thuật là n
2
) và ta ký hiệu
T(n) = O(n
2
) (ký hiệu chữ O lớn)
Một cách tổng quát có thể định nghĩa:
Một hàm f(n) được xác định là O(g(n))
f(n) = O(g(n)) và được gọi là cấp g(n) nếu tồn tại các hằng số c và n
0
sao
cho:
f(n) ≤ cg(n) khi n ≥ n
0
nghĩa là f(n) bị chặn trên bởi một hằng số nhân với g(n), với mọi giá trị của n từ một
điểm nào đó. Thông thường các hàm thể hiện độ phức tạp về thời gian của giải thuật có
dạng: log
2
n, n, nlog
2
n, n

2
n, n, nlog
2
n,
n
2
,n
3
được gọi là các hàm loại đa thức. Giải thuật với thời gian thực hiện có cấp hàm đa
thức thì thường chấp nhận được.
1.3.4.2 Xác định độ phức tạp về thời gian
* Quy tắc tổng: Giả sử T
1
(n) và T
2
(n) là thời gian thực hiện hai đoạn chương
trình P
1
và P
2
mà T
1
(n) = O(f(n)); T
2
(n) = O(g(n)) thì thời gian thực hiện P
1
và P
2
kế tiếp
nhau sẽ là:

Một ứng dụng khác của quy tắc này là nếu g(n) ≤ f(n) với mọi n ≥ n
0
thì O(f(n) +
g(n)) cũng là O(f(n)). Chẳng hạn: O(n
4
+ n
2
) = O(n
4
) và O(n+log
2
n) = O(n).
* Quy tắc nhân: Nếu tương ứng với P
1
và P
2
là T
1
(n) = O(f(n)), T
2
(n) = O(g(n))
thì thời gian thực hiện P
1
và P
2

lồng nhau sẽ là:
T
1
(n)T

chính xác của thuật toán thì để biểu diễn thuật toán người ta thường dùng các cách sau:
Liệt kê từng bước, dùng sơ đồ khối, dùng ngôn ngữ lập trình(thường là giả mã lệnh)
Sinh viên thực hiện: Lưu Thị Lan Hương K54A-CNTT-DHSPHN
8
Báo cáo nghiên cứu khoa học GVHD: PGS.TS Vũ Đình Hoà
CHƯƠNG II
LÝ THUYẾT ĐỘ PHỨC TẠP
Máy tính Turing
Máy tính Turing là một máy tính toán trừu tượng, vừa có khả năng của máy tính
thực sự, vừa cho phép định nghĩa về mặt toán học về những gì có thể tính toán được
2.1 Máy tính Turing tất định
2.1.1 Định nghĩa
Máy Turing tất định là một bộ M = (Σ, A , δ
1
, δ
2
, δ
3
, q
0
,  , q
r
) trong đó
Σ: Là bảng chữ cái
A: Tập hữu hạn trạng thái bên trong
δ
1
:

Là hàm kí tự

2.1.2 Cấu tạo
Máy tính Turing tất định là một máy trừu tượng bao gồm:
- Một bảng chữ cái Σ
- Băng vô hạn có thể mở rộng về một phía hoặc cả hai phía. Trên băng
được chia thành các ô chứa một kí hiệu lấy từ bảng chữ cái Σ
- Một tập trạng thái bên trong A
- Một đầu đọc ghi luôn đặt vào một ô trên băng và ta nói đầu đọc ghi đang
nhìn ô đó. Đầu đọc ghi này có thể di chuyển mỗi lần một ô (về cả hai phía trên băng). Tại
một ô có thể đọc hay ghi một kí tự vào ô đó
- Một bộ điều khiển có thể ở bất kì trạng thái nào trong một tập hữu hạn
trạng thái, trong đó có một trạng thái ban đầu và một trạng thái kết thúc
Sinh viên thực hiện: Lưu Thị Lan Hương K54A-CNTT-DHSPHN
9
Báo cáo nghiên cứu khoa học GVHD: PGS.TS Vũ Đình Hoà
Máy Turing tất định
1.2.3 Hoạt động
- Đầu đọc ghi đọc kí tự trên ô của băng, phụ thuộc vào trạng thái bên trong mà
đầu đọc viết một kí tự thuộc (Σ ∪  ) lên ô
- Đầu đọc ghi dịch chuyển một ô sang phải, sang trái hoặc là đứng yên tại chỗ
- Trạng thái bên trong được được thay đổi tuỳ thuộc vào kí hiệu được đọc và trạng
thái ban đầu
Điều đáng ngạc nhiên là máy Turing làm được tất cả những việc mà các máy tính
khác làm được
Máy tính Turing có thể có nhiều băng nhưng nó không làm được gì nhiều hơn
máy tính Turing một băng (tương đương với máy tính một băng)
2.2 Máy tính Turing không tất định
2.1.1 Định nghĩa
Máy Turing không tất định là một bộ M = (Σ, A , δ
1
, δ

10
Báo cáo nghiên cứu khoa học GVHD: PGS.TS Vũ Đình Hoà
δ
2
:

Là hàm trạng thái
δ
3
: (Σ ∪ { }) × A → A
q
0
: Trạng thái ban đầu (q
0
∈ A)
q
r
: Trạng thái kết thúc (q
r
∈ A)
 : Ký tự rỗng
2.1.2 Cấu tạo
Máy tính Turing tất định là một máy trừu tượng bao gồm:
- Một bảng chữ cái Σ
- Băng vô hạn có thể mở rộng về một phía hoặc cả hai phía. Trên băng
được chia thành các ô chứa một kí hiệu lấy từ bảng chữ cái Σ
- Một tập trạng thái bên trong A
- Một đầu đọc ghi luôn đặt vào một ô trên băng và ta nói đầu đọc ghi đang
nhìn ô đó. Đầu đọc ghi này có thể di chuyển mỗi lần một ô (về cả hai phía trên băng). Tại
một ô có thể đọc hay ghi một kí tự vào ô đó