8/31/2023

Cấu trúc dữ liệu và thuật toán | Hàng đợi (Queue)


1. Cấu trúc dữ liệu hàng đợi và ứng dụng

Hàng đợi là một dạng CTDL mà ở đó thao tác chèn vào sẽ được diễn ra ở một đầu, thường gọi là phía sau hay cuối (back or rear), trong khi phép toán xóa chỉ được thực hiện ở phía còn lại, gọi là phía trước hay đầu (front or head).

Nguyên tắc của hàng đợi: Vào trước ra trước, First-In First-Oout (FIFO)


Giống với ngăn xếp, hàng đợi cũng có 2 cách cài đặt cơ bản là dùng mảng và con trỏ.

Hàng đợi cũng có rất nhiều ứng dụng trong thực tế, ví dụ như là:

- Trong hệ điều hành: hàng đợi xử lý sự kiện, quản lý tiến trình, xử lý các câu lệnh. CPU không thể chạy tất cả các task cùng lúc nên các task sẽ được sắp xếp theo thứ tự ưu tiên lần lượt.

- Web server: một trang web cần phải xử lý vài nghìn files của người dùng nhưng khả năng của trang web chỉ xử lý được 100 files cùng một lúc, lúc này chúng ta cần một hàng đợi để đưa các request vào hàng đợi để chờ xử lý.

- Ứng dụng khi in hoặc upload nhiều ảnh cùng lúc

- Lưu vết trong quá trình tìm kiếm, quay lui, vét cạn,...

- Duyệt đồ thị

2. Cài đặt ngăn xếp sử dụng mảng

Khai báo một struct Queue và viết các hàm tương ứng với các phép toán trên hàng đợi:

- isFull(): kiểm tra hàng đợi đã đầy chưa

- enqueue(): thêm phần từ vào cuối hàng đợi

- dequeue(): lấy phần tử ra khỏi đầu hàng đợi

- getFront(): xem phần tử đầu hàng đợi

- getRear(): xem phần tử ở cuối hàng đợi

Tùy thuộc vào từng bài toán, khi cần thêm những chức năng cụ thể nào cho hàng đợi thì chúng ta có thể viết thêm các hàng tương ứng để công việc được thực hiện một cách dễ dàng hơn.

#define INT_MIN -2147483648

struct Queue {
    int front, rear, size;
    unsigned capacity;
    int* array;
};

struct Queue* createQueue(unsigned capacity){
    struct Queue* queue = (struct Queue*) malloc(sizeof(struct Queue));
    queue->capacity = capacity;
    queue->front = queue->size = 0;
    queue->rear = -1;
    queue->array = (int*) malloc(queue->capacity * sizeof(int));
    return queue;
}

// Kiem tra queue day
int isFull(struct Queue* queue){
    return (queue->size == queue->capacity);
}

// Kiem tra queue rong
int isEmpty(struct Queue* queue){
    return (queue->size == 0);
}

// Them phan tu vao queue
void enqueue(struct Queue* queue, int item){
    if(isFull(queue)){
        return;
    }

    queue->rear = (queue->rear + 1);
    queue->array[queue->rear] = item;
    queue->size = queue->size + 1;
    printf("%d enqueued to queue\n", item);
}

int dequeue(struct Queue* queue){
    if(isEmpty(queue)){
        return INT_MIN;
    }

    int item = queue->array[queue->front];
    queue->front = (queue->front + 1);
    queue->size = queue->size - 1;
    return item;
}

int getFront(struct Queue* queue){
    if(isEmpty(queue)){
        return INT_MIN;
    }

    return queue->array[queue->front];
}

int getRear(struct Queue* queue){
    if(isEmpty(queue)){
        return INT_MIN;
    }

    return queue->array[queue->rear];
}

int main(){
    struct Queue* queue = createQueue(10);
    enqueue(queue, 1);
    enqueue(queue, 2);
    printf("Top of queue is %d", getFront(queue));
    printf("Rear of queue is %d", getRear(queue));

}

3. Cài đặt ngăn xếp sử dụng con trỏ

Với con trỏ thì chúng ta cũng cài đặt tương tự các hàm so với sử dụng mảng.


#include<stdio.h>
#include<stdlib.h>

struct node
{
    int data;
    struct node *next;
};

struct node *front = NULL, *rear = NULL;

void enqueue(int val)
{
    struct node *newNode = malloc(sizeof(struct node));
    newNode->data = val;
    newNode->next = NULL;

    if(front == NULL && rear == NULL){
        front = rear = newNode;
    } else {
        rear->next = newNode;
        rear = newNode;
    }
}

void dequeue()
{
    struct node *temp;

    if(front == NULL)
         printf("Queue is Empty\n");
    else
    {
        temp = front;
        front = front->next;

        if(front == NULL){
            rear = NULL;
        }

       free(temp);
    }

}

void printList()
{
    struct node *temp = front;

    while(temp)
    {
        printf("%d->",temp->data);
        temp = temp->next;
    }
    printf("NULL\n");
}

int main()
{
    enqueue(10);
    enqueue(20);
    enqueue(30);
    printf("Queue :");
    printList();
    dequeue();
    printf("After dequeue the new Queue :");
    printList();
    dequeue();
    printf("After dequeue the new Queue :");
    printList();

    return 0;
}

Xem đầy đủ code tại repo github: https://github.com/piandhust/data-structures/blob/main/queue.chttps://github.com/piandhust/data-structures/blob/main/queue_pointer.c

8/27/2023

Cấu trúc dữ liệu và thuật toán | Ngăn xếp (Stack)


1. Cấu trúc dữ liệu ngăn xếp và ứng dụng

Ngăp xếp là một dạng cấu trúc dữ liệu mà ở đó các thao tác với CTDL này chỉ diễn ra ở một đầu, được gọi là đỉnh của ngăn xếp (top). Hai thao tác phổ biến đối với ngăn xếp là đẩy vào (push) và lấy ra (pop), cả hai thao tác này đều tác động vào đỉnh của ngăn xếp.

Nguyên tắc của ngăn xếp: Vào trước ra sao, First-In Last-Out (FILO)

Có 2 cách cài đặt ngăn xếp là sử dụng mảng hoặc sử dụng con trỏ.

Mặc dù nhìn bề ngoài ngăn xếp có vẻ trông đơn giản nhưng nó lại có ứng dụng rất lớn trong thực tế. Ứng dụng trong sử dụng điều hướng các màn hình của điện thoại, ví dụ chúng ta đang ở một màn hình Settings của Facebook, Khi bấm vào General sẽ bị chuyển hướng sang một màn khác, vậy thì làm sao để khi bấm quay lại có thể quay lại đúng màn Settings một cách nhanh nhất? Đó chính là vứt nó vào ngăn xếp, mỗi khi bấm quay lại chỉ cần lấy nó ra từ đỉnh của ngăn xếp là được. Một số các ứng dụng khác của ngăn xếp như là lịch sử trình duyệt, hay là các cơ chế Undo (Redo) trong các trình soạn thảo văn bản. 

Ngăn xếp còn rất quan trọng trong việc giải một số bài toán như: 

- Tính giá trị biểu thức trung tố, hậu tố

- Bài toán cộng hai số lớn

- Bài toán kiểm tra ngoặc đúng 

- Bài toán đảo ngược xâu

2. Cài đặt ngăn xếp sử dụng mảng

Khai báo một struct Stack và viết các hàm tương ứng với các phép toán trên ngăn xếp: 

- isFull(stack): kiểm tra xem ngăn xếp đã đầy chưa 

- isEmpty(stack): kiểm tra ngăn xếp có rỗng không

- push(stack, item):  thêm phần tử vào ngăn xếp

- pop(stack): lấy phần tử ra khỏi ngăn xếp

- getTop(stack): xem phần tử ở đầu ngăn xếp và không xóa phần tử đó khỏi ngăn xếp

Tùy thuộc vào từng bài toán, khi cần thêm những chức năng cụ thể nào cho ngăn xếp thì chúng ta có thể viết thêm các hàm tương ứng để công việc được thực hiện một cách dễ dàng hơn.


#define INT_MIN -2147483648

struct Stack {
    int top;
    unsigned capacity;
    int* array;
};


// Khoi tao ngan xep
struct Stack* createStack(unsigned capacity){
    struct Stack* stack = (struct Stack*) malloc(sizeof(struct Stack));
    stack->capacity = capacity;
    stack->top = -1;
    stack->array = (int*) malloc(stack->capacity * sizeof(int));
}

// Kiem tra xem ngan xep day chua
int isFull(struct Stack* stack){
    return stack->top == stack->capacity - 1;
}

// Kiem tra ngan xep rong khong
int isEmpty(struct Stack* stack){
    return stack->top == -1;
}

// Them phan tu vao stack
void push(struct Stack* stack, int item){
    if(isFull(stack)){
        return;
    }

    stack->array[++stack->top] = item;
    printf("%d push to stack\n", item);
}

int pop(struct Stack* stack){
    if(isEmpty(stack)){
        return INT_MIN;
    }

    return stack->array[stack->top--];
}

int getTop(struct Stack* stack){
    if(isEmpty(stack)){
        return INT_MIN;
    }

    return stack->array[stack->top];
}

int main(){
    struct Stack* stack = createStack(10);
    push(stack, 2);
    push(stack, 3);
    printf("Top of value in stack: %d", getTop(stack));

}

3. Cài đặt ngăn xếp sử dụng con trỏ

Với con trỏ thì chúng ta cũng cài đặt tương tự các hàm so với cài đặt ngăn xếp sử dụng mảng.


#include <stdio.h>

struct Node {
    int data;
    struct Node* next;
};

struct Node* newNode(int val){
    struct Node* newN = (struct Node*) malloc(sizeof(struct Node));
    newN->data = val;
    newN->next = NULL;

    return newN;
}

void push(struct Node* head, int val){
    struct Node* newN = newNode(val);
    if(head == NULL){
        newN->next = NULL;
    } else {
        newN->next = head;
    }

    head = newN;

    printf("Top of stack is %d\n", head->data);
    printf("----------------\n");
}

int pop(struct Node* head){
    if(head == NULL){
        printf("Stack is empty\n");
        return;
    }

    int item = head->data;
    struct Node* tmp = head;
    head = head->next;
    free(tmp);

    printf("Top of stack is %d\n", head->data);
    return item;
}

int isEmpty(struct Node* head){
    return head == NULL;
}

int getTop(struct Node* head){
    if(head == NULL){
        return NULL;
    }

    return head->data;
}

int main(){
    struct Node* head = NULL;
    push(head, 10);
    pop(head);

    //printf("Top stack: %d", getTop(head));
}

Xem đầy đủ code tại repo github: https://github.com/piandhust/data-structures/blob/main/stack.chttps://github.com/piandhust/data-structures/blob/main/stack_pointer.c

8/19/2023

Cấu trúc dữ liệu và thuật toán | Mảng (Array) và Linked List


1. "Cấu trúc dữ liệu"

Cấu trúc dữ liệu là một họ các biến có thể có kiểu dữ liệu khác nhau, được liên kết với nhau theo một cách thức được quy định trước nào đó. Ví dụ như mảng là một dãy các ô có cùng kiểu dữ liệu xác định. 

Một số cấu trúc dữ liệu phổ biến như là: 

- Mảng

- Danh sách

- Đồ thị

- Ngăn xếp

- Hàng đợi

- Cây

Với các bài viết về cấu trúc dữ liệu này, mình sẽ đề cập tới khái niệm chính và cách cài đặt từng loại cấu trúc dữ liệu.

2. Cấu trúc dữ liệu mảng 

Dữ liệu dạng mảng là một dạng dữ liệu vô cùng phổ biến mà chúng ta có thể gặp thường xuyên trong mọi ngôn ngữ lập trình và mọi dự án.

Thông thường mảng thường được lưu trữ trên một dãy liên tiếp các ô nhớ trên bộ nhớ, vì vậy việc truy cập các phần tử trong mảng là cực kỳ nhanh chóng, nhưng lại bất lợi trong việc phân bổ thêm ô nhớ cho mảng.

Mảng thì rất quen thuộc rồi, các ngôn ngữ lập trình đều hỗ trợ hầu như mọi phép toán liên quan tới mảng, nên phần cài đặt mảng mình sẽ không đề cập tới trong phần này.

3. Cấu trúc dữ liệu danh sách liên kết đơn 

Danh sách liên kết đơn (hay một số tài liệu đề cập là danh sách móc nối đơn) là danh sách các phần tử mà mỗi phần tử sẽ chứa giá trị và một con trỏ chứa trỏ tới ô kế tiếp của danh sách.



Danh sách liên kết sẽ khắc phục được một số nhược điểm của việc sử dụng mảng đó là: 

- Bổ sung một phần tử tốn kém thời gian

- Lãng phí khoảng bộ nhớ trống khai báo ban đầu không dùng đến

- Phải duy trì một khoảng không gian lưu trữ liên tục trong bộ nhớ

3.1 Cài đặt danh sách liên kết đơn

Các ví dụ về cài đặt cấu trúc dữ liệu trong các bài viết mình sẽ sử dụng ngôn ngữ lập trình C.

Khai báo một struct node, và viết 5 hàm tương ứng với 5 phép toán trên danh sách liên kết: 

- isEmpty(): kiểm tra danh sách liên kết rỗng 

- print_list(): in danh sách phần tử 

- push(item): thêm phần tử vào đầu danh sách liên kết

- pop(): loại bỏ phần tử cuối danh sách

- insert_by_index(inx, item): chèn một phần tử vào vị trí bất kỳ trong danh sách liên kết

Tùy thuộc vào từng bài toán, khi cần thêm những chức năng cụ thể nào cho danh sách liên kết thì chúng ta có thể viết thêm các hàm tương ứng để công việc được thực hiện một cách dễ dàng hơn.

#include<stdio.h>
#define INT_MIN -2147483648

struct node {
    int data;
    struct node *next;
};

struct node* head = NULL;

int isEmpty(){
    return head == NULL;
}

void print_list(){
    struct node *current = head;

    while(current != NULL){
        printf("%d\n", current->data);
        current = current->next;
    }
}

// push to front list
void push(int item){
    struct node* newN = (struct node*) malloc(sizeof(struct node));
    newN->data = item;
    newN->next = head;

    head = newN;
}

// pop last
void pop(){
    struct node* it = head;

    if(it->next == NULL){
        head = NULL;
        free(it);
        return;
    }

    while(it->next->next != NULL){
        it = it->next;
    }

    struct node* lastN = it->next;
    it->next = NULL;
    free(lastN);
}

void insert_by_index(int item, int inx){
    if(inx == 0){
        push(item);
        return;
    }

    struct node* it = head;
    int cnt = 1;

    while(cnt < inx){
        it = it->next;
        cnt++;
    }

    struct node* prev = it;
    struct node* next = it->next;

    // create new node
    struct node* newN = (struct node*) malloc(sizeof(struct node));
    newN->data = item;


}

3.2 Kiểm tra danh sách liên kết đơn vừa cài đặt

Chúng ta kiểm tra nhanh về cấu trúc dữ liệu vừa cài đặt có đúng không bằng cách sử dụng các hàm vừa cài đặt để thao tác với cấu trúc dữ liệu và kiểm tra dữ liệu sau khi sử dụng các hàm đã đúng chưa bằng cách in ra (sử dụng hàm print_list()).

int main(){
    // data example
    push(1);
    push(2);
    push(4);
    pop();
    pop();
    push(4);

    print_list();
}

Xem đẩy đủ code tại repo github: https://github.com/piandhust/data-structures/blob/main/list.c

5/19/2023

Tổng hợp câu hỏi phỏng vấn về cấu trúc dữ liệu và giải thuật


Câu 1: Độ phức tạp của thuật toán sắp xếp nổi bọt?

A. N

B. 2N

C. N * Log(N)


Câu 2: Độ phức tạp của thuật toán sắp xếp Quicksort

a. N

b. 2N

c. N * Log(N)


Câu 3: Cấu trúc dữ liệu nào hỗ trợ nhanh nhất việc kiểm tra một phần tử có nằm trong danh sách hay không?

A. ArrayList

B. HashSet

C. TreeMap


Câu 4: Giải thuật đệ quy là?

A. Trong giải thuật của nó có lời gọi tới chính nó nhưng với phạm vi nhỏ hơn

B. Trong giải thuật của nó có lời gọi tới chính nó

C. Trong giải thuật của nó có lời gọi tới một giải thuật khác đã biết kết quả

D. Trong giải thuật của nó có lời gọi tới chính nó nhưng với phạm vi lớn hơn


Câu 5: Ngăn xếp làm việc theo nguyên tắc

A. LILO ( last in last out)

B. LIFO ( last in first out)

c. FOLO (first out last out)

d. FIFO ( first in first out)


Câu 6: Định nghĩa danh sách tuyến tính hàng đợi:

A. Là một danh sách tuyến tính trong đó phép bổ sung một phần tử và phép loại bỏ một phần tử được thực hiện ở tại một vị trí bất kì trong danh sách.

B. Hàng đợi là kiểu danh sách tuyến tính trong đó, phép bổ sung một phần tử được thực hiện ở một đầu, gọi là lối sau (rear) hay lối trước (front). Phép loại bỏ không thực hiện được.

C. Hàng đợi là kiểu danh sách tuyến tính trong đó, phép bổ sung một phần tử hay loại bỏ được thực hiện ở một đầu danh sách gọi là đỉnh (Top)

D. Hàng đợi là kiểu danh sách tuyến tính trong đó, phép bổ sung phần tử ở một đầu, gọi là lối sau (rear) và phép loại bỏ phần tử được thực hiện ở đầu kia, gọi là lối trước (front).


Câu 7: Độ phức tạp của việc tìm kiếm 1 số trong 1 mảng số nguyên đã sắp xếp là bao nhiêu?

A. N

B. N * Log(N)

C. Log(N)

D. N


Câu 8: Tạo một file ignore.txt gồm 500 nghìn phần tử random từ 1-> 2triệu.  Tạo một file data.txt có 1,5 triệu phần tử. Các phần tử tăng dần từ 1 đến 2 triệu và loại trừ các phần tử trong file ignore yêu cầu: Có thể dùng bất kỳ ngôn ngữ gì để thực hiện. 

Áp dụng các kiến thức về cấu trúc dữ liệu giải thuật sao cho code tối ưu và thời gian thực thi ngắn nhất có thể. 

Bài nộp bao gồm code và thời gian thực thi đoạn code đó. Không bao gồm các file dữ liệu.


Câu 9: A là một sinh viên CNTT, làm thêm việc shipper hàng ngày. A nhận ra, mỗi ngày mình chỉ có thể chở tổng cộng 100kg. Nên giờ A cần tìm một thuật toán để tối ưu giá trị thu lại của mình. Vì vậy A lên danh sách các đơn hàng mỗi ngày. Trong ngày hôm nay, A có danh sách như sau: 

Cân nặng = [20, 30, 40, 50]

Giá trị = [10, 40, 10, 20]

Theo danh sách trên, A sẽ trở món hàng ở vị trí 0, 1, 3 - tổng cân nặng là 20 + 30 + 50 = 100kg và có tổng giá trị là 10 + 40 + 20 = 70 là lớn nhất.

Yếu cầu: viết hàm với đầu vào là 2 danh sách, danh sách cân nặng và giá trị theo thứ tự tương ứng của từng mặt hàng, tính ra phương án cho A chọn những mặt hàng nào để tối ưu giá trị nhận được.

Input:

    Cân nặng = [20,30,40,50]

    Giá trị = [10,40,10,20]

Output:

    [0, 1, 3],100,70


Câu 10: Ai là người nổi tiếng:

Người nổi tiếng trong một nhóm là người không biết ai trong nhóm đó, nhưng tất cả mọi người trong nhóm đó đều biết anh ta. 

Ví dụ 1: Cho một nhóm người, dưới dạng ma trận như sau:

A B C
A 0 0 0
B 1 0 1
C 1 0 0

Như vậy người nổi tiếng là A, vì anh ta không quen ai trong nhóm, nhưng tất cả đều biết anh ta.

Ví dụ 2: 

A B C
A 0 1 0
B 1 0 1
C 1 1 0

Trong ví dụ này không có ai là người nổi tiếng cả.

Yêu cầu: Đầu vào là một ma trận quen biết như ví dụ, hãy tìm nguời nổi tiếng trong danh sách đầu vào.

Input:
[
[0, 0, 0],
[1, 0, 1],
[1, 0, 0]
      ]
Output: 0 => người ở vị trí 0 là người nổi tiếng

Input:
[
[0, 1, 0],
[1, 0, 1],
[1, 0, 0]
      ]
Output: null => không có ai là người nổi tiếng

Câu 11: Tính giai thừa của n một cách nhanh nhất.  Với n được người dùng nhập.

1/17/2023

What’s the Best Programming Language to Learn? | Sharing


Chúc mừng năm mới 2023, mình xin chúc toàn bộ đọc giả của tailieubkhn có một năm mới thuật lợi, dành dựt được nhiều học bổng, học thêm được vô vàn kiến thức, vân vân và mây mây. Lâu lắm rồi mình mới quay trở lại blog, bỏ bê cũng khá lâu và hôm nay nhân dịp một trong những ngày đầu năm 2023 mình muốn chia sẻ quan điểm của mình về một chủ đề mình nghĩ cũng khá thu hút là: đâu là ngôn ngữ lập trình đáng học nhất năm? Mình không nhắc tới năm 2022 hay 2023 vì mình nghĩ bài viết sẽ giúp ích cho các bạn dù cho đang ở năm nào đi nữa.

Nếu các bạn theo dõi nhiều các bài viết của HUST & PI thì chắc nhiều bạn cũng biết quan điểm của mình là chúng ta nên học những cái gốc dễ, hiểu những cái gốc dễ như là cấu trúc dữ liệu và thuật toán, lập trình hướng đối tượng, kỹ thuật lập trình, mạng máy tính,... Khi hiểu rõ, nắm bắt được các kiến thức trên thì việc tiếp cận với từng ngôn ngữ lập trình các bạn sẽ thấy điều đó là cực kỳ dễ dàng. 

Tuy nhiên thì chắc chắn rồi, mỗi lập trình viên phải biết và thành thạo ít nhất một ngôn ngữ lập trình, không thì phát triển ứng dụng như thế nào, đúng không! Vậy thì học ngôn ngữ gì?

Có bao giờ bạn tự hỏi rằng tại sao lại có nhiều ngôn ngữ lập trình như vậy không? Tại sao không thống nhất chúng lại thành một ngôn ngữ lập trình duy nhất để cho lập trình viên dễ học và dễ sử dụng hơn. Mình sẽ giải thích với hai ý như sau: 

- Đầu tiên là mỗi ngôn ngữ lập trình được phát triển bởi những người/nhóm người khác nhau vì thế việc gộp vào chưa chắc đã dễ dàng hay tóm gọn lại là khó khăn.

- Tiếp là, mọi thứ sinh ra thì đều có những ý nghĩa của nó, các ngôn ngữ lập trình cũng vậy, mỗi ngôn ngữ lập trình sẽ sinh ra để giải quyết một vấn đề riêng và việc gộp lại chưa chắc đã tốt, vì khi gộp toàn bộ lại thành một thì chúng ta sẽ có một ngôn ngữ khổng lồ với bộ biên/phiên dịch cực lớn mà rõ ràng với những vấn đề cụ thể thì chúng ta chỉ cần một ngôn ngữ tương ứng để giải quyết vấn đề đó. Vậy lúc này thay vì gọt quả táo chúng ta chỉ cần con dao gọt hoa quả là được thì chúng ta lại cầm hẳn con dao thịt lợn để gọt quả táo đó, xong thì cũng xong thôi nhưng chắc chắn thời gian gọt sẽ lâu hơn, quả táo gọt ra sẽ không đẹp và tròn, chúng ta còn vất vả trong việc cầm con dao để gọt quả táo nữa.

Điểm qua một số ngôn ngữ phổ biến thì có thể thấy Python là một ngôn ngữ ngắn gọn, cú pháp gần gũi, phù hợp với các nhà toán học hay các nhà phân tích dữ liệu để họ có thể biểu diễn một cách dễ dàng các công thức toán học sang ngôn ngữ lập trình. Javascript là một ngôn ngữ bất đồng bộ và chỉ chạy đơn luồng. C/C++ giúp lập trình viên tự quản lý và phân chia bộ nhớ, với C/C++ lập trình viên có thể "thao túng" máy tính ở mức độ khá thấp (có rất nhiều người vẫn coi C/C++ là một ngôn ngữ lập trình bậc thấp hoặc bậc trung). Java thì lại là một ngôn ngữ 100% hướng đối tượng, hướng tới việc viết một lần và chạy trên nhiều nền tảng. PHP là một ngôn ngữ khá dễ dàng trong phát triển các trang web...


Bây giờ chúng ta sẽ quay lại câu hỏi ở đầu bài viết, Vậy thì học ngôn ngữ gì?, và câu trả lời dưới đây là quan điểm của riêng mình về vấn đề này.

Mình sẽ đưa ra một số các gạch đầu dòng về tiêu chí để chọn ngôn ngữ lập trình như sau:

- Một là về chuyên ngành mà bạn theo đuổi. Như mình nói bên trên thì mỗi ngôn ngữ lập trình sinh ra để giải quyết một số vấn đề cụ thể vì thế khi bạn quyết định chọn một chuyên ngành hẹp thì hãy chọn một ngôn ngữ lập trình mà cộng đồng trong đó sử dụng phổ biến vì chắc chắn là nó phù hợp đã, phù hợp thì nó mới phổ biến, tiếp là sẽ có một cộng đồng mạnh hỗ trợ, có nhiều các hướng dẫn trên Google hay StackOverFlow. Một số đại diện tiêu biểu mà mình đưa ra là: 

    - Web Frontend: Javascript, HTML, CSS

    - Web Backend: Hầu như mọi ngôn ngữ lập trình đều có thể làm được web backend, tùy mục đích của bạn để chọn ngôn ngữ cho phù hợp. Nếu như bạn muốn làm một hệ thống chat realtime thì có thể nghĩ tới Nodejs. Nếu như bạn đang chuẩn bị làm một hệ thống thanh toán thì có thể nghĩ tới Java. Nếu như trang web của bạn là một trang web nhỏ, thuần là web bán hàng thì có thể sử dụng PHP,...

    - Game: C/C++, Java, C#

    - AI, Khoa học dữ liệu: Python và 1 số ít là Java

    - Nhúng, IoT: C/C++

    - ...

-  Hai là về độ hot của nó hiện tại hay chính là nhu cầu của thị trường hiện tại. Các doanh nghiệp và nhất là các doanh nghiệp Việt Nam thì thường chạy theo trend khá nhanh. Vì đa số các doanh nghiệp Việt Nam là làm outsource nên họ sẽ sử dụng các công nghệ mới nhất để có thể hỗ trợ tối đa trong việc phát triển, vì thế việc chọn một ngôn ngữ được nhiều lập trình viên sử dụng hay nhiều nhà tuyển dụng đăng tuyển thì sẽ là một lợi thế lớn cho mọi người. Để biết ngôn ngữ lập trình nào đang hot, đang top, các bạn có thể tham khảo một số bảng xếp hạng sau: 

    1. PYPL (The PopularitY of Programming Language): bảng xếp hạng này dựa trên việc theo dõi tìm kiếm của từ khóa "[language] tutorial" (hướng dẫn học [ngôn ngữ]) trên Google. Bảng xếp hạng này rất tốt cho việc thống kê xem có bao nhiêu lập trình viên đang tiếp cận một ngôn ngữ mới.

    2. TIOBE INDEX: cũng giống với PYPL, TIOBE cũng dựa trên việc tìm kiếm để xác định sự phổ biến của một ngôn ngữ

    3. IEEE SpectrumIEEE kết hợp dữ liệu từ khắp nơi trên Internet để xác định ngôn ngữ nào đang phát triển. Bạn thậm chí có thể sắp xếp danh sách của họ theo xu hướng, tìm kiếm việc làm hoặc xếp hạng tùy chỉnh

    4. Stackoverflow Developer SurveysMỗi năm, StackOverflow, một trang web hỏi đáp rất phổ biến dành cho các nhà phát triển, tổ chức một cuộc khảo sát người dùng. Tại đây, bạn có thể tìm thấy các ngôn ngữ phổ biến nhất được các nhà phát triển như bạn sử dụng, cũng như các công nghệ được mong muốn nhất và thậm chí bị ghét nhất.

- Ba là độ yêu thích của bạn với ngôn ngữ đó. Ví dụ như mình là người yêu thích sự chặt chẽ, rõ ràng nên mình khá thích Java và khá ghét Javascript. Dĩ nhiên ghét hay thích còn tùy thuộc vào khi bạn tiếp cận với chúng nữa.

Cuối cùng, với mình thì lập trình viên nên có cho mình một ngôn ngữ tủ và bạn có thể học thêm một vài các ngôn ngữ tùy trường hợp và sở thích. Chúc mọi người một năm mới vui vẻ!

Tham khảo: https://torquemag.io/

9/24/2022

Xử lý ngôn ngữ tự nhiên | Tài liệu, chuyên ngành


Xử lý ngôn ngữ tự nhiên là môn học kỹ sư mà các bạn theo bên Hệ thống thông tin (HTTT) hay Công nghệ phần mềm (CNPM) đều phải học. Thoạt nghe thì chúng ta chắc ai cũng nghỉ tới những công nghệ AI gì đó cao siêu, nhưng môn học này không dạy như vậy, môn học này dạy đúng bản chất thực sự gọi là xử lý ngôn ngữ tự nhiên. Các bạn sẽ được học về các bài toán cụ thể của xử lý ngôn ngữ tự nhiên và các phương pháp để giải quyết các bài toán này và thường là các phương pháp giải quyết bằng xác suất. Các bài toán cụ thể mà môn học đề cập tới như là: Tách từ tiếng Việt, gán nhãn từ loại, phân tích cú pháp, phân tích vai nghĩa, nghĩa từ vựng và phân giải nhập nhằng.

Nếu các bạn chưa biết thì chúng ta có một thư viện cũng khá nổi tiếng trong bài toán tách từ tiếng việt của thầy Trần Việt Trung là thư viện Pyvi, có thể nhiều bạn chưa biết hoặc cũng có thể nhiều bạn đã dùng nhưng chưa biết nó là của thầy Trung. Github của thư viện trên github của thầy Trung tại https://github.com/trungtv/pyvi.

Môn học này thường sẽ thi tự luận và thường tập chung vào các dạng bài: 

  • Tính xác suất bigram (ở chương 2, mô hình ngôn ngữ)
  • Thuật toán CKY (ở chương 5a, phân tích cú pháp)
  • Thuật toán Early (ở chương 5a, phân tích cú pháp)
  • Vẽ cây cú pháp (ở chương 5a, phân tích cú pháp)
  • Tính xác suất cây cú pháp (ơ chương 5b, phân tích xác suất)
  • ...

Tài liệu môn học: 

Về bài tập lớn, bài tập lớn các bạn sẽ phải làm về xử lý ngôn ngữ tự nhiên. Nếu đề tài mà nhóm bạn chọn bạn không chắc chắn nó là một đề tài của xử lý ngôn ngữ tự nhiên hãy hỏi lại cô giáo để tránh làm lệch đề. Các bạn có thể tham khảo danh sách đề tài của cô Lê Thanh Hương TẠI ĐÂY.

Các bạn có thể xem qua trang web về môn học Xử lý ngôn ngữ tự nhiên (NLP) của cô Lê Thanh Hương tại website cá nhân của cô Hương: https://users.soict.hust.edu.vn/huonglt/NLP/

8/27/2022

Cơ sở dữ liệu điện tử thư viện Tạ Quang Bửu | Sharing


Lâu rồi, hôm nay mình mới quay lại đăng bài trên website, hôm nay không phải là một bài viết về môn học hay gì đó liên quan tới lập trình, bài viết này được Hỗ trợ Sinh viên Bách khoa đăng trên fanpage về các nguồn cơ sở dữ liệu điện tử của thư viện Tạ Quang Bửu. Khi đọc dược bài viết của fanpage Hỗ trợ sinh viên Bách Khoa rất nhiều bạn rất tiếc là không được biết tới sớm hơn, cũng một phần vì do fanpage của thư viện Tạ Quang Bửu ít được mọi người chú ý mà khi Hỗ trợ Sinh viên Bách Khoa đăng lại mọi người mới biết tới nhiều hơn. Mình thấy đây là một nguồn dữ liệu cực kì hữu ích cho mỗi bạn sinh viên mà lại ít người biết tới nên muốn chia sẻ lại để lưu lại cũng như nhiều bạn sinh viên biết tới hơn.

Thư viện Tạ Quang Bửu đang có cơ sở dữ liệu sau:

Lưu ý: mỗi cơ sở dữ liệu này đều chỉ có thể sử dụng trong thời gian bạn là sinh viên, vì vậy nếu có ý định nghiên cứu, tìm hiểu thì hãy sử dụng nó ngay đi, thời gian trôi qua sẽ là không thể lấy lại.

Fanpage chính thức của thư viện Tạ Quang Bửu - đại học Bách Khoa Hà Nội: fb.com/TQB.library

6/10/2022

Pull down refresh và Pull up loading | Phát triển ứng dụng đa nền tảng - Sharing



Pull down refresh

Kiểu kéo để làm mới (hoặc vuốt để làm mới - pull down refresh) cho phép người dùng kéo xuống danh sách dữ liệu bằng cách sử dụng thao tác chạm để truy xuất thêm dữ liệu. Cử chỉ “Kéo để làm mới” được Loren Brichter giới thiệu lần đầu tiên trong ứng dụng Tweetie và nhanh chóng nó trở nên phổ biến đến mức vô số ứng dụng đã áp dụng cử chỉ này. Ngày nay, tính năng "kéo để làm mới" là một phần tự nhiên của nhiều ứng dụng phổ biến, bao gồm Twitter, Gmail, Tweetbot và những ứng dụng khác. 

Cách hoạt động: một chỉ báo làm mới ( mũi tên vòng tròn) xuất hiện để báo hiệu cho người dùng hành động kéo xuống này sẽ làm mới lại màn hiện tại. 

Pull down refresh hoạt động tốt cho danh sách, danh sách dạng lưới hoặc bộ sưu tập được sắp xếp theo nội dung gần đây nhất, vì thế thao tác pull down refresh thích hợp trong các trường hợp như là bảng tin Facebook hay Twitter, Inbox messenger,… 

Các trường hợp không thích hợp sử dụng:  

+ Bản đồ: vì bản đồ không có hướng xác định 

+ Danh sách không có thứ tự: vì việc danh sách không có thứ tự thì làm mới sẽ không mang lại được tác dụng gì 

+ Các ứng dụng hoặc màn hình mà có tỉ lệ cập nhật thông tin thấp hoặc không thường xuyên 

+ Dữ liệu sắp xếp theo thứ tự thời gian: nên có nút làm mới vì khi sắp xếp theo thứ tự thời gian người dùng sẽ kéo từ trên xuống để xem và khi đó việc kéo lên cùng để làm mới là khó khăn 

+ Một số dạng nội dung đặc biệt khác 

Pull up loading

Pull up loading hay là lazy loading là một cách tốt để cải thiện trải nghiệm người dùng, lazy loading trì hoãn tải hoặc khởi tạo tài nguyên hoặc đối tượng cho đến khi chúng thực sự cần thiết. Ví dụ: nếu một trang web có hình ảnh mà người dùng phải cuộn xuống để xem, chúng ta có thể hiển thị trình giữ chỗ và chỉ tải hình ảnh đầy đủ một cách chậm rãi khi người dùng đến vị trí của trang đó. Hoặc là bảng tin facebook, facebook chỉ tải 1 số status và khi người dùng kéo xuống mới tiếp tục tải những status khác. 

Lợi ích của pull up loading: giảm thời gian tải ban đầu, bảo toàn băng thông, bảo tồn tài nguyên hệ thống 

Pull up loading sử dụng trong các trường hợp mà ứng dụng có nhiều thông tin mà việc tải ngay ban đầu có thể gây mất thời gian hoặc quá tải, sử dụng trong các trường hợp danh sách mà các phần tử cũ hơn ít được xem xét đến, hoặc là trường hợp mà nội dung thay đổi như là bảng tin facebook, twitter. 

Pull up loading là rất tốt để giảm băng thông tuy nhiên không lên quá lạm dụng, trong các ứng dụng có ít thông tin hoặc các ứng dụng mà nội dung ít thay đổi. 

Trong React Native 

Pull down refresh: Chức năng Kéo để Làm mới được triển khai bằng cách sử dụng thành phần RefreshControl trong React Native. RefreshControl được sử dụng bên trong ScrollView hoặc ListView để thêm kéo để làm mới chức năng. Khi ScrollView ở scrollY: 0, vuốt xuống sẽ kích hoạt sự kiện onRefresh. 

Pull up loading: Đặt vị trí ban đầu của Hình ảnh trong ScrollView, Theo dõi vị trí hiện tại của page offset, Thay đổi trạng thái khi page offset đến gần  

Trong Flutter

Pull down refresh: Đặt ListView, GridView… bên trong Widget RefreshIndicator, thuộc tính onRefresh: mô tả cách thức chương trình refresh dữ liệu. 

Pull up loading: Sử dụng ListView.builder, GridView.builder… thuộc tính controller của của ListView.builder… sẽ thực hiện việc load các dữ liệu khi người dùng thực hiện thao thác cuộn màn hình. 

6/01/2022

Phát triển ứng dụng đa nền tảng | Tài liệu, chuyên ngành


Phát triển ứng dụng đa nền tảng trình bày khái niệm cơ bản, quy trình, công cụ và các thư viện, framework hỗ trợ để xây dựng ứng dụng đa nền tảng và chủ yếu chính là React Native và Flutter (Cross platform). 

Nếu ai học KHMT thì ở module 1 các bạn cũng đã được học môn học "Phát triển ứng dụng cho thiết bị di động", môn học này giới thiệu về phát triển các ứng dụng trên mobile với các công cụ phát triển gốc trên Android (Native platform) bằng ngôn ngữ lập trình Java. Nếu bạn muốn biết thêm về ưu nhược điểm của Native platform và cross platform thì có thể xem qua bài viết trước đó trên website của mình: Native với Cross Platform: ưu và nhược điểm


Các bạn sẽ học được gì ở môn học này? Như bao môn khác, không thể nào qua 1 môn học mà các bạn có thể trở thành một nhà phát triển ứng dụng đa nền tảng được, môn học chỉ cung cấp cho bạn những thứ cơ bản nhất để nếu bạn nào có theo hướng này thì cũng sẽ cần tự mình nghiên cứu thêm rất nhiều hay là đi thực tập tại các công ty để có thể học hỏi thêm từ các doanh nghiệp.

Trong phát triển ứng dụng đa nền tảng các bạn sẽ được dạy tập chung chủ yếu vào các phần chính: 

  • Tổng quan và kiến trúc của thiết bị di động (kiến trúc android, kiến trúc iOS, kiến trúc đa nền tảng)
  • Dart và Flutter
  • Javascript và React native

(Tham khảo bài viết: Các điểm nhấn trong cú pháp của ES6)

Với bài tập lớn các bạn có thể tùy ý lựa chọn xây dựng ứng dụng đa nền tảng dựa trên Flutter hoặc React Native tùy ý. Các bạn đã được cung cấp sẵn backend khi làm bài tập lớn và công việc của mỗi nhóm chỉ là xây dựng ứng dụng frontend cho thiết bị di động với công nghệ đa nền tảng. Dĩ nhiên là các bạn được phép thêm các chức năng, chỉnh sửa để có một ứng dụng ưng ý hơn, thậm chí đây còn là điều bắt buộc khi trong kỳ mình học bản backend thầy đưa cho là một bản backend bị thiếu một số chức năng và thầy giáo không tìm được bản đầy đủ. Hoặc các bạn cũng có thể xây dựng một con backend mới hoàn toàn nếu có thời gian, nhưng nhớ là con backend các bạn xây dựng mới nên có các chức năng cũng phải giống với con backend mà thầy giáo cung cấp.

Môn học này có 1 số thầy giáo phụ trách như là thầy Nguyễn Mạnh TuấnNguyễn Tiến Thành,... Các bạn học thầy Tuấn thì có vẻ điểm sẽ cao hơn, học thầy Thành thì sẽ được làm các đề thi thử trước khi các bạn thi cuối kì.

Một số tài liệu dành cho môn học: 

Môn học này sẽ có 1 số kiến thức xung quanh môn học được thầy giáo hay hỏi trong quá trình học tập, mình sẽ viết thành các bài viết riêng đăng sau bài viết này vì chúng cũng là những vấn đề không nhỏ.

5/08/2022

Các điểm nhấn trong cú pháp của ES6 | Phát triển ứng dụng đa nền tảng - Sharing


Trong phát triển ứng dụng đa nền tảng các bạn sẽ được đề cập tới 2 framework đa nền tảng mobile nổi tiếng nhất hiện nay đó là React NativeFlutter. Với React Native việc nắm vững Javascript và những cú pháp mới trong ES6 là điều rất cần thiết. Trong bài viết này mình muốn viết về những điểm nhấn trong cú pháp của ES6, bài viết được tham khảo trong chương 4, phần 1.2 của slide bài giảng phát triển ứng dụng đa nền tảng sẽ được chia sẻ ở những bài viết sau trên blog của mình và đã được bổ sung và sửa đổi một số kiến thức cho đầy đủ hơn.

Từ khóa let và const

Trong ES5, chúng ta định nghĩa 1 biến sử dụng từ khóa var, phạm vi của biến khi sử dung var để khai báo sẽ chỉ có 2 trường hợp là global hoặc local. Khi chúng ta định nghĩa biến ngoài một hàm thì nó là biến global, còn khi chúng ta định nghĩa biến ở bên trong hàm thì nó là một biến local.

Trong ES6 giới thiệu cho chúng ta một từ khóa let giúp cho việc khai báo biến chạy trong một block (block ở đây được hiểu như là giới hạn trong 2 dấu "{}")

Ví dụ: 

let x = 10;
if (x == 10) {
    let x = 20;
    console.log(x); // 20:  reference x inside the block
}
console.log(x); // 10: reference at the begining of the script

Chúng ta có thể thấy biến x được khai báo mới trong block if hoàn toàn được khai báo mới chứ không hề liên quan gì tới biến đã được khai báo ở ngoài. Việc này cũng giúp chúng ta tránh nhầm lẫn trong việc sử dụng tên biến hơn và cũng giúp Javascript gần hơn với các ngôn ngữ khác.

ES6 cũng cung cấp một cách định nghĩa hằng số sử dụng const. const keyword dùng để định nghĩa các biến chỉ đọc và tham chiếu tới một giá trị.

Các biến được khai báo bởi từ khóa let là mutable (có thể thay đổi), còn các biến khai báo bởi từ khóa const là immutable (không thể thay đổi).

Vòng lặp for...of

Cú pháp mới for...of giúp lặp một cách dễ dàng hơn trên các đối tượng có thể lặp lại như là: mảng, string, map, set,...

Ví dụ: 

let scores = [80, 90, 70];

for (let score of scores) {
    score = score + 5;
    console.log(score);
}

Template literals

Trước ES6, chúng ta sử dụng dấu ngoặc đơn (') và ngoặc kép (") để biểu thị cho string javascript, và string bị giới hạn rất nhiều chức năng. 

Với template literals chúng ta có thể làm nhiều hơn với một string như là: 

- Khai báo và sử dụng string có thể kéo dài trên nhiều dòng

- Thực hiện nội suy cho phép nhúng các biến hoặc biểu thức vào chuỗi 

- An toàn khi chèn vào các mã HTML

Template literals được đặt trong 2 dấu (``), ví dụ: 

let str = `Template literal in ES6`;

console.log(str);// Template literal in ES6
console.log(str.length); // 23
console.log(typeof str);// string

Arrow Function

Cú pháp mũi tên (=>), đây như là một cách viết gọn hàm lại. Ví dụ với một hàm bình thường như sau: 

let add = function (x, y) {
	return x + y;
};
console.log(add(10, 20)); // 30

Chúng ta có thể viết gọn lại với cú pháp của arrow function như sau: 

let add = (x, y) => x + y;
console.log(add(10, 20)); // 30;

Một số trường hợp chúng ta có thể viết gọn lại hơn nữa arrow function, khi danh sách tham số chỉ có 1, chúng ta có thể bỏ qua dấu ngoặc đơn: 

(singleParam) => { statements }
singleParam => { statements }

Tuy nhiên nếu hàm không có tham số thì cặp dấu ngoặc đơn là bắt buộc sử dụng: 

() => { statements }

Nếu chỉ có một biểu thức trong nội dung của arrow function thì chúng ta có thể bỏ qua dấu ngoặc nhọn: 

let square = x => x * x;

Giá trị mặc định cho tham số

Ví dụ: 

function say(message='Hi') {
    console.log(message);
}

say(); // 'Hi'
say('Hello') // 'Hello'

Xây dựng các Class

Trước ES6, Javascript không có khái niệm về class, mà để bắt chước một class thì chúng ta có thể sử dụng constructor/prototype pattern

Ở ES6, khái niệm class đã được giới thiệu và đây chắc chắn là những tin vui cho những ai fan của hướng đối tượng: 

class Person {
    constructor(name) {
        this.name = name;
    }
    getName() {
        return this.name;
    }
}

Module

- Mỗi module được biểu diễn bằng một thẻ .js riêng biệt 

- Lệnh import hoặc export trong một module để xuất hoặc nhập các biến, hàm, class hoặc bất cứ một thực thể nào đến từ một module hoặc tệp khác

Ví dụ, tạo một file message.js có nội dung như sau: 

export let message = 'ES6 Modules';

Để sử dụng biến message trong một file khác, chúng ta có thể sử dụng cú pháp import như sau: 

import { message } from './message.js'

Rest Parameters

- Truyền vào lượng tham số tùy ý cho hàm dưới dạng mảng

- Thêm vào phía trước tham số toán từ ... (dấu ba chấm)

function sortNumbers(...numbers) {
    return numbers.sort();
}
console.log(sortNumbers(3, 5, 7));
console.log(sortNumbers(3, 5, 7, 1, 0));

Toán tử Spread

Toán tử spread (tức là chia nhỏ) một mảng và chuyển các giá trị vào hàm được chỉ định.

const odd = [1,3,5];
const combined = [2,4,6, ...odd];
console.log(combined);

// => output: [ 2, 4, 6, 1, 3, 5 ]

function f(a, b, ...args) {
	console.log(args);
}

f(1, 2, 3, 4, 5);

// => output: [ 3, 4, 5 ]

Phép gán hủy cấu trúc

Biểu thức giúp dễ dàng trích xuất các giá trị từ mảng hoặc thuộc tính từ các đối tượng, thành các biến riêng biệt bằng cách cung cấp một cú pháp ngắn gọn.

let colors = ["Xanh", "Đỏ"];
let [a, b] = colors;

Tham khảo: https://www.javascripttutorial.net/es6/