LÝ THUYẾT ĐỘ PHỨC TẠP VÀ ỨNG DỤNG.doc

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 II. LÝ THUYẾT ĐỘ PHỨC TẠP

2.1 Máy tính Turing tất định

2.1.1 Định nghĩa

2.1.2 Cấu tạo

2.1.3 Hoạt động

2.2 Máy tính Turing không tất định

2.1.1 Định nghĩa

2.1.2 Cấu tạo

2.1.3 Hoạt động

2.3 Các bài toán quyết định

2.4 Các bài toán lớp P, NP và mối quan hệ giữa lớp P và lớp NP

2.4.1 Các bài toán lớp P

2.4.2 Các bài toán lớp NP

2.4.3 Mối quan hệ giữa lớp P và lớp NP

Sinh viên thực hiện: Lưu Thị Lan Hương K54A-CNTT-DHSPHN 2