1
S
ố hóa bởi Trung tâm Học liệu ĐẠI HỌC THÁI NGUYÊN
TRƢỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN VÀ TRUYỀN THÔNG Nguyễn Văn Kiên
LÝ THUYẾT LẬP LỊCH VÀ ỨNG DỤNG GIẢI QUYẾT BÀI
TOÁN LẬP LỊCH CHO CPU
LUẬN VĂN THẠC SĨ KHOA HỌC MÁY TÍNH
2
LỜI CAM ĐOAN
Em xin cam đoan luận văn tốt nghiệp: “Lý thuyết lập lịch và ứng dụng giải
quyết bài toán lập lịch cho CPU” do em tự thực hiện dƣới sự hƣớng dẫn của thầy giáo
Vũ Vinh Quang. Các kết quả và số liệu hoàn toàn trung thực.
Ngoài các tài liệu tham khảo đã dẫn ra ở cuối luận văn em đảm bảo rằng không
sao chép các công trình hay luận văn tốt nghiệp của ngƣời khác. Nếu phát hiện có sự
sai phạm với điều cam đoan trên, em xin hoàn toàn chịu trách nhiệm.
4
S
húa bi Trung tõm Hc liu MC LC
LI CM N 1
LI CAM OAN 3
MC LC 4
LI NểI U 6
CHNG 1 8
MT S KIN THC C BN V THUT TON V PHC TP THUT
TON 8
1.1. Khỏi nim c bn 8
1.1.1. Thut toỏn 8
1.1.2. Khái niệm về độ phức tạp thuật toán. 8
1.1.3. Cỏch tớnh phc tp 12
1.2. Vn phõn lp cỏc bi toỏn 13
1.2.1. Tng quan v s phõn lp cỏc bi toỏn 13
1.2.2. Khỏi nim dn v c 16
1.3. Lp cỏc bi toỏn P v NP 16
KẾT QUẢ CÀI ĐẶT MỘT SỐ THUẬT TOÁN LẬP LỊCH CPU 51
3.1. Giới thiệu sơ lƣợc về ngôn ngữ lập trình C# và công cụ lập trình Visual Studio. 51
3.1.1.Giới thiệu về ngôn ngữ lập trình C# 51
3.1.2. Giới thiệu về công cụ lập trình Visual Studio 54
3.2. Phân tích thuật toán cài đặt CPU 56
3.2.1. Thuật toán FCFS 56
3.2.2 Thuật toán SJF 57
3.2.3. Thuật toán RR 59
3.2.4. Sơ đồ thuật toán CPU 60
3.3. Kết quả cài đặt thuật toán CPU 60
3.3.1. Các thành phần của chƣơng trình 60
3.3.2. Cấu trúc chi tiết 61
3.3.3. Sử dụng chƣơng trình. 63
KẾT LUẬN 66
TÀI LIỆU THAM KHẢO 67
PHỤ LỤC 68
I. Thuật toán cài đặt 68
II. Các hàm và phƣơng thức cơ bản của chƣơng trình. 77
6
S
ố hóa bởi Trung tâm Học liệu LỜI NÓI ĐẦU
Máy tính điện tử ra đời vào những năm 40 của thế kỷ XX. Ban đầu, phạm vi sử
dụng máy tính còn rất hẹp, đa phần chỉ nhằm phục vụ mục đích nghiên cứu khoa học.
Hơn nữa, để vận hành hệ thống cần phải sử dụng các công cụ phần cứng đặc biệt và
thao tác vận hành rất phức tạp.
Cùng phát triển song song với sự phát triển của kỹ thuật điện tử, các thế hệ máy
Chƣơng 3: Đƣa ra kết quả cài đặt các thuật toán lập lịch cho CPU trên nền ngôn
ngữ Visual Studio 10.
Nội dung đề tài là một lĩnh vực rộng và khó, với khoảng thời gian không nhiều
cùng với kiến thức của bản thân còn hạn chế, trong đề tài này mới chỉ đề cập đến việc
nghiên cứu thuật toán lập lịch chủ yếu là trên một máy và ứng dụng cho lập lịch CPU.
8
S
húa bi Trung tõm Hc liu CHNG 1
MT S KIN THC C BN V THUT TON
V PHC TP THUT TON
S
ố hóa bởi Trung tâm Học liệu + Với thuật toán tựa Algol: Chi phí thời gian là số các phép tính cơ bản cần thực
hiện trong quá trình tính toán.
- Chi phí không gian chính là số ô nhớ cần để thực hiện hoàn chỉnh trong quá
trình tính toán.
Gọi A là một thuật toán tƣơng ứng với một mô hình tính toán, gọi e là bộ dữ liệu
vào đã đƣợc mã hóa theo cách nào đó. Khi đó thuật toán A tính trên bộ dữ liệu e cần
phải trả về giá thời gian và giá không gian trong đó ta kí hiệu
+
()
A
te
là giá phải trả về thời gian tính toán
+
()
A
le
là giá về không gian của bộ nhớ cần thiết sử dụng
Khi đó tổng giá phải trả của thuật toán A tính trên bộ dữ liệu e chính bằng :
T(A)=
()
A
te
+
()
A
le
có tốc độ tăng là O(f(n))
10
S
ố hóa bởi Trung tâm Học liệu
11
S
ố hóa bởi Trung tâm Học liệu Độ phức tạp đa thức (Polynomial)
Thuật toán đƣợc gọi là có độ phức tạp đa thức nếu tồn tại đa thức P(n) mà
0
( ) . ( ),
A
T n C P n n N£ " ³
.
Thuật toán đa thức
Thuật toán đƣợc gọi là đa thức nếu độ phức tạp về thời gian trong trƣờng hợp
xấu nhất của nó là đa thức.
Việc đánh giá đúng độ phức tạp của bài toán là một vấn đề hết sức phức tạp. Vì
vậy ngƣời ta thƣờng quan tâm đến việc đánh giá độ phức tạp thời gian trong trƣờng
hợp xấu nhất của bài toán.
Một số quy ước kí hiệu về độ phức tạp thuật toán
Kí hiệu
Độ phức tạp
Độ phức tạp giai thừa
Copyright: Tài liệu đại học ©