Kỹ thuật lập trình - Chương 4: Giải thuật xử lý thông tin và ngôn ngữ lập trình

Chương 4. Giải thuật xử lý thông tin và ngôn ngữ lập trình HỌC VIỆN KTQSKHOA CÔNG NGHỆ THÔNG TIN Học phần: LẬP TRÌNH CƠ BẢNTà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 DUNGKhái niệm bài toán và giải thuật Đặc trưng (yêu cầu) của giải thuậtCác phương pháp diễn đạt giải thuậtSơ lược về đánh giá giải thuậtNgôn ngữ lập trình và các mức khác nhau của ngôn ngữ lập trìnhQuá 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ìnhKHÁI NIỆM BÀI TOÁNCho số tự nhiên nn có phải số nguyên tố hay không“có” hay “không” Cho hồ sơ điểm sinh viênTìm tất cả các sinh viên có điểm trung bình trên 8Danh sách sv thoả mãn Thiết kế hình học, tải trọngTính sức bền Độ bền InputYêu cầuOutputCho 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ìnhKHÁI NIỆM THUẬT TOÁNThuậ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ìnhTHUẬT TOÁN EUCLID TIM USCLN CỦA HAI SỐ TỰ NHIÊNBà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 2Bước 2: Nếu m> n thì về bước 4 nếu không thực hiện tiếp bước 3Bước 3: m nm>nmn ?+- m:=m-nd:= m*Giải thuật xử lý thông tin và ngôn ngữ lập trìnhBắt đầuKết thúcBIỂU DIỄN BẰNG GIẢ MÃ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à nread(m,n);while m n do if m>n m=m-n else n= n-m;write(m);Đ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à nBớ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ìnhTÍNH NGHIỆM XẤP XỈ VỚI ĐỘ CHÍNH XÁC ε = 0.000001 CỦA PHƯƠNG TRÌNH f(x)= ex- x3 = 0Sử 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ìnhTÍNH NGHIỆM XẤP XỈ VỚI ĐỘ CHÍNH XÁC ε = 0.000001 CỦA PHƯƠNG TRÌNH f(x)= ex- x3 = 0Ta có f(a)>0, f(b) 0 thay a bởi c, sau đó thực hiện bước 4Nếu f(c) ε, quay về 1, nếu không làm tiếpDừng, lấy c làm nghiệm abc*Giải thuật xử lý thông tin và ngôn ngữ lập trình c:= (a+b)/2b-a 0 ?+- a:= ca:= 1; b:= 4; ε = 0.00001TÍ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ìnhBIỂU DIỄN BẰNG GIẢ MÃCho ε = 0.000001, a=1 b=4Lặp lại khối sau:Cho tới khi b-a 0 thì thực hiện khốiNếu ngược lại thì thực hiện khối a=1; b= 4; epsi= 0.000001;do c= (a+b)/2; if (epx(c)-sin(c) > 0) a=c else b= cwhile (b-a n. Nếu đúng về bước 4. Nếu sai quay về bước 2Bước 4. Tuyên bố không có số x. Kết thúcBước 5. Tuyên bố số x chính là số thứ i. Kết thúcSố 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ìnhHIỆU QUẢ CỦA THUẬT TOÁNNế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ếmBướ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 4Bướ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 theoBước 5. Nếu x AX1010 0011 0000 0000 0010 1011 A3 00 2B Ghi từ AX về 2B00*Giải thuật xử lý thông tin và ngôn ngữ lập trìnhHỢP NGỮ (ASSEMBLY)Về cơ bản, mỗi lệnh hợp ngữ tương tự với một lệnh máy – nhưng dùng mã chữ nên dễ hiểu, dễ sửa.Phải dịch ra ngôn ngữ máy (thay mã lệnh và địa chỉ)Có các lệnh macro, cho phép thay thế hiệu quả hơnƯu điểm: dễ lập trình dễ sửa lỗi hơn ngôn ngữ máyNhược điểm: vẫn còn phức tạp và phụ thuộc vào máyHợp ngữMã máy trong hệ hexaMOV AX CHIEU_DAI A1 64 10ADD AX CHIEU_RONG 03 66 10 MOV NUA_CHU_VI AX A3 00 2B *Giải thuật xử lý thông tin và ngôn ngữ lập trìnhDỊCH HỢP NGỮ (ASSEMBLY)Để máy có thể chạy được thì phải dịch chương trình trên hợp ngữ thành một chương trình trên ngôn ngữ máy -> 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ìnhNGÔN NGỮ BẬC CAONgô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ìnhVÍ DỤ VỀ NGÔN NGỮ BẬC CAOVí dụ giải phương trình bậc 2 trên PASCALDELTA := 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); ENDELSE 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ìnhTóm tắt nội dungNgô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ìnhTHẢO LUẬNSự 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 một 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ìnhCÂU HỎI VÀ BÀI TẬPThuậ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ìnhCÂU HỎI VÀ BÀI TẬPSo 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ếtNếu các bước thực hiện một chương trình trên ngôn ngữ thuật giảiPhân biệt lỗi cú pháp và lỗi ngữ nghĩaTrì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ìnhHỎI VÀ ĐÁPMáy tính điện tử và xử lý thông tin