08.CS-Kĩ thuật lập trình

Giới thiệu

Kĩ thuật lập trình là một chủ đề lớn trong khoa học máy tính. Cùng với với CSDL, đây là một trong những mảng kiến thức nền tảng và quan trọng của sinh viên tất cả các ngành liên quan đến CNTT và tự động hóa. Ngày nay, với sự phát triển mạnh của khoa học dữ liệu và nhiều ngành nghề có xu hướng dịch chuyển sang khai thác các thành tựu của ngành khoa học này thì kỹ năng về lập trình cơ bản trở thành một kỹ năng quan trọng cho rất nhiều người thuộc nhiều ngành nghề, lĩnh vực khác nhau.

Trong nội dung chủ đề, chúng ta tập trung vào các yêu cầu cần đạt cơ bản mà Bộ GD quy định trong chương trình.

Yêu cầu cần đạt

Viết chương trình cho một số thuật toán sắp xếp, tìm kiếm cơ bản

- 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ể.

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

- 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.

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

- 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.

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

- 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 đề. 

Tóm tắt lý thuyết

Nguồn: Phần tóm tắt lý thuyết sau đây sử dụng các nguồn tài liệu sau đây

• Cấu trúc và nhiều phần nội dung chính lấy từ sách "Hướng dẫn ôn thi tốt nghiệp THPT môn Tin học" của nhóm tác giả Nguyễn Chí Trung (chủ biên), Phạm Thọ Hoàn, Nguyễn Thị Thanh Huyền, Đỗ Trung Kiên, Nguyễn Thế Lộc, NXB ĐH Quốc Gia Hà Nội.

• Một số phần nội dung chi tiết lấy từ sách giáo khoa Tin học 11 Cánh Diều, tác giả Hồ Sỹ Đàm (chủ biên), NXB Đại Học Sư Phạm.

• Một số hình ảnh lấy từ các website dạy học lập trình như: GeeksforGeeks, tutorialspoint, ...

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

Chương trình = Cấu trúc dữ liệu + giải thuật

Tổ chức dữ liệu chính là cấu trúc dữ liệu, là cách chúng ta tổ chức việc lưu trữ dữ liệu để chương trình thực thi, lưu trữ kết quả chương trình, .... Việc lưu trữ này ảnh hưởng rất lớn đến hiệu quả chương trình cũng như tài nguyên máy tính. Bản thân cấu trúc dữ liệu là một nhánh nghiên cứu lớn của khoa học máy tính. Trong phạm quy chủ đề, chúng ta quan tâm đến ba cấu trúc dữ liệu được nói đến trong yêu cầu cần đạt: Mảng một chiều, mạng hai chiều và danh sách liên kết.

Mảng một chiều

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

• Trong bộ nhớ, 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ố.

• Các ngôn ngữ lập trình bậc cao đều có sẵn kiểu dữ liệu mảng.

• Để xem thêm chi tiết về mảng một chiều trong python: Các em xem tại đây

• Để xem thêm chi tiết về mảng một chiều trong C++: Các em xem tại đây

Mảng hai chiều

• Còn gọi là ma trận dùng để lưu trữ một bảng dữ 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.

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

• Để truy cập vào từng phần tử của mảng hai chiều người ta dùng Tên mảng[chỉ số hàng][chỉ số cột]

• 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 2 chiều.

• Để xem thêm chi tiết về mảng hai chiều trong C++, các em xem tại đây

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

• Để xem chi tiết về mảng hai chiều trong Python, các em xem tại đây

Danh sách liên kết - Link list

• Là một cầu trúc động, 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ó hai thành phần: Data chứa dữ liệu và phần liên kết gọi là next.

• 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 gồm:

  • Tìm kiếm phần tử có khóa k trong dách sách cho trước

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

  • Xóa phần tử có khóa k trong danh sách

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

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 hóa ý 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 thành.

Phương pháp thiết kế chương trình thành các modun

Là phương pháp tách rời bài toán lớn thành các bài toán nhỏ hơn, hay thành các modun độc lập với nhau, sau đó sẽ phân tích, thiết kế giải thuật, viết chương trình cho từng modun. Chương trình chính là một bảng ghép nối các hàm và thủ tục, đôi khi là ghép nối các chương trình khác.

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

• Giúp làm việc đồng thời.

• Dễ bảo trì, phát triển

• Dễ nâng cấp, thay đổi, chỉnh sửa.

• Dễ bổ sung các modun mới

• Tái sử dụng modun

Tổ chức thư viện

Thư viện là một tập tin chứa các hàm, thủ tục được viết sẵn, khi cần dùng ở đâu thì gọi tên thư viện đó vào rồi có thể sử dụng các hàm của nó.

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

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

Lỗi cú pháp (Syntax Error): Xảy ra khi chúng ta viết chương trình quy phạm các cú pháp do ngôn ngữ lập trình cụ thể quy định. Ngày nay các trình dịch đều có cơ chế phát hiện các lỗi cú pháp.

Lỗi Logic (Logical Errors), hay còn gọi là lỗi ngữ nghĩa: Là những lỗi mà chương trình chạy đúng nhưng không cho kết quả mong muốn.

Lỗi thời gian (Time Errors): Chương trình thực thi được nhưng chậm hơn mong đợi hoặc vượt quá thời gian xử lý cho phép, có thể do vòng lặp vô hạn hoặc các thuật toán không hiệu quả.

Lỗi thực thi (Run-time Errors): Những lỗi này xuất hiện khi chương trình đang chạy, có thể do tràn số, lỗi chia cho 0, hay truy cập ngoài vùng nhớ của mảng đang xét.

Gỡ lỗi

Lỗi cú pháp thường được trình dịch hỗ trợ thông báo rõ vị trí lỗi và nguyên nhân lỗi, chúng ta chỉ cần chịu khó đọc đúng và tìm cách sửa và chạy lại.

Lỗi thực thi (Run-time): Thường mất thời gian sửa hơn, đòi hỏi phải hiểu về miền giá trị của dữ liệu, về cấu trúc bộ nhớ và về ý nghĩa thật sự khi chạy của các câu lệnh.

Lỗi Logic (ngữ nghĩa): Tạo các bộ dữ liệu kiểm (testcase) để kiểm tra dữ liệu đầu ra. Kiểm tra các lệnh rẽ nhành, lặp, các giá trị tại các đầu mút trái phải cảu các biểu thức điều kiện. Chúng ta thường không thể tạo đủ testcase để kiểm tra hết tất cả lỗi ngữ nghĩa chương trình mà chỉ ở mức tương đối, đảm bảo được phần nào độ tin cậy của chương trình chứ không thể chứng mình tính đúng đắn của chương trình.

Để chứng minh tính đúng đắn một cách phổ quát, chúng ta cần nền tản toán học vững chắc. Tuy nhiên, trong một chừng mực nào đó, đảm bảo được độ tin cậy là đủ cho phạm vi sử dụng và một khoản thời gian chấp nhận được.

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

Hiệu quả của một thuật toán được đánh giá dựa vào thời gian thực thi (chạy) và lượng tài nguyên mà nó sử dụng trong quá trình đó. Người ta có thể đánh giá thực nghiệm bằng cách chạy thử rồi quan sát, tuy nhiên, thời gian chạy phụ thuộc nhiều yếu tố khác nên thường người ta đưa ra hai chỉ số độ phức tạp thời gian (Time complexity) và độ phức tạp không gian (Space complexity) rồi tìm các lý thuyết toán học để chứng minh, tính toán hai chỉ số này.

Thời gian tính của một thuật toán đước ký hiệu là T, với một bộ dữ liệu đầu vào có kích thước n thì ta kí hiệu là T(n). T(n) được tính dựa vào số lần thực hiện các phép 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ụ

Trong ví dụ trên, dòng lệnh số 1 là hai phép gán, là hai phép tính đơn. Câu lệnh số 3 thực hiện một lệnh xuất dữ liệu, nhưng lệnh này đặt trong vòng lặp, nên sẽ được lặp lại n lần (cụ thể ở đây là 8 lần). Do vậy T(n) = n + 2

Khi n càng lớn, T(n) sẽ tăng lên, tùy theo hàm số theo sau nó thì tốc độ tăng nhanh chậm khác nhau.

Người ta dùng kí pháp Omega, hay big-O để ký hiệu cho độ phức tạp thời gian của thuật toán.

Để xác định O của một hàm T(n), người ta tìm hằng số dương c và một số nguyên dương n_0 sao cho T(n) <=c*g(n), ∀n >=n_0.

Khi đó: T(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, ∀n >=1.

Vậy: T(n) <= 3*n, ∀n >=1

Như vậy, chọn c = 3, n_0 = 1 ta có T(n)  = O(n)

Một số quy tắc xác định độ phức tạp cơ bản

Cấu trúc tuần tự: Nếu ta có hai đoạn chương trình có thơi gian thực thi là lược là P, Q độc lập nhau thì thời gian của chương trình là P + Q.

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: Tính bằng tổng thời gian thực hiện các phép toán bên trong vòng lặp, thường để dễ tính, chúng ta coi là miền chạy của biến đếm. Ví dụ for i from n to m do: ... thì độ phức tạp là O(n - m) và thông thường được xem là O(n).

Quy tắc cộng: Nếu chúng ta có hai vòng lặp độc lập nhau. Vòng lặp đầu có độ phức tạp O(m), vòng lặp sau có độ phức tạp O(n) thì độ phức tạp thời gian tổng thể là max(O(m), O(n)).

Quy tắc nhân: Nếu ta có hai vòng lặp lồng nhau, vòng lặp bên ngoài có độ phức tạp O(m), vòng lặp trong có độ phức tạp O(n) thì độ phức tạp tổng thể là O(m*n).

Nhiệm vụ 1: Tính độ phức tạp cho bài toán sau đây theo hai cách tiếp cận.

Bài toán tìm kiếm và sắp xếp

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

Là bài toán phổ biến trong mọi lĩnh vực, mô hình chung là cho một tập dữ liệu, ta cần tìm một giá trị cụ thể hoặc đáp ứng một số điều kiện nào đó.

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

Cho dãy số A gồm n phần tử: A[0], A[1], ..., A[n-1] và giá trị k. Tìm chỉ số i mà phần tử A[i] có giá trị bằng k. Nếu không tìm thấy thì in ra -1.

Hai thuật toán phổ biến nhất để giải quyết bài toán trên là tìm kiếm tuần tự và tìm kiếm nhi phân.

Tìm kiếm tuần tự

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; Nếu đã tìm hết dãy mà không thấy thì trả về -1.

Nhiệm vụ 2: Phân tích độ phức tạp thuật toán trên

Nhiệm vụ 3: Dùng ngôn ngữ C++ hoặc Python cài đặt thử thuật toán trê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 chính của thuật toán là thu hẹp dần phạm vi tìm kiếm. Nếu giá trị giữa bằng K, ta thông báo vị trí giữa, ngược lại nếu vị trí giữa lớn hơn K, ta tìm bên trái, ngược lại tìm bên phải. Cứ lặp lại như vậy cho đến khi tìm thấy, nếu không thì thông báo không tìm thấy.

Nhiệm vụ 4: Đánh giá độ phức tạp thuật toán

Nhiệm vụ 5: Cài đặt thử bằng ngôn ngữ C++ hoặc Python

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

Bài toán sắp xếp cũng là một bài toán phố biến trong thực tế, như cầu sắp xếp một danh sách theo thứ tự tăng hoặc giảm dần xuất hiện ở khắp mọi nơi.

Bài toán sắp xếp tăng dần có thể được phát biểu một cách đơn giản như sau:

Cho một dãy A có n phần tử A[0], A[1],..., A[n]. Hãy sắp xếp dãy A theo thứ tự tăng dần nghĩa là:

A[0] <= A[1] <= A[2]<=...<=A[n].

Có rất nhiều thuật toán để sắp xếp một dãy A theo yêu cầu như trên, trong phạm vi chủ đề này, chúng ta chỉ phân tích các thuật toán sắp xếp cơ bản.

Sắp xếp nổi bọt (Bubble Sort)

Lấy ý tưởng từ hình ảnh bóng khí nổi lên mặt nước. Thuật toán lặp đi lặp lại việc duyệt qua dãy và so sánh cặp phần tử liền kề, nếu chúng không đúng thứ tự thì thực hiện đổi chỗ chúng. Sau mỗi lượt duyệt, giá trị lớn nhất (hoặc nhỏ nhất) sẽ nằm ra cuối dãy. Thực hiện lặp lại các lượt trên, ta thu được dãy đã sắp xếp.

Chi tiết về ý tương, mã giả và giải thuật, các em có thể xem tại đây.

Sắp xếp chèn (Insertion Sort)

Ý tưởng thuật toán là ta 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 được sắp xếp là các phần tử ở phía trước vị trí đang duyệt.

Chi tiết về ý tưởng, mã giả và giải thuật, các em xem tại đây.

Sắp xếp chọn (Selection Sort)

Ý tưởng thuật toán là tìm phần tử nhỏ nhất trong dãy chưa sắp xếp và hoán đổi phần tử này với phần tử đầu tiên. Lặp lại quá trình này cho các phần tử tiêp theo đến khi toàn bộ mảng được sắp xếp.

Chi tiết về ý tưởng, giải thuật, mã giả và cài đặt các em xem chi tiết tại đây.

Nhiệm vụ 6. Thực hiện trắc nghiệm 11-CS-Tìm kiếm sắp 1