Yaoの程式小窩

【計算機網路筆記】1.5 Protocol Layers and Their Service ModelsHello 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., p....

【計算機網路筆記】1.4 Delay, Loss, and Throughput in Packet-Switched NetworksHello 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 CoreHello 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 EdgeHello 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.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），將全球數十億個運算裝置（Computi...

【Uva 題庫解題】CPE 二顆星選集 - part1本筆記及該系列主要以每篇 5 題為主，也僅供筆者個人學習用途，斟酌參考。 若你喜歡本筆記，不妨為文章按下一顆愛心，或是追蹤我的個人公開頁，感謝您點入本篇筆記。 CPE 二顆星選集來源：https://par.cse.nsysu.edu.tw/~advprog/star.php Uva 151 - Power CrisisPDF 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$ 後，即可湊出 $j +...

【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）組成，一個節點又由以下...

【考試向】資料結構筆記（堆疊、佇列、環狀佇列、後序表示式）歡迎你點入本篇文章！我是 LukeTseng，本系列文章主要整理自學資料結構的一些知識，如果你喜歡我的文章，麻煩您不吝嗇的在文章底下按下一顆愛心，或是追蹤我唷～ 最後更新時間： 堆疊（Stack）特性：後進先出（LIFO：Last In First Out） 資料只能在頂端（Top）做堆入（Push），跟移除（Pop）。 Image Source：Stack Data Structure and Implementation in Python, Java and C/C++ 應用： Ctrl + Z 復原功能 函式呼叫 括號匹配 DFS（Depth First Search：深度優先搜尋） 時間複雜度： 堆入（Push）： $O(1)$ 移除（Pop）： $O(1)$ 優點： 記憶體管理高效：資料只在頂端操作，記憶體配置連續可預測。在系統層級（如 Call Stack），比堆積（Heap）快很多。 存取速度快（$O(1)$）：無論堆疊有多大，Push 跟 Pop 的時間複雜度永遠是 $O(1)$ 。 防資料碎...

【C++】競程筆記（多維 DP、LCS 最長共同子序列 習題練習）練習題目參考自：NTUCPC Guide，此筆記僅為個人學習用途。 823 . RGBProblem Source：https://oj.ntucpc.org/problems/823 先定義三種顏色的代號以及對分數的貢獻（權重）： 紅色（$j=0$）：權重為 $-v_i$（題目要求扣掉紅色數字總和）。 綠色（$j=1$）：權重為 $+v_i$（題目要求加上綠色數字總和）。 藍色（$j=2$）：權重為 $0$（藍色不影響分數）。 最後再來定義狀態：定義 $dp[i][j]$ 為考慮到第 $i$ 個數字，且將第 $i$ 個數字塗上顏色 $j$ 時，目前所能獲得的最大價值。 $i : 1 \le i \le N$ $j : 0 \le j \le 2$ （分別代表紅、綠、藍） 求 DP 轉移式： 題目限制「相鄰的數字必須標上不同的顏色」，要計算第 $i$ 個數字塗某個顏色時，第 $i-1$ 個數字必須是另外兩種顏色之一，最終解答是從中選取較大者，再加上當前顏色的權重。 對第 $i$ 個數字 ($i > 1...

【C++】競程筆記（多維 DP、LCS 最長共同子序列）題目範例參考：NTUCPC Guide，此筆記僅為個人學習用途。 什麼是多維的 DP?一開始入門 DP 所寫的全都是一維的 DP，例如在爬樓梯問題， $dp[i]$ 就表示成到達第 $i$ 階的方法數。 而當中只有一個變數，叫做 $i$ ，故稱為一維 DP。 多維的 DP 就是有多個變數的 DP，一個變數不足以清楚描述當前的子問題，需要兩個或更多的變數來鎖定狀態。 例如： 走迷宮需要 $x, y$ 座標兩個變數來表示 $dp[x][y]$ LCS（Longest Common Subsequence：最長共同子序列）需要字串 A 的位置 $i$ 和字串 B 的位置 $j$ 表示 $dp[i][j]$ 背包問題：需要物品編號 $i$ 和剩餘重量 $w$ 表示 $dp[i][w]$ VacationProblem Source：https://atcoder.jp/contests/dp/tasks/dp_c 狀態定義：不能只紀錄 $dp[i]$ 代表第 $i$ 天的最大快樂值，因為要知道第 $i$ 天到底做了什麼活動，才能...

【Pytorch 深度學習筆記】模型驗證與過擬合以及 Autograd 的細節哈囉大家好我是 LukeTseng，感謝您點進本篇筆記，該篇筆記主要配合讀本 《Deep Learning with pytorch》 進行學習，另外透過網路資料作為輔助。本系列筆記是我本人奠基深度學習基礎知識的開始，若文章有誤煩請各位指正，謝謝！ 本篇為 《Deep Learning with pytorch》 這本書 5.5.3 Training, validation, and overfitting 及 5.5.4 Autograd nits and switching it off 的相關筆記。 模型驗證（validation）在訓練模型時，最重要的目標是讓模型不僅能記住所給定的訓練資料，還能對沒見過的資料泛化（Generalization）。而最壞的情況是遇到過擬合。 :::info泛化（Generalization）指的是模型在訓練時從資料中學到「可重複使用的規律」，因此面對沒看過的新資料（同類型、但不是訓練集裡的樣本）也能做出合理的預測，而不是只有把訓練資料背起來而已。::: 因此需要有...

【Pytorch 深度學習筆記】Autograd 自動微分機制與 Optimizers 優化器哈囉大家好我是 LukeTseng，感謝您點進本篇筆記，該篇筆記主要配合讀本 《Deep Learning with pytorch》 進行學習，另外透過網路資料作為輔助。本系列筆記是我本人奠基深度學習基礎知識的開始，若文章有誤煩請各位指正，謝謝！ 本篇為 《Deep Learning with pytorch》 這本書 5.5 PyTorch’s autograd: Backpropagating all things 的相關筆記。 什麼是 Autograd在機器學習中，需要計算損失函數對參數（權重 $w$ 和偏差 $b$ ）的導數，以便更新參數。 雖然可以手動推導並解析運算式，但如果今天是擁有數百萬個參數的深層模型呢？總不可能一個一個手動去算吧，因此 PyTorch 提供一個機制叫做 Autograd。 只要給定一個前向運算式（無論多麼複雜），PyTorch 都能自動提供該運算式對其輸入參數的梯度。 使用 Autograd先前溫度計例子定義的模型函數、損失函數如下（Code So...