Yaoの程式小窩

【計算機網路筆記】2.5 Peer-to-Peer File Distribution Hello Guys, I’m LukeTseng. 歡迎你也感謝你點入本篇文章，本系列主要讀本為《Computer Networking: A Top-Down Approach, 8th Edition》，就是計算機網路的聖經，會製作該系列也主要因為修課上會用到。若你喜歡本系列或本文，不妨動動你的手指，為這篇文章按下一顆愛心吧，或是追蹤我的個人公開頁也 Ok。 P2P 架構與自我擴充性（Scalability） 複習：什麼是 P2P？ 在傳統的主從式架構（Client-Server Architecture）中，伺服器必須承擔所有的上傳工作。 如果要發送一個檔案給 $N$ 個使用者，伺服器就必須把這個檔案傳送 $N$ 次，會導致伺服器的頻寬成為巨大的瓶頸。 在 P2P 架構（Peer-to-Peer Architecture）中，每一台參與的電腦被稱為 Peer（對等點）。 Peer 不僅僅是下載檔案，還會將已下載的檔案片段重新上傳給其他的 Peer。 為什麼 P2P 很重要？ 這個架構最...

【計算機網路筆記】2.4 DNS—The Internet’s Directory Service Hello Guys, I’m LukeTseng. 歡迎你也感謝你點入本篇文章，本系列主要讀本為《Computer Networking: A Top-Down Approach, 8th Edition》，就是計算機網路的聖經，會製作該系列也主要因為修課上會用到。若你喜歡本系列或本文，不妨動動你的手指，為這篇文章按下一顆愛心吧，或是追蹤我的個人公開頁也 Ok。 2.4.1 Services Provided by DNS（由 DNS 提供的服務） 什麼是 DNS？ DNS（Domain Name System，網域名稱系統）就像是網際網路的「電話簿」，負責將人類好記的網址翻譯成電腦能理解的 IP 位址。 當在瀏覽器輸入 google.com 這種人類好記的網址時，電腦其實看不懂。 電腦需要透過 DNS 把網址翻譯成一串數字構成的 IP 位址（例如 142.250.190.46），才能正確連接到該網站的伺服器。 DNS 也是一個建立在應用層上的協定，它主要由兩部分組成： 分散式...

【計算機網路筆記】2.3 Electronic Mail in the Internet Hello Guys, I’m LukeTseng. 歡迎你也感謝你點入本篇文章，本系列主要讀本為《Computer Networking: A Top-Down Approach, 8th Edition》，就是計算機網路的聖經，會製作該系列也主要因為修課上會用到。若你喜歡本系列或本文，不妨動動你的手指，為這篇文章按下一顆愛心吧，或是追蹤我的個人公開頁也 Ok。 電子郵件系統的核心在於提供一種非同步（Asynchronous）的通訊方式。 什麼意思？就像傳統的郵政服務，寄信時，收件人不需要坐在家裡等，寄件人寫好信丟進郵筒，系統會負責傳遞到收件人的郵箱，對方有空時再開箱讀取。 電子郵件的出現打破了時間的限制，不需要通訊雙方同時在線（Always-on）也能交換資訊，且成本極低、速度快。 Image Source：Computer Networking: A Top-Down Approach (8th ed., p. 147, Figure 2.14) 上圖中呈現一份網際網路郵件系統的高...

【計算機網路筆記】2.2 The Web and HTTP Hello Guys, I’m LukeTseng. 歡迎你也感謝你點入本篇文章，本系列主要讀本為《Computer Networking: A Top-Down Approach, 8th Edition》，就是計算機網路的聖經，會製作該系列也主要因為修課上會用到。若你喜歡本系列或本文，不妨動動你的手指，為這篇文章按下一顆愛心吧，或是追蹤我的個人公開頁也 Ok。 2.2.1 Overview of HTTP（HTTP 的概觀） 什麼是 HTTP？ HTTP（HyperText Transfer Protocol），中譯「超文本傳輸協定」，是 Web 的核心應用層協定。 它定義了客戶端（Client）和伺服器（Server）之間「如何對話」的規則。 也規定了訊息的結構（語法）以及交換訊息的方式（語義）。 為什麼需要 HTTP？ 在 1990 年代初期，網際網路主要用於傳輸文字和文件。 為了讓這些文件（也稱為網頁，Web Pages）能在不同的電腦系統之間互相請求和傳送，需要一個通用的標準。 HTTP 即該標準，讓大家可用...

【計算機網路筆記】2.1 Principles of Network Applications Hello Guys, I’m LukeTseng. 歡迎你也感謝你點入本篇文章，本系列主要讀本為《Computer Networking: A Top-Down Approach, 8th Edition》，就是計算機網路的聖經，會製作該系列也主要因為修課上會用到。若你喜歡本系列或本文，不妨動動你的手指，為這篇文章按下一顆愛心吧，或是追蹤我的個人公開頁也 Ok。 2.1.1 Network Application Architectures（網路應用程式架構） 在現代網路應用開發中，開發者通常會在以下兩種典範中擇一使用： 主從式架構（Client-Server Architecture） 對等式架構（Peer-to-Peer, P2P Architecture） 主從式架構（Client-Server Architecture） 這是目前最常見、也最傳統的架構模式（例如 Web、Email）。 在此架構中會有永遠開啟的主機，稱之為伺服器（Server）。 伺服器會服務其他許多主機...

【計算機網路筆記】1.5 Protocol Layers and Their Service Models Hello Guys, I’m LukeTseng. 歡迎你也感謝你點入本篇文章，本系列主要讀本為《Computer Networking: A Top-Down Approach, 8th Edition》，就是計算機網路的聖經，會製作該系列也主要因為修課上會用到。若你喜歡本系列或本文，不妨動動你的手指，為這篇文章按下一顆愛心吧，或是追蹤我的個人公開頁也 Ok。 1.5.1 Layered Architecture（分層架構） 航空系統的比喻 網際網路是一個非常複雜的系統，包含了應用程式、協定、端系統、封包交換機和各種連結層媒介。 為了理解這個複雜的系統，書中以航空系統作為比喻。 搭飛機的過程當中涉及了票務代理、行李檢查、登機口人員、機師、飛機、空中交通管制等。 若要把這個系統描述清楚，可依照「動作發生的順序」來分層： Image Source：Image Source：Computer Networking: A Top-Down Approach (8th ed.,...

【計算機網路筆記】1.4 Delay, Loss, and Throughput in Packet-Switched Networks Hello Guys, I’m LukeTseng. 歡迎你也感謝你點入本篇文章，本系列主要讀本為《Computer Networking: A Top-Down Approach, 8th Edition》，就是計算機網路的聖經，會製作該系列也主要因為修課上會用到。若你喜歡本系列或本文，不妨動動你的手指，為這篇文章按下一顆愛心吧，或是追蹤我的個人公開頁也 Ok。 1.4.1 Overview of Delay in Packet-Switched Networks（封包交換網路中的延遲概述） 該節核心概念：解釋封包從源頭（Source）經過一系列路由器（Routers）到達目的地（Destination）的過程中，為什麼會發生延遲（Delay），以及這些延遲是由哪些部分組成的。 一個封包在單一節點所經歷的延遲總和定義為四個主要部分的累加： 節點處理延遲（Nodal Processing Delay） 佇列延遲（Queuing Delay） ...

【計算機網路筆記】1.3 The Network Core Hello Guys, I’m LukeTseng. 歡迎你也感謝你點入本篇文章，本系列主要讀本為《Computer Networking: A Top-Down Approach, 8th Edition》，就是計算機網路的聖經，會製作該系列也主要因為修課上會用到。若你喜歡本系列或本文，不妨動動你的手指，為這篇文章按下一顆愛心吧，或是追蹤我的個人公開頁也 Ok。 註：後來改成看第八版了，發現第七版在一些資訊蠻落後的。 1.3.1 Packet Switching（封包交換） 基本概念與封包 回顧 1.1 若要寄一封很長的電子郵件或下載一個很大的高畫質影片，網路不會一次把整個巨大的檔案傳出去。 來源終端系統會將這些訊息切成較小的資料塊，這些資料塊被稱為封包（Packet）。 在來源與目的地終端系統之間，每個封包都會經過通訊連結（Communication Links）與封包交換（Packet Switches）設備，而封包交換設備主要有兩種類型： 路由器（router） 連結層交換器（link-layer switch...

【計算機網路筆記】1.2 The Network Edge Hello Guys, I’m LukeTseng. 歡迎你也感謝你點入本篇文章，本系列主要讀本為《Computer Networking: A Top-Down Approach, 7th Edition》，就是計算機網路的聖經，會製作該系列也主要因為修課上會用到。若你喜歡本系列或本文，不妨動動你的手指，為這篇文章按下一顆愛心吧，或是追蹤我的個人公開頁也 Ok。 終端系統（End System） 回顧 1.1： 終端系統（End Systems） = 主機（Hosts） 在網路術語中，連接到網際網路的電腦和其他設備（如智慧型手機、平板、甚至現在的物聯網設備如恆溫器、汽車等）被稱作終端系統或主機。 而主機分成兩大類： 客戶端（Client）：通常是桌機、筆電、手機等，主要是發起請求的一方。 伺服器（Server）：通常是更強大的機器，用來儲存和發送網頁、影片、電子郵件等。現代伺服器集中在大型的資料中心（Data Centers）裡，如 Google 就有數十個大型資料中心，每個資料中心可能有數十萬台伺服器。 1.2....

【計算機網路筆記】1.1 What Is the Internet? Hello Guys, I’m LukeTseng. 歡迎你也感謝你點入本篇文章，本系列主要讀本為《Computer Networking: A Top-Down Approach, 7th Edition》，就是計算機網路的聖經，會製作該系列也主要因為修課上會用到。若你喜歡本系列或本文，不妨動動你的手指，為這篇文章按下一顆愛心吧，或是追蹤我的個人公開頁也 Ok。 1.1.1 A Nuts-and-Bolts Description（基本要素描述） 註：nuts and bolts 直翻就是螺帽跟螺栓，引伸為「具體細節」、「基本要素」或「實際運作的基礎」。因為螺帽和螺栓是機械中最基本且不可或缺的零件，沒有它們，大型機器也無法運作，因此 nuts and bolts 比喻事物最核心且基礎的部分。 該節以「硬體」的角度來看網際網路。 網際網路的節點：主機與終端系統（Hosts / End Systems） 網際網路（Internet）即為電腦網路（Computer Network），將全球數十億個運算裝置（Comp...

【Uva 題庫解題】CPE 二顆星選集 - part1 本筆記及該系列主要以每篇 5 題為主，也僅供筆者個人學習用途，斟酌參考。 若你喜歡本筆記，不妨為文章按下一顆愛心，或是追蹤我的個人公開頁，感謝您點入本篇筆記。 CPE 二顆星選集來源：https://par.cse.nsysu.edu.tw/~advprog/star.php Uva 151 - Power Crisis PDF Source：https://onlinejudge.org/external/1/151.pdf Uva Online Judge：https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=87 Zerojudge：https://zerojudge.tw/ShowProblem?problemid=q891 該題為約瑟夫問題的變體。 題目架構： 共 $N$ 個地區（ $1$ 到 $N$ ） 地區 $1$ 總是第一個被切斷。 剩下 $N-1$ 個地...

【C++】競程筆記（約瑟夫問題） 歡迎您點進本篇文章，本系列旨在記錄與筆記個人學習歷程，內容僅供學習用途，斟酌參考。若你喜歡本文，也可以為本篇文章按愛心，或是追蹤我來取得最新文章的資訊。 什麼是約瑟夫問題（Josephus Problem）？ 約瑟夫問題（Josephus Problem）是一個經典的數學和演算法問題，而同樣的問題又稱為約瑟夫環。 歷史由來： 這個問題是以弗拉維奧·約瑟夫斯命名的，他是1世紀的一名猶太歷史學家。他在自己的日記中寫道，他和他的40個戰友被羅馬軍隊包圍在洞中。他們討論是自殺還是被俘，最終決定自殺，並以抽籤的方式決定誰殺掉誰。約瑟夫斯和另外一個人是最後兩個留下的人。約瑟夫斯說服了那個人，他們將向羅馬軍隊投降，不再自殺。約瑟夫斯把他的存活歸因於運氣或天意，他不知道是哪一個。 From Wikipedia 問題定義 約瑟夫問題的標準數學模型如下： 總人數（$n$）：有 $n$ 個人圍成一圈，編號為 $1, 2, …, n$。 報數間隔（$m$ 或 $k$）：從第 1 個人開始報數（從 1 報到 $m$）。 規則： 報到 $m$ 的人出局（被殺）。 從...

【C++】競程筆記（背包問題 習題練習） 練習題目參考自：NTUCPC Guide，此筆記僅為個人學習用途。 電車遊戲 這道題是 0/1 背包問題或集合劃分的變形題。 Problem Source：https://oj.ntucpc.org/problems/803 該題目標是將 $N$ 個移動距離 $a_i$ 分配到兩個集合中：一個集合是「向左走（$X$軸）」，另一個集合是「向上走（$Y$軸）」。 設所有 $a_i$ 的總和為 $S$，且向左走的總距離為 $x$，那麼向上走的總距離就是 $S - x$。 題目要求最小化距離的平方：$x^2 + (S - x)^2$。 定義狀態：Boolean 陣列 $dp[j]$ 為是否能夠湊出總和為 $j$ 的移動距離。 若 $dp[j]$ 為 true，表示可從給定的數字中選出若干個，使其總和剛好為 $j$（作為 $X$ 軸的移動距離）。 定義轉移式： 對每個新移動距離 $v$（為輸入的 $a_i$），更新所有可能的 $j$。 若在之前的步驟中已能湊出 $j$（$dp[j] = true$)，則加上現在的 $v$ 後，即可湊出 $...

【C++】競程筆記（背包問題） 題目範例參考：NTUCPC Guide，此筆記僅為個人學習用途。 最後更新時間： 什麼是背包問題 背包問題（Knapsack Problem）是一種組合最佳化的 NP-Complete 問題，有著多種變形，其中最基礎的是「0/1 背包問題」。 在 DP 裡面，背包問題是最經典且常見的題型之一。 01 背包問題 Problem Source：https://oj.ntucpc.org/problems/801 所謂 0 1 就是物品可拿或不拿。 題目敘述： 有 $N$ 個物品編號 $1 \sim N$ ，第 $i$ 個物品的重量和價值分別是 $w_i$ 和 $v_i$ 。學姐打算從這 $N$ 個物品選其中一些帶走，但她只有大小為 $W$ 的背包，也就是說她選擇的物品總重不能超過 $W$ 。請問背包能容納的物品的總價值最大是多少？ 如果直接定義 $dp[i]$ 是前 $i$ 個物品的最大總價值，是不實際的，因為還要考慮到 $W$ 重量的因素。 因此用到二維 DP 觀念：$dp[i][j]$ 為前 $i$ 個物品且背包當前容量限制為 $j$ 時，能獲得...

【考試向】資料結構筆記（鏈結串列） 歡迎你點入本篇文章！我是 LukeTseng，本系列文章主要整理自學資料結構的一些知識，如果你喜歡我的文章，麻煩您不吝嗇的在文章底下按下一顆愛心，或是追蹤我唷～ 最後更新日期： 單向鏈結串列（Singly Linked list） 一般的陣列會在連續的記憶體空間中儲存資料。 鏈結串列可將資料儲存在不連續（non-contiguous）的記憶體空間中。 連續的壞處： 在中間插入需要將後面的元素各移動一格。 做刪除操作也要將後面元素往前補上去。 而在鏈結串列只需要改變指標指向就可以做到插入、刪除的操作。 在存取元素方面，陣列只需 $O(1)$ ，因為有 index，而鏈結串列需要 $O(n)$ ，因為要從頭一個一個找。 陣列 v.s. 鏈結串列 陣列（Array） 鏈結串列（Linked-list） 記憶體空間 連續 不連續 大小 固定 動態 插入/刪除操作 慢（要移動後面的所有資料） 快（只需改變指標指向） 讀取資料 $O(1)$ $O(n)$ 組成的基本要素 鏈結串列由數個節點（node）組成，一個節點又由...