計算機科學

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

0
關於圖靈機接受的語言定義的困惑,一個非常基本的問題
我正在為即將參加的考試而學習,我的書給出了以下定義:讓 $ M $ 成為圖靈機,然後將接受的語言 $ T(M)$ $ M $ 的定義為 $ T(M)= \ {x \ in \ Sigma ^ * \ mid z_0 x\ vdash ^ * \ alpha z \ beta;\ alpha,\ beta \在\ Gamma ^ *;z \ in E \} $ 。作為旁注...
  


0
哪種不確定的語言$ B $可以還原為它的補語?
我遇到了一個問題,要求給出一個不確定語言的示例 $ B $ 這樣的 $ B \ leq_m\ overline {B} $ ... 但是,我發現很難構造一個示例...我的困難是,鑑於一種不確定但圖靈可識別的語言,請說 $ A_ {TM} $ ,其補語 $ \ overline {A_ {TM}} $ 無法識...
   

0
是否存在諸如使用不同b值進行b匹配的問題?
考慮兩人的Garph $ G =(L \ cup R,E)$ 。自然,b匹配問題是找到一組邊 $ M \ subset E $ ,這樣,$ L $ 和 $ R $ 與最大的 $ b $ 鄰居相鄰,並且權重函數 $ w(e),e \ in E $ 被最大化。如果我們有不同的 $ b $ 怎麼辦?例如, $ b(v)= 5,\ f...
    

2
Krom公式的等價性易於處理嗎?
假設我有兩個Krom formulas $ \ psi_1,\ psi_2 $ 。Krom公式是CNF中的命題公式,每個子句中都有2個文字。每個文字可以取反或取反。換句話說, $ \ psi_1,\ psi_2 $ 是2-CNF公式。例如: $(x_1 \ vee \ neg x_2)\ land(\ neg x_2 \ vee x_3)\ land(x_3 \...
    

0
高效的群組查找數據結構
我需要一個數據結構,該結構允許有效查詢 給我x組 。讓我給你舉個例子:Group 1: [a, b, c] Group 2: [d, e] Group 3: [f] getGroupOf(d) -> [d, e] 對存儲或構建時間沒有明顯的限制。我只需要getGroupOf為O(logn)或更快。我正在考慮使用Dictionary&...
 

0
什麼是外行項目的最小化(μ函數)?
在計算機科學中,μ函數用於將一組原始遞歸函數擴展為一般的遞歸函數,但我不明白此函數的作用。有很多公式,但是我不明白它是什麼。假設我正在用Python(或任何其他通用語言)編寫。μ函數IRL的例子有哪些?...
 

4
無向圖在DFS中的第一次和第二次看到的邊緣
假設一個無向圖和對其進行DFS遍歷。我對DFS樹感興趣,該樹編碼遍歷的發現者/發現者(父/子)關係。為了確保我們在同一頁面上,將 discovered 頂點 x 定義為已被訪問但其後代仍在處理中的那個頂點,即,我們尚未卻又返回到 x ...
   


0
在一定範圍內打印質數的時間複雜度?
我為this問題寫了一個答案,該問題詢問以下內容:打印從start到end的質數的給定代碼的時間複雜度是多少?是 $ O(end * \ sqrt {n})$ ?/** * Print prime numbers between start and end inputs * Time-Complexity: O(end * sqrt(n)) * Space-Complexity: O(1) only o...
  

0
證明$ \ lceil \ lg n \ rceil -1 = \ lfloor \ lg n \ rfloor $
我最近遇到了一個問題:顯示在任何nn元素堆中,最多有高度為hh的 $ \ lceil n / 2 ^ {h + 1} \ rceil $ 節點。我尋找了一些解決方案,並找到了以下解決方案:Binary heap: prove that number of nodes of height h is not bigger than $\lceil \frac{n}{2^{h+1}} cei...
  

1
是否有任何隨機算法是確定性算法集上的概率分佈?
如果存在大小為n的有限實例集,並且(合理的)確定性算法集為finit。任何隨機算法都可以看作是確定性算法集上的概率分佈嗎?如果可以,為什麼?...
    

1
為了比較兩種排序算法,可以更改整數數據集排序的哪些因素?
我正在比較兩種基於比較和二進制數據結構的排序算法,即樹排序和堆排序。我正在測量兩種算法對一個遞增的整數數據集進行排序所花費的時間。但是,我想知道整數數據集本身中是否還有其他可以修改的變量(例如標準差)...
     


2
聯合查找時,等級之間的運行時差異與等級之間的運行時差異
我正在研究Union Find,根據Wikipedia,有兩種工會類型:按等級劃分的工會和按規模劃分的聯盟。我的問題是,兩者(如果有)之間的運行時區別是什麼?直覺上,感覺像以大小為單位的並集總是更好,因為每次合併時,我們都將...
     

1
使用一個添加和刪除頂點操作查找一個MST
我正面臨以下問題:給定無向完整歐氏加權圖 $ G(V,E)$ 及其 MST $ T $ 。我需要刪除任意頂點 $ v_i \ in V(G)$ ,並指定一個頂點 $ v_j \ notin V(G)$ ,我必須計算 $$ G ^ {'}((V(G)\反斜杠\ {v_i \})\ cup \ {v_j \},(E \反斜杠\ {(...
   

1
掃掠線算法如何使用矢量叉積檢查交點?
我正在盡力了解sweep-line algorithm來找到線的交點。我了解大多數直覺,除了它如何使用叉積計算兩個線段之間的交點。 我正在為下面的代碼提供代碼,如果對代碼有任何疑問,請問我,以便我可以向不熟悉編程的人解釋。 完整...
   


0
離散函數的哪些屬性使其成為理論上有用的目標函數?
首先要避免的一些事情:我不是在問函數必須具有哪些屬性以使得存在全局最優,我們假設目標函數具有一個(可能是非唯一的)全局最優,它可以從理論上通過詳盡搜索候選空間找到。我也以一種有點誤導的方式使用 理論上...
 

1
如何遵循本指南來構建具有矩陣/可達性的圖
讓我們有k個矩陣。例如,我們現在有3個,其中第一個是8x5( $ a_1 $ x $ b_1 $ ),第二個是5 x 6( $ a_2 $ x $ b_2 $ ),最後一個是6 x 8( $ a_3 $ x $ b_3 $ )。我們的目標是確定在 x 和...
     

Next page