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)

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 (wikitoidicodedao.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


Xem tiếp >>

KHÔNG GIAN BANACH

1. Lịch sử (Banach space)

Không gian Banach được đặt theo tên nhà toán học người  Ba Lan Stefan Banach. Ông cùng với  Hans Hahn và Eduard Helly nghiên cứu và đưa ra khái niệm năm 1920-1922, không gian Banach được phát triển từ nghiên cứu về không gian Hàm của HilbertFréchet và Riesz. Không gian Banach là một trong những đối tượng trung tâm của nghiên cứu về giải tích hàm. 

2. Định nghĩa 

Không gian Banach là không gian định chuẩn đầy đủ (đầy đủ tức là mọi dãy cauchy đều hội tụ)

3. Ví dụ

$\bullet$ các không gian $l_p^n$ là không gian Banach.($l_p^n$ là ký hiệu không gian $\mathbb{R}^n$)
Chứng minh. Giả sử $\{x_n\},x_n=(x_1^{(n)},...,x_n^{(n)})$ là một dãy Cauchy trong $l_p^n$ khi đó
$\forall \varepsilon > 0, \exists n_o \in \mathbb{N},\forall m,n \in \mathbb{N},m,n>n_o$ ta có $\left\|x_n-x_m \right\|< \varepsilon (1) $ 
Vì chuẩn trong không gian $l_p^n$ là tương đương nên ta chỉ xét chuẩn "sup" cho đơn giản
Trong $l_p^n$ ta chọn chuẩn $ \left \| x \right \|_p=sup_{i=1,...,n}(|x_i^{(n)}-x_i^{(m)}|)$
từ (1) suy ra $|x_i^{(n)}-x_i^{(m)}| < \varepsilon,\forall i=1,...,n.$ 
tức là $\lim_{n\rightarrow \infty} x_i^{(n)}=x_i^{(m)},\forall i=1,...,n.$
điều này tương đương với $\lim_{n\rightarrow \infty}x_n=x_m.$
tức là dãy Cauchy ${x_n}$ hội tụ tới $x_m$


 

Xem tiếp >>

KHÔNG GIAN ĐỊNH CHUẨN

 

1. Lịch sử

2. Định nghĩa

Cho $E$ là một không gian vectơ trên trường $F$. Một chuẩn trên $E$ là một hàm $\left \|. \right \|:E \rightarrow \mathbb{R}$ thỏa mãn các điều kiện sau: với mọi $x,y \in E, \lambda  \in F$
    $(N_1)$    $\left \|x \right \| \geq 0,\left \|x \right \|=0 \Leftrightarrow x=0$
    $(N_2)$    $\left \|\lambda x \right \|=\left|\lambda\right|\left \|x \right \|$
    $(N_3)$    $\left \|x+y \right \| \leq \left \|x \right \|+\left \|y \right \|$

3. Một số ví dụ về chuẩn

$\bullet $ Không gian $\mathbb{R}^{n}$. Xét không gian tuyến tính $\mathbb{R}^{n}.$Với mọi $x=(x_1,x_2,...,x_n) \in \mathbb{R}^{n}$ ta định nghĩa
    $\left \|x \right \|_p=\left(\sum_{i=1}^{n}\left|x_i \right|^p\right)^\frac{1}{p}$, là một chuẩn với p không nhỏ hơn 1. và được gọi là chuẩn $l_p^n.$
$\bullet $ Không gian $C[a,b].$ (https://www.youtube.com/watch?v=lChYgNGFZUU&t=129s)
$C[a,b]=\left\{f :[a,b] \rightarrow F:f  \text{ liên tục trên } [a,b]\right\}$ Với mọi $f,g \in C[a.b] \text{ và  mọi }\alpha \in F$ ta định nghĩa
    $(f+g)(t)=f(t)+g(t),   (\alpha f)(t)=\alpha f(t),  \text{với mọi } t \in [a,b]$
Thế thì có  $f+g,\alpha f \in C[a,b]$
Ta nói $f=g \text{ nếu } f(t)=g(t) \forall t \in [a,b]$
Ta kiểm tra $C[a,b]$ có là không gian tuyến tính hay không
Chú ý: việc kiểm tra các tiên đề là đơn giản tuy nhiên nó không tầm thường rất dễ hiểu nhầm.
Với mọi $f,g,k \in C[a.b] \text{ và  mọi }\alpha ,\beta \in F$
Kiểm tra tiên đề 1: $(f+g)(t)\overset{\underset{\mathrm{def}}{}}{=}f(t)+g(t)\overset{\underset{\mathrm{2}}{}}{=}g(t)+f(t)\overset{\underset{\mathrm{def}}{}}{=}(g+f)(t), \forall t \in [a,b]$
(dấu bằng thứ nhất là do định nghĩa của C[a,b], dấu bằng thứ hai là do định nghĩa của trường.
Suy ra $f+g=g+f$.
Kiểm tra tiên đề 2: $f(t)+(g+k)(t)\overset{\underset{\mathrm{def}}{}}{=}f(t)+g(t)+k(t)\overset{\underset{\mathrm{def}}{}}{=}(f+g)(t)+k(t)$
Suy ra $[f+(g+k)](t)=[(f+g)+k](t)$ hay $f+(g+k)=(f+g)+k$
Kiểm tra tiên đề 3: Xét hàm $g(t)=0,\forall t \in [a,b],g \in C[a,b]$
$(f+g)(t)=f(t)+g(t)=g(t)+f(t)=f(t)$
Suy ra $f+g=g+f=f$   
Kiểm tra tiên đề 4: Xét hàm $k(t)=0,\forall t \in [a,b],g(t)=-f(t),\forall t\in [a,b],g,k \in C[a,b]$
(chú ý: giả sử hàm f liên tục trên [a,b] ta cần chứng minh g liên tục trên [a,b],có thể gọi trực tiếp hàm -f thay vì gọi hàm $g=-f$)
$(f+g)(t)=f(t)+g(t)=f(t)+(-f(t))=0=k(t)$
Suy ra $f+g=f+(-f)=k$ (hàm k gọi là hàm đồng nhất không)
Kiểm tra tiên đề 5: $[(\alpha \beta)f](t)=(\alpha \beta)f(t)=\alpha(\beta f(t))=\alpha(\beta f)(t)=[\alpha(\beta f)](t)$
Suy ra $(\alpha \beta)f=\alpha(\beta f)$
Kiểm tra tiên đề 6: $[(\alpha+\beta)f](t)=(\alpha+\beta)f(t)=\alpha f(t)+\beta f(t)=(\alpha f)(t)+(\beta f)(t)=(\alpha f+\beta f)(t)$
Suy ra $(\alpha+\beta)f=(\alpha f+\beta f)$
Kiểm tra tiên đề 7: $[\alpha (f+g)](t)=\alpha (f+g)(t)=\alpha [f(t)+g(t)]=\alpha f(t)+\alpha g(t)=(\alpha f)(t)+(\alpha g)(t)=(\alpha f+\alpha g)(t)$
Suy ra $\alpha (f+g)=\alpha f+\alpha g$
Kiểm tra tiên đề 8: $(1.f)(t)=1.f(t)=f(t)$
Suy ra $1.f=f$ (chú ý phần tử đơn vị của trường các số thì là số 1, còn các trường khác có thể không phải là số 1)
Vậy $C[a,b]$ là một không gian tuyến tính trên trường F.
Ta định nghĩa $\left \| f \right \|_p=\left ( \int_{a}^{b}\left | f(t) \right|^p dt \right )^{\frac{1}{p}},p \geq 1$. Là một chuẩn.
Với $p=1, \left \| f \right \|_1= \int_{a}^{b}\left | f(t) \right| dt $
Kiểm tra $(N_1)$: Ta có $-\left | f(t) \right | \leq f(t) \leq \left | f(t) \right |, \forall t \in [a,b],f \in C[a,b]$
Suy ra $\int_{a}^{b}-\left | f(t) \right |dt \leq \int_{a}^{b}f(t)dt \leq \int_{a}^{b}\left | f(t) \right |dt$
Hay $-\int_{a}^{b}\left | f(t) \right |dt \leq \int_{a}^{b}f(t)dt \leq \int_{a}^{b}\left | f(t) \right |dt$
Vì $\left |a \right| \leq b \Leftrightarrow -b\leq a \leq b.$ Nên   $\left|\int_{a}^{b}f(t)dt \right| \leq \int_{a}^{b}\left | f(t) \right |dt$
Suy ra $\int_{a}^{b}\left | f(t) \right |dt \geq 0,\forall t \in[a,b]$ Hay $\left \| f \right \|_1 \geq 0$
$(\Leftarrow )$ giả sử $f(t)=0,\forall t \in [a,b]$. Khi đó $\left \| f \right \|_1= \int_{a}^{b}\left | f(t) \right| dt = \int_{a}^{b}\left | 0 \right| dt =0 \int_{a}^{b}1dt =0(b-a)=0 $
$(\Rightarrow )$ giả sử $\left \| f \right \|_1=0$. Ta chia $[a,b]$ thành n khoảng $ x_0 \equiv a < x_1<...<x_n\equiv b$ 
đặt $\Delta x_i=x_i-x_{i-1}(i=1,...,n)$, trong mỗi khoảng nhỏ $[x_{i-1},x_i]$ lấy một điểm $t_i$ tùy ý: $x_{i-1} \leq t_i \leq x_i,i=1,...,n$. Khi đó  $\left \| f \right \|_1=\int_{a}^{b}\left | f(t) \right| dt=\lim_{n\rightarrow \infty}\sum_{i=1}^{n}\left | f(t_i) \right |\Delta x_i=\lim_{n\rightarrow \infty }0=0$
Suy ra $\sum_{i=1}^{n}\left | f(t_i) \right |\Delta x_i=0$. Mà $\Delta x_i > 0,$ do đó $\sum_{i=1}^{n}\left | f(t_i) \right| \Delta x_i=0 \Leftrightarrow \sum_{i=1}^{n} \left| f(t_i) \right| =0\Leftrightarrow f(t_i)=0 (t_i \in [a,b],\forall i=1,...,n)$
Do vậy $\left \| f \right \|_1 = 0 \Leftrightarrow f=0 $
Kiểm tra $(N_2)$: $\left \| \alpha f \right \|_1=\int_{a}^{b}\left|(\alpha f)(t)\right|dt=\int_{a}^{b}\left|\alpha f(t)\right|dt=\left|\alpha\right|\int_{a}^{b}\left|f(t)\right|dt=\left|\alpha\right| \left \| f \right \|_1$
Kiểm tra $(N_3)$: $\left \| f+g \right \|_1=\int_{a}^{b}\left | (f+g)(t) \right |dt=\int_{a}^{b}\left | f(t)+g(t) \right |dt \leq \int_{a}^{b}\left | f(t) \right |dt+\int_{a}^{b}\left | g(t) \right |dt$ (theo bất đẳng thức Minkowski dưới dạng tích phân)
Với $p=2,\left \| f \right \|_2=\sqrt{\int_{a}^{b}\left | f(t) \right |^2dt}$
Kiểm tra tương tự trường hợp $p=1$
Với $p\rightarrow \infty$ đặt $t_i = argsup_{t \in [a,b]} \left |f(t)\right|,(t_i \text{ là chỉ số để f(t) là cận trên tức là }f(t_i) \text{ là cận trên )}. $ Khi đó $\left \| f \right \|_p =\left( \int_{a}^{b}\left | f(t) \right |^p dt \right)^\frac{1}{p}=\left ( \lim_{n\rightarrow \infty } \sum_{i=1}^{n} \left | f(t_i) \right |^p \Delta x_i \right )^\frac{1}{p}= \left | f(t_i) \right |\left [ \left ( 1+\left | \frac{f(t_1)}{f(t_i)} \right |^p +...+ \left | \frac{f(t_n)}{f(t_i)}\right |^p+... \right )\Delta x_i \right ]^\frac{1}{p}$  
Ta thấy $\lim_{p\rightarrow \infty}\left [ \left ( 1+\left | \frac{f(t_1)}{f(t_i)} \right |^p +...+ \left | \frac{f(t_n)}{f(t_i)}\right |^p+... \right )\Delta x_i \right ]^\frac{1}{p}=1$
$\left \| f \right \|_\infty = \left|f(t_i)\right |=sup_{t \in [a,b]}\left|f(t)\right |$
$(N_1),(N_2)$ kiểm tra tương tự, 
$\bullet $ Các không gian dãy bị chặn $c_o,l_{\infty},l_p(p\geq 1).$ Ta ký hiệu $\mathbb{K}^\mathbb{N}$ là tập hợp tất cả dãy số thực hay phức. (https://en.wikipedia.org/wiki/Sequence_space#c,_c0_and_c00)
$c_o = \left\{ (x_1,x_2,...) \in \mathbb{K}^\mathbb{N} : \lim_{n\rightarrow \infty}x_n=0  \right\}.$ (tập hợp các dãy số hội tụ tới không)  
$l_\infty=\left\{(x_1,x_2,...) \in \mathbb{K}^{\mathbb{N}}: sup_n \left| x_n \right| < \infty \right\}.$ 
 $l_p = \left\{ (x_1,x_2,...) \in \mathbb{K}^\mathbb{N} : \lim_{n\rightarrow \infty}x_n < \infty  \right\}.$
Với $x = (x_1,x_2,...),y = (y_1,y_2,...) \in c_o$ (hoặc $l_\infty, l_p$) và $\alpha \in F$ ta định nghĩa $x+y = (x_1+y_1,x_2+y_2,...)$ và $\alpha x=(\alpha x_1,\alpha x_2,...).$
Từ định nghĩa ta thấy ngay nếu $x,y \in c_o$ (hoặc $l_\infty$) và $\alpha \in F$ thì $x+y \in c_o$ (hoặc $l_\infty$). Dễ ràng nhưng không tầm thường, kiểm tra được với 2 phép toán này $c_o$ và $l_\infty$ là các không gian tuyến tính.
Nếu $x,y \in l_p$ và $\alpha \in F$ thì rõ ràng $\alpha x \in l_p.$ Với mọi $n \in \mathbb{N}$ ta có
$\left|x_n+y_n \right| \leq \left|x_n \right|+\left|y_n\right| \leq 2 max \left\{ \left|x_n \right|,\left|y_n\right| \right\}.$
Cho nên
$\left|x_n+y_n \right|^p \leq 2^p [max \{ |x_n|,|y_n|\}]^p \leq 2^p(|x_n|^p+|y_n|^p).$
Vì vậy
$\sum_{n=1}^\infty|x_n+y_n|^p \leq 2^p (\sum_{n=1}^\infty |x_n|^p + \sum_{n=1}^\infty |y_n|^p) <\infty .$
Tức là $x+y \in l_p.$ Với hai phép toán trên, dễ kiểm tra $l_p$ là một không gian tuyến tính.
Dễ ràng kiểm tra $c_o,l_{\infty},l_p(p\geq 1).$ là các không gian định chuẩn. $c_o,l_{\infty}$ có chuẩn là $\|x\|=sup_n |x_n|$. $l_p,p \geq 1$ có chuẩn là $\|x\|=(\sum_{n=1}^\infty |x_n|^p)^\frac{1}{p}.$

4. Sự hội tụ trong không gian định chuẩn


Xem tiếp >>

KHÔNG GIAN MÊTRIC

 

1. Lịch sử

Năm 1906 Maurice Fréchet giới thiệu về không gian mêtric trong cuốn Sur quelques points du calcul fonctionnel

2. Định nghĩa

Không gian mêtric ký hiệu là (M,d) trong đó M là một tập hợp và d là một mêtric trên M, tức là một hàm 
    $d:M\times M\rightarrow\mathbb{R}$
sao cho với mọi $x,y,z\in M$ thỏa mãn:
    1. $d(x,y) \geq 0$
    2. $d(x,y) = 0 \Leftrightarrow  x=y$
    3. $d(x,y)=d(y,x)$
    4. $d(x,z) \leq d(x,y)+d(y,z)$

3. Một số mêtric thường dùng

cho $x=(x_1,x_2,...,x_n),y=(y_1,y_2,...,y_n)\in \mathbb{R}^{n}$
ta định nghĩa $d_p(x,y)=(\sum_{i=1}^{n}(\left|x_i-y_i \right|)^p)^\frac{1}{p}$
Với  $p=1$ chúng ta có $d_1(x,y)=\left|x_1-y_1\right|+....+\left|x_n-y_n\right|$
khi đó $d_1(x,y)=\left|x_1-y_1\right|+....+\left|x_n-y_n\right|$ là một mêtric vì thỏa mãn 4 điều kiện của mêtric và còn gọi là mêtric Taxicab
với mọi $x,y,z \in \mathbb{R}^n$
kiểm tra điều kiện 1, $\left|x_1-y_1\right|+....+\left|x_n-y_n\right| \geq 0$ (theo định nghĩa trị tuyệt đối) 
                               $\Leftrightarrow d_1(x,y) \geq 0$
kiểm tra điều kiện 2, $d_1(x,y)=0$ 
                               $\Leftrightarrow  \left|x_1-y_1\right|+....+\left|x_n-y_n\right| = 0$
                               $\Leftrightarrow  \begin{cases}\left|x_1-y_1\right|=0\\ \vdots \\ \left|x_n-y_n\right|=0 \end{cases} $
                               $\Leftrightarrow  \begin{cases}x_1=y_1\\ \vdots \\x_n=y_n \end{cases} $
                               $\Leftrightarrow x=y $
kiểm tra điều kiện 3, $d_1(x,y)=\sum_{i=1}^{n}\left|x_i-y_i \right|=\sum_{i=1}^{n}\left|-(x_i-y_i \right)|=\sum_{i=1}^{n}\left|y_i-x_i \right|=d_1(y_i,x_i)$
kiểm tra điều kiện 4, $d_1(x,z)=\sum_{i=1}^{n}\left|x_i-z_i \right|=\sum_{i=1}^{n}\left|x_i-y_i+y_i-z_i \right| \leq \sum_{i=1}^n \left|x_i-y_i \right|+ \sum_{i=1}^{n} \left|y_i-z_i \right|$
                                $\Leftrightarrow d_1(x,z) \leq d_1(x,y)+d_1(y,z)$
Với $p=2$ chúng ta có $d_2(x,y)=\sqrt{\sum_{i=1}^n \left|x_i-y_i \right|^2}$
khi đó $d_2(x,y)=\sqrt{\sum_{i=1}^n \left|x_i-y_i \right|^2}$ là một mêtric vì thỏa mãn 4 điều kiện của mêtric và được gọi là mêtric Euclidean hay khoảng cách Euclidean.
với mọi $x,y,z \in \mathbb{R}^n$
kiểm tra điều kiện 1, $\left|x_i-y_i \right|^2 \geq 0,\forall x_i,y_y \in \mathbb{R},i=1,...,n$
                                 $\Leftrightarrow \sqrt{\sum_{i=1}^n \left|x_i-y_i \right|^2} \geq 0$
kiểm tra điều kiện 2, $d_2(x,y)=0$
                                 $\Leftrightarrow\sqrt{\sum_{i=1}^n \left|x_i-y_i \right|^2}=0$
                                 $\Leftrightarrow \sum_{i=1}^n \left|x_i-y_i \right|^2=0$
                                 $\Leftrightarrow \begin{cases}\left|x_1-y_1\right|^2=0\\ \vdots \\ \left|x_n-y_n\right|^2=0 \end{cases}$
                                 $\Leftrightarrow \begin{cases}x_1=y_1\\ \vdots \\ x_n=y_n \end{cases}$
                                 $\Leftrightarrow x=y$
kiểm tra điều kiện 3, $d_2(x,y)=\sqrt{\sum_{i=1}^n \left|x_i-y_i \right|^2}=\sqrt{\sum_{i=1}^n \left|-(x_i-y_i)\right|^2}=\sqrt{\sum_{i=1}^n \left|y_i-x_i \right|^2}=d_2(y,x)$
kiểm tra điều kiện 4, $\sqrt{\sum_{i=1}^n \left|x_i-z_i \right|^2}=\sqrt{\sum_{i=1}^n \left|x_i-y_i+y_i-z_i \right|^2} \leq \sqrt{\sum_{i=1}^n \left|x_i-y_i \right|^2}+\sqrt{\sum_{i=1}^n \left|y_i-z_i \right|^2}$ (áp dụng bất đẳng thức Minkowski)
Với $p \rightarrow \infty$, giả sử $i=arg max_{j=1,...,n} \left|x_j-y_j \right|$. Khi đó:
$d_p(x,y)=\left| x_i-y_i \right|\left(1+\left|\frac{x_1-y_1}{x_i-y_i} \right|^p+...+\left|\frac{x_{i-1}-y_{i-1}}{x_i-y_i} \right|^p+\left|\frac{x_{i+1}-y_{i+1}}{x_i-y_i} \right|^p+...+\left|\frac{x_n-y_n}{x_i-y_i} \right|^p\right)^{\frac{1}{p}}$
Ta thấy $\lim_{p \rightarrow \infty}\left(1+\left|\frac{x_1-y_1}{x_i-y_i} \right|^p+...+\left|\frac{x_{i-1}-y_{i-1}}{x_i-y_i} \right|^p+\left|\frac{x_{i+1}-y_{i+1}}{x_i-y_i} \right|^p+...+\left|\frac{x_n-y_n}{x_i-y_i} \right|^p\right)=1$
Nên $d_{\infty}(x,y)=\lim_{p \rightarrow \infty}d_p(x,y)=\left| x_i-y_i \right|=max_{j=1,...,n}\left| x_j-y_j\right|$

Xem tiếp >>

Bài 6: NGĂN XẾP VÀ HÀNG ĐỢI

 1. Ngăn xếp. Định nghĩa Ngăn xếp: Là một loại dữ liệu trừu tượng và các thao tác có thể dùng: Push(data): Thêm data vào ngăn xếp Top(): Tìm...