Bài giảng Nhập môn tin học: Chương 3 - Trần Phước Tuấn

Chương 3 của bài giảng sẽ đề cập đến việc giải bài toán trên máy tính. Trong chương này sẽ tìm hiểu các nội dung: Vấn đề - bài toán, thuật toán - thuật giải, các phương pháp biểu diễn thuật toán, các bước giải một bài toán trên máy tính, tổng quan về ngôn ngữ lập trình. Mời các bạn cùng tham khảo.
Nội dung trích xuất từ tài liệu:
Bài giảng Nhập môn tin học: Chương 3 - Trần Phước Tuấn Ch ng 3 Gi i Bài Toán Trên Máy TínhTr n Ph c Tu ntranphuoctuan.khoatoan.dhsp@gmail.comhttp://baigiang.tranphuoctuan.com i dung bài h c1. n - bài toán2. Thu t toán - thu t gi i3. Các ph ng pháp bi u di n thu t toán4. Các b c gi i m t bài toán trên máy tính5. ng quan v ngôn ng p trình Page 2 T.P.Tu n-NH P MÔN TIN H C 12/12/20091. V n - bài toánKhái ni m • n th ng c dùng v i ngh a r ng h n bài toán, bài toán là v n mà gi i quy t nó ph i liên quan ít nhi u n tính toán • Pitago chia m i v n mà con ng i c n gi i quy t thành hai lo i: – Theorema: v n n kh ng nh tính úng – sai – Problema: v n n tìm gi i pháp t c m c tiêu t nh ng u ki n ban u nào ó Page 3 T.P.Tu n-NH P MÔN TIN H C 12/12/20091. V n - bài toánKhái ni m • Theo nhi u k t qu nghiên c u: vi c gi i quy t n - bài toán mà Pitago nêu ra u có th di n ra theo m t s chung: A B • ây: – A có th là gi thi t, i u ki n ban u – B có th là k t lu n, m c tiêu c n t – là suy lu n, gi i pháp c n xác nh Page 4 T.P.Tu n-NH P MÔN TIN H C 12/12/20091. V n - bài toánKhái ni m • Ví d 1: Bài toán ki m tra tính nguyên t – Cho: S nguyên d ng N – n bi t: N có là s nguyên t hay không? • Ví d 2: Bài toán qu n lý h sinh viên – Cho: H g c c a các sinh viên trong tr ng – n bi t: B ng th ng kê, phân lo i sinh viên theo k t qu ct p Page 5 T.P.Tu n-NH P MÔN TIN H C 12/12/20091. V n - bài toánKhái ni m • u trúc m t bài toán: – Thông tin u vào (input): cái cho tr c – Thông tin u ra (output): cái c n tìm • Gi i bài toán: là vi c xác nh t ng minh output theo input b ng m t quá trình có th th c hi n m t cách hi u qu Page 6 T.P.Tu n-NH P MÔN TIN H C 12/12/20092. Thu t toán – thu t gi iThu t toán – khái ni m • Thu t toán là khái ni m c s a toán h c và tin h c • Thu t toán là m t dãy các ch th rõ ràng và có th thi hành c ng d n th c hi n hành ng nh m t c m c tiêu t ra • Thu t toán là s th hi n c a m t ph ng pháp gi i quy t v n Page 7 T.P.Tu n-NH P MÔN TIN H C 12/12/20092. Thu t toán – thu t gi iThu t toán – c tr ng• Nh p (input). Các thu t toán th ng có giá tr u vào• Xu t (output). T giá tr vào thu t toán cho ra k t qu .• Tính xác nh (definiteness). Các b c trong thu t toán ph i chính xác rõ ràng.• Tính h u h n (finiteness). Thu t toán ph i cho ra l i gi i (hay k t qu ) sau m t s c h u h n.• Tính hi u qu . Tính hi u qu 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 s ng (khi th c hi n thu t toán trên máy tính).• Tính t ng quát. Thu t toán ph i áp d ng c cho t t c các bài toán cùng d ng, ch không ch áp d ng c cho m t s tr ng p riêng l nào ó. Page 8 T.P.Tu n-NH P MÔN TIN H C 12/12/20092. Thu t toán – thu t gi iThu t toán – ví d Thu t toán gi i ph ng trình b c hai: AX2 + BX + C = 0 (A 0) -B c 1 : Tính DELTA = B*B-4*A*C -B c 2 : So sánh DELTA v i s 0 -B c 3 : R làm 3 tr ng h p : . -Tr ng h p DELTA < 0 : vô nghi m; -Tr ng h p DELTA = 0 : B X1 X 2 2* A -Tr ng h p DELTA > 0 : b b 2 4ac X 1,2 2a Page 9 T.P.Tu n-NH P MÔN TIN H C 12/12/20092. Thu t toán – thu t gi iThu t toán – các c u trúc c b n 1. Tu n t : th c hi n h t l nh này n nh khác 2. nhánh: tùy theo d li u u vào mà ta quy t nh th c hi n câu l nh gì ti p theo 3. p: th c hi n l i nhi u l n m t s câu nh nào ó cho n khi u ki n không còn th a mãn n a Page 10 T.P.Tu n-NH P MÔN TIN H C 12/12/20092. Thu t toán – thu t gi iThu t gi i• Khái ni m thu t toán ã trình bày chính là cánh a khép kín cho vi c gi i các bài toán vì: – Nhi u bài toán không th a các c tr ng c b n a thu t toán. – Có nhi u bài toán ch a tìm ra thu t toán ho c ch a ch ng minh c là có thu t toán hay không. – Có nh ng bài toán có thu t toán nh ng khó th c hi n ho c không th c hi n c Page 11 T.P.Tu n-NH P MÔN TIN H C 12/12/20092. Thu t toán – thu t gi iThu t gi i• nh ng nh n ...