Chủ Đề 11F(CS):

Yêu cầu cần đạt của Chủ đề Fcs là:

- Phát biểu được bài toán sắp xếp và bài toán tìm kiếm.

- Viết được chương trình cho một vài thuật toán sắp xếp và tìm kiếm.

- Vận dụng được các thuật toán đã học để giải quyết một bài toán cụ thể.

- Biết được việc kiểm thử giúp lập trình viên phát hiện lỗi, làm tăng độ tin cậy của chương trình nhưng chưa chứng minh được tính đúng của chương trình.

- Trình bày được sơ lược khái niệm độ phức tạp thời gian của thuật toán và phép toán tích cực. Nêu được ví dụ minh hoạ.

- Vận dụng được những quy tắc thực hành xác định độ phức tạp thời gian của một số thuật toán, chương trình đã biết.

- Giải thích và vận dụng được phương pháp làm mịn dần trong lập trình.

-Giải thích và vận dụng được phương pháp thiết kế chương trình thành các mô đun cho một bài toán cụ thể.

- Nhận biết được lợi ích của phương pháp nêu trên: hỗ trợ làm việc đồng thời, dễ dàng bảo trì, phát triển chương trình và tái sử dụng các mô đun.

- Trình bày được cấu trúc dữ liệu mảng (một và hai chiều) và danh sách liên kết.

- Tạo được một thư viện nhỏ và viết được chương trình có sử dụng thư viện vừa tạo ra.

- Viết được chương trình vận dụng những kiến thức tích hợp liên môn để giải quyết vấn đề.

NỘI DUNG KIẾN THỨC

1. Tổ chức dữ liệu trong chương trình

1.1. Mảng một chiều

- Là một cấu trúc dữ liệu tuyến tinh bao gồm một dãy các phần tử có cùng kiểu.

- Khai báo mảng: tên biến mảng, kiểu dữ liệu, kích thước.

-Mảng một chiều được lưu trữ thành một khối các ô nhớ liền kề liên tục, có dung lượng bằng kích thước * độ dài kiểu dữ liệu.

- Các phần tử của máng có thể truy cập theo chỉ số.

- Hầu hết các ngôn ngữ lập trình bậc cao đều có sẵn kiểu dữ liệu mảng. Tuy nhiên, trong Python để sử dụng kiểu dữ liệu mảng phải sử dụng thư viện bên ngoài.

- Có thể sử dụng kiểu danh sách (list) của Python làm màng một chiều. Không những thế, kiểu danh sách linh hoạt hơn nhiều và có thêm nhiều phép toán so với màng.

1.2. Mảng hai chiều

- Mảng hai chiều hay còn gọi là ma trận dùng để lưu trữ một bảng số liệu hình chữ nhật với m hàng và n cột.

-Mảng hai chiều (m* n) là mâng một chiều kích thước m mà mỗi phần tử là một máng một chiều kích thước n.

- Khai báo mảng hai chiều: tên biển màng, kiểu dữ liệu, kích thước (m, n). 

- Màng hai chiều cũng được lưu trữ thành một khối các ô nhớ liên tục, có độ lớn bằng: số hàng * số cột * độ dài kiểu dữ liệu.

- Hầu hết các ngôn ngữ lập trình bậc cao đều có sẵn kiểu màng hai chiều.

- Trong Python, có thể sử dụng danh sách làm màng hai chiều.

1.3. Danh sách liên kết

- Danh sách liên kết gồm các phần tử gọi là các nút (node). Mỗi nút có 2 thành phần: Data chứa dữ liệu và phần liên kết gọi là next. Trường next trỏ tới địa chỉ của nút tiếp theo, nút cuối cùng trường next bằng Null.

-Mỗi danh sách liên kết quản lí một con trò Head trỏ tới nút đầu tiên trong danh sách, và có thể thêm con trỏ Tail trò tới nút cuối cùng trong danh sách.

- Các phép toán trên danh sách liên kết:

• Tìm kiếm phần tử có khoá k trong danh sách cho trước.

• Bổ sung một phần tử với khoá k cho trước vào danh sách.

• Xoá phần tử có khoá k trong danh sách.

2. Phương pháp làm mịn dần và sử dụng mô đun trong lập trình

2.1. Phương pháp làm mịn dần

Phương pháp làm mịn dần trong thiết kế chương trình là quá trình chi tiết hoá ý tưởng của các bước trước thành những hành động cụ thể hơn ở các bước sau. Ở bước cuối cùng, các hành động tương ứng với các câu lệnh của ngôn ngữ lập trình để viết chương trình hoàn chỉnh.

2.2. Phương pháp thiết kế chương trình thành các mô đun

Trong nội dung này, người học cần giải thích và vận dụng được phương pháp thiết kế chương trình thành các mô đun cho một bài toán cụ thể.

Phương pháp thiết kế chương trình theo mô đun sẽ tách bài toán lớn thành các bài toán nhỏ hơn, hay thành các mô đun tương đối độc lập với nhau, sau đó tiến hành thiết kế thuật toán và chương trình cho từng mô đun con. Mỗi mô đun có thể là một hàm hoặc thủ tục độc lập. Chương trình chính là một bàn ghép nối các hàm và thủ tục con.

2.3. Lợi ích của các phương pháp trên

Trong nội dung này, cần nhận biết được lợi ích của các phương pháp nêu trên, như:

- Hỗ trợ làm việc đồng thời: Có thể chia sẻ trong môi trường làm việc nhóm, ví dụ phân công mỗi người một công việc độc lập.

- Dễ dàng bảo trì, phát triển chương trình.

- Dễ dàng nâng cấp, thay đổi, chỉnh sửa mà không mất công sửa lại toàn bộ chương trình.

- Dễ dàng bổ sung các mô đun mới.

- Tái sử dụng các mô đun: Các mô đun được thiết lập một lần và sử dụng nhiều lần.

2.4. Tổ chức thư viện

Để có thể sử dụng lại các hàm, chúng ta cần thiết lập một thư viện. Cụ thể đưa các hàm chuẩn vào một tệp chương trình.

3. Kiểm thử và đánh giá hiệu quả của chương trình

3.1. Kiểm thử chương trình

Các loại lỗi và nguyên nhân:

- Lỗi cú pháp: Lỗi xảy ra trong quá trình soạn thảo chương trình do người lập trình chưa hiểu rõ ngôn ngữ lập trình mình sử dụng. Hiện nay các môi trường tích hợp phát triển phần mềm có công cụ soạn thảo chương trình hỗ trợ hạn chế các sai sót có thể sinh ra lỗi củ pháp.

- Lỗi thời gian chạy: Chương trình bị lỗi với một số bộ dữ liệu, ví dụ như chương trình đột ngột dừng giữa chừng hoặc chạy mãi không dừng.

- Lỗi ngữ nghĩa: Chương trình không bị hai lỗi trên nhưng cho kết quả không đúng.

Cần chạy thử chương trình để phát hiện ra các lỗi trong mã nguồn của chương trình. Gỡ lỗi là xác định vị trí có lỗi, nguyên nhân gây lỗi và sửa lỗi. Đảm bảo chương trình hoạt động đúng, đáp ứng yêu cầu bài toán đặt ra.

- Gỡ lỗi cú pháp: Khi kiểm thử chương trình, thông báo lỗi in ra danh sách số thứ tự các dòng lệnh bị lỗi và nguyên nhân lỗi.

- Gỡ lỗi thời gian chạy và lỗi ngữ nghĩa. Tạo các bộ dữ liệu kiểm thử để kiểm tra dữ liệu đầu ra có chính xác không. Kiểm tra các lệnh rẽ nhánh, các lệnh lập, các giá trị tại đầu mút trái phải của các biểu thức điều kiện.

- Khi phát hiện ra kết quả đầu ra của chương trình không như mong đợi:

 + Thiết lập điểm dừng hoặc cho chương trình chạy theo từng lệnh đề kiểm tra và tìm ra lỗi của chương trình.

+ Thực hiện in dữ liệu trung gian trong quá trình kiểm thử để tìm ra lỗi của chương trình.

- Tập hợp toàn bộ các trường hợp đầu vào có thể xảy ra của một bài toán thường là vô hạn. Không thể chạy thử chương trình với tất cả các đầu vào có thể. Do vậy, kiểm thử chương trình chỉ làm tăng độ tin cậy của chương trình nhưng chưa chứng minh được tỉnh đúng của chương trình.

3.2. Đánh giá độ phức tạp của thuật toán

Để đánh giá hiệu quả của thuật toán, người ta có thể cài đặt và chạy thử chương trình. Từ đó, đánh giá thời gian và lượng tài nguyên cần thiết để thực hiện chương trình. Tuy nhiên, thời gian đo được phụ thuộc vào nhiều yếu tố không liên quan tới thuật toán như: phần cứng máy tính, ngôn ngữ lập trình, kĩ thuật lập trình. Hơn nữa, sẽ không khả thi nếu muốn chọn cách lập nhiều chương trình để so sánh. Do vậy, cần có một cách phân tích lí thuyết để đánh giá thuật toán.

Thời gian tính của thuật toán (7) phụ thuộc vào kích thước dữ liệu đầu vào n. kí hiệu hàm số T(n) Để xác định người ta đi đếm số lần thực hiện các phép T(n) toán sơ cấp (phép toán đơn) như: phép gán, phép tỉnh số học, phép so sánh,...

 Ví dụ: Cho chương trình sau:

Câu lệnh 1 thực hiện 1 phép toán sơ cấp (phép gán), câu lệnh 3 thực hiện 2 phép toán sơ cấp (phép cộng và phép gán) và được lặp lại n lần. Do vậy, T(n) = 2n + 1

Khi n càng lớn thì thời gian T(n) sẽ tăng lên nhưng tốc độ tăng khác nhau. Các nhà khoa học sử dụng  kí pháp O để đánh giá và phân loại tốc độ tăng của hàm 7(n) khi n tiến tới vô cùng (Bảng 1)

Để xác định O của một hàm 7(n), người ta tìm hằng số dương c và số nguyên dương n sao cho: T(n) ≤c*g(n), Vnn

Khi đó: 7(n) = O(g(n)).

Ví dụ: Ta có chương trình với thời gian tỉnh là T(n)=2^ * n + 1

Ta có 2^ * n + 1 <=2^ * n+n với mọi n >= 1 .

Do vậy: 7(n) ≤ 3*n với mọi n >= 1 .

Chọn c = 3 n_{0} = 1 Ta có 7(n) = O(n).

Một số quy tắc xác định độ phức tạp thời gian

- Cấu trúc tuần tự: Giả sử P và Q là hai đoạn của thuật toán. Gọi Time(P), Time(Q) là thời gian tính của P và Q tương ứng. Khi đó ta có thời gian tính đòi hỏi bởi “P; Q", nghĩa là P thực hiện trước, tiếp đến là Q, sẽ là: Time(P; Q) = Time(P) + Time(Q).

- Cấu trúc rẽ nhánh: Thời gian tính của cấu trúc rẽ nhánh là thời gian lớn nhất của các nhánh và thời gian kiểm tra điều kiện.

– Cấu trúc lặp (for, while): Thời gian thực hiện của cấu trúc lặp bằng tổng thời gian thực hiện mỗi bước lập. Nếu mỗi bước lặp có số phép toán cơ sở bằng nhau thì thời gian thực hiện của cấu trúc lặp bằng giá trị đó nhân với số lần lặp.

- Quy tắc lấy max (quy tắc cộng): Nếu f (n) = O(g,(n)) và f(n) = O(g(n)) thì f(n)+f(n) = O(max(g,(n), g(n))). Công thức áp dụng cho hai cấu trúc điều khiển được thực hiện tuần tự.

- Quy tắc nhân: f(n) = O(g(n)) và (n) = O(g,(n)) thi f(n) *f(n) = O(g,(n) * g(n)). Công thức áp dụng cho hai cấu trúc điều khiển lồng nhau.

4. Viết chương trình cho một số thuật toán tìm kiếm

4.1. Bài toán tìm kiếm

Theo nghĩa chung nhất, bài toán tìm kiếm: Cho một yêu cầu tìm kiếm và một tập hợp dữ liệu là phạm vi tìm kiếm. Hãy tìm mục (các mục) dữ liệu đáp ứng yêu cầu tìm kiếm đã cho hoặc khẳng định không có mục dữ liệu nào đáp ứng yêu cầu đó.

Bài toán tìm kiếm có thể mô tả một cách hình thức như sau:

+ Đầu vào: Cho trước dây số 4[0], A[1],..., A[n - 1] và giá trị K + Đầu ra: Cần tìm ra chỉ số í mà phần từ A[i] có giá trị bằng K. Nếu không thấy thì trả về giá trị -1.

4.2. Thuật toán tìm kiếm tuần tự

Ý tưởng thuật toán: Duyệt lần lượt các phần tử của dây để tìm phần tử có giá trị bằng K. Nếu tìm thấy, trả về chỉ số của phần tử bằng K; ngược lại, thông báo không tìm thấy và trả về giá trị -1.

Dưới đây là hai đoạn mã giả sử dụng câu lệnh for và while để thực hiện việc duyệt qua các phần tử trong dãy

4.3. Thuật toán tìm kiếm nhị phân

Khác với thuật toán tìm kiểm tuần tự, thuật toán tìm kiếm nhị phân tìm kiếm trên dây số đã được sắp xếp.

Ý tường thuật toán: Thuật toán thực hiện bằng cách liên tục thu hẹp phạm vi tìm kiếm. Nếu giá trị của phần tử ở giữa bằng Á thì thông báo tìm thấy. Nếu giá trị K nhỏ hơn giá trị của phần tử ở giữa thì thu hẹp phạm vì tìm kiếm là nửa đầu của dây (ngược lại là nửa sau). Cứ tiếp tục thu hẹp phạm vì như vậy cho tới khi tìm thấy hoặc đã duyệt hết thì thông báo không tìm thấy

5. Viết chương trình cho một số thuật toán sắp xếp

5.1. Bài toán sắp xếp

Là quá trình tổ chức lại tập hợp các mục sao cho mỗi mục và phần kế tiếp của nó thoả mãn một mối quan hệ quy định trước (sắp xếp tăng dần hoặc giảm dần). Bài toán sắp xếp có thể được phát biểu một cách đơn giản như sau: Cho dây A gồm n phần tử A[0], A[1] ,...,A[n]. Hãy sắp xếp dây 4 theo thứ tự tăng hoặc giảm dần, nghĩa là A[0] <= A[1] <= A[2] <=...<= A[n]

5.2. Thuật toán sắp xếp nổi bọt (Bubble Sort)

Thuật toán sắp xếp nổi bọt lấy ý tưởng tử hiện tượng "nổi bọt" của không khi dưới nước.

  Ý tưởng thuật toán: Lập đi lặp lại việc duyệt dãy cần sắp xếp, mỗi lần duyệt thực hiện thao tác đổi chỗ các giá trị trong dây sao cho các giá trị lớn hơn "nổi bọt" lên đầu (khí sắp xếp giảm dần) hoặc xuống cuối (khi sắp xếp tăng dần).

5.3. Thuật toán sắp xếp chèn (Insertion Sort)

Ý tưởng thuật toán: Thực hiện vòng lập duyệt từ phần từ thứ hai đến cuối dây. Sau mỗi bước lập, phần tử tương ứng sẽ được chèn vào vị trí đúng của dây con đã được sắp xếp là các phần tử ở phía trước vị trí đang duyệt.