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 1: Thuật toán

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

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

Thuật toán đơn hình đối ngẫu là thuật toán đơn hình áp dụng vào giải toán đối ngẫu của quy hoạch tuyến tính đã cho nhưng các bước tiến hành lại được diễn tả trên bài toán gốc. Sau đây ta tìm hiểu nội dung của thuật toán đơn hình đối ngẫu.

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 1: Thuật toán

  1. Tin h c đ i cương Bài 4: Gi i quy t bài toán - Ph n 1: Thu t 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. Thu t toán (Algorithm) Bi u di n thu t toán M t s thu t toán thông d ng Thu t toán đ quy Thu t gi i heuristic N i dung Thu t toán (Algorithm) 1 Bi u di n thu t toán 2 M t s thu t toán thông d ng 3 Thu t toán đ quy 4 Thu t gi i heuristic 5 2 / 71
  3. Thu t toán (Algorithm) Bi u di n thu t toán Khái ni m M t s thu t toán thông d ng Các đ c trưng c a thu t toán Thu t toán đ quy Thu t gi i heuristic Thu t toán (Algorithm) 1 Khái ni m Các đ c trưng c a thu t toán Bi u di n thu t toán 2 M t s thu t toán thông d ng 3 Thu t toán đ quy 4 Thu t gi i heuristic 5 3 / 71
  4. Thu t toán (Algorithm) Bi u di n thu t toán Khái ni m M t s thu t toán thông d ng Các đ c trưng c a thu t toán Thu t toán đ quy Thu t gi i heuristic Đ nh nghĩa thu t toán ! là khái ni m cơ s trong tin h c và toán h c ! "Algorithm" ra đ i d a theo cách phiên âm tên c a nhà toán h c Trung á (Abu Abd - Allah ibn Musa al’Khwarizmi) ! ĐN chung: thu t toán bao g m m t dãy h u h n các ch th rõ ràng, có trình t và có th thi hành đư c đ hư ng d n th c hi n hành đ ng nh m đ t đư c m c tiêu đ ra ! Thu t toán đư c xem như là s th hi n c a 1 phương án gi i quy t 1 v n đ nào đó 4 / 71
  5. Thu t toán (Algorithm) Bi u di n thu t toán Khái ni m M t s thu t toán thông d ng Các đ c trưng c a thu t toán Thu t toán đ quy Thu t gi i heuristic Đ nh nghĩa thu t toán ! ĐN trong khoa h c máy tính: – g m các dãy các ch th không m p m và có th th c thi đư c (tính xác đ nh) không m p m : t i m i bư c, hành đ ng k ti p ph i đư c xác đ nh m t cách duy nh t theo ch th hành đ ng và d li u t i th i đi m đó – quá trình ho t đ ng theo thu t toán ph i d ng (tính h u h n) và cho k t qu như mong mu n (tính đúng) 5 / 71
  6. Thu t toán (Algorithm) Bi u di n thu t toán Khái ni m M t s thu t toán thông d ng Các đ c trưng c a thu t toán Thu t toán đ quy Thu t gi i heuristic Thu t toán ? Ch th không m p m ? - thu t toán ch n l p trư ng ! VD1: l p danh sách t t các SV trong l p 1 s p th t danh sách SV 2 ch n h c sinh đ ng đ u danh sách đ làm l p trư ng 3 ! VD2: l p danh sách t t các SV trong l p theo hai thông tin: H và 1 Tên, T ng đi m thi đ u vào s p th t danh sách SV theo th t t ng đi m gi m d n, 2 h c 2 sinh có cùng đi m TB có cùng h ng n u có 1 HS đ ng h ng nh t ch n HS đó làm l p trư ng, n u 3 không thì ti n hành b c thăm cho các SV đư c x p h ng nh t 6 / 71
  7. Thu t toán (Algorithm) Bi u di n thu t toán Khái ni m M t s thu t toán thông d ng Các đ c trưng c a thu t toán Thu t toán đ quy Thu t gi i heuristic Thu t toán ? ! Ch th th c thi đư c: xét trong đi u ki n hi n t i c a bài toán – VD1: sqrt (−1) – VD2: bài toán ch đư ng: ... bư c n: r vào đư ng X (X đư ng ngư c chi u) ... ! Tính h u h n (d ng): d b vi ph m nh t, thư ng do sai sót khi trình bày thu t toán B1 Nh p n B2 i=n B3 Gán i = i-2 B4 N u (i < 0) thì sang B6 B5 Quay l i B3 B6 Hi n th giá tr c a i 7 / 71
  8. Thu t toán (Algorithm) Bi u di n thu t toán Khái ni m M t s thu t toán thông d ng Các đ c trưng c a thu t toán Thu t toán đ quy Thu t gi i heuristic Thu t toán - Ví d Tìm giá tr l n nh t trong m t dãy h u h n s nguyên Đ t giá tr l n nh t t m th i = s nguyên đ u tiên 1 So sánh giá tr s nguyên k ti p v i giá tr l n nh t t m th i, 2 n u nó l n hơn thì gán l i giá tr l n nh t t m th i b ng giá tr s nguyên này L p bư c 2 n u còn s nguyên trong dãy chưa đư c xét t i 3 D ng n u không còn s nguyên nào trong dãy chưa đư c xét, 4 giá tr l n nh t trong dãy chính là giá tr l n nh t t m th i lúc này 8 / 71
  9. Thu t toán (Algorithm) Bi u di n thu t toán Khái ni m M t s thu t toán thông d ng Các đ c trưng c a thu t toán Thu t toán đ quy Thu t gi i heuristic Thu t toán (Algorithm) 1 Khái ni m Các đ c trưng c a thu t toán Bi u di n thu t toán 2 M t s thu t toán thông d ng 3 Thu t toán đ quy 4 Thu t gi i heuristic 5 9 / 71
  10. Thu t toán (Algorithm) Bi u di n thu t toán Khái ni m M t s thu t toán thông d ng Các đ c trưng c a thu t toán Thu t toán đ quy Thu t gi i heuristic Các đ c trưng c a thu t toán ! Tính xác đ nh: các bư c trong thu t toán ph i chính xác, rõ ràng ! Tính h u h n: thu t toán ph i cho k t qu (l i gi i) sau m t s h u h n các bư c ! Tính đúng: thu t toán ph i cho k t qu đúng ! Nh p: các giá tr nh p vào (input values) t m t t p nào đó ! Xu t: giá tr vào + thu t toán => giá tr ra (output values) : th hi n l i gi i cho bài toán ! Tính hi u qu : d a trên kh i lư ng tính toán, không gian và th i gian s d ng,... ! Tính t ng quát: ph i áp d ng cho t t c các bài toán có d ng như mong mu n ch không ph i ch cho 1 trư ng h p riêng l nào 10 / 71
  11. Thu t toán (Algorithm) Bi u di nb ng ngôn ng t nhiên Bi u di n thu t toán Bi u di nb ng lưu đ (sơ đ kh i) M t s thu t toán thông d ng Bi u di nb ng mã gi Thu t toán đ quy Bi u di nb ng ngôn ng l p trình Thu t gi i heuristic M ts ví d Cách bi u di n thu t toán ! Ngôn ng t nhiên ! Ngôn ng lưu đ (lưu đ /sơ đ kh i) ! Ngôn ng t a l p trình (mã gi -pseudocode ) g i là ngôn ng mô ph ng chương trình PDL (Programming Description Language ) ! Ngôn ng l p trình: Pascal, C/C++ hay Java, ... 11 / 71
  12. Thu t toán (Algorithm) Bi u di nb ng ngôn ng t nhiên Bi u di n thu t toán Bi u di nb ng lưu đ (sơ đ kh i) M t s thu t toán thông d ng Bi u di nb ng mã gi Thu t toán đ quy Bi u di nb ng ngôn ng l p trình Thu t gi i heuristic M ts ví d Thu t toán (Algorithm) 1 Bi u di n thu t toán 2 Bi u di n b ng ngôn ng t nhiên Bi u di n b ng lưu đ (sơ đ kh i) Bi u di n b ng mã gi Bi u di n b ng ngôn ng l p trình M t s ví d M t s thu t toán thông d ng 3 Thu t toán đ quy 4 Thu t gi i heuristic 5 12 / 71
  13. Thu t toán (Algorithm) Bi u di nb ng ngôn ng t nhiên Bi u di n thu t toán Bi u di nb ng lưu đ (sơ đ kh i) M t s thu t toán thông d ng Bi u di nb ng mã gi Thu t toán đ quy Bi u di nb ng ngôn ng l p trình Thu t gi i heuristic M ts ví d Bi u di n b ng ngôn ng t nhiên ! S d ng m t lo i ngôn ng t nhiên (Anh, Pháp, Vi t, ...) đ li t kê các bư c c a thu t toán ! Ví d : đưa ra k t lu n v tương quan gi a hai s a và b (>, < hay =) – Đ u vào: Hai s a và b – Đ u ra: K t lu n a>b hay a b, hi n th “a>b” và k t thúc 2 N u a=b, hi n th “a=b” và k t thúc 3 N u (a
  14. Thu t toán (Algorithm) Bi u di nb ng ngôn ng t nhiên Bi u di n thu t toán Bi u di nb ng lưu đ (sơ đ kh i) M t s thu t toán thông d ng Bi u di nb ng mã gi Thu t toán đ quy Bi u di nb ng ngôn ng l p trình Thu t gi i heuristic M ts ví d Bi u di n b ng ngôn ng t nhiên ! Ưu đi m: – Đơn gi n – Không yêu c u ngư i vi t và ngư i đ c ph i có ki n th c n n t ng ! Như c đi m: – Dài dòng – Không làm n i b t c u trúc c a thu t toán – Khó bi u di n v i nh ng bài toán ph c t p 14 / 71
  15. Thu t toán (Algorithm) Bi u di nb ng ngôn ng t nhiên Bi u di n thu t toán Bi u di nb ng lưu đ (sơ đ kh i) M t s thu t toán thông d ng Bi u di nb ng mã gi Thu t toán đ quy Bi u di nb ng ngôn ng l p trình Thu t gi i heuristic M ts ví d Thu t toán (Algorithm) 1 Bi u di n thu t toán 2 Bi u di n b ng ngôn ng t nhiên Bi u di n b ng lưu đ (sơ đ kh i) Bi u di n b ng mã gi Bi u di n b ng ngôn ng l p trình M t s ví d M t s thu t toán thông d ng 3 Thu t toán đ quy 4 Thu t gi i heuristic 5 15 / 71
  16. Thu t toán (Algorithm) Bi u di nb ng ngôn ng t nhiên Bi u di n thu t toán Bi u di nb ng lưu đ (sơ đ kh i) M t s thu t toán thông d ng Bi u di nb ng mã gi Thu t toán đ quy Bi u di nb ng ngôn ng l p trình Thu t gi i heuristic M ts ví d Bi u di n b ng lưu đ (sơ đ kh i) Lưu đ : m t h th ng các nút có hình d ng khác nhau, th hi n các ch c năng khác nhau và đư c n i v i nhau b i các cung nút gi i h n: hình oval và có ch ghi bên trong nút thao tác: hình ch nh t, bên trong ghi các l nh nút đi u ki n: hình thoi, bên trong ghi đi u ki n, có 2 cung ra ch đi u ki n đúng/sai cung: đư ng n i t nút này đ n nút khác c a lưu đ 16 / 71
  17. Thu t toán (Algorithm) Bi u di nb ng ngôn ng t nhiên Bi u di n thu t toán Bi u di nb ng lưu đ (sơ đ kh i) M t s thu t toán thông d ng Bi u di nb ng mã gi Thu t toán đ quy Bi u di nb ng ngôn ng l p trình Thu t gi i heuristic M ts ví d Bi u di n b ng lưu đ (sơ đ kh i) 17 / 71
  18. Thu t toán (Algorithm) Bi u di nb ng ngôn ng t nhiên Bi u di n thu t toán Bi u di nb ng lưu đ (sơ đ kh i) M t s thu t toán thông d ng Bi u di nb ng mã gi Thu t toán đ quy Bi u di nb ng ngôn ng l p trình Thu t gi i heuristic M ts ví d Bi u di n b ng lưu đ (sơ đ kh i) ! Ưu đi m: – tr c quan, d di n đ t, d hi u – cung c p toàn c nh, t ng quan v thu t toán ! Như c đi m: – c ng k nh nh t là v i bài toán ph c t p 18 / 71
  19. Thu t toán (Algorithm) Bi u di nb ng ngôn ng t nhiên Bi u di n thu t toán Bi u di nb ng lưu đ (sơ đ kh i) M t s thu t toán thông d ng Bi u di nb ng mã gi Thu t toán đ quy Bi u di nb ng ngôn ng l p trình Thu t gi i heuristic M ts ví d Thu t toán (Algorithm) 1 Bi u di n thu t toán 2 Bi u di n b ng ngôn ng t nhiên Bi u di n b ng lưu đ (sơ đ kh i) Bi u di n b ng mã gi Bi u di n b ng ngôn ng l p trình M t s ví d M t s thu t toán thông d ng 3 Thu t toán đ quy 4 Thu t gi i heuristic 5 19 / 71
  20. Thu t toán (Algorithm) Bi u di nb ng ngôn ng t nhiên Bi u di n thu t toán Bi u di nb ng lưu đ (sơ đ kh i) M t s thu t toán thông d ng Bi u di nb ng mã gi Thu t toán đ quy Bi u di nb ng ngôn ng l p trình Thu t gi i heuristic M ts ví d Bi u di n b ng mã gi (pseudo code) ! Ngôn ng t a (g n gi ng) v i ngôn ng l p trình đư c g i là mã gi – s d ng m nh đ có c u trúc – s d ng ngôn ng t nhiên – s d ng các bi n, các kí hi u toán h c, các c u trúc ki u th t c, ... ! Ưu đi m: ti n l i, đơn gi n, d hi u, d di n đ t ! Như c đi m: ngư i đ c/vi t ph i hi u đư c c u trúc trong l p trình và cách bi u di n 20 / 71
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