Cơ sở dữ liệu - Thiết kế thuật toán

Nội dung text: Cơ sở dữ liệu - Thiết kế thuật toán

1. Thuật toán v 1.0 - 10/2012 Lê Viết Mẫn - lvman@hce.edu.vn 1 Thuật toán
2. chúng ta đã học 1. Lập trình là gì ? 1.1. Lập trình và ngôn ngữ lập trình 1.2. Lịch sử và các hướng lập trình 1.3. Chương trình và thuật toán 1.4. Các bước trong lập trình 2. C# và .NET Lê Viết Mẫn - lvman@hce.edu.vn 2 Thuật toán
3. Giải bài toán trên máy tính 1. Xác định bài toán 2. Thiết kế thuật toán 3. Phân tích thuật toán 4. Cài đặt thuật toán 5. Kiểm tra / Bắt lỗi 6. [ Sửa lỗi ] Lê Viết Mẫn - lvman@hce.edu.vn 3 Thuật toán
4. Nội dung 1. Thuật toán 1.1. Khái niệm 1.2. Các tính chất 1.3. Phát triển thuật toán 2. Mô tả thuật toán 3. Các dạng thuật toán cơ bản 4. Ví dụ Lê Viết Mẫn - lvman@hce.edu.vn 4 Thuật toán
5. Thuật toán Lê Viết Mẫn - lvman@hce.edu.vn 5 Thuật toán
6. Thuật toán • Một tập các chỉ thị / lệnh đơn giản được xác định rõ ràng để giải quyết một bài toán nào đó • Nhận một tập các giá trị ở đầu vào (input) • Tính toán và trả ra một hoặc một tập các giá trị ở đầu ra (output) • Thuật toán = Logic + Điều khiển • Logic - trả lời câu hỏi “Thuật toán làm gì ? Giải quyết vấn đề gì ? Những yếu tố trong bài toán có quan hệ với nhau thế nào ? ” • Gồm các kiến thức chuyên môn mà bạn phải biết để có thể giải bài toán • Để giải bài toán tính diện tích hình cầu, bạn phải biết công thức tính diện tích hình cầu • Điều khiển - trả lời câu hỏi “Giải thuật phải làm như thế nào ?” Lê Viết Mẫn - lvman@hce.edu.vn 6 Thuật toán
7. Thuật toán • Có thể được mô tả bằng • Ngôn ngữ tự nhiên • Ngôn ngữ lập trình • Mã giả • Lưu đồ • Cấu trúc dữ liệu - Phương pháp tổ chức dữ liệu • Chương trình = Thuật toán + Cấu trúc dữ liệu Lê Viết Mẫn - lvman@hce.edu.vn 7 Thuật toán
8. Ví dụ - giải p.t bậc nhất ax + b = 0 Lê Viết Mẫn - lvman@hce.edu.vn 8 Thuật toán
9. Ví dụ - giải p.t bậc nhất ax + b = 0 Nếu a ≠ 0: x = -b/a Ngược lại, a = 0: Nếu b = 0: pt có vô số nghiệm Nếu b ≠ 0: pt vô nghiệm Lê Viết Mẫn - lvman@hce.edu.vn 9 Thuật toán
10. Ví dụ - tìm số lớn nhất Cho ba số a, b, c. Tìm số lớn nhất trong ba số đó Lê Viết Mẫn - lvman@hce.edu.vn 10 Thuật toán
11. Ví dụ - tìm số lớn nhất Cho ba số a, b, c. Tìm số lớn nhất trong ba số đó Bước 1 : Cho Max = a Bước 2 : So sánh b với Max. Nếu b > Max thì cho Max = b Bước 3 : So sánh c với Max. Nếu c > Max thì cho Max = c Bước 4 : Trả ra Max là giá trị lớn nhất Bước 5 : Dừng Lê Viết Mẫn - lvman@hce.edu.vn 11 Thuật toán
12. Các câu hỏi về thuật toán • Thuật toán đã giải quyết được bài toán được phát biểu ? • Thuật toán đã được định nghĩa tốt ? • Thuật toán đưa ra được một kết quả ? • Thuật toán kết thúc sau thời gian tính toán hợp lý ? Lê Viết Mẫn - lvman@hce.edu.vn 12 Thuật toán
13. Tính chất Tính kết thúc (tính dừng) • quá trình thực hiện thuật toán phải kết thúc sau khi thực hiện một số hữu hạn các bước công việc Thuật toán tính tổng các số tự nhiên Bước 1 : Cho s = 0, i = 1 Bước 2 : Cộng thêm i vào s ( s = s + i ) Bước 3 : Tăng i thêm 1 ( i = i + 1 ) Bước 4 : Quay lại bước 2 Bước 5 : Nhận s là kết quả giải bài toán Bước 6 : Dừng Lê Viết Mẫn - lvman@hce.edu.vn 13 Thuật toán
14. Tính chất Tính xác định • nếu trong những điều kiện như nhau thì kết quả thực hiện không phụ thuộc vào đối tượng thực hiện thuật toán • thuật toán phải rõ ràng, không nhập nhằng, không thể hiểu theo nhiều nghĩa Thuật toán tìm giá trị lớn nhất Bước 1 : Cho Max = a Bước 2 : So sánh b với Max. Nếu b > Max thì cho Max = b Bước 3 : So sánh c với Max. Nếu c > Max thì cho Max = c Bước 4 : Trả ra Max là giá trị lớn nhất Bước 5 : Dừng Lê Viết Mẫn - lvman@hce.edu.vn 14 Thuật toán
15. Tính chất Tính tổng quát • nếu thuật toán được dùng để giải cả một lớp bài toán cùng loại Thuật toán tìm giá trị lớn nhất Bước 1 : Cho Max = a Bước 2 : So sánh b với Max. Nếu b > Max thì cho Max = b Bước 3 : So sánh c với Max. Nếu c > Max thì cho Max = c Bước 4 : Trả ra Max là giá trị lớn nhất Bước 5 : Dừng Lê Viết Mẫn - lvman@hce.edu.vn 15 Thuật toán
16. Tính chất Tính xác định đầu vào - đầu ra • nếu xác định rõ các dữ liệu đầu vào và các dữ liệu đầu ra • đầu vào, đầu ra được xác định càng chính xác thì quá trình xây dựng thuật toán càng thuận lợi và thuật toán càng có chất lượng cao hơn Thuật toán tìm giá trị lớn nhất Bước 1 : Cho Max = a Bước 2 : So sánh b với Max. Nếu b > Max thì cho Max = b Bước 3 : So sánh c với Max. Nếu c > Max thì cho Max = c Bước 4 : Trả ra Max là giá trị lớn nhất Bước 5 : Dừng Lê Viết Mẫn - lvman@hce.edu.vn 16 Thuật toán
17. Tính chất Tính hiệu quả • nếu cho ra kết quả đúng trong mức chi phí ít nhất về thời gian, không gian Thuật toán tìm giá trị lớn nhất Bước 1 : Cho Max = a Bước 2 : So sánh b với Max. Nếu b > Max thì cho Max = b Bước 3 : So sánh c với Max. Nếu c > Max thì cho Max = c Bước 4 : Trả ra Max là giá trị lớn nhất Bước 5 : Dừng Lê Viết Mẫn - lvman@hce.edu.vn 17 Thuật toán
18. Phát triển thuật toán • Xác định đầu vào (Input) • Xác định các bước xử lý (Process) • Xác định đầu ra (Output) • Vẽ biểu đồ HIPO • Xác định các chương trình con (Module) Lê Viết Mẫn - lvman@hce.edu.vn 18 Thuật toán
19. Xác định đầu vào • Chúng ta cần dữ liệu gì ? • Chúng ta lấy dữ liệu đó như thế nào ? • Dữ liệu tồn tại ở dạng nào ? Lê Viết Mẫn - lvman@hce.edu.vn 19 Thuật toán
20. Xác định đầu ra • Những kết quả nào chương trình phải trả ra cho người sử dụng ? • Kết quả phải được trả ra ở dạng nào ? Lê Viết Mẫn - lvman@hce.edu.vn 20 Thuật toán
21. Xác định các bước xử lý • Cách xử lý dữ liệu để đạt được kết quả có ý nghĩa ? • Áp dụng công thức gì ? Lê Viết Mẫn - lvman@hce.edu.vn 21 Thuật toán
22. Vẽ biểu đồ HIPO Hierarchy of Inputs Processes & Outputs Bài toán Đầu vào Xử lý Đầu ra C.t. con C.t. con C.t. con C.t. con C.t. con C.t. con Lê Viết Mẫn - lvman@hce.edu.vn 22 Thuật toán
23. Xác định các c.t. con • Cách nào để chia các vấn đề lớn thành các vấn đề nhỏ hơn, dễ quản lý hơn ? • Các chương trình con cần những đầu vào nào ? • Các xử lý nào là cần thiết cho mỗi chương trình con ? • Đầu ra nào là được chờ đợi tại mỗi chương trình con ? Lê Viết Mẫn - lvman@hce.edu.vn 23 Thuật toán
24. Mô tả thuật toán Lê Viết Mẫn - lvman@hce.edu.vn 24 Thuật toán
25. Ngôn ngữ tự nhiên ax + b = 0 Nếu a ≠ 0: x = -b/a Ngược lại, a = 0: Nếu b = 0: pt có vô số nghiệm Nếu b ≠ 0: pt vô nghiệm • Sử dụng ngôn ngữ thường ngày (tiếng mẹ đẻ) • Dễ trình bày vấn đề • Dài dòng, không trình bày rõ cấu trúc thuật toán, khó hiểu Lê Viết Mẫn - lvman@hce.edu.vn 25 Thuật toán
26. Mã giả ax + b = 0 If a ≠ 0 then x = -b/a else a = 0: If b = 0 then pt có vô số nghiệm If b ≠ 0 then pt vô nghiệm • Dùng kết hợp ngôn ngữ tự nhiên với các cú pháp của một/nhiều ngôn ngữ lập trình nào đó • Diễn tả được cấu trúc thuật toán, dễ viết • Phụ thuộc vào ngôn ngữ lập trình Lê Viết Mẫn - lvman@hce.edu.vn 26 Thuật toán
27. Lưu đồ • Còn được gọi là sơ đồ khối • Sử dụng các khối hình để thể hiện một bước công việc / thao tác nào đó • Thứ tự thực hiện các công việc được chỉ định bằng các cạnh có hướng nối liền các khối với nhau • Trình bày thuật toán bằng hình vẽ trực quan, dễ nhìn, dễ hiểu và dễ thấy được tổng thể của thuật toán • Độc lập ngôn ngữ Lê Viết Mẫn - lvman@hce.edu.vn 27 Thuật toán
28. Ví dụ - lưu đồ p.t bậc nhất Lê Viết Mẫn - lvman@hce.edu.vn 28 Thuật toán
29. Ngôn ngữ lưu đồ Thực hiện công việc A Vào / ra dữ liệu Một phép kiểm tra B, tùy thuộc Bắt đầu hay kết thúc vào trạng thái của B là đúng hay một thuật toán sai mà rẻ nhánh thích hợp Lê Viết Mẫn - lvman@hce.edu.vn 29 Thuật toán
30. Các dạng thuật toán cơ bản Lê Viết Mẫn - lvman@hce.edu.vn 30 Thuật toán
31. Thuật toán tuần tự entry statement 1 ; { statement 2 ; statement 3 statement n ; } exit Lê Viết Mẫn - lvman@hce.edu.vn 31 Thuật toán
32. Ví dụ 1 Tính tiền lương công nhân nếu biết lương căn bản và số ngày công Lê Viết Mẫn - lvman@hce.edu.vn 32 Thuật toán
33. Ví dụ 1 Tính tiền lương công nhân nếu biết lương căn bản và số ngày công Đầu vào : lương căn bản, số ngày công Đầu ra : tiền lương công nhân Xử lý : tính theo công thức Lương = Lương căn bản * Ngày công Lê Viết Mẫn - lvman@hce.edu.vn 33 Thuật toán
34. Ví dụ 1 Tính tiền lương công nhân nếu biết lương căn bản và số ngày công Begin Nhập LCB, NC Lương = LCB * NC In Lương End Lê Viết Mẫn - lvman@hce.edu.vn 34 Thuật toán
35. Thuật toán lựa chọn entry true false expression true expression statement statement_1 statement_2 false exit Dạng 1 Dạng 2 Lê Viết Mẫn - lvman@hce.edu.vn 35 Thuật toán
36. Ví dụ 2 Cho ba số a, b, c. Tìm số lớn nhất trong ba số đó Bước 1 : Cho Max = a Bước 2 : So sánh b với Max. Nếu b > Max thì cho Max = b Bước 3 : So sánh c với Max. Nếu c > Max thì cho Max = c Bước 4 : Trả ra Max là giá trị lớn nhất Bước 5 : Dừng Lê Viết Mẫn - lvman@hce.edu.vn 36 Thuật toán
37. Begin Nhập a, b, c Max = a false b > Max true Max = b false c > Max true Max = c In Max End Lê Viết Mẫn - lvman@hce.edu.vn 37 Thuật toán
38. Ví dụ 3 Nhập vào số nguyên n. Kiểm tra nếu n > 0 thì tăng n lên 1 đơn vị. Xuất kết quả ra màn hình Đầu vào : số nguyên n Đầu ra : giá trị của n Xử lý : kiểm tra n > 0, nếu đúng tăng n lên 1 Lê Viết Mẫn - lvman@hce.edu.vn 38 Thuật toán
39. Ví dụ 3 Nhập vào số nguyên n. Kiểm tra nếu n > 0 thì tăng n lên 1 đơn vị. Xuất kết quả ra màn hình Begin Nhập n false n > 0 true n = n + 1 In n End Lê Viết Mẫn - lvman@hce.edu.vn 39 Thuật toán
40. Ví dụ 4 Nhập vào số nguyên n. Kiểm tra nếu n chẵn xuất ra màn hình câu “n chẵn”, ngược lại xuất “n lẻ” Đầu vào : số nguyên n Đầu ra : giá trị của n Xử lý : kiểm tra n chẵn hoặc lẻ thì xuất ra dòng tương ứng Lê Viết Mẫn - lvman@hce.edu.vn 40 Thuật toán
41. Ví dụ 4 Nhập vào số nguyên n. Kiểm tra nếu n chẵn xuất ra màn hình câu “n chẵn”, ngược lại xuất “n lẻ” Begin Nhập n true false n % 2 = 0 In “n chẵn” In “n lẻ” End Lê Viết Mẫn - lvman@hce.edu.vn 41 Thuật toán
42. Thuật toán lặp statement_1 false false condition statement condition true statement_2 true true statement condition statement_3 false Dạng 1 Dạng 2 Dạng 3 Lê Viết Mẫn - lvman@hce.edu.vn 42 Thuật toán
43. Ví dụ 5 Nhập vào điểm thi ( ∈ [0 10]). Nếu nhập sai thì yêu cầu nhập lại Đầu vào : số nguyên n ∈ [0 10] Đầu ra : Xử lý : nếu n ∉ [0 10] thì yêu cầu nhập lại Lê Viết Mẫn - lvman@hce.edu.vn 43 Thuật toán
44. Ví dụ 5 Nhập vào điểm thi ( ∈ [0 10]). Nếu nhập sai thì yêu cầu nhập lại Begin Nhập n true n ∉ [0 10] false End Lê Viết Mẫn - lvman@hce.edu.vn 44 Thuật toán
45. Ví dụ 6 Tính tổng S = 1 + 2 + + n (với n > 0). Nhập n vào từ bàn phím Đầu vào : số nguyên n (n > 0) Đầu ra : S Xử lý : i = i + 1 và S = S + i Lê Viết Mẫn - lvman@hce.edu.vn 45 Thuật toán
46. Begin Nhập n S = 0 i = 1 true i > n false S = S + i i = i + 1 In S End Lê Viết Mẫn - lvman@hce.edu.vn 46 Thuật toán
47. Cảm ơn sự chú ý Câu hỏi ? Lê Viết Mẫn - lvman@hce.edu.vn 47 Thuật toán