 |
 |
 |
 |
 |
 |
||
 |
 |
 |
 |
 |
| 3 | 1/1 | 返回列表 |
| 查看: 1807 | 回復(fù): 2 | ||
袁飛燕鐵蟲 (初入文壇)
|
[求助]
求助！關(guān)于Misra-Gries 算法和數(shù)據(jù)流的兩道題！萬分感謝！
|
 求助兩道計(jì)算題，請(qǐng)各路大神幫忙看看！1. 假設(shè)有一個(gè)包含 90 個(gè)數(shù)據(jù)的數(shù)據(jù)流，該數(shù)據(jù)流一共有 5 個(gè)不同的元素，即 （x1, x2, x3, x4, x5），其中 x1 出現(xiàn)的頻率為 50， x2 出現(xiàn)的頻率為 10， x3 出 現(xiàn)的頻率為 10， x4 出現(xiàn)的頻率為 10， x5 出現(xiàn)的頻率為 10�？紤]在該數(shù)據(jù)流 上運(yùn)行參數(shù)為 k=2 的 Misra-Gries 算法， 嘗試解決以下問題： (a) 數(shù)據(jù)流中的數(shù)據(jù)以怎樣的到達(dá)順序可以使得元素 x1 的計(jì)數(shù)最大（也就是 Misra-Gries 算法在最終狀態(tài)下 x1 的計(jì)數(shù)最大）？該最大的計(jì)數(shù)值是多少？ (b) 數(shù)據(jù)流中的數(shù)據(jù)以怎樣的到達(dá)順序可以使得元素 x1 的計(jì)數(shù)最小（也就是 Misra-Gries 算法在最終狀態(tài)下 x1 的計(jì)數(shù)最�。吭撟钚〉挠�(jì)數(shù)值是多少？ 2. 假設(shè)有兩個(gè)數(shù)據(jù)流 E1 和 E2，其中 E1 包含 n1 個(gè)數(shù)據(jù)， E2 包含 n2 個(gè)數(shù)據(jù)。 令 E 為 E1 和 E2 合并后的數(shù)據(jù)流，即 E={E1, E2}。 例如， E1={a, b, a, c}， E1={a, b, c, c, d}，那么 E= { a, b, a, c, a, b, c, c, d}�？紤]兩個(gè)蓄水池采樣算法，分別對(duì) 數(shù)據(jù)流 E1 和 E2 進(jìn)行采樣。兩個(gè)采樣算法的蓄水池大小都為 k (k<n1, k<n2)， 也即對(duì)于每個(gè)數(shù)據(jù)流，我們可以得到 k 個(gè)均勻的樣本。請(qǐng)?jiān)O(shè)計(jì)一個(gè)樣本合并 算法將這 2k 個(gè)樣本進(jìn)行合并，得到 k 個(gè)合并流 E 中的均勻樣本？ 并證明得到 的 k 個(gè)樣本中的任何一個(gè)樣本數(shù)據(jù)被抽取的概率為 k/(n1+n2)。 |
回復(fù)此樓» 猜你喜歡
重慶交通大學(xué)光子學(xué)微結(jié)構(gòu)與器件課題組招收2026年碩士研究生信息
已經(jīng)有2人回復(fù)
-
一志愿鄭大材料學(xué)碩298分，求調(diào)劑
已經(jīng)有6人回復(fù)
-
物理學(xué)I論文潤色/翻譯怎么收費(fèi)?
已經(jīng)有146人回復(fù)
-
尋合作：應(yīng)力腐蝕多尺度模擬
已經(jīng)有6人回復(fù)
-
考研交流
已經(jīng)有0人回復(fù)
-
【新加坡】納米電子器件項(xiàng)目組有“聯(lián)合培養(yǎng)博士生”名額
已經(jīng)有0人回復(fù)
-
【新加坡】納米電子器件項(xiàng)目組有“聯(lián)合培養(yǎng)博士生”名額
已經(jīng)有0人回復(fù)
-
幫我的英語口語老師找學(xué)生
已經(jīng)有3人回復(fù)
orta1986
新蟲 (初入文壇)
- 應(yīng)助: 0 (幼兒園)
- 金幣: 33
- 帖子: 11
- 在線: 2.1小時(shí)
- 蟲號(hào): 12953315
- 注冊(cè): 2018-11-26
- 專業(yè): 光學(xué)
2樓2019-10-13 09:50:41
袁飛燕
鐵蟲 (初入文壇)
- 應(yīng)助: 0 (幼兒園)
- 金幣: 34.4
- 帖子: 10
- 在線: 16.9小時(shí)
- 蟲號(hào): 4413787
- 注冊(cè): 2016-02-18
- 專業(yè): 生物化學(xué)
3樓2019-10-13 23:59:26
相關(guān)版塊跳轉(zhuǎn)
我要訂閱樓主 袁飛燕 的主題更新
| 3 | 1/1 | 返回列表 |
| 最具人氣熱帖推薦 [查看全部] | 作者 | 回/看 | 最后發(fā)表 | |
|---|---|---|---|---|
|
[考研] 復(fù)試調(diào)劑 +5 | 呼呼？~+123456 2026-03-05 | 5/250 |
|
|---|---|---|---|---|
|
|
[考研] 材料調(diào)劑 +4 | L9370 2026-03-05 | 4/200 |
|
|
[考研] 306求調(diào)劑 +3 | Bahati 2026-03-05 | 3/150 |
|
|
|
[考研] 347求調(diào)劑 +6 | 啊歐歐歐 2026-03-03 | 8/400 |
|
|
|
[考研] 一志愿南京大學(xué)資源與環(huán)境專業(yè)283分求調(diào)劑 +3 | 追云?? 2026-03-04 | 3/150 |
|
|
|
[考研] 材料復(fù)試調(diào)劑 +7 | 學(xué)材料的點(diǎn) 2026-03-01 | 8/400 |
|
|
|
[考研] 264求調(diào)劑 +8 | 26調(diào)劑 2026-03-03 | 8/400 |
|
|
|
[考研] 0855機(jī)械工程324求調(diào)劑 +3 | 鄭SK 2026-03-02 | 7/350 |
|
|
|
[考研] 295求調(diào)劑 +6 | 等春來， 2026-03-04 | 6/300 |
|
|
|
[考研] 材料化工調(diào)劑 +15 | 今夏不夏 2026-03-01 | 18/900 |
|
|
|
[考研] 291求調(diào)劑 +3 | 咕嚕咕嚕123123 2026-03-02 | 4/200 |
|
|
|
[考研] 化工專碩調(diào)劑 +4 | 利好利好. 2026-03-03 | 7/350 |
|
|
|
[考研] 化工專碩348，一志愿985求調(diào)劑 +8 | 弗格個(gè) 2026-02-28 | 11/550 |
|
|
|
[考研] 26考研報(bào)考西工大材料308分求調(diào)劑 +4 | weizhong123 2026-03-01 | 5/250 |
|
|
|
[考研] 307求調(diào)劑 +6 | wyyyqx 2026-03-01 | 6/300 |
|
|
|
[考研] 求調(diào)劑 +11 | yunziaaaaa 2026-03-01 | 13/650 |
|
|
|
[考研] 材料工程274求調(diào)劑 +5 | Lilithan 2026-03-01 | 5/250 |
|
|
|
[考研] 1 +5 | 2026計(jì)算機(jī)_誠心 2026-03-01 | 8/400 |
|
|
|
[考研] 一志愿鄭大材料學(xué)碩298分，求調(diào)劑 +6 | wsl111 2026-03-01 | 6/300 |
|
|
|
[考研] 材料調(diào)劑 +6 | 愛擦汗的可樂冰 2026-02-28 | 7/350 |
|