Giới thiệu Khoa học máy tính - Chương 5

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.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).
Nội dung trích xuất từ tài liệu:
Giới thiệu Khoa học máy tính - Chương 5 THUẬT TOÁN & CHƯƠNG TRÌNH Nguyễn Thanh Trung 1 Giải thuật & chương trình 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. 2 Giải thuật & chương trình 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  3 Giải thuật & chương trình 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. 4 Giải thuật & chương trình 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,… 5 Giải thuật & chương trình 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,…) 6 Giải thuật & chương trình 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  7 Giải thuật & chương trình 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.  8 Giải thuật & chương trình 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 9 Giải thuật & chương trình Đị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,…  10 Giải thuật & chương trình 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 11 Giải thuật & chương trình 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. 12 Giải thuật & chương trình 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ữ  13 Giải thuật & chương trình ...