王 芳，蔡 沂

?

基于生成樹的學(xué)生互校驗簽到應(yīng)用研究

王 芳，蔡 沂

（華南理工大學(xué) 廣州學(xué)院計算機工程學(xué)院，廣東 廣州 510800）

文中提出了一種課堂簽到方案，主要思路是通過學(xué)生座位信息之間的相互校驗來驗證簽到的真實性。首先，文中描述了該簽到方案的工作流程；然后設(shè)計了基于生成樹的相互校驗算法；最后分析了該簽到方案的優(yōu)勢。分析和測試結(jié)果表明：該簽到方案能夠快速產(chǎn)生簽到結(jié)果、防止代簽、減少遲到早退；基于該方案的簽到系統(tǒng)實現(xiàn)簡單，具有很強的實用性和推廣價值。

簽到；生成樹；選座；相互校驗；考勤

0 引言

大學(xué)課堂簽到可以粗略地分為人工簽到和自動簽到兩類。人工簽到或點名不僅消耗了課堂時間，而且具有較大的局限性，遲到、早退、代簽等現(xiàn)象時有發(fā)生。隨著移動互聯(lián)網(wǎng)技術(shù)的發(fā)展，近年來涌現(xiàn)出大批手機簽到系統(tǒng)，如使用無線局域網(wǎng)和手機IMEI的簽到系統(tǒng)[1]、使用藍牙技術(shù)和二維碼技術(shù)的點名軟件[2]、基于微信公眾號的簽到[3]、基于WIFI的室內(nèi)定位簽到[4]、基于WIFI熱點和MAC地址的手機簽到[5-6]、基于GPS定位的簽到[7-8]等，但都存在無法精確判斷學(xué)生是否在教室內(nèi)、是否簽到后離開等問題。還有些方案依賴于特定的手機操作系統(tǒng)和網(wǎng)絡(luò)設(shè)備的支持，在學(xué)校推廣和普及的難度較大。

本文提出一種基于生成樹的學(xué)生互校驗簽到方案。該方案要求學(xué)生在規(guī)定時間內(nèi)提交自己的座位號，并且通過掃碼獲取前后左右的位置信息。系統(tǒng)通過課堂上所有簽到學(xué)生位置信息之間的相互校驗生成簽到座位表，簽到座位表直觀地展示了學(xué)生的入座情況，方便教師使用手機快速查看和操作。為縮短簽到位置信息的校驗時間，本文提出一種基于生成樹的相互校驗算法。最后，文章分析了基于本方案的課堂簽到系統(tǒng)的優(yōu)勢。

1 系統(tǒng)設(shè)計與功能描述

本文針對大學(xué)課堂準確并快速簽到設(shè)計一種簽到方案，能較大程度上避免學(xué)生抱著僥幸心理逃課、遲到、早退。主要包括學(xué)生選座、教師考勤、學(xué)生確認入座、系統(tǒng)校驗簽到信息、系統(tǒng)生成簽到座位表、教師管理考勤記錄等功能，所有操作都在手機上完成。圖1給出了此課堂簽到方案的工作流程圖。

圖1 系統(tǒng)工作流程

功能描述如下：（1）學(xué)生選座：學(xué)生選擇即將要上的課程，進入對應(yīng)教室座位表頁面選座；（2）開始考勤：教師選擇正在上的課程，進入對應(yīng)教室座位表頁面查看選座情況，可開始考勤；（3）學(xué)生確認入座：教師開始考勤后，教室座位表頁面顯示確認入座倒計時，學(xué)生通過掃碼提交前后左右同學(xué)的位置信息完成確認入座；（4）系統(tǒng)校驗簽到信息：確認入座倒計時結(jié)束，系統(tǒng)通過所有學(xué)生位置信息的相互校驗得出每個學(xué)生的簽到結(jié)果；（5）系統(tǒng)生成簽到座位表：系統(tǒng)根據(jù)簽到結(jié)果將簽到有效的學(xué)生姓名顯示在教室座位表上；（6）教師確認簽到座位表：教師查看簽到座位表，并可修改簽到座位表以應(yīng)對特殊情況；（7）結(jié)束考勤：教師點擊結(jié)束考勤按鈕表示完成本次課堂考勤，系統(tǒng)保存本次課堂考勤記錄；（8）管理考勤記錄：課后學(xué)生可查看自己的考勤記錄；教師可管理相關(guān)課程的考勤記錄，教師還可以登錄PC端后臺完成考勤記錄的統(tǒng)計、匯總和導(dǎo)出等。

2 互校驗簽到理論依據(jù)與算法設(shè)計

2.1 座位表與選座

大學(xué)教室座位一般為m*n型，m為座位行數(shù)，n為座位列數(shù)。作者所在的學(xué)校已存在教室座位表系統(tǒng)，可直接使用。每個座位的座位號按行號和列號來編排，i-j表示第i行第j列座位的座位號（1≤i≤m, 1≤j≤n)。圖2為一個8行8列教室座位示意圖。

圖2 教室座位表

Fig.2 Classroom seating chart

學(xué)生上課之前，根據(jù)課程信息進入相應(yīng)教室座位表頁面選座。圖3為某堂課選座座位表，灰色表示該座位已被某學(xué)生選中。

圖3 選座座位表

每個選座的學(xué)生都將產(chǎn)生一條如表1所示的選座記錄。表中省略了與課程相關(guān)的教室和上課時間等信息，本文暫不討論簽到記錄與課程相關(guān)信息的關(guān)聯(lián)。

2.2 確認入座與位置信息

上課后，教師可開始考勤，學(xué)生需要確認入座。

表1 選座記錄

Tab.1 Seat selection record

一次有效的簽到需要得到鄰座同學(xué)位置信息的證明，確認入座是為了讓學(xué)生提交其前后左右位置同學(xué)的信息（學(xué)生通過掃描鄰座同學(xué)的二維碼來提交其位置信息）。由于方向的相對性，當某學(xué)生的前方位置有人時，他把前方學(xué)生的信息填入自己的‘前位’中，同時他也將被前方位置的學(xué)生填入其‘后位’中；當某學(xué)生的左方位置有人時，他把左方學(xué)生的信息填入自己的‘左位’中，同時他也將被左方位置的學(xué)生填入其‘右位’中。左右位置與前后位置同理，不再累述。

系統(tǒng)可設(shè)置確認入座時間段，比如學(xué)生必須在教師開始考勤后的5分鐘內(nèi)完成確認入座操作。在確認入座時間段內(nèi)，已選座的學(xué)生還可以重新選座（換座）。學(xué)生要確保自己前后左右至少有一個位置有學(xué)生坐，這樣才能被他人填入位置信息中，才能使自己得到校驗。學(xué)生在確認入座時填寫位置信息后將產(chǎn)生一條如表2所示的位置信息記錄。

表2 某學(xué)生的位置信息記錄

Tab.2 A student's location information record

表2為學(xué)生‘周圍’的位置信息記錄。根據(jù)表2以及前后左右座位的特點，可以由學(xué)生‘周圍’確認入座的位置信息得到表3所示的座位對應(yīng)關(guān)系。

表3 由表2得出的學(xué)生座位對應(yīng)關(guān)系

Tab.3 The seat correspondence of students is obtained from table 2

用表3的座位對應(yīng)關(guān)系與表1的選座記錄進行對比，不僅校驗了學(xué)生‘周圍’的簽到記錄，同時也校驗了學(xué)生‘張倩’和‘李悠’。由此可知，并不需要所有的學(xué)生都提交前后左右的位置信息，有些學(xué)生是主動驗證，如學(xué)生‘周圍’；有些學(xué)生是被動驗證，如學(xué)生‘張倩’和‘李悠’。

接下來我們要討論的問題是：如何利用最少的位置信息驗證選座座位表中所有位置的簽到記錄。

2.3 位置信息的數(shù)學(xué)表示

2.3.1 無向圖

定義1 無向圖G=，其中：V是非空集合，稱為頂點集；E是V中元素構(gòu)成的無序二元組的集合，稱為邊集[9]。

若將選擇座位號i-j的學(xué)生看成頂點vi, j，圖3的選座座位表可轉(zhuǎn)化為圖4。

圖4 頂點化的選座座位表

若用座位前后左右的相鄰關(guān)系表示邊，則可能與頂點vi, j有關(guān)的邊為(vi–1, j, vi, j)、(vi, j, vi+1, j)、(vi, j–1, vi, j)、(vi, j, vi, j+1)，其中1≤i–1, i, i+1≤m，1≤j–1, j, j+1≤n。因此，圖4的選座座位表可表示成一個非連通的無向圖G，G有3個連通分量：G1、G2、G3，如圖5。

由此可得，所有的選座座位表都可以表示成類似圖5的無向圖，連通分量的個數(shù)大于等于1。又因為每個學(xué)生的前后左右至少有一個位置有同學(xué)坐，所以每個連通分量至少包含2個頂點。

2.3.2 生成樹

引理1 如果連通圖 G的一個子圖是一棵包含G的所有頂點的樹，則該子圖稱為G的生成樹（Spanning Tree）。生成樹是連通圖的包含圖中的所有頂點的極小連通子圖[10]。

引理2 若G是非連通的無向圖，則要若干次從外部調(diào)用DFS（Depth First Search深度優(yōu)先搜索）或BFS（Breadth First Search 廣度優(yōu)先搜索）算法，才能完成對G的遍歷。每一次外部調(diào)用，只能訪問到G的一個連通分量的頂點集，這些頂點和遍歷時所經(jīng)過的邊構(gòu)成了該連通分量的一棵DFS或BPS生成樹。G的各個連通分量的DFS或BFS生成樹組成了G的DFS或BFS生成森林[10-11]。

圖5 無向圖G，連通分量G1、G2、G3

由引理1和引理2可知，對于由選座座位表轉(zhuǎn)換成的無向圖G，通過對G的遍歷找到G的每個連通分量的生成樹，就找到了每個連通分量中連接所有頂點的最短連通路徑。

圖的生成樹不惟一。從不同的頂點出發(fā)進行遍歷，可以得到不同的生成樹。[11]對于圖5中無向圖G的連通分量G3，若從頂點v6,1出發(fā)進行遍歷，圖6為G3的一棵生成樹，v6,1為樹的根節(jié)點。

對于圖5生成樹中的節(jié)點，只要父節(jié)點位置所代表的學(xué)生提交其子節(jié)點位置的學(xué)生信息，就可以完成對圖中8個節(jié)點位置所代表的學(xué)生簽到信息的校驗。

2.4 位置信息的收集

根據(jù)生成樹中節(jié)點之間的父子關(guān)系和節(jié)點本身的位置關(guān)系，系統(tǒng)向每個選座的學(xué)生發(fā)送收集位置信息的指令。由圖6和表4，座位號6-1的學(xué)生接收到的指令為“請?zhí)峤缓蠓胶陀曳酵瑢W(xué)信息”，座位號6-2的學(xué)生接收到的指令為“請?zhí)峤磺胺胶陀曳酵瑢W(xué)信息，并將你的信息提供給左方同學(xué)”，座位號8-2的學(xué)生接收到的指令為“請將你的信息提供給左方同學(xué)”，諸如此類。根據(jù)指令收集到的位置信息如表5所示。

圖6 連通分量G3的生成樹

表4 圖6樹的父子節(jié)點關(guān)系

Tab.4 The parent-child relationship of the tree in figure 6

表5 收集的位置信息

Tab.5 Collected location information

如果選座座位號為5-2的學(xué)生沒來，那么他將不會出現(xiàn)在座位號為6-2的學(xué)生的前方位置信息中。

如果選座座位號為8-2的學(xué)生沒來，那么他將不會出現(xiàn)在座位號為8-1的學(xué)生的右方位置信息中。而座位號為8-1的學(xué)生收到了“請?zhí)峤挥曳綄W(xué)生信息”的指令卻無信息可填，此時8-1的學(xué)生應(yīng)填寫有人坐的一個方向的同學(xué)信息來證明自己的存在（因為每個學(xué)生的前后左右至少有一個位置有同學(xué)坐，這是學(xué)生確認入座的必要條件）。座位號8-1的學(xué)生應(yīng)提交補充信息“前方同學(xué)的信息：XXX”。

如果選座座位號為7-1的學(xué)生沒來，那么他將不會出現(xiàn)在座位號為6-1的學(xué)生的前方位置信息中。而座位號為7-2的學(xué)生收到了“請將你的信息提供給左方同學(xué)”的指令，當他發(fā)現(xiàn)自己的信息無法被填入時（左方位置7-1無人），應(yīng)填寫有人坐的一個方向的學(xué)生信息來證明自己的存在。座位號7-2的學(xué)生應(yīng)提交補充信息“前方同學(xué)的信息：XXX”或“后方同學(xué)的信息：XXX”。

由此可知，對于由選座座位表轉(zhuǎn)換成的無向圖G的生成森林，只要生成樹中每個父節(jié)點位置所代表的學(xué)生填寫其子節(jié)點位置的學(xué)生信息，且當有節(jié)點發(fā)現(xiàn)自己的信息無法被填入并且也沒有接收到填入他人信息的指令時能填寫補充信息來證明自己，就能收集到足夠的位置信息與選座座位表進行對比校驗，得出簽到結(jié)果。收集位置信息的過程即為獲取簽到記錄的過程，校驗位置信息的過程即為驗證簽到真實性的過程。

2.5 基于生成樹的互校驗簽到算法設(shè)計

為了獲得足夠的位置信息與選座座位表進行對比校驗，系統(tǒng)要向選座的學(xué)生發(fā)送收集位置信息的指令。要向哪些學(xué)生發(fā)送指令？分別給他們發(fā)送什么樣的指令呢？這兩個問題才是獲取位置信息的關(guān)鍵所在。

算法1 基于生成樹的互校驗簽到算法。

第1步：根據(jù)選座座位表生成無向圖G

第2步：調(diào)用DFS（或BFS）算法遍歷無向圖G，生成森林

第3步：對生成森林中的每棵生成樹，根據(jù)樹的生成路徑，調(diào)用generateOrders算法（見算法2）生成要發(fā)送給每個節(jié)點的指令

第4步：向每個節(jié)點表示的學(xué)生發(fā)送對應(yīng)的指令

第5步：獲取學(xué)生根據(jù)指令提交的位置信息

第6步：將位置信息與選座座位表進行對比，生成簽到座位表

算法1第3步中對每棵生成樹調(diào)用名為gen-erate-Orders的算法：數(shù)組nodeArr[]用于存儲其生成路徑的節(jié)點信息，是算法1第2步的輸出；哈希表orderMap用于存儲節(jié)點與應(yīng)發(fā)送給節(jié)點的指令列表的鍵值對，初始情況下所有節(jié)點對應(yīng)的指令列表都為空。

算法2generateOrders生成指令算法。

for each fnode in nodeArr[]

for each snode in sonArr[]

orderList_of_fnode.add(orderStr_of_fnode), orderList_of_snode.add(orderStr_of_snode)//將前面構(gòu)造的指令字符串添加到對應(yīng)的指令列表中

orderMap.set(fnode, orderList_of_fnode), o-r---d-er-Map.set(snode, orderList_of_snode)//分別更新orderMap中key為fnode和snode的value

end for

end for

通過調(diào)用算法2，哈希表orderMap中存儲了要向node節(jié)點所表示的學(xué)生發(fā)送指令列表orderList。

3 系統(tǒng)分析與實現(xiàn)

3.1 算法時間復(fù)雜度

算法1第2步，調(diào)用DFS和BFS算法遍歷無向圖G，若用鄰接矩陣來實現(xiàn)，時間復(fù)雜度均為O(n2)，其中n為頂點數(shù)。

算法1第3步，對每棵生成樹調(diào)用算法2。因為每棵生成樹至少有2個節(jié)點，所以生成樹的數(shù)量一定小于n/2。而算法2中，因為每個節(jié)點最多有4個子節(jié)點，所以時間復(fù)雜度為O(n*4)。因此，算法1第3步的時間復(fù)雜度為O(n*4*n/2)=O(n2)。

算法1第6步，將位置信息與選座座位表進行對比，時間復(fù)雜度也為O(n2)。

因為算法1的時間復(fù)雜度集中體現(xiàn)在第2步、第3步和第6步，所以基于生成樹的互校驗簽到算法的時間復(fù)雜度為O(n2)[11]。

n為頂點數(shù)，即為一堂課上的學(xué)生數(shù)量。大學(xué)課堂一般為兩個行政班合并為一個教學(xué)班，人數(shù)在120人左右，對于時間復(fù)雜度為O(n2)的算法都能很快執(zhí)行完畢。算法1第4步為發(fā)送指令，第5步為表單提交，系統(tǒng)可設(shè)置學(xué)生必須在發(fā)送指令后的5分鐘內(nèi)完成確認入座。

3.2 實現(xiàn)確認入座

為了防止簽到作弊，教師開始考勤后，系統(tǒng)給每個選座的學(xué)生生成限本次考勤使用的二維碼，并設(shè)置有效時間，學(xué)生通過掃描二維碼來獲取指令中要求提供的鄰座同學(xué)的位置信息。如座位號6-1的學(xué)生接收到的指令為“請輸入后方和右方同學(xué)信息”，表示他要掃描后方和右方位置同學(xué)的二維碼；座位號6-2的學(xué)生接收到的指令為“請輸入前方和右方同學(xué)信息，并將你的信息提供給左方同學(xué)”，表示他要掃描前方和右方位置同學(xué)的二維碼，并將自己的二維碼提供給左方位置的同學(xué)掃描。

3.3 獲得簽到座位表

將學(xué)生在確認入座時間段內(nèi)提交的位置信息與選座座位表進行對比校驗，可得出簽到座位表如 圖7。

圖7 簽到座位表

教師可查看并修改簽到座位表，以應(yīng)對特殊情況的出現(xiàn)。如有學(xué)生忘帶手機，教師可幫學(xué)生簽到。當教師認為不再需要修改簽到座位表時，可確認簽到座位表以完成本次考勤。

3.4 非正常簽到分析

開始考勤后，系統(tǒng)向選座的學(xué)生發(fā)送收集位置信息的指令，學(xué)生根據(jù)指令提交位置信息以確認入座，學(xué)生必須在規(guī)定時間段完成確認入座。教師可自主選擇考勤的時間，遲到或早退的學(xué)生很可能不能按時完成確認入座，也就無法簽到成功。

系統(tǒng)根據(jù)選座記錄和確認入座記錄快速生成簽到結(jié)果，教師可以實時查看簽到座位表。教師在確認簽到座位表之前可以修改簽到座位表，如教師在上課過程中發(fā)現(xiàn)有位置完成簽到卻無人，可判斷為早退，可點擊相應(yīng)座位取消其簽到或修改成早退狀態(tài)。

4 結(jié)語

本文提出基于生成樹的學(xué)生互校驗簽到方案，利用學(xué)生之間的位置信息進行相互校驗，不但提高了簽到的效率，而且保證了簽到的真實性?；谠摲桨傅暮灥较到y(tǒng)不依賴除手機之外的其他設(shè)備、不限于某種手機操作系統(tǒng)。系統(tǒng)全部采用web實現(xiàn)，使它能快速集成到如微信、智慧校園、課程表等其他學(xué)生廣泛使用的應(yīng)用系統(tǒng)或平臺中，具有很強的實用性和推廣價值。

簽到的前提是選座，類似于電影院選座。對于一些有較多學(xué)生感興趣、教師授課方式生動的課程，可能會出現(xiàn)“前排搶座”現(xiàn)象，在線選座也達到了在線搶座的目的。從心理學(xué)的角度來說，選座（搶座）行為可以提高學(xué)生上課的積極性。[12]

簽到活動的第二步是確認入座，由教師主動發(fā)起。教師可根據(jù)實際情況決定是否對本堂課考勤，開始考勤才會有確認入座流程。簽到活動由學(xué)生通過互動完成，確認入座增強了學(xué)生簽到的主動性，是一種積極的心理暗示。

大學(xué)課堂的座位選擇與教學(xué)情況緊密相關(guān)。教師預(yù)覽系統(tǒng)生成的簽到座位表，可以加深教師對學(xué)生的了解，使教師更好地把握課堂教學(xué)。系統(tǒng)將累計產(chǎn)生大量選座數(shù)據(jù)，這些數(shù)據(jù)不但可以用來分析學(xué)生上課時的座位分布對學(xué)生成績的影響[13]，而且可以分析教師的授課形式和授課質(zhì)量對學(xué)生學(xué)習(xí)積極性的影響。分析學(xué)生上課時的座位分布對學(xué)生成績的影響，讓老師更加了解學(xué)生，對成績不好的學(xué)生進行勸導(dǎo)；分析教師的授課形式和授課質(zhì)量對學(xué)生學(xué)習(xí)積極性的影響，讓老師對自己的教學(xué)方式和手段進行反思，推動教學(xué)改革。[14]

[1] 劉冬梅, 任亞平, 周杰等. 基于Android的手機簽到系統(tǒng)[J]. 科技資訊, 2017, 14: 17-18.

[2] 陳三清, 殷鵬. 基于Android手機的課堂點名軟件設(shè)計與實現(xiàn)[J]. 電腦知識與技術(shù), 2017, 7, 95-99.

[3] 陳東偉, 譚建新, 溫家成等. 基于微信的考勤信息管理系統(tǒng)設(shè)計與實現(xiàn)[J]. 信息技術(shù), 2017, 5, 85-88.

[4] 蔣航, 蔡秋楓. 基于室內(nèi)定位的學(xué)生簽到系統(tǒng)設(shè)計[J]. 電腦知識與技術(shù), 2017, 1, 54-55.

[5] 趙靚, 張玉. 基于WIFI熱點的手機簽到系統(tǒng)設(shè)計[J]. 計算機編程技巧與維護, 2017, 6, 59-61.

[6] 肖俊生, 劉俊娟. 基于WI-FI的學(xué)生考勤系統(tǒng)研究與設(shè)計[J]. 工業(yè)控制計算機, 2017, 1, 114-115.

[7] 張勁波, 周澤崇, 李雅杰等. 基于Android的上課簽到軟件分析與設(shè)計[J]. 電腦編程技巧與維護, 2017, 2(3), 28.

[8] 徐寧. 基于微信平臺的并行簽到考勤管理系統(tǒng)[J]. 電腦知識與技術(shù), 2016, 30, 77-79.

[9] 耿素云, 屈婉玲, 張立昴. 離散數(shù)學(xué)[M]. 北京: 清華大學(xué)出版社, 2013.

[10] 李明哲等. 圖論及其算法[M]. 北京: 機械工業(yè)出版社, 2010.

[11] 嚴蔚敏, 吳偉民. 數(shù)據(jù)結(jié)構(gòu)(C語言版)[M]. 北京: 清華大學(xué)出版社, 2011.

[12] 王會廷, 張艷平, 閻慧. 大學(xué)生課堂行為的心理學(xué)研究[J]. 安徽工業(yè)大學(xué)學(xué)報: 社會科學(xué)版, 2012, 29(3): 37-38.

[13] 王映學(xué), 段寶軍, 張曉州. 大學(xué)課堂座位選擇與學(xué)業(yè)成績的關(guān)系研究[J]. 重慶高教研究, 2017, 5(3): 65-72.

[14] 程永佳. 大學(xué)課堂有效教學(xué)的影響因素及提高策略[J]. 教育與教學(xué)研究, 2012, 26(5): 22-25.

Research on Class Sign_in Application Based on Validation between Classmates using Spanning Tree

WANG Fang, CAI Yi

(Guangzhou College of South China University of Technology, Guangzhou 510800, Guangdong, China)

In this paper, we put forward a class sign-in solution which verify the authenticity of sign-in by the seat information of classmates. Firstly, the work flow of this solution is described; secondly, the mutual validation algorithm based on Spanning Tree is described; finally, the greatest strengths of our solution are analyzed. Analysis results and test results show that using our solution can produce accurate sign-in results, prevent cheating, reduce arrive late and leave early, and the class sign-in system based on our solution is simple and very practical and has strong promotional value.

Class sign-in; Spanning Tree; Seat selection; Mutual validation; Attendance

TP311

A

10.3969/j.issn.1003-6970.2018.07.002

廣東省高等學(xué)校特色專業(yè)建設(shè)項目(JY170102)

王芳(1986-)，女，助教，主要研究方向：軟件工程、大數(shù)據(jù)技術(shù)；蔡沂，(1978-)，女，副教授，主要研究方向：網(wǎng)絡(luò)工程、信息安全。

本文著錄格式：王芳，蔡沂. 基于生成樹的學(xué)生互校驗簽到應(yīng)用研究[J]. 軟件，2018，39（7）：06?-11