算法是什麼:計算機領域中算法的科普

2020-12-27 TechWeb

 

當你使用搜尋引擎(例如Google Chrome、Mozilla Firefox等)的時候,後臺發生了什麼?當你詢問虛擬助手(例如Alexa、Google助手或Siri)的時候,後臺發生了什麼?它們怎麼會知道答案?為何它們會顯示正確答案?所有這些都要感謝算法。

每當你使用手機、計算機、筆記本電腦或計算器時,其實都在使用算法。

那麼,什麼是算法?

如果你想做數學運算,比如說兩個數字相乘(不使用任何電子設備),那麼你需要在紙上做乘法。你按照一定的規則獲得正確的答案。你也可以使用耗時更少的方法來做計算。這就是算法。

算法是為執行特定的任務而設計的一組指令。

有些算法很簡單,而有些則非常複雜,具體取決於你要實現的目標。

算法的歷史

了解歷史總是有好處,因為歷史可以幫助你更好地理解主題,並了解何時使用這些知識。

「算法」一詞源自九世紀波斯數學家Muhammad Ibn Musa Al-Khwarizmi(代數之父),拉丁語為Algoritmi。最初算法被稱為Algorismus。15世紀後期,改名為Algorithmus(源自希臘語Arithmetic)。現代英語中的Algorithm一詞是於19世紀引入的。

算法在中國古代文獻中稱為「術」,最早出現在《周髀算經》、《九章算術》。特別是《九章算術》,給出四則運算、最大公約數、最小公倍數、開平方根、開立方根、求素數的埃拉託斯特尼篩法,線性方程組求解的算法。三國時代的劉徽給出求圓周率的算法:劉徽割圓術。

 


1842年,Ada Lovelace首次編寫了計算引擎的算法,因此許多人常常稱她為世界上第一位電腦程式員。她為巴貝奇分析機(自動計算的機械計算機)編寫了求解伯努利微分方程的算法(巴貝奇分析機由計算機之父Charles Babbage開發)。


1936年,Alan Turing的圖靈機首次提出了第一個以現代形式表示的算法。


如何表達算法?

表達算法的方法多種多樣,例如自然語言、偽代碼、流程圖、程式語言、動態圖表、控制表等等。

使用自然語言表達算法不夠清晰,因此很少用於複雜或技術算法。偽代碼、流程圖、drakon圖和控制表是表達算法的結構化方法,因為與自然語言相比,它們可以避免許多歧義。程式語言旨在以可由計算機執行的形式表達算法。

在計算機系統中,算法是由軟體開發人員以他們選擇的任何程式語言編寫的邏輯。但是,在設計算法時,我們需要記住一些規則。其中包括:

輸入:算法至少需要一個或多個輸入值。如果沒有給出輸入,那麼算法將產生什麼輸出呢? 輸出:算法至少應產生一個輸出。如果沒有產生任何結果,則無需設計算法。 效率:算法應該保證高效利用計算和內存資源。產生的輸出應該又正確又快。 簡單性:算法不應過於複雜。 可擴展性:算法必須能夠在不更改核心邏輯的情況下進行擴展。 有限性:算法必須在有限步驟後終止。假設輸入錯誤的情況下,算法在第一步就終止,我們將永遠無法得知算法有什麼問題。而且,算法也不能陷入無限循環。 不依賴於程式語言:算法必須與語言無關,也就是說,它必須是可以用任何一種語言都可以實現的簡單指令,但是無論任何語言,輸出都應當相同。

下面,我們來構建一個簡單的算法:兩個數字的加法(且滿足上述要求)。

第1步:開始; 第2步:聲明變量num1,num2和sum; 第3步:讀取值num1和num2; 第4步:將num1和num2相加,然後將值賦給sum。 第5步:顯示和; 第6步:停止。

下面,為了測試這個算法,我們使用一種程式語言來實現它,我選擇用Java語言來實現,你可以任意選擇其他語言。

public class Addition  {  public static void main(String[] args) {  int num1, num2, sum;  Scanner sc = new Scanner(System.in);  System.out.println(「Enter First Number: 「);  num1 = sc.nextInt;  System.out.println(「Enter Second Number: 「);  num2 = sc.nextInt;  sc.close;  sum = num1 + num2;  System.out.println(「Sum of two numbers: 「+sum);  }  } 

輸出如下:

我們的算法運作良好,且滿足上述要求。

算法必須高效。算法的效率取決於時間和空間。一個好的算法佔用的時間更少,佔用的空間也更少,我們無法時刻兼顧兩者。如果減少時間,則則空間可能會增加,反之亦然。因此,我們必須妥協一方。算法的空間複雜度表示算法運行時佔用或需要的總空間。時間複雜度是指算法花完成任務所需的操作數。以最少操作數執行任務的算法就是最有效的算法。此外,算法花費的時間還取決於計算機的計算速度,但是在我們考慮算法的效率率時,通常不會考慮這些外部因素。衡量算法效率的一種方法是測量算法在不同輸入下找到答案所需的操作次數。


算法的種類

遞歸算法:通過重複將問題分解為同類的子問題而解決問題。 分治算法:把一個複雜的問題分成兩個或更多的相同或相似的子問題,直到最後子問題可以簡單的直接求解,原問題的解即子問題的解的合併。 動態規划算法(又名動態優化算法):記住過去的結果,以備將來使用。與分治算法相似,這種算法可以將複雜的問題分解相對簡單的子問題,然後將解決方案保存起來,以便下次需要同一個子問題解之時直接使用,而無需再次重新計算。 貪婪算法:在每一步選擇中都採取在當前狀態下最好或最優(即最有利)的選擇,從而希望得出結果是最好或最優的算法。該算法不能保證最終獲得最佳解決方案。 暴力算法:簡單明了,嘗試所有的可能性,直到找到滿意的解決方案為止。 回溯算法:嘗試分步地去解決一個問題。如果發現其中某一步的解決方案失敗,則後退一步或幾步,重新開始尋找解決方案。


如今,幾乎每個領域都使用算法,例如數據科學、機器學習、農業、科學、運輸等。算法是每個應用程式(Google Chrome與Mozilla Firefox、Uber與Ola)最大的不同之處,例如Google Chrome和Mozilla Firefox都是搜尋引擎應用程式,它們提供相同的結果,但是結果的順序有所不同,這是因為二者使用了不同的排序算法。Google的排序算法與Firefox不同。

算法無處不在,並將繼續傳播,算法讓我們的生活更加輕鬆,但我們還需要考慮一些問題,例如,

當有一天數據和預測模型統治世界,那麼我們就會喪失人性和判斷力。 隨著更智能、更高效的算法逐步取代許多的人類活動,失業人數將上升。

21世紀,算法就像魔術一樣,我們可以解釋其背後的原理以及如何創建網絡等,卻無法機械地解釋為什麼這些算法會產生特定的輸出。而這僅僅是個開始。

 

相關焦點

  • 算法到實戰,如何零基礎入門計算機視覺領域
    為了讓大家更好的理解計算機視覺在人工智慧領域的強大應用,12月7日晚,上海交通大學盧憲凱博士受【雷鋒網】AI慕課學院邀請,開展了一場主題為《計算機視覺概述和深度學習簡介》的公開課,盧博士在公開課中給大家介紹了計算機視覺的定義、研究方法和應用舉例,重點介紹深度學習發展歷史,常見深度學習網絡介紹和開發平臺,幫助計算機視覺入門者和從業者進行有效的基礎夯實和系統梳理。
  • 理論計算機有哪些特別的算法,它們的算法複雜性很高嗎?
    理論計算機作為現代計算機體系結構的一個分支,其算法與複雜性是理論計算機中最核心、最基礎的主題。下面是小編關於一些關於理論計算機算法的資料心得,與大家分享。1.算法算法的出現遠遠早於計算機的出現,比如我們在小學時學過的通過列豎式的方法來計算兩個整數乘積,再比如,用著名的歐幾裡得的輾轉相除法來求兩個整數的最大公約數。很多好的算法,比如快速排序算法、高斯消元法快速傅立葉變換等,是計算機如今能在生產和生活中有如此廣泛應用的基礎。雖然算法因問題而異,但一些設計算法的方法,總會在不同的場景出現。比如貪心法、分治法、動態規劃、最大流和線性規劃等。
  • AI英雄 | 矽谷尤達大師高德納:算法領域的精神導師
    他是出了名的完美主義者,任何在他的書中發現錯誤的人,他都會給予獎勵。《紐約時報》最近採訪了矽谷的尤達大師、算法和程序設計技術的先驅者高德納(DonaldKnuth)。高德納在採訪中談到了其對算法的看法,並回顧了傾注其畢生心血的巨著《電腦程式設計藝術》(TheArt of Computer Programming)。
  • 世界級計算機算法大師們,他們到底想的是什麼?
    40年前誕生在倫敦的哈薩比斯絕對是個神童,從小就在西洋棋領域展現才華,過五關斬六將拿過不少獎項。可正當父母親戚們覺得新一代棋類明星即將誕生時,畫風一轉,這孩子又愛上了計算機編程和遊戲開發,而且一發不可收拾。長大成人後,他開發過很多遊戲作品,以至於後來又對人工智慧產生興趣,創立Deepmind公司,完成由象棋少年到遊戲開發者再到人工智慧企業家的蛻變。
  • 算法下的選擇讓渡,你被算法裹挾了嗎?
    1946年,世界上第一臺計算機「埃尼阿克」在美國問世。它重30噸,能用20秒計算出炮彈的軌道。從此,算法走出古典數學家的演算紙,進入計算機時代。而數據信息則是算法存在的前提。事實上,算法的本質就是對數據信息的獲取、佔有和處理,在此基礎上產生新的數據和信息。簡言之,算法是對數據信息或獲取的所有知識進行改造和再生產。
  • 計算機專業應數據結構和算法至上?還是與業務掛鈎的技術至上?
    近日,一位網友在知乎上發起提問:計算機學生在大學四年應是以數據結構和算法為重還是技術為重?引來網友紛紛圍觀!讀計算機專業的你,大學四年是否還在迷茫是以數據結構和算法為重還是技術為重? 要想解除疑惑,先要知道計算機科學與技術這個專業都包含了什麼。
  • 陳根:算法下的選擇讓渡,你被算法裹挾了嗎?
    從此,算法走出古典數學家的演算紙,進入計算機時代。而數據信息則是算法存在的前提。事實上,算法的本質就是對數據信息的獲取、佔有和處理,在此基礎上產生新的數據和信息。簡言之,算法是對數據信息或獲取的所有知識進行改造和再生產。
  • 資料|世界著名計算機教材精選:數據挖掘十大算法(中文版)
    內容簡介  · · · · · ·《世界著名計算機教材精選:數據挖掘十大算法》詳細介紹了在實際中用途最廣、影響最大的十種數據挖掘算法,這十種算法是數據挖掘領域的頂級專家進行投票篩選的,覆蓋了分類、聚類、統計學習、關聯分析和連結分析等重要的數據挖掘研究和發展主題。
  • 加強網絡消費領域算法規制
    據新華社電 中國消費者協會7日在京召開網絡消費領域算法規制與消費者保護座談會,會議提出有效規制算法應用中的問題,切實解決消費者維權難,更好保護網絡領域消費者權益。  大數據殺熟、刷好評隱差評使評價結果呈現失真、平臺採用算法限制交易、網絡消費促銷規則繁複、網絡搜索競價排名推薦、網絡直播推送違反法律規定和公序良俗……這些問題的背後,核心是網際網路平臺對算法技術的應用。根據中消協調查,網絡領域涉及消費者權益的算法應用問題,包括推薦算法、價格算法、評價算法、排名算法、概率算法、流量算法等。
  • MIT提出了用隨機數生成隨機數的計算機算法
    眾所周知,計算機無法製造出隨機性,它們也不應該:計算機軟體和硬體運行在布爾邏輯,而非概率上。 目前,我們使用的真隨機數據,一般來自系統從物理環境中採集到的「隨機噪音」。 但是計算機科學家想要可以處理隨機性的程序,因為那有時候是解決問題所必須的。
  • 圖的最短路徑算法-Floyd算法-弗洛伊德算法
    Floyd算法又稱為插點法,是一種利用動態規劃的思想尋找給定的加權圖中多源點之間最短路徑的算法 在計算機科學中,Floyd-Warshall算法是一種在具有正或負邊緣權重(但沒有負周期)的加權圖中找到最短路徑的算法。算法的單個執行將找到所有頂點對之間的最短路徑的長度(加權)。
  • 算法到底算什麼?
    然而,即使如同盧曼的信徒一樣,認為法律是個單獨的系統,但是由於法律必然擁有影響其他所有社會領域的能力,並且也在事實上影響到其他的社會領域,而其中都涉及有或高或低的專業知識,這看起來會導致法律除了自己的領域,別的都一概插不上手。真實情況並非如此。
  • 編程是什麼?什麼是算法?這裡有一個簡單的表述
    雖然筆者水平尚有限,但是還是想嘗試把計算機的學習難度降低,成與不成,看後續吧。本文主要解答編程是什麼?編程是筆者認為計算機最神奇的地方,因為通過編程,個人可以讓計算機完成各種任務,現存的計算機軟體都是編造出來的。
  • 加速AR對象分類,Facebook開源計算機視覺算法Detectron
    文章相關引用及參考:roadtovrFacebook今天正式開源基於深度學習框架的計算機視覺對象檢測算法平臺Detectron(映維網 2018年01月24日)Facebook今天正式開源基於深度學習框架的計算機視覺對象檢測算法平臺Detectron。
  • 圖像處理算法有哪些_圖像處理十大經典算法
    同時,計算機已經作為一種人們普遍使用的工具為人們的生產生活服務。圖像處理概況圖像處理,是對圖像進行分析、加工、和處理,使其滿足視覺、心理以及其他要求的技術。圖像處理是信號處理在圖像域上的一個應用。目前大多數的圖像是以數字形式存儲,因而圖像處理很多情況下指數字圖像處理。本文接下來將簡單粗略介紹下數字圖像處理領域中的經典算法。
  • 小樂數學科普:新量子算法終於破解非線性方程——譯自量子雜誌
    Levy) 2021-1-5譯者:zzllrr小樂 2021-1-6有時,計算機很容易預測未來。簡單的現象(例如樹汁如何流到樹幹上)很簡單,可以使用數學家稱之為線性微分方程的幾行代碼來捕獲。但是在非線性系統中,相互作用會影響自身:當氣流經過噴氣機的機翼時,氣流會改變分子相互作用,從而改變氣流,依此類推。
  • 什麼是時間戳,什麼是哈希算法,網友:連女朋友都懂
    什麼是時間戳,什麼是哈希算法,網友:連女朋友都懂從百度「萊茨狗」到「網易星球」再到騰訊的「大家一起來捉妖」,這些網際網路巨頭紛紛入局區塊鏈。區塊鏈的關注也日益增高,每個人都想參與進來,區塊鏈想不火都難,今天就給大家說說與區塊鏈相關的幾個專業術語:時間戳和哈希算法一時間戳(timestamp)先讓我們看看專業上是怎麼說的,區塊鏈上時間戳就是保證每個區塊按照一定的次序相連。使區塊鏈上每一筆數據都具時間標記。打個比方說,在某個平臺發布了一篇文章,誰是原創的,誰是轉載的,怎麼證明呢?
  • 為何要打開算法「黑箱」:數據並不正義,算法也難中立
    這裡的「黑箱」並不只意味著不能觀察,還意味著即使計算機試圖向我們解釋,我們也無法理解。 事實上,早在1962年,美國的埃魯爾在其《技術社會》一書中就指出,人們傳統上認為的技術由人所發明就必然能夠為人所控制的觀點是膚淺的、不切實際的。技術的發展通常會脫離人類的控制,即使是技術人員和科學家,也不能夠控制其所發明的技術。
  • FLDR算法問世,人類距離將隨機性注入計算機還差一步
    選擇一個序列中的七個數字,以便每個數字均等地出現,並且選擇一個數字不會影響下一個數字。但很遺憾地告訴你,你做不到。計算機也不會很好地產生隨機性。因為計算機軟體和硬體運行在布爾邏輯上,而不是概率上。麻省理工學院概率計算項目的負責人維卡什·曼辛格(Vikash Mansinghka)表示,「計算文化以確定性為中心。」
  • 市面上的算法書,公認最好的是這幾本
    算法作為自計算機技術萌生便一直蓬勃的科學支撐了這門技術最基礎、最內涵的邏輯任憑IT技術如何發展算法和計算機基本的邏輯始終不會變《未來簡史》的作者甚至說這本書的地位就不需要我多講了吧,算法領域書中宗師級別的地位,每一個算法入門都應該看並且能看懂的書。沒學過高等數學?只要你知道高中數學知識就行。沒學過編程?