Bài giảng Tin học đại cương: Chương 3 - Trần Quang Hải Bằng

Chia sẻ: Vdgv Vdgv | Ngày: | Loại File: PDF | Số trang:26

Thêm vào BST

Báo xấu

86
lượt xem 5
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Nội dung trình bày trong chương 3 Lý thuyết thuật toán nằm trong bài giảng tin học đại cương nhằm trình bày về khái niệm thuật toán, chương trình máy tính, ngôn ngữ lập trình, tính chất của thuật toán, các cách biểu diễn của thuật toán...

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 Tin học đại cương: Chương 3 - Trần Quang Hải Bằng

TIN H C ð I CƯƠNG Chương 3: Lý thuy t thu t toán bangtqh@utc2.edu.vn N i dung 1. Khái ni m thu t toán. 2. Chương trình máy tính, ngôn ng l p trình. 3. Tính ch t c a thu t toán. 4. Các cách bi u di n thu t toán. 5. Thi t k và phân tích thu t toán. 6. Đ quy và thu t toán đ quy. 7. M t s bài toán tìm ki m, s p x p đơn gi n. 8. Bài t p. bangtqh@utc2.edu.vn Tin h c đ i cương - Chương 3 2
Thu t toán là gì? Thu t toán, thu t gi i, hay gi i thu t, ñ u dùng đ ch m t thu t ng ti ng Anh có tên là ALGORITHM. Chúng ta s tìm hi u: q Thu t toán theo cách hi u thông thư ng q Các thao tác trong thu t toán q Đ nh nghĩa thu t toán trong tin h c bangtqh@utc2.edu.vn TinTinchĐ ci đ i cương - Chương 3 h cương - Chương 3 3 3/51 Thu t toán - cách hi u thông thư ng q B t c công yêu c u gì cũng c n ph i đư c gi i quy t m t cách khoa h c Theo nghĩa r ng, khái ni m “thu t toán” (algorithm) đư c s d ng m i nơi, không riêng gì trong lĩnh v c tin h c. q Theo cách hi u thông tư ng Thu t toán là m t lo t các thao tác (operation) có th t (order) nh m gi i quy t m t yêu c u nào đó. q Ví d : “Thu t toán n u cơm” – Bư c 0: Ư c lư ng g o c n thi t – Bư c 1: Vo g o – Bư c 2: Cho g o và nư c thích h p vào n i cơm đi n(NCĐ) – Bư c 3: C m đi n, chuy n ch ñ “cook” – Bư c 4: Ch ñ n khi NCĐ chuy n sang ch ñ “warm” – Bư c 5: Ch thêm 10 phút n a – Bư c 6: Cơm chín, k t thúc. bangtqh@utc2.edu.vn Tin h c đ i cương - Chương 3 4
Trò chơi 5 quân bài q Ch n 5 quân bài ng u nhiên trong b bài 52 quân. q Yêu c u: Hãy tìm ra quân bài l n nh t trong s các quân bài hi n có. – M i l n ch ñư c l t 1 quân bài trong s 5 quân. – Ghi l i quá trình tìm ki m theo m i bư c bangtqh@utc2.edu.vn Tin h c đ i cương - Chương 3 5 Trò chơi 5 quân bài … Quân bài l n nh t là: bangtqh@utc2.edu.vn Tin h c đ i cương - Chương 3 6
Trò chơi 5 quân bài (tt) So sánh Quân bài l n nh t: bangtqh@utc2.edu.vn Tin h c đ i cương - Chương 3 7 Trò chơi 5 quân bài (tt) So sánh Quân bài l n nh t: bangtqh@utc2.edu.vn Tin h c đ i cương - Chương 3 8
Trò chơi 5 quân bài (tt) So sánh Quân bài l n nh t: bangtqh@utc2.edu.vn Tin h c đ i cương - Chương 3 9 Trò chơi 5 quân bài (tt) So sánh Quân bài l n nh t: bangtqh@utc2.edu.vn Tin h c đ i cương - Chương 3 10
Các thao tác trong thu t toán q Thao tác tu n t (sequential operation): M t công vi c đã đư c xác đ nh rõ ràng, th c hi n xong thì chuy n sang công vi c khác. q Thao tác ki m tra đi u ki n (conditional operation): Ki m tra đi u ki n đưa ra có tho mãn hay không đ quy t đ nh thao tác ti p theo. q Thao tác l p (iterative operation): Quay tr l i bư c nào đó trong dãy thao tác. – M t thao tác có th ñư c l p đi l p l i nhi u l n t i khi m t đi u ki n nào đó ñư c tho mãn bangtqh@utc2.edu.vn Tin h c đ i cương - Chương 3 11 Đ nh nghĩa gi i thu t – (Cách 1) q Gi i thu t là m t dãy các câu l nh ch t ch và rõ ràng xác đ nh m t trình t thao tác trên m t đ i tư ng nào đó sao cho sau m t s bư c h u h n th c hi n, ta thu đư c k t qu mong mu n. – Câu l nh (statement): đơn v thao tác, tính toán, x lý – Trình t rõ ràng (well-ordered): th c hi n xong bư c này m i chuy n sang bư c khác, không nh p nh ng. – Đ i tư ng (object): các d ki n c a bài toán, d li u trung gian, k t qu ,… – K t qu (result): Thông tin, l i gi i cho bài toán,… bangtqh@utc2.edu.vn Tin h c đ i cương - Chương 3 12
Đ nh nghĩa gi i thu t – Cách 2 q Gi i thu t là b t c th t c tính toán (computational procedure) nào nh n các d li u vào (input) và tr thông tin ra (output). q Gi i thu t là dãy các thao tác x lý d li u đ có đư c thông tin mong mu n. q Ví d : “Bài toán s p x p dãy s ” – Input: Dãy s . – Output: Dãy s ñã s p x p. INPUT ALGORITHM OUTPUT bangtqh@utc2.edu.vn Tin h c đ i cương - Chương 3 13 Chương trình máy tính q Máy tính? – Làm theo “l nh” c a con ngư i. – Đi m m nh là tính toán v i t c đ cao (hàng t phép tính trên giây). q Làm th nào đ “ra l nh” cho máy tính? – L p chương trình cho máy tính. q Chương trình ? – Nói cho máy tính bi t ph i làm gì, như th nào,… bangtqh@utc2.edu.vn Tin h c đ i cương - Chương 3 14
Ngôn ng l p trình q Mu n “ra l nh” cho máy tính: – S d ng m t “ngôn ng ” chung ngôn ng l p trình (programming language) – L p trình (computer programming) • Dùng ngôn ng l p trình l p nên chương trình ho t đ ng cho máy tính. q Các th h c a ngôn ng l p trình – Th h 1 (b c th p): ngôn ng máy, assembly. – Th h 2: G n v i ngôn ng t nhiên hơn, ph c v nh ng nhu c u l p trình nh t đ nh (FORTRAN, COBOL, ALGOL,… ) – Th h 3: G n gũi, v n năng (PASCAL, C, C++,…) – Th h 4: Truy v n, h tr quy t đ nh, l p trình trí tu nhân t o (SQL, LISP, PROLOG,…). bangtqh@utc2.edu.vn Tin h c đ i cương - Chương 3 15 T gi i thu t đ n chương trình q Gi i thu t ch là “phương pháp”. q S d ng gi i thu t như th nào đ gi i quy t bài toán – C n ph i có máy tính. – L p trình: Mô t (cài đ t) gi i thu t lên máy tính. q Bi u di n đ i tư ng x lý b i d li u (data) trong chương trình (có nhi u ki u d li u v i c u trúc khác nhau). q Thu t gi i + c u trúc d li u = chương trình DATA STRUCTURES + ALGORITHMS = PROGRAM bangtqh@utc2.edu.vn Tin h c đ i cương - Chương 3 16
Chương trình vi t b ng ngôn ng C bangtqh@utc2.edu.vn Tin h c đ i cương - Chương 3 17 “Gi i thu t n u cơm” q Gi i thu t n u cơm (đ phòng trư ng h p có thêm khách) – Bư c 0: Ư c lư ng s g o c n thi t. – Bư c 1: Vo g o. – Bư c 2: Cho g o và nư c thích h p vào n i cơm đi n(NCĐ). – Bư c 3: C m đi n, chuy n ch ñ “cook”. – Bư c 4: Ch ñ n khi NCĐ chuy n sang ch ñ “warm”. – Bư c 5: Ch thêm 10 phút n a. – Bư c 6: Cơm chín. N u không có thêm khách thì sang bư c 8. – Bư c 7: Quay l i bư c 0. – Bư c 8: K t thúc. q Nh n xét: Bư c 6 là thao tác ki m tra đi u ki n và bư c 7 là thao tác l p. bangtqh@utc2.edu.vn Tin h c đ i cương - Chương 3 18
Các tính ch t c a thu t toán q Tính h u h n d ng – M t thu t toán b t kỳ ph i đ m b o d ng sau m t s h u h n bư c. q Tính đúng đ n – Thu t toán ph i đ m b o gi i quy t bài toán m t cách đúng đ n, cho k t qu “chính xác” và “đ y đ ” theo yêu c u. q Tính đơn gi n và hi u qu – Đơn gi n: D hi u, d l p trình. – Hi u qu : Tiêu t n ít th i gian và tài nguyên máy tính. bangtqh@utc2.edu.vn Tin h c đ i cương - Chương 3 19 Các tính ch t c a thu t toán (tt) q Tính xác đ nh: – M i thao tác th c hi n trong thu t toán ph i đư c xác đ nh rõ ràng, không gây hi u l m. q Tính ph d ng: – M i thu t toán ph i đ m b o gi i quy t đư c nhi u bài toán đ ng d ng, trên nhi u b s li u khác nhau. q Luôn có ñ i lư ng vào ra (input/output) – M i thu t toán đ u ph i minh h a cách nh n s li u vào đ tính toán (input) sau ñó thông báo k t qu tìm đư c (output). bangtqh@utc2.edu.vn Tin h c đ i cương - Chương 3 20
Có ph i m i bài toán đ u có thu t gi i ? q Có nh ng bài toán không có gi i thu t t ng quát đ gi i quy t. q Có nh ng bài toán chưa có gi i thu t h u hi u đ gi i quy t. q Có nh ng bài toán chưa có gi i thu t tìm l i gi i. bangtqh@utc2.edu.vn Tin h c đ i cương - Chương 3 21 Các cách bi u di n thu t toán q Li t kê t ng bư c q Sơ đ kh i q S d ng gi ngôn ng l p trình bangtqh@utc2.edu.vn Tin h c đ i cương - Chương 3 22
Phương pháp li t kê t ng bư c q Các thao tác c a gi i thu t đư c li t kê t ng bư c. q T i m i bư c, s d ng ngôn ng t nhiên ñ di n t công vi c ph i làm. q Bư c đ ng trư c (có s th t nh hơn) đư c th c hi n trư c. q Ưu như c đi m – D hi u, d làm – Ph thu c vào “cách hành văn” c a ngư i di n đ t – V i nh ng gi i thu t ph c t p, cách di n đ t này tr nên rư m rà – … bangtqh@utc2.edu.vn Tin h c đ i cương - Chương 3 23 Ví d q Gi i thu t “Tìm v trí xu t hi n đ u tiên c a m t s nguyên trong dãy s nguyên ñã cho”: – Bư c 1: Nh p dãy s nguyên a1, a2, …., aN – Bư c 2: Nh p s nguyên s – Bư c 3: Gán v trí p ban ñ u = 0 và v trí i ñang xét = 1 p = 0, i=1 – Bư c 4: So sánh ai v i s • N u ai =s thì ghi nh n v trí p = i Sang Bư c 5 • N u ai ≠ s và i < N thì gán i=i+1 và l p l i bư c 4, ngư c l i sang Bư c 5 – Bư c 5: N u p ≠ 0 thì ñưa ra v trí c n tìm là p, ngư c l i thông báo không tìm th y giá tr s trong dãy s ñã cho. – Bư c 6: K t thúc. bangtqh@utc2.edu.vn Tin h c đ i cương - Chương 3 24
Bi u di n thu t toán b ng sơ đ kh i q S d ng các hình kh i đ minh ho cho các l nh hay thao tác. q S d ng mũi tên đ di n đ t th t th c hi n. q Đây là cách di n đ t khoa h c, có tính nh t quán cao. q Các hình kh i cơ b n – Kh i b t đ u. – Kh i k t thúc. – Kh i thao tác c th . – Kh i ki m tra đi u ki n. – Kh i vào/ra d li u. – Kh i g i chương trình con. q Các ký pháp. bangtqh@utc2.edu.vn Tin h c đ i cương - Chương 3 25 Các hình kh i cơ b n q Kh i b t đ u và k t thúc q G i chương trình con A (ít dùng) Begin A End q Ki m tra đi u ki n q Th c hi n công vi c A – Tuỳ thu c đi u ki n (Đúng hay Sai) mà r nhánh thích A h p q Vào/ra d li u Đúng Đi u ki n Sai bangtqh@utc2.edu.vn Tin h c đ i cương - Chương 3 26
M t s c u trúc cơ b n q C u trúc r nhánh q C u trúc l p If… then… while…do… Xö lý nÕu §iÒu KiÖn §óng ®óng If… then… Sai repeat…until… else… Xö lý nÕu sai bangtqh@utc2.edu.vn Tin h c đ i cương - Chương 3 27 Tính chu vi và di n tích HCN q Phương pháp li t kê q Sơ đ kh i – B1. Nh p hai c nh a,b – B2. Tính chu vi Begin • C = 2*(a+b) – B3. Tính di n tích §äc c¹nh a,b • S = a*b C := 2*(a+b) – B4. In chu vi C – B5. In di n tích S S := a*b – K t thúc In ra C,S End bangtqh@utc2.edu.vn Tin h c đ i cương - Chương 3 28
Lưu đ thu t gi i tính t ng N s t nhiên ñ u tiên q Cách 1 q Cách 2 bangtqh@utc2.edu.vn Tin h c đ i cương - Chương 3 29 Tính chu vi, di n tích tam giác q Phương pháp li t kê q Lưu đ thu t toán – B1. Nh p c nh a,b,c – B2. Ki m tra xem a,b,c có ph i ba c nh tam giác không • N u (a+b>c) và (b+c>a) và (a+c>b) thì sang bư c 3 • N u không thì thông báo “không t o thành tam giác” và k t thúc – B3. Tính chu vi C = (a+b+c) – B4. Tính n a chu vi p = C/2 p * ( p − a ) * ( p − b) * ( p − c) – B5. Tính di n tích tam giác theo công th c Hê-rông • S= p *( p − a) *( p − b) *( p − c) – B6. In k t qu C,S bangtqh@utc2.edu.vn Tin h c đ i cương - Chương 3 30
Bi u di n thu t toán b ng gi ngôn ng q Gi ngôn ng – D a trên ngôn ng l p trình b c cao. – G n v i ngôn ng t nhiên c a con ngư i. – Ví d : • Ngôn ng gi Pascal (t a Pascal) có các ký pháp khá gi ng v i ngôn ng l p trình Pascal, ñư c rút g n sao cho d di n đ t. q Gi ngôn ng ñư c đưa ra v i m c đích di n đ t các gi i thu t sao cho g n v i ngôn ng l p trình và ngôn ng t nhiên. q S d ng gi ngôn ng khi n vi c chuy n t gi i thu t sang chương trình d dàng hơn. bangtqh@utc2.edu.vn Tin h c đ i cương - Chương 3 31 Gi i thu t tính t ng N s t nhiên ñ u tiên Nh p N i:=0 S:=0 REPEAT S:=S+i i:=i+1 UNTIL (i>N) In S bangtqh@utc2.edu.vn Tin h c đ i cương - Chương 3 32
Thi t k và phân tích thu t toán q Quá trình vi t chương trình gi i bài toán: – Phân tích yêu c u bài toán – Thi t k gi i thu t – Vi t chương trình – Ch y th , đánh giá q Thi t k gi i thu t là t yêu c u c a m t bài toán, di n đ t m t gi i thu t gi i quy t bài toán đó. – Mô-đun hoá vi c gi i quy t bài toán. – Tinh ch nh t ng bư c. q Phân tích gi i thu t – Xem xét các tiêu chu n c a gi i thu t có ñư c tho mãn không, n u có thì ñ n m c đ nào. bangtqh@utc2.edu.vn Tin h c đ i cương - Chương 3 33 Thi t k t trên xu ng q Các bài toán l n đòi h i gi i thu t có quy mô l n. q Mô-đun hoá BÀI TOÁN – Bài toán = nhi u mô-đun – Mô-đun l n = nhi u mô-đun con. A B C – Vi c gi i quy t m t mô-đun m c th p nh t là “đ ñơn gi n” A1 A2 C1 C2 Chia đ tr . A2.1 A2.2 A2.3 q Thi t k t trên xu ng (top- down design): Bài toán đư c xem xét t t ng quát đ n chi ti t. bangtqh@utc2.edu.vn Tin h c đ i cương - Chương 3 34
Bài toán gi i phương trình b c 2 GI I PHƯƠNG TRÌNH B C II NH P H S X LÝ HI N TH K T QU TRƯ NG H P SUY BI N TRƯ NG H P KHÔNG SUY BI N TÍNH DELTA TÍNH NGHI M THEO DELTA bangtqh@utc2.edu.vn Tin h c đ i cương - Chương 3 35 Phương pháp tinh ch nh t ng bư c q Phương pháp tinh ch nh t ng bư c (stepwise refinement) – Ban đ u, s d ng ngôn ng t nhiên ñ di n t nh ng công vi c chính c a gi i thu t. – Các bư c sau, các công vi c đư c chi ti t hoá d n d n, ngôn ng t nhiên ñư c thay th d n d n b ng gi ngôn ng . – Cu i cùng, gi ngôn ng ñư c chuy n sang ngôn ng l p trình q Đ c đi m – Th hi n rõ ý tư ng thi t k t trên xu ng – G n li n vi c thi t k gi i thu t v i vi c l p trình bangtqh@utc2.edu.vn Tin h c đ i cương - Chương 3 36
S p x p dãy theo th t tăng d n q Phác th o “thô” v i nh ng “ý tư ng cơ b n” – “T dãy các s chưa ñư c s p x p, tìm s nh nh t và ñưa lên ñ u” – L p l i quy trình trên t i khi dãy chưa đư c s p x p tr thành r ng. q Ban đ u, dãy chưa s p x p là dãy ñã cho, dãy đã s p x p là r ng. q Lưu tr dãy b ng “m ng” (danh sách các s ), ñưa s nh nh t (aj) lên đ u danh sách là ñ i ch nó v i s ñ u tiên. q Đ i ch – S trung gian := aj – aj := s ñ u tiên – S ñ u tiên : = s trung gian q …, cu i cùng ta đư c chương trình v i ngôn ng c th bangtqh@utc2.edu.vn Tin h c đ i cương - Chương 3 37 Phân tích gi i thu t q Tính đúng đ n – Ch y th nghi m, ñ i chi u k t qu phát hi n đư c tính sai. – Dùng công c toán h c đ ch ng minh tính đúng đ n. q Tính đơn gi n – Gi i thu t có d hi u, d l p trình không? q Tính hi u qu – Đơn gi n chưa ch c đã hi u qu . – Đ i v i nhi u bài toán, tính hi u qu là quan tr ng, các gi i thu t đơn gi n l i gây t n tài nguyên, ch y ch m. – Th i gian tính toán ð ph c t p tính toán – Nh ng gi i thu t hi u qu ph i có ñ ph c t p (th i gian) tính toán ch p nh n đư c. q Tính d ng – Ch ng minh, suy lu n – Ch y th bangtqh@utc2.edu.vn Tin h c đ i cương - Chương 3 38
Đ quy và gi i thu t đ quy q M t đ i tư ng là ñ quy n u nó bao g m chính nó ho c đư c đ nh nghĩa b i chính nó. q Ví d : – Trong chương trình th i s trên vô tuy n, ñôi khi ta th y l i hình nh c a màn hình phía sau phát thanh viên. – Đ nh nghĩa s t nhiên: • 1 là s t nhiên • N là s t nhiên n u N-1 là s t nhiên – Đ nh nghĩa giai th a: • 0! = 1 • N! = N(N-1)! bangtqh@utc2.edu.vn Tin h c đ i cương - Chương 3 39 Gi i thu t đ quy q L i gi i c a bài toán T có ñư c d a trên l i gi i m t bài toán T’ nào đó thì l i gi i đó là m t l i gi i đ quy và gi i thu t đó g i là gi i thu t đ quy. q Bài toán T’ ph i nh hơn bài toán T. q Ví d “Bài toán tính N!” Tính 3! – Tn = tính N! • Tính Tn-1 = tính (N-1)! Tính 2! 3! = 3 x 2! – Tính Tn-2 = (N-2)! » … Tính 1! 2! = 2 x 1! – Tn-1 = Tn-2 x (N-1) • Tn = Tn-1 x N Tính 0! = 1 1! = 1 x 0! bangtqh@utc2.edu.vn Tin h c đ i cương - Chương 3 40