《刺激消費,我是主角》心得

當代消費文化與社會 期中報告

閱讀書名:《刺激消費,我是主角》
書目作者:日野佳惠子

對於當今社會物質富裕已經為大多數人的基礎,因此消費行為也越來越特異化,從注重環保以及各種責任意義,消費的著重點也有所不同。

如何聰明消費?或者說消費出聰明的價值?的確有一股取向,有錢人的消費模式在於大批購買,而我們這種一般人對於聰明的消費是相當自豪的,聰明消費能夠展現自己能在低價購入高品質的產品,這裡的低價就不單單只是低消費額,是一個相對於產品應有的價值之下。在這股潮流之下,依賴情報消費真的很重要,因此也易受於口碑品牌的影響。就如比特幣剛出時,大批人覺得是一個未來重要的貨幣商品而大量購買 … 等。

如果徵才也是互動型的消費,文中說明消費者若有貢獻出一己之力的機會,將會更容易讓其主動消費,例如廣告為『我們想像身為家庭主婦的您,購買做家事的能力與烹飪能力』比起『時薪 OO 徵才』好太多了,文中所提的例子相當有感,能對別人有所助益,即使中間的過程是消費的一環,也是相當具有自願性的行為。不單單只是為了個人去購買商品,同時也是為了其他外界因素而進行消費。如同當初 Firefox 打擊微軟的 IE 手法,提供開源代碼的方式,希望其他人參與這場攻防戰,願意幫助這個軟體更完善,在不花一毛錢的情況下,這個組織靠著消費者活到了至今。

模仿身邊的人進行消費,如果這個商品是對於土豪們為取向,那麼消費族群也總是那一群,需要靠身邊親朋好友的消費習慣來渲染自己,如果身邊沒有人這麼消費,那要成為第一個購買者的機會是相當低的,因此企業常會用親民的代表人物來推銷自己的商品。我相信在相同處境下,需求是彼此靠攏的。這有點粒子群聚算法的感覺。

『對於不懂得使用方法的人,不了解真正含義的人,無法因商品獲得快樂的人而言,即使技術再進步,一切都是毫無意義。』看到這一句話,越來越明白消費的同時也是在教導,如果單純只是想要擴張客源,沒有好好教導消費者如何使用也是不行的。

『消費者也是加工者,開創低價商品交給消費者加工,並且銷售宣傳』由於消費者不喜歡與別人相同,又想要做出自己的風格,低價商品的拓展性就變得相當高了,低價商品通常有著量多便宜的特性,譬喻成大自然的元素也不為過。想到這一點,有人開發出有前景的軟硬體,通常會湧出一批人去購買,並且修正或運用然後進行傳播,這影響力堪稱指數擴張。這也應對消費者也是企業的助手,一群消費者就是一大群的應援團,將與企業或產品一同發展。

『不消費的智慧』雖然使得商品沒有利益,但是這也表示新的消費可能再也不是利益,而是商品後頭的智慧,看著越來越多的消費手法,沒有智慧學習的商品,除了一般生活所需外,在未來可能很難遍及市場,娛樂市場又是另外一回事。

『把整個環境一同賣給你』即使商品單獨具有高性能,沒有環境展現其性能事件很糟糕的事情,就如蘋果電腦和軟體總是整包出售,兩項缺一不可。而最近微軟最近正有著附上環境出售的趨勢,不過搭配性不強,跟裸機差不多。

Read More +

作業系統 筆記 (1)

讀物

現在恐龍書不知道第幾版了,而且中文翻譯有點慘。看英文原文又太慢的情況,剛好查到聯合大學陳士杰教授寫的 ppt。繁體中文的說明,採用恐龍書第七版的內容。

下附章節簡報和課後習題解答。

稍微看過每一章的內容後,就可以著手看習題解答。

CH 1
CH 2
CH 3
CH 4
CH 5
CH 6
CH 7
CH 8
CH 9
CH 10

恐龍書課後習題解答 感謝大大的提供

之前也有好幾次參照教授寫的中文簡報,相當有助益。

可能遭遇的問題

個人拙見,請自行過濾

Round-Robin Scheduling

  • 這個問題在寫考題的時候,略顯著的疑惑。
  • 對於 Round-Robin Scheduling 的部分
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    queue Q
    while(true) {
    w = Q.front()
    w = work(w)
    if(hasProcess())
    Q.push(nextPorcess())
    if(w != null)
    Q.push(w)
    time++
    }
    詳見代碼後,由於超過時限後,還要將變數存起來,所以丟入 queue 的時間會晚一點,也就是說在同一時刻會慢於新抵達的 process。之後的程序就按照 queue 的順序去運行。

考古題(課本後習題)

(=゚ω゚)= 下附解答僅個人拙見,請勿隨意採信,請發揮您的善心,救救笨蛋

95 期中考

  • What is multiprogramming ? what is time-sharing ?(10%)

    • Multiprogramming(多重程式):

      • 定義:
        內存有多個 processs 同時執行,一般電腦的運行方式。透過 CPU scheduling 將發生中斷 (eg. wait for I/O complete, resource not available, etc.) 的行程切換給可執行的運作。
      • 特色:
        可以避免 CPU idle,提高 CPU utilization(使用率)
      • 其他:
        1. Multiprogramming Degree:系統內存在執行的 process 數目
        2. 通常 Multiprogramming Degree 越高,則 CPU utilization 越高(p.s. ch7 Thrashing 除外)
        3. 多個 process 同時執行,mode 有兩種 Concurrent(並行)、Parallel(平行)
    • Time-sharing:

      • 定義:
        Multiprogramming 的一種,在 CPU 排班法則方面,其使用 RR(Round-Robin) 法則。
        // RR 法則-CPU time quantum,若 process 在取得 CPU 後,未能於 quantum
        // 內完成工作,則必須被迫放棄 CPU,等待下一次輪迴。
      • 特色:
        對每個 user 皆是公平的,適用在 user interactive 且 response time (反應時間)要求較短的系統環境,透過 resource sharing 技術(eg. CPU scheduling, memory sharing, spooling 達到 I/O Device 共享),使得每個user皆認為有專屬的系統存在。
  • Describe the differences between symmetric and asymmetric multiprocessing. What are three advantages and one disadvantage of multiprocessor systems ?
    In Distributed System - Multiprocessor - Tightly-Coupled System(different from Loosely-Coupled Distributed System)

    • Symmetric Multiprocessors (SMP) 對稱式多處理器
      • 定義:
        每個 processor 的能力皆相同,即可負責的功能完全一樣。萬一某個 processor 壞了,其上工作可由其他processor 接手,系統不會整個 crash,只是整體效能下降而已。
      • 特色:
        Reliability (可靠性)大幅提升,強調 load balancing (負載平衡)(每個CPU的工作負擔相同)
    • Asymmetric Multiprocessors (ASMP) 非對稱式多處理器
      • 定義:
        不同(群)顆的 processor,其負擔的功能不盡相同,在此架構下,通常含有一個Master CPU,負責工作的分派與協調,其他 CPUs 稱為 Slave CPU (稱為 Master-Slave Architecture)
      • 特色:
        效能通常較SMP高,但可靠度較差
  • What are the differences between a trap and an interrupt? What is the use of each function ?
    • Trap:
      軟體產生 system call
      an exception in a user process.
      ex. system call (software divide-by-zero)
    • Interrupt:
      硬體產生 signal
      something generated by the hardware.
      ex. IO-complete interrupt (hardware generated)
    • 兩者相同之處
      從 User Mode 切換到 Kernel Mode。
      兩者都算是 interrupt 中斷指令。
  • What is the purpose of system calls?
    System calls allow user-level processes to request services of the operating system.
    System calls 提供 使用者級別 的程序來請求作業系統給的服務。
    // process control, file Management, device management, information maintenance, communication
  • Describe the differences among short-term, medium-term, and long-term scheduling.
    • short-term (CPU scheduler) —
      CPU 工作排程
      selects from jobs in memory those jobs that are ready to execute and allocates the CPU to them.
    • medium-term —
      常用於分時系統的排程器。當記憶體不夠的時候,需要暫時將部分的執行程序搬出,將新來的程序載入,置換機制被建置用來移除部份在記憶體執行中及恢復那些被暫時移除的程式。
      used especially with time-sharing systems as an intermediate scheduling level. A swapping scheme is implemented to remove partially run programs from memory and reinstate them later to continue where they left off.
    • long-term (job scheduler) —
      將 job 變成 process 的工作排程,將工作從硬碟載入到主記憶體中。
      determines which jobs are brought into memory for processing.
  • Can a multithreaded solution using multiple user-level threads achieve better performance on a multiprocessor system than on a single-processor system? Why?
    • A multithreaded system comprising of multiple user-level threads cannot make use of the different processors in a multiprocessor system simultaneously. The operating system sees only a single process and will not schedule the different threads of the process on separate processors. Consequently, there is no performance benefit associated with executing multiple user-level threads on a multiprocessor system.
    • 以 user-level hreads 實現 multithread 的程式,在多處理器系統中不能比在單處理機系統中有更好的效率, 因在多處理機系統中之作業系統不會將多個 CPU 同時分配給該 user-level multithread 程式。
  • Consider the following set of processes, with the length of the CPU-burst time given in milliseconds:

    Process           Burst Time         Priority
      P1                 10                  3
      P2                  1                  1
      P3                  2                  3
      P4                  1                  4
      P5                  5                  2
    

    The processes are assumed to have arrived in the order P1,P2,P3,P4,P5, all at time 0.

    • (a) Draw four Gantt charts illustrating the execution of these processes using FCFS, SJF, a nonpreempitive priority(a small priority number implies a higher priority), and RR(quantum = 1) scheduling.(5%)
    • (b) What is the turnaround time of each process for each of the scheduling algorithms in part(a).(5%)
    • (c) What is the waiting time of each process for each of the scheduling algorithms in part(a).(5%)
    • (d) Which of the schedules in part (a) results in the minimal average waiting time(over all processes)? (5%)

      請參照上附的習題解法。
      

      5.12 solution


96 期中考

  • FCFS, SJF, Priority, Round-Robin and Multilevel Queue
    Which can be preemptive ? (5%)

    • preemptive 可搶先
      SRTF (剩餘最短優先)、Priority (優先權優先)、Multilevel Queue (多層佇列)、RR
    • non-preemptive 不可搶先
      FCFS (先到先服務)、SJF (最短工作優先)、Priority (優先權優先)
    • Priority (優先權優先) 屬於可搶先跟不可搶先。
    • 可搶先的定義為非自願性被踢出 CPU。
  • What are the four main purposes of an operating system ? (10%)

    • Managing programs
    • Managing Memory
    • Handling input and output
    • User Interface
  • Please give a detail description on the differences among the terms multiprocessing, multitasking and multithreading. (15%)

    • multiprocessing
      具有多個處理器,在同一時間可以在各自處理器上運行程序。
    • multitasking
      執行單一使用者的多個行程,利用排程器讓每一個行程都在平均時間內解決。
    • multithreading
      可以將程序切成好幾個執行緒,若硬體可以同時執行多個執行緒,效率將會上升,如果不能,由於速度夠快看起來也很像多個執行緒同時運行。
  • What are the differences between a trap and an interrupt ? What is the use if each function ? (20%)

    • Trap:
      軟體產生 system call
      an exception in a user process.
      ex. system call (software divide-by-zero)
    • Interrupt:
      硬體產生 signal
      something generated by the hardware.
      ex. IO-complete interrupt (hardware generated)
    • 兩者相同之處
      從 User Mode 切換到 Kernel Mode。
      兩者都算是 interrupt 中斷指令。
  • What is the purpose of system calls, Please describe three general methods that be used to pass parameters to the operating system. (10%).

    • System call 由作業系統提供 API interface 給 user program,可以藉由 system call 向作業系統請求服務,作業系統接收到請求後,執行完報告結果給 user program。
    • [方法1] Registers
      利用Registers ( 暫存器 )儲存這些參數
      優:速度快
      (∵不用作記憶體的存取 )
      缺:不適用於參數個數多的情況
    • [方法2] Memory
      將參數利用 Table 或 Block 的方式儲存在 Memory 中,同時利用一個 Register 記錄此 Table 或 Block 的起始位址,並傳給O.S.
      優:適用於參數個數較多的情況
      缺:速度慢
    • [方法3] Stack
      利用System Stack (堆疊 )。要存放參數時,將之Push 到Stack Stack, 再由O.S.從Stack中Pop 取出參數 。
      Stack在系統中比Register多一些(可用Mem. 或其它硬體(如:Register)來實作此Stack)
  • What is a process ? Draw the diagram of Process State. And describe every state. (15%)
    process state

  • What are the differences between thread and process ? Why do threads have much shorter context switching times ? (10%)

    |        Thread                   |      Process              |
    |---------------------------------|---------------------------|
    | Light Weight Process            | Heavy Weight Process      |
    |                                 |                           |
    | 同一個Task (或 Process ) 內的   |  不同的Process之間無共享的| 
    | Threads可以共享 Code Section,   |  Address Space,互為獨立。|
    | Data Section, 及O.S. Resources  |                           |
    |                                 |
    | Context Switching 負擔輕        |  負擔重
    |                                 |
    | Thread的管理(Management)成本低  |  成本高
    | (管理項目: Creation,           |
    | Scheduling, Context, Switching  |
    | Switching…etc.)                 |
    |                                 |
    | 一個Task內有多條Threads存在     |  一個Task內只有一條Thread
    |  Process (Task) 內的某 Thread   |
    | 被 Block,則可切到其它Thread    |
    | 執行。此時,若 Process 內只要還有
    | Thread 在執行,則 Process 不會被 Block
    
  • What is Multilevel Feedback-Queue scheduling ? (5%)

    定義:
    與Multilevel Queue的定義相似,差別在於允許 Process 在各佇列之間移動 ,以避免Starvation 的情況。
    * 採取類似 “Aging” 技術,毎隔一段時間就將 Process 往上提升到上一層 Queue 中。∴在經過有限時間後,在 Lower Priority Queue 中的 Process 會被置於 Highest Priority Queue 中。故無 Starvation。
    * 亦可配合降級之動作。當上層 Queue 中的 Process 取得 CPU 後,若未能在 Quantum 內完成工作,則此 Process 在放棄 CPU 後,會被置於較下層的 Queue 中。
    
  • Please draw the Gantt charts for the following processes for the problems shown below.
    (a) Round-Robinm time quantum = 1 (5%)
    (b) Shortest-remaining-time-first (Preemptive SJF) (5%)

                Arrival Time    Brust Time
    
        P1      0               4
        P2      1               2
        P3      2               3
        P4      5               4
        P5      6               3
    
    (a) Time : 0
        Queue: P1
    
        0   1
        +---+
          P1
    
        先丟入 P2, P1 因為超時丟入,此時執行 P2
        Time : 1
        Queue: P2, P1
    
        0   1   2
        +---+---+
         P1  P2
    
        丟入 P3, P2 因為超時丟入,此時執行 P1
        Time : 2
        Queue: P1, P3, P2
    
        0   1   2   3
        +---+---+---+
         P1  P2  P1
    
        P1 因為超時丟入,此時執行 P3
        Time : 3
        Queue: P3, P2, P1
    
        0   1   2   3   4
        +---+---+---+---+
         P1  P2  P1  P3
    
        P3 因為超時丟入,此時執行 P2
        Time : 4
        Queue: P2, P1, P3
    
        0   1   2   3   4   5
        +---+---+---+---+---+
         P1  P2  P1  P3  P2
    
        P2 完成,P4 抵達丟入,此時執行 P1
        Time : 5
        Queue: P1, P3, P4
    
        0   1   2   3   4   5   6
        +---+---+---+---+---+---+
         P1  P2  P1  P3  P2  P1
    
        P5 抵達丟入,P1 超時丟入,此時執行 P3
        Time : 6
        Queue: P3, P4, P5, P1
    
        0   1   2   3   4   5   6   7
        +---+---+---+---+---+---+---+
         P1  P2  P1  P3  P2  P1  P3
    
        P3 超時丟入,此時執行 P4
        Time : 7
        Queue: P4, P5, P1, P3
    
        0   1   2   3   4   5   6   7   8
        +---+---+---+---+---+---+---+---+
         P1  P2  P1  P3  P2  P1  P3  P4
    
        P4 超時丟入,此時執行 P5
        Time : 8
        Queue: P5, P1, P3, P4
    
        0   1   2   3   4   5   6   7   8   9
        +---+---+---+---+---+---+---+---+---+
         P1  P2  P1  P3  P2  P1  P3  P4  P5
    
        P5 超時丟入,此時執行 P1
        Time : 6
        Queue: P1, P3, P4, P5
    
        0   1   2   3   4   5   6   7   8   9  10
        +---+---+---+---+---+---+---+---+---+---+
         P1  P2  P1  P3  P2  P1  P3  P4  P5  P1
    
        P1 完成,此時執行 P3
        Time : 10
        Queue: P3, P4, P5
    
        0   1   2   3   4   5   6   7   8   9  10  11
        +---+---+---+---+---+---+---+---+---+---+---+
         P1  P2  P1  P3  P2  P1  P3  P4  P5  P1  P3
    
        P3 完成,此時執行 P4
        Time : 11
        Queue: P4, P5
    
        0   1   2   3   4   5   6   7   8   9  10  11  12
        +---+---+---+---+---+---+---+---+---+---+---+---+
         P1  P2  P1  P3  P2  P1  P3  P4  P5  P1  P3  P4
    
        ...
    
        0   1   2   3   4   5   6   7   8   9  10  11  12  13  14  15  16
        +---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+
         P1  P2  P1  P3  P2  P1  P3  P4  P5  P1  P3  P4  P5  P4  P5  P4
    

課本習題快取區

ch 5

  • 5.9 Why is it important for the scheduler to distinguish I/O-bound programs
    from CPU-bound programs?
    為什麼排程器需要需分 IO 密集程式 CPU 綁定程式 ?

Answer: I/O-bound programs have the property of performing only a small amount of computation before performing I/O. Such programs typically do not use up their entire CPU quantum. CPU-bound programs, on the other hand, use their entire quantum without performing any blocking I/O operations. Consequently, one could make better use of the computer’s resouces by giving higher priority to I/O-bound programs and allow them to execute ahead of the CPU-bound programs.
IO 密集程式占用 CPU 的時間比較少,大部分時間等在等待 IO。相反地 CPU 綁定程式則會大幅度占用 CPU 的時候,因為沒有 IO 操作的堵塞。

而 CPU bound 的程序因此而得到了很多調度機會並且每次都能把CPU run完。故在這樣的系統裡要給 I/O bound 的程序更高的優先級使其能被調度得更多些。

  • 5.10 Discuss how the following pairs of scheduling criteria conflict in certain
    settings.
    a. CPU utilization and response time // CPU 使用率 和 回應時間 的比較
    b. Average turnaround time and maximum waiting time // 平均運轉時間 和 最大等待時間 的比較
    c. I/O device utilization and CPU utilization // IO 裝置使用率 和 CPU 使用率 的比較

Answer:
a. CPU utilization and response time: CPU utilization is increased if the overheads associatedwith context switching isminimized. The context switching overheads could be lowered by performing context switches infrequently. This could, however, result in increasing
the response time for processes.
CPU 的使用率(utilization)上升時,切換工作的次數(context-switches)就會少,由於切換次數少,則回應時間(response time)就會上升。

b. Average turnaround time and maximum waiting time: Average turnaround time is minimized by executing the shortest tasks first. Such a scheduling policy could, however, starve long-running tasks and thereby increase their waiting time.
平均運作時間(average turnaround time) 的最小化可以藉由最短工作優先的方式,但是這將會使得長工作飢餓,如此會增加最大等待時間。

c. I/O device utilization and CPU utilization: CPU utilization is maximized by running long-running CPU-bound tasks without performing context switches. I/O device utilization is maximized by scheduling I/O-bound jobs as soon as they become ready to run, thereby incurring the overheads of context switches.
CPU 使用率的上升盡可能讓 CPU 密集工作長時間運行 (減少 IO 或者其他的中斷所引發的上下文切換),IO 裝置使用率的上升靠的是讓排入的 IO 密集工作立即地運行,但這會增加上下文切換的開銷。

  • 5.11 Consider the exponential average formula used to predict the length of the next CPU burst.What are the implications of assigning the following values to the parameters used by the algorithm?
    使用指數平均公式去預測下一次的 CPU burst。 t0 預估時間。
    a. a = 0 and t0 = 100 milliseconds
    b. a = 0.99 and t0 = 10 milliseconds

Answer: When a = 0 and t0 = 100 milliseconds, the formula always makes a prediction of 100 milliseconds for the next CPU burst. When a = 0.99 and t0 = 10 milliseconds, themost recent behavior of the process is given much higher weight than the past history associated with the process. Consequently, the scheduling algorithm is almost memoryless, and simply predicts the length of the previous burst for the next quantum of CPU execution.
當 a = 0 時,預測的時間總會是 100 milliseconds,而當 a = 0.99 時,將會高度依賴近期幾次的結果,而對於歷史關聯只有較輕的權重。
// t(n+1) = a * 上一次實際時間 + (1 - a) * t(n)

Reference

Kernel Mode 與 User Mode 的概念
恐龍書中文 ppt 介紹 聯合大學 陳士杰

Read More +

大學專題紀錄 Universities Project

Morris’ 大學專題

前言

大學專題時間為期一年,分為上下兩學期習滿才能畢業,但有些科系不是,但多少資工系基本上都是的,沒有修過專題,就相當於只是寫學校作業!如何研究與邁向下新的目標,這將會是專題給您的經驗。

怎麼選專題教授

首先,先來區分教授類型。

  • 自由放任型
    您的專題將會任您發展,同時也是掛名的教授,相當建議有想法的同學們去選,畢竟想做想學的事情可能很多,中間變卦也是常有的事情,但您必須真的有去學到知識的衝勁。但有自主學習動力的人少之又少,更別說學習目標的定論,如果您是那種不管課業上什麼,都會額外深入學習者 … 或許您有那股潛力。
  • 學術研究型
    您將會開始看論文,並且實作和學習。身邊人沒什麼聽聞。
  • 產學合作型
    您將會用基礎程式和教授專長去討論做出相關產品,至於有沒有深入了解產業需求和教授專長領域又是另一回事情了。這是最有可能產出作品的,如果想要在面試中講講大學做了什麼成果,大概這是最有機會的一群。
    但是必須得明白,有作品不見得是好事,也就是說沒有實質學習和產出品質,也只是陡增垃圾。
  • 業界指導型
    相較於產學合作,告訴您宏觀的慘業現況,並且指導走入業界環境,突破學習的局限與個人思維,通常是屬於資訊系所中偏向軟體開發教授們的領導風格。

選教授要看個人性格,如果平常不怎麼專注於學習者,就跟著最要好的小夥伴們選吧。

而雖然對於 ACM 算法競程稍有經驗,可能就會被旁人認為要去玩學術研究,不過學術研究也是相當嚴苛的一條路,沒有想法沒有產出,那可是會逼死人的,只有一年的學習專題(當然有人會無限延長),最後選了軟體工程來玩玩,結果沒想到跟以前所寫的 ACM 那套可說是八字相剋。

於是漫長的旅行就開始了 …

何時修專題課程

專題要不要產出

很多人一直都想要有個成果發表展之類的,或者是可以張貼海報展覽的機會,看起來會留下美好的紀錄,且認為相當有機會在面試的時候被提及,以免被問到時,什麼都沒有得說。

但是請自行思考,這是唯一的成果製造流程?

進度狀況

  • 上學期為軟體工程圍觀

    • 程式基礎-物件導向,軟工產業介紹

      只會寫學校作業是不夠的,產業界要的不是這種人。

    • 修習物件物件導向課程
      雖然以前修過物件導向,但是相當輕描淡寫,真正應該是要學到 Design pattern 、資料表單的建造後,才算學過物件導向,否則只是濫用三大利器繼承、多型、封裝。

      學過、學會、應用 乃屬三個階段,少自以為是。

    • 工具的重要性

      如何用好工具將會給予後期強大的助力開發。

    • 開發前奏曲 prototype 的製作與重要性
      與業界需求產出網頁 prototype,使用 JQuery, HTML。

      相當慘淡,經驗沒到,思維不足,無法造出需求結果。

  • 下學期為軟體工程入門

    • 跟著 Mozilla 導師們學習
      • Sprint meeting
      • GitHub
      • Nodejs
      • FirefoxOS - gaia // 環境卡太久,什麼都還沒學到就胎死腹中

階段性

學習條目

結語

Read More +

計算型智慧 - 學習 (Computational Intelligence)

計算型智慧

文章簡介

  • 下學期修了這門課,這其中會與另一門類神經網路有關。
  • 中間穿插工數和微積分的一些數學名詞。
  • 接著,您將會看到一系列筆者對計算型智慧的認知。
  • 看到以下內容,雖有數學模型、演算法成份,但主體為模擬自然界的各種思維。

算法設計

特定型最佳化法則

根據函數的特性,衍伸出來的搜尋方式,目標函數有特別性質,例如:線性、微分 … 等。微分法、梯度法都是屬於此類。再講白一點,一般大學時學的演算法都是如此,通常是具有最佳化結構的情況,因此會有最短路徑算法、二分搜尋、三分搜尋 … 等。

廣義型最佳化法則

不管目標函數的特性為何,無須修改設計法則,亂做一通、隨機搜索、以及接下來講的主題都屬此類。

模糊系統

模型簡介

  • 一般程式撰寫判斷條件相當精準,同時也不好做修正,畢竟一般人看不懂那麼多 if-else 語句。
  • 那有沒有更好一點的描述方式?這就是接下來要講的。
  • 如果硬要說明,模糊系統相當於一個精準輸入→亂來一通→精準輸出,也就是多了中間那個過程。

模型介紹

  • 是或不是,僅有 0/1 描述。
    真實世界是按照是的相似度有多高,不是的話就是有多高。或者描述多是有多多,少是有多少。

  • 歸屬函數 (membership function)
    值介於 [0, 1] 同時也是相似度的描述。
    詳細請參照 wiki 模糊集

  • 模糊關係 (fuzzy relation)
    簡單的說,一般用稀疏矩陣是用 N * N 的陣列,並且裡面存放 0/1 數值,但是在模糊關係中,將會使用 [0, 1] 之間的實數來代替。
    詳細請參照 wiki 模糊關係

    • 有什麼樣的操作 ?
      對於關係運算,也有關係合成或者是條件機率。對於關係合成就可以自訂函數來合成,而條件機率通常會使用積分去查閱,但是模糊關係至少三維空間 (因為多一個歸屬函數值),所以必須走投影擴充的方式,當然可能有其他的做法。
  • 單一規則,單一變數
    if x = p, then y = q.
    模糊起來

    x = p 的關聯性多少,y = q 的多少比率。
    

    舉個例子來說

    x 相當靠近 p, 假使說相似度 50%, 則 y = 0.5 * q
    

    以上是函數是說法,當然您可以自由選擇越接近反而越低,或者是客製化。

  • 單一規則,多變數
    if x1 = p1 and x2 = p2, then y = q

    • 由上一條,會有一點想法,那把兩個相似度取最小值如何?或者是相乘(假使相似度小於 1)。
    • 模糊沒有標準答案,覺得合理就行。
  • 單一規則,多變數
    if x1 = p1 or x2 = p2, then y = q

    • 由上一條,會有一點想法,那把兩個相似度取最大值如何?或者是相加後約束小於 1。
    • 模糊沒有標準答案,覺得合理就行。
  • 多規則,單一變數
    if x1 = p1, then y1 = q1
    if x2 = p2, then y1 = q2

    • 再藉由上一條相乘,那接著相加如何?還是要來個加權平均?
    • 一樣沒有標準答案,加權就是拿相似度出來當權重。
  • 多規則,多變數
    想必已經自動推論出來,在此就不多說。

  • 怎麼來亂?(隨便說說)

    • 函數式:多少相似度 p 根據多項式 f(p) 產出 y 值。
    • 語意式:畫出 f(y) = p 的圖,計算 p 所占有面積的面積(劃一條線取交集),來決定 y 要取多少。
    • 中間要不要遵守遞移律、交換律、結合律?照理來講是要的。
      不過想吐槽的是,都這麼模糊了,還要遵守這三律嗎?
      
  • 建造模糊規則

    • 通常由有經驗的專家口頭描述,然後讓程式慢慢演化。
    • 如果沒有專家可問,先把參數空間做切割,分別定義產出。
      最簡單的大小分,如果有 n 個參數,將會產出 2^n 個空間,定義起來就很累。
      
  • 模糊化類神經網路 … 略

結語

  • 運算方式,跟編程複雜度有關。
  • 函數式最好寫,但是彈性不高,產出結果通常有限(多樣性)。
  • 如果採用非連續性的就很痛苦,通常會使用離散化取數值分析,可用重心法。
  • 有重心法、肯定有眾數、中數法。
  • 一般來說函數式就夠用,世界萬物都是簡單構成複雜。
  • 可以利用收集資料,讓類神經網路產生演化結果 (稍後會提到),神經應該也是模糊的!
  • 收集到的資料正確性不知道有多高,根據簡單的投影法則,也可以變成模糊系統(初版)。

模擬退火

簡介

「模擬退火來自冶金學的專有名詞退火。退火是將材料加熱後再經特定速率冷卻,目的是增大晶粒的體積,並且減少晶格中的缺陷。」取自 wiki

簡單的說,膨脹去雜質,冷卻來精煉。冷卻得到區域最佳解,膨脹增加得到全局最佳解的機率。

操作

  • 以 f(x, y) = z 的函數,要找到全局最小值,圖形看起來就是 3D 模型。
    水往低處流,人往低處走
    
  • 當現在在 (x, y) 時,笨的方式就是往四處看看,看哪邊更小就往哪裡走出下一步。而高明的作法則是根據梯度(微分來了)低的地方走,您就講想您有一個重力感測器。
  • 步伐將會越來越小,這樣才能步步靠近區域最佳解。
  • 當相當靠近區域最佳解時,變小幅度(dx/dt)太小,那就跳到更遠的地方去吧,相當於容忍較差的環境。
  • 什麼時候容忍?可以根據某些指數函數結果跟隨機亂數比大小。

結語

  • 寫 ACM 題目時,通常會選擇隨機撒點,然後對於每一個點根據相同步伐走相同步數,逐一縮小步伐。因為跳出的容忍不好設計。
    foreach 隨機點
        for stepSize big to small
            for i = 0 to stepCount
                四處看看找更好的,Update 當前隨機點。
    
  • 簡單運用,找出多邊形費馬點、最小覆蓋圓 … 等。
  • 與隨機搜索差別在哪?隨機搜索相當於對每個子空間猜測,分布密度高才會準,空間越大,連區域最佳解都得不到。
  • 講到區域最佳解-看看咱們的政治人物,不外乎都是講那些事情,這樣就是區域最佳解。思維跳脫機率不夠高,看來是火不夠大。

基因算法

簡介

又稱 GA 算法,模擬生物遺傳的過程,根據「物競天擇,適者生存」的演化論,最後會得到最好的解答。而進行演化就是染色體的事情了,當一開始的多樣性夠,再搭配突變情況交織出來,那崇高的自然藝術便會出現。

看看人類,您覺得有適者生存嗎?那這樣會進化嗎?
有空去搜尋電影-《蠢蛋進化論》看看不願面對的真相?

操作

  • 將資料表示成基因片段,最簡單為二進編碼,當然也可以用實數。
    資料是什麼?函數的常數參數,來驅使我們的模型可以更接近收集出來的數據。
  • 第一步-初始化物種
    隨機產生基因片段,或者來個生物大滅絕保留可能好的再隨機生成。
  • 第二步-適應環境
    越接近收集出來的數據(差值總和越小),適應力越高。這就相當於成長階段。
  • 第三步-擇偶
    通常適應度高的會配在一起,就如人類有反例,這沒有絕對。
  • 第四步-交配
    交配方式如同染色體行減數分裂後的運作,將某幾段進行交換,而生物染色體只會切一刀然後配對,因為當初的雙股螺旋 … 各種原因,反正就是生物物質關係。如果是實數,則可以想像成會生成拉近關係或者是拉遠關係的結果。

    兩個好的物種交配,也不見得子代會好。

  • 第五步-突變
    個體突變,染色體的 01 互換機率,或者在實數方面特化或者是弱化(就是乘實數)。

設定集

  • 基因種類

    • 一般型基因原則
      DNA[i] 只會有 0 或 1
    • 實數型基因原則
      DNA[i] 可以是任意實數
    • 為什麼這麼分類?IEEE floating-point format 感覺不是好的方法?請自行思考,其中最大的原因是不應該侷限基因。
  • 一般型交配手法

    • 單點交配
      對兩段基因,隨機找索引 i,交換索引 i 之後的所有基因。
      i = rand_generate();
      for j = i to length
          swap(dna1[j], dna2[j])
      
    • 兩點交配
      與單點交配類似,不過是找一個區間 [l, r] 進行交換
      for i = l to r
          swap(dna1[j], dna2[j])
      
    • 字罩交配
      隨機挑數個隨機位置做交換。
    • 更多,您可以妄想。
  • 實數型交配手法

    DNA1[i]' = DNA1[i] + k * (DNA1[i] - DNA2[i])
    DNA2[i]' = DNA2[i] - k * (DNA1[i] - DNA2[i])
    k 取 [-1, 1] 的微量亂數。
    
  • 繁殖
    因為繁殖池大小有限,物種數量將會被約束。

    • 輪盤式選擇
      根據適應函數反應分布群族大小,四捨五入填滿整個繁殖池。
    • 競爭式選擇
      每次隨機挑選兩個,對於這兩個挑一個好的留下,直到繁殖池滿。
  • 更多設定

    • 基因長度:
      反應精準度、編碼方式。
    • 交配機率:
      機率高,容易產生混種!看看混血兒多聰明且吸引人,通常子代就不是如此。
    • 突變機率:
      機率太高反而是隨機搜索,調適好相當於爆炸式搜索。
    • 適應函數:
      如何反應好的物種?

結語

  • 應用-使用類神經網路的模型,利用基因算法找到最佳解。而每個神經元都有搭配的參數,就是把參數基因化,調用基因算法。
    幾句話說明類神經網路

    每個神經元根據所受到的刺激產出一個定值,而神經元也有階層關係,每一個階層間會互相刺激,最外層吸收外界資訊,慢慢細化傳入最後階段的神經元來反應。而 ‘刺激到產出’ 可以猜想為加權平均。

  • 實作後,這種算法必須應用在接近連續層面上會比較好,離散函數的問題效果不彰,也就是會有一些額外的判斷條件。
  • 擇偶相當困擾,通常根據隨機亂數,在排序後做選擇。
  • 交配相當刺激,同時也是最難抉擇的地方,個人造化。
  • 要不要適應繁殖?都行,適應好的物種就多複製幾個!// 看您要不要固定,不然數量會爆炸,或者加入篩選。
  • 大量繁殖大量突變,造就爆炸效應!(在鄰近空間進行爆炸找更好的地方)
  • 最後根本就是在玩突變,突變算法就此誕生!

螞蟻算法

簡介

螞蟻單一功能低,群體完成最佳化。螞蟻行動過程中會留下費洛蒙,隨著時間費洛蒙也會下降,在這反反覆覆的過程中,蟻群很有機會開創出全局最佳解。

螞蟻雖小,亦能驅象。

操作

  • 鮮少有人根據時間做迭代模擬的基底。
  • 由於模擬上相當困難,所以來點不科學的寫法,但仍要抓住費洛蒙的核心。
  • 第一版本-對於最短路徑搜索
    • 決定有多少隻螞蟻
    • 所有路徑上的費洛蒙初始為 0。
    • 決定要跑多少次迭代
    • 每次迭代,依序放出螞蟻,螞蟻會根據路徑上費洛蒙隨機走(也並不是越高越好),對於走比較好的路徑,將其走過路徑上的費洛蒙濃度增加。
    • 每次迭代,消散一點費洛蒙,來減少重複的錯誤區域解。
      這樣有什麼缺點?因為是依序放出螞蟻,所以相當不自然。
      再者每隻螞蟻還要有能力記錄走過的路徑。
      螞蟻的記憶能力有多高?
      
  • 虛擬碼

    Initialize
        Loop /* at this level each loop is called an iteration */
            Each ant is positioned on a starting node
            Loop /* at this level each loop is called a step */
                Each ant applies a state transition rule to     incrementally build a solution and a local pheromone     updating rule
            Until all ants have built a complete solution
            A global pheromone updating rule is applied
        Until End_condition
    
  • 第二版本-收集食物

    • 決定有多少隻螞蟻,並且隨機撒下。
    • 每隻螞蟻會搜索鄰近的食物
    • 根據概率撿起某個食物,朝向費洛蒙高的地方搬運。
    • 再根據概率將食物放下,放下時增加該地費洛蒙。

設定集

  • 費洛蒙的濃度消散函數
  • 螞蟻根據費洛蒙濃度的選擇函數
    • 不遵守?機率為何?
    • 遵守?又是根據什麼條件機率。

結語

  • 應用方面
    • 分群,把文章分類。
    • 搜索,各種 NPC 問題都可以拿來玩玩。
  • 小遊戲
    感覺攻城遊戲對於這方面相當有意思,不過此遊戲有炒地皮的設定,基礎建設越來越貴,各種不科學的情況,七八千分還算正常人吧,沒有搭載最佳化系統的素人。
  • 另外可見 DJWS的說明

粒子算法

簡介

英文名稱 Particle Swarm Optimization,粒子群聚演算法。看過鳥群群舞嗎?魚群穿梭嗎?

鳥群
圖片來源地址

在相互模仿效應中,牠們會向鄰近學習,部分保留、部分學習,這也是向其好的一面靠攏。

借由互相學習來調整群體面向,最後演化應該是會非常接近的群體。以人類來說,演化時間還不夠久 看起來個體智慧與能力的分歧度還相當大。根據演化結果,由於互動機率因歧異性而下降,導致演化不會趨近于一。

粒子演算法三項重點:評估,比較,模仿

  • 評估 - 目標函數值
  • 比較 - 根據評估結果比較,根據機率還是特定條件符合後
  • 模仿 - 將部分屬性(參數)模仿過來

操作

  • 一開始把族群撒在特定區域,並且賦予牠一個初速度。
  • 接著將會根據這個速度飛行。
  • 但是同時會根據鄰近或區域最佳進行模仿,速度矢量會有兩條(原本和模仿),兩個矢量根據參數調整後相加。
  • 慢慢地朝著某個方向飛行,帶頭的也會往其他的地方飛行。

結語

  • 單純模仿也行,只是要明白模仿對象是鄰居還是全局最佳。
  • 單純模仿的壞處在於搜索中的過程路徑會相當短,但是迭代次數應該會比較少次。
  • 如果是向鄰近模仿,可能是按照歐幾里德距離找最近幾個資料點。說不定會運用到 K-d Tree 這個資料結構。

反思題目

  1. (25%) 請說明模糊系統的構成要件為何 ? 其功能分別是 ? 如何建立模糊系統 ?
    其優缺點分別是 ?
    大體要件:模糊化機構、模糊推論引擎、模糊規則庫、去模糊化系統。

    模糊化機構:輸入有可信度問題,加以模糊。
    模糊推論引擎:將數個模糊規則合併篩選用途。
    模糊規則庫:每條規則將根據輸入產出相對應模糊輸出。
    去模糊化系統:將模糊產出的圖,進行調整最後以向量形式輸出。

    細節要件:模糊集合、模糊運算、模糊關係。

    模糊集合:用來表示一個函數對於某個條件的歸屬程度。
    模糊運算:表示每一個模糊集合之間的合成方法,用以做更複雜的組合。
    模糊規則:明確判斷條件 if else 轉換成模糊的判斷條件,即為模糊規則。
    模糊關係:在龐大的關係中,輔助綜合條件判斷的模型。

    建造模糊系統:通常由專家提供的語意規則建造,否則將會使用均勻切割的方式去建造模糊系統。
    優點:語意式的描述給予程式判斷上更大的彈性,不用撰寫非常明確的判斷條件於程式中,也能讓結果相當符合一般人的需求,而且後期可調整參數。
    缺點:可能沒有專家協助,模糊定義上很難得到好的結果。相較於明確判斷,去模糊化的過程速度會慢上許多,以及模糊運算上動用到的函數複雜度與所需時間成正比。

  2. (25%) 螞蟻是如何找到最短路徑 ? 請詳述 AS-TSP algorithm。
    就是那個每次回合,依序放出螞蟻,螞蟻根據費洛蒙走判斷條件走,最佳的走法將會在下一次運行時,路徑上的費洛蒙額外增加。

  3. (20%) 請詳述 RBF network 的架構為何 ? 如何訓練 RBF network ?
    全名:Radial basis function network
    架構有三層輸入層、隱藏層、輸出層。
    要素為非線性激活函數、向量形式的輸入輸出。
    在這門課中,採用基因算法來訓練它,根據與收集資料的誤差來當作適應程度,不斷地調整至好的參數。
    而在線性可分割的高維空間中,可以利用數學函數的運算再加上一個微量調整的偏量相乘,將整個函數慢慢導向至最好結果。(曾經所說的向量疊加,新的法向量 = 所在的法向量 + 微量 * 資料表誤差表示出來的向量。)

  4. (10%) 請說明有哪兩大類最佳化工具 ? 其優缺點分別為何 ?
    • 特定型最佳化法則
      快,一個問題一個算法。同一算法能解決的問題少,幾乎都要客製化。
    • 廣義型最佳化法則
      慢,無須根據問題調整算法。
  5. (20%) 請詳述 Genetic algorithm。其優缺點分別為何 ? 如何改進其缺點 ?
    優點

    1 与问题领域无关切快速随机的搜索能力。
    2 搜索从群体出发,具有潜在的并行性,可以进行多个个体的同时比较,robust。
    3 搜索使用评价函数启发,过程简单。
    4 使用概率机制进行迭代,具有随机性。
    5 具有可扩展性,容易与其他算法结合。

    缺點

    1 遗传算法的编程实现比较复杂,首先需要对问题进行编码,找到最优解之后还需要对问题进行解码。
    2 另外三个算子的实现也有许多参数,如交叉率和变异率,并且这些参数的选择严重影响解的品质,而目前这些参数的选择大部分是依靠经验。
    3 没有能够及时利用网络的反馈信息,故算法的搜索速度比较慢,要得要较精确的解需要较多的训练时间。
    4 算法对初始种群的选择有一定的依赖性,能够结合一些启发算法进行改进。
    5 算法的并行机制的潜在能力没有得到充分的利用,这也是当前遗传算法的一个研究热点方向。

    參考

  6. (20%) 請詳述 螞蟻算法。其優缺點分別為何 ? 如何改進其缺點 ?
    優點

    1 求解性能上,具有很强的鲁棒性(对基本蚁群算法模型稍加修改,便可以应用于其他问题)和搜索较好解的能力。
    2 蚁群算法是一种基于种群的进化算法,具有本质并行性,易于并行实现。
    3 蚁群算法很容易与多种启发式算法结合,以改善算法性能。

    缺點

    基本蚁群算法计算量大,求解所需时间较长。

    參考

  7. (20%) 請詳述 粒子算法。其優缺點分別為何 ? 如何改進其缺點 ?
    優點

    简单、易实现、计算量小和计算效率高

    缺點

    问题最主要的是它容易产生早熟收敛(尤其是在处理复杂的多峰搜索问题中)、局部寻优能力较差等。PSO 算法陷入局部最小,主要归咎于种群在搜索空间中多样性的丢失。

    改善

    (1)全局优化算法与局部优化算法混合
    (2)全局优化算法与全局优化算法混合。纵观各种与 PSO 算法相关的混合算法,大多数基本上采用一种策略对其改进,要么与其他算法,要么加入变异操作,同时采用两种策略的混合算法较少。

    參考


題外話

  • 關於單一感知機
    • 假設現在處於平面上,也就是說 f(xi, yi) = ci
      根據感知機會有三個變數,猶如 w[1] x + w[2] y + w[0]
      現在得到一堆 (xi, yi, ci) 是實際的情況,如何訓練感知機得到 w[] ?
      假設感知機會根據 (xi, yi) 產出 di
      根據調整參數 w’[i] = w[i] + wwww((yi - di))
      wwww 可以是任意函數,不過盡可能地介於 [0, 1]。
      會發現地,最後產出 di 會相當接近於 yi。
    • 當處於線性可分割,也就是可以一刀把兩個群族分開,那麼感知機是會收斂得到好的結果。
    • 也有另外一種方式,採用偏離向量的迭加,這個向量也會來自於產出的誤差效應。

Reference

  • NCU CSIE 計算型智慧課程
Read More +

敏捷方法 - 學習 (Agile Method)

敏捷開發

重點筆記

XP 極限開發

簡介

溝通為其特色,某方面來講有過於親密的傾向。
如果程序猿們按照 Pair Programming 的方式運行,被當成基佬們也不意外。

1. Fine scale feedback  細部回授
    * TestDrivenDevelopment via ProgrammerTests and CustomerTests (were UnitTests & AcceptanceTests) 
    * PlanningGame 
    * WholeTeam (was OnsiteCustomer) 
    * PairProgramming 
2. Continuous process rather than batch  非批次流程
    * ContinuousIntegration 
    * DesignImprovement (was RefactorMercilessly) 
    * SmallReleases 
3. Shared understanding  分享所知
    * SimpleDesign (DoSimpleThings, YouArentGonnaNeedIt, OnceAndOnlyOnce, SimplifyVigorously) 
    * SystemMetaphor 
    * CollectiveCodeOwnership 
    * CodingStandard or CodingConventions 
4. Programmer welfare  員工福祉
    * SustainablePace (original name: FortyHourWeek)
  • 強調團隊溝通,確保每一步都是正確且穩定。
  • 強調個人思考,藉由溝通引出每個人的思考。
  • 測試驅動開發,先有測試資料,才開始撰寫。

對於台灣人

  • 強烈抨擊文件不是首要任務,英文不好,還不如不要用英文撰寫。
  • 英文文件能提高溝通力?請自行反思。

回過頭來,看待敏捷

  • 文件越簡單越好,花在寫文件的時間可能太多。
  • 同一室工作,最多 10 人一室,以免過度干擾。
    • 溝通滲透-簡單說就是偷聽長知識。
    • 惡性溝通滲透-聽到沒有用的資訊。
  • 駐點客戶的存在
    • 與工程師溝通,確保需求符合,常駐程序猿們的公司,改完馬上可以詢問滿意。
    • 通常專案的費用,額外含駐點客戶員工的薪水。(畢竟不常在原公司)
  • 定期交貨,一分錢一分貨
    • 功能做到哪就給多少錢,風險分散。
    • 如果做失敗,可以即早治療。
  • 程序自動化測試
    • 採用連續整合 (可以去 CI 網站 看看)
    • 每天修改的程序,隔天起來就能查錯。

行動

  • 請參閱考古題條目,將會給你更多的執行項目。

做了一點小修改,馬上就能得到回饋,所以能敏捷。
敏捷不是快速,敏捷不是力量。雖然有點慢,但是穩定運作,避開不好的危機。
我們不是工廠!不是重複做相同的事情。

Lean Development 精實開發

1. Eliminate waste 根除浪費
2. Amplify learning 大量學習
3. Decide as late as possible 盡晚決定
4. Deliver as fast as possible 盡早交貨
5. Empower the team 授權團隊
6. Build integrity in 整合思維
7. See the whole 眼觀全局
  • 另一種軟體開發方式
  • 敏捷開發-共同向善,督促所有人進步。
  • 精實開發-剔除累贅,改善開發。

WHEN YOU ARE AGILE, YOU GET LEAN. 敏捷之後 自然瘦身

SCRUM

用以輔助 XP 極限開發的一種敏捷管理法

Role 主要角色

  • Product Owner
    • 產品負責人,負責在有限的時間和預算將產品做到最好。
    • 下面的人全照他的想法建造產品。
  • The Team
    • 團隊必須有產品製造過程中的技術。
    • 在每一個 Sprint 中,產出或增加軟體潛力。
      • The Team Resource
        開發前先餵點飼料,給予團隊之後會需要的資源。
      • Manual
        每一次 Sprint,制定軟體確切的模式(樣貌),這比寫文件更困難。
  • Scrum Master
    • 一個人管理和疏通所有程序猿、確認生存狀況以及環境障礙。
    • 程序猿通常有溝通上的障礙,需要有人引導。
    • 確認每一個人的進度,並且不會某些人有卡在相同問題(愚蠢狀況)。

Meeting 會議形式

  • Sprint Meeting
    • 產品負責人將會釋放出新的功能項目。
    • 團隊要根據技術去完成它們。
    • 在會議結束後,確定每個程序猿都知道如何去實作。
    • 會議兩周一次。
  • Sprint Demo
    • 開會期間,展示上次 Sprint 要求完成後的結果。
    • 同時檢查是否合乎預期,以及當初是為了造什麼來的。(工作不飽和,可能造出非物。)
  • Sprint Retrospective
    • 回顧和檢討,改善開發環境,可能是採用開發工具替換。
    • 或者是會議、討論形式的改善。
    • 最後同意並確定檢討後遵守的條目。
  • Daily SCRUM
    • 每個程序猿簡單報告這兩個星期做了什麼、中間遇到什麼問題、下次要完成什麼。
    • 如果遇到的問題可以自行解決,也可以協助或告知其他程序猿。
    • 這些技術或者是其他問題將要在 Daily SCRUM 後被解決。

Retrospective - 中文意思: 回顧
Sprint - 中文意思: 衝刺
Scrum - 中文意思: 爭球

Artifacts 神器

  • Increment 增量
    • 每次 Sprint,將軟體潛力增加,藉由當初定義 ‘完成(done)’ 為標竿。
    • 完成(down)
      每況愈下,完成的定義越來越嚴苛。最後如下定義:
      1.    All the PO’s defined acceptance tests run,
      2.    The system is fully integrated and running on the production servers,
      3.    All the manual pages are up to date,
      4.    The code is clean and well-factored,
      5.    All the programmer tests are running green.
      
    • 由於 ‘完成’ 定義嚴苛,即使有缺陷 (Bug),也能在短時間內修復。
    • 小檢查、小修復比起改造整個產品成本更低。
  • Product Backlog 產品待辦
    有序地完成需求項目,產品負責人和團隊要一致認可。
  • Sprint Backlog 衝刺待辦
    確認每一個 ‘done’ 的完成,看得到完成進度。

期中考古題

以下內容為本人網路搜索的轉換,如有錯誤請多多指教

  • 1 張氏軟體公司有張一張二張三張四等四位工程師及客戶公司派來的駐點使用專家王五, 另聘工讀生工一工二兩位。

    • 1.1 公司現場應如何佈置
      Answer. 
      1. 分 Common 及 Cave 兩區、和四周的 White Board(白版)
          **Common 區**: 兩人一組,在一台大尺寸螢幕前工作 (pair programming)                  各組可目視、交談、溝通
          **Cave 區**: 個人處理 e-mail,電話,閱讀資料等
          **White Board**: 供討論用
      2. 採用 Central Desk (相較於 U-pod) 配置,可以相互看到對方的工作區。
      3. 細節補充:
          1. 勿用需工人搬動的傢俱,用簡單桌子即可
          2. 電源線,網路線走底下或頭上,易接到桌子
          3. 椅子勿節省,有人因背痛要跪姿椅或升降桌
          4. 白板要很多,含輪子白板,相機白板,動態顯示板(連接投影機,如顯示 build 狀況)
          5. 見下圖 Central Desk 有 eye contact,U-Pod 則有 ear contact 且易看別組螢幕
      
    • 1.2 探索需求 誰做 何處做 產生何文件

      Answer. 客戶公司兩位資深人員做需求分析,在客戶公司做,產出功能清單及相關特性、限制、偏好。
          分析工作如下:
          1. 列出使用者名單
          2. 選取使用者樣本 
          3. 觀察、訪談(2),與之開會 
          4. 開會要充份討論 
          5. 會後得到功能清單,及相關特性、限制、偏好 
          6. 功能分次開發後,做喜好度調查
          最後派遣一位當作駐點客戶給開發團隊即可。
      
          對於顧客
          * 顧客不明白他自己需要什麼
          * 顧客不願將他們的需要固定在一系列寫在紙上的條例中
          * 在價格和時間確定後,顧客堅持要求新的需要
          * 分析者與顧客的通訊太緩慢
          * 顧客不參加回顧或無法參加回顧
          * 顧客缺乏技術上的知識
          * 顧客缺乏對軟體開發的知識
          ----
          對於分析師
          * 是否可行
          * 是否在規定的時間裡可以完成
          * 價格上是否負擔得起
          * 是否合法
          * 是否符合道德
      
    • 1.3 Scenario 誰做 文件為何
      Answer. 駐點客戶說明,並寫出 Scenario 和 User Story 文件。
          * 寫使用情節 (Scenarios) 並與開發者確認使用畫面,
          * 撰寫方式:由簡而繁、由正常到異常
      
    • 1.4 Acceptance Test Case 誰做 文件為何
      Answer. 駐點客戶寫,並且產出 驗收案例文件。
          * 由使用情節寫驗收測試(需準備大量 data )
          * 驗收測試應在程序員寫代碼之前就寫好。
          * 根據使用使用操作,會產生何種操種介面或者是輸出。
      
    • 1.5 CRC session 誰做 文件為何

      Answer. 工程師五人以內圍坐,產出 Class Diagram, Sequence Diagram 等設計圖文件
          * 群體智慧,設計出好的程式架構
          * 切割類別(C)、每個類別自己要做什麼(R)以及類別的合作類別(C)
      
          架構設計會議,準備 CRC Card (Class-Responsibility-Collaborator cards) 
          以下為 CRC Card 的欄位項目 (相當於 O-O 架構的設計)
          * 資訊保持者(information holder) ─ 知道或提供資訊,也就是說保持事實,例如郵件地址,帳號,交易記錄等;
          * 結構者(structurer) ─ 保養物件間的關聯以及與這些關聯相關的資訊,例如檔案系統的folder;
          * 服務提供者(service provider) ─ 執行工作,一般來說提供運算服務,例如信用授權;
          * 協調者(coordinator) ─ 委託工作,例如交通號誌燈,文字處理器的字體管理;
          * 管制者(controller) ─ 決定並指揮它物的行動,例如交通指揮員;
          * 介面者(interfacer) ─ 支持系統內外各部門的間通訊,例如ATM的金錢出口。
      
          決定以上內容後
          * 可以撰寫 Class header 和 Method header 的簡單說明。
          * Class header 由其下 Method header 匯集篩選而成。
      
    • 1.6 Dispatching and Scheduling 誰做 文件為何
      開發條目
      Answer. 工程師們根據自己的狀況,將認領的類別 Class 估算工作天數。產出每個人要在這段期間內完成那些功能項目的文件。
          Dispatching - 派工 (有人可能完成不了某些項目,著手工作分配)
          Scheduling - 時程 (功能所需完成時間進行分配)
          * 每一回合 - 平均三周,做一次派工和時程規劃 (工作分配,時間分配)
          * 每三回合 - 平均兩個月,交貨給客戶
      
    • 1.7 Unit test planning 誰做 文件為何
      Answer. 由工程師撰寫對於每個類別 Class method 的測試代碼 (根據之前 CRC 的討論),產出 Unit test code
          * 這玩意必須在程式撰寫前開始,而且通常比源代碼還長。
          * Test code 又稱 Test-First Development。
          * 不知道算不算 **測試驅動開發** 前置作業
          * 每一個 method 根據參數、環境做預期結果的測試。
      
    • 1.8 Data structure design 誰做 文件為何
      Answer. 工程師,產生數據結構的 Class。
          * 除了工程師外,沒人辦得到。
          * 高級數據結構比一般數據結構好用,而且擴充性和彈性較強。
          * 通常內建標準函數庫就很好用
          * C++: #include <stack>, #include <queue>, ...
          * Java Collections Framework: ArrayList, Vector, Stack ...
      
    • 1.9 Algorithm design 誰做 文件為何
      Answer. 工程師,產出虛擬碼 pseudo code、設計草圖 design sketch
          * 虛擬碼不說自明,設計草圖就是圖形化的想法來源
          * 根據數據結構也有所不同。
          * 演算法也是有抽象層次 Abstraction levels,相互調用什麼的。
          * 要做 Trace test code 來 Debug。
          * 要做時間複雜度分析。
          * 同時簡化到可以在白板上,讓團隊審查 Group review。
      
    • 1.10 Coding 誰做 文件為何
      Answer. 工程師,產出源代碼 source code
          * 終於開始工作,還會一直被 Unit test code 
          * 程式易於閱讀、了解、維修,才是 **活著**
          * 強調重複利用別人代碼 (因為通常已經通過測試,不用 Debug)
      
    • 1.11 Unit testing 誰做 使用何文件
      Answer. 工程師使用測試軟件運行 Unit test code,產出測試結果。
          * 如 Java unit test,產出測試記錄檔,表示哪些 method test case 通過。
      
    • 1.12 Acceptance testing 誰做 使用何文件
      Answer. 駐點客戶手動測試,使用驗收案例文件,產出測試結果。
          * 手動操作所有驗收案例
          * 如果驗收案例太多,那也是駐點客戶疲累的地方。
          * 測試文檔,不外乎就是哪些連續動作 (Action) 通過或者是不通過
      
    • 1.13 Reverse Engineering Tool 何工序後可使用
      Answer. 在架構設計 (CRC) 後,便啟動這類型逆向工具。
          * 利用逆向工程工具 如 eUML2、AgileJ。
          * 工具將動態產生 Class diagram, Sequence diagram ... 等。
          * 協助設計草圖不偏離,同時能了解設計樣貌,幫助維護和修改。
      
    • 1.14 此軟體的需求有七個功能( user story ) 駐點使用專家規劃為三次交貨( release )工程師們規劃用兩個回合( iteration )完成第一次交貨的功能
      • 1.14.1 派工 (dispatching) 如何做
        Answer. 在 CRC 工作結束後,每個成員認領一項類別 Class 進行開發。而在每回合微調工作分配。
        
      • 1.14.2 時程 (scheduling) 的時間單位為何
        Answer. 平均 2-3 週
        
      • 1.14.3 工作中客戶公司會不會來催進度為什麼
        Answer. 定期交貨,以執行力達成承諾取信客戶,客戶只需固定時程檢驗進度。
        
  1. 因有 Continuous Integration(CI) 使 Agile method 不須 integration testing. Explain it.
    Answer. 連續整合採用自動化的方式進行,每一天或者是固定時間,便會將團隊開發、撰寫立刻回饋分析結果,如此一來不用人工繁瑣的整合測試程序。
        * 這問題相當奇怪,因為連續整合也算是整合測試 ?
        * 連續整合不用人工測試,可以降低風險。
        * 連續整合隨時都有可以發布的版本。
        * 增加系統透明度。也就是說可以追蹤或者是預測發展趨勢。
    
  2. Test-driven development 的 development, test 及 drive分別是什麼
    Answer. 因為在源代碼 source code 撰寫開始前,必須先把所有測試項目撰寫成 test code 或者是人工驗收的案例,
    * development 開發方式,做事的風格
    * test 測試,經由 test code, case, tool 產生預期結果和實際形況的差異分析。
    * drive 驅動則是根據測試結果驅使源代碼的修正。
    
  3. 維修軟體時,應閱讀 sourse code 或 pseudo code? Why?
    Answer. Pseudo code,方便理解與快速找到要維修的地方。
        * 題目應為先讀哪一項,照理來講要先讀 pseudo code 再讀 source code。
    
  4. Pair programming 何以能提高軟體品質?
    Answer. 一人撰寫一人修正,分散思考壓力,同時可以激發出創意,可以降低錯誤率、提升除錯效率。
        * 主要是分散思考壓力、增加思考廣度。
        * 缺點是開發時間會稍慢,但是品質不錯。
        * 編程能力水準相當才能相互激發,否則是純教導或者是管理功用。
        * [搞笑影片](https://www.youtube.com/watch?v=dYBjVTMUQY0)
    
  5. Method interface 與 method header 有何相關舉例說明之。
    Answer. 
    1. method interface 指的是關於這個 method 參數型態和意義、以及額外調用的 method 說明。
    2. method header 指的是在 method 前面的說明,通常具有這個 method 如何快速簡易使用的說明。
            * 通常 method header 算是 method interface 的摘要,或者是組合使用的說明。
            * 因此 method interface 完成後,才會有完整的 method header。
            * method interface 指的並不是 java 的某種 interface 類別,而是類似 UML 有哪些 method 和 attribute,能提供做出什麼事情。
            * 別跟 class header 搞在一起,請弄清楚。
    
  6. Data structure design 與 Algorithm design 有何關係
    Answer. 演算法中會調用到資料結構,根據搭配的資料結構才能估算時間複雜度,以及支持效果。同時,演算法也能針對搭配資料結構做最佳化。
        * 面相來說,Data structure 是工具 Tool。
        * 怎麼最佳化使用工具就是演算法的事情。
        * 例如: 資料結構的幾種操作的複雜度不同,調用操作的比率將會是演算法的重點。
    

Reference

Websites

  1. 台灣敏捷苗圃
  2. BLOG - 輕鬆談軟工
  3. Wiki

Friends

  • Iris
  • 等待更多網友
Read More +