#98 淺談機器學習

人工智慧在電腦科學的領域不是一個新主題，已經存在很長的時間．其目的是希望電腦可以做出接近人腦一樣的決策，甚至希望比人腦更好．從以前到現在曾試過了數種不同的方式，從 90 年代開始，機器學習成為了人工智慧裡主流的方式，革新了我們處理數據分析、自動化和決策的方式。這文章將討論機器學習的基礎概念，淺談其不同類型、訓練模型等． 機器學習是近二三十年來人工智慧裡流行的方法，專注於開發能夠基於數據的了解並做出預測或決策的演算法。它涉及創建模型和使用模型，這些模型可以找到模式、做出決策，並且隨著時間的推移提高其準確性。機器學習的廣泛分類可以分為 3 大類：監督學習...

閱讀全文

#97 Segment Tree

在 binary tree 的文章時曾提到從 tree 開始後的資料結構文章將會開啟另一個大門，看來許多問題可以透過 tree 結構來解決．今天要介紹的 segment tree 就是一個例子． 試想一個情況，在現實生活中一定常常會遇到一個工作，一堆資料裡面，在某一個特定範圍依照某一個資料特徵來尋找資料．例如，在公司組織結構裡，找出 A 老闆底下的員工數總和．假設你已經有了員工組織樹狀結構，第一件要做的事情便是尋找 A 老闆節點，找到 A 老闆節點後，再從這裡出發將所有子節點計算個數，便能得到答案．一旦這樣的查詢工作常常發生的話，你會發現前面說的動作並不能馬上回應答案，因為還是要對員工組織樹狀結構進行...

閱讀全文

#96 分散式系統介紹

分散式系統是我念書過程裡最喜歡的課程之一，也是以前我的研究領域．這一門課通常開設在碩博士班的課程裡，因為這門課需要不少基礎的課程，如果開在大學部的話，也一定是屬於大四選修課的內容．它的先修課程包含了作業系統, 演算法, 資料庫理論, 網路理論，網路程式設計等．它有一個兄弟課程叫分散式演算法．這兩門課蠻接近的，對我而言，分散式系統是比較以工程實作導向來討論分散式系統，而分散式演算法是以數學和演算法更嚴謹的電腦理論來談許多分散式系統裡所需要的運作細節. 我剛好都修過這兩門課，所以都清楚這兩個課程的內容．由於這個部落格的目的是將較不好懂的電腦理論用較白話易懂的方式來介紹給大家，所以在分散式系統的文章裡，不會著重在分散式演算法的內容．這是分散式系統系列文章的第一篇，所以會用一個較宏觀的角度來說明什麼是分散式系統.在...

閱讀全文

#95 Priority Queue 是不是 Queue ?

 在日常生活的情況中，排隊是一件很常見的事．原因是提供資源的人少，而使用資源的人多．例如，一堆人到便利商站買東西，買完後要結帳，而櫃檯人員只有一個，所以結帳得一個一個來，因此買商品的人就得排隊．在此時，如果出現一個文化水準低落的人來插隊，想必你一定會很生氣去跟對方說．在便利商店的排隊結帳來說，插隊通常不是件好事，但日常生活裡，某些特殊情況下，插隊是需要的，比如在醫院的急診室，或是馬路上遇到救護車救火車之類的，這種特殊情況，不緊急的必須先讓給緊急的．當我們撰寫程式碼時，一般情況下我們會使用 Queue 資料結構來達成 "排隊" 的目的，然後，因應需求，如同急診室或救護車的例子，我們必須提供一個方法讓...

閱讀全文

#94 演算法的 Backtracking 策略

 Backtracking 是一種演算法的策略，可用來解決三種面向的問題，分別是 Decision problem, Optimization problem, 以及 Enumeration problem．有關 Optimization problem 在前面的文章裡已經談過不少，這裡不多說明．一個 Decision problem 可能會有至少一個或一個以上的解答，這種問題我們通常只要找一個可用的解答．Enumeration problem 和 Optimization problem 蠻相近，就是要將所有解答找出來．舉個例子，之前講過的老鼠走迷宮是一種問題，如果我們要找一條可行的路，那麼老鼠走迷宮將是...

閱讀全文

#93 平衡樹系列 - AVL Tree

在前面的資料庫文章裡曾介紹過 B-tree，一種平衡的搜尋樹，利用樹狀的結構來達成快速尋找的目的，而且因為是平衡的，所以從 root 出發到每一個樹葉的尋找成本是一樣的，這也是必要的，畢竟資料庫引擎用公平的方式來對待所有的資料．然而，B-tree 的結構並非是 binary 的型式，因此這帶給它很大的彈性可以方便地達成一個完全平衡的狀態．在前幾篇的文章也談過了 binary search tree，若你看過的話，你會清楚地知道 binary search tree 和 binary tree 的不同．在 binary search tree 裡，因為在建立樹的過程中有一個很重要的特性，就是右邊子節點的值大於父節點，左邊子節點的值小於父節點，因此在建立樹或是尋找節點時，到達一個節點時，只需要選擇其中一邊，不是左邊就是右邊，所以也達到...

閱讀全文

#92 今年一月份 APCS 程式設計第三題 - 切割費用

前陣子，我的小徒弟去報名他人生第一次的 APCS 考試，可以說是他學習電腦科學以來第一次的正式上機考試．一共有四題的程式設計題目，前面兩題算是簡單的，第三題算中等，第四題比第三題再進階一點點．這篇文章就來談談第三題的解題思考．完整的題目在 https://zerojudge.tw/ShowProblem?problemid=f607 ，首先，要解題之前，請先確定自已己經百分百了解題目．這一個題目的解決過程可以分成下列 2 個部份,1. 讀取輸入參數，因為輸入參數並非按照切割次序而輸入的，我們要進行切割時是按照次序來切割的．因此，我們必須對輸入參數做處理，以讓沒有次序的參數集合變成有次序的參數集合．2. 每一次切割時，都需要知道左右兩端的長度，這樣才能算出該次切割的費用，而知道左右兩端的長度，這需要一個快速的行為才能符合題目的要求．因為題目提到切割次數最多會到二十萬次，並且棍子的長度可以到...

閱讀全文

#91 如何寫有影響力的履歷表

根據 Facebook 社團上的成員資料，目前三百多位成員裡有將近 40% 成員的年紀在 34 歲以下，因此，希望這篇文章可以提供年輕人有關撰寫履歷表內容時的參考. 一般來說，我會把履歷表的寫法分成兩種，一種是屬於年輕工程師的寫法，另一種是資深工程師的寫法，我將年資不到十年的人定義為年輕工程師，所以可能是在 32 - 36 歲之間，就看你在幾歲從學校畢業．在這年資以下的人，撰寫履歷表時應該要著重在技能的部份．也就是說，你得在履歷表上說明你用過了那些工具與方法來製造軟體系統，以及你運用了那些專業知識 (課本上學的) 在你的工作上．比如，某個年輕工程師從事電商系統前端功能的開發，屣歷表上就需要清楚說明用 Javascript/TypeScript 寫了什麼東西，是否用到其他的 framework，如...

閱讀全文

#90 淺談 Dynamic Programming (2)

 前面說過 dynamic programming 的應用很多，這一篇文章來說明其中一種應用，Maximun subarray sum．這個問題是在一個整數的 array 裡找一個連續空間的元素，其元素的總和的值是最大的．如下圖: source: https://www.geeksforgeeks.org/largest-sum-contiguous-subarray/從 index 2 到 index 6 之間的元素總和等於 7，這個區間是這個 array 裡最大的區間總和. 要解決這個問題其實不難，因為用最直接的暴力法就可以解決了，其程式結構如下: ...

閱讀全文

#89 淺談 Dynamic Programing (1)

Dynamic programming 是大學部演算法課程裡相當重要的一個主題，也是典型用空間換取時間的策略．但奇怪的是，這個策略一點也不 dynamic ，一點也不 programming．老實說，我不知道為何這個策略叫 dynamic prograaming，我倒覺得它比較適合叫 "查表法". 接著就來看看為何說它是查表法.Fibonacci number 是許多演算法課本用來解釋 dynamic programming 最簡單的例子．Fibonacci number 是以數學多項式來表達的數字集合，以數學式來表達就可以寫成如下:F(n) = F(n-1) + F(n-2) 也就是說求第 10 項 (n=10) 的答案時，你必須要先算出來第 9 項和第 8 項. 如果要求第 1...

閱讀全文