這個內容是用來回憶一下EDA2涉及的算法和解題的主要步驟：
有疑問或發現錯誤可以私信來討論
高級綜合概述
柏拉圖優化：這個是來判斷是否有哪些節點能完全被其他節點優化掉。比如（1,2）這個節點就可以完全優化（3,4）（3,2）這些節點。判斷的方式就是兩個值都比已經存在的其他節點大或相等（也可以使用坐標系向坐標軸做垂線，如果完全某節點的區域完全包裹另外一個就說明它會被優化）
操作調度
最小延遲無約束調度
沒有約束可以直接理解為沒有處理機資源數量的限制，只考慮先后次序
ASAP?從前向后
這個算法就是針對有向圖，從前向后先把無前驅的節點標成1，之后根據后繼順序依次標為2、3、4直到完成所有節點的標注
ALAP?從后向前
這個算法會給出一個時間限制，是從最后一個節點按照這個根據這個時間限制的數值來進行標注。
看一下上圖F的區別，就可以看出來前向后調度和后向前調度的區別
上述的ALAP和ASAP是下面這些算法中的一種調度思路
有約束調度
有約束和上面
Hu調度算法
這個算法針對的有限個是同種處理機資源進行的調度
1.?劃分出優先級（使用ALAP）
2.根據優先級進行調度（考慮每個時刻處理機的使用量）
列表調度
這個算法是針對不同處理機進行的調度，有MR-LCS（對時間有具體限制，處理機數量是未知量表示）與ML-RCS（對處理機數量有明顯顯示，但是對于時間并無要求）。
這個調度會使用下面的ILP進行數字化處理（畫的圖用于對ILP的唯一約束化簡）
ILP優化（x?數值上只能為1或0）
ML-RCS中有三個約束
1.唯一約束：每個節點只被調度一次??
2.順序約束：后繼節點時間必須大于等于 前驅節點時間+處理前驅節點所用時間
3.資源約束：在同一時刻某一類資源被調度的數量必須小于等于該類資源的處理機的數量
對于這種題的做法就是根據上面的列表調度，使用ALSP算法畫圖，對唯一限制的式子進行優化
MR-LCS中有三個約束
1.唯一約束：每個節點只被調度一次??
2.順序約束：后繼節點時間必須大于等于 前驅節點時間+處理前驅節點所用時間
3.時間約束：最終的時間必須小于 給出時間+1（調度最后一個節點的時間）
對于這種題需要將處理機數量設置為a1?a2這種，之后進行類型資源約束的寫法，之后按照ML-RCS的方法進行化簡
MIN 權重*資源數量+權重*資源數量（這個是最終的表達式，列出來化簡就行，不用全算出來）
時間分析
關鍵節點關鍵性
這種題的步驟：
1.標出：需要時間/到達時間（第一個節點前后都有、后面節點的都是后面）
2.裕量=需要時間-到達時間
3.裕量為零的節點是關鍵節點，這些節點形成的路徑是關鍵路徑
4.關鍵性=1-（裕量/圖中最大裕量）
綁定問題
兼容圖和沖突圖
這個也是針對有向圖，一般是使用優化算法處理過的
兼容圖：節點之間不存在并發關系（說白了就是在ASAP這種圖里面不在同一排）
沖突圖：兼容圖的補圖
左邊緣算法
放兩張圖就明白了
兩級邏輯優化
優化目標
假設一家公司有很多人，有會前端和后端的、有會后端和運維的......
最小覆蓋：裁員之后在所有技術棧都被覆蓋的情況下剩余的人數最少
非冗余覆蓋：不一定人數最少，但每個人都不可或缺（再裁誰就必然會有某個技術棧沒被覆蓋）
單個蘊含項下的非冗余覆蓋：一個人被另一個人完全替代（技術棧被完全包括）
精確兩級優化邏輯
Quine算法
On數組（1），Off數組（0），Dc數組（非0也非1）
比如F=abcd+ab（非c）d+a（非b）cd這種形式，要求出其一次的最小蘊涵項：
1.枚舉出可以使F=1的情況，比如abcd就是1111，ac（非c）d就是1101
2.兩兩對比，找出可以概括的項合并為*，比如1111和1101可以合并成11*1
3.再次合并直到無法合并為止
列出合并的最終結果和合并過程中沒有合并進去的列在一起
分支優化
這個不會考遞歸那個式子，考的是矩陣的縮減
1.?按照題目給出蘊涵項那一列（打勾），劃掉那一列所含1所在的行
2.之后進行列之間的支配（1被全覆蓋），不打勾
3.之后掃描每一列，發現進出現一個1的話就這一列打勾，并且劃掉那一列所含1所在的行
4.直到不存在1為止
打勾的行頭部的式子就是蘊含式
啟發式兩級優化邏輯
矩陣表示法
首先兩個操作：
1.Intersection：同1才為1
2.supercube：存1即為1
之后有一個操作：
求余子式Fa：
F先對a進行Inter操作、操作結果對a取反的結果進行supercube操作
重言式：
1.余子式存在全為1的一行
2.對于唯一決定項，每一列都不全為0
非重言式：
對于唯一決定項，存在一列都全為0
單調性：
對于F中的某一個元素，比如是a，若只存在a即a為單調增，若只存在（非a）則a為單調減
操作
取反
使用德摩根律和矩陣計算對F去某一個因子的反，如果算不出來就接著取
拓展
會讓嘗試拓展某一項
1.F取反
2.檢查F中某一個項是否可以簡化，比如abc是否可以簡化成ab（F反和ab進行Inter運算）
3.若運算結果為空（存在00項的話該行直接劃掉），則可以拓展
4.之后可以進一步拓展，比如ab可否簡化為a，即F反與a進行Inter運算，看結果是否為空
縮減
其實是增加了字母（抽象程度降低）
下面這個例子說的很明白，這是者怒地某一個元素進行的縮減嘗試
1.對剩余子式取反
2.之后求該反式對a取余因子的結果
3.之后對于該結果進行supercube運算
4.最后看選出項和3的運算結果交集是否等于選出項
5.若相等說明無法化簡，不相等更新原函數該項
去冗余
非冗余覆蓋是Rp中的元素+Er中的元素
Er存放必須存在的項（處理之后不是重言式）
Rp存放不存在的項（處理之后無法判斷不是重言式）
1.在F中去除一個項
2.剩余項對該項取余子式
3.余子式不是重言式的話就放入Er，反之先放入Rp
Rt
對于Rp中的元素進行如下判定：
1.H=Rp中的元素+Er中的元素-選出來接受判定的元素
2.H對該元素求余因子，若結果不是重言式，就不可以去掉該元素
3.去掉的元素放入Rt，并從Rp中刪去
