2025年大學(xué)《信息與計算科學(xué)》專業(yè)題庫——信息與計算科學(xué)專業(yè)實踐教學(xué)案例考試時間：______分鐘總分：______分姓名：______注意事項：1.請將所有答案寫在答題紙上，寫在試卷上無效。2.答案要求字跡工整、卷面整潔。3.考試時間：120分鐘。一、閱讀以下案例，并回答相關(guān)問題。某城市交通管理部門希望利用歷史交通流量數(shù)據(jù)優(yōu)化主要干道的信號燈配時方案，以減少平均等待時間，提高道路通行效率。數(shù)據(jù)表明，某主干道在高峰時段（7:00-9:00）的交通流量呈現(xiàn)明顯的潮汐現(xiàn)象，即東西向和南北向的流量差異很大。管理部門收集了連續(xù)一周該主干道在高峰時段每15分鐘記錄的車輛等待時間數(shù)據(jù)，并繪制了相應(yīng)的流量變化曲線。1.假設(shè)你需要設(shè)計一個算法，根據(jù)這些15分鐘間隔的數(shù)據(jù)點，估算高峰時段內(nèi)該主干道不同方向（東西向和南北向）的平均車輛等待時間。請描述你將采用的數(shù)據(jù)結(jié)構(gòu)來存儲這些數(shù)據(jù)，并簡述算法的主要步驟。2.在選擇了合適的數(shù)據(jù)結(jié)構(gòu)和算法后，你發(fā)現(xiàn)計算得到的平均等待時間與管理部門的直觀感受存在一定偏差，特別是在流量極低的時段，平均等待時間計算值依然偏高。請分析可能導(dǎo)致這種偏差的原因，并提出至少兩種改進(jìn)平均等待時間估算方法或參數(shù)調(diào)整策略。3.基于上述分析，如果你被要求設(shè)計一個簡單的信號燈配時調(diào)整策略，該策略能根據(jù)實時檢測到的交通流量（東西向和南北向的車輛排隊長度或等待車輛數(shù)）動態(tài)調(diào)整信號燈的綠燈時間。請?zhí)岢鲈摬呗缘幕究蚣芎秃诵倪壿嫛６?、考慮一個需要處理大規(guī)?？茖W(xué)計算數(shù)據(jù)的場景，數(shù)據(jù)以矩陣形式存儲，矩陣的大小約為MxN(M,N均大于1000)，矩陣元素包含浮點數(shù)。假設(shè)內(nèi)存資源有限，無法一次性將整個矩陣加載到內(nèi)存中進(jìn)行處理。請回答以下問題。1.若需要對矩陣中的每個元素進(jìn)行相同的標(biāo)量運算（例如，每個元素乘以一個常數(shù)C），且運算可以并行化，請描述一種可行的內(nèi)存高效且可并行處理的方法。2.假設(shè)需要計算該矩陣與其自身（即A*A）的乘積，結(jié)果存儲在矩陣B(大小為MxN)中。請描述一種適用于大規(guī)模稀疏矩陣（假設(shè)該矩陣A是稀疏的）且內(nèi)存高效的矩陣乘法算法的基本思路。說明需要考慮的關(guān)鍵點。3.對比上述兩種計算任務(wù)，分析它們在內(nèi)存使用和計算方式上的主要差異。三、某軟件開發(fā)團(tuán)隊正在開發(fā)一個在線社交平臺的推薦系統(tǒng)。該系統(tǒng)需要根據(jù)用戶的行為數(shù)據(jù)（如瀏覽、點贊、關(guān)注、分享等）為用戶推薦可能感興趣的內(nèi)容（如文章、視頻、用戶等）。請就以下問題進(jìn)行分析和闡述。1.推薦系統(tǒng)通常需要構(gòu)建用戶畫像來表示用戶的興趣偏好。請簡述一種基于用戶歷史行為數(shù)據(jù)構(gòu)建用戶畫像的方法，并說明該方法可能面臨的數(shù)據(jù)稀疏性和冷啟動問題。2.假設(shè)推薦系統(tǒng)需要考慮內(nèi)容的多樣性和新穎性，避免持續(xù)推薦相似內(nèi)容。請?zhí)岢鲋辽賰煞N能夠在推薦時融入多樣性和新穎性考慮的策略。3.用戶對推薦結(jié)果的反饋（如點擊、喜歡、忽略等）對于優(yōu)化推薦模型至關(guān)重要。請描述一種利用用戶反饋進(jìn)行在線學(xué)習(xí)或模型更新的基本機(jī)制，并說明該機(jī)制需要考慮的關(guān)鍵因素。四、在信息與計算科學(xué)領(lǐng)域，數(shù)值算法的精度和效率至關(guān)重要。請針對以下問題進(jìn)行分析。1.考慮求解線性方程組Ax=b，其中A是一個大型稀疏矩陣。請比較直接法（如高斯消元法）和迭代法（如雅可比法、高斯-賽德爾法）在適用性、收斂速度和內(nèi)存需求方面的主要差異。在什么情況下，迭代法可能比直接法更優(yōu)？2.在進(jìn)行數(shù)值積分時，如果被積函數(shù)在積分區(qū)間內(nèi)存在奇點或劇烈振蕩，使用傳統(tǒng)的數(shù)值積分方法（如梯形法則、辛普森法則）可能會得到非常不準(zhǔn)確的結(jié)果。請介紹一種能夠更好處理此類問題的數(shù)值積分方法，并簡述其基本原理。3.算法的穩(wěn)定性是數(shù)值計算中的一個重要概念。請解釋什么是算法的數(shù)值穩(wěn)定性，并舉例說明一個數(shù)值不穩(wěn)定的算法實例，簡要分析其不穩(wěn)定性可能帶來的問題。試卷答案一、1.數(shù)據(jù)結(jié)構(gòu)：可使用數(shù)組或列表存儲每個15分鐘間隔的數(shù)據(jù)點，每個數(shù)據(jù)點包含東西向和南北向的流量值和等待時間。例如，使用結(jié)構(gòu)體或字典存儲。對于整個時間段的數(shù)據(jù)，可以使用二維數(shù)組或列表的列表。算法步驟：a.遍歷存儲數(shù)據(jù)的數(shù)據(jù)結(jié)構(gòu)。b.分別累加?xùn)|西向和南北向的等待時間。c.分別計算東西向和南北向的總流量（例如，可使用流量曲線下的面積或15分鐘間隔的平均流量乘以時間間隔長度）。d.分別計算東西向和南北向的平均等待時間（總等待時間/總流量）。2.偏差原因分析及改進(jìn)方法：*原因：平均等待時間是所有時間段內(nèi)車輛等待時間的平均值，它不能反映交通流量的影響。在流量極低的時段，即使等待車輛少，但由于幾乎沒有車輛通過，計算出的平均等待時間（總等待時間/極低流量）仍然會偏高。平均等待時間未考慮流量對等待時間的影響。*改進(jìn)方法：*加權(quán)平均等待時間：使用流量作為權(quán)重計算加權(quán)平均等待時間。例如，計算每個15分鐘間隔的等待時間與流量的乘積，然后求和，再除以總流量（或流量加權(quán)和）。這更能反映高流量時段的等待狀況。*分段評估：將高峰時段劃分為流量高、中、低不同區(qū)間，分別計算各區(qū)間內(nèi)的平均等待時間，并進(jìn)行分析比較，而不是計算整個時段的單一平均值。3.動態(tài)信號燈配時策略框架與邏輯：*框架：實時監(jiān)測東西向和南北向的車輛排隊長度或等待車輛數(shù)（QueueLength或NumberofWaitingVehicles）。根據(jù)監(jiān)測到的實時數(shù)據(jù)，動態(tài)調(diào)整每個方向的綠燈時間。*核心邏輯：*設(shè)定基線綠燈時間（MinimumGreenTime）。*實時檢測東西向（Q_E）和南北向（Q_N）的排隊長度/等待車輛數(shù)。*調(diào)整邏輯：如果Q_E>Q_N，則適當(dāng)增加?xùn)|西向的綠燈時間（或減少南北向的綠燈時間/增加其紅燈時間），反之亦然。調(diào)整的幅度可以基于預(yù)設(shè)的規(guī)則（如排隊長度每增加一定數(shù)量，綠燈時間增加固定秒數(shù)）或更復(fù)雜的模型。*確保綠燈時間調(diào)整后，總周期時間保持相對穩(wěn)定（或按需調(diào)整周期時長）。需要考慮最小綠燈時間約束，避免綠燈時間過短。二、1.內(nèi)存高效并行標(biāo)量運算方法：*方法：采用分塊（Blocking）或分片（Stripping）策略，將大矩陣A分割成更小的子矩陣或子數(shù)組塊。每個處理單元（如CPU核心或線程）負(fù)責(zé)加載一個數(shù)據(jù)塊到局部內(nèi)存，對該塊內(nèi)的所有元素執(zhí)行標(biāo)量運算（乘以C），然后將結(jié)果寫回全局存儲。可以并行執(zhí)行。*原理：只需要將當(dāng)前處理的數(shù)據(jù)塊加載到內(nèi)存，大大降低了單次運算的內(nèi)存需求。并行化允許不同的處理單元同時處理不同的數(shù)據(jù)塊。2.大規(guī)模稀疏矩陣乘法算法思路：*基本思路：利用稀疏矩陣的非零結(jié)構(gòu)，僅對非零元素進(jìn)行計算和存儲。核心思想是將A*B的計算轉(zhuǎn)化為對A的非零元素及其索引和B的對應(yīng)行向量的操作。*步驟（以三重循環(huán)為例）：*對A的每一行i，其非零元素記為(i,j_k,a_ijk)(k=1,...,nnz_i，nnz_i為第i行的非零元素個數(shù))。*對于A的每一個非零元素a_ijk：*在B的第j_k列中找到所有非零元素(l,j_k,b_lj_k)(l=1,...,nnz_jk，nnz_jk為第j_k列的非零元素個數(shù))。*對每一個這樣的B的非零元素，計算累加項a_ijk*b_lj_k。*將計算得到的累加項加到C的第(i,l)位置上（即C[i][l]=C[i][l]+a_ijk*b_lj_k）。*關(guān)鍵點：*需要高效的稀疏矩陣存儲格式（如CompressedSparseRow,CSR）來表示A和B，以便快速定位非零元素及其索引。*算法的性能很大程度上取決于稀疏結(jié)構(gòu)的稀疏度和數(shù)據(jù)訪問模式。需要考慮數(shù)據(jù)局部性。3.計算任務(wù)差異分析：*標(biāo)量運算：主要是對矩陣的每個元素執(zhí)行簡單的算術(shù)運算。內(nèi)存需求低（只需加載當(dāng)前處理的小塊數(shù)據(jù)）。計算量與元素總數(shù)成正比。并行化相對簡單（塊級并行）。*矩陣乘法（稀疏）：計算涉及非零元素的匹配和累加。內(nèi)存需求主要取決于非零元素的數(shù)量和存儲結(jié)構(gòu)。計算量取決于非零元素的數(shù)量及其連接關(guān)系，通常比全矩陣乘法少。算法設(shè)計復(fù)雜，需要利用稀疏結(jié)構(gòu)，數(shù)據(jù)訪問模式不規(guī)則。并行化可能更復(fù)雜，需要考慮非零元素的稀疏連接。三、1.用戶畫像構(gòu)建方法及問題：*構(gòu)建方法（示例：基于協(xié)同過濾）：收集用戶對物品的行為數(shù)據(jù)（如評分、點擊、購買等）。計算用戶與用戶之間或用戶與物品之間的相似度。對于目標(biāo)用戶，找到與其最相似的其他用戶（用戶-用戶協(xié)同過濾）或物品（物品-物品協(xié)同過濾），將這些相似用戶的興趣（他們喜歡的物品）或相似物品的信息，作為目標(biāo)用戶的興趣表示?？梢允褂孟蛄浚ㄈ缥锲?用戶矩陣中的用戶行向量）來量化用戶的興趣偏好。*問題：*數(shù)據(jù)稀疏性：大多數(shù)用戶只與少量物品有交互，形成稀疏矩陣。這使得計算相似度變得困難，可能導(dǎo)致推薦結(jié)果不夠準(zhǔn)確或過于集中。*冷啟動問題：對于新用戶（沒有行為數(shù)據(jù)）或新物品（沒有用戶交互數(shù)據(jù)），難以構(gòu)建準(zhǔn)確的畫像，導(dǎo)致推薦效果不佳。新用戶面臨冷啟動，新物品也面臨冷啟動。2.推薦多樣性與新穎性策略：*策略一（基于多樣性度量）：在推薦列表中引入多樣性度量，如基于物品之間的相似度距離或主題分布的距離。在保證預(yù)測準(zhǔn)確性的前提下，優(yōu)先選擇與已推薦物品距離較遠(yuǎn)的物品，以增加推薦列表的多樣性。*策略二（基于探索與利用E&E）：在推薦時，除了利用用戶過去的偏好（利用）來推薦相似物品外，還按一定概率（如基于物品的新穎度、流行度或用戶對其的未交互程度）推薦一些用戶可能感興趣但與過去偏好不太相關(guān)的物品（探索），以發(fā)現(xiàn)用戶的潛在興趣和新穎內(nèi)容。3.用戶反饋在線學(xué)習(xí)機(jī)制：*基本機(jī)制：采用在線學(xué)習(xí)算法，如在線梯度下降（OnlineGradientDescent）或隨機(jī)梯度下降（StochasticGradientDescent,SGD）。當(dāng)用戶對推薦結(jié)果提供反饋（如點擊、喜歡、忽略、負(fù)面反饋等）時，立即使用該反饋信號來更新推薦模型（如用戶向量、物品向量、或模型參數(shù)）。*更新邏輯（示例：更新用戶/物品向量）：基于用戶u對物品i的反饋r（正值表示積極反饋，負(fù)值表示消極反饋），更新用戶特征向量pu和物品特征向量qi：pu=pu-learning_rate*?L(pu,qi,r)和qi=qi-learning_rate*?L(pu,qi,r)，其中L是模型的目標(biāo)函數(shù)（如交叉熵?fù)p失），learning_rate是學(xué)習(xí)率，?L是梯度。*關(guān)鍵因素：*反饋信號的質(zhì)量和及時性：反饋需要準(zhǔn)確反映用戶的真實偏好，且越及時越好。*學(xué)習(xí)率的選擇：合適的學(xué)習(xí)率能保證模型穩(wěn)定收斂，過小則收斂慢，過大則可能不穩(wěn)定。*模型的選擇：不同的在線學(xué)習(xí)算法適用于不同的模型和數(shù)據(jù)場景。*噪聲的處理：用戶反饋可能包含噪聲，需要設(shè)計魯棒的在線學(xué)習(xí)算法來減輕噪聲影響。四、1.直接法與迭代法比較：*適用性：直接法（如LU分解）適用于求解精度要求高、規(guī)模不是特別巨大的稠密矩陣方程組。迭代法（如雅可比、高斯-賽德爾）適用于稀疏矩陣方程組，尤其是具有良好譜性質(zhì)（如對角占優(yōu)、對稱正定）的矩陣，或者當(dāng)矩陣規(guī)模非常大時，內(nèi)存成本是主要限制因素。*收斂速度：直接法一旦求解成功，就能得到精確解（考慮浮點數(shù)精度）。迭代法的收斂速度取決于迭代矩陣的譜半徑或收斂因子，通常線性或超線性收斂，對于某些矩陣可能收斂很慢甚至不收斂。收斂速度與矩陣性質(zhì)和初始猜測值有關(guān)。*內(nèi)存需求：直接法通常需要存儲完整的系數(shù)矩陣（或其分解結(jié)果），內(nèi)存需求與矩陣大小MxN成正比。迭代法只需要存儲系數(shù)矩陣的非零元素（如果使用稀疏存儲）和當(dāng)前迭代向量，內(nèi)存需求通常遠(yuǎn)小于MxN，只與非零元素數(shù)量有關(guān)。*優(yōu)缺點：直接法計算效率高（對于可解問題），但準(zhǔn)備工作（如LU分解）可能耗時，且對大規(guī)模稀疏矩陣內(nèi)存需求大。迭代法內(nèi)存效率高，適合大規(guī)模稀疏問題，但可能需要更多迭代次數(shù)，總計算時間不確定，且對初始值和矩陣性質(zhì)敏感。*何時迭代法更優(yōu)：當(dāng)矩陣是大規(guī)模稀疏矩陣，且其性質(zhì)有利于迭代法收斂時；當(dāng)內(nèi)存資源非常有限，無法使用直接法時；當(dāng)求解精度要求不是極端苛刻，迭代法能在可接受時間內(nèi)達(dá)到足夠精度時。2.處理奇點/劇烈振蕩的數(shù)值積分方法：*方法：改進(jìn)吉布斯現(xiàn)象（GibbsPhenomenon）影響的方法，如辛普森法則的復(fù)合應(yīng)用（對積分區(qū)間進(jìn)行細(xì)分，在每個子區(qū)間上使用辛普森法則，然后求和）或連分式法（PadéApproximants）。*