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

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...
Nội dung trích xuất từ tài liệu:
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ánbangtqh@utc2.edu.vnN i dung1. 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 2Thu 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ư ngq Các thao tác trong thu t toánq Đ 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/51Thu t toán - cách hi u thông thư ngq 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 4Trò chơi 5 quân bàiq 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 5Trò 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 6Trò 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 7Trò 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 8Trò 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 9Trò 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 10Các thao tác trong thu t toánq 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ínhq 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 14Ngôn ng l p trìnhq 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 h ...