Bài 5. Giải thuật xử lý thông tin và ngôn ngữ lập trình

Bài 5. Giải thuật xử lý thông tin và ngôn ngữ lập trình KHOA CÔNG NGHỆ THÔNG TIN BỘ MÔN CÔNG NGHỆ PHẦN MỀM Bài giảng: LẬP TRÌNH CƠ BẢN Tài liệu tham khảo Giải thuật xử lý thông tin và ngôn ngữ lập trình * Giáo trình tin học cơ sở, Hồ Sỹ Đàm, Đào Kiến Quốc, Hồ Đắc Phương. Đại học Sư phạm, 2004 – Chương 7, 9. NỘI DUNG Khái niệm bài toán giải thuật Đặc trưng của giải thuật Các phương pháp diễn đạt giải thuật Sơ lược về đánh giá giải thuật Ngôn ngữ lập trình và các mức khác nhau của ngôn ngữ lập trình Quá trình thực hiện chương trình trên ngôn ngữ bậc cao * Giải thuật xử lý thông tin và ngôn ngữ lập trình 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 * Giải thuật xử lý thông tin và ngôn ngữ lập trình 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. Thay vì phải tính toán theo định nghĩa chỉ làm rõ cấu trúc của USCLN (tích của các ước số chung với số mũ nhỏ nhất) thuật toán Euclid dựa trên các tính chất sau: USCLN(a,b) = USCLN (b,a)) Nếu a> b, USCLN(a,b) = USCLN (a-b,b) USCLN(a,a)= a * Giải thuật xử lý thông tin và ngôn ngữ lập trình 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 m>n 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 * Giải thuật xử lý thông tin và ngôn ngữ lập trình TÍNH NGHIỆM XẤP XỈ VỚI ĐỘ CHÍNH XÁC ε = 0.000001 CỦA PHƯƠNG TRÌNH f(x)= ex- x3 = 0 Sử dụng thuật toán chia đôi dựa vào tính chất: nếu một hàm f liên tục trên đoạn [a,b] có f(a) và f(b) thì phương trình f(x) = 0 nhất định thừa nhận một nghiệm c nằm giữa [a,b] Phương trình có hai nghiệm như trong hình vẽ. Ta vây nghiệm nhỏ hơn trong đoạn [1,4] * Giải thuật xử lý thông tin và ngôn ngữ lập trình TÍNH NGHIỆM XẤP XỈ VỚI ĐỘ CHÍNH XÁC ε = 0.000001 CỦA PHƯƠNG TRÌNH f(x)= ex- x3 = 0 Ta có f(a)>0, f(b) 0 thay a bởi c, sau đó thực hiện bước 4 Nếu f(c) ε, quay về 1, nếu không làm tiếp Dừng, lấy c làm nghiệm * Giải thuật xử lý thông tin và ngôn ngữ lập trình c:= (a+b)/2 b-a 0 ? + - a:= c a:= 1; b:= 4; ε = 0.00001 TÍNH NGHIỆM XẤP XỈ VỚI ĐỘ CHÍNH XÁC ε = 0.000001 CỦA PHƯƠNG TRÌNH f(x)= ex- x3 = 0 b:= c * Giải thuật xử lý thông tin và ngôn ngữ lập trình BIỂU DIỄN BẰNG CẤU TRÚC ĐIỀU KHIỂN Cho ε = 0.000001, a=1 b=4 Lặp lại khối sau: Cho tới khi b-a 0 thì thực hiện khối Nếu ngược lại thì thực hiện khối a:=1; b:= 4; epsi:= 0.000001; repeat c:= (a+b)/2; if epx(c)-sin(c) > 0 then a:=c else b:= c until b-a 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 * Giải thuật xử lý thông tin và ngôn ngữ lập trình HIỆU QUẢ CỦA THUẬT TOÁN Nếu sắp xếp dãy số theo thứ tự tăng dần có thể tìm bằng thuật toán tìm kiếm nhị phân, với tư tưởng thu hẹp dần vùng tìm kiếm 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 ag. Nếu x=ag 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 nhờ một phần mềm có tên là bộ hợp dịch (assembler) đầu tiên bộ hợp dịch sẽ phải bố trí không gian nhớ cho các đối tượng, sau đó thay thế mã lệnh và địa chỉ bằng các mã số. Thay thế được thực hiện với các lệnh macro, là các lệnh tương đương với nhiều lệnh. Kết quả của bước dịch đầu tiên là tạo ra các mô đun đối tượng, là các đoạn chương trình dưới dạng nhị phân nhưng chưa có cấu trúc hoàn chỉnh để sẵn sàng chạy ngay. Thường thực hiện một bước khác là liên kết, để kết hợp nhiều mô đun đối tượng thành một chương trình nhị phân hoàn chỉnh. Sau đó mới nạp chương trình này vào thi hành * Giải thuật xử lý thông tin và ngôn ngữ lập trình NGÔN NGỮ BẬC CAO Ngôn ngữ máy và hợp ngữ phụ thuộc vào máy, lại khó dùng, vì nó buộc người lập trình phải viết tinh tế đến mức lệnh máy. Người ta muốn các ngôn ngữ chỉ diễn tả thuật toán mà thôi, không liên quan đến các hệ lệnh đặc thù của máy tính cụ thể. Các ngôn ngữ này gọi là ngôn ngữ bậc cao (high level language) hay còn gọi là ngôn ngữ thuật toán (algorithmic language) Ngôn ngữ thuật toán có hình thức giống với ngôn ngữ tự nhiên hoặc ngôn ngữ toán học nên dễ diễn đạt hơn nhiều so với ngôn ngữ máy hoặc hợp ngữ * Giải thuật xử lý thông tin và ngôn ngữ lập trình VÍ DỤ VỀ NGÔN NGỮ BẬC CAO Ví dụ giải phương trình bậc 2 trên PASCAL DELTA := B*B - 4*A*C; IF DELTA >= 0 THEN BEGIN X1 := (- B + SQRT(DELTA))/(2*A); X2 := (- B - SQRT(DELTA))/(2*A); WRITE (X1,X2); END ELSE WRITE(‘Vô nghiệm) FORTRAN DELTA = B*B - 4* A*C IF DELTA toàn bộ các quá trình soạn thảo, dịch, liên kết , thi hành và gỡ lỗi được thực hiện trong cùng một mối trường liên hệ chặt chẽ bước phát triển tiếp của IDE là việc phát triển hướng đối tượng, phát triển theo mẫu, lập trình hướng tới thành phần (liên kết động các thành phần có sẵn trong mã nhị phân) làm việc sinh mã chương trình trở nên hiệu quả hơn rất nhiều. Các hệ CASE (Computer Aided Software Engineering) còn cho phép phát sinh mã trên nền thiết kế là một bước tiến theo một khuynh hướng khác. * Giải thuật xử lý thông tin và ngôn ngữ lập trình Tóm tắt nội dung Ngôn ngữ lập trình là phương tiện diễn tả thuật toán để máy tính có thể sử dụng trực tiếp hoặc gián tiếp. Theo mức trừu tượng hoá có các mức là ngôn ngữ máy, hợp ngữ và ngôn ngữ thuật toán. Đối với hợp ngữ phải sử dụng phần mềm hợp dịch, với ngôn ngữ thuật toán phải dùng phần mềm biên dịch để tạo ra phần mềm tương ứng trong ngôn ngữ máy – ngôn ngữ mà máy có thể chạy trực tiếp. Các bước chính để dịch từ một chương trình nguồn sang mã nhị phân là soạn thảo, phân tích từ vựng, phân tích cú pháp, dịch, tối ưu hoá, liên kết mã. Trong các môi trường tích hợp các khâu trên và cả khâu gỡ lỗi được tích hợp vào trong một tổng thể. * Giải thuật xử lý thông tin và ngôn ngữ lập trình THẢO LUẬN Sự khác biệt giữa các mức ngôn ngữ lập trình, nguyên tắc phân biệt các mức của NNLT. Đánh giá hiệu quả của các thuật toán khác nhau cùng giải quyết 1 bài toán. Phân tích ưu, nhược điểm của từng phương pháp biểu diễn giải thuật? * Giải thuật xử lý thông tin và ngôn ngữ lập trình 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ố * Giải thuật xử lý thông tin và ngôn ngữ lập trình CÂU HỎI VÀ BÀI TẬP So sánh ngôn ngữ thuật toán với ngôn ngữ máy và hợp ngữ Kể tên một số ngôn ngữ lập trình mà bạn biết Nếu các bước thực hiện một chương trình trên ngôn ngữ thuật giải Phân biệt lỗi cú pháp và lỗi ngữ nghĩa Trình bày môi trường phát triển tích hợp * Giải thuật xử lý thông tin và ngôn ngữ lập trình HỎI VÀ ĐÁP Máy tính điện tử và xử lý thông tin