Cong ty Cong Nghe Tin hoc Nha truong http://www.vnschool.net
Mô hình Mẫu đề kiểm tra (Test Template) trong phần mềm iQB (tiếp theo)
11/04/2010

Bùi Việt Hà, Công ty Công nghệ Tin học Nhà trường

IV. Bài toán kiểm tra khả năng sinh đề từ mẫu đề tỷ lệ phạm vi kiến thức

Trong mô hình phần mềm iQB, các đề kiểm tra được tạo ra từ CSDL ngân hàng câu hỏi từ dữ liệu ban đầu là một mẫu đề kiểm tra theo Sơ đồ test hoặc theo Bảng tỷ lệ phạm vi kiến thức. Bài toán đặt ra là cho trước một mẫu đề kiểm tra, hay đúng hơn là cho trước một Sơ đồ Test hoặc Bảng tỷ lệ phạm vi kiến thức, hãy kiểm tra xem từ các dữ liệu ban đầu này có tạo ra được một đề kiểm tra cụ thể hay không thỏa mãn các điều kiện ràng buộc này.


Bài viết này sẽ đi sâu vào bài toán kiểm tra khả năng sinh đề kiểm tra từ mẫu đề tỷ lệ phạm vi kiến thức cho trước. Trước tiên chúng ta cùng tìm hiểu lại mô hình mẫu đề kiểm tra theo tỷ lệ phạm vi kiến thức trong phần mềm iQB.

1. Mô hình mẫu đề kiểm tra kiểu Tỷ lệ phạm vi kiến thức

Trong phần mềm iQB, mô hình mẫu đề kiểm tra theo Tỷ lệ phạm vi kiến thức được cho bởi 2 màn hình sau:

- Màn hình thứ nhất bao gồm các thông tin về số lượng câu hỏi và phân bổ số lượng này theo thuộc tính câu hỏi như tự luận/ trắc nghiệm, lý thuyết/bài tập, ngắn/dài.

Cửa sổ nhập các thông tin này có dạng như hình dưới đây:

- Màn hình thứ 2 là nhập tỷ lệ phần trăm kiến thức theo các phạm vi kiến thức có trong CSDL ngân hàng câu hỏi.

Cửa sổ nhập các thông tin này có dạng như hình dưới đây:

Giả sử bảng tỷ lệ phần trăm kiến thức của mẫu đề kiểm tra được cho trong bảng sau:

Từ bảng trên dễ dàng tính ra được số câu hỏi cụ thể tương ứng với phạm vi kiến thức (i) mà đề kiểm tra cần có là Pi.

Do vậy ta sẽ có phân bổ số lượng câu hỏi cho các phạm vi kiến thức khác nhau là:

N = P1 + P2 + ... + Ps

Bài toán kiểm tra khả năng sinh đề kiểm tra có thể phát biểu như sau:

Cho trước các thông số ban đầu của một mẫu đề kiểm tra theo bảng tỷ lệ phạm vi kiến thức như trên, có thể kiểm chứng và chứng minh được hay không rằng chắc chắn sẽ tồn tại một cách chọn câu hỏi từ CSDL ngân hàng câu hỏi thỏa mãn tất cả các điều kiện đã cho? Nếu chứng minh được sự tồn tại thì phải chỉ ra được một cách (hay thuật toán) để thực hiện được từng bước cách thiết lập đó.

Như vậy bài toán có thể được tách làm 2 câu hỏi riêng biệt:

1. Có tồn tại hay không một lời giải của bài toán.

2. Chỉ ra một thuật toán cụ thể để dẫn đến việc tìm ra nghiệm nếu tồn tại lời giải của câu hỏi 1.

Trong bài viết này chúng ta sẽ cùng nhau giải quyết bài toán 1.

2. Mô tả chính xác bài toán

2.1. Các thông số gốc của bài toán

Các thông số gốc ban đầu của mẫu đề kiểm tra theo tỷ lệ kiến thức:

2.2. Diễn giải chi tiết bài toán gốc

Vì các cặp thuộc tính câu hỏi tự luận / trắc nghiệm, lý thuyết / bài tập, ngắn / dài của câu hỏi là độc lập với nhau nên bài toán gốc với các thông số ban đầu sẽ được tách ra thành 3 bài toán con sau, tương ứng với 3 bộ, cặp thuộc tính khác nhau của câu hỏi:

(T1) tự luận / trắc nghiệm.

(T2) ngắn / dài.

(T3) lý thuyết / bài tập.

Bài toán gốc sẽ phân rã thành 03 bài toán con sau:



Ba bài toán trên có thực sự độc lập với nhau hay không? Chúng ta sẽ được biết trong phần cuối của bài viết này rằng 3 bài toán trên (T1 - T2 - T3) hoàn toàn độc lập với nhau. Do đó việc kiểm tra sự tồn tại của đề kiểm tra tương đương với việc chứng minh sự tồn tại nghiệm của cả 3 bài toán trên. 3 bài toán trên là hoàn toàn tương tự nhau về toán học, chúng ta sẽ tập trung phân tích và quan sát kỹ bài toán (T1), các bài toán còn lại (T2), (T3) sẽ được làm hoàn toàn tương tự.

2.3. Diễn giải chi tiết bài toán (T1)

Giả sử N = m + tphân bổ số lượng câu hỏi của đề kiểm tra thành câu hỏi trắc nghiệm và tự luận.

N = p1+ p2 + ... + ps phân bổ câu hỏi theo các phạm vi kiến thức 1, 2, ..., S.

Ta sẽ phân bổ từng loại câu hỏi pi theo trắc nghiệm / tự luận như sau:

pi= pim + pit, trong đó pimlà số lượng câu hỏi trắc nghiệm tương ứng phạm vi kiến thức (i) và pit là số lượng câu hỏi tự luận tương ứng phạm vi kiến thức (i).

Ta thu được hệ phương trình sau:

Đồng thời các số pimpitphải thỏa mãn các đẳng thức sau:

Bài toán (T1) có thể diễn giải như sau:

Với mỗi phạm vi kiến thức (i), cần tìm ra pim câu hỏi trắc nghiệm và pit câu hỏi tự luận sao cho thỏa mãn các phương trình (1) và (2).

Giả sử trong CSDL câu hỏi hiện thời, phạm vi kiến thức (i) có Ki câu hỏi, trong đó có mi câu trắc nghiệm và ti câu hỏi tự luận. Ta sẽ có đẳng thức:

Ki= mi + ti

Diễn giải chi tiết cho toàn bộ các phạm vi kiến thức tham gia trong đề kiểm tra ta có đẳng thức sau:


Trong (3), hàng số cuối cùng là tổng của các cột tương ứng.

Bây giờ hệ phương trình (1) có thể viết lại thành:

Do vậy bài toán (T1) bây giờ có thể được cho bởi các hệ phương trình (6) và (2).

Ta sẽ cùng nhau xem xét sơ bộ các điều kiện của bài toán (T1).

Kilà tổng số câu hỏi thuộc phạm vi kiến thức (i) của CSDL Ngân hàng câu hỏi nên bắt buộc số câu hỏi piphải thỏa mãn điều kiện: pi ≤ Ki.

Vậy ta có điều kiện ràng buộc sau:

(7) p1≤ K1, p2K2, ..., ps ≤ Ks

Mặt khác, tổng số câu hỏi trắc nghiệm m và tự luận tcủa đề kiểm tra phải nhỏ hơn các giá trị mT, tTnên ta suy ra điều kiện sau:

(8) m ≤ mT, t ≤ tT

Các điều kiện ràng buộc (7) và (8) có phải là điều kiện cần và đủ để tồn tại nghiệm của bài toán (T1) hay chưa?

Câu trả lời là chưa đủ.

Trong phần tiếp theo chúng ta sẽ cùng nhau giải quyết triệt để bài toán (T1).

3. Điều kiện cần và đủ tồn tại nghiệm của bài toán (T1)

Lời giải của bài toán (T1) được phát biểu bởi định lý sau:

Định lý:

Điều kiện cần và đủ để bài toán (T1) tồn tại nghiệm là các tham số của bài toán phải thỏa mãn tất cả các điều kiện ràng buộc sau:

Dễ dàng nhận thấy điều kiện ràng buộc (8) có thể suy ra từ điều kiện (9).

Trong phần tiếp theo của bài viết này chúng ta sẽ chứng minh định lý quan trọng trên.

4. Chứng minh định lý cơ bản

Ta sẽ chứng minh tồn tại các nghiệm thỏa mãn hệ phương trình (6) và điều kiện (2).

Việc chứng minh định lý trên được tiến hành theo hai bước sau:

Bước 1.Với mọi i = 1, 2, ..., s, xác định các giá trị pimpit thỏa mãn:

pi= pim + pit

pim≤ mi, pit ≤ ti.

Các giá trị pimpit có thể tìm và xác định như sau:

Lấy giá trị pitngẫu nhiên trong khoảng sau:

(11) max(0, pi- mi) ≤ pit ≤ min(ti, pi)

Để tồn tại pit thỏa mãn bất đẳng thức (11) ta cần chứng minh:

max(0, pi- mi) ≤ min(ti, pi)

Bất đẳng thức trên tương đương với điều kiện pi ≤ mi + ti= Ki. Đây chính là điều kiện (7).

Từ (11) suy ra:

pim= pi - pit ≤ pi - max(0, pi - mi) ≤ pi - (pi - mi) = mi.

Vậy pimpit thỏa mãn điều kiện của bước 1.

Bước 2.Đặt:

pm= p1m + p2m + ... + psm

pt= p1t + p2t + ... + pst

Nếu pm= mpt = tthì các bộ số (pim, pit)đã thỏa mãn hệ phương trình (6), (2) và đó chính là nghiệm của bài toán (T1).

Xét các trường hợp pm ≠ m hoặc pt ≠ t.

Khi đó ta sẽ chứng minh rằng có thể thay đổi các bộ số (pim, pit)sao cho cuối cùng sẽ đạt được đẳng thức pm = mpt = t.

Ta xét kỹ trường hợp pm, trường hợp ptsẽ thực hiện hoàn toàn tương tự.

Xét trường hợp pm < m.

Ta sẽ xây dựng thuật toán điều chỉnh thích hợp cho pm tăng dần cho đến khi = m và chứng minh rằng thuật toán này luôn hội tụ.

Thuật toán như sau:

while (pm < m) do

{

Tìm phần tử i tiếp theo sao cho đồng thời thỏa mãn pim < mivà pit > 0.

Nếu tìm thấy thì:

tăng pim, giảm pit 1 đơn vị.

tính lại các tổng pm, pt.

}

Chứng minh sự hội tụ của thuật toán trên:

Giả sử thuật toán trên không hội tụ, nghĩa là đến một lúc nào đó sẽ không thể tìm thấy i thỏa mãn điều kiện và khi đó vòng lặp while sẽ chạy vô hạn và pm sẽ luôn luôn nhỏ hơn m.

Khi đó ta sẽ phải có:

Với mọi i, hoặc pim = mi hoặc pit= 0

Điều này tương đương với việc với mọi i, các câu hỏi trắc nghiệm đã được chọn hết và không thể tăng lên được nữa. Dễ thấy rằng với mỗi phạm vi kiến thức (i), số lượng câu hỏi trắc nghiệm có thể chọn tối đa cho mẫu đề kiểm tra là min(pi, mi).

Do tổng tất cả các giá trị này = pm < m nên ta sẽ có bất đẳng thức sau:

min(p1, m1) + min(p2, m2) + ... + min(ps, ms) < m

điều này mâu thuẫn với bất đẳng thức đầu tiên của điều kiện (9).

Xét trường hợp pm > m.

Ta sẽ xây dựng thuật toán điều chỉnh thích hợp cho pmgiảm dần cho đến khi = m và chứng minh rằng thuật toán này luôn hội tụ.

Thuật toán như sau:

while (pm > m) do

{

Tìm phần tử i tiếp theo sao cho đồng thời thỏa mãn pit < tivà pim > 0.

Nếu tìm thấy thì:

tăng pit, giảm pim 1 đơn vị.

tính lại các tổng pm, pt.

}

Chứng minh sự hội tụ của thuật toán trên:

Giả sử thuật toán trên không hội tụ, nghĩa là đến một lúc nào đó sẽ không thể tìm thấy i thỏa mãn điều kiện và khi đó vòng lặp while sẽ chạy vô hạn và pm sẽ luôn luôn lớn hơn m.

Khi đó ta sẽ phải có:

Với mọi i, hoặc pit = ti hoặc pim= 0

Điều này tương đương với việc với mọi i, các câu hỏi trắc nghiệm đã được chọn là minimum và không thể giảm bớt được nữa. Dễ thấy rằng với mỗi phạm vi kiến thức (i), số lượng câu hỏi trắc nghiệm có thể chọn minimum đa cho mẫu đề kiểm tra là max(0, pi- ti).

Do tổng tất cả các giá trị này = pm > m nên ta sẽ có bất đẳng thức sau:

max(0, p1- m1) + max(p2 - m2) + ... + max(ps- ms) > m

điều này mâu thuẫn với bất đẳng thức đầu tiên của điều kiện (10).

Trường hợp pt< t hoặc pt > tđược xét và chứng minh hoàn toàn tương tự trên.

Vậy định lý cơ bản về điều kiện tồn tại nghiệm của bài toán (T1) đã được chứng minh.

5. Diễn giải và phát biểu các điều kiện tồn tại nghiệm cho bài toán (T2) và (T3)

Bài toán tổng quát kiểm tra sinh đề kiểm tra theo tỷ lệ phạm vi kiến thức được tiến hành độc lập với các bài toán (T1), (T2) và (T3). Trên chúng ta đã phân tích kỹ bài toán (T1). Bây giờ ta sẽ mô tả chi tiết các bài toán (T2) và (T3) tương tự như đã làm đối với (T1).

Diễn giải bài toán (T2)

Giả sử N = n + dphân bổ số lượng câu hỏi của đề kiểm tra thành câu hỏi ngắn và dài (phức hợp).

N = p1+ p2 + ... + ps phân bổ câu hỏi theo các phạm vi kiến thức 1, 2, ..., S.

Ta sẽ phân bổ từng loại câu hỏi pi theo ngắn / dài như sau:

pi= pin + pid, trong đó pinlà số lượng câu hỏi ngắn tương ứng phạm vi kiến thức (i) và pid là số lượng câu hỏi dài tương ứng phạm vi kiến thức (i).

Ta thu được hệ phương trình sau:


Đồng thời các số pinpidphải thỏa mãn các đẳng thức sau:

Giả sử trong CSDL câu hỏi hiện thời, phạm vi kiến thức (i) có Ki câu hỏi, trong đó có ni câu ngắn và di câu hỏi dài. Ta sẽ có đẳng thức:

Ki= ni + di

Diễn giải chi tiết cho toàn bộ các phạm vi kiến thức tham gia trong đề kiểm tra ta có đẳng thức sau:

Trong (14), hàng số cuối cùng là tổng của các cột tương ứng.

Bây giờ hệ phương trình (12) có thể viết lại thành:

Điều kiện cần và đủ để bài toán (T2) tồn tại nghiệm là các tham số của bài toán phải thỏa mãn tất cả các điều kiện ràng buộc sau:

(18) p1≤ K1, p2K2, ..., ps ≤ Ks

(19) n ≤ nT, d ≤ dT

Diễn giải bài toán (T3)

Giả sử N = l + bphân bổ số lượng câu hỏi của đề kiểm tra thành câu hỏi lý thuyết và bài tập.

N = p1+ p2 + ... + ps phân bổ câu hỏi theo các phạm vi kiến thức 1, 2, ..., S.

Ta sẽ phân bổ từng loại câu hỏi pi theo lý thuyết / bài tập như sau:

pi= pil + pib, trong đó pillà số lượng câu hỏi lý thuyếttương ứng phạm vi kiến thức (i) và pib là số lượng câu hỏi bài tập tương ứng phạm vi kiến thức (i).

Ta thu được hệ phương trình sau:


Đồng thời các số pilpibphải thỏa mãn các đẳng thức sau:

Giả sử trong CSDL câu hỏi hiện thời, phạm vi kiến thức (i) có Ki câu hỏi, trong đó có li câu hỏi lý thuyết và bi câu hỏi bài tập. Ta sẽ có đẳng thức:

Ki= li + bi

Diễn giải chi tiết cho toàn bộ các phạm vi kiến thức tham gia trong đề kiểm tra ta có đẳng thức sau:

Trong (24), hàng số cuối cùng là tổng của các cột tương ứng.


Bây giờ hệ phương trình (22) có thể viết lại thành:

Điều kiện cần và đủ để bài toán (T3) tồn tại nghiệm là các tham số của bài toán phải thỏa mãn tất cả các điều kiện ràng buộc sau:

6. Điều kiện tồn tại đề kiểm tra theo mẫu đề kiểm tra theo bảng tỷ lệ phạm vi kiến thức

Bây giờ chúng ta sẽ phát biểu lại chính thức lời giải cuối cùng cho bài toán kiểm tra điều kiện sinh đề kiểm tra với mẫu theo bảng tỷ lệ phạm vi kiến thức đã được phát biểu ngay từ đầu bài viết này.

Các điều kiện ban đầu

N = số lượng câu hỏi của đề kiểm tra.

N = m + t = n + d = l + b phân bổ số lượng câu hỏi theo trắc nghiệm / tự luận, ngắn / dài, lý thuyết / bài tập.

N = p1 + p2+ ... + pS phân bổ các câu hỏi theo từng chủ đề kiến thức (1), (2), ..., (S).

K1, K2, ...., KS - tổng số câu hỏi tương ứng có trong phạm vi kiến thức (1), (2), ..., (S).

Ki = mi+ ti = ni + di = li + bi- phân bổ câu hỏi của phạm vi kiến thức (i), i = 1, 2, ..., S theo trắc nghiệm / tự luận, ngắn / dài, lý thuyết / bài tập.

Định lý

Điều kiện cần và đủ để tồn tại đề kiểm tra thỏa mãn các ràng buộc trên là tất cả các bất đẳng thức sau phải thỏa mãn:
URL của bài viết này::http://www.vnschool.net/modules.php?name=Sanpham&file=article&sid=3841
© Cong ty Cong Nghe Tin hoc Nha truong contact: sales@schoolnet.vn