Giải thuật & chương trình
1
THUẬT TOÁN & CHƯƠNG TRÌNH
Nguyễn Thanh Trung
MỤC TIÊU
Giới thiệu tổng quan về thuật toán và cách chuyển từ 1 thuật toán thành 1 chương trình bằng một ngôn ngữ lập trình cụ thể (C).
Những yêu cầu khi xây dựng thuật toán: tính đúng đắn, khả thi,… cũng như xác định độ phức tạp của thuật toán.
Giải thuật & chương trình
2
Bố cục
Giới thiệu tổng quan
Trình bày và triển khai thuật toán
Đánh giá thuật toán
Cài đặt Chương trình
Giải thuật & chương trình
3
Tài liệu tham khảo
-Chương 5,6 Computer Science
-Chương 5 bài giảng Giới thiệu Khoa học Máy tính.
Giải thuật & chương trình
4
Giải thuật & chương trình
5
5.1. Tổng quan
Máy tính?
Làm theo “lệnh” của con người.
Điểm mạnh là tính toán với tốc độ cao (hàng tỷ phép tính trên giây).
Làm thế nào để “ra lệnh”cho máy tính?
Lập chương trình cho máy tính
Chương trình?
Nói cho máy tính biết phải làm gì, như thế nào,…
Giải thuật & chương trình
6
Muốn “ra lệnh” cho máy tính: Sử dụng một “ngôn ngữ” chung  ngôn ngữ lập trình (programming language)
Lập trình (computer programming)
Dùng ngôn ngữ lập trình lập nên chương trình hoạt động cho máy tính.
Các thế hệ của ngôn ngữ lập trình
Thế hệ 1 (bậc thấp): ngôn ngữ máy, assembly.
Thế hệ 2: Gần với ngôn ngữ tự nhiên hơn, phục vụ những nhu cầu lập trình nhất định (FORTRAN, COBOL, ALGOL,… )
Thế hệ 3: Gần gũi, vạn năng (PASCAL, C, C++,…)
Thế hệ 4: Truy vấn, hỗ trợ quyết định, lập trình trí tuệ nhân tạo
(SQL, LISP, PROLOG,…)
Giải thuật & chương trình
7
Thuật toán
Giải thuật, thuật giải, thuật toán đều dùng để ám chỉ một thuật ngữ tiếng Anh có tên là ALGORITHM.
Chúng ta sẽ tìm hiểu:
Giải thuật theo cách hiểu thông thường
Các thao tác trong giải thuật
Định nghĩa giải thuật
Giải thuật & chương trình
8
Theo nghĩa rộng, khái niệm “giải thuật” (algorithm) được sử dụng ở mọi nơi, không riêng gì trong lĩnh vực tin học.
Giải thuật là một loạt các thao tác (operation) có thứ tự (order) nhằm giải quyết một bài toán nào đó.
Ví dụ: “Thuật toán nấu cơm”
Bước 0: Ước lượng gạo cần thiết
Bước 1: Vo gạo
Bước 2: Cho gạo và nước thích hợp vào nồi cơm điện(NCĐ)
Bước 3: Cắm điện, chuyển chế độ “cook”
Bước 4: Chờ đến khi NCĐ chuyển sang chế độ “warm”
Bước 5: Chờ thêm 10 phút nữa
Bước 6: Cơm chín, kết thúc.
Giải thuật & chương trình
9
Các thao tác trong giải thuật
Thao tác tuần tự (sequential operation): Một công việc đã được xác định rõ ràng, thực hiện xong thì chuyển sang công việc khác.
Thao tác kiểm tra điều kiện (conditional operation): Kiểm tra điều kiện đưa ra có thoả mãn hay không để quyết định thao tác tiếp theo.
Thao tác lặp (iterative operation): Quay trở lại bước nào đó trong dãy thao tác. Một thao tác có thể được lặp đi lặp lại nhiều lần tới khi một điều kiện nào đó được thoả mãn
Giải thuật & chương trình
10
Định nghĩa về giải thuật
Giải thuật là một dãy các câu lệnh chặt chẽ và rõ ràng xác định một trình tự thao tác trên một đối tượng nào đó sao cho sau một số bước hữu hạn thực hiện, ta thu được kết quả mong muốn.
… Câu lệnh (statement/instruction): đơn vị thao tác, tính toán, xử lý
… Trình tự rõ ràng (well-ordered): thực hiện xong bước này mới chuyển sang bước khác, không nhập nhằng.
… Đối tượng (object): các dữ kiện của bài toán, dữ liệu trung gian, kết quả,…
… Kết quả (result): Thông tin, lời giải cho bài toán,…
Giải thuật & chương trình
11
Yêu cầu đối với giải thuật
Tính dừng: Một giải thuật bất kỳ phải đảm bảo dừng sau một số hữu hạn bước.
Tính đúng đắn: Giải thuật phải đảm bảo giải quyết bài toán một cách đúng đắn, cho kết quả “chính xác” và “đầy đủ” theo yêu cầu.
Tính đơn giản và hiệu quả
Đơn giản: Dễ hiểu, dễ lập trình.
Hiệu quả: Tiêu tốn ít thời gian và tài nguyên máy tính
Giải thuật & chương trình
12
Mọi bài toán đều có giải thuật ?
Có những bài toán không có giải thuật tổng quát để giải quyết.
Có những bài toán chưa có giải thuật hữu hiệu để giải quyết.
Có những bài toán chưa có giải thuật tìm lời giải.
Giải thuật & chương trình
13
5.2. Trình bày và triển khai thuật toán
Liệt kê từng bước
Sơ đồ khối
Sử dụng giả ngôn ngữ
Giải thuật & chương trình
14
5.2.1. Liệt kê từng bước
Các thao tác của giải thuật được liệt kê từng bước
Tại mỗi bước, sử dụng ngôn ngữ tự nhiên để diễn tả công việc phải làm.
Bước đứng trước (có số thứ tự nhỏ hơn) được thực hiện trước.
Ưu nhược điểm
Dễ hiểu, dễ làm
Phụ thuộc vào “cách hành văn” của người diễn đạt
Với những giải thuật phức tạp, cách diễn đạt này trở nên rườm rà
…
Giải thuật & chương trình
15
Ví dụ 1: Giải phương trình bậc nhất ax+b=0
1. Nhập a,b.
2. Nếu a=0 và b=0 thì viết “Phương trình nghiệm đúng với mọi x” rồi sang bước 5.
3. Nếu a=0 và b # 0 thì viết “Phương trình vô nghiệm” rồi sang bước 5.
4. Nếu a # 0 thì tính x=-b/a rồi viết x là nghiệm.
5. Kết thúc
Giải thuật & chương trình
16
VD2: Nhập n phần tử a1..an, sau đó tính tổng n số: S=a1+ a2+a3+......+an

Bước 1: Nhập n.
Bước 2: Cho S=0 (lưu trữ số 0 trong S)
Bước 3: Cho i=1 (lưu trữ số 1 trong i)
Bước 4: Kiểm tra nếu i<=n thì thực hiện bước 5, ngược lại thực hiện bước 8.
Bước 5: Nhập ai
Bước 6: Cho S=S+ai (lưu trữ giá trị S + ai trong S)
Bước 7: Tăng i lên 1 đơn vị và quay lại bước 4.
Bước 8: In S và kết thúc chương trình.
Giải thuật & chương trình
17
VD3: Viết GT nhập vào 2 giá trị a, b tìm số lớn hơn
- Bước 1: Nhập 2 số a và b
- Bước 2: Nếu a >b thì viết a lớn hơn b, sang thực hiện bước 5, (còn không sang bước 3)
- Bước 3: Nếu a=b thì viết a=b, sang thực hiện bước 5, (còn không sang bước 4).
- Bước 4: viết b lớn hơn a
-Bước 5:kết thúc.
Giải thuật & chương trình
18
VD4: Xây dựng TT nhập n giá trị a1, a2,…,an. in ra giá trị lớn nhất
Bước 1: Nhập số n
Bước 2: Nhập số thứ nhất a1
Bước 3: Gán max=a1
Bước 4: Gán i=2
Bước 5: Nếu i<=n thì thực hiện bước 6, ngược lại thực hiện bước 9
Bước 6: Nhập ai
Bước 7: Nếu max < ai thì gán max=ai.
Bước 8: Tăng i lên một đơn vị và quay lại bước 5
Bước 9: In max - kết thúc
Giải thuật & chương trình
19
VD5: Xây dựng TT nhập n giá trị a1, a2, …, an. Sắp theo thứ tự tăng dần
Bước 1: Gán i=1
Bước 2: Gán j=i+1
Bước 3: Nếu i <=n-1 thì thực hiện bước 4, ngược lại thực hiện bước 8
Bước 4: Nếu j <=n thì thực hiện bước 5, ngược lại thì thực hiện bước 7.
Bước 5: Nếu ai > aj thì hoán đổi ai và aj cho nhau (nếu không thì thôi).
Bước 6: Tăng j lên một đơn vị và quay lại bước 4
Bước 7: Tăng i lên một đơn vị và quay lại bước 3
Bước 6: In dãy số a1, a2,..., an - Kết thúc.
Giải thuật & chương trình
20
5.2.2. Diễn đạt giải thuật bằng sơ đồ khối (block diagram)
Sử dụng các hình khối để minh hoạ cho các lệnh hay thao tác.
Sử dụng mũi tên để diễn đạt thứ tự thực hiện
Đây là cách diễn đạt khoa học, có tính nhất quán cao
Giải thuật & chương trình
21
Sơ đồ khối (Lưu đồ)

Các ký hiệu được sử dụng trong lưu đồ:

Nhập – Input

Xử lý – Process

Quyết định – Decision

Thủ tục – Procedure

Đường kết nối - Flow line
Giải thuật & chương trình
22
Giải thuật và Lưu đồ (tt)

Các ký hiệu được sử dụng trong lưu đồ (tt):

Bắt đầu và Kết thúc – Start and Stop

Kết nối trên cùng một trang – On page connector

Kết nối ở trang khác – Off page connector

Chú thích – Annotation

Hiển thị - Display/Output
Giải thuật & chương trình
23
Lưu đồ sau đây nhập hai số, tính tích và hiển thị tích của hai số.
Giải thuật & chương trình
24
Lưu đồ sau đây hiển thị số lớn hơn trong hai số đã nhập.
Giải thuật & chương trình
25
?
Giải thuật & chương trình
26
Giải thuật & chương trình
27
American National Standards Institute (ANSI) đề nghị một số qui luật cần phải tuân theo khi vẽ lưu đồ như sau:
Toàn bộ lưu đồ nên được biểu diễn bằng ký hiệu chuẩn.
Lưu đồ nên rõ ràng, chính xác và dễ theo dõi.
Lưu đồ chỉ nên có một điểm bắt đầu và một điểm kết thúc.
Các bước trong lưu đồ nên đi từ trên xuống và đi từ trái sang phải.
Tất cả dữ liệu nhập phải được liệt kê hết theo một thứ tự hợp lý.
Các qui tắc vẽ lưu đồ
Giải thuật & chương trình
28
Ký hiệu bắt đầu và kết thúc chỉ nên có một đường kết nối duy nhất.
Ký hiệu nhập dữ liệu, xử lý, xuất dữ liệu, hiển thị nên có hai đường kết nối để nối ký hiệu đứng trước và đứng sau chúng.
Ký hiệu quyết định nên có một đường kết nối với ký hiệu trước nó và có hai đường kết nối đến hai ký hiệu đứng sau nó.
Nếu có quá nhiều đường kết nối làm cho lưu đồ trở nên phức tạp thì nên dùng ký hiệu kết nối trang để giảm số đường kết nối.
Các qui tắc vẽ lưu đồ
Giải thuật & chương trình
29
Điểm mạnh của lưu đồ

Lưu đồ là phương pháp tốt để truyền đạt lập luận của giải thuật.

Lưu đồ giúp phân tích vấn đề một cách hiệu quả.

Lưu đồ đóng vai trò như người hướng dẫn trong giai đoạn phát triển chương trình.

Dễ tìm và sửa lỗi bằng lưu đồ.

Lưu đồ trợ giúp đắc lực trong việc bảo trì chương trình.
Giải thuật & chương trình
30
Điểm yếu của lưu đồ

Lưu đồ dài có thể trãi ra trên nhiều trang, làm giảm tính dễ đọc.

Việc vẽ lưu đồ bằng các công cụ đồ hoạ là việc làm tốn nhiều thời gian.

Thay đổi chỉ một bước nào đó có thể dẫn đến việc vẽ lại toàn bộ lưu đồ.
Lưu đồ biểu diễn giải thuật phức tạp có thể chứa rất nhiều đường kết nối. Điều này làm giảm tính dễ đọc, tốn thời gian để vẽ và hiểu lập luận của giải thuật.
Giải thuật & chương trình
31
5.3.3. Diễn đạt giải thuật bằng ngôn ngữ giả
Dựa trên ngôn ngữ lập trình bậc cao
Gần với ngôn ngữ tự nhiên của con người
Ví dụ: Ngôn ngữ giả Pascal (tựa Pascal) có các ký pháp khá giống với ngôn ngữ lập trình Pascal, được rút gọn sao cho dễ diễn đạt
Giả ngôn ngữ được đưa ra với mục đích diễn đạt các giải thuật sao cho gần với ngôn ngữ lập trình và ngôn ngữ tự nhiên.
Sử dụng giả ngôn ngữ khiến việc chuyển từ giải thuật sang chương trình dễ dàng hơn.
Giải thuật & chương trình
32
Ví dụ: Giải thuật tính tổng N số tự nhiên đầu tiên
Nhập N
i:=0
S:=0
REPEAT
S:=S+i
i:=i+1
UNTIL (i>N)
In S
Giải thuật & chương trình
33
5.3. Đánh giá thuật toán
Phân tích thuật toán: tìm một cách đánh giá về thời gian và “không gian” cần thiết để thực hiện 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 mà là mối liên quan giữa dữ liệu đầu vào và chi phí để thực hiện thuật toán T=f(input)
Thông thường chỉ quan tâm đến mối liên quan giữa độ lớn của dữ liệu đầu vào và chi phí T=f(n) trong trường hợp tốt nhất và xấu nhất
Giải thuật & chương trình
34
Độ phức tạp của thuật toán
Giải thuật & chương trình
35
Độ phức tạp của thuật toán
Chi phí chung = chi phí so sánh + chi phí gán
Trong mọi trường hợp, phép so sánh ai>amax luôn được thực hiện và số lần thực hiện là n-1: chi phí cố định (bất biến) của bài toán
Trường hợp tốt nhất: số lớn nhất ở đầu dãy. Do đó phép gán amax= ai không cần thực thi, như vậy chi phí chung cho trường hợp này chính là chi phí cố định T=f(n)=n-1
Trường hợp xấu nhất: số lớn nhất ở cuối dãy. Do đó phép gán amax= ai luôn cần thực thi, số lần thực thi là n-1, như vậy chi phí chung cho trường hợp này là T=f(n)=2(n-1)=2n-2
Độ phức tạp của thuật toán là O(n), tuyến tính
Giải thuật & chương trình
36
5.4. Xây dựng chương trình
Xác định vấn đề - bài toán
Lựa chọn phương pháp giải
Xây dựng thuật toán hoặc thuật giải
Cài đặt chương trình
Hiệu chỉnh chương trình
Thực thi chương trình
Giải thuật & chương trình
37
Phương pháp lập trình
Lập trình cấu trúc có các đặc trưng
Tính đơn thể
Cấu trúc điều khiển: phối hợp cấu trúc tuần tự, cấu trúc chọn và cấu trúc lặp
Tính vào/ra đơn
Lập trình hướng đối tượng: một tiếp cận mới trong lập trình sử dụng khái niệm đối tượng, kết hợp cả dữ liệu và các câu lệnh của chương trình
Giải thuật & chương trình
38
Ngôn ngữ lập trình
Tập từ ngữ và cú pháp cho phép lập trình viên hoặc người dùng có thể nói chuyện với máy tính
Chương trình máy tính là tập các chỉ thị nhằm thực hiện nhiệm vụ cụ thể được viết bằng ngôn ngữ lập trình
Các loại ngôn ngữ lập trình
Ngôn ngữ máy
Hợp ngữ
Ngôn ngữ cấp cao
Giải thuật & chương trình
39
MACHINE CODE
ASSEMBLER LANGUAGES

HIGH-LEVEL
LANGUAGES
ForTran, COBOL, C, C++,
LISP, Pascal, Java, ...
4GLs
ORACLE, SEQUEL, INGRES, ...
5GLs
artificial intelligence
Ngôn ngữ lập trình
Giải thuật & chương trình
40
Ngôn ngữ lập trình

Ngôn ngữ lập trình là phương tiện truyền thông giữa Lập trình viên và máy tính.

Lập trình viên sử dụng ngôn ngữ lập trình để viết các lệnh yêu cầu máy tính thực hiện một công việc nào đó. Tập hợp các lệnh này được gọi là chương trình.
Các loại ngôn ngữ lập trình:
Giải thuật & chương trình
41
Ngôn ngữ máy:
Từ vựng được tạo nên từ mã nhị phân 0-1 để tạo ra các câu lệnh, các chỉ dẫn nhằm yêu cầu máy tính thực hiện một công việc nào đó.
Các lệnh được máy tính thực hiện trực tiếp (không qua mã trung gian).
Ngoài ngôn ngữ máy, các NNLT khác đều cần được dịch ra mã trung gian trước khi thực thi.
Ngôn ngữ Assembly:
Còn gọi là ngôn ngữ máy tính thế hệ thứ 2 là ngôn ngữ sử dụng bảng mã chữ cái và các ký hiệu để đưa ra các chỉ dẩn
Ngôn ngữ cấp cao:
Đây là ngôn ngữ thân thiện với người sử dụng vì dùng những từ ngữ thông dụng tiếng Anh để đưa ra các chỉ dẩn cho máy tính ví dụ như PRINT, GOTO
Giải thuật & chương trình
42
Ví dụ về các ngôn ngữ lập trình cấp cao

Một số ngôn ngữ lập trình cao cấp là:
BASIC
Pascal
C
Java
C#


Giải thuật & chương trình
43
Lựa chọn ngôn ngữ lập trình
Một số các yếu tố khi lựa chọn ngôn ngữ lập trình:
Tiêu chí 1: lựa chọn đầu tiên là tùy thuộc vào loại ứng dụng cần phát triển.
Ví dụ:
- Tạo ra chương trình thực hiện các phép toán đơn giản (+ - * /) ta có thể sử dụng Pascal.
- Để phát triển ứng dụng dùng trong gia đình hoặc doanh nghiệp nhỏ có thể dùng Visual BASIC
Tiêu chí 2: Nếu có nhiều ngôn ngữ phù hợp để phát triển ứng dụng thì bạn nên chọn ngôn ngữ mà bạn thông thạo nhất.
Tiêu chí 3: Nếu bạn không thông thạo ngôn ngữ nào cả thì nên chọn ngôn ngữ lập trình dễ học và dễ sử dụng.
Giải thuật & chương trình
44
Cài đăt chương trình từ 1 thuật toán
Ví dụ: Chuyển một số giải thuật cơ bản
Lặp
Đệ quy
Sắp xếp
Tìm kiếm
…
Tóm tắt và một số câu hỏi
Tại sao cần có thuật toán ?
Một số phương pháp biểu diễn thuật toán?
Những yêu cầu đối với 1 thuật toán ?
Biểu diễn thuật toán tìm số lớn nhất giữa 2 số a và b ?
Biểu diễn thuật toán giải PT bậc 2?
Tìm giá trị lớn nhất của 1 dãy số ?
Đánh giá độ phức tạp và cài đặt 3 thuật toán trên bằng C hoặc Pascal ?
Giải thuật & chương trình
45
Giải thuật & chương trình
46
Thuật toán đệ quy
Đưa bài toán hiện tại về một bài toán cùng loại, cùng tính chất (đồng dạng) nhưng ở cấp độ thấp hơn và quá trình này tiếp tục cho đến lúc bài toán được đưa về một cấp độ mà tại đó có thể giải được. Từ kết quả ở cấp độ này, lần ngược để giải được bài toán ở cấp độ cao đến lúc ban đầu
Định nghĩa giai thừa: 0!=1, n!=(n-1)!n với mọi n>0
Định nghĩa dãy số Fibonacci: f0=1, f1=1, fn=fn-1+fn-2 với mọi n>1
 Định nghĩa theo kiểu quy nạp
Giải thuật & chương trình
47
Thuật toán đệ quy
Mọi thuật toán đệ quy gồm hai phần:
Phần cơ sở: các trường hợp không cần thực hiện lại thuật toán (không gọi đệ quy), chính là các điểm dừng
Phần đệ quy: có yêu cầu gọi đệ quy, tức yêu cầu thực hiện lại thuật toán với cấp độ dữ liệu thấp hơn
Giải thuật & chương trình
48
Thuật toán đệ quy
Giải thuật & chương trình
49
Trình thông dịch và biên dịch
Mọi chương trình đều phải được chuyển đổi qua ngôn ngữ máy trước khi thực thi
Trình hợp dịch (assembler)
Trình biên dịch (compiler): chuyển đổi toàn bộ chương trình cấp cao nguồn sang chương trình đối tượng để thực thi
Trình thông dịch (interpreter): chuyển đổi từng mệnh đề và thực thi đoạn mã kết quả ngay, không tạo ra chương trình đối tượng
Giải thuật & chương trình
50
Trình biên dịch

Là chương trình (phần mềm) được sử dụng để chuyển các câu lệnh được viết bằng ngôn ngữ cấp cao sang ngôn ngữ máy tính có thể hiểu được.

Mỗi ngôn ngữ lập trình cấp cao có một trình biên dịch riêng tương ứng.
Giải thuật & chương trình
51
Trình biên dịch (tiếp theo)

Hình vẽ sau thể hiện sự hoạt động của trình biên dịch:
Giải thuật & chương trình
52
Trình biên dịch (tiếp theo)

Khi trình biên dịch dịch một chương trình, nó sẽ kiểm tra Từ vựng và Cú pháp các câu lệnh.

Nếu trình biên dịch tìm thấy lỗi trong chương trình nguồn thì nó sẽ hiển thị danh sách các lỗi.

Trình biên dịch sẽ không sinh ra mã trung gian nếu như tất cả các lỗi của chương trình nguồn chưa được sửa hết.
Giải thuật & chương trình
53
Bộ liên kết

Mỗi NNLT sẽ có các thư viện chứa các từ khóa với các chức năng được định nghĩa trước. Người lập trình sẽ sử dụng những từ khóa này kết hợp với các cú pháp để viết chương trình.

Khi dịch, trình biên dịch sẽ sinh ra mã trung gian.

Để sinh mã thực thi từ mã trung gian thì chức năng của các từ khóa (lưu trong các thư viện) và các thư viện cũng cần được đưa vào mã trung gian.

Bộ liên kết thực hiện việc gắn chức năng của các từ khóa với mã trung gian để tạo ra mã thực thi.

Giải thuật & chương trình
54
Bộ liên kết (tiếp theo)

Quá trình liên kết này được thể hiện bằng hình vẽ sau đây:
Giải thuật & chương trình
55
Trình thông dịch
Một số ngôn ngữ lập trình cấp cao sử dụng cơ chế dịch khác gọi là thông dịch. Chương trình dịch theo cơ chế này được gọi là trình thông dịch.

Trình thông dịch sẽ đọc một lệnh được viết bằng ngôn ngữ lập trình cấp cao, chuyển sang mã máy, thực thi câu lệnh này và không lưu mã trung gian.
Chương trình thực thi dùng trình thông dịch sẽ tiết kiệm được thời gian hơn trình biên dịch.
Trình thông dịch cũng giúp cho việc dò tìm lỗi dễ dàng hơn vì nó chỉ ra chính xác những dòng nào phát sinh lỗi.
Ngôn ngữ lập trình sử dụng trình thông dịch như PERL, BASIC, Visual Basic, v.v..