Bài giảng Tin học cơ sở - Bài 7: Thuật toán - Đào Kiến Quốc

BÀI GIẢNG  TIN HỌC CƠ SỞ 
Giảng viên : ĐÀO KIẾN QUỐCMobile 098.91.93.980 Email: dkquoc@vnu.edu.vn 
BÀI 7 . THUẬT TOÁN 
ĐẠI HỌC QUỐC GIA HÀ NỘI 
TRƯỜNG ĐẠI HỌC CÔNG NGHỆ 
NỘI DUNG 
Bài toán và thuật toán 
Các phương pháp biểu diễn thuật toán 
Các đặc trưng của thuật toán 
KHÁI NIỆM BÀI TOÁN 
Cho số tự nhiên n 
n có phải số nguyên tố hay không 
“ có ” hay “ không ” 
 Cho hồ sơ điểm sinh viên 
Tìm tất cả các sinh viên có điểm trung bình trên 8 
Danh sách sv thoả mãn 
 Thiết kế hình học , tải trọng 
Tính sức bền 
Đ ộ bền 
Input 
Yêu cầu 
Output 
Cho một bài toán nghĩa là cho input, và yêu cầu để tìm ( tính ) ra output 
KHÁI NIỆM THUẬT TOÁN 
Thuật toán (algorithm) là một quá trình gồm một dãy hữu hạn các thao tác có thể thực hiện được sắp xếp theo một trình tự xác định dùng để giải một bài toán 
Ví dụ : thuật toán Euclid tìm ước số chung lớn nhất của hai số tự nhiên . 
USCLN(a,b ) = USCLN ( b,a )) 
Nếu a> b, USCLN(a,b ) = USCLN (a- b,b ) 
USCLN(a,a )= a 
THUẬT TOÁN EUCLID TIM USCLN CỦA HAI SỐ TỰ NHIÊN 
Bài toán : 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 
VÍ DỤ CÁC BƯỚC CỦA THUẬT TOÁN EUCLID 
m n 
15 21 
9 6 
15 6 
3 6 
3 3 
m<n 
m>n 
m>n 
m<n 
m=n 
USCLN(15,21) = 3 
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 
CÁC ĐẶC TRƯNG CỦA THUẬT TOÁN 
Input 
Output 
Tính xác định 
Tính khả thi 
Tính dừng 
Tính phổ dụng 
PHƯƠNG PHÁP BIỂU DIỄN THUẬT TOÁN 
Dùng các chỉ dẫn 
Dùng sơ đồ khối 
Dùng cấu trúc điều khiển 
BIỂU DIỄN BẰNG LƯU ĐỒ/SƠ ĐỒ KHỐI 
Khởi đầu 
Kết thúc 
Thứ tự xử lý 
Khối thao tác 
đối tượng := biểu thức 
Khối input 
Khối output 
Khối input 
Khối điều kiện 
+ 
- 
BIỂU DIỄN BẰNG LƯU ĐỒ  thuật toán EUCLID 
n:= n - m 
m=n? 
- 
+ 
 d 
m,n 
m>n ? 
+ 
- 
 m:= m-n 
d:= m 
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 
BIỂU DIỄN BẰNG CẤU TRÚC ĐIỀU KHIỂN 
Trong khi m n thì lặp lại khối sau : 
Cho tới khi m = n thì tuyên bố USCLN chính là giá trị chung của m và n 
read(m,n ); 
while m n do 
 if m>n then 
 m:= m-n 
 else 
 n:= n-m ; 
write(m ); 
Chương trình trong PASCAL 
Điều chỉnh lại giá trị của m và n 
Nếu m > n thì   
Nếu ngược lại thì   
Bớt m đi một lượng là n 
Bớt n đi một lượng là m 
HIỆU QUẢ CỦA THUẬT TOÁN 
Mỗi bài toán có thể có nhiều thuật toán khác nhau : hiệu quả khác nhau 
Độ phức tạp về thời gian : quy về số phép tính cơ bản cần được thực hiện 
Độ phức tạp không gian : sự tiêu tốn không gian nhớ . 
VÍ DỤ HIỆU QUẢ TÌM KIẾM 
	 Bài toán t ìm kiếm : 
	 Cho một dãy n số khác nhau a 1 ,a 2 ... a i ... a n và một số x. Hãy cho biết x có trong dãy số đó hay không và ở vị trí thứ bao nhiêu . Thuật toán tìm kiếm tuần tự như sau : 
Bước 1. Cho i = 1 
Bước 2. Nếu a i = x thì chuyển tới bước 5, nếu không thực hiện tiếp bước 3 
Bước 3. Tăng i lên 1 và kiểm tra i > n. Nếu đúng về bước 4. Nếu sai quay về bước 2 
Bước 4. Tuyên bố không có số x. Kết thúc 
Bước 5. Tuyên bố số x chính là số thứ i. Kết thúc 
	 Số bước tìm trung bình là n/2. 
	 Nếu có 1 triệu phần tử thì phải mất khoảng 500.000 phép so sánh 
HIỆU QUẢ CỦA THUẬT TOÁN 
	 Thuật toán 2: Tìm kiếm nhị phân ( thu hẹp dần vùng tìm kiếm , đối với danh sách đã được sắp xếp ) 
Bước 1. Cho d := 1, c:=n ( d: đầu , c: cuối , g: giữa ) 
Bước 2. Tính g := [(d+c)/2] 
Bước 3. So x với a g . Nếu x= a g chuyển tới bước 7. Nếu khác thì tiếp tục thực hiện bước 4 
Bước 4. Nếu d=c thì tuyên bố không có số x và kết thúc . Nếu không thì thực hiện bước 5 tiếp theo 
Bước 5. Nếu x < a g thì thay c bằng a g và quay về bước 2. Nếu không thì thực hiện bước 6 tiếp theo 
Bước 6. Thay d bằng a g và quay về bước 2 
Bước 7. Tuyên bố số x chính là số thứ g. Kết thúc 
	 Số bước tìm trung bình là log 2 n. 
	 Nếu có 1 triệu phần tử thì chỉ mất khoảng 20 lần tìm , rất nhỏ so với tìm tuần tự 
CÂU HỎI VÀ BÀI TẬP 
Thuật toán là gì ? Cho ví dụ . 
Xác định input và output cho các thuật toán sau đây : 
Rút gọn một phân số . 
Kiểm tra xem ba số cho trước a, b và c có thể là độ dài ba cạnh của một tam giác hay không ? 
Trình bày tính chất xác định của thuật toán và nêu rõ nghĩa của tính chất này 
Cho tam giác ABC có góc vuông A và cho biết cạnh a và góc B. Hãy viết thuật toán để tính góc C, cạnh b và cạnh c. 
Hãy phát biểu thuật toán để giải bài toán sau : " Có một số quả táo . Dùng cân hai đĩa ( không có quả cân ) để xác định quả táo nặng nhất " 
Chỉ dùng phép cộng , tính bình phương của một số