Giáo trình lý thuyết cấu trúc rời rạc (2021-2022) chương 1 – CHƯƠNG I: THUẬT TOÁN 1. KHÁI NIỆM THUẬT – Studocu
CHƯƠNG I:
THUẬT
T
OÁN
1.1. KHÁI NIỆM
THUẬT
T
OÁN.
1.1.1. Mở đầu:
Có
nhiều
lớp
bài
toán
tổng
quát
xuất
hiện
trong
toán
học
rời
rạc.
Chẳng
hạn,
cho
một dãy
các số nguyên, tìm
số lớn
nhất; cho một
tập hợp, liệt
kê các tập
con của nó;
cho
tập
hợp
các
số
nguyên,
xế
p
chúng
theo
thứ
tự
tăng
dần;
cho
một
mạng,
tìm
đường
đi
ngắn
nhất
giữa
hai
đỉnh
c
ủa
nó.
Khi
được
giao
cho
một
bài
toán
như
vậy
thì
việc
đầu
tiên
phải
làm
là
xâ
y
dựng
một
mô
hình
dịch
bài
toán
đó
thành
ngữ
cảnh
toán
học.
Các
cấu trúc rời rạc được dùng trong các mô hình này là tập hợp, dãy
, hàm, hoán vị, quan hệ,
cùng với
các cấu
trúc khác
như đồ thị,
cây
, mạng
– những
khái niệm sẽ
được nghiên
cứu
ở các chương sau.
Lập
được
một
mô
hình
toán
học
thích
hợp
chỉ
là
một
phần c
ủa
quá
trình
giải.
Để
hoàn tất
quá
trình
giải,
còn
cần
phải
có
một
phương
pháp dùng
mô
hình
để
giải
bài
toán
tổng
quát.
Nói
một
cách
lý
tưởng,
cái
được
đòi
hỏi
là
một
thủ
tục,
đó
là
dãy
các
bước
dẫn tới đáp số mong muốn. Một dãy các
bước như vậy
, được
gọi là một thuật toán.
Khi
thiết
kế và
cài
đặt
một
phần
mềm
tin
học
cho
một
vấn đề
nào
đó,
ta
cần
phải
đưa
ra
phương
pháp
giải
quyết
mà
thực
chất
đó
là
thuật
toán
giải
quyết
vấn
đề
này
.
Rõ
ràng
rằng,
nếu
không
tìm
được
một
phương
pháp
giải
quyết
thì
không
thể
lập
trình
được.
Chính
vì
thế,
thuật
toán
là
khái
niệm
nền
tảng
của
hầ
u
hết
các
lĩnh
vực
của
tin
học.
1.1.2.
Định
nghĩa:
Thuật
toán
là
một
bảng
liệt
kê
các
chỉ
dẫn
(hay
quy
tắc)
cần
thực
hiện theo từng bước xác định nhằm
giải một bài toán đã cho.
Thuật
ngữ
“Algorithm”
(thuật
toán)
là
xuất
phát
từ
tên
nhà
toán
học
Ả
Rập
Al-
Khowarizmi. Ban đầu, từ algorism được
dùng để chỉ các quy
tắc thực hiện các phép tính
số
học
trên
các
s
ố
thập
phâ
n.
Sau
đó,
algorism
chuyển
thành
algorithm
vào
thế
kỷ
19.
Với sự
quan tâm
ngày càng tăng
đối với
các máy
tính, khái
niệm thuật
toán đã
được cho
một ý
nghĩa chung hơn,
bao hàm cả các
thủ tục xác
định để giải
các bài
toán, chứ không
phải chỉ là thủ tục để thực hi
ện các phép tính số học.
Có nhiều
cách trình
bày thuật toán:
dùng ngôn
ngữ
tự nhiên, ngôn
ngữ
lưu đồ
(sơ
đồ
khối),
ngôn
ngữ
lập
trình.
T
uy
nhiên,
một
khi
dùng
ngôn
ngữ
lập
trình
thì
chỉ
những
lệnh được phép trong ngôn ngữ đó mới có thể dùng được và
điều này thường làm cho sự
mô
tả
các
thuật
toán
trở
nên
rối
rắm
và
khó
hiểu.
Hơn
nữa,
vì
nhiều
ngôn
ngữ
lập
trình
đều
được
dùng
rộng
rãi,
nên
chọn
một
ngôn
ngữ
đặc
biệt
nào
đó
là
điều
người
ta
không
muốn.
Vì
vậy
ở
đây
các
thuật
toán
ngoài
việc
được
trình
bày
bằng
ngôn
ngữ
tự
nhiên
cùng
với
những
ký
hiệu
toán
học
quen
thuộc
còn
dùng
một
dạ
ng
giả
mã
để
mô
tả
thuật
4
