Programming

什麼是 AI & ML & DL 人工智慧是我們想要達成的目標，而機器學習是想要達成目標的手段，希望機器通過學習的方式，變得跟人一樣聰明。 而深度學習就是機器學習的其中一種方法。 人工智慧(Aritificial Intelligence, AI) → 目標 機器學習(Machine Learning, ML) → 手段 深度學習(Deep Learning, DL) … 在機器學習出現之前 生物的行為取決於兩件事，一個是後天學習的結果，一個是天生的本能。 Hand-crafted rules: 人類為機器設定好的天生本能 僵化，無法超越創造者 需要大量人力，不適合小企業 機器學習 寫程式讓機器可以學習 → 尋找關聯資料的函式 舉例：語音辨識、影像辨識、Alpha Go、對話機器人 框架(Framework) 設定一定量的函數 餵入數據 評估函數的好壞 找出最好的函數 \(\begin{array}{rc} \text{step1}&\boxed{\text{Define a set of function}}\\ &\downarrow\\ \text{step2}&\boxed{\text{Evaluate goodness of function}}\\ &\downarrow\\ \text{step3}&\boxed{\text{Pick the best function}}\end{array}\) 告訴機器 input 和正確的 output 這就叫作 supervised learning。 機器學習相關的技術 任務(Task) 迴歸(Regression) Regression 指的是函數的輸出為 scalar(數值)，如 PM2.5。 分類(Classification) Classification 指的是函數的輸出為 東西的類別。 當分類為 Yes or No，則為 Binary Classificatino，如垃圾郵件。 當分類是多個選項的，則為 Multi-Classification，如新聞分類。 結構性學習(Structured Learning) 讓機器的輸出具有結構性。 如語音辨識，聲音訊號為輸入，句子為輸出。 如影像辨識，圖片是輸入，人名是輸出。 方法(Method) 選不同的 function set 就是選不同的 model。 ...

Deque 不同於 stack 與 queues， deques 兩個端點都支援擴展。 基於 doubly linked list，deques 有幾項額外的特徵： 支援隨機存取 插入元素時間 \(O(1)\) 函式 1. push_front() 2. push_back() 3. front() 4. back() 5. begin() 6. end() 7. insert() 8. erase() 9. pop_front() 10. pop_back() 11. empty() 12. clear() 13. random_access() 內部運作原理 上述所有函數和操作都在雙鏈表中以O（1）時間執行，但這些清單不能隨機訪問任何元素。C++中的deque也是如此。這個 O（1） 在 deque 中可以使用圓形陣列來實現。使用循環陣列，可以在O（1）時間內實現從陣列的正面和背面插入和刪除等操作以及元素的隨機訪問。但這帶來了一個問題。當 deque 增長到超出容量時，使用者將需要將數位大小加倍，並將所有數據複製到陣列中。此外，如果數據是某個使用者定義的對象，那麼加倍和複製數據的成本就會變得非常昂貴。 這是一個基本的解決方案。Deque使用一些棘手的實現，當它說O（1）來push_back（）和push_front（）時，它實際上是調用的複製構造函數數量的常數時間。因此，如果數據物件是具有多個成員的某個類物件，則最小化複製構造函數調用的數量將節省時間。此外，複製構造函數調用的次數是恆定的。現在讓我們看看如何實現這一點。 這可以通過使用指向一些固定大小的塊的指標數位來實現，這些塊包含deque數據。下面是一個說明性示例。 這些 Deque 數據被劃分為固定大小的塊。在這裡，我們考慮了將數據劃分為大小為5的固定塊。 塊的填充從指標的兩個 deque 陣列的中間開始，並使用push_front和push_back操作向前和向後擴展。中間塊通常是滿的，當它被填滿時，數據被移動到上部或下部塊。 在上部塊中，元素以相反的順序推送，因為在這種情況下，填充數據的第一個位置將是4，然後是3，2，1，0。但是在中間和下部塊中，數據按正向順序填充，如0，1，2，3，4等。 當上面的塊被填滿時，指標將創建一個新塊並開始指向一個新的數位塊。這為更多數據創造了空間。在這種情況下，也可以填充指標塊。這會導致一個問題。 這是加倍來救援的時候。在加倍時，指標陣列的大小加倍。這不會複製整個數據，而只會複製指標。這是許多人在討論恆定時間時提出的一般論點。時間在調用的複製構造函數數方面保持不變。 如果數據集非常大，則指標塊幾乎不會執行加倍，因為單個指標可以指向大量數據塊。因此，指標陣列被填充並加倍的可能性非常小。

C++ Custom Comparator sort(iter, iter, comp) Lambda function int main(){ auto comp = [](int a, int b){ return a < b; } vector<int> = {3,6,7,2,1,9,5,4,8}; sort(vec.begin(), vec.end(), comp); // 1,2,3,4,5,6,7,8,9 } Usual boolean function bool comp(const int& a, const int& b){ return a < b; } int main(){ vector<int> = {3,6,7,2,1,9,5,4,8}; sort(vec.begin(), vec.end(), comp); // 1,2,3,4,5,6,7,8,9 } Old solution using struct/class with () operator struct cmp { bool operator() (int a, int b) const { return a < b; } }; int main(){ vector<int> = {3,6,7,2,1,9,5,4,8}; sort(vec.begin(), vec.end(), comp()); // 1,2,3,4,5,6,7,8,9 } priority_queue(element, container, comp) Modern C++20 Solution(lambda) We can use lambda function as comparator. As usual, comparator should return boolean value, indicating whether the element passed as first argument is considered to go before the second in the specific strict weak ordering it defines. int main(){ auto comp = [](int a, int b){ return a < b; } vector<int> vec = {3,6,7,2,1,9,5,4,8}; priority_queue<int, vector<int, decltype(comp)> pq; for (int num : vec) pq.push(num); while (!pq.empty()) { cout << pq.top() << " "; // 9,8,7,6,5,4,3,2,1 pq.pop(); } cout << endl; } Modern C++11 Solution(lambda) Before C++20 we need to pass lambda function as argument to set constructor. int main(){ auto comp = [](int a, int b){ return a < b; } vector<int> vec = {3,6,7,2,1,9,5,4,8}; priority_queue<int, vector<int, decltype(comp)> pq(comp); for (int num : vec) pq.push(num); while (!pq.empty()) { cout << pq.top() << " "; // 9,8,7,6,5,4,3,2,1 pq.pop(); } cout << endl; } Usual function Make comparator as usual boolean function bool comp(int a, int b){ return a < b; } int main(){ vector<int> vec = {3,6,7,2,1,9,5,4,8}; priority_queue<int, vector<int, decltype(&comp)> pq(comp); // priority_queue<int, vector<int, decltype(comp)*> pq(comp); // in C++20, constructor can be ignored the same as lambda function. for (int num : vec) pq.push(num); while (!pq.empty()) { cout << pq.top() << " "; // 9,8,7,6,5,4,3,2,1 pq.pop(); } cout << endl; } Old solution using struct/class with () operator struct cmp { bool operator() (int a, int b) const { return a < b; } }; int main(){ vector<int> = {3,6,7,2,1,9,5,4,8}; priority_queue<int, vector<int>, comp> pq(vec.begin(), vec.end()); while (!pq.empty()) { cout << pq.top() << " "; // 9,8,7,6,5,4,3,2,1 pq.pop(); } cout << endl; } Alternative solution: create struct/class from boolean function bool comp(int a, int b){ return a < b; } #include <type_traits> using Cmp = integral_constant<decltype(&comp), &comp>; int main(){ vector<int> = {3,6,7,2,1,9,5,4,8}; priority_queue<int, vector<int, decltype(&comp)> pq(comp); for (int num : vec) pq.push(num); while (!pq.empty()) { cout << pq.top() << " "; // 9,8,7,6,5,4,3,2,1 pq.pop(); } cout << endl; }

pair 函式庫 #include <utility> 宣告 pair<data_type1, data_type2> Pair_name; 初始化 pair<int, int> p1; // 宣告但不初始化 pair<int, char> p2(1, 'a'); // 不同資料型態的初始化 pair<int, int> p3(1, 10); // 同資料型態的初始化 pair<int, int> p4(p3); // 利用其它 pair 來初始化 pair<int, int> p5 = {1, 2} // 用 assign 的方式初始化 p2 = make_pair(1, 'a'); // 利用 make_pair 函式 成員 .first .second 函式 1. make_pair(v1, v2); 2. pair1.swap(pair2); 3. tie(a,b) 示例 #include <iostream> #include <utility> using namespace std; int main(){ // initialize pair<int,int> p1; pair<int,int> p2(2,4); pair<int,char> p3(3,'c'); pair<int,int> p4(p2); pair<int,int> p5 = {5,10}; // member cout << p2.first << " " << p2.second << endl; // 2 4 cout << p3.first << " " << p3.second << endl; // 3 c cout << p4.first << " " << p4.second << endl; // 2 4 cout << p5.first << " " << p5.second << endl; // 5 10 // function p1 = make_pair(1,2); cout << p1.first << " " << p1.second << endl; // 1 2 // a.swap(b) p1.swap(p2); cout << p1.first << " " << p1.second << endl; // 2 4 cout << p2.first << " " << p2.second << endl; // 1 2 // tie(a,b) = pair int a, b; tie(a, b) = p1; cout << a << " " << b << endl; // 2 4 return 0; }

HDLBits HDLBits 是一系列小型電路設計的練習，用於使用 Verilog 硬體描述語言(HDL)進行數位硬體設計。 由教學的題型由淺入深，逐步建立起電路設計的技能。 每個問題都會要求讀者使用 Verilog 設計一個小電路。HDLBits 會對提交的程式碼作判讀。透過一組測試碼來進行向量模擬，並與解答比較，檢查正確性。 Catalog 1. Getting Started 2. Verilog Language 3. Circuits 4. Verification: Reading Simulations 5. Verification: Writing Testbenches 6. CS450 1 Getting Started \(\text{assign one}\) Build a circuit with no inputs and one output. The output should always drive 1 (or logic high). module top_module( output one); assign one = 1'b1; endmodule \(\text{assign zero}\) Build a circuit with no inputs and one output that outputs a constant 0. module top_module( output zero ); assign zero = 1'b0; endmodule

1. Getting Started 2. Verilog Language 3. Circuits 4. Verification: Reading Simulations 5. Verification: Writing Testbenches 6. CS450 2 Verilog Language 2.1 Basics wire Create a module with one input and ont output that behaves like a wire module top_module( input in, output out); assign out = in; endmodule multi-in-out Create a module with 3 inputs and 4 outputs that behaves like wires that makes these connections: module top_module( input a,b,c, output w,x,y,z ); assign w = a; assign x = b; assign y = b; assign z = c; endmodule not gate Create a module that implements a NOT gate. module top_module( input in, output out ); assign out = ~in; endmodule and gate Create a module that implments an AND gate. module top_module( input a,b, output out ); assign out = a & b; endmodule nor gate Create a module that implements a NOR gate. A NOR gate is an OR gate with its output inverted. A NOR function needs two operators when written in Verilog. module top_module( input a,b, output out ); assign out = ~(a|b); endmodule xnor gate Create a module that implements a XNOR gate. module top_module( input a, b, output out ); assign out = ~(a^b); endmodule wire declaration Implement following circuits. Create two intermediate wires to connect the AND and OR gates together. Note that the wire that feeds the NOT gate is really wire out, so you do not necessarily need to declare a third wire here. Notice how wires are driven by exactly one source (output of a gate), but can feed multiple inputs. module top_module( input a,b,c,d, output out, out_n ); wire w1, w2; assign w1 = a & b; assign w2 = c & d; assign out = w1 | w2; assign out_n = ~out; endmodule 7458 The 7458 is a chip with four AND gates and two OR gates. Create a module with the same functionality as the 7458 chip. It has 10 inputs and 2 outputs. module top_module( input p1a, p1b, p1c, p1d, p1e, p1f, output p1y, intput p2a, p2b, p2c, p2d, output p2y ); wire w1a, w1b; wire w2a, w2b; assign w1a = p1a & p1b & p1c; assign w1b = p1d & p1e & p1f; assign p1y = w1a | w1b; assign w2a = p2a & p2b; assign w2b = p2c & p2d; assign p2y = w2a | w2b; endmodule 2.2 Vectors vector Build a circuit that has one 3-bit input, then outputs the same vector, and also splits it into three separate 1-bit outputs. Connect outputs o0 to the input vector’s position 0, o1 to position 1, etc. In a diagram, a tick mark with a number next to it indicates the width of the vector (or “bus”), rather than drawing a separate line for each bit in the vector. module top_module ( input wire [2:0] vec, output wire [2:0] outv, output wire o2, output wire o1, output wire o0 ); assign outv = vec; assign o0 = vec[0]; assign o1 = vec[1]; assign o2 = vec[2]; endmodule vector select Build a combinational circuit that splits an input half-word (16 bits, [15:0]) into lower [7:0] and upper [15:8] bytes. module top_module ( input [15:0] in, output [7:0] out_hi, output [7:0] out_lo ); assign out_hi = in[15:8]; assign out_lo = in[7:0]; endmodule vector swap A 32-bit vector can be viewed as containing 4 bytes (bits [31:24], [23:16], etc.). Build a circuit that will reverse the byte ordering of the 4-byte word. AaaaaaaaBbbbbbbbCcccccccDddddddd => DdddddddCcccccccBbbbbbbbAaaaaaaa This operation is often used when the endianness of a piece of data needs to be swapped, for example between little-endian x86 systems and the big-endian formats used in many Internet protocols. module top_module ( input [31:0] in, output [31:0] out ); assign out[31:24] = in[ 7: 0]; assign out[23:16] = in[15: 8]; assign out[15: 8] = in[23:16]; assign out[ 7: 0] = in[31:24]; endmodule vector gates uild a circuit that has two 3-bit inputs that computes the bitwise-OR of the two vectors, the logical-OR of the two vectors, and the inverse (NOT) of both vectors. Place the inverse of b in the upper half of out_not (i.e., bits [5:3]), and the inverse of a in the lower half. module top_module ( input [2:0] a, input [2:0] b, output [2:0] out_or_bitwise, output out_or_logical, output [5:0] out_not ); assign out_or_bitwise = a | b; assign out_or_logical = a || b; assign out_not[2:0] = ~a; assign out_not[5:3] = ~b; endmodule gate-prefix vector Build a combinational circuit with four inputs, in[3:0]. There are 3 outputs: out_and: output of a 4-input AND gate. out_or: output of a 4-input OR gate. out_xor: outout of a 4-input XOR gate. module top_module ( input [3:0] in, output out_and, output out_or, output out_xor ); assign out_and = & in; assign out_or = | in; assign out_xor = ^ in; endmodule vector concatenate Given several input vectors, concatenate them together then split them up into several output vectors. There are six 5-bit input vectors: a, b, c, d, e, and f, for module top_module ( input [4:0] a, b, c, d, e, f, output [7:0] w, x, y, z ); assign {w, x, y, z} = {a, b, c, d, e, f, 2'b11}; endmodule vector reverse Given an 8-bit input vector [7:0], reverse its bit ordering. module top_module( input [7:0] in, output [7:0] out ); assign {out[0], out[1], out[2], out[3], out[4], out[5], out[6], out[7]} = in endmodule module top_module( input [7:0] in, output [7:0] out ); always @(*) begin for (int i=0; i<8; i++) out[i] = in[8-i-1]; end endmodule module top_module( input [7:0] in, output [7:0] out ); generate genvar i; for (i=0; i<8; i = i+1) begin: my_block_name assign out[i] = in[8-i-1]; end endgenerate endmodule vector replication Build a circuit that sign-extends an 8-bit number to 32 bits. This requires a concatenation of 24 copies of the sign bit (i.e., replicate bit[7] 24 times) followed by the 8-bit number itself. module top_module ( input [7:0] in, output [31:0] out ); assign out = {{24{in[7]}}, in}; endmodule vector replication2 Given five 1-bit signals (a, b, c, d, and e), compute all 25 pairwise one-bit comparisons in the 25-bit output vector. The output should be 1 if the two bits being compared are equal. module top_module ( input a, b, c, d, e, output [24:0] out ); assign out = ~{{5{a}}, {5{b}}, {5{c}}, {5{d}}, {5{e}}} ^ {5{a,b,c,d,e}}; endmodule 2.3 Modules: Hierarchy By now, you’re familiar with a module, which is a circuit that interacts with its outside through input and output ports. Larger, more complex circuits are built by composing bigger modules out of smaller modules and other pieces (such as assign statements and always blocks) connected together. This forms a hierarchy, as modules can contain instances of other modules. ...

1. Getting Started 2. Verilog Language 3. Circuits 4. Verification: Reading Simulations 5. Verification: Writing Testbenches 6. CS450 3 Circuits 3.1 Combinational Logic 3.1.1 Basic Gates Wire module top_module ( input in, output out); assign out = in; endmodule GND module top_module ( output out); assign out = 1'b0; endmodule NOR module top_module ( input in1, input in2, output out); assign out = ~(in1|in2); endmodule Another Gate ...

4 Verification - Reading Simulations 4.1 Finding bugs in code 4.2 Build a circuit from a simulation waveform 1. Getting Started 2. Verilog Language 3. Circuits 4. Verification: Reading Simulations 5. Verification: Writing Testbenches 6. CS450

5 Verification - Writing Testbenches 1. Getting Started 2. Verilog Language 3. Circuits 4. Verification: Reading Simulations 5. Verification: Writing Testbenches 6. CS450

6 CS450 1. Getting Started 2. Verilog Language 3. Circuits 4. Verification: Reading Simulations 5. Verification: Writing Testbenches 6. CS450