用 cut property 證明 Prim 與 Kruskal|Stanford CS161 第 15 堂
MST 的核心不是背兩支演算法,而是維持『目前選邊仍包含於某棵 MST』,再用 cut property 證明 Prim 與 Kruskal 每一步都安全。
第 104 頁,共 129 頁
MST 的核心不是背兩支演算法,而是維持『目前選邊仍包含於某棵 MST』,再用 cut property 證明 Prim 與 Kruskal 每一步都安全。
Ford–Fulkerson 在殘餘網路沿 augmenting path 推流;找不到路時,可達集合形成與 flow 同值的 cut,同時證明最大流、最小割與兩者相等。
Deferred Acceptance 允許暫時接受後再反悔;proposal 的單調性證明它在 O(n²) 結束、產生 stable matching,且偏向 proposal 的一側。
期末課以 slides 回顧 CS161 工具箱,再用 LP duality、Reed–Solomon 與 ML-assisted algorithms 指向後續方向;官方沒有提供 notes。
選型的主判準沒有變,仍然是採用度——而 AI 讓它更重要,不是更不重要:用的人多,訓練語料就多,agent 寫出來的正確率就高。這個系列整理的另外五條判準(文件的機器可讀性、型別、原始碼在不在你 repo 裡、資料骨架、機器可呼叫性)是用來在採用度相近時分勝負,或估算你選冷門要付多少代價。
AI SDK v5 把一則 AI 訊息拆成 parts 陣列——text、reasoning、source-url、tool-* 各自是獨立片段。這個資料結構決定了現代 AI 對話介面怎麼寫:render 時 switch part.type,每種片段交給對應元件。這篇拆解 parts 模型的設計邏輯、useChat 的串流機制,以及它如何成為 AI Elements 這類元件庫的地基。
Drizzle ORM 是一個 SQL-first 的 TypeScript ORM——query builder 長得像 SQL,agent 寫出來的查詢在 diff 裡讀得懂。零依賴、約 7.4 KB gzipped,原生支援 Cloudflare D1、Neon、Turso 等 edge database。版本至今仍是 0.45.2,但週下載量已達 1,690 萬,超過 Prisma 的 1,380 萬。
llms.txt 是 Jeremy Howard 於 2024-09-03 提出的慣例(規範已更新至 v2):在網站根目錄放一份給 LLM 讀的 Markdown 索引。六個前端文件站實測:TanStack、shadcn、Zustand、AI SDK、Next.js 都有,React Router 是唯一 404。配套的 llms-full.txt(全文版)Anthropic、Cloudflare 等也已採用。這篇講規範內容、誰在用、以及它為什麼開始影響套件選型。
元件分發向來只有兩條路:npm 套件(黑盒依賴)或手動複製貼上。shadcn registry 把第三條路標準化——元件以 JSON 描述原始碼與依賴,CLI 一鍵裝進你的 repo 變成你的程式碼。任何人都能架自己的 registry(AI Elements 就是一個),官方 MCP server 更讓 AI agent 直接瀏覽與安裝元件。
Supabase 不只是 Firebase 的開源替代,它的核心設計是把 Auth、Storage、Realtime 全部建在 PostgreSQL 的 schema 和 WAL 上。結果是:你可以用一條 SQL 查所有東西,pgvector 直接用,agent 寫 SQL 就能操作整個平台。108k GitHub stars、Apache 2.0 授權、Free 方案 500 MB 資料庫。
自架一個 24 小時跑著的 agent,等於在自己網路裡開了一個必須從外面連得到、又不能開在公網上的東西。這篇拆 Tailscale 的四個機制各自解決什麼:tailnet 解決連得到、subnet router 解決碰內網、tag 與 ACL 解決權限邊界、policy 秒級生效與 tailnet lock 解決收得回。附 2026-08 實查的定價:Personal 免費、6 個使用者、user device 無上限、50 個 tagged resource。
TanStack Router(2023-12 發 1.0,週下載約 20M)把路徑、params、search params 全部做成編譯期推導:導航到不存在的路由是型別錯誤,不是執行期 404。這篇拆解它的三個核心設計——型別安全、search params 一等公民、與 Query 整合的 loader——以及為什麼這在 AI agent 寫碼的時代價值被放大。
Temporal 是 durable execution 平台(Server 1.31.2、Python SDK temporalio 1.31.0,MIT,2026-08 實查)。它跟 BullMQ / Celery 那種任務佇列的差別不是規模,是保證的東西不同:佇列保證訊息被消費,Temporal 保證一段橫跨多次外部呼叫的流程走完。代價是工作流程碼必須決定性——而 LLM 呼叫天生非決定性,這篇講這個張力怎麼解、什麼時候不划算。
Trigger.dev 是 Apache 2.0 的持久任務平台(v4.5.12,2026-08 實查),用 CRIU 對整個 Node.js 行程做記憶體快照來暫停與復原。跟 Temporal 的 replay 模型不同,它不重跑你的編排碼、不要求決定性——LLM 呼叫直接寫在 task 裡就行。代價是快照無法保留 TCP 連線,還原後要自己重建;而且快照是 cloud-only,自架拿不到。
WebMCP 讓網頁用 document.modelContext.registerTool() 把自己的功能註冊成 agent 可呼叫的工具,取代 agent 猜 DOM 點按鈕。Chrome 已在 149 開 origin trial、預計 157 進 stable,Edge 150 跟進。但 WebKit 明確表態反對(「agent 本質上是輔助科技,網站不該把它單獨挑出來對待」),Mozilla 給 neutral。這篇講兩套 API 怎麼寫、安全模型擋在哪、以及在只有一個半引擎支持的情況下要不要現在投資。
在 109 篇確實含中國用語的文章上,zhtw-mcp 精確率 29.4%、召回 85.2%,twlint 是 21.2% / 82.5%——但 twlint 有 195 個 error 級判斷是把合法正體字當簡體字(干→幹 60 次、只→隻 15 次),跑 --fix 會毀掉文章。最有用的發現不是誰勝出:zhtw-mcp 幫我補了五個自己漏抓的中國用語,也擋下一個我誤列的(審計)。工具的價值在校準你的清單,不是取代它。
Zod 週下載 224M(2026-08 實查),已遠超「表單驗證庫」的定位:API 邊界、環境變數、路由 search params、LLM tool schema 與 structured output,全在用同一套 schema。核心機制是「一次定義、兩層收穫」——執行期驗證與靜態型別從同一個來源推導。Zod 4(2025-07 上 npm)主打更快、更省 tsc。
行為面試不是靠臨場發揮,而是靠事前準備好的故事庫。AI Engineer 的行為面試有獨特的考點:AI 倫理(bias、fairness、privacy)、技術決策的影響力敘事(為什麼選這個模型/架構)、跨團隊推動 ML 專案的經驗。準備策略:建立 8-10 個 STAR 故事,每個故事練到能在 2 分鐘內講完。
AI Engineer 的 coding 面試和 SWE 不完全一樣——除了 LeetCode medium,還會出 ML-flavored 的題(實作 tokenizer、寫 batch inference pipeline、處理稀疏矩陣)。準備策略:LeetCode medium 練到 70% 通過率就夠,剩下的時間花在 numpy/pandas 操作、資料處理 pipeline、以及 ML 相關的程式題。
深度學習面試重點不是推導反向傳播,而是能不能解釋架構背後的設計直覺。高頻考點:CNN 的 locality 與 translation invariance、RNN 到 Transformer 的演進為什麼必要、self-attention 的計算邏輯與複雜度、BatchNorm vs LayerNorm 的適用場景、常見的 training tricks(learning rate schedule、gradient clipping、mixed precision)。