計算機科學

針對計算機科學的學生,研究人員和從業人員的問答

2
具有多個具有不同優先級的隊列的BFS變體的名稱
是否存在以下BFS變體的名稱,該變體在具有非根起點的樹上運行?使用兩個隊列來代替處理一個節點時所有鄰居節點都添加到的單個隊列( $ Q_A $ 和 $ Q_B $ )。將子節點添加到 $ Q_A $ ,將父節點添加到 $ Q_B $ 。選擇下一個要處理...
     

3
動態編程-小偷變異探針
我遇到了一個動態編程問題,它是小偷的變種。假設您是小偷,並且連續給了您一些房屋,您應該搶劫 $$ House_1,House_2 \ dots House_N $$ 每所房子具有以下值: $$(x_i \ geq y_i \ geq z_i \ gt0)$$ 如果您搶劫房屋但您沒有相鄰的房屋,您...
  

2
已知P / poly位於RE中嗎?
是否知道P / poly在RE中?如果是的話,它還屬於其他哪些類。...
   



0
當$ F(N)$為偶數或奇數時如何證明Big-O
如果給我一個函數 $ f(n)$ ,例如 $ 4n + 1 $ 當是偶數且 $ 3n ^ 2 + 2 $ 時,我必須證明或不贊成 $ f(n)$ 是 $ \數學O(n ^ 2)$ 。我是否必須對所有 $ n> n0 $ 做 $ f(n)...
   

0
證明從排序數組中構建平衡的BST是$ \ Theta(n)$
我很難證明從排序數組中構建平衡的BST是 $ \ Theta(n)$ 我得到以下公式: $$ T(n)= 2T(\ frac {n} {2})+ \ Theta(1)$$ 我試圖通過歸納法證明這一點,但對 $ n $ 是奇數的情況感到困惑。有沒有更好的方法來證明這一點?替代將不會...
    

0
PDA的高度有任何特性嗎?
我正在嘗試為 $ L $ 找到一個PDA,它最多可以修改堆棧高度。 $ L = \ {a ^ ib ^ i \ mid i \ geq 0 \} $ 我認為沒有這種PDA,但是我怎麼證明呢?我的嘗試是針對給定的字符串,找到PDA中的堆棧高度與CFG中最左導數之間的關係,然後證明沒...
   

1
尋找非凸多面體相交的算法
上下文:我有兩個多面體, $ A = V_1 \ times F_1 $ 和 $ B = V_2 \ times F_2 $ ,其中 $ V_i $ 是一組頂點(這些頂點恰好在 $ \ mathbb R ^ 3 $ )和 $ F_i $ 是一組面孔(長度為 $ \ geq 3 $ 的元組如 $(i_1,...,i_k)\在F_i $ 中,如果存在 $ i_1 $形成...
  

1
使用貪婪算法找到至少有一半邊緣被切割的切割S
讓 $ G $ 成為無向圖。找到一個貪婪算法,該算法找到至少切掉一半邊緣的切面 $ S $ 。我試圖考慮一些事情,例如選擇具有最高度的頂點,將其添加到 $ S $ ,從圖形中將其刪除,然後重複此過程直到我受夠了。但是,這僅是猜測...
   

0
語言$ \ overline {L _ {\ epsilon}} $的半確定性
首先考慮問題:給定 $ L_H = \ {R(M)w:M \ in TM_0,w \ in L(M)\} $ 其中 $ R(M)$ 是在TM_0 $ 中 $ M \的編碼轉換。假設矛盾 $ \ overline {L_ {H}} $ 是半確定的,那麼TM_0中有 $ Q \$ 與 $ L(Q)= \ overline {L_ {H}} $ ,因此,每個 $ M\在TM_0 $ 中,...
    


1
除二叉樹中的一個以外的所有節點的乘積
假設我們給了一個二叉樹,每個節點上都有一個整數。我正在尋找一種有效的方法,以找到從根到葉的每條路徑的每個可能的產品,並省略一個節點。我正在尋找無除法的解決方案(即整數可以為零)。我想到的一種解決方法是...
   

2
獲取包含x個節點的每個可能的(連接的)子圖
如果我有一個表示美國的圖,每個節點代表一個州,並且每個邊都鏈接相鄰的州,那麼是否有一個圖算法可以為我提供每個可能的唯一的4個連接狀態的組(狀態的順序不是重要)? 鏈接 是指有效組中的所有狀態都應可從組中的...
  

0
同心凸包
給定2D平面中的N個點,如果我們從給定點開始,並開始包含集合中的點,則該點按它們到起點的距離排序。包括每個點之後,我們檢查是否可能存在凸包,然後將所有這些點移至受訪集並繼續。每次確定凸包時,如果如此構造的...
  

3
1英寸SAT的完整解析規則
在CNF SAT中,每個子句(A或B或C或...)必須至少包含一個真實文字。解決規則適用於一對具有完全相反的文字的子句。(A或B或C)和(!A或D或E)=>(B或C或D或E)我說這條規則是完整的,從某種意義上來說,如果公式不令人滿意...
   

1
動態編程中的空間優化版本的零錢和背包問題
我最近一直專注於某些問題的動態編程中的DP配方和空間優化。我已經經歷過標準問題,例如0-1 Knapsack和Coin Change問題。在空間優化部分,我不知道應該以什麼順序填寫表格以獲得所需的結果。例如,在上述0-1背包問題中,該問...
   

0
多項式上界和下界是什麼意思
我剛剛遇到了這個漸近邊界: $(\ log n)!= \ Theta \ left(n ^ {\ log \ log n} \ right)$ 有以下評論: Hence, polynomially lower bounded but not upper bounded. 我在這裡找到了這個 https://gateoverflow.in/12928/%24-log-and-log-log-are-polynomially-bounded-anybody...
  


0
如何用漢密爾頓NP-Hard問題證明兩個頂點之間最長路徑的NP完全性
我有一個問題:我有一個無向圖G(V,E)(其中V =頂點集,E =邊集)。考慮兩個頂點s和t之間的最大路徑:LPATH = {⟨G,s,t,k⟩|There is in G a simple path as long as at least k from s to t} 簡單路徑是沒有任何重複頂點的路徑,即每個頂點只能...
    

Next page