Thuật Toán (Algorithm)
Trịnh Tân Đạt
Khoa CNTT - Đại Học Sài Gòn
Email: trinhtandat@sgu.edu.vn
Website: https://sites.øgoogle.com/site/ttdat88/ Nội dung
“ Vân đê, bài toán "Thuật toán © Khái niệm ©_ Các đặc trưng của thuật toán o Phương pháp biểu diễn thuật toán : mã giả, lưu đô khối.
"_ Cải bài toán trên máy tính Vân đê, bải toán
" Vấn đề (issue/problem): o_ Những vướng mặc, khó khăn trong cuộc sống mà ta cân giải quyết m.. Bài toán (problem): o_ Một loại vẫn đê mà để giải quyết, cân đến tính toán (phép toán số, luận lí, quan hệ). o_ Khi giải bài toán, cần quan tâm 02 yêu tô: đâu vào (input) và đâu ra (output)
WHENYOUFINDNO I2NPEnnn TO A Mục CV ý TỔ
sMBlïn Tre
XTRUTH Tổ ẾE 10 -Â
- AMOMYHOUS
Cải quyêt vân đề, bài toàn
" Bất kỳ vân đê, bài toán ngoài đời nào cũng có thể được chia thành trình tự nhiều công việc nhỏ hơn. “ Trình tự các công việc nhỏ này được gọi là giải thuật giải quyết công việc ngoài đời. " Mỗi công việc nhỏ hơn cũng có thể được chia nhỏ hơn nữa nếu nó còn phức tạp.... Ví dụ: ??? “= Vận đề mâu chốt của việc dùng máy tính giải quyết công việc ngoài đời là lập
trình. Thuật toán
Thuật toán (Algorithm):
" Là cách biểu diễn lời giải "bài toán“ rõ ràng (không mập mò), chỉ tiết để có thể thực thi được trên máy tính.
“Là một dãy hữu hạn các bước nhằm xác định các thao tác mà máy tính có thể thực hiện được sao cho sau khoảng thời gian hữu hạn (có tính dừng) thì cho ra kết quả.
Ví dụ: Bài toán giải phương trình bậc I (l1 ân; ax+b=0). Ví dụ:
“ Thuật toán giải PT bậc nhất: ax +b = 0 (a, b là các sô thực). Đầu vào: a, b thuộc R -Đâu ra: nghiệm phương trình ax + b = 0
- Nếua=0 *° b =0 thì phương trình có nghiệm bất kì. ° b #0 thì phương trình vô nghiệm. ° Nếu a#0 ° Phương trình có nghiệm duy nhất x = -b/a

Các đặc trưng của thuật toàn
" Tính hữu hạn: có hữu hạn bước và phải dừng.
" Tính xác định: các bước rõ ràng, thực thi được.
“Tính đúng: quá trình thực thi theo các bước đã chỉ ra phải đi đến kết quả như ý. " Tính hiệu quả: khôi lượng, không gian, thời gian tính toán không quá “lớn”.
“Tính tổng quát: áp dụng được cho mọi trường hợp của bài toán. Vị dụ
— Một lớp học cân chọn lớp trưởng theo các bước: l. Lập danh sách sinh viên 2. Sắp thứ tự 3. Chọn người đứng đâu làm lớp trưởng
— Danh sách cân øì?
— Sắp theo thứ tự nào? (tăng giảm, tiêu chí nào)
— Nếu trùng tiêu chí thì giải quyết ra sao? Ví dụ
Sửa lại:
a) Lập danh sách theo: họ tên, ngày tháng năm sinh, điểm các môn, điểm trung bình CuÔI1 năm.
b) Sắp xếp theo ĐTB giảm. Nếu ĐTB băng nhau —> cùng hạng.
e) Nếu có 01 HS đứng đầu —> chọn, ngược lại chọn người có điểm toán cao nhất, nêu không chọn được —> bôc thăm.
"Phân biệt mập mờ và lựa chọn có quyết định:
— Mập mờ là thiêu thông tin hoặc có nhiều lựa chọn nhưng không đủ điêu kiện quyết định, ví dụ: bước ], 2.
— Lựa chọn 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 đê, ví dụ bước c. Ví dụ
m _ Tính thực thi được, ví dụ:
— Tính v-io 2
- Chạy xe thăng từ ĐHSG đến sân bay TSN? m Tính dừng, ví dụ:
— BI nhập n;
— B2 s=0;
— B31-l;
- B4 nếu i=n+1 sang B8, ngược lại sang B5 — B5 cộng 1 vào s
— Bó cộng 2 vào 1
— B7 quay lại B4
- B§ Tổng cần tính là s Phương pháp biểu diễn thuật toán
“ Thuật toán thường được biêu diễn băng các ngôn ngữ sau: ©_ Dùng ngôn ngữ tự nhiên (NNTN - natural language) ©_ Dùng mã giả (pseudocode): ngôn ngữ tự nhiên (NNTN) + ngôn ngữ lập trình (NNLT)
©o_ Dùng lưu đồ - sơ đồ khối (flowchart) Biêu diên băng ngôn ngữ tự nhiên
“ Dùng ngôn ngữ thường ngày để liệt kê các bước của thuật toán. “ Không thể hiện rõ cấu trúc của thuật toán. “ Dài dòng, có thê gây hiểu lâm hoặc khó hiểu ". KHÔNG yêu cầu người viết hay đọc nắm quy tắc. ©o_ Không có một quy tắc cô định =" Tính dễ đọc: ©o_ Viết các bước con lùi vào bên phải
©o_ Đánh số bước theo quy tắc phân cấp như 1, 1.1,... Biêu diễn băng mã giả
"_ Vay mượn các cú pháp của một ngôn ngữ lập trình o dùng một phân ngôn ngữ tự nhiên © bị phụ thuộc vào ngôn ngữ lập trình. “ Mọi ngôn ngữ lập trình đều có những thao tác cơ bản © xử lý, rẽ nhánh và lặp © tận dụng được các khái niệm trong ngôn ngữ lập trình
" Dễ dàng năm bắt nội dung thuật toán Biêu diên băng mã giả - Ví dụ
Một đoạn mã giả của thuật toán giải pt bậc hai
IÝ Delta > 0Ú then xI1=(-b-sqart(delta))/(2*a) x2=(-b+sdart(delta))/(2a) xuất kết quả : phương trình có hai nghiệm là xI và x2
end else If delta = 0 then xuất kết quả : phương trình có nghiệm kép là -b/(2*a) else {trường hợp delta < 0 }
xuất kết quả : phương trình vô nghiệm
Biêu diên băng lưu đồ Hành động (Acuvity)
" Các nhà lập trình đưa ra dạng Dữ liệu vào (Input) lưu đô đê minh họa từng bước quá trình xử lý một vân đề (bài toán).
Xử lý (Process)
max x = s 3
<> Quyết định (Decision), sử dụng điều kiện
Gợi CT con, hảm... (Procedure, Function...]
- mỐ K= =
Điểm ghép nỗi (Connector)
Biêu diên băng lưu đồ
" Công cụ trực quan diễn đạt thuật toán. © Biểu diễn bằng mô hình — hình vẽ " Theo dõi được: © Sự phân cấp các trường hợp ©O Quá trình xứ lý của thuật toán " Phân biệt hai loại thao tác: o Chọn lựa theo một điều kiện nào đó
© X# lý, hành động Biêu diên băng lưu đồ
" Chọn lựa theo một điêu kiện nào đó: o Biểu diễn bằng một hình thoi, bên trong chứa biểu thức điều kiện. " Ví dụ: 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
Biêu diên băng lưu đồ
" Thao tác chọn lựa: có thể có hai hướng đi o một hướng ứng với điều kiện thỏa o một hướng ứng với điều kiện không thỏa. © 2 nhánh có nhãn
°Ồ Đ/Đúng,Y/Yes
*® S/SaLN/No
Biêu diên băng lưu đồ
" Xử lý, hành động: o Biểu diễn bằng một hình chữ nhật, bên trong chứa nội dung xử lý.
" Ví dụ: "Chọn một môn học và m ra." là một thao tác thuộc loại hành
động.
Biêu diên băng lưu đồ
" (Quá trình thực hiện các thao tác: Hi © Đưởng đi — roufc © Biểu diễn băng cung có hướng
* nôi giữa 2 thao tác: thực hiện lần lượt
Biêu diên băng lưu đồ
" Diễm cuối (terminator) o Biểu diễn bằng hình ovan o Điểm khởi đầu ° chỉ có cung ởi ra ° bên trong ovan hi chữ: bắt đầu/start/begin o Điểm kết thúc
° Chỉ có cung đi vào

° bên trong ovan ghi chữ: kết thúc/end
“" Mỗi lưu đồ chỉ có I điểm bắt đầu và I điểm kết thúc. Biêu diên băng lưu đồ

" Điểm nôi (connector) © Nồi các phần khác nhau của một lưu đồ © Nổi sang trang © Sử dụng với lưu đô phức tạp
« Giảm độ rắc rôi
° Đặt ký hiệu liên hệ giữa các điêm nôi Ví dụ: Sử dụng ngôn ngữ tự nhiên
BS BS nh nh nh nh SH TH HH HH THỊ HH HH CHỊ HH HH HH HH TH HH HH HH HH HH TH HH HH HH HH HH HH HH. HH HH HH TH HH HH HH HH HH HH THỊ HH HH HH TH HH HH HH HH HH HH HH. HH HH HH TH HH HH HH HH HH HH HH HH nH mm mm,
| Đầu vào: a, b thuộc R -Đâu ra: nghiệm phương trình ax + b = 0

1. Nhập 2 số thực a và b. 2. Nếu a = 0 thì 2.1. Nếu b = 0 thì 2.1.1. Phương trình vô số nghiệm 2.1.2. Kết thúc thuật toán. 2.2. Ngược lại 2.2.1. Phương trình vô nghiệm. 2.2.2. Kết thúc thuật toán. 3. Ngược lại 3.1. Phương trình có nghiệm. 3.2. Giá trị của nghiệm đó là x = -b/a 3.3. Kết thúc thuật toán.
Ví dụ: Sử dụng mã giả
| - Đầu vào: a,b thuộc R Đâu ra: nghiệm phương trình ax + b = 0
Ha = 0 Then IWb= 0 Then Xuất “Phương trình vô số nghiệm” Else
Xuất “Phương trình vô nghiệm”
End Else Xuât “Phương trình có nghiệm x = -b/a”
Ví dụ: Sử dụng sơ đô khôi
Bắt đầu
Đọc a,b
pH
Ð Tính x=-b/a
Xuât x
Cài đặt thuật toán băng C/C++
†include f†include
1nt ma1n ()
{ 1nt a, b; printf£ ("Nhap a, b: "); scanf("%d $%d", &a, &b) ; 1£ (a == 0Ô)
1£ (b == Q)
printf (*Phương trình VSN”); else
printf£ (`*Phương trình VN”);
else print£f (`x = %.2f”, -£loat(b) /a) ; return 0Ô;
Ví dụ l “ Chuẩn bị cà phê Bỏ đường vào
Khuấy đều hỗn hợp
Cả phê đã sẵn sảng
Ví dụ 2
" Tính toán nghiệm x = -b/a Cộng hai sô c = a+b
Ví dụ 3
" Kiếm tra 2 số a và b giông hay khác nhau
Ví dụ 4
" Kiểm tra điểm thi có hợp lệ hay không?

Điểm hợp lệ Điểm không hợp lệ Ví dụ 5
" Kiểm tra một số là © Số dương o Sốâm ©o hay bằng0
Ví dụ 6
" Xếp lon bia vào thùng (tôi đa chứa được 24 lon)
°s.oộ 9 >¬+- Lư ^^ Lư ⁄ Cải bài toán trên máy tính " Các bước giải quyết vân đề, bài toán bằng máy tính điện tử (MTĐT):
1) Xác định vấn đề, bài toán: xác định rõ yêu câu của bài toán, bài toán cho gì (Input) và yêu câu tìm gì (Output).
2) Lựa chọn phương pháp giải: Có thể có nhiêu cách khác nhau để giải bài toán. Các phương pháp có thể khác nhau về thời gian thực hiện, chi phí lưu trữ đữ liệu, độ
chính xác, ... => tùy theo nhu câu cụ thê mà chọn phương pháp giải thích hợp. Cải bài toán trên máy tính
3) Xây dựng thuật toán: xây dựng mô hình chặt chẽ, chính xác hơn và chỉ tiết hơn cho phương pháp giải đã chọn. Xác định rõ ràng dữ liệu vào, ra cho các bước thực hiện cơ bản và trật tự thực hiện các bước đó. Nên áp dụng phương pháp thiết kế có cầu trúc, từ thiết kế tông thê tiến hành làm mịn dân từng bước.
4) Cài đặt chương trình: mô tả thuật giải bằng chương trình. Dựa vào thuật giải đã được xây dựng, căn cứ quy tắc của một ngôn ngữ lập trình để soạn thảo ra chương
trình thể hiện giải thuật thiết lập ở bước 3. Cải bài toán trên máy tính
5) Hiệu chỉnh chương trình: Cho chương trình chạy thử để phát hiện và điều chỉnh sai sót nêu tìm thấy. Có hai loại lỗi: lỗi cú pháp và lỗi ngữ nghĩa. 6) Thực hiện chương trình: Cho MTĐT thực hiện chương trình. Tiến hành phân tích kết quả thu được. Việc phân tích kết quả nhằm khắng định kết quả đó có phù hợp hay
không. Nêu không, cân kiêm tra lại toàn bộ các bước một lân nữa. Tử bài toán đên chương trình
Bài toán thực (Pseudocode) I2 - Dùng flowchart
- Mô hình toán Phân tích, đánh giá Ngôn ngữ lập trình - Chọn kiều dữ liệu, thuật toán 0e"
câu trúc dữ liệu -Độ phức tạp Java - Thiết kế giải thuật - Cải tiễn thuật toán Python
Từ bài toán đến chương trình
s* Chương trình (Program)
“ Là một tập hợp các mô tả, các phát biểu, năm trong một hệ thống qui ước về ý nghĩa và thứ tự thực hiện, nhằm điêu khiến máy tính làm việc. Theo Niklaus Wirth thì: Chương trình = Thuật toán + Câu trúc dữ liệu.
" Các thuật toán và chương trình đều có câu trúc dựa trên 3 câu trúc điêu khiển cơ bản:
o Tuần tự (Sequenfial): Các bước thực hiện tuân tự một cách chính xác từ trên xung, mỗi bước chỉ thực hiện đúng một lân. ©_ Chọn lọc (Selection): Chọn l trong 2 hay nhiêu thao tác để thực hiện.
© Lạp lại (Repetition): Một hay nhiêu bước được thực hiện lặp lại một số lần. ^^ On lập Thuật toán là øì? Trình bày các tính chất quan trọng của một thuật toán? 2. Các bước xây dựng chương trình (giải bài toán trên máy tính)?
Các cách biểu diễn thuật toán? Ưu và khuyết điểm của từng phương pháp? Cho ví dụ minh họa. Bài lập
“ Viết mã giả và vẽ lưu đô thuật toán cho các chương trình sau:
1. Đôi từ tiên VND sang tiên USD.
2. Tính điểm trung bình của học sinh gôm các môn Toán, Lý, Hóa. 3. Giải phương trình bậc 2: ax” + bx +e=0
4. Đôi từ độ sang radian và đổi từ radian sang độ
(công thức ơ/7r = a/180, với œ: radian, a: độ)
5. Kiểm tra 2 số a, b giỗng nhau hay khác nhau.
6. Nhập năm sinh của một người. Tính tuôi người đó.
7. Nhập 2 số a và b. Tính tổng, hiệu, tính và thương của hai số đó. Š. Nhập bán kính của đường tròn. Tính chu vi và diện tích của hình tròn đó. 9. Nhập vào 2 số nguyên. Tính min và max của hai số đó. 10. Giải hệ phương trình bậc nhất hai ấn. `. ® ^ Bài tập " Nâng cao: Vẽ lưu đô thuật toán cho các chương trình sau:
I. Nhập vào số nguyên dương n. Tính tổng S=1+2+3+4+...+n
2. Nhập vào số nguyên dương n. Kiểm tra n có phải là số nguyên tô hay không?