BÀI 1: TỔNG QUAN VỀ GIẢI THUẬT

PHẦN 1: Giải thuật cơ bản

Bài 1: tổng quan về giải thuật

1. Tổng quan môn học

Trước khi đi vào nội dung chính, chúng ta cần hiểu rõ các khái niệm cơ bản trong cấu trúc dữ liệu và giải thuật và vai trò của nó.

$\bullet$ Video: Giới thiệu môn học cấu trúc dữ liệu và giải thuật (các bạn chọn audit để học miễn phí chứ không mấy bài sau nó không cho học)

$\bullet$  Bài đọc: Tham khảo vietjack.com, tham khảo cafedev.vn

Giải thuật(Algorithms) hay thuật toán là một tập hợp hữu hạn các hướng dẫn được xác định rõ ràng, có thể thực hiện bằng máy tính, thường để giải quyết một lớp vấn đề hoặc thực hiện một phép tính.

Đặc điểm của thuật toán

Tính xác định: Thuật toán phải rõ ràng và không mơ hồ. Mỗi một bước phải rõ ràng và chỉ mang một mục đích nhất đinh.

Dữ liệu đầu vào: Một thuật toán phải có 0 hoặc nhiều dữ liệu đầu vào được xác định

Kết quả đầu ra: Một thuật toán phải có 1 hoặc nhiều dữ liệu đầu ra rõ ràng và phù hợp với đầu ra mong muốn.

Tính hữu hạn: Thuật toán phải kết thúc sau một số bước hữu hạn.

Tính khả thi: Một thuật toán phải khả thi với các nguồn lực có sẵn (tài nguyên, thiết bị hiện có)

Độc lập: Một thuật toán nên có hướng dẫn từng bước độc lập với bất kỳ code lập trình nào

Độ phức tạp của thuật toán (wiki, toidicodedao.com)

$\bullet$ Video: Khái niệm Big-O

$\bullet$ Video: Sử dụng Big-O

Độ phức tạp của một thuật toán là 1 hàm phụ thuộc vào độ lớn của dữ liệu đầu vào.

Để ước lượng độ phức tạp của một thuật toán ta thường dùng khái niệm Big-O hoặc Big-Θ.

Big O Notation có thể dùng cho cả thời gian chạy – số lượng câu lệnh chạy, cũng như lượng bộ nhớ mà thuật toán cần sử dụng. Để dễ phân biệt, người ta phân ra thành:

• Time Complexity: Số lượng câu lệnh phải chạy – thời gian chạy của thuật toán dựa theo lượng phần tử đầu vào
• Space Complexity: Số lượng bộ nhớ thêm mà thuật toán cần, dựa theo số lượng phần tử đầu vào

Định nghĩa Big-O: Cho $f$ và $g$ là các hàm số dương không giảm trên tập số tự nhiên, tức là $f,g: \mathbb{N} \rightarrow \mathbb{R}^+$ và $c \in \overline{\mathbb{R}^+}$ là điểm giới hạn của $\overline{\mathbb{R}^+}.$ Nếu $\frac{f(x)}{g(x)}$ bị chặn trong lân cận của $c$ thì ta viết $f(x)=O(g(x))$ khi $x \rightarrow c.$

- Ví dụ: Xét $f,g: \mathbb{N} \rightarrow \mathbb{R}^+$ sao cho $f(x)=3x^2+5x+2, g(x)=x^2$, $f(x)=O(g(x))$ khi $x \geq 1$ vì $3x^2+5x+2 \leq 3x^2+5x^2+2x^2=10x^2 \Rightarrow \frac{f(x)}{g(x)} \leq 10.$ 

Định nghĩa. Hàm số $f,g$ xác định trên $\mathbb{N}$ thỏa mãn điều kiện $\lim_{x \rightarrow c}\frac{f(x)}{g(x)}=1$ thì chúng được gọi là những hàm tương đương nhau khi $x \rightarrow c,$ và ký hiệu $f \approx  g$ khi $x \rightarrow c.$

Từ định nghĩa và ví dụ ta có thể coi $x$ như là dữ liệu đầu vào của thuật toán.

Cấu trúc dữ liệu
$\bullet$  Bài đọc: cấu trúc dữ liệu vietjack.com
$\bullet$ Video: Tại sao cần phải học cấu trúc dữ liệu
Cấu trúc dữ liệu là một cách lưu dữ liệu trong máy tính sao cho nó có thể được sử dụng một cách hiệu quả.

 2. Một số bài toán về giải thuật cơ bản

$\bullet$ Định nghĩa: Đệ quy

Trong toán học và khoa học máy tính, một lớp đối tượng hoặc phương thức thể hiện hành vi đệ quy khi nó có thể xác định được bởi hai thuộc tính:

• Trường hợp cơ sở (hoặc các trường hợp) đơn giản - một kịch bản kết thúc không sử dụng đệ quy để đưa ra câu trả lời
• Bước đệ quy - một bộ quy tắc giảm tất cả các trường hợp khác đối với trường hợp cơ sở

Trong tin học, đệ quy là phương pháp dùng trong các chương trình máy tính trong đó có một hàm tự gọi chính nó.

$\bullet$ Ví dụ về đệ quy
- Tìm số fibonacci thứ n.
dãy fibonacci có công thức truy hồi là 
$F(n)=\begin{cases}0& \text{ khi } n=0 \\ 1& \text{ khi } n=1 \\F(n-1)+F(n-2)& \text{ khi } x \geq  2 \end{cases}$

import sys
def fibonacci(n):
    if n<=1:
        return n
    else:
        return fibonacci(n-1)+fibonacci(n-2)
while True:
    try:
        n=int(input('nhập vào số tự nhiên n: '))
        if n>=0:
            break
    except:
        print(sys.exc_info()[0])
print('số fibonacci thứ {} là: F({}) ='.format(n,n),fibonacci(n))

Mô phỏng cây đệ quy của hàm fibonacci

Gọi $T(n)$ là số dòng code của hàm fibonacci(n), ta có 

$T(n)=\begin{cases}2 & \text{nếu } n \leq 1 \\ T(n-1)+T(n-2)+3 & \text{nếu } n>1 \end{cases}$

$T(n)=T(n-1)+T(n-2) +3 < 2T(n-1)+3 <...< 2^n+3<2.2^n, \forall n >1$

Suy ra $\frac{T(n)}{2^n}$ bị chặn tức là $T(n)=O(2^n)$ khi $n>1$ 

Ngoài ra ta có thể tính chính xác số dòng code của hàm fibonacci bằng cách đặt  $T(n)=T'(n)-3,$ suy ra $T'(n)=\frac{5}{\sqrt{5}}\left[ \left(\frac{1+\sqrt{5}}{2}\right)^{n+1}-\left(\frac{1-\sqrt{5}}{2}\right)^{n+1}\right]$

Hay là $T(n)=\frac{5}{\sqrt{5}}\left[ \left(\frac{1+\sqrt{5}}{2}\right)^{n+1}-\left(\frac{1-\sqrt{5}}{2}\right)^{n+1}\right]-3$

Ta có thể thấy Big-O là hàm mũ do đó với đầu vào lớn thì thuật toán chạy rất lâu, nên ta cần giảm độ phức tạp của thuật toán xuống.

import sys
def fibonacci(n):
    F=[0]*(n+1)
    F[0]=0
    F[1]=1
    for i in range(2,n+1):
        F[i]=F[i-1]+F[i-2]
    return F[n]
while True:
    try:
        n=int(input('nhập vào số tự nhiên n: '))
        if n>=0:
            break
    except:
        print(sys.exc_info()[0])
print('số fibonacci thứ {} là: F({}) ='.format(n,n),fibonacci(n))

Hàm fibonacci(n) mới này có $T(n)=2n+2$ dòng code nên  $T(n)=O(n)$

Để hình dung $O(2^n)$ lớn hơn $O(n)$ như thế nào ta vẽ đồ thị của chúng 

Bài này còn nhiều khái niệm chưa nhắc đến như ký hiệu $\Omega,\Theta,o$ các bạn có thể tìm hiểu thêm về nó trên giaithuatlaptrinh.github.io