Bài giảng Tin học đại cương - Chương 6: Thuật toán và Ngôn ngữ lập trình

HỌC VIỆN NÔNG NGHIỆP VIỆT NAM

KHOA CÔNG NGHỆ THÔNG TIN

Chương 6

Thuật toán và Ngôn ngữ lập trình

Khoa Công nghệ thông ꢀn – Học viện Nông nghiệp Việt nam

Bài giảng Tin học đại cương

NỘI DUNG CHƯƠNG 6

1. PHƯƠNG PHÁP GIẢI QUYẾT VẤN ĐỀ BẰNG MÁY TÍNH

2. THUẬT TOÁN

2.1. Khái niệm thuật toán

2.2. Các tính chất của thuật toán

2.3. Độ phức tạp của thuật toán

2.4. Các cách diễn đạt thuật toán

3. NGÔN NGỮ LẬP TRÌNH

3.1. Khái niệm về ngôn ngữ lập trình

3.2. Lịch sử phát triển của ngôn ngữ lập trình

3.3. Trình biên dịch và trình thông dịch

3.4. Các công việc của lập trình

Chương 6: Thuật toán và Ngôn ngữ lập trình

2

Khoa Công nghệ thông ꢀn – Học viện Nông nghiệp Việt nam

Bài giảng Tin học đại cương

1. PHƯƠNG PHÁP GIẢI QUYẾT VẤN ĐỀ BẰNG MÁY TÍNH

•ꢀ Phương pháp chung để giải quyết vấn đề (bài toán) bằng

máy tính được thể hiện theo sơ đồ sau:

Cho một bài toán nghĩa là phải xác định dữ

liệu cần nhập vào máy ꢁnh và ꢂm đầu ra

BÀI TOÁN

Tìm ra cách xử lý dữ liệu đầu vào

THUẬT TOÁN

Viết chương trình bằng một ngôn ngữ lập

trình nào đó

CHƯƠNG TRÌNH

NGÔN NGỮ MÁY

MÁY THỰC HIỆN

Biên dịch chương trình sang ngôn ngữ

máy

Chương 6: Thuật toán và Ngôn ngữ lập trình

3

Khoa Công nghệ thông ꢀn – Học viện Nông nghiệp Việt nam

Bài giảng Tin học đại cương

NỘI DUNG CHƯƠNG 6

1. PHƯƠNG PHÁP GIẢI QUYẾT VẤN ĐỀ BẰNG MÁY TÍNH

2. THUẬT TOÁN

2.1. Khái niệm thuật toán

2.2. Các tính chất của thuật toán

2.3. Độ phức tạp của thuật toán

2.4. Các cách diễn đạt thuật toán

3. NGÔN NGỮ LẬP TRÌNH

3.1. Khái niệm về ngôn ngữ lập trình

3.2. Lịch sử phát triển của ngôn ngữ lập trình

3.3. Trình biên dịch và trình thông dịch

3.4. Các công việc của lập trình

Chương 6: Thuật toán và Ngôn ngữ lập trình

4

Khoa Công nghệ thông ꢀn – Học viện Nông nghiệp Việt nam

Bài giảng Tin học đại cương

2.1 Khái niệm thuật toán

•ꢀ Thuật toán (thuật giải, algorithms): là tập hợp hữu hạn

các thao tác, phép toán được thực hiện theo một trình tự

xác định trên một số đối tượng dữ liệu nào đó để đạt được

kết quả mong muốn.

•ꢀ Để tìm thuật toán cho một bài toán ta cần xác định dữ liệu

vào (input) và dữ liệu ra (output) cho bài toán.

•ꢀ VD: Bài toán giải phương trình bậc 2 ax²+ bx + c = 0

–ꢀ Dữ liệu vào: Giá trị của 3 hệ số a, b, c

–ꢀ Dữ liệu ra: Là nghiệm của phương trình

Chương 6: Thuật toán và Ngôn ngữ lập trình

5

Khoa Công nghệ thông ꢀn – Học viện Nông nghiệp Việt nam

Bài giảng Tin học đại cương

NỘI DUNG CHƯƠNG 6

1. PHƯƠNG PHÁP GIẢI QUYẾT VẤN ĐỀ BẰNG MÁY TÍNH

2. THUẬT TOÁN

2.1. Khái niệm thuật toán

2.2. Các tính chất của thuật toán

2.3. Độ phức tạp của thuật toán

2.4. Các cách diễn đạt thuật toán

3. NGÔN NGỮ LẬP TRÌNH

3.1. Khái niệm về ngôn ngữ lập trình

3.2. Lịch sử phát triển của ngôn ngữ lập trình

3.3. Trình biên dịch và trình thông dịch

3.4. Các công việc của lập trình

Chương 6: Thuật toán và Ngôn ngữ lập trình

6

Khoa Công nghệ thông ꢀn – Học viện Nông nghiệp Việt nam

Bài giảng Tin học đại cương

2.2. Các ꢀnh chất của thuật toán

•ꢀ Tính kết thúc

•ꢀ Tính thực hiện được

•ꢀ Tính kết quả

•ꢀ Tính hiệu quả

•ꢀ Tính duy nhất

•ꢀ Tính hình thức

Chương 6: Thuật toán và Ngôn ngữ lập trình

7

Khoa Công nghệ thông ꢀn – Học viện Nông nghiệp Việt nam

Bài giảng Tin học đại cương

NỘI DUNG CHƯƠNG 6

1. PHƯƠNG PHÁP GIẢI QUYẾT VẤN ĐỀ BẰNG MÁY TÍNH

2. THUẬT TOÁN

2.1. Khái niệm thuật toán

2.2. Các tính chất của thuật toán

2.3. Độ phức tạp của thuật toán

2.4. Các cách diễn đạt thuật toán

3. NGÔN NGỮ LẬP TRÌNH

3.1. Khái niệm về ngôn ngữ lập trình

3.2. Lịch sử phát triển của ngôn ngữ lập trình

3.3. Trình biên dịch và trình thông dịch

3.4. Các công việc của lập trình

Chương 6: Thuật toán và Ngôn ngữ lập trình

8

Khoa Công nghệ thông ꢀn – Học viện Nông nghiệp Việt nam

Bài giảng Tin học đại cương

2.3. Độ phức tạp của thuật toán

•ꢀ Đánh giá một thuật ta dựa vào hai tiêu chí sau:

–ꢀ Thời gian thực hiện: Đây là tiêu chí chủ yếu để đánh giá

–ꢀ Dung lượng bộ nhớ sử dụng

•ꢀ Đánh giá thời gian thực hiện thuật toán người ta dùng “Độ

phức tạp tính toán của thuật toán”.

=> Độ phức tạp tính toán của thuật toán là thời gian thực

hiện của thuật toán được đánh giá mà không phụ thuộc vào

máy tính và các yếu tố liên quan, chỉ phụ thuộc vào kích

thước của dữ liệu đầu vào.

Chương 6: Thuật toán và Ngôn ngữ lập trình

9

Khoa Công nghệ thông ꢀn – Học viện Nông nghiệp Việt nam

Bài giảng Tin học đại cương

2.3. Độ phức tạp của thuật toán

•ꢀ Gọi n là kích thước của dữ liệu vào, thì thời gian thực hiện T của

một giải thuật được biểu diễn như một hàm của n, gọi là T(n).

•ꢀ Nếu T(n) = Cn²trong đó C là hằng số, thì ta nói độ phức tạp tính

toán của thuật toán này có cấp n², kí hiệu là: T(n) = O(n²)

•ꢀ Tổng quát:

–ꢀ Hàm f(n) có độ phức tạp tính toán cấp g(n) nếu hàm f(n) bị chặn bởi

Cg(n), với C là hằng số. Kí hiệu là f(n) = O(g(n))

•ꢀ Các hàm thể hiện độ phức tập tính toán của giải thuật có các

dạng sau: nⁿ, n!, 2ⁿ, n³, n², nlog₂n, n, log₂n. Các hàm đó đã

được sắp theo thứ tự ưu tiên giá trị giảm dần

Chương 6: Thuật toán và Ngôn ngữ lập trình

10

Khoa Công nghệ thông ꢀn – Học viện Nông nghiệp Việt nam

Bài giảng Tin học đại cương

NỘI DUNG CHƯƠNG 6

1. PHƯƠNG PHÁP GIẢI QUYẾT VẤN ĐỀ BẰNG MÁY TÍNH

2. THUẬT TOÁN

2.1. Khái niệm thuật toán

2.2. Các tính chất của thuật toán

2.3. Độ phức tạp của thuật toán

2.4. Các cách diễn đạt thuật toán

3. NGÔN NGỮ LẬP TRÌNH

3.1. Khái niệm về ngôn ngữ lập trình

3.2. Lịch sử phát triển của ngôn ngữ lập trình

3.3. Trình biên dịch và trình thông dịch

3.4. Các công việc của lập trình

Chương 6: Thuật toán và Ngôn ngữ lập trình

11

Khoa Công nghệ thông ꢀn – Học viện Nông nghiệp Việt nam

Bài giảng Tin học đại cương

2.4. Các cách diễn đạt thuật toán

Cách 1:

•ꢀ Liệt kê các bước bằng lời: Sử dụng ngôn ngữ tự nhiên để liệt kê

các công việc của thuật toán qua các bước: Bước 1, Bước 2, Bước 3…

VD: Cho hai số m, n tìm d = USCLN(m,n)

Bước 1: Kiểm tra nếu m= n thì về bước 5, nếu không thực hiện tiếp bước

2

Bước 2: Nếu m> n thì về bước 4 nếu không thực hiện tiếp bước 3

Bước 3: m <n, bớt m đi một lượng bằng n và quay về bước 1

Bước 4: bớt m đi một lượng bằng n và quay về bước 1

Bước 5: Lấy d chính là giá trị chung của m và n. Kết thúc

Chương 6: Thuật toán và Ngôn ngữ lập trình

12

Khoa Công nghệ thông ꢀn – Học viện Nông nghiệp Việt nam

Bài giảng Tin học đại cương

VÍ DỤ CÁC BƯỚC CỦA THUẬT TOÁN EUCLID

Bước 1: Kiểm tra nếu m= n thì về bước 5,

m n So sánh

nếu không thực hiện tiếp bước 2

15 21 m>n

Bước 2: Nếu m> n thì về bước 4 nếu không

thực hiện tiếp bước 3

15 6 m>n

Bước 3: m <n, bớt m đi một lượng bằng n

và quay về bước 1

9 6 m>n

Bước 4: bớt m đi một lượng bằng n và quay

3 6 m<n

về bước 1

Bước 5: Lấy d chính là giá trị chung của m

3 3 m=n

và n. Kết thúc

USCLN(15,21) = 3

Chương 6: Thuật toán và Ngôn ngữ lập trình

13

Khoa Công nghệ thông ꢀn – Học viện Nông nghiệp Việt nam

Bài giảng Tin học đại cương

2.4. Các cách diễn đạt thuật toán

Cách 2:

•ꢀ Dùng lưu đồ thuật toán: Sử dụng các hình vẽ

cơ bản để vẽ hình có hướng đi thể hiện các công

việc và trình tự thực hiện thuật toán.

•ꢀ Các hình cơ bản gồm có: Bắt đầu, Kết thúc,

Vào/Ra dữ liệu, Thực hiện một công việc A, Kiểm

tra điều kiện đúng/sai.

Chương 6: Thuật toán và Ngôn ngữ lập trình

14

Khoa Công nghệ thông ꢀn – Học viện Nông nghiệp Việt nam

Bài giảng Tin học đại cương

Các hình cơ bản gồm có:

Khối thao tác

Khối output

Khối input

đối tượng:= biểu

thức

Khởi đầu Kết thúc

Thứ tự xử lý

Khối điều kiện

+

-

Chương 6: Thuật toán và Ngôn ngữ lập trình

15

Khoa Công nghệ thông ꢀn – Học viện Nông nghiệp Việt nam

Bài giảng Tin học đại cương

VD: BIỂU DIỄN BẰNG LƯU ĐỒ THUẬT TOÁN EUCLID

Bước 1: Kiểm tra nếu m= n

thì về bước 5, nếu

không thực hiện tiếp

bước 2

Vào m,n

Đúng

Bước 2: Nếu m> n thì về

bước 4 nếu không thực

hiện tiếp bước 3

Bước 3: m <n, bớt m đi một

lượng bằng n và quay

về bước 1

Sai

So sánh

m=n?

+

Sai

d:= m

Đúng

m>n ?

Bước 4: bớt m đi một lượng

bằng n và quay về

bước 1

Bước 5: Lấy d chính là giá trị

chung của m và n. Kết

thúc

d

m:=m-n

n:= n - m

Chương 6: Thuật toán và Ngôn ngữ lập trình

16

Khoa Công nghệ thông ꢀn – Học viện Nông nghiệp Việt nam

Bài giảng Tin học đại cương

2.4. Các cách diễn đạt thuật toán

Cách 3:

•ꢀ Sử dụng giả ngôn ngữ lập trình (giả mã): Sử dụng

ngôn ngữ tự nhiên kết hợp với một số từ khóa và cấu

trúc điều khiển trong ngôn ngữ lập trình bậc cao để

diễn tả các công việc của thuật toán.

•ꢀ VD: Viết thuật toán ꢂm USCL của 2 số nguyên dương

Chương 6: Thuật toán và Ngôn ngữ lập trình

17

Khoa Công nghệ thông ꢀn – Học viện Nông nghiệp Việt nam

Bài giảng Tin học đại cương

VD: Viết thuật toán tìm USCL của 2 số nguyên

dương

Trong khi m ≠ n thì lặp lại khối sau:

read(m,n);

while m <> n do

if m>n then

m:=m-n

Nếu m > n thì

Bớt m đi một lượng là n

Nếu ngược lại thì

else

Bớt n đi một lượng là m

n:= n-m;

write(m);

Cho tới khi m = n thì kết luận USCLN

chính là giá trị chung của m và n

Chương trình

trong PASCAL

Chương 6: Thuật toán và Ngôn ngữ lập trình

18

Khoa Công nghệ thông ꢀn – Học viện Nông nghiệp Việt nam

Bài giảng Tin học đại cương

NỘI DUNG CHƯƠNG 6

1. PHƯƠNG PHÁP GIẢI QUYẾT VẤN ĐỀ BẰNG MÁY TÍNH

2. THUẬT TOÁN

2.1. Khái niệm thuật toán

2.2. Các tính chất của thuật toán

2.3. Độ phức tạp của thuật toán

2.4. Các cách diễn đạt thuật toán

3. NGÔN NGỮ LẬP TRÌNH

3.1. Khái niệm về ngôn ngữ lập trình

3.2. Lịch sử phát triển của ngôn ngữ lập trình

3.3. Trình biên dịch và trình thông dịch

3.4. Các công việc của lập trình

Chương 6: Thuật toán và Ngôn ngữ lập trình

19

Khoa Công nghệ thông ꢀn – Học viện Nông nghiệp Việt nam

Bài giảng Tin học đại cương

3.1. Khái niệm về ngôn ngữ lập trình

•ꢀ Ngôn ngữ lập trình (programming language : Tập

hợp các ký hiệu và các quy tắc viết các lệnh để thể hiện

thuật toán

•ꢀ Ngôn ngữ lập trình gồm 2 loại chính:

–ꢀ Ngôn ngữ lập trình bậc thấp (hợp ngữ, assembly):

•ꢀ Có cấu trúc lệnh rất giống với ngôn ngữ máy, chỉ

khác là dùng mã chữ thay cho mã nhị phân.

•ꢀ Ví dụ: Lệnh ADD AX, BX cộng (Addition) nội dung

thanh ghi AX và BX, kết quả để trong AX.

Chương 6: Thuật toán và Ngôn ngữ lập trình

20