在線算法

在計算機科學中，一個在線算法是指它可以以序列化的方式一個個的處理輸入，也就是説在開始時並不需要已經知道所有的輸入。相對的，對於一個離線算法，在開始時就需要知道問題的所有輸入數據，而且在解決一個問題後就要立即輸出結果。例如，選擇排序在排序前就需要知道所有待排序元素，然而插入排序就不必。 ^[1] 

因為在線算法並不知道整個的輸入，所以它被迫做出的選擇最後可能會被證明不是最優的，對在線算法的研究主要集中在當前環境下怎麼做出選擇。對相同問題的在線算法和離線算法的對比分析形成了以上觀點。如果想從其他角度瞭解在線算法可以看一下流算法（關注精確呈現過去的輸入所使用的內存的量），動態算法（關注維護一個在線輸入的結果所需要的時間複雜度）和在線機器學習。

一個很好的展示在線算法概念的例子是加拿大旅行者問題，這個問題的目標是在一個有權圖中以最小的代價到達一個目標節點，但這個有權圖中有些邊是不可靠的可能已經被剔除。然而一個旅行者只有到某個邊的一個端點時才能確定該邊是否已經被移除了。最壞情況下，該問題會變得簡單了，即所有的不確定的邊都被移除該問題將會變成通常的最短路徑問題。 ^[2] 

插入排序（英語：Insertion Sort）是一種簡單直觀的排序算法。它的工作原理是通過構建有序序列，對於未排序數據，在已排序序列中從後向前掃描，找到相應位置並插入。插入排序在實現上，通常採用in-place排序（即只需用到 O(1) 的額外空間的排序），因而在從後向前掃描過程中，需要反覆把已排序元素逐步向後挪位，為最新元素提供插入空間。 ^[1] 

感知器（英語：Perceptron）是Frank Rosenblatt在1957年就職於康奈爾航空實驗室（Cornell Aeronautical Laboratory）時所發明的一種人工神經網絡。它可以被視為一種最簡單形式的前饋神經網絡，是一種二元線性分類器。

Frank Rosenblatt給出了相應的感知機學習算法，常用的有感知機學習、最小二乘法和梯度下降法。譬如，感知機利用梯度下降法對損失函數進行極小化，求出可將訓練數據進行線性劃分的分離超平面，從而求得感知機模型。

感知機是生物神經細胞的簡單抽象。神經細胞結構大致可分為：樹突、突觸、細胞體及軸突。單個神經細胞可被視為一種只有兩種狀態的機器——激動時為‘是’，而未激動時為‘否’。神經細胞的狀態取決於從其它的神經細胞收到的輸入信號量，及突觸的強度（抑制或加強）。當信號量總和超過了某個閾值時，細胞體就會激動，產生電脈衝。電脈衝沿着軸突並通過突觸傳遞到其它神經元。為了模擬神經細胞行為，與之對應的感知機基礎概念被提出，如權量（突觸）、偏置（閾值）及激活函數（細胞體）。

在人工神經網絡領域中，感知機也被指為單層的人工神經網絡，以區別於較複雜的多層感知機（Multilayer Perceptron）。作為一種線性分類器，（單層）感知機可説是最簡單的前向人工神經網絡形式。儘管結構簡單，感知機能夠學習並解決相當複雜的問題。感知機主要的本質缺陷是它不能處理線性不可分問題。 ^[1] 

貪心算法（英語：greedy algorithm），又稱貪婪算法，是一種在每一步選擇中都採取在當前狀態下最好或最優（即最有利）的選擇，從而希望導致結果是最好或最優的算法。比如在旅行推銷員問題中，如果旅行員每次都選擇最近的城市，那這就是一種貪心算法。

貪心算法在有最優子結構的問題中尤為有效。最優子結構的意思是局部最優解能決定全局最優解。簡單地説，問題能夠分解成子問題來解決，子問題的最優解能遞推到最終問題的最優解。

貪心算法與動態規劃的不同在於它對每個子問題的解決方案都做出選擇，不能回退。動態規劃則會保存以前的運算結果，並根據以前的結果對當前進行選擇，有回退功能。 ^[2]