ĐẠI HỌC ĐÀ NẴNG
TRƯỜNG ĐẠI HỌC SƯ PHẠM
KHOA TIN HỌC
  
GIÁO TRÌNH
TIN HỌC ĐẠI CƯƠNG
TIN HỌC ĐẠI CƯƠNG
(Cho các lớp chuyên tin)
Biên soạn: Đinh thị Đông Phương
Đại Học Sư Phạm
Khoa Tin Học
Đà Nẵng, 2005
Trang 2
Đại Học Sư Phạm
Khoa Tin Học
MỤC LỤC
Chương 1: MÁY TÍNH VÀ BIỂU DIỄN THÔNG TIN TRONG MÁY TÍNH............4
1. Thông tin và tin học.........................................................................................................4
2. Lịch sử máy tính...............................................................................................................4
3. Phân loại máy tính............................................................................................................4
4. Hệ đếm...............................................................................................................................5
5. Biểu diễn thông tin trong máy tính................................................................................7
6. Giải bài toán trên máy tính...........................................................................................11
Chương 2: CẤU TRÚC MÁY TÍNH...............................................................................23
1. Máy tính là gì?................................................................................................................23
2. Mô hình cấu trúc cơ bản của một máy vi tính............................................................24
3. Central Processing Unit (CPU).....................................................................................24
4. Computer Memory.........................................................................................................25
5. Computer Bus.................................................................................................................25
6. Thiết bị ngoại vi..............................................................................................................26
7. Phần mềm máy tính.......................................................................................................27

1. Thông tin và tin học
Dữ liệu (Data) chưa mang lại hiểu biết về đối tượng
Thông tin (Information): dữ liệu sau khi được xử lý, cho ta hiểu biết về đối tượng
Ví dụ:
- Ảnh mây vệ tinh: Dữ liệu
- Bản tin dự báo thời tiết: Thông tin
Tin học: Là ngành khoa học nghiên cứu các vấn đề thu thập và xử lý dữ liệu để có được
thông tin mong muốn, sử dụng máy tính như một công cụ hỗ trợ chính.
2. Lịch sử máy tính
Chúng ta có thể điểm qua một số mốc chính và các tên tuổi trong tiến trình phát triển của
máy tính:
• 1937, Turing, khái niệm về các con số tính toán và máy Turing.
• 1943-1946, ENIAC
o Máy tính điện tử đa chức năng đầu tiên.
o J.Mauchly & J.Presper Eckert.
• 1945, John Von Neumann đưa ra khái niệm về chương trình được lưu trữ.
• 1952, Neumann IAS parallel-bit machine.
• 1945 – 1954, thế hệ 1 (first generation)
o Bóng đèn chân không (vacuum tube)
o Bìa đục lỗ
o ENIAC: 30 tấn, 18.000 bóng đèn, 100.000 phép tính/giây.
• 1955-1964, thế hệ 2
o Transitor
o Intel transitor processor
• 1965-1974, thế hệ 3
o Mạch tích hợp (Intergrated Circuit – IC)
• 1975, Thế hệ 4
o LSI (Large Scale Integration), VLSI (Very LSI), ULSI (Ultra LSI).
3. Phân loại máy tính
Tùy theo hình thức và mục đích sử dụng máy tính có thể được phân thành các loại như

0
= a
n
.10
n
+ a
n-1
.10
n-1
+…+ a
0
.10
0
Ví dụ: 123 = 1.10
2
+ 2.10
1
+3.10
0
Ta viết một số trong hệ đếm cơ số 10 ví dụ số “2005” là 2005 hoặc 2005
10
4.3. Hệ đếm cơ số a bất kỳ
Sử dụng a ký hiệu để biểu diễn.
- Ký hiệu có giá trị nhỏ nhất là ‘0’
- Ký hiệu có giá trị lớn nhất là ‘a-1’
Một số N trong hệ cơ số a ký hiệu N
a
và:
Được biểu diến: N
a

.a
-1
+… +b
-m
.a
-m
.
Ở đây các chử số ở phần thập phân được đánh số âm (-1,-2,…,-m).
4.4. Hệ đếm cơ số 2
Hệ đếm cơ số 2 hay hệ nhị phân (Binary) sử dụng 2 ký hiệu 0 và 1 để biểu diễn các
số.
Hệ đếm này được sử dụng để biểu diễn thông tin trong máy tính vì
Các linh kiện điện tử chỉ có hai trạng thái:
- Đóng hoặc mở (công tắc).
- Có điện hoặc không có điện.
Do đó chỉ cần sử dụng 2 ký hiệu để biểu diễn
Một số nhị phân ‘0’, hoặc ‘1’ tương ứng với một BIT (BInary digiT).
Ta viết số nhị phân như sau: 1001
2
hoặc 1001
B
4.4.1. Chuyển từ hệ 2 sang hệ 10
Để chuyển các số từ hệ 2 sang hệ 10 ta áp dụng quy tắc biểu diễn số ở cơ số 2 ở trên:
(a
n
a
n-1
…a
0
)

Ta có quy tắc chuyển một số từ hệ 10 sang hệ 2 như sau:
- Gọi D = số cần chuyển
- Chia D (chia nguyên) liên tục cho 2 cho tới khi kết quả phép chia = 0
- Lấy phần dư các lần chia viết theo thứ tự ngược lại.
Như ví dụ trên số 11
10
sẽ tương ứng với số 1011
B
Trang 5
Đại Học Sư Phạm
Khoa Tin Học
4.4.3. Chuyển đổi số lẻ thập phân từ hệ 10 sang hệ 2
Để chuyển đổi các số có phần lẻ thập phân (Ví dụ: 12,73) ta có quy tắc sau:
• Phần nguyên:
- Chia liên tiếp cho 2.
- Viết phần dư theo chiều ngược lại.
• Phần thập phân
- X = phần thập phân.
- Nhân X với 2 ta có kết quả:
Phần nguyên là một trong 2 số (0,1)
Còn lại phần thập phân
- Lặp lại từ bước đầu, đến khi muốn dừng hoặc kết quả=0.
- Viết các phần nguyên theo đúng thứ tự được kết quả.
4.4.4. Các phép toán trên hệ cơ số 2
• Cộng hai số nhị phân
Cộng có nhớ các cặp số cùng vị trí từ phải sang trái
Bảng cộng:
Ví dụ: 1010
B
+ 1111

F
H
= 1111
B
Xem bảng chuyển đổi các hệ

• Chuyển đổi hệ 16 sang hệ 2
Căn cứ vào bảng chuyển đổi, thay thế 1 chữ số của số hệ 16 bằng 4 bit nhị phân.
Ví dụ:
A
H
= 1100
B
7
H
= 0111
B
A7
H
= 1100 0111
B
5. Biểu diễn thông tin trong máy tính
5.1. Cách biểu diễn
Thông tin trong máy tính biểu diễn dưới dạng nhị phân.
Ví dụ:
Trang 7
Đại Học Sư Phạm
Khoa Tin Học
- 5 bit biểu diễn được 32 trạng thái
- 5 bit có thể dùng để biểu biểu diễn 26 ký tự…

Các ký tự từ 0à31,127: Các ký tự điều khiển
32à126: Các ký tự thông thường
128à255: Các ký tự đặc biệt
b. Mã Unicode
Sử dụng nhiều hơn 8 bit để mã hoá ký tự. Với 2 Bytes Unicode có thể mã hoá được
216 = 65536 ký tự. Do đó bảng mã có thể mã hóa được hầu hết các chữ cái của các
nước trên thế giới như: Việt Nam, Trung Quốc, Nga, Thái …
Trang 8
1Byte 8 BIT
1KB 2
10
Bytes = 1024 Bytes
1MB 1024 KB
1GB 1024 MB
Đại Học Sư Phạm
Khoa Tin Học
5.3.3 Biểu diễn số
Số được biểu diễn ở dạng nhị phân. Có các phương pháp biểu diễn sau:
a. Phương pháp dấu lượng (sign - magnitude)
Theo cách biểu diễn này, bit cực trái được dùng làm bit dấu (1 là dấu + và 0 là dấu -) các
bit còn lại biểu diễn độ lớn của số.
Ví dụ: Với mẫu là 4 bit thì các số biểu diễn như sau:
Mẫu bit Giá trị được biểu diễn
1111 7
1110 6
1101 5
1100 4
1011 3
1010 2
1001 1

Đại Học Sư Phạm
Khoa Tin Học
Biểu diễn số bù 2 qua mẫu 4 bit
Mẫu bit Giá trị được biểu diễn
0111 7
0110 6
0101 5
0100 4
0011 3
0010 2
0001 1
0000 0
1111 -1
1110 -2
1101 -3
1100 -4
1011 -5
1010 -6
1001 -7
1000 -8

** Thực chất số biểu diễn dưới dạng bù 2 là số biểu diễn ở bù 1 sau đó ta cộng thêm 1.
Ví dụ:
Số -6 có biểu diễn bù 1 là 1001 nếu ta lấy số bù 1 này cộng thêm 1 thì kết quả là
1001 + 1 = 1010 đây chính là dạng bù 2
Hình vẽ sau sẽ minh hoạ biểu diễn số bù 2 cho số -6:
nếu biểu diễn nhị phân của 6 là 0 1 1 0
thì biểu diễn số bù 1 của -6 sẽ là 1 0 0 1
cộng thêm 1 + 1
thì biểu diễn số bù 2 của -6 sẽ là = 1 0 1 0

số bù 2 ta lại dùng mẫu 5 bit chứ không là 4 bit? Ý nghĩa của lỗi tràn số đã giới thiệu ở
các các phần trước, đó là hiện tượng xảy ra khi số cần biểu diễn vượt quá số bit cho trước
để biểu diễn nó.
Ví dụ:
nếu ở ví dụ 2 ta dùng mẫu 4 bit cho biểu diễn bù 2 cho -6 và -4, khi đó bài toán
được thực hiện như sau:
-6 biểu diễn ở bù 2 với mẫu 4 bit là 1010
-4 biểu diễn ở bù 2 với mẫu 4 bit là 1100
Kết quả phép cộng ở dạng bù 1 là 0110 là biểu diễn của +6, do đó kết quả bị sai.
Nguyên nhân là do ta lấy số lượng bit để biểu diễn quá ít nên xảy ra lỗi tràn số.
Do đó người sử dụng máy tính phải lường trước được tình huống này khi muốn lưu trữ
dữ liệu, để khắc phục ta tăng số lượng bit nhiều hơn thì sẽ không gây hiện tượng tràn. Ví
dụ với mẫu 32 bit thì giá trị dương lớn nhất là 2147483647.
⊕ Tổng quát ta có số ở phép biểu diễn bù 1 và bù 2 thì giá trị dương lớn nhất cho phép
khi dùng mẫu n bit là: 2
n-1
-1 và giá trị âm nhỏ nhất là -2
n-1

6. Giải bài toán trên máy tính
6.1 Thuật toán
Thuật toán là một khái niệm cơ sở của Toán học và Tin học. Hiểu một cách đơn
giản, thuật toán là một tập các hướng dẫn nhằm thực hiện một công việc nào đó. Ðối với
việc giải quyết một vấn đề - bài toán thì thuật toán có thể hiểu là một tập hữu hạn các
hướng dẫn rõ ràng để người giải toán có thể theo đó mà giải quyết được vấn đề. Như
vậy, thuật toán là một phương pháp thể hiện lời giải của vấn đề - bài toán.
Việc nghiên cứu về thuật toán có vai trò rất quan trọng trong khoa học máy tính vì
máy tính chỉ giải quyết được vấn đề khi đã có hướng dẫn giải rõ ràng và đúng. Nếu
hướng dẫn giải sai hoặc không rõ ràng thì máy tính không thể giải đúng được bài toán.
Trang 11

Trường hợp có nhiều học sinh đồng hạng nhất thì chọn học sinh có điểm môn Toán cao
nhất làm lớp trưởng.
Nếu vẫn còn nhiều hơn một học sinh đồng hạng nhất và có cùng điểm môn Toán
cao nhất thì tiến hành bốc thăm.
Ở đây chúng ta cần phân biệt mập mờ và sự chọn lựa có quyết định. Mập mờ là
thiếu thông tin hoặc có nhiều chọn lựa nhưng không đủ điều kiện để quyết định. Còn chọn
lựa có quyết định là hoàn toàn xác định duy nhất trong điều kiện cụ thể của vấn đề.
Chẳng hạn trong vấn đề chọn lớp trưởng ở trên, bước 3 thể hiện một sự lựa chọn có quyết
định. Tất nhiên, khi chưa lập danh sách, chưa xếp hạng theo điểm trung bình thì giáo viên
không thể biết được sẽ chọn lớp trưởng theo cách nào. Nhưng khi đã sắp xong danh sách
thì chỉ có một phương án chọn duy nhất.
Tính "thực thi được" cũng là một tính chất khá hiển nhiên. Rõ ràng nếu trong
"thuật toán" tồn tại một bước không thể thực thi được thì làm sao ta có được kết quả đúng
như ý muốn? Tuy nhiên, cần phải hiểu là "thực thi được" xét trong điều kiện hiện tại của
bài toán. Chẳng hạn, khi nói "lấy căn bậc hai của một số âm" là không thể thực thi được
nếu miền xác định của bài toán là số thực, nhưng trong miền số phức thì thao tác "lấy căn
bậc hai của một số âm" là hoàn toàn thực thi được. Tương tự, nếu ta chỉ đường cho một
người đi xe máy đến một bưu điện nhưng con đường ta chỉ là đường cụt, đường cấm hoặc
đường ngược chiều thì người đi không thể đi đến bưu điện được.
Tính "dừng" là tính chất dễ bị vi phạm nhất, thường là do sai sót khi trình bày
thuật toán. Dĩ nhiên, mọi thuật toán đều nhằm thực hiện một công việc nào đó nên sau
một thời gian thi hành hữu hạn thì thuật toán phải cho chúng ta kết quả mong muốn. Khi
Trang 12
Đại Học Sư Phạm
Khoa Tin Học
không thỏa tính chất này, ta nói rằng "thuật toán" bị lặp vô tận hoặc bị quẩn. Ðể tính tổng
các số nguyên dương lẻ trong khoảng từ 1 đến n ta có thuật toán sau:
B1. Hỏi giá trị của n.
B2. S = 0
B3. i = 1

bảo được tính chất này vì nó luôn giải được với mọi giá trị số thực a,b,c bất kỳ. Tuy
nhiên, không phải thuật toán nào cũng đảm bảo được tính tổng quát. Trong thực tế, có lúc
người ta chỉ xây dựng thuật toán cho một dạng đặc trưng của bài toán mà thôi.
6.1.1 Thuật toán giải phương trình bậc hai ax2 + bx + c = 0
1. Yêu cầu cho biết giá trị của 3 hệ số a, b, c
2. Nếu a = 0 thì
1. Yêu cầu đầu vào không đảm bảo.
2. Kết thúc thuật toán.
3. Trường hợp a khác 0 thì
3.1. Tính giá trị D = b
2
-4ac
3.2. Nếu D > 0 thì
3.2.1. Phương trình có hai nghiệm phân biệt x
1
và x
2
3.2.2. Giá trị của hai nghiệm được tính theo công thức sau
Trang 13
Đại Học Sư Phạm
Khoa Tin Học
a
b
x
2
1
∆+−
=
a
b

Giải thuật
1. Nếu chỉ có 1 hộp (n=1) thì
1.1. Hộp đó chính là hộp nặng nhất.
1.2. Kết thúc thuật toán.
2. Ngược lại nếu có từ hai hộp trở lên (n>1)
2.1. Chọn hai hộp bất kỳ và đặt lên bàn cân.
2.2. Giữ lại hộp nặng hơn, cất hộp nhẹ hơn sang chỗ khác.
3. Nếu còn hộp chưa được cân thực hiện các bước sau, nếu không còn hộp nào
nữa, sang bước 5.
3.1. Chọn một hộp bất kỳ và để lên dĩa cân còn trống.
3.2. Giữ lại hộp nặng hơn, cất hộp nhẹ hơn sang chỗ khác.
4. Trở lại bước 3.
5. Hộp còn lại trên cân chính là hộp nặng nhất. Kết thúc.

6.1.3 Thuật toán Euclid tìm ước số chung lớn nhất
Bài toán:Cho hai số nguyên dương a và b. Tìm ước số chung lớn nhất của a và b.
Giải thuật:
1. Yêu cầu cho biết giá trị của a, b.
2. a
0
= a
3. b
0
= b
4. i = 0
5. Nếu a
i
khác b
i
thì thực hiện các thao tác sau, ngược lại qua bước 7.

i-1
6. Trở lại bước 5
7. Ước số chung lớn nhất của a, b là a
i
6.2 Các phương pháp biểu diễn thuật toán
Khi chứng minh hoặc giải một bài toán trong toán học, ta thường dùng những ngôn từ
toán học như: "ta có", "điều phải chứng minh", "giả thuyết", ... và sử dụng những phép
suy luận toán học như phép suy ra, tương đương, ...Thuật toán là một phương pháp thể
hiện lời giải bài toán nên cũng phải tuân theo một số quy tắc nhất định. Ðể có thể truyền
đạt thuật toán cho người khác hay chuyển thuật toán thành chương trình máy tính, ta phải
có phương pháp biểu diễn thuật toán. Có 3 phương pháp biểu diễn thuật toán:
6.2.1 Ngôn ngữ tự nhiên
Trong cách biểu diễn thuật toán theo ngôn ngữ tự nhiên, người ta sử dụng ngôn ngữ
thường ngày để liệt kê các bước của thuật toán (Các ví dụ về thuật toán trong mục 1 của
chương sử dụng ngôn ngữ tự nhiên). Phương pháp biểu diễn này không yêu cầu người
viết thuật toán cũng như người đọc thuật toán phải nắm các quy tắc. Tuy vậy, cách biểu
diễn này thường dài dòng, không thể hiện rõ cấu trúc của thuật toán, đôi lúc gây hiểu lầm
hoặc khó hiểu cho người đọc. Gần như không có một quy tắc cố định nào trong việc thể
hiện thuật toán bằng ngôn ngữ tự nhiên. Tuy vậy, để dễ đọc, ta nên viết các bước con lùi
vào bên phải và đánh số bước theo quy tắc phân cấp như 1, 1.1, 1.1.1, ... Bạn có thể tham
khảo lại ba ví dụ trong mục 1 của chương để hiểu cách biểu diễn thuật toán theo ngôn ngữ
tự nhiên.
6.2.2 Lưu đồ - sơ đồ khối
Lưu đồ hay sơ đồ khối là một công cụ trực quan để diễn đạt các thuật toán. Biểu diễn
thuật toán bằng lưu đồ sẽ giúp người đọc theo dõi được sự phân cấp các trường hợp và
quá trình xử lý của thuật toán. Phương pháp lưu đồ thường được dùng trong những thuật
toán có tính rắc rối, khó theo dõi được quá trình xử lý.
Ðể biểu diễn thuật toán theo sơ đồ khối, ta phải phân biệt hai loại thao tác. Một thao tác là
thao tác chọn lựa dựa theo một điều kiện nào đó. Chẳng hạn: thao tác "nếu a = b thì thực
hiện thao tác B2, ngược lại thực hiện B4" là thao tác chọn lựa. Các thao tác còn lại không

∆ =
0
Đ
Có 2 nghiệm
phân biệt x
1
, x
2
∆ >
0
S
∆ =
0
Đ
Có 2 nghiệm
phân biệt x
1
, x
2
∆ = b
2
– 4ac
Nhập a, b, c
Bắt đầu
S
Có nghiệm
kép x
0
Đ
Vô nghiệm

f. Ðiểm nối sang trang (off-page connector)
Tương tự như điểm nối, nhưng điểm nối sang trang được dùng khi lưu đồ quá lớn, phải
vẽ trên nhiều trang. Bên trong điểm nối sang trang ta cũng đặt một ký hiệu để biết được
sự liên hệ giữa điểm nối của các trang.
Trang 17
S < a + b
S
S >
0
Đ
1
S
Đ
1
S < a + b
S
S >
0
Đ
S
Đ
#1
#1
Đại Học Sư Phạm
Khoa Tin Học
Ở trên chỉ là các ký hiệu cơ bản và thường được dùng nhất. Trong thực tế, lưu đồ còn có
nhiều ký hiệu khác nhưng thường chỉ dùng trong những lưu đồ lớn và phức tạp. Ðối với
các thuật toán trong cuốn sách này, ta chỉ cần sử dụng các ký hiệu trên là đủ.
6.2.3 Mã giả
Tuy sơ đồ khối thể hiện rõ quá trình xử lý và sự phân cấp các trường hợp của thuật toán

xuất kết quả: phương trình vô nghiệm
6.3 Độ phức tạp của thuật toán
Một chương trình máy tính thường được cài đặt dựa trên một thuật toán đúng để giải
quyết bài toán hay vấn đề. Tuy nhiên, ngay cả khi thuật toán đúng, chương trình vẫn có
thể không sử dụng được đối với một dữ liệu đầu vào nào đó vì thời gian để cho ra kết quả
là quá lâu hoặc sử dụng quá nhiều bộ nhớ (vượt quá khả năng đáp ứng của máy tính).
Khi tiến hành phân tích thuật toán nghĩa là chúng ta tìm ra một đánh giá về thời
gian và "không gian" cần thiết để thực hiện thuật toán. Không gian ở đây được hiểu là các
yêu cầu về bộ nhớ, thiết bị lưu trữ, ... của máy tính để thuật toán có thể làm việc. Việc
xem xét về không gian của thuật toán phụ thuộc phần lớn vào cách tổ chức dữ liệu của
thuật toán. Trong phần này, khi nói đến độ phức tạp của thuật toán, chúng ta chỉ đề cập
đến những đánh giá về mặt thời gian mà thôi.
Phân tích thuật toán là một công việc rất khó khăn, đòi hỏi phải có những hiểu
biết sâu sắc về thuật toán và nhiều kiến thức toán học khác. Ðây là công việc mà không
phải bất cứ người nào cũng làm được. Rất may mắn là các nhà toán học đã phân tích cho
chúng ta độ phức tạp của hầu hết các thuật toán cơ sở (sắp xếp, tìm kiếm, các thuật toán
số học, ...). Chính vì vậy, nhiệm vụ còn lại của chúng ta là hiểu được các khái niệm liên
quan đến độ phức tạp của thuật toán.
Ðánh giá về thời gian của thuật toán không phải là xác định thời gian tuyệt đối
(chạy thuật toán mất bao nhiêu giây, bao nhiêu phút,...) để thực hiện thuật toán mà là xác
định mối liên quan giữa dữ liệu đầu vào (input) của thuật toán và chi phí (số thao tác, số
Trang 18
Đại Học Sư Phạm
Khoa Tin Học
phép tính cộng,trừ, nhân, chia, rút căn,...) để thực hiện thuật toán. Sở dĩ người ta không
quan tâm đến thời gian tuyệt đối của thuật toán vì yếu tố này phụ thuộc vào tốc độ của
máy tính, mà các máy tính khác nhau thì có tốc độ rất khác nhau. Một cách tổng quát, chi
phí thực hiện thuật toán là một hàm số phụ thuộc vào dữ liệu đầu vào:
T = f(input)
Tuy vậy, khi phân tích thuật toán, người ta thường chỉ chú ý đến mối liên quan

max
= a
1
.
2. i = 2.
3. Nếu (i £ n) thì thực hiện các bước sau, ngược lại sang bước 5.
3.1. Nếu (a
i
> a
max
) thì
3.1.1. Ghi nhớ a
max
= a
i
3.2. Tăng i lên 1
4. Trở lại bước 3
5. Phần tử lớn nhất dãy a chính là amax.Kết thúc.
Trong thuật toán trên, để đơn giản, ta chỉ xem chi phí là số lần so sánh ở bước 3.1
và số lần "ghi nhớ" trong bước 3.1.1. Trường hợp tốt nhất của thuật toán này xảy ra khi
con số lớn nhất nằm đầu dãy (a
max
= a
1
); trường hợp xấu nhất xảy ra khi con số lớn nhất
nằm ở cuối dãy (a
max
=a
n
) và dãy được sắp xếp theo thứ tự tăng dần.

i
-1 < a
i
(do định nghĩa dãy được sắp xếp tăng dần) nên điều
kiện a
i
>a
max
ở bước 3.1 luôn thỏa, bước 3.1.1 luôn được thực hiện. Như vậy, ngoài chi phí
chung là n-1 phép so sánh, ta cần phải dùng thêm n-1 phép "ghi nhớ" ở bước 3.1.1. Như
vậy, tổng chi phí của trường hợp này là : T = f(n) = 2(n-1)=2n-2
Ðịnh nghĩa: Cho hai hàm f và g có miền xác định trong tập số tự nhiên. Ta viết
f(n) = O(g(n)) và nói f(n) có cấp cao nhất là g(n) khi tồn tại hằng số C và k sao cho:
|f(n)| ≤ C.|g(n)| với mọi n > k
Tuy chi phí của thuật toán trong trường hợp tốt nhất và xấu nhất có thể nói lên
nhiều điều nhưng vẫn chưa đưa ra được một hình dung tốt nhất về độ phức tạp của thuật
toán. Ðể có thể hình dung chính xác về độ phức tạp của thuật toán, ta xét đến một yếu tố
khác là độ tăng của chi phí khi độ lớn n của dữ liệu đầu vào tăng.
Theo định nghĩa ở trên, ta nhận thấy chi phí thấp nhất và lớn nhất của thuật toán
tìm số lớn nhất đều bị chặn bởi O(n) (tồn tại hằng số C = 10, k = 1 để 2n - 2 < 10n với
mọi n > 1).
Một cách tổng quát, nếu hàm chi phí của thuật toán (xét trong một trường hợp nào
đó) bị chặn bởi O(f(n)) thì ta nói rằng thuật toán có độ phức tạp là O(f(n)) trong trường
hợp đó.
Trang 20
i <=
n
S
i = 2
Ghi nhớ a

a
n).
Tên gọi Ký hiệu
Độ phức tạp hằng O(C)
Độ phức tạp logarit O(log
a
n)
Độ phức tạp nlogn O(n.log
a
n)
Độ phức tạp đa thức O(n
k
)
Độ phức tạp luỹ thừa O(a
n
)
Độ phức tạp giai thừa O(n!)
6.4 Phân loại bài toán
Ðộ phức tạp của thuật toán chính là yếu tố cơ sở để phân loại vấn đề-bài toán. Một
cách tổng quát, mọi bài toán đều có thể chia làm 2 lớp lớn là: giải được và không giải
được. Lớp giải được chia làm 2 lớp con. Lớp con đầu tiên là các bài toán có độ phức tạp
đa thức: nghĩa là bài toán có thể giải được bằng thuật toán có độ phức tạp đa thức (hay
nói ngắn gọn: lớp đa thức) được xem là có lời giải thực tế. Lớp con thứ hai là những bài
toán có độ phức tạp không phải là đa thức mà lời giải của nó được xem là thực tế chỉ cho
những số liệu đầu vào có chọn lựa cẩn thận và tương đối nhỏ. Cuối cùng là những bài
toán thuộc loại NP chưa thể phân loại một cách chính xác là thuộc lớp bài toán có độ
phức tạp đa thức hay có độ phức tạp không đa thức.
6.4.1 Lớp bài toán có độ phức tạp đa thức
Các bài toán thuộc lớp này có độ phức tạp là O(n
k

khóa 128-bit là trên 1 triệu năm với điều kiện làm việc trên các siêu máy tính mạnh nhất
hiện nay!
Chính vì lý do này, một bài toán được xem là có thể giải được trên thực tế hay
không phụ thuộc vào độ phức tạp của bài toán đó có phải là đa thức hay không.
6.4.2 Lớp bài toán có độ phức tạp không đa thức
Thật không may mắn, nhiều bài toán thực sự có lời giải lại không thuộc lớp của
bài toán đa thức. Ví dụ: cho một tập hợp có n phần tử, hãy liệt kê tất cả các tập con khác
Trang 21
Đại Học Sư Phạm
Khoa Tin Học
trống của tập hợp này. Bằng toán học, người ta đã chứng minh được rằng số tập con của
một tập hợp có n phần tử là 2
n-1
. Lời giải tuy đã có nhưng khi thể hiện lời giải này bằng
bất kỳ thuật toán nào thì phải tốn ít nhất 2
n-1
bước. Dễ thấy rằng độ phức tạp của bài toán
này cũng cỡ O(2
n
). Như vậy bài toán này không thuộc lớp của bài toán đa thức. Với n vào
khoảng 16, số bước cần thiết chỉ khoảng vài chục ngàn là hoàn toàn giải được trên các
máy tính hiện nay. Nhưng khi số phần tử lên đến 32 thì ta đã tốn một số bước lên đến 4
tỷ, chỉ thêm một phần tử nữa thôi, chúng ta đã tốn 8 tỷ bước! Với số lượng bước như vậy,
dù chạy trên một siêu máy tính cũng phải tốn một thời gian đáng kể! Các bài toán không
thuộc lớp đa thức chỉ giải được với một độ lớn dữ liệu đầu vào nhất định.
6.4.3 Lớp bài toán NP
Chúng ta đều biết rằng tính xác định là một trong ba đặc tính quan trọng của thuật
toán. Nghĩa là mỗi bước của thuật toán phải được xác định duy nhất và có thể thực thi
được. Nếu có sự phân chia trường hợp tại một bước thì thông tin tại bước đó phải đầy đủ
để thuật toán có thể tự quyết định chọn lựa trường hợp nào. Trong mục 4.3 này, ta tạm gọi

chọn lựa sai.
Quan điểm của ta trong cách giải quyết này là nếu chọn sai thì là do lỗi của người
chọn chứ không phải lỗi của thuật toán!
Theo thuật toán này thì chi phí để tính chiều dài của con đường được chọn sẽ tỷ lệ
với số đại lý; chi phí để so sánh chiều dài quãng đường với giới hạn cho phép thì không
liên quan đến số thành phố. Như vậy, chi phí của thuật toán này là một hàm có dạng T =
Trang 22
Đại Học Sư Phạm
Khoa Tin Học
an + b với n là số đại lý và a,b là các hằng số. Ta kết luận rằng, độ phức tạp của thuật toán
này là O(n) hay độ phức tạp thuộc lớp đa thức.
Như vậy, nếu dùng thuật toán tự quyết thì bài toán người bán hàng sẽ có độ phức
tạp không thuộc lớp đa thức, còn nếu dùng thuật toán không tự quyết thì bài toán sẽ có độ
phức tạp đa thức.
Ðịnh nghĩa
Một bài toán khi được giải bằng một thuật toán không tự quyết mà có độ phức tạp
thuộc lớp đa thức thì được gọi là một bài toán đa thức không tự quyết hay viết tắt là bài
toán NP.
Theo định nghĩa trên thì bài toán người bán hàng là bài toán thuộc lớp NP.
Cho đến nay người ta chưa chứng minh được rằng tồn tại hay không một thuật
toán tự quyết có độ phức tạp đa thức cho bài toán người bán hàng rong. Vì vậy, bài toán
này (là một bài toán NP) chưa thể xếp được vào lớp đa thức hay không đa thức. Do đó,
lớp bài toán NP chưa thể phân loại là thuộc lớp đa thức hay không.
Dĩ nhiên, lớp bài toán NP cũng chứa những bài toán thuộc lớp đa thức thực sự,
bởi vì nếu một bài toán được giải bằng thuật toán tự quyết có độ phức tạp đa thức thì chắc
chắn khi dùng thuật toán không tự quyết thì cũng sẽ có độ phức tạp đa thức.
Chương 2: CẤU TRÚC MÁY TÍNH
1. Máy tính là gì?
Máy tính Là thiết bị xử lý dữ liệu để có thông tin mong muốn.
Dữ liệu được xử lý theo sơ đồ sau:

- Giải mã lệnh (instruction decode).
- Thực thi lệnh đã giải mã một cách tuần tự (instruction excution).
Khối tính toán (ALU - Arithmetic Logic Unit): Thực hiện các phép toán số học và logic
- Các phép toán số học: +,-,*,/.
- Các phép toán logic: NOT, AND, OR,…
- Các phép so sánh…
Dữ liệu tính toán là:
Trang 24
Đại Học Sư Phạm
Khoa Tin Học
- Số nguyên (integer).
- Số dấu phảy tĩnh (fixed point number).
- Số dấu phảy động (floating point number).
Tập thanh ghi (Registers)
Lưu trữ toán hạng, kết quả và các thông số khác trong quá trình tính toán của CPU.
Bao gồm:
- Con trỏ chương trình (PC - Program Counter).
- Các thanh ghi đa chức năng.
- Thanh ghi chỉ số (index register).
- Thanh ghi cờ (flag register).
4. Computer Memory
Bộ nhớ được sử dụng để lưu trữ chương trình, dữ liệu.
Bao gồm:
Bộ nhớ đệm (cache)
Bộ nhớ chính (main memory)
Bộ nhớ ngoài (auxiliary or external memory)
Bộ nhớ nào càng “gần” CPU thì tốc độ và giá thành chế tạo càng cao
4.1. Bộ nhớ chính (main memory)
Chứa chương trình và dữ liệu đang xử lý. Được kết nối và có thể trao đổi dữ liệu trực
tiếp với CPU và được tổ chức thành các ngăn nhớ, đánh địa chỉ trực tiếp bởi CPU