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

Tin học đại cương - Bài 4 - Phần 2: Giải quyết bài toán

Chia sẻ: July Man | Ngày: | Loại File: PDF | Số trang:28

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

Trong quá trình nghiên cứu giải quyết các vấn đề – bài toán, người ta đã đưa ra những nhận xét như sau: Có nhiều bài toán cho đến nay vẫn chưa tìm ra một cách giải theo kiểu thuật toán và cũng không biết là có tồn tại thuật toán hay không.

Chủ đề:

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

Lưu

Nội dung Text: Tin học đại cương - Bài 4 - Phần 2: Giải quyết bài toán

  1. Tin h c đ i cương Bài 4: Gi i quy t bài toán - Ph n 2: Gi i quy t bài toán NGUY N Th Oanh oanhnt@soict.hut.edu.vn B môn H th ng thông tin - Vi n CNTT và Truy n Thông Đ i h c Bách Khoa Hà n i 2010 - 2011
  2. Bài toán Gi i quy t bài toán b ng máy tính Các phương pháp gi i quy t bài toán b ng máy tính Phân lo i bài toán N i dung Bài toán 1 Gi i quy t bài toán b ng máy tính 2 Các phương pháp gi i quy t bài toán b ng máy tính 3 Phân lo i bài toán 4 2 / 28
  3. Bài toán Gi i quy t bài toán b ng máy tính Các phương pháp gi i quy t bài toán b ng máy tính Phân lo i bài toán Khái ni m ! "Bài toán" vs. "V n đ " – v n đ có nghĩa r ng hơn bài toán – bài toán là m t lo i v n đ mà đ gi i quy t ph i liên quan ít nhi u đ n tính toán: bài toán trong v t lý, hóa h c, xây d ng, kinh t , ... ! Pitago chia m i v n đ thành 2 lo i: – Theorema: v n đ c n đư c kh ng đ nh tính đúng / sai, ví d : ch ng minh đ nh lý trong toán h c – Problema: v n đ c n tìm đư c gi i pháp đ đ t đư c m t m c tiêu xác đ nh t nh ng đi u ki n ban đ u nào đó, ví d : bài toán d ng hình, tìm đư ng đi ng n nh t, ... 3 / 28
  4. Bài toán Gi i quy t bài toán b ng máy tính Các phương pháp gi i quy t bài toán b ng máy tính Phân lo i bài toán Khái ni m ! Bi u di n v n đ - bài toán: A→B A: gi thi t, đi u ki n ban đ u B : k t lu n, m c tiêu c n đ t đư c →: suy lu n và gi i pháp c n xác đ nh ! Gi i quy t v n đ - bài toán: – t A dùng m t s h u h n các bư c suy lu n có lý ho c hành đ ng thích h p đ đ t đư c B – trong tin hoc: A: đ u vào (input ) B : đ u ra (output ) →: chương trình t o thành t các l nh cơ b n c a máy tính cho phép bi n đ i A thành B (cách mã hóa l i thu t toán hay thu t gi i) 4 / 28
  5. Bài toán Gi i quy t bài toán b ng máy tính Các phương pháp gi i quy t bài toán b ng máy tính Phân lo i bài toán Gi i quy t bài toán b ng máy tính ! Máy tính không th dùng, ít nh t là tr c ti p, đ gi i quy t các v n đ liên quan đ n hành đ ng v t lý ho c bi u th c m xúc ! Máy tính ch làm đư c nh ng gì mà nó đư c b o ph i làm. Máy tính không t thông minh, nó không th t phân tích v n đ và đưa ra gi i pháp ! Con ngư i (l p trình viên) là ngư i phân tích v n đ , t o ra các ch d n đ gi i quy t v n đ (chương trình), và máy tính s th c hi n các ch d n đó 5 / 28
  6. Bài toán Gi i quy t bài toán b ng máy tính Các phương pháp gi i quy t bài toán b ng máy tính Phân lo i bài toán Thi t k thu t toán ! Tính không xác đ nh c a v n đ -bài toán: – A, B không đ y đ , rõ ràng – thông báo v các đi u ki n đ t ra cho gi i thu t thư ng đư c nêu trong bài toán ! Thi t k thu t toán/ thu t gi i: – ch y u là do con ngư i: thông tin (ti m n ho c rõ ràng) trong A, B + tri th c => thu t gi i – t đ ng hóa xây d ng thu t toán / thu t gi i: bi u di n bài toán + tri th c liên quan tư ng minh và đ y đ ==> xây d ng trí tu nhân t o cho máy tính 6 / 28
  7. Bài toán Gi i quy t bài toán b ng máy tính Các phương pháp gi i quy t bài toán b ng máy tính Phân lo i bài toán Các bư c gi i quy t bài toán b ng máy tính Không ch đơn gi n là l p trình, ph c t p, g m nhi u bư c: ! B1: Xác đ nh yêu c u bài toán làm rõ yêu c u c a ngư i s d ng, đánh giá, nh n đ nh tính kh thi c a bài toán ! B2: L a ch n phương pháp gi i ! B3: Xây d ng thu t toán ! B4: L p trình: mô t thu t gi i b ng chương trình ! B5: Ki m th và hi u ch nh chương trình: ! B6: Tri n khai và b o trì 7 / 28
  8. Bài toán Gi i quy t bài toán b ng máy tính Các phương pháp gi i quy t bài toán b ng máy tính Phân lo i bài toán Các bư c gi i quy t bài toán b ng máy tính Không ch đơn gi n là l p trình, ph c t p, g m nhi u bư c: ! B1: Xác đ nh yêu c u bài toán ! B2: L a ch n phương pháp gi i – 1 bài toán có nhi u phương án khác nhau v th i gian th c hi n, chi phí lưu tr DL, đ chính xác, ... – phương pháp phù h p tùy theo nhu c u kh năng x lý t đ ng, ... B3: Xây d ng thu t toán ! B4: L p trình: mô t thu t gi i b ng chương trình ! B5: Ki m th và hi u ch nh chương trình: ! B6: Tri n khai và b o trì ! 8 / 28
  9. Bài toán Gi i quy t bài toán b ng máy tính Các phương pháp gi i quy t bài toán b ng máy tính Phân lo i bài toán Các bư c gi i quy t bài toán b ng máy tính Không ch đơn gi n là l p trình, ph c t p, g m nhi u bư c: ! B1: Xác đ nh yêu c u bài toán ! B2: L a ch n phương pháp gi i ! B3: Xây d ng thu t toán xây d ng mô hình ch t ch , chính xác, chi ti t cho phương pháp đã ch n: d li u vào ? các bư c và trình t th c hi n? ! B4: L p trình: mô t thu t gi i b ng chương trình ! B5: Ki m th và hi u ch nh chương trình: ! B6: Tri n khai và b o trì 9 / 28
  10. Bài toán Gi i quy t bài toán b ng máy tính Các phương pháp gi i quy t bài toán b ng máy tính Phân lo i bài toán Các bư c gi i quy t bài toán b ng máy tính Không ch đơn gi n là l p trình, ph c t p, g m nhi u bư c: B1: Xác đ nh yêu c u bài toán ! B2: L a ch n phương pháp gi i ! B3: Xây d ng thu t toán ! B4: L p trình: mô t thu t gi i b ng chương trình ! B5: Ki m th và hi u ch nh chương trình: ! B6: Tri n khai và b o trì ! 10 / 28
  11. Bài toán Gi i quy t bài toán b ng máy tính Các phương pháp gi i quy t bài toán b ng máy tính Phân lo i bài toán Các bư c gi i quy t bài toán b ng máy tính Không ch đơn gi n là l p trình, ph c t p, g m nhi u bư c: B1: Xác đ nh yêu c u bài toán ! B2: L a ch n phương pháp gi i ! B3: Xây d ng thu t toán ! B4: L p trình: mô t thu t gi i b ng chương trình ! B5: Ki m th và hi u ch nh chương trình: ch y th và hi u ch nh ! sai sót ! B6: Tri n khai và b o trì 11 / 28
  12. Bài toán Gi i quy t bài toán b ng máy tính Các phương pháp gi i quy t bài toán b ng máy tính Phân lo i bài toán Các bư c gi i quy t bài toán b ng máy tính Không ch đơn gi n là l p trình, ph c t p, g m nhi u bư c: B1: Xác đ nh yêu c u bài toán ! B2: L a ch n phương pháp gi i ! B3: Xây d ng thu t toán ! B4: L p trình: mô t thu t gi i b ng chương trình ! B5: Ki m th và hi u ch nh chương trình: ! B6: Tri n khai và b o trì ! 12 / 28
  13. Bài toán Gi i quy t bài toán b ng máy tính Các phương pháp gi i quy t bài toán b ng máy tính Phân lo i bài toán 2 giao đo n chính đ hi n th c hóa bài toán ! Giai đo n quan ni m: – phân tích – l a ch n mô hình – xây d ng gi i thu t – cài đ t ! Giai đo n khai thác và b o trì: s d ng => c i ti n, m r ng 13 / 28
  14. Bài toán Gi i quy t bài toán b ng máy tính Theo hư ng tr c ti p xác đ nh l i gi i Các phương pháp gi i quy t bài toán b ng máy tính Theo hư ng tìm ki m l i gi i Phân lo i bài toán Các phương pháp gi i quy t bài toán b ng máy tính 14 / 28
  15. Bài toán Gi i quy t bài toán b ng máy tính Theo hư ng tr c ti p xác đ nh l i gi i Các phương pháp gi i quy t bài toán b ng máy tính Theo hư ng tìm ki m l i gi i Phân lo i bài toán Bài toán 1 Gi i quy t bài toán b ng máy tính 2 Các phương pháp gi i quy t bài toán b ng máy tính 3 Theo hư ng tr c ti p xác đ nh l i gi i Theo hư ng tìm ki m l i gi i Phân lo i bài toán 4 15 / 28
  16. Bài toán Gi i quy t bài toán b ng máy tính Theo hư ng tr c ti p xác đ nh l i gi i Các phương pháp gi i quy t bài toán b ng máy tính Theo hư ng tìm ki m l i gi i Phân lo i bài toán Gi i bài toán theo hư ng tr c ti p xác đ nh l i gi i ! Xác đ nh l i gi i thông qua: – các th t c tính toán (công th c, h th c, đ nh lý, ...) – ho c m t dãy h u h n các thao tác sơ c p (d ng hình, ph n ng hóa h c, ...) ! Ví d : – gi i PT b c 2 theo đ nh lý VIET – phương pháp l p đ toán tính nghi m g n đúng, ... 16 / 28
  17. Bài toán Gi i quy t bài toán b ng máy tính Theo hư ng tr c ti p xác đ nh l i gi i Các phương pháp gi i quy t bài toán b ng máy tính Theo hư ng tìm ki m l i gi i Phân lo i bài toán Bài toán 1 Gi i quy t bài toán b ng máy tính 2 Các phương pháp gi i quy t bài toán b ng máy tính 3 Theo hư ng tr c ti p xác đ nh l i gi i Theo hư ng tìm ki m l i gi i Phân lo i bài toán 4 17 / 28
  18. Bài toán Gi i quy t bài toán b ng máy tính Theo hư ng tr c ti p xác đ nh l i gi i Các phương pháp gi i quy t bài toán b ng máy tính Theo hư ng tìm ki m l i gi i Phân lo i bài toán Gi i bài toán theo hư ng tìm ki m l i gi i ! Nguyên lý th -sai ! ng d ng r ng rãi cho các bài toán-v n đ ph c t p ! M t s phương pháp đi n hình: – phương pháp li t kê (hay vét b n): th t t c các kh năng có th đ ki m tra – phương pháp th ng u nhiên: d a trên m t s kh năng đư c ch n ng u nhiên kh năng thành công ph thu c: chi n lư c ch n và đi u ki n c th c a bài toán – phương pháp quay lui: đánh d u các th nghi m th t b i và th kh năng khác (vd: tìm đư ng trong mê cung) khi không th xác đ nh ho c li t kê t trư c t t c các kh năng có th ! Ví d : bài toán 8 h u, phân tích ra th a s nguyên t , ... 18 / 28
  19. Bài toán Gi i quy t bài toán b ng máy tính Đ ph c t p thuât toán Các phương pháp gi i quy t bài toán b ng máy tính Phân lo i Phân lo i bài toán Bài toán 1 Gi i quy t bài toán b ng máy tính 2 Các phương pháp gi i quy t bài toán b ng máy tính 3 Phân lo i bài toán 4 Đ ph c t p thuât toán Phân lo i 19 / 28
  20. Bài toán Gi i quy t bài toán b ng máy tính Đ ph c t p thuât toán Các phương pháp gi i quy t bài toán b ng máy tính Phân lo i Phân lo i bài toán Đ ph c t p thuât toán ! Đ ph c t p thu t toán – không gian: tùy thu c vào c u trúc d li u s d ng khi cài đ t – th i gian ⇒ Đ ph c t p v th i gian c a thu t toán: khó xác đ nh chính xác – s lư ng thao tác đư c s d ng trong thu t toán: phép so sánh 2 s nguyên, c ng, nhân, chia hai s nguyên hay b t kỳ m t thao tác cơ b n – s lư ng thao tác này ph thu c vào đ l n c a d li u nh p (n) ⇒ t (n) ! Th i gian nh nh t: th i gian th c hi n TT trong trư ng h p t t t đ i v i d li u có d li u nh p có đ l n n nh ! Th i gian l n nh t: th i gian th c hi n TT trong trư ng h p x u t đ i v i d li u có d li u nh p có đ l n n nh 20 / 28
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
18=>0