Thuật toán

Khái niệm thuật toán
Thuật toán (Algorithm) được biết đến từ thế kỷ IX do nhà toán học người Ba tư al-Khowarizmi đưa ra.
Bài toán tính toán (Computation) là một ánh xạ từ tập các đầu vào nào đó vào tập các đầu ra nhất định.
Thuật toán là một thủ tục xác định, bao gồm một dãy các bước cần thực hiện để từ một đầu vào cho trước nó cho một đầu ra.
Ví dụ: Bài toán sắp xếp một dãy số theo thứ tự tăng dần.

Đầu vào: Một dãy số (a1,..., an)
Đầu ra: Một hoán vị (a1(k),...,an(k)) sao cho a1(k) <=. . . <= an(k)
Thuật toán Insertion-Sort:

Procedure Insertion-Sort (a, n)
For i:=2 to n do do
Begin
key := ai ;
(* Chèn ai vào dãy đã sắp a1.. ai-1*)
j:=i-1
While j>0 and ai>key do
Begin
ai+1:= ai ;
j := j-1;
End;
ai+1 := key;
End;
2. Các tính chất của thuật toán
Tính chính xác (Precision): Thuật toán phải được mô tả chính xác.
Tính hữu hạn (Finiteness): Dừng và cho kết quả sau hữu hạn bước.
Tính đơn trị (Uniqueness): Các kết quả trung gian ở mỗi bước phải được xác định đơn trị phụ thuộc vào đầu vào và kết quả của bước trước.
Tính phổ dụng (Generality): Áp dụng được cho một lớp bài toán.

Ví dụ: Với thuật toán Insertion-Sort
Thuật toán mô tả chính xác từng bước thực hiện
Thuật toán dừng sau hữu hạn bước
Các kết quả trung gian ở mỗi bước được xác định một cách đơn trị, chỉ phụ thuộc vào và kết quả ở bước trước
Thuật toán áp dụng được cho một lớp bài toán
3. Các cấu trúc của thuật toán
Cấu trúc tuần tự
Cấu trúc lựa chọn
Cấu trúc lặp
4. Biểu diễn thuật toán
Có nhiều cách biểu diễn
Quy ước về biểu diễn thuật toán bằng ngôn ngữ giả code:
+ Việc viết dòng thụt vào biểu thị cấu trúc khối
+ Ký hiệu “” : Lời chỉ dẫn phía sau
+ j  i: Gán giá trị của i cho j
+ j  i  e: Gán giá trị của e cho i và j
+ Các cấu trúc lặp WHILE, FOR, và REPEAT và các cấu trúc điều kiện IF, THEN, và ELSE được thể hiện giống như trong Pascal.
5. Phân tích thuật toán?
Phân tích thuật toán là quá trình tìm ra những đánh giá về thời gian tính và bộ nhớ cần thiết để thực hiện thuật toán.
Phân tích có thể cho biết tính khả thi của thuật toán từ đó có thể loại các thuật toán không tốt.
Lượng thời gian tính và bộ nhớ cần thiết để thực hiện thuật toán được gọi là độ phức tạp của thuật toán.
* Ở đậy ta chỉ quan tâm đánh giá về thời gian tính.
6. Một số khái niệm cơ bản.
Kích thước dữ liệu đầu vào: Số bít cần thiết để biểu diễn nó.
Phép toán cơ bản: Phép toán có thể thực hiện với thời gian bị chặn bởi một hằng số không phụ thuộc vào kích thước dữ liệu đầu vào (Phép tính số học, so sánh, gán, ...).
Từ số lượng phép toán cơ bản => Thời gian thuật toán đòi hỏi.
Đánh giá độ phức tạp thuật toán là đánh giá số phép toán cơ bản như là hàm của kích thước dữ liệu đầu vào.
6. Một số khái niệm cơ bản (tiếp)

Thời gian tính tốt nhất của thuật toán là thời gian tối thiểu để thực hiện thuật toán với mọi bộ dữ liệu đầu vào kích thước n.
Thời gian tính tồi nhất của thuật toán là thời gian nhiều nhất để thực hiện thuật toán với mọi bộ dữ liệu đầu vào kích thước n.
Thời gian tính trung bình của thuật toán là thời gian trung bình để thực hiện thuật toán với mọi bộ dữ liệu đầu vào kích thước n.
Ví dụ. Xét thuật toán tìm số lớn nhất trong một dãy hữu hạn số.
Đầu vào: Một dãy số (a1,..., an)
Đầu ra: Số lớn nhất của dãy – max
Thuật toán:
Procedure Tim_Max(a,n)
Begin
Max:= a1;
For i:=2 to n do
if ai >max then Max:=ai;
End;
Trong thuật toán này, số n là đại lượng hợp lý nhất để đánh giá kích thước đầu vào. Khi đó thời gian tính tốt nhất, tồi nhất và trung bình đều bằng n-1.
7. Các ký hiệu tiệm cận
Trong thực tế, người ta thường quan tâm tốc độ tăng của thời gian tính khi tăng kích thước đầu vào hơn thời gian chính xác mà thuật toán đòi hỏi. Chẳng hạn thời gian tính của một thuật toán với kích đầu vào n là
t(n)=60n2 + 9n+9
Với n đủ lớn, t(n) xấp xỉ bằng n2. Khi đó ta nói t(n) có bậc là n2. Viết t(n)=(n2).
Ta có các định nghĩa:
7. Các ký hiệu tiệm cận (tiếp)
Giả sử f và g là các hàm đối số nguyên dương.
Ta nói f(n) có bậc không quá g(n), viết f(n)=O(g(n)) nếu tồn tại hằng số dương c và số nguyên dương n0 sao cho
|f(n)|  c |g(n)| với mọi n>n0.
Ta nói f(n) có bậc ít nhất là g(n), viết f(n)=(g(n)) nếu tồn tại hằng số dương c và số nguyên dương n0 sao cho
|f(n)|  c |g(n)| với mọi n>n0.
Ta nói f(n) có bậc là g(n), viết f(n)= (g(n)) nếu f(n)=O(g(n)) và f(n)=(g(n))
Ví dụ. Giả sử k là số nguyên dương. Chứng minh rằng 1k +2k+...+nk có bậc là nk+1.
Ta có
1k +2k+...+nk  nk+nk+...+nk = n.nk = nk+1
Suy ra 1k +2k+...+nk =O(nk+1)
Mặt khác
1k +2k+...+nk  [n/2]k+...+nk
 [n/2]k+...+[n/2]k
 n/2.[n/2]k = nk+1/2k+1
Suy ra 1k +2k+...+nk = (nk+1)
Vậy 1k +2k+...+nk = (nk+1)
Bài tập.

Chứng minh rằng mọi đa thức bậc k hệ số dương
Pk(n)=aknk + ak-1nk-1+...+a1n+a0
có bậc là nk (nghĩa là Pk(n)= (nk)
2. Chứng minh rằng
lg n!= (n lg n)
Hướng dẫn. lgn! =lgn+lgn-1+...+lg1>=lgn+...+lgn/2
>=lgn/2+...+lgn/2=n/2.lgn/2
>= (nlgn)/4.

Định nghĩa thời gian tính của thuật toán.
Nếu thuật toán đòi hỏi thời gian tính tốt nhất là t(n) với kích thước đầu vào n và t(n)=O(g(n)) thì thời gian tính tốt nhất của thuật toán có bậc không quá g(n) (hay thời gian tính tốt nhất của thuật toán có bậc là O(g(n)).
Nếu thuật toán đòi hỏi thời gian tính tồi nhất là t(n) với kích thước đầu vào n và t(n)=O(g(n)) thì thời gian tính tồi nhất của thuật toán có bậc không quá g(n) (hay thời gian tính tồi nhất của thuật toán có bậc là O(g(n)).
Nếu thuật toán đòi hỏi thời gian tính trung bình là t(n) với kích thước đầu vào n và t(n)=O(g(n)) thì thời gian tính tồi nhất của thuật toán có bậc không quá g(n) (hay thời gian tính trung bình của thuật toán có bậc là O(g(n)).
Khái niệm bậc ít nhất của thời gian tính tốt nhất, tồi nhất, trung bình của thuật toán được định nghĩa tương tự bằng cách thay O bởi  và “không quá” bởi “ít nhất” trong định nghĩa trên.
Nếu thời gian tính tốt nhất (tồi nhất, trung bình) của thuật toán vừa là O(g(n)) vừa là (g(n)) thì ta nói thời gian tính tốt nhất (tồi nhất, trung bình) của thuật toán là (g(n)).
!!! Khi nói thời gian tính của thuật toán là O(f(n)) ta hiểu đó là thời gian tính trong tình huống tồi nhất. Còn khi nói thời gian tính của thuật toán là (f(n)) ta hiểu đó là thời gian tính trong tình huống tốt nhất.
Ví dụ 1. Đánh giá số lần thực hiện câu lệnh x:=x+1 trong đoạn chương trình sau:
For i:=1 to n do
For j:=1 to i do
x:=x+1;

Ta có số lần thực hiện câu lênh x:=x+1 là
1+2+...+n = O(n2)
Ví dụ 2. Đánh giá số lần thực hiện câu lệnh x:=x+1 trong đoạn chương trình sau:
j:=n;
While j>=1 do
Begin
For i:=1 to j do x:=x+1;
j:=j div 2;
End;
Ký hiệu số lần thực hiện của câu lệnh là t(n). Ta có:
+ Lần lặp while đầu tiên (j=n), câu lệnh x:=x+1 thực hiện n lần. Vì vậy t(n)= (n). (vì t(n)>n)
+ Sau lần lặp đầu tiên đó, j:=j div 2 => j+ Ký hiệu k là số lần lặp của vòng while, khi đó số lần lặp của câu lệnh x:=x+1 không quá n+n/2+n/4+...+n/2k-1. Nghĩa là
t(n) < n+n/2+n/4+...+n/2k-1 = n(1-1/2k)/(1-1/2) = 2n(1-1/2k)<2n
Suy ra t(n)=O(n).
Vậy số lần thực hiện câu lênh x:=x+1 là t(n) = (n2)
Ví dụ 3. Đánh giá thời gian tính của thuật toán sau:
Function Linear_Search (s, n, key);
Begin
i:=0;
Repeat
i:=i+1;
Until (i>=n) or (si=key);
Linear_Search := i;
End;
Rõ ràng, thời gian tính của thuật toán có thể đánh giá bởi số lần thực hiện của câu lệnh i:=i+1;
Ta có:
Nếu s1:=key => câu lệnh i:=i+1 thực hiện 1 lần => thời gian tính tốt nhất của thuật toán là (1);
Nếu key không có trong dãy => câu lệnh i:=i+1 thực hiện n+1 lần => thời gian tính tồi nhất của thuật toán là (n);
Ta sẽ tính thời gian trung bình t(n) của thuật toán.
Nếu si=key (i=1, 2, ..., n) => câu lệnh i:=i+1 thực hiện i lần và nếu không tìm thấy thì câu lệnh i:=i+1 thực hiện n lần => thời gian tính trung bình của thuật toán là
[(1+2+...+n) +n ]/(n+1)
Ta có
[(1+2+...+n) +n ]/(n+1)=[n(n+1)/2+n]/(n+1)<(n2+n)/(n+1)=n.
Suy ra t(n)=O(n).
+ Mặt khác
[(1+2+...+n) +n ]/(n+1) > (n2+n)/(n+1)=n/4
Suy ra t(n)= (n).
Vậy t(n) = (n)
Đánh giá độ phức tập của thuật toán là việc làm không đơn giản. Thông thường, ta sử dụng các đánh giá sau:

Một số tính chất của các ký hiệu tiệm cận
Mệnh đề 1.
Nếu c là hằng số thì O(c*f(x))=O(f(x)), (c*f(x))= (f(x)), (c*f(x))= (f(x)).
Nếu f1(x)= O(g1(x)) và f2(x)= O(g2(x)) thì f1(x)+f2(x) = max(|g1(x)|,|g2(x)|).
Nếu f1(x)= O(g1(x)) và f2(x)= O(g2(x)) thì f1(x)*f2(x) = O(g1(x)*g2(x)).
Nếu f(x)=O(g(x)) và a>0 thì (f(x))a=O(g(x)a)

Mệnh đề 2.
f(n)=O(g(n)) và g(n)=O(h(n))  f(n)=O(h(n))
f(n)=(g(n)) và g(n)=(h(n))  f(n)=(h(n))
f(n)=(g(n)) và g(n)= (h(n)) f(n)= (h(n))
f(n)= (g(n))  g(n)= (f(n))
f(n)= O(g(n))  g(n)= (f(n))
! Sự so sánh tiệm cận giữa f và g tương tự so sánh 2 số:
f(n)=O(g(n))  a  b
f(n)=  (g(n))  a  b
f(n)= (g(n))  a = b
1. Phân tích độ phức tạp của các cấu trúc
1.1. Cấu trúc tuần tự
Giả sử P, Q là 2 đoạn độc lập của một thuật toán với thời gian tính tương ứng là T(P) và T(Q).
Quy tắc tuần tự. Thời gian đòi hỏi bởi (P; Q) (thực hiện P rồi tiếp theo thực hiện Q) sẽ là
T(P;Q) = T(P)+T(Q).
Vì vậy
T(P; Q) = (max(T(P),T(Q));
1.2. Cấu trúc lặp
Vòng lặp For
Xét vòng lặp
For i:=1 to n do P(i);
Nếu thời gian tính của P(i) là t với mọi i:=1..n và không tính đến thời gian tổ chức vòng lặp thì thời gian thực hiện vòng lặp là mxt
Trong trường hợp tổng quát, gọi t(i) là thời gian thực hiện P(i). Nếu không tính đến thời gian tổ chức vòng lặp thì thời gian tính của vòng lặp trên là
T= mi=1t(i).
Ví dụ. Xét thuật toán tìm số Fibonacci thứ n sau:
Function Fibiter(n)
Begin
i:=0;
j:=1;
For k:=1 to n do
Begin
j:=j+i;
i:=j-i;
End;
Fibiter:=j;
End;
Nếu xem các phép toán số học đòi hỏi thời gian là hằng số thì thời gian tính của thuật toán là (n).
b) Vòng lặp While và Repeat
Xét vòng lặp
While B do P; hoặc Repeat P Until B;
Việc phân tích các vòng lặp này rất khó khăn vì không biết số lần lặp.
Kỹ thuật cơ bản:
Cần xác định một hàm của các biến trong vòng lặp sao cho nó có giá trị giảm dần trong quá trình lặp. Vòng lặp dừng nếu hàm nhận giá trị nguyên dương
Coi vòng lặp như một thuật toán đệ quy
Ví dụ. Xét thuật toán tìm tìm kiếm nhị phân sau:
Function Binary_Search(T[1..n], x)
Begin
i:=1;
j:=n;
While i Begin
k:=(i+j) div 2;
Case
x x=T[k]: i:=k; j:=k; Binary_Search:=k; Exit;
x>T[k]: i:=k+1;
End;
End;
End;
Hướng dẫn. Để phân tích thuật toán này, ta xác định hàm d:=j-i+1. Như vậy d là số lượng phần tử của mảng T cần được khảo sát.
Vòng lặp bắt đầu với d=n và kết thúc khi d<=1 (tương ứng với i>=j).
Thời gian tính của thuật toán này là O(log n).
Ký hiệu d, d’ là giá trị của j-i+1 và i, j, i’, j’ là giá trị của i, j trước và sau khi thực hiện vòng lặp.
Khi đó:
- Nếu xdo đó d’=j’-i’+1=(i+j) div 2 -1-i+1
<=(i+j)/2 – i < (j-i+1)/2=d/2
- Nếu x >T[k], thì j’=j, i’=(i+j) div 2 +1
do đó d’=j’-i’+1=j-(i+j) div 2
<=j-(i+j-1)/2 – i < (j-i+1)/2=d/2
- Nếu x = T[k] thì d’=1 và d>=2
Vậy ta luôn có d’<=d/2. Do vòng lặp dừng khi d<=1 nên thuật toán phải dừng.
Tính thời gian tính của thuật toán:
Gọi dm là giá trị của j-i+1 ở lần lặp thứ m, m>=1 và d0 = n. Ta có
dm <= dm-1/2, m>=1. Suy ra dm<=n/2m.
Do vòng lặp kết thúc khi d<=1. Do đó vòng lặp kết thúc khi m= logn, nghĩa là vòng lặp kết thúc sau không quá logn lần.
Vì mỗi lần lặp, thời gian tính là hằng số nên ta có thời gian tính của thuật toán là O(logn)
2. Công thức đệ quy
Việc đánh giá thời gian tính của các thuật toán đệ quy là rất khó. Ta thường xây dựng công thức đệ quy để đánh giá thuật toán đệ quy.
Công thức đệ quy thường gặp:
T(n)= (1) nếu n<=c
T(n)=T(n/b)+D(n)+C(n) nếu ngược lại
Các phương pháp giả công thức đệ quy:
+ Phương pháp đoán nhận
+ Phương pháp lặp
+ Định lý thợ
C-1) Phương pháp đoán nhận
Dự đoán lời giải
Dùng quy nạp để chứng minh tính đúng đắn của dự đoán
Ví dụ. Giải công thức đệ quy T(n)=3T(n/3) +n
Dự đoán: T(n)=O(n log n)
Chứng minh điều dự đoán trên:
Ta cần chứng minh T(n) c.n.logn. Ta có
T(n) = 3T(n/3) +n  3.c. n/3.log n/3+n
 c.n.log(n/3) + n  c’.n.log(n),
với c’ max(c,1/log3).
Vậy công thức đúng.

! Để dự đoán lời giải, ta thường sử dụng các cách sau:
Dựa vào các lời giải tương tự đã gặp.
Chứng minh cận trên và cần dưới cho công thức đệ quy. Chẳng hạn nếu T(n)= (n) và T(n)=O(n2) => Dự đoán T(n)= (n logn)
Sử dụng kỹ thuật đổi biến. Chẳng hạn để giải công thức T(n)=2T(n1/2) + logn.
Đặt m=log n => T(2m) = 2T(2m/2)+m.
Đặt S(m)=T(2m) => S(m)=2S(m/2)+m
Do đó S(m)=O(mlogm) => T(n)=O(log n loglog n).
iv) Nếu không chứng minh được dự đoán => Điều chỉnh số hạng tăng chậm trong dự đoán.
C-2) Phương pháp lặp
Thực hiện thế dần công thức đệ quy để biểu diễn nó như là tổng của các số hạng chỉ phụ thuộc điều kiện đầu vào n.
Ví dụ. Giải công thức đệ quy T(n)=3T(n/4)+n
Ta có
T(n) = n + 3T(n/4)
= n + 3n/4 + 9T(n/16)
= n + 3n/4 +9[n/16+27T(n/64)
= ...<3n
=> T(n) = O(n)
C-3) Phương pháp sử dụng định lý thợ
Định lý thợ. Giả sử T(n)=aT(n/b)+f(n). Trong đó
a 1, b>1 là các hằng số
f(n) là hàm số tiệm cận dương
T(n) xác định với mọi số nguyên không âm
n/b có thể là n/b hoặc n/b.
Khi đó T(n) có thể đánh giá tiệm cận như sau:
1. Nếu f(n)=O(nlogba-) với hằng số >0 nào đó, thì T(n)= (nlogba)
2. Nếu f(n)= (nlogba), thì T(n)= (nlogbalogn)
3. Nếu f(n)= (nlogba+) với hằng số >0 nào đó và nếu a.f(n/b)< c.f(n) với hằng số c<1, thì T(n)= (f(n)).
Định lý thợ rút gọn. Giả sử a 1, b>1 là các hằng số và T(n)=a.T(n/b)+c.nk, với n>0. Khi đó ta có
1. Nếu a>bk thì T(n)= (nlogba)
2. Nếu a=bk thì T(n)=(nk log n)
3. Nếu aVí dụ 1. Giải công thức đệ quy T(n)=16T(n/4)+n
Áp dung định lý thợ với trường hợp (1): a=16, b=4 và =1 ta có, f(n)=n= (nlogba-  ) => T(n)= (nlogba)= (n2).
Ví dụ 2. Giải công thức đệ quy T(n)=T(3n/7)+1
Áp dung định lý thợ với trường hợp (2): a=1, b=7/3 ta có, f(n)=1= O(nlogba) => T(n)= (nlogbalogn)= (logn).
Ví dụ 3. Giải công thức đệ quy T(n)=3T(n/4)+nlogn
Áp dung định lý thợ với trường hợp (3): a=3, b=4 và =(1-log43)  0.2 ta có, f(n)=n.logn=(nlog43+) (vì nlog43+n => n.logn > n) và lấy c=3/4
=> a.f (n/b)Chú ý. Có thể áp dụng định lý thợ rút gọn với các ví dụ 1 và 2.
3. Phương pháp sử dụng câu lệnh đặc trưng
Câu lệnh đặc trưng là câu lệnh có số lần thực hiện không ít hơn bất kỳ câu lệnh nào trong thuật toán.
Khi phân tích thuật toán ta chỉ quan tâm đến việc đếm số lần thực hiện của câu lệnh đặc trưng.
Ví dụ. Với thuật toán Fibiter trên, ta chọn câu lệnh j:=i+j là câu lệnh đặc trưng. Khi đó ta có thời gian tính của thuật toán là (n).
!Ngoài các phương pháp trên còn có các phương pháp phân tích thuật toán khác, chẳng hạn phương pháp phân tích khấu trừ.
3. Phương pháp phân tích khấu trừ
Giới thiệu
Phương pháp cài đặt con đếm nhị phân
Phương pháp tính toán chi li
Phương pháp sử dụng hàm thế năng.
Bài tập.
Chứng minh rằng thời gian tính của công thức T(n)= T(n/2 )+n là O(n)
Chứng minh rằng thời gian tính của công thức T(n/2+17) + n là O(n log n)
Sử dụng phương pháp đổi biến để giải công thức T(n)=2 T(n1/2) + 1.
Chứng minh rằng T(n)=9T(n/3)+n có thời gian tính là O(n2).
Chứng minh rằng T(n)=2T(n/2)+nlogn có thời gian tính là O(lgn).
Một bài toán có thể có nhiều lời giải khác nhau. Các lời giải có thể đã biết hoặc chưa biết
Đánh giá độ phức tạp tính toán của bài toán là đưa ra thời gian tính của thuật toán tốt nhất trong tất cả các thuật toán
Có 2 cách tiếp cận để giải quyết vấn đề này:
Đưa ra đánh giá cận dưới độ phức tạp của bài toán
Chỉ ra mức độ khó của bài toán
3.1. Đánh giá cận dưới
3.1.1. Độ phức tạp tính toán của bài toán
Ký hiệu T(A) là thời gian tính của thuật toán A với đầu vào X. Khi đó, thời gian tính trong tình huống tồi nhất của thuật toán A đối với dữ liệu vào kích thước n là
TA(n)=max{TA(X): |X|=n}
Độ phức tạp trong tình huống tồi nhất của bài toán P là thời gian tính trong tình huống tồi nhất của thuật toán tốt nhất để giải nó. Nghĩa là
TP(n) = min{TA(n): A  }=min{max{TA(X)|X|=n}:A  }
Trong đó  là tập tất cả các thuật toán giải bài toán P.
Cận trên. Nếu thuật toán A giải bài toán P có thời gian tính trong tình huống tồi nhất là TA(n) = O(f(n)) thì
TP(n) <= TA(n) =O(f(n)).
Nghĩa là ta có cận trên cho độ phức tập của bài toán P (vì mọi thuật toán tốt hơn sẽ cho cận trên tốt hơn)
Cận dưới. Việc đánh giá cận dưới của bài toán là chỉ ra mức độ khó của bài toán.
Để chỉ ra
Tp(n) = (f(n))
ta cần chỉ ra rằng
i) Có thuật toán với thời gian tính (f(n)) để giải bài toán P
ii) Mọi thuật toán giải bài toán P đều đòi hỏi thời gian tính trong tình huống tồi nhất là (f(n)).
Đòi hỏi ii) có thể thay bởi: Cận dưới cho độ phức tạp tính toán của bài toán P là (f(n)).
3.1.2. Các phương pháp đánh giá cận dưới độ phức tạp tính toán của bài toán
PP sử dụng cây quyết định
Cây quyết định là cây mà mỗi đỉnh của nó tương ứng với một truy vấn dữ liệu. Các cạnh của nó tương ứng với các khả năng trả lời câu hỏi. Mỗi lá tương ứng với một đầu ra.
Để tính toán với cây quyết định, ta bắt đầu từ gốc và đi theo một đường đi đến lá. Tại mỗi nút trung gian, câu trả lời cho truy vấn sẽ dẫn ta tới nut tiếp theo. Khi đến lá, ta thu được một đầu ra.
Thời gian tính của thuật toán cây quyết định là số truy vấn trên đường đi từ gốc đến lá.
Như vậy,
 Thời gian tính trong tình huống tồi nhất của thuật toán sẽ là độ cao của cây quyết định
 Số truy vấn là cận dưới cho thời gian tính.
Việc xác định cận dưới nhờ sử dụng cây quyết định được dựa trên lập luận:
“Các truy vấn đối với dữ liệu phải đảm bảo đủ thông tin để có thể xác định được đầu ra có thể”.
Nếu bài toán có N đầu ra thì mọi cây quyết đều có N lá
Nếu cây có N lá và mỗi nút có nhiều nhất k con thì độ cao của cây ít nhất là
logkN = (log N)
- Số trung vấn là cận dưới cho thời gian tính.
Ví dụ 1. (Bài toán tra từ điển)
Bài toán. Cho mảng A gồm n số được sắp theo thứ tự tăng dần và một số x. Xác định xem x có mặt trong mảng A hay không? Nếu có hãy chỉ ra vị trí của x trong mảng.
Ta xây dựng cây quyết định như sau:
Mỗi nút ứng với một câu hỏi dạng “xMỗ nút có 2 con, một con ứng với giá trị i và một nút ứng với giá trị “none”
Chẳng hạn với dãy A:
2, 3, 5, 7, 11,13,17,19
Ta có thể xây dựng cây quyết định sau:
X<11?
X<17?
X<5?
X<19?
X<13?
X<7?
X<3?
X=19?
X=15?
X=13?
X=5?
X=7?
X=11?
X=3?
X=2?
13
5
7
11
3
2
-
-
-
-
-
19
17
-
-
-
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Với bài toán tra từ điển, nếu tập A gồm N phần tử, do có N+1 đầu ra nên mọi cây quyết định đều có N+1 lá. Vì vậy mọi cây quyết định đều có độ cao ít nhất là logkN+1 = (log N).
 cận dưới của độ phức tạp tính toán của bài toán tra từ điển trong mô hình tính toán cây quyết định là (log N).

b) PP lập luận phản biện
Ý tưởng. Có một nhà phản biện siêu phàm có khả năng ra bộ dữ liệu sao cho thuật toán làm việc tồi nhất, mặc dù không biết thuật toán.
Ví dụ. Trò chơi đoán bit.
Có một dãy nhị phân gồm n bit. Cần xác định xem nó có chứa bit 1 hay không?
Ta có thể trả lời coi hỏi trên bằng cách duyệt qua tất cả các bit của dãy.
Câu hỏi đặt ra là: Liệu có thuật toán nào trả lời câu hỏi trên mà không cần xem xét hết tất cả các bit của dãy hay không?
Câu trả lời là không.
Chứng minh như thế nào?
Khi thuật toán khảo sát dãy bit, nhà phản biện sẽ bật các bít có giá trị thích hợp để thuật toán làm việc lâu nhất: Nếu thuật toán hỏi đến bit nào thì thành phân tương ứng của dãy bit đầu vào được đặt là 0.
- Giả sử thuật toán còn bit thứ i chưa khảo sát.
- Nếu thuật toán trả lời là “dãy đã cho có chứa bit 1” thì bật bit thứ i trong dãy đầu vào là 0. Nếu thuật toán trả lời là “dãy đã cho không chứa bit 1” thì bật bit thứ i trong dãy đầu vào là 1. Như vậy ta có phản ví dụ.
Vậy cận dưới độ phức tạp của bài toán là (N).
Bài tập. Đánh giá cận dưới độ phức tạp tính toán của bài toán sắp xếp.

3.2. Nhập môn NP-đầy đủ.
- Năm 1960, Steve Cook và Dick Karp đã khẳng định rằng yếu cầu tối thiểu đối với một thuật toán hiệu quả là thời gian tính của nố phải là đa thức.
- Với nhiều bài toán, việc tìm ra thuật toán như vậy rất khó khăn. Thậm chí không biết coá tồn tại thuật toán như vậy không?
 Steve Cook và Dick Karp đã đưa ra định nghĩa lớp bài toán NP-đậy đủ mà đến nay vẫn chưa có thuật toán giải nó.
3.2.1. Bài toán quyết định.
Là bài toán có đầu ra là (Yes/No)
Có những bộ dữ liệu đầu vào cho câu trả lời Yes (bộ dữ liệu Yes). Có những bộ dữ liệu đầu vào cho câu trả lời No (bộ dữ liệu No).
Ví dụ.
Bài toán về tính nguyên tố. Hỏi số n cso là nguyên tố hay không?
+ Nếu n= 7  Câu trả lời là yes
+ Nếu n= 8  Câu trả lời là No
Bài toán tổng con. Cho tập S gòm n số nguyên dương và một số nguyên dương T. Hỏi có thể tìm được tập con của S sao cho tổng của chúng bằng T?
+ Có những bộ dữ liệu cho câu trả lời Yes
+ Có những bộ dữ liệu cho câu trả lời No
3.2.2. Bằng chứng ngắn gọn dễ kiểm tra.
Ta gọi bằng chứng ngắn gọn dễ kiểm tra để xác nhận câu trả lời Yes cho bộ dữ liệu đầu vào Yes là một bằng chứng có độ dài bị chặn bởi một đa thức bậc cố định của độ dài dữ liệu đầu vào của bài toán và việc kiểm tra nó là bằng chứng xác thực nhận câu trả lời yes đối với đầu vào đã cho của bài toán có thể thực hiện xong sau thời gian đa thức.
Tương tự ta có khái niệm bằng chứng ngắn gọn dễ kiểm tra để xác nhận câu trả lời No cho bộ dữ liệu đầu vào No.
Ví dụ. Với bài toán kiểm tra tính hợp số (tính nguyên tố). Ta có thể đưa ra bằng chứng ngắn gọn dễ kiểm tra cho câu trả lời Yes (No) bằng cách đưa ra một ước khác 1 và chính nó.
3.2.3. Lớp bài toán P, NP và co-NP.
+ Lớp P. Lớp các bài toán có thể giải được sau thời gian đa thức.
+ Lớp NP. Lớp các bài toán quyết định mà để xác nhận câu trả lời yes của nó, ta có thể đưa ra bằng chứng ngắn gọn dễ kiểm tra.
+ Lớp co-NP. Lớp các bài toán quyết định mà để xác nhận câu trả lời No của nó, ta có thể đưa ra bằng chứng ngắn gọn dễ kiểm tra.
Từ các khái niệm trên ta có:
P  NP và P  co-NP
Vấn đề đặt ra là:
P=NP?
NP  co-NP
Đến nay vẫn chưa có câu trả lời!
3.2.4. Quy dẫn.
Giả sử A và B là hai bài toán quyết định.
Ta nói A có thể quy dẫn sau thời gian đa thức về B nếu tồn tại thuật toán thời gian đa thức R cho phép biến đổi bộ dữ liệu vào x của A thành bộ dữ liệu vào R(x) của B sao cho x là bộ dữ liệu vào yes của a khi và chỉ khi R(x) là bộ dữ liệu yes của B. Khi đó R được gọi là phép quy dẫn.
Nếu A quy dẫn được về B và B có thuật toán đa thức  A có thuật toán đa thức.
Ký hiệu  để chỉ A quy dẫn về B. Ta có:
Nếu A  B và B  C thì A  C
Lớp bài toán P đóng với phép quy dẫn.
3.2.5. Lớp bài toán NP-khó và NP-đầy đủ.
Một bài toán quyết định A được gọi là NP-đầy đủ nếu:
A là bài toán trong NP
Mọi bài toán trong NP đều có thể quy dẫn về A.
Một bài toán A được gọi là NP-khó nếu như sự tồn tại thuật toán đa thức để giải nó kéo theo sự tồn tại thuật toán đa thức để giải mọi bài toán trong NP.
Giả sử A là bài toán NP-đầy đủ, bài toán B thuộc NP và A quy đẫn được về B thì B cũng là bài toán NP-đầy đủ.
A là NP-khó  Nếu A giải được trong thời gian đa thức thì P=NP.
NP-đầy đủ  NP-khó.
Co-NP
NP
P
NP- đầy đủ
NP- khó
Phân lớp các bài toán
3.2.6. Ví dụ về các lớp bài toán.
Bài toán thuộc lớp P:
Bài toán về tính liên thông của đồ thị. Hỏi đồ thị vô hướng G=(V, E) có liên thông hay không.
Có thể giải bài toán này với thời gian tính O(n2).

Bài toán thuộc lớp NP
Bài toán kiểm tra tính hợp số
Bài toán kiểm tra sự tồn tại chu trình Hamilton của đồ thị.
Bài toán thuộc lớp Co-NP
Bài toán kiểm tra tính nguyên tố
Bài toán kiểm tra tính tồn tại duy nhất của đường đi đơn độ dài L nối hai đỉnh s và t trong đồ thị.
Bài toán thuộc lớp NP-đầy đủ
Bài toán 3-SAT:
Cho biểu thức bun là hội của các mệnh đề, mỗi mệnh đề là tuyển của 3 toán hạng, mỗi toán hạng là một biên Bun hoặc phủ định của nó. Biểu thức có dạng như vậy gọi là công thức 3-CNF.
Bài toán: Cho công thức 3-CNF. Hỏi có tồn tại một bộ giá trị của các biến sao cho biểu thức nhận giá trị True hay không.
Bài toán quy hoạch nguyên tuyến tính dạng quyết định (ILP): Hởi hệ bất phương trình Ax b có nghiệm nguyên hay không?
Bài toán thuộc lớp NP- khó
Bài toán hamilton dạng quyết định (Ham-cycle): Hỏi đồ thị vô hướng G=(V, E) có chứa chu trình Hamilton hay không?
Bài toán tổng con: Cho tập S gồm n số nguyên dương s1,..., sn và số nguyên dương t. Hỏi có thể tìm được tập con S’ của S sao cho tổng của các số thuộc S’ bằng t.
4.1. Kỹ thuật thiết kế thuật toán
Có nhiều chiến lược để thiết kế thuật toán, một trong những chiến lược phổ biến nhất là chiến lược chia để trị
Để thể hiện chiến lược chia để trị ta sử dụng phương pháp phân tích TOP-DOWN
Trong quá trình thiết kế giải thuật theo phương pháp phân tích Top-Down, ta tiến hành tinh chỉnh từng bước:
- Lúc đầu trình bày giải thuật theo ngôn ngữ tự nhiên phả ánh các nội dung chính của bài toán.
Trong quá trình phân rã, chuyển dần thành giả ngôn ngữ, định hướng về ngôn ngữ lập trình.
Định hướng chuyển dữ liệu từ dạng cấu trúc thành dạng lưu trữ.
Ví dụ. Thiết kế thuật toán sắp xếp dãy số nguyên a1, a2, . . ., an theo thứ tự tăng dần.
Trước hết ta mô tả giải thuật như sau:
Từ dãy số chưa sắp, chọn phần tử nhỏ nhất đặt vào cuối dãy đã sắp
Lặp lại quá trình trên cho đến khi dãy chưa sắp rỗng.
Vấn đề đặt ra là: Dãy đã sắp đặt ở đâu?
Nếu quyết định đặt dãy đã sắp ở tại vị trí của dãy ban đầu => Đổi chổ phần tử nhỏ nhất với phần tử hiện dang ở vị trí đó.
Ta có bước mô tả tiếp theo của thuật toán:
Với mỗi i=1,...,n
+ Tìm phần tử nhỏ nhất aj trong dãy con ai,...,an.
+ Đổi chỗ ai và aj cho nhau
Nếu định hướng chương trình vào ngôn ngữ Pascal, ta có:
For i:=1 to n do
+ Tìm phần tử nhỏ nhất aj trong dãy con ai,...,an.
+ Đổi chổ ai và aj cho nhau.
Đến đây ta còn 2 bài toán con cần giải quyết:
(1) Tìm phần tử nhỏ nhất aj trong dãy con ai,...,an.
(2) Đổi chổ ai và aj cho nhau.
Đối với bài toán con (1), có thể giải quyết như sau:
Coi ai là phần tử nhở nhất của dãy con ai,...,an.
Lần lượt so sánh giá trị nhỏ nhất đó với ai+1, ...,an, nếu gặp phần tử nhỏ hơn thì coi nó là phần tử nhở nhất mới
Sau khi so sánh với n, ta thu được phần tử nhỏ nhất.
J:=i;
For k:=j+1 to n do
if akĐối với bài toán con (2), để đổi chỗ ta có thể sử dụng biến trung gian TG.
tg:=ai; ai:=aj; aj:=tg;
Như vậy ta có thuật toán sắp xếp sau:
For i:=1 to n do
Begin
J:=i;
For k:=j+1 to n do
if ak tg:=ai; ai:=aj; aj:=tg;
End;
Chia để trị và đệ quy
Chiến lược thiết kế thuật toán chia để trị nhiều khi được găn liện với đệ quy. Để giải quyết bài toán đưa ra, chúng chia bài toán ra thành một số bài toán con tương tự với bài toán gốc nhưng với kích thước nhỏ hơn, giải quyết đệ quy các bài toán con, và sau đó kết hợp các lời giải đó để tạo ra lời giải cho bài toán gốc.
Kiểu chia và trị bao gồm 3 bước cho mỗi mức đệ quy:
Chia: Chia bài toán thành các bài toán con.
Trị: Giải quyết các bài toán con một cách đệ quy.
Kết hợp Kết hợp các lời giải của các bài toán con thành lời giải cho bài toán gốc.
Ví dụ. Sắp xếp trộn (Merge-Sort)
MERGE-SORT(A,p,r)
if p < r then
Begin
q := (p + r) div 2
MERGE-SORT(A,p,q)4
MERGE-SORT(A, q + 1, r)
MERGE(A,p,q,r)
End;
4.2. Một số thuật toán trong tin học.
1. Thuật toán tham lam
2. Thuật toán chia để trị
3. Các thuật toán trên đồ thị
4. Giải thuật song song
The End
Cao Thanh Sơn; Hoàng Hà; Trung Thành
Cao Thanh Liêm; Thảo; Huyền
Trần Thanh Mơ; V. Quang; Dũng
Trần Thanh Phong; Hưng; Tiến
Lê Văn Thuận; H. Quang; Nhung
Trần Bình Giang; M.Thanh; C.Thành