 |
 |
 |
 |
 |
 |
||
 |
 |
 |
 |
 |
| 5 | 1/1 | 返回列表 |
| 查看: 1811 | 回復(fù): 2 | ||
| 當(dāng)前只顯示滿足指定條件的回帖，點(diǎn)擊這里查看本話題的所有回帖 | ||
袁飛燕鐵蟲 (初入文壇)
|
[求助]
求助！關(guān)于Misra-Gries 算法和數(shù)據(jù)流的兩道題！萬(wàn)分感謝！
|
|
 求助兩道計(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 算法， 嘗試解決以下問(wèn)題： (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ù)此樓» 猜你喜歡
【新加坡】納米電子器件項(xiàng)目組有“聯(lián)合培養(yǎng)博士生”名額
已經(jīng)有0人回復(fù)
-
幫我的英語(yǔ)口語(yǔ)老師找學(xué)生
已經(jīng)有4人回復(fù)
-
物理學(xué)I論文潤(rùn)色/翻譯怎么收費(fèi)?
已經(jīng)有118人回復(fù)
-
計(jì)算三階力常數(shù)用thirdorder擴(kuò)胞時(shí)參數(shù)如何選擇？臨近原子數(shù)怎么取值
已經(jīng)有7人回復(fù)
-
2026年循環(huán)經(jīng)濟(jì)功能材料國(guó)際會(huì)議（ICFMCE 2026）
已經(jīng)有0人回復(fù)
-
2026年第五屆電氣、電子與信息工程國(guó)際會(huì)議（ISEEIE 2026）
已經(jīng)有0人回復(fù)
-
哈爾濱理工大學(xué)物理系招收物理學(xué)考研調(diào)劑
已經(jīng)有0人回復(fù)
-
0702一志愿吉大B區(qū)求調(diào)劑
已經(jīng)有2人回復(fù)
袁飛燕
鐵蟲 (初入文壇)
- 應(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
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
| 最具人氣熱帖推薦 [查看全部] | 作者 | 回/看 | 最后發(fā)表 | |
|---|---|---|---|---|
|
[考研] 調(diào)劑 +4 | 調(diào)劑的考研學(xué)生 2026-03-09 | 4/200 |
|
|---|---|---|---|---|
|
[考研] 0703化學(xué) 學(xué)碩 理工科均可 不區(qū)分研究方向 總分279求調(diào)劑 +9 | 1一11 2026-03-03 | 9/450 |
|
|
|
[考研] 考研求調(diào)劑，工科，總分304 +4 | 矮子不想長(zhǎng)高了 2026-03-08 | 7/350 |
|
|
|
[考研]
一志愿天津大學(xué)材料與化工275求調(diào)劑
 10+3
|
穿只靴子 2026-03-07 | 14/700 |
|
|
|
[考研] 288求調(diào)劑085600材料與化工 +13 | Daunrin 2026-03-07 | 15/750 |
|
|
|
[考研] 求調(diào)劑 +3 | 拾柒12。 2026-03-08 | 3/150 |
|
|
|
[考研] 物理學(xué)求調(diào)劑 +3 | sx宋 2026-03-05 | 3/150 |
|
|
|
[考研] 不限學(xué)校專業(yè)的調(diào)劑同學(xué)看過(guò)來(lái) +5 | 啊擺啊擺 2026-03-05 | 9/450 |
|
|
|
[考研] 268求調(diào)劑 +4 | 劉合華 2026-03-05 | 4/200 |
|
|
|
[考研] 275求調(diào)劑 +4 | 大爆炸難民 2026-03-06 | 5/250 |
|
|
|
[考研] 316求調(diào)劑 +3 | 林小星發(fā)大財(cái) 2026-03-05 | 5/250 |
|
|
|
[考研] 材料調(diào)劑 +4 | L9370 2026-03-05 | 4/200 |
|
|
|
[考研] 一志愿武理085601專碩347分求調(diào)劑 +4 | 啊歐歐歐 2026-03-04 | 5/250 |
|
|
|
[考研] 334求調(diào)劑 +3 | Trying] 2026-03-03 | 4/200 |
|
|
|
[考研] 一志愿985材料與化工 326分求調(diào)劑 +3 | Hz795795 2026-03-04 | 3/150 |
|
|
|
[考研] 307求調(diào)劑 +4 | xuyuan111 2026-03-04 | 5/250 |
|
|
|
[考研] 一志愿西交大材料學(xué)碩 346 求調(diào)劑 +3 | zju51 2026-03-04 | 3/150 |
|
|
|
[考研] 322,求調(diào)劑 +3 | 菜菜愛玩 2026-03-04 | 3/150 |
|
|
|
[考研]
 0703化學(xué)學(xué)碩 288分
+4
|
旅行中的紫葡萄 2026-03-03 | 4/200 |
|
|
|
[考研] 復(fù)試調(diào)劑 +4 | 杰尼龜aaa 2026-03-03 | 4/200 |
|