Bài giảng Toán rời rạc - Chương 1: Thuật toán - Nguyễn Lê Minh

Toán rời rạcChương 1: THUẬT TOÁNGV: Nguyễn Lê MinhBộ môn: Công nghệ thông tin7/29/20211Nội dungKhái niệm thuật toánTính chất của thuật toánCác cách biểu diễn thuật toánCấu trúc cơ bản của thuật toánMột số thuật toán cơ bảnBài tập7/29/20212Nội dungKhái niệm thuật toánTính chất của thuật toánCác cách biểu diễn thuật toánCấu trúc cơ bản của thuật toánMột số thuật toán cơ bảnBài tập7/29/202131. Khái niệm thuật toánThuật toán là một tập hữu hạn các bước, các phép toán cơ bản được sắp xếp theo một trình tự nhất định để từ thông tin đầu vào của bài toán sau một tập hữu hạn các bước đó sẽ đạt được kết quả ở đầu ra như mong muốn.InputAlgorithmOutput7/29/202141. Khái niệm thuật toánThông thường, thuật toán dùng để giải một lớp các bài toán cụ thế. Gồm 2 thành phần chính:Input : Thông tin bài toán đã choOutput : Thông tin cần tìm hoặc trả lời câu hỏi cần thiếtVí dụ: S = a *b7/29/202151. Khái niệm thuật toánVí dụ : Giải phương trình bậc nhất P(x): ax + b = 0, (a, b là các số thực)Input : a, bOutput : Kết quả P(x)Mô tả thuật toán:Nếu a = 0Nếu b = 0 thì P(x) có nghiệm bất kìNếu b 0 thì P(x) vô nghiệmNếu a 0P(x) có duy nhất một nghiệm x = -b/a7/29/202161. Khái niệm thuật toánVí dụ 2 : Kiểm tra một số nguyên X có chia hết cho 5 không ?Input : XOutput : Kết quả kiểm tra ResultMô tả thuật toán:Bước 1: Tìm số dư r của phép chia x cho 5Bước 2: Kiểm traNếu r = 0 thì result = TrueNếu r 0 thì result = False7/29/20217Nội dungKhái niệm thuật toánTính chất của thuật toánCác cách biểu diễn thuật toánCấu trúc cơ bản của thuật toánMột số thuật toán cơ bảnBài tập7/29/202182. Tính chất của thuật toánTính dừngTính xác địnhTính đúngÐầu vào và đầu ra (input/output)Tính hiệu quả Tính tổng quát 7/29/202192. Tính chất của thuật toánTính dừng : Thuật toán phải bao đảm được kết thúc sau một số hữu hạn bước.Tính dừng là tính dễ bị vi phạm, thường là do sai sót khi trình bày thuật toán dẫn đến “Lặp vô tận”.7/29/2021102. Tính chất của thuật toánThuật toán phải có tính xác định: các bước trong thuật toán phải được xác định rõ ràng, có thể thực thi được, không gây mập mờ, nhập nhằng, tùy chọn.7/29/2021112. Tính chất của thuật toánThuật toán phải có Tính đúng đắn: để đảm bảo kết quả tính toán hay các thao tác mà máy tính thực hiện được là chính xác.Trong một kỳ thi kiểm tra không phải tất cả các học sinh điều đưa ra được lời giải “đúng”.Khi thiết kế thuật toán cần kiểm nghiệm và chỉnh sửa nhiều lần để có được một thuật toán đúng.7/29/2021122. Tính chất của thuật toánÐầu vào và đầu ra (input/output): Mọi thuật toán đều có đại lượng vào và ra.Tính hiệu quả: Một bài toán có thể có nhiều thuật toán khác nhau để giải, một thuật toán tốt thì nó phải hiệu quả, tính hiệu quả của thuật toán được đánh giá dựa trên một số tiêu chuẩn như khối lượng tính toán, không gian và thời gian khi thuật toán được thi hành.Tính tổng quát: Thuật toán có tính tổng quát là thuật toán phải áp dụng được cho mọi trường hợp của bài toán chứ không phải chỉ áp dụng được cho một số trường hợp riêng lẻ nào đó.7/29/202113Nội dungKhái niệm thuật toánTính chất của thuật toánCác cách biểu diễn thuật toánCấu trúc cơ bản của thuật toánMột số thuật toán cơ bảnBài tập7/29/2021143. Các cách biểu diễn của thuật toánSơ đồ khốiLiệt kêMã giả7/29/2021153. Các cách biểu diễn của thuật toánPhương pháp liệt kê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.Các bước được đánh số thứ tự, bước có số thứ tự nhỏ hơn được thực hiện trước.Ưu điểm: Dễ hiểu, dễ thực hiện.Khuyết điểm: Phụ thuộc cách trình bày của người thiết kế, khó áp dụng cho những thuật toán có tính phức tạp.7/29/2021163. Các cách biểu diễn của thuật toánVí dụ : Giải phương trình bậc nhất P(x): ax +b = 0:Input: a,bOutput: Kết quả giải phương trình.Bước 1: Nhập vào 2 số thực a, bBước 2: Kiểm tra nếu a = 0 thực hiện:Bước 2.1: Nếu b = 0 thì phương trình vô số nghiệmBước 2.2: Nếu b 0 thì phương trình vô nghiệmBước 3: Khi a 0 phương trình có nghiệm x=-b/aBước 4: Kết thúc thuật toán7/29/2021173. Các cách biểu diễn của thuật toánPhương pháp sơ đồ khốiSử dụng các hình khối để biểu diễn các lệnh hay thao tác.Sử dụng mũi tên để biểu diễn thứ tự thực hiện.Ưu điểm: Diễn đạt khoa học, có tính nhất quán, dễ hiểu và dễ kiểm tra.Khuyết điểm: Phải vẽ nhiều hình, cồng kềnh, không phù hợp với các thuật toán phức tạp.7/29/2021183. Các cách biểu diễn của thuật toánHìnhÝ nghĩaBắt đầu thuật toánKết thúc thuật toánNhập dữ liệuXuất dữ liệuBeginEndInputOutput7/29/2021193. Các cách biểu diễn của thuật toánHìnhÝ nghĩaCâu lệnh rẽ nhánhNếu đúng thì thực hiện nhánh ĐNếu sai thì thực hiện nhánh SBiểu diễn thực hiện công việc ABiểu diễn việc gọi chương trình con AHướng của thuật toánEndBiểu thứcĐ S AA7/29/2021203. Các cách biểu diễn của thuật toán7/29/2021213. Các cách biểu diễn của thuật toán7/29/2021223. Các cách biểu diễn của thuật toánPhương pháp mã giảDựa trên các ngôn ngữ bậc cao (Pascal, C...)Sử dụng ngôn ngữ tự nhiên con ngườiƯu điểm: Tương tự ngôn ngôn ngữ lập trình và ngôn ngữ tự nhiên, chuyển từ thuật toán sang chương trình dễ dàng.Khuyết điểm: Viết như cách biểu diễn liệt kê, khó bao quát với những bài toán nhiều chương trình. Phải làm quen với những ngôn ngữ mới.7/29/2021233. Các cách biểu diễn của thuật toánVí dụ: Tính tổng n số tự nhiên đầu tiênNhập n i:=0 s:=0REPEAT s=s+i; i=i+1;UNTIL (i>n)Xuất s7/29/202124Nội dungKhái niệm thuật toánTính chất của thuật toánCác cách biểu diễn thuật toánCấu trúc cơ bản của thuật toánMột số thuật toán cơ bảnBài tập7/29/2021253. Các cấu trúc cơ bản của thuật toánRẽ nhánhTuần tựLặp7/29/2021264. Các cấu trúc cơ bản của thuật toánCấu trúc tuần tự:Gồm nhiều bước, sắp xếp theo trình tự nhất định, chương trình được thực hiện theo các bước đã tạo sẵn.Trong biểu diễn thuật toán bằng phương pháp liệt kê từng bước cấu trúc tuần tự được thể hiện ở việc mô tả cụ thể bước thứ i thực hiện: Bước 1, Bước 2, Bước 2.1, .. Khi dùng sơ đồ khối ta sử dụng để biểu diễn thứ tự thực hiện của thuật toán.7/29/2021274. Các cấu trúc cơ bản của thuật toánCấu trúc rẽ nhánh:Là cấu trúc kiểm tra một điều kiện, khi điều kiện đúng chương trình sẽ thực hiện theo nhánh đúng, khi điều kiện sai chương trình sẽ thực hiện theo nhánh sai.7/29/2021284. Các cấu trúc cơ bản của thuật toánCấu trúc lặp:Là cấu trúc lặp đi lặp lại một hành động nhiều lần:Số lần lặp xác định trước.Số lần lặp không xác định trước.7/29/202129Nội dungKhái niệm thuật toánTính chất của thuật toánCác cách biểu diễn thuật toánCấu trúc cơ bản của thuật toánMột số thuật toán cơ bảnBài tập7/29/2021304. Một số thuật toán cơ bảnTính chu vi và diện tích hình trònCho 3 số a,b,c. In ra màn hình 3 số sau khi đã cộng thêm 1Nhập n. Nếu n>0, in ra màn hình n sau khi bình phươngTính tổng dãy số p = 1+2+3+...+nTính tích dãy số p = 1x2x3x...xnTìm n min thỏa mãn S = 1 + ½ + 1/3 + ... + 1/n >= 37/29/2021314. Một số thuật toán cơ bảnKiểm tra xem N có phải là 1 số nguyên tố không ?Ý tưởng :Nếu N=1 -> N không là số nguyên tốNếu 14 -> N là số nguyên tốNếu N >= 4 : Tìm ước i > 1 của N + Nếu i N không phải số nguyên tố ( vì N có ít nhất 3 ước N, i, 1) + Nếu i=N -> N là số nguyên tố7/29/2021324. Một số thuật toán cơ bảnTính tổng dãy sốTính tích dãy sốTìm kiếm một số có trong dãy hay khôngĐếm số lượng phần tử thỏa mãn điều kiệnTìm giá trị max, minSắp xếp tăng, giảm dãy số7/29/2021334. Một số thuật toán cơ bảnTính tổng: Cho dãy n phần tử a1,a2,a3....an Hãy tính tổng ra dãy số trênÝ tưởng:Sử dụng một biến để tính tổng các phần tử. Ban đầu biến này bằng 0.- Duyệt từng phần tử và cộng phần tử vào biến tổng.7/29/2021344. Một số thuật toán cơ bản7/29/2021354. Một số thuật toán cơ bảnTính tổng: Cho dãy n phần tử a1,a2,a3....an Hãy tính tích ra dãy số trênÝ tưởng: tương tự như thuật toán tính tổngSử dụng một biến để tính tích các phần tử. Ban đầu biến này bằng 1 (nếu biến ban đầu bằng 0 thí tích sẽ bằng 0  sai).Duyệt từng phần tử và nhân phần tử vào biến tích.7/29/2021364. Một số thuật toán cơ bảnTính tổng: Cho dãy n phần tử a1,a2,a3....an Kiểm tra số X có nằm trên dãy trên hay không ?Ý tưởng:Sử dụng một biến để đánh đánh dấu xem có tìm thấy phần tử X hay không. Ban đầu biến đánh dấu có giá trị là FALSE.Duyệt từng phần tử, nếu phần tử thứ i có giá trị bằng X thì gán biến đánh dấu là TRUE.7/29/2021374. Một số thuật toán cơ bản7/29/2021384. Một số thuật toán cơ bảnTính tổng: Cho dãy n phần tử a1,a2,a3....an Đếm xem trong dãy có bao nhiêu phần tử thỏa mãn điều kiện nào đó.Ý tưởng:Sử dụng một biến đếm số lượng phần tửDuyệt từng phần tử.Kiểm tra phần tử đó có thỏa điều kiện hay không, nếu thỏa điều kiện thì tăng biến đếm lên 1.7/29/2021394. Một số thuật toán cơ bản7/29/2021404. Một số thuật toán cơ bảnĐếm số chẵn7/29/2021414. Một số thuật toán cơ bảnTính tổng: Cho dãy n phần tử a1,a2,a3....an Tìm phần tử Max – Min trong dãy số.Ý tưởng:Sử dụng một biến lưu giá trị max (min), ban đầu max = a1Duyệt từng phần tử.Kiểm tra phần tử đó có lớn hơn biến giá trị max (nhỏ hơn giá trị min) nếu thỏa điều kiện biến max bằng phần tử đó.7/29/2021424. Một số thuật toán cơ bảnTìm max7/29/2021434. Một số thuật toán cơ bảnTính tổng: Cho dãy n phần tử a1,a2,a3....an Sắp xếp dãy số tăng giảmÝ tưởng:Duyệt từng phần tử:Phần tử đang duyệt được gọi là phần tử hiện tạiThực hiện một vòng lặp con, duyệt các phần tử còn lại. Nếu giá trị của phần tử được duyệt trong vòng lặp con bé hơn phần tử hiện tại  thực hiện việc đổi chỗ 2 phần tử.7/29/2021444. Một số thuật toán cơ bảnTăng dần7/29/202145Nội dungKhái niệm thuật toánTính chất của thuật toánCác cách biểu diễn thuật toánCấu trúc cơ bản của thuật toánMột số thuật toán cơ bảnBài tập7/29/2021465. Bài tập1. Vẽ sơ đồ khối biểu diễn thuật toán tính trung bình cộng dãy số a1,a2,a3,.,an2. Vẽ sơ đồ thuật toán kiểm tra xem số N có phải là số nguyên tố hay không?3. Vẽ sơ đồ khối biểu diễn thuật toán nhập dãy số a1,a2,a3,.,an , sắp xếp và in ra màn hình dãy số tăng dần.4. Vẽ sơ đồ khối biểu diễn thuật toán nhập dãy số a1,a2,a3,.,an , in ra màn hình dãy số theo chiều ngược lại.5. Vẽ sơ đồ khối biểu diễn thuật toán nhập dãy số a1,a2,a3,.,an , xuất ra màn hình 3 số âm lớn nhất trong dãy.6. Vẽ sơ đồ khối biểu diễn thuật toán nhập dãy số a1,a2,a3,.,an , tìm và in ra màn hình số xuất hiện nhiều lần nhất trong dãy trên.7/29/202147