Tin học đại cương - Bài 4 - Phần 1: Thuật toán

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.
Nội dung trích xuất từ tài liệu:
Tin học đại cương - Bài 4 - Phần 1: Thuật toán Tin h c đ i cươngBà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 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 heuristicN i dung Thu t toán (Algorithm)1 Bi u di n thu t toán2 M t s thu t toán thông d ng3 Thu t toán đ quy4 Thu t gi i heuristic5 2 / 71 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án2 M t s thu t toán thông d ng3 Thu t toán đ quy4 Thu t gi i heuristic5 3 / 71 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 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 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 heuristicThu 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 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 heuristicThu 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 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 heuristicThu t toán - Ví dTì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 ...