2024-10-08/15 課程問答簡記

檢討和回顧

學員作業清單

$s q r t (x)$

櫻木滑倒-Sakuragi

NE6121131
「整數平方根」在電腦領域的使用場景？與質數判定的關係？
若自然數
$n$ 沒有小於或等於根號
$n$ 的質因數，則
$n$ 就是質數（記得補充！）:
Ans : 這個問題可以用反證法去解答，先假設
$n$ 不是質數，則
$n = a * b$ (
$a > 1, b > 1$ ,
$a$ 、
$b$ 皆為正整數，且是
$n$ 的因數)，因為
$n$ 沒有小於或等於根號
$n$ 的質因數，所以
$a$ 跟
$b$ 必須要大於根號
$n$ (
$a > \sqrt{n}, b > \sqrt{n}$ )，這導致
$n = a * b > \sqrt{n} * \sqrt{n} = n$ 產生矛盾，所以
$n$ 是質數。
「質數」在密碼學中的應用? 詳見：RSA 質因數分解
- 質數在密碼學中的應用非常重要，尤其是在 RSA 這種加密技術裡發揮了關鍵作用。簡單來說，RSA 會利用兩個非常大的質數 𝑝 和 𝑞 來加密訊息，破解這樣的加密則需要將這個數分解成質因數，但由於這個過程極其困難，讓加密變得非常安全。雖然加密的規則是公開的，但只有擁有私密金鑰的人才能解密訊息。這有點像上鎖的信件，大家都可以看到鎖，但只有擁有鑰匙的人能打開。
  質數分解的困難性是這類加密系統的基礎，即使知道加密的方式，沒有快速找到質數的能力，依然無法解密。這樣的技術每天都應用在網路交易、銀行帳戶管理等方面，保護隱私和數據安全。質數的這種獨特性質讓加密變得簡單，但解密變得非常困難。

linked list

華一跤-slipontheway

P76131351 :

「從 linked list 中取出一個節點」的應用場景?以任務管理、排程為例如何包裝？
- 從 task list 中挑出任務並移走。將問題包裝為在一個ready queue中選擇要執行的task，將其標為執行中並從ready queue中移除。

參考：快慢指標

2024-10-15

devarajabc

如何將 in-order 的表示式新增至 binary-tree

(8+9)*(8+9) =>

8+9x5 => 8, 2^16 +1 ,9, 2^16+2, 5

使用 RPN（逆波蘭表示法）

(8+9)*(8+9) => 8 9 + 8 9 + *
 
    *
   /  \
  +     +
 / \   / \
8   9 8    9

read(char )

if(val == '+'){
    val = (1<<16)+1;
}else if (val == '*'){
    val = (1<<16)+1;
}else if(val == )
     


struct TreeNode {
     int val;
      struct TreeNode *left;
      struct TreeNode *right;
};

struct TreeNode* parent =NULL;
struct TreeNode* root = NULL;
struct TreeNode* current = root;

val

while(current != NULL){
parent = current;
if (val< current->val){
    current = current->left;
}else{
    current = current-> left;
}


}

過程發生的問題

對觀念不夠熟悉，在 Approach 階段沒有將 RPN 與面試題目對應。
在提出 Approach 階段沒有將程式碼列出。Approach 階段可以列出部分程式碼。
程式與提出的 Approach 看不出有二元樹與 RPN 的跡象。至少要有關鍵程式碼

jychen0611

(good) memory allocator

de-fragmentation
fast vs. O(1)
first-fit
Maximizing throughput
- minimizing the average time to satisfy allocate and free requests
Maximizing memory utilization
- 可被分配的記憶體空間受限於 disk 中 swap space 的大小
- peak utilization
  $U_{k} = \frac{m a x_{i <= k} P_{i}}{H_{k}}$
  - $P_{k}$ 表完成第 k 個請求後，總分配出去的 payload 大小
  - $H_{k}$ 表當前 heap 大小 (單調非遞減)

https://ossna2017.sched.com/event/BCsR

process control block (PCB)
ready queue
https://wiki.csie.ncku.edu.tw/embedded/freertos

Explicit allocator
- 須由 programmer 主動呼叫 free 釋放空間
- C, C++
Implicit allocator (garbage collector)
- allocator 自動偵測未被 program 使用的 block，並釋放該 block
- Lisp, ML, and Java

Implementation Issues

Free block organization.
- How do we keep track of free blocks?
Placement.
- How do we choose an appropriate free block in which to place anewly allocated block?
Splitting.
- After we place a newly allocated block in some free block, what do we do with the remainder of the free block?
Coalescing.
- What do we do with a block that has just been freed?

Image Not Showing Possible Reasons

The image was uploaded to a note which you don't have access to
The note which the image was originally uploaded to has been deleted

Learn More →

如圖，參考 CS:APP 的作法，

block = a one-word header + payload + some additional padding

考慮 32-bit 系統， 2-word(=2*4byte) alignment 的情境，每個 block 的大小必為 8 bytes 的倍數，因此末三 bits 必為 0，可用來存放其他資訊。

header 的前 29 bits 用以表示空間大小，剩餘 3 bits 用以表達該空間是否 free。
此外，malloc 回傳位址應為 payload 起始位置，由於 header 大小為 1-word，需移動 4 bytes，相當於 4 個 char。
free 時由於輸入為 payload 起始位置，若要修改 header 資訊則需走 4 bytes 回來，才能指向 header。

struct node{
    uint32_t  size;
    struct node* next;
};
void* my_allocate(struct node* head, uint32_t  n){
    if(!head)
        return NULL;
    struct node* cur = head;
    while(cur){
        if(!(cur->size & 1)  && cur->size>=n){
            cur->size &= 0xFFFFFFF8;
            return ((char*)cur+4); // 移動到 payload
        }    
        cur = cur->next;
    }
    return NULL;
}
void my_free(void* ptr){
    if(!ptr)
        return;
    struct node* block = (struct node*)((char*)ptr - 4); // 移回 header
    block->size |= 1;
}

P76131589

infix（中序表示式）轉換成 postfix（後序表示式）: Shunting Yard Algo.

a + b * ( c - d ) * e => a b c d - * e * +

struct Operator {
    int weight;
};

bool isOperator(const string &token) {
    return token == "+" || token == "-" || token == "*" || token == "(" || token == ")";
}

unordered_map<string, Operator> operators = {
    {"+", {1}}, {"-", {1}},
    {"*", {2}},
    {"(", {0}}, {")", {0}}
};

bool precedence(const string &op1, const string &op2) {
    return operators[op1].weight <= operators[op2].weight;
}

vector<string> infixToPostfix(const vector<string> &tokens) {
    stack<string> operator_stack;
    vector<string> output;

    for (const string &token : tokens) {
        if (isalnum(token[0])) {
            output.push_back(token);
        }
        else if (token == "(") {
            operator_stack.push(token);
        }
        else if (token == ")") {
            while (!operator_stack.empty() && operator_stack.top() != "(") {
                output.push_back(operator_stack.top());
                operator_stack.pop();
            }
            operator_stack.pop(); 
        }
        else if (isOperator(token)) {
            while (!operator_stack.empty() && isOperator(operator_stack.top()) && precedence(token, operator_stack.top())) {
                output.push_back(operator_stack.top());
                operator_stack.pop();
            }
            operator_stack.push(token);
        }
    }

    while (!operator_stack.empty()) {
        output.push_back(operator_stack.top());
        operator_stack.pop();
    }

    return output;
}