intTypePromotion=1
zunia.vn Tuyển sinh 2024 dành cho Gen-Z zunia.vn zunia.vn
ADSENSE
 » 
 » 

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

Chia sẻ: Năm Tháng Tĩnh Lặng | Ngày: | Loại File: PDF | Số trang:16

Thêm vào BST
Báo xấu
76
lượt xem 4
download
 
  Download Vui lòng tải xuống để xem tài liệu đầy đủ

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.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

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

  1. Ch ng 3 Gi i Bài Toán Trên Máy Tính Tr n Ph c Tu n tranphuoctuan.khoatoan.dhsp@gmail.com http://baigiang.tranphuoctuan.com i dung bài h c 1. n - bài toán 2. Thu t toán - thu t gi i 3. Các ph ng pháp bi u di n thu t toán 4. Các b c gi i m t bài toán trên máy tính 5. ng quan v ngôn ng p trình Page 2 T.P.Tu n-NH P MÔN TIN H C 12/12/2009
  2. 1. V n - bài toán Khá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/2009 1. V n - bài toán Khá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/2009
  3. 1. V n - bài toán Khá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/2009 1. V n - bài toán Khá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/2009
  4. 2. Thu t toán – thu t gi i Thu 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/2009 2. Thu t toán – thu t gi i Thu 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/2009
  5. 2. Thu t toán – thu t gi i Thu 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/2009 2. Thu t toán – thu t gi i Thu 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/2009
  6. 2. Thu t toán – thu t gi i Thu 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/2009 2. Thu t toán – thu t gi i Thu t gi i • nh ng nh n nh trên ng i ta th y r ng: n ph i có nh ng i m i cho khái ni m thu t toán “Thu t gi i” Page 12 T.P.Tu n-NH P MÔN TIN H C 12/12/2009
  7. 2. Thu t toán – thu t gi i Thu t gi i – m ng tính xác nh • Tính xác nh th c ch t là tính n tr a cách gi i a m t thu t toán và s rõ ràng t i a. • Trong th c t có nhi u bài toán vi ph m tính xác nh mà v n cho k t q a. Nh v y thay cho vi c xây ng toàn b quá trình gi i ch n ch ra cách chuy n t c i sang b c i+1. • Cách g ai ng u nhiên, quy là m ng tính xác nh Page 13 T.P.Tu n-NH P MÔN TIN H C 12/12/2009 2. Thu t toán – thu t gi i Thu t gi i – m ng tính úng n • Tính úng n c hi u là cho k t qu úng. • Trong th c t thì s n úng là có th ch p nh n c • Ngoài ra dùng cách gi i heuristic n gi n, c áo v n có th cho k t q a m t cách sáng t o Page 14 T.P.Tu n-NH P MÔN TIN H C 12/12/2009
  8. 3. Các ph ng pháp bi u di n thu t toán • Ngôn ng nhiên • u - kh i • Mã gi Page 15 T.P.Tu n-NH P MÔN TIN H C 12/12/2009 3. Các ph ng pháp bi u di n thu t toán Ngôn ng nhiên • Li t kê các thao tác, các ch th ng ngôn ng nhiên • Ví d : Có 43 que diêm. Hai ng i ch i luân phiên b c diêm. M i l t, m i ng i b c t 1 n 3 que diêm. Ng i nào b c cu i cùng th ng cu c Page 16 T.P.Tu n-NH P MÔN TIN H C 12/12/2009
  9. 3. Các ph ng pháp bi u di n thu t toán Ngôn ng nhiên • Gi i thu t ng i i tr c luôn th ng cu c c di n t ng cách li t kê t ng b c nh sau: – c 1: c 3 que r i i i ph ng i – c 2: i ph ng b c (gi x que, 0
  10. 3. Các ph ng pháp bi u di n thu t toán kh i t u u ki n t thúc thao tác input Ch ng trình con output ng x lý Page 19 T.P.Tu n-NH P MÔN TIN H C 12/12/2009 3. Các ph ng pháp bi u di n thu t toán kh i – ví d t u t u t u Thùng = 0 Lon a, S b a, b 1 Lon Thêm 1 Lon vào thùng a có b ng Không c=a+b b không? Ch a Thùng = 24 Lon? c Có ng a b ng S b a không b ng S b t thúc t thúc t thúc Page 20 T.P.Tu n-NH P MÔN TIN H C 12/12/2009
  11. 3. Các ph ng pháp bi u di n thu t toán Mã gi • Ngoài vi c s ng ngôn ng nhiên và u bi u di n thu t toán, ng i ta còn ng ngôn ng a pascal, c, … cg i là mã gi • Trong mã gi ta s ng c u trúc c a ngôn ng p trình và ngôn ng nhiên Page 21 T.P.Tu n-NH P MÔN TIN H C 12/12/2009 3. Các ph ng pháp bi u di n thu t toán Mã gi - ví d Bi n A,B,C,DELTA,X1,X2 : S Th c ; u Nh p A,B,C; DELTA:=B*B-4*A*C; u DELTA
  12. 3. Các ph ng pháp bi u di n thu t toán Bài t p 1. Tính m trung bình c a h c sinh g m các môn Toán, Lý, Hóa. 2. Ki m tra 2 s a, b gi ng nhau hay khác nhau. 3. Ki m tra 1 s a ch n hay l 4. Gi i pt: ax+b=0 5. Gi i ph ng trình b c 2: ax2 + bx + c = 0 Page 23 T.P.Tu n-NH P MÔN TIN H C 12/12/2009 4. Các b c gi i m t bài toán trên máy tính • c 1: Xác nh v n - bài toán • c 2: L a ch n ph ng pháp gi i • c 3: Xây d ng thu t toán ho c thu t gi i • c 4: Cài t ch ng trình • c 5: Hi u ch nh ch ng trình • c 6: Th c hi n ch ng trình Page 24 T.P.Tu n-NH P MÔN TIN H C 12/12/2009
  13. 4. Các b c gi i m t bài toán trên máy tính c 1: Xác nh v n - bài toán • Phân tích h th ng nh m phát bi u chính xác v n , làm rõ yêu c u c a ng i s ng • ánh giá, nh n nh tính kh thi c a v n Page 25 T.P.Tu n-NH P MÔN TIN H C 12/12/2009 4. Các b c gi i m t bài toán trên máy tính c 2: L a ch n ph ng pháp gi i • Có nhi u cách khác nhau gi i quy t v n , tùy theo nhu c u c th mà ta l a ch n ph ng pháp thích h p • Vi c l a ch n ph ng pháp c ng c n c n c vào kh ng x lý t ng mà ta c n s ng Page 26 T.P.Tu n-NH P MÔN TIN H C 12/12/2009
  14. 4. Các b c gi i m t bài toán trên máy tính c 3: Xây d ng thu t toán ho c thu t gi i • Xác nh input, output • Xác nh các b c th c hi n c b n cho d li u u vào và u ra • Nên áp d ng ph ng pháp thi t k có c u trúc, t thi t k ng th ti n hành làm m n n các b c Page 27 T.P.Tu n-NH P MÔN TIN H C 12/12/2009 4. Các b c gi i m t bài toán trên máy tính c 4: Cài t ch ng trình • Mô t thu t gi i thành ch ng trình • n n m v ng ngôn ng p trình và th hi n m t cách chính xác thu t toán ã c a ra. Page 28 T.P.Tu n-NH P MÔN TIN H C 12/12/2009
  15. 4. Các b c gi i m t bài toán trên máy tính c 5: Hi u ch nh ch ng trình • Cho ch ng trình ch y th và hi u ch nh nh ng sai sót • Trong b c này ta c n kh c ph c hai lo i l i: – i cú pháp (có s tr a IDE) – i ng ngh a (th ng khó phát hi n h n l i cú pháp) Page 29 T.P.Tu n-NH P MÔN TIN H C 12/12/2009 4. Các b c gi i m t bài toán trên máy tính c 6: Th c hi n ch ng trình • Cho ch ng trình ch y v i nh ng b li u khác nhau ki m tra • u ý các tr ng h p c bi t • u ý các tr ng h p ng i dùng nh p d li u có ki u không phù h p v i ki u d li u ng trong ch ng trình Page 30 T.P.Tu n-NH P MÔN TIN H C 12/12/2009
  16. 5. T ng quan v ngôn ng p trình tr a máy tính Gi i bài toán này th nào ây? Ch ng trình biên d ch File Ngôn (B máy c a NNLT) ng máy (exe, dll, com, ...) Source code Cách gi i c Ki n th c Ki n th c di n t b ng Chuyên môn NNLT ngôn ng nhiên Page 31 T.P.Tu n-NH P MÔN TIN H C 12/12/2009
ADSENSE

CÓ THỂ BẠN MUỐN DOWNLOAD

THÔNG TIN
TRỢ GIÚP
HỖ TRỢ KHÁCH HÀNG
Theo dõi chúng tôi

Chịu trách nhiệm nội dung:

Nguyễn Công Hà - Giám đốc Công ty TNHH TÀI LIỆU TRỰC TUYẾN VI NA

LIÊN HỆ

Địa chỉ: P402, 54A Nơ Trang Long, Phường 14, Q.Bình Thạnh, TP.HCM

Hotline: 093 303 0098

Email: support@tailieu.vn

Giấy phép Mạng Xã Hội số: 670/GP-BTTTT cấp ngày 30/11/2015 Copyright © 2022-2032 TaiLieu.VN. All rights reserved.

 

Đồng bộ tài khoản
2=>2