tailieunhanh - Bài giảng Tin học căn bản (Phần 2): Chương 2 - Nguyễn Hồng Phương

Bài giảng "Tin học căn bản (Phần 2) - Chương 2: Thuật toán" cung cấp cho người học các kiến thức: Định nghĩa thuật toán; biểu diễn thuật toán, một số thuật toán thông dụng, thuật toán đệ quy, thuật giải heuristic. . | Chương 2: Thuật toán Ngo Van Linh Bộ môn Hệ thống thông tin Viện Công nghệ thông tin và Truyền thông Đại học Bách Khoa Hà Nội 1 Nội dung chương này . . . . . Định nghĩa thuật toán Biểu diễn thuật toán Một số thuật toán thông dụng Thuật toán đệ quy Thuật giải heuristic 2 . Định nghĩa thuật toán Là một khái niệm cơ sở của toán học và tin học. Bao gồm một dãy hữu hạn các lệnh/chỉ thị rõ ràng và có thể thi hành được để hướng dẫn thực hiện một hành động nhằm đạt được mục tiêu đề ra. Thuật toán là sự thể hiện của một phương pháp để giải quyết một vấn đề. 3 Ví dụ 1: Thuật toán tìm phần tử lớn nhất của một dãy hữu hạn các số nguyên Các bước: 1. Đặt giá trị lớn nhất tạm thời là số nguyên đầu tiên. 2. So sánh số nguyên kế tiếp trong dãy với giá trị lớn nhất tạm thời, nếu số nguyên này lớn hơn giá trị lớn nhất tạm thời thì đặt giá trị lớn nhất tạm thời bằng số nguyên này. 3. Lặp lại bước 2 nếu còn số nguyên trong dãy chưa được xét. 4. Dừng nếu không còn số nguyên nào trong dãy chưa được xét. Giá trị lớn nhất tạm thời lúc này chính là giá trị lớn nhất trong dãy số. 4 Ví dụ 2: Thuật toán giải phương trình bậc hai: ax2 + bx + c = 0 (a 0) 1. Nhập 3 hệ số a, b, c 2. Tính giá trị Δ = b2 - 4*a*c 3. Xét dấu Δ. Nếu Δ>0 thì thực hiện các thao tác sau đây: . Tính các nghiệm theo các công thức: x1 = (-b-sqrt(Δ))/(2*a) x2 = (-b+sqrt(Δ))/(2*a) . Xuất kết quả: phương trình có hai nghiệm x1 và x2. 4. Nếu Δ là 0 thì xuất kết quả: phương trình có nghiệm kép là -b/(2*a) 5. Nếu Δ<0 thì xuất kết quả: phương trình vô nghiệm 6. Dừng thuật .