宅學習 - Social Learning Space 社交學習空間@FJU CSIE

"

Sychronization Problem 一直是 Thread 相關議題的重點之一，因為許多的 Thread 會同時存取 Shared variable，所以若沒有將此 shared variable 做好 synchronization，則會產生 race condition 的情況。

JAVA 提供 programmer 簡易的使用 synchronization 機制，利用 synchronized 關鍵字來完成同步的技巧。

synchronized 有兩種方式可以完成。

1. synchronized method

就是對 method 作同步，當被同步過的 method 同時有兩個 thread 需要存取時，先到者就可以優先使用，後到者必須等到前一個 thread 釋放其 lock 才可以使用，並且是持續等待下去。

而且，被同步化的 method 的 lock 是該 class 的 lock，也就是說，當這個 class 擁有兩個以上的同步化 method：

public class TwoSyncMethod
{
    public synchronized void first(){}
    public synchronized void second(){}
}

當有兩個 thread 同時存取 first() 與 second() method，也就是存取不同的 method，但是都位於同一 class 之中，第一個到達的 thread 可以使用它所呼叫的 method ，但是第二位 thread 卻必須等待，即使兩個 thread 是存取不同的 method，由於 synchronized method 是使用 class lock 來作為 lock，所以即使存取不同 method，只要是為在同一 class 之中，也是必須等待，直到前者釋放此 class lock，所以，當我們在設計 thread 議題時，效能也是必須考量的。 

2. synchronizated block

有時候為了考慮效能等種種原因，希望將 synchronized 的影響範圍給縮小，那就可以使用 synchronized block

synchronized (lock) {...}

lock 就是要進入此 block 所需要取得或是等待前者釋放的 lock。當然，我們也可以將 lock 設為 class 的 lock，那就改用 synchronized ( this ) {...} 即可。

接下來就是特別的部分： synchronized static method，static 與 non-static method 所取得的 class 的 lock 是不同的!! 所以，synchronized static method and synchronized non-static method 是可以同時執行的，但是注意的是：對每一個 class 來說，同時只有一個 thread 可以執行 synchronized static method；每個 class 的 instance 只有一個 thread 可以執行 synchronized method ( non-static )。

"

"還是一樣,希望可以獲得更多, 課程"

一部分是因為Vista要作兩個不同執行緒的桌面...而且另一個桌面好像是可以接受遠端近來的

車用軟體就可以用，配合新的駕駛與副駕駛以角度不同看到的畫面不同之類的技術，可以同一時間透過遠端桌面連線進行不同的動作。

車端不用什麼硬體，就是個多角度的LCD觸控板，剩下韌體軟體只要把遠端桌面連線跟網路技術作進去就好了～省了一些硬體成本又可以帶來更大的軟體服務內容。

==================================

１.不過社會成本倒是提高很多，哪來這麼多隨時隨地可用的無線網路或是無線通訊？

２.誰人家裡沒電腦不就挫屎了？

３.假如能做的話搞不好有新興行業產生－－車用桌面開發公司……。

"

註：這篇文章原po於無名小站blog
資工四甲　492511635　林泰昇

[12/29筆記]

1.          BT(backtracking)和B&B(branch and round)的不同：

• 都有使用state space tree、promising function。
• 若能找出比較好的promising function，則會使得algorithm的效率更好。

2.          不同處：

• BT：使用DFS。
  B&B：使用BFS。
• BT：常以recursive實做。
  B&B：可以求得最佳解。
• Q：那麼，BT和B&B哪個比較好？
  A：看情形。

3.          如果設計遊戲的話，B&B會較常使用到。

4.          Knapsack問題包括：

• 0-1 problem(不是拿就是不拿)
• fractional(可以拿一部分)

5.          若程式邏輯正確，但卻無法找出解答的可能原因：

• 佔用CPU時間太多。
• 佔用太多memory。

由於以上的兩個原因導致OS把這個程式的process設成die，因此沒有解出題目。

"

"

註：這篇文章原po於無名小站blog
資工四甲　492511635　林泰昇

[1/04筆記]

1.          加密演算法的目的：

A.         Confidentiality

僅sender和receiver知道message的內容。

B.         Authentication

Sender和receiver互相確定對方是否為真正的對象。

C.         Message Integrity

Sender和receiver希望確保message的完整性而不需要額外detection。

D.         Access & availability

Survice provider必須讓user可存取(accessible)和可取得(available)其服務。

2.          Symmetric key crypto : sender, receiver keys identical.

• Substitution cipher：以一個東西代換另一個東西。
• 對稱加密法的重要問題：該如何保證key傳輸的安全？

3.          Public key crypto : encryption key public, decryption key private.

Requirement:

• 需要 K_B⁺和K_B^-使得K_B^-(K_B⁺(m)) = m
• K_B^-應該和K_B⁺沒有關聯。

4.          RSA加密演算法

A.         選擇key：

B.         選擇兩個非常大的質數p, q。

C.         計算n=p*q
     z=(p-1)*(q-1)

D.         選一個數字e(e < n)和e互質(或e*d mod z = 1)。

E.          則：

• Public key: (n,e)：K_B⁺
• Private key:(n,d)：K_B^-

5.          加密解密步驟：

A.         取得上一個步驟所計算出的K_B⁺和K_B^-。

B.         To encrypt bit pattern m，計算

        c = m^e mod e

C.         To decrypt bit pattern c，計算

        m = c^d mod n

則m = (m^e mod n)^d mod n

註：(m^e mod n)就是c"

"

註：這篇文章原po於無名小站blog
～引用自「Term Project: Indepth Survey and Analysis」～

資工四甲 492511635 林泰昇

　　許許多多的遊戲都會有「讓電腦控制的怪物等角色可以找到玩家」的需求，但若僅以隨機暴力法來達成這件事，那麼怪物的移動路徑看起來就會像是少了一根筋似的亂繞一通，這會讓玩家覺得「電腦很笨」，而且這樣做的效率也不好。

　　在人工智慧方面，像以上所提的路徑搜尋問題是一個基本的問題。稍微深入路徑搜尋的問題，其中一個演算法是A*(A-star)演算法。A*演算法和BFS (breadth-first search)類似，但有較多的彈性，使用A*演算法做為路徑搜尋基礎的遊戲也顯得較為聰明。

　　這次打算深入探討A*演算法，分析其演算法的優點，以及A*演算法和幾種路徑搜尋方法的比較。

"

"

註：這篇文章原po於無名小站blog
引用自～「Lab3: SuDoKu Solver 3」～

資工四甲 492511635 林泰昇

　　這次的作業並沒有實做新的候選數消去法，由於從Lab1以來都是使用backtracking實做，因此這次Lab的重點還是和Lab2相同──最佳化(optimization)。

　　承襲Lab2，這次進行的optimization的重點在於：

1. 改寫class，改變class基本結構，減少使用object data type的地方，儘量採用primitive data type。
2. 改寫backtracking method，增加backtracking的效率。
3. 改變呼叫method的順序，減少多餘的檢查次數。
4. 由於Lab2雖然大幅改進Lab1的效率，但backtracking的次數卻大幅增加。根據實驗結果，backtracking次數越多，所花費的運算時間就會越高。Lab3修正這點降低backtracking的次數。

經過三次Lab的改進後，總結心得如下：
　　這三次的Lab讓我相當深入的瞭解sudoku遊戲的運作與解題技巧，原本我並沒有接觸過這個遊戲，在完成三次Lab後，像x-wing這種較進階的解題技巧都能清楚其運作原理，這是意想不到的收穫(或痛苦)。

　　其次就是熟悉backtracking的背後原理與實際運用。對於backtracking的理論與應用都有了更進一步的瞭解，也讓我對演算法增加了不少興趣，這是做完Lab後最大的收穫。

改進事項與未來目標

1. 三次Lab的backtracking都沒有使用recursive實做，也許其中一兩次應該改成recursive。這樣的話相信可以更增進對backtracking的瞭解。
2. 程式效率還是不盡理想。也許整個程式的結構都需要分別改進才能進一步得到更好的效率(Greedy？)
3. 程式結構不夠清楚。雖然和演算法主題無關，不過就物件導向程式來說，程式必須能夠適應變化才是最好的，我的程式顯然還是離這個目標有很大的距離。
4. 可增加GUI介面，這樣可以使程式提供更佳的人機介面，最好能再提供操作介面讓使用者匯入題目，增加程式的友善性。

執行結果與比較
　　以下是各題經程式執行後的結果，和三次Lab的比較表格：

註1：三次Lab均在同機器下執行。
註2：計算時間為呼叫method System.nanoTime()，這邊所列時間為運算和製作log file合計之時間，不含顯示所花時間，三次Lab計時機制相同。

圖1  Lab2和Lab3解題時間的比較(由於4-7耗費太多時間，顯示的話難以比較出其他題的改變程度，因此不列在表中)

圖2  三個Lab解題時間比較

[sdk1-1.txt]
題目：
7 8 1 6 - 2 9 - 5
9 - 2 7 1 - - - -
- - 6 8 - - - 1 2
2 - - 3 - - 8 5 1
- 7 3 5 - - - - 4
- - 8 - - 9 3 6 -
1 9 - - - 7 - 8 -
8 6 7 - - 3 4 - 9
- - 5 - - - 1 - -

花費 7.896814 毫秒

最後結果：
7 8 1 6 3 2 9 4 5
9 5 2 7 1 4 6 3 8
4 3 6 8 9 5 7 1 2
2 4 9 3 7 6 8 5 1
6 7 3 5 8 1 2 9 4
5 1 8 4 2 9 3 6 7
1 9 4 2 6 7 5 8 3
8 6 7 1 5 3 4 2 9
3 2 5 9 4 8 1 7 6
================

[sdk1-2.txt]
題目：
- - 2 5 4 7 3 6 -
4 6 5 - - 3 - - 7
7 3 - - - 6 8 - 5
- - 6 8 1 5 4 7 9
- - - 3 6 4 5 - -
- - 4 - - - - - -
- 5 7 - - 8 - - -
- 4 - 6 - 1 - 9 -
- 9 8 7 - - - 5 -

花費 4.136559 毫秒

最後結果：
9 8 2 5 4 7 3 6 1
4 6 5 1 8 3 9 2 7
7 3 1 9 2 6 8 4 5
3 2 6 8 1 5 4 7 9
8 7 9 3 6 4 5 1 2
5 1 4 2 7 9 6 8 3
1 5 7 4 9 8 2 3 6
2 4 3 6 5 1 7 9 8
6 9 8 7 3 2 1 5 4
================

[sdk1-3.txt]
題目：
4 - - 8 9 3 2 - -
- 2 - 1 - 4 - 3 -
- 9 - - 2 6 4 - 5
- - 8 - - 9 - 5 4
- - - 3 - 1 7 2 8
3 7 - - - 5 1 - -
- 3 9 - - - - 1 7
- 8 6 - - - - - -
- - 1 - - - 9 - 2

花費 7.772217 毫秒

最後結果：
4 6 5 8 9 3 2 7 1
8 2 7 1 5 4 6 3 9
1 9 3 7 2 6 4 8 5
6 1 8 2 7 9 3 5 4
9 5 4 3 6 1 7 2 8
3 7 2 4 8 5 1 9 6
5 3 9 6 4 2 8 1 7
2 8 6 9 1 7 5 4 3
7 4 1 5 3 8 9 6 2
================

[sdk1-4.txt]
題目：
- - 7 - 6 - - 3 -
9 - - - - - 1 4 -
- 6 4 - - 5 - - -
1 - - - - 8 - - 5
- - - 5 7 - 9 1 -
5 3 9 - 4 - - 6 -
6 - - - 5 1 - 7 2
2 - - - 3 7 6 - 1
- - - 6 - - - - -

花費 2.252242 毫秒

最後結果：
8 1 7 2 6 4 5 3 9
9 5 2 7 8 3 1 4 6
3 6 4 9 1 5 2 8 7
1 7 6 3 9 8 4 2 5
4 2 8 5 7 6 9 1 3
5 3 9 1 4 2 7 6 8
6 9 3 4 5 1 8 7 2
2 4 5 8 3 7 6 9 1
7 8 1 6 2 9 3 5 4
================

[sdk1-5.txt]
題目：
- 7 - - - 2 3 - 4
- - 9 - 5 3 - - -
- - 4 - - - - - -
- - - - - - - - 8
- - - 6 - 8 1 9 -
- - 7 2 - - - 5 -
- 8 - - 1 - 4 - -
- 6 - - - - 7 - -
- 3 2 - - - - - -

花費 0.926095 毫秒

最後結果：
5 7 8 9 6 2 3 1 4
6 1 9 4 5 3 8 7 2
3 2 4 1 8 7 5 6 9
1 9 6 7 3 5 2 4 8
2 5 3 6 4 8 1 9 7
8 4 7 2 9 1 6 5 3
7 8 5 3 1 9 4 2 6
9 6 1 8 2 4 7 3 5
4 3 2 5 7 6 9 8 1
================

[sdk2-1.txt]
題目：
- 8 - - - - - - -
- 4 7 8 - 9 - - 1
- - 1 4 5 - - 2 -
8 1 6 7 - - 5 - -
9 - - - - 1 - - -
- - - 5 6 - - - -
- - - - - 8 - 5 3
- - - - - - - 8 -
- - - 3 1 - - 4 6

花費 2.110324 毫秒

最後結果：
6 8 2 1 3 7 4 9 5
5 4 7 8 2 9 3 6 1
3 9 1 4 5 6 7 2 8
8 1 6 7 9 4 5 3 2
9 3 5 2 8 1 6 7 4
2 7 4 5 6 3 8 1 9
4 2 9 6 7 8 1 5 3
1 6 3 9 4 5 2 8 7
7 5 8 3 1 2 9 4 6
================

[sdk2-2.txt]
題目：
- - - 7 - - - - 2
- - - - 3 6 - - -
- - 5 - - - - 3 -
- - 8 - - 2 5 4 -
7 - - 4 - 9 - - -
- - - - - - - - 6
- 4 3 - 7 - - 2 -
- - - - - - 9 - -
- 7 - 1 5 - - - -

花費 1.885435 毫秒

最後結果：
3 1 4 7 9 5 6 8 2
9 2 7 8 3 6 4 5 1
8 6 5 2 4 1 7 3 9
1 9 8 3 6 2 5 4 7
7 5 6 4 8 9 2 1 3
4 3 2 5 1 7 8 9 6
6 4 3 9 7 8 1 2 5
5 8 1 6 2 3 9 7 4
2 7 9 1 5 4 3 6 8
================

[sdk3-1.txt]
題目：
- - 2 - - 1 4 - -
7 - - 3 8 - - 2 6
- - 6 - - - - - 5
- - 9 - - - - - 8
1 - - - - 3 9 - -
8 - - - - 2 - - -
- - - 2 - - - - -
5 - - - - - - - 4
- - 7 - - 9 6 - -

花費 1.129753 毫秒

最後結果：
3 8 2 6 5 1 4 7 9
7 9 5 3 8 4 1 2 6
4 1 6 9 2 7 8 3 5
6 2 9 1 7 5 3 4 8
1 7 4 8 6 3 9 5 2
8 5 3 4 9 2 7 6 1
9 3 8 2 4 6 5 1 7
5 6 1 7 3 8 2 9 4
2 4 7 5 1 9 6 8 3
================

[sdk3-2.txt]
題目：
7 - 8 1 4 - - - -
- 6 5 - - - 4 2 -
3 4 - 9 - - - - -
6 - - - - - - 7 5
- - - - 9 - - 4 -
- - 3 - - - - 6 -
1 9 - 8 - 6 - - 7
- - - 4 - - - - -
5 - - - 3 - - - 4

嘗試代入次數=2
花費 7.266287 毫秒

最後結果：
7 2 8 1 4 5 3 9 6
9 6 5 7 8 3 4 2 1
3 4 1 9 6 2 7 5 8
6 1 9 3 2 4 8 7 5
8 5 2 6 9 7 1 4 3
4 7 3 5 1 8 9 6 2
1 9 4 8 5 6 2 3 7
2 3 6 4 7 1 5 8 9
5 8 7 2 3 9 6 1 4
================

[sdk4-1.txt]
題目：
4 - - - 2 3 - - -
- - - 5 9 6 7 - -
- 9 - 7 - - - - -
8 - - - - - - - -
- - 5 - - - 1 6 -
- - - - - - - 9 4
- 8 - - - - - - -
9 - - - - 2 - - 3
6 - 3 8 5 4 - 1 2

嘗試代入次數=3
花費 12.192611 毫秒

最後結果：
4 5 7 1 2 3 6 8 9
3 2 8 5 9 6 7 4 1
1 9 6 7 4 8 2 3 5
8 3 9 4 6 1 5 2 7
2 4 5 9 3 7 1 6 8
7 6 1 2 8 5 3 9 4
5 8 2 3 1 9 4 7 6
9 1 4 6 7 2 8 5 3
6 7 3 8 5 4 9 1 2
================

[sdk4-2.txt]
題目：
- 2 - - 3 - - - 4
- 1 9 - 2 - - 8 -
7 - 8 - - - - - -
2 7 6 - - 4 3 - -
8 - - - - - - - 6
- - - - 8 - - - -
- - - - 6 - - 9 5
- - - 5 - 9 - - -
- - 3 7 - - - - -

花費 0.988953 毫秒

最後結果：
6 2 5 8 3 7 9 1 4
3 1 9 4 2 6 5 8 7
7 4 8 9 5 1 6 3 2
2 7 6 1 9 4 3 5 8
8 9 4 3 7 5 1 2 6
5 3 1 6 8 2 7 4 9
1 8 7 2 6 3 4 9 5
4 6 2 5 1 9 8 7 3
9 5 3 7 4 8 2 6 1
================

[sdk4-3.txt]
題目：
- 9 4 - 3 6 2 - -
- 7 - - - - - - 5
- 3 - 4 - - - - -
- - - 8 - 1 5 - -
- 2 - - 4 - - - -
7 - - - - - - - 6
8 - - - 5 7 9 - -
- - - - - - 3 - -
- - - - - 2 - - 7

嘗試代入次數=5
花費 8.280661 毫秒

最後結果：
5 9 4 7 3 6 2 8 1
6 7 1 2 9 8 4 3 5
2 3 8 4 1 5 7 6 9
3 4 6 8 7 1 5 9 2
1 2 5 6 4 9 8 7 3
7 8 9 5 2 3 1 4 6
8 6 2 3 5 7 9 1 4
9 5 7 1 6 4 3 2 8
4 1 3 9 8 2 6 5 7
================

[sdk4-4.txt]
題目：
- - 5 - - - - - -
- - 4 8 6 - 9 - -
- - - 3 - 7 8 - -
- - - - 4 2 - - 7
- - 2 - - - - - -
1 - - - - 8 6 - -
- 8 - - 9 - 7 - -
- - - - 1 5 - - 6
6 - - - - - - - 4

花費 1.305193 毫秒

最後結果：
8 7 5 9 2 4 1 6 3
2 3 4 8 6 1 9 7 5
9 1 6 3 5 7 8 4 2
3 9 8 6 4 2 5 1 7
5 6 2 1 7 9 4 3 8
1 4 7 5 3 8 6 2 9
4 8 3 2 9 6 7 5 1
7 2 9 4 1 5 3 8 6
6 5 1 7 8 3 2 9 4
================

[sdk4-5.txt]
題目：
- 2 - - - 1 - - 4
5 - - 7 6 - - - -
- - 7 - - - - - 8
1 - 6 - - - - - -
- 8 - - - 5 - 3 -
- 7 - - - - 4 9 -
- - 8 - 3 - 5 - -
- - - 8 - - 2 - -
6 - - - 5 - 3 - -

嘗試代入次數=3
花費 5.701562 毫秒

最後結果：
8 2 3 5 9 1 7 6 4
5 1 4 7 6 8 9 2 3
9 6 7 3 2 4 1 5 8
1 5 6 9 4 3 8 7 2
4 8 9 2 7 5 6 3 1
3 7 2 1 8 6 4 9 5
2 4 8 6 3 7 5 1 9
7 3 5 8 1 9 2 4 6
6 9 1 4 5 2 3 8 7
================

[sdk4-6.txt]
題目：
- 5 - - 7 - - - -
1 7 8 - - - - - 9
- 9 6 - - - - - 3
3 - - - - 1 - - 8
- - 9 4 3 - 7 - -
- - - 2 - - 6 - -
- 3 7 - 2 - - 6 -
8 - - 3 5 - 4 - -
- - - - - - - - -

嘗試代入次數=3
花費 3.629511 毫秒

最後結果：
2 5 3 1 7 9 8 4 6
1 7 8 6 4 3 2 5 9
4 9 6 5 8 2 1 7 3
3 4 5 7 6 1 9 2 8
6 2 9 4 3 8 7 1 5
7 8 1 2 9 5 6 3 4
9 3 7 8 2 4 5 6 1
8 1 2 3 5 6 4 9 7
5 6 4 9 1 7 3 8 2
================

[sdk4-7.txt]
題目：
- 1 9 - - - - - -
- - 8 - - 3 - 5 -
- 7 - 6 - - - 8 -
- - 1 - - 6 8 - 9
8 - - - 4 - - - 7
9 4 - - - - - 1 -
- - - - - 2 - - -
- - - - 8 - 5 6 1
- - 3 7 - - - 9 -

嘗試代入次數=20
花費 24.976358 毫秒

最後結果：
5 1 9 4 2 8 7 3 6
6 2 8 9 7 3 1 5 4
3 7 4 6 1 5 9 8 2
7 3 1 2 5 6 8 4 9
8 6 5 1 4 9 3 2 7
9 4 2 8 3 7 6 1 5
1 8 6 5 9 2 4 7 3
2 9 7 3 8 4 5 6 1
4 5 3 7 6 1 2 9 8
================

三次Lab的比較表(時間取小數點第二位四捨五入)

"