text:
Giáo trình Lý thuyết thuật toán
Chia sẻ: Phan Thi Ngoc Giau | Ngày: | Loại File: PDF | Số trang:92
lượt xem 58
download
Giáo trình Lý thuyết thuật toán
Giải bài toán có nghĩa là xuất phát từ dữ liệu vào, thực hiện một dãy hữu hạn những thao tác có có sở khoa học thích hợp để tìm được dữ liệu ra theo yêu cầu của bài toán. Độ phức tạp dữ liệu vào của bài toán được hiểu là số lượng dữ liệu vào các bài toán.
Bình luận(0) Đăng nhập để gửi bình luận!
Nội dung Text: Giáo trình Lý thuyết thuật toán
- Giáo trình Lý thuyết thuật toán
- Giáo trình Lý thuyết thuật toán-Bộ môn Khoa học máy tính-2010 MỤC LỤC Nội dung Trang Chương 1: Kỹ thuật phân tích đánh giá thuật toán 4 1.1. Khái niệm bài toán và độ phức tạp dữ liệu vào 4 1.1.1. Khái niệm bài toán 4 1.1.2. Độ phức tạp dữ liệu vào của bài toán 4 1.2. Các mô hình tính toán 4 1.2.1. Máy Turing 5 1.2.2. Máy xử lý thuật toán viết bằng ngôn ngữ tựa ALGOL 7 1.3. Khái niệm thuật toán và độ phức tạp của thuật toán 7 1.3.1. Thuật toán(Algorithm) 7 1.3.2 Chi phí phải trả cho một quá trình tính toán và các khái 7 niệm về độ phức tạp thuật toán 1.4. Cách tính độ phức tạp 10 1.4.1. Các quy tắc cơ bản 10 1.4.2. Độ phức tạp của các chương trình đệ quy 11 1.5. Thuật toán không đơn định đa thức(Nodeterministic 14 Polynomial NP) 1.5.1. Sự phân lớp các bài toán. 16 1.5.2. Khái niệm “dẫn về được” (Phép quy dẫn) 17 1.5.3 Lớp bài toán NP - khó (NP - hard) và NP - đầy đủ (NP – 18 Complate) 1.6. Thuật toán xấp xỉ (Heuristic) 22 1.6.1. Các khái niệm 22 1.6.2. Thuật toán ε - xấp xỉ tuyệt đối 24 1.6.3.Thuật toán ε - xấp xỉ 26 1.7. Chứng minh tính đúng đắn của thuật toán 28 1.7.1. Ví dụ: 28 1.7.2. Phương pháp thử 28 1.7.3. Kiểm chứng tính đúng đắn 29 Chương 2: Các thuật toán Sắp xếp 31 2.1. Bài toán sắp xếp 31 2.1.1. Tầm quan trọng của bài toán sắp xếp 31 2.1.2. Sắp xếp trong và sắp xếp ngoài 31 2.1.3. Tổ chức dữ liệu và ngôn ngữ cài đặt 31 2.1.4. Thuật toán sắp xếp 32 2.2. Các phương pháp sắp xếp đơn giản 32 2.2.1. Sắp xếp chọn (Selection Sort) 32 2.2.2. Sắp xếp chèn (InsertionSort) 33 2.2.3. Sắp xếp nổi bọt(Bubble Sort) 35 2.3. Sắp xếp nhanh QUICK SORT 36 2.3.1. Ý tưởng 36 2.3.2. Thiết kế giải thuật 36 2.3.3. Đánh giá độ phức tạp 38 2.4. Sắp xếp kiểu vun đống (Heapsort) 39 2.4.1. Định nghĩa HEAP 39 2.4.2. Sắp xếp kiểu vun đống 40 1
- Giáo trình Lý thuyết thuật toán-Bộ môn Khoa học máy tính-2010 2.4.3. Độ phức tạp tính toán 40 2.5. Sắp xếp hòa nhập (Merge Sort) 43 2.5.1. Ý tưởng 43 2.5.2. Thiết kế giải thuật 44 2.5.3. Đánh giá độ phức tạp 46 2.6. Cấu trúc dữ liệu và giải thuật xử lý ngoài 46 2.6.1. Mô hình xử lý ngoài 46 2.6.2. Đánh giá các giải thuật xử lý ngoài 47 2.6.3. Sắp xêp ngoài - MergeSorting 47 2.6.4. Cải tiến sắp xếp trộn 51 2.6.5. Trộn nhiều đường 52 Chương 3: Kỹ thuật thiết kế thuật toán 54 3.1. Chia để trị 54 3.1.1. Nội dung 54 3.1.2. Một số bài toán áp dụng 55 3.2. Quy hoạch động (Dynamic) 58 3.2.1. Nội dung 58 3.2.2. Ví dụ áp dụng 59 3.3. Phương pháp tham lam (Greedy Method) 63 3.3.1. Bài toán tối ưu tổ hợp 63 3.3.2. Nội dung 64 3.4. Phương pháp nhánh cận (Branch- and- Bound) 68 3.4.1. Nội dung 68 3.4.2. Các bài toán áp dụng 69 Chương 4: Lý thuyết lập lịch 75 4.1. Vấn đề lập lịch tối ưu 75 4.1.1. Bài toán 75 4.1.2. Nhận xét 76 4.1.3. Tình hình giải bài toán lập lịch hiện nay 77 4.2. Phân lớp bài toán lập lịch dạng tĩnh 78 4.2.1. Thông tin về công việc 78 4.2.2. Quan hệ giữa các máy 78 4.2.3. Quan hệ giữa các công việc 79 4.2.4. Một số tiêu chuẩn tối ưu 80 4.2.5. Một số ví dụ 80 4.2.6. Một số thuật toán lập lịch 81 4.3. Một số bài toán lập lịch giải bằng thuật toán lập lịch tối 81 ưu nhanh 4.3.1. Hệ 1,n Cmax 81 4.3.2. Nhóm hệ 1, nLmax và 1, n max 83 T 4.3.3. Hệ 1,nri ≥ 0 max 85 C 4.4. Bài toán lập lịch gia công trên 2 máy, thuật toán Johnson 88 4.4.1. Bài toán 2; F i ≥ 0Cmax 88 r 4.4.2. Thiết kế thuật toán 88 4.4.3. Một số trường hợp riêng có thể dẫn về bài toán 2 máy 91 2
- Giáo trình Lý thuyết thuật toán-Bộ môn Khoa học máy tính-2010 Chương 1 KỸ THUẬT PHÂN TÍCH, ĐÁNH GIÁ THUẬT TOÁN 1.1. Khái niệm bài toán và độ phức tạp dữ liệu vào 1.1.1. Khái niệm bài toán - Thông thường một bài toán được cho dưới dạng sau: + Input: Các dữ liệu vào của bài toán. + Output: Các dữ liệu ra thoả mãn yêu cầu của bài toán. - Giải bài toán có nghĩa là xuất phát từ dữ liệu vào, thực hiện một dãy hữu hạn những thao tác có cơ sở khoa học thích hợp để tìm được dữ liệu ra (kết quả) theo yêu cầu của bài toán. 1.1.2. Độ phức tạp dữ liệu vào của bài toán Có hai quan niệm chủ yếu: Quan niệm 1(quan niệm đơn giản): Độ phức tạp dữ liệu vào của bài toán đựoc hiểu là số lượng dữ liệu vào của bài toán (kích thước của bài toán Quan niệm 2: Là tổng độ dài của mọi dữ liệu vào đã được mã hóa theo một cách nào đó. Ví dụ: Cho dãy số nguyên X={x1,x2,…,xn}. Tìm giá trị lớn nhất trong dãy? Bài toán được biểu diễn như sau: Input : Cho dãy số nguyên X= {x1,x2,…,xn}, số lượng n. Output: Tìm số lớn nhất Max của dãy X. - Theo quan niệm 1 : Kích thước của bài toán là (n+1) - Theo quan niệm 2 : Kích thước của bài toán là + Số tự nhiên xi theo mã nhị phân có độ dài là [log2xi]+1 độ dài VD: xi mã 3 11 [log23]+1=2 5 101 [log25]+1=3 n ∑ +Độ dài dữ liệu của bài toán trên là: [log2xi] +log2n+n+1 i =1 1.2. Các mô hình tính toán Thông tường người ta xét đến 2 mô hình tính toán thông dụng: - Mô hình lí thuyết: Máy Turing. 3
- Giáo trình Lý thuyết thuật toán-Bộ môn Khoa học máy tính-2010 - Mô hình ứng dụng: Máy xử lý thuật toán viết bằng ngôn ngữ tựa Algol ( các ngôn ngữ lập trình bậc cao). 1.2.1. Máy Turing a) Câú tạo: + Bộ nhớ: Gồm một băng tuyến tính vô hạn ở đầu phải, chia thành các ô nhớ, mỗi ô chứa được một kí hiệu nguyên tố. n ô trái (n ≥ 0) được ghi các kí hiệu của xâu vào, phần còn lại ở bên phải được lấp đầy bởi một kí hiệu đặc biệt gọi là kí hiệu trắng B. + Bộ điều khiển: Có hữu hạn trạng thái, tại mỗi thời điểm có một trạng thái xác định. + Một đầu đọc/ viết, nó cho phép tại một thời điểm có thể đọc hay viết ở một ô trên băng. b) Hoạt động: Theo thời gian “rời rạc”, được điều khiển bởi bộ điều khiển. Tùy thuộc vào trạng thái hiện tại và kí hiệu đọc được trên băng mà nó tiến hành một bước chuyển gồm đồng thời 3 động tác sau: 1. Đổi trạng thái trên bộ điều khiển 2. Viết một kí hiệu lên ô đang đọc 3. Chuyển đầu đọc viết sang phải hay trái một ô theo quy định của hàm chuyển. Một cách hình thức, xem máy Turing là một bộ T = (∑, Q, Γ, δ , q0, B,F) Trong đó : Q: Tập hữu hạn các trạng thái. Γ : Tập hữu hạn các kí hiệu trên băng B : Một kí hiệu đặc biệt thuộc Γ gọi là kí hiệu trắng. ∑ : Tập con của Γ , không chứa B, được gọi là bộ chữ vào(kí hiệu kết thúc) q0: Trạng thái đầu F⊆ Q: Tập trạng thái kết thúc. δ : Hàm chuyển trạng thái δ : Q x Γ Q x Γ x {L,R} L, R là các trạng thái: trái, phải 4
- Giáo trình Lý thuyết thuật toán-Bộ môn Khoa học máy tính-2010 Một hình trạng của máy Turing là một xâu có dạng #γ 1q γ 2#, trong đó # là một ký hiệu không thuộc Γ , # gọi là ký hiệu mút ; còn γ 1, γ 2 ∈Γ*, q ∈Q. Hình trạng đầu là #q0w # với w∈∑* Ví dụ 1: Thời điểm t XZ C D p Thời điểm t+1 YZ C1 D1 q (sang phải) Hình 1: Một bước hoạt động của máy Turing Tại thời điểm t máy Turing ở trạng thái p, đầu đọc /viết nhòm vào ô nhớ có kí hiệu là X. Tại thời điểm tiếp theo t+1 (một đơn vị thời gian) máy ở trạng thái q, ký hiệu X đã thay bằng Y, đầu đọc/viết chuyển sang trái hoặc sang phải. δ: d∈{L,R} (p,X)→(q,Y,d) hay viết pX→qYd gọi là một mệnh lệnh của máy T, xâu kí tự CpXD gọi là một hình trạng của máy T. CpXD→C1qZD1 gọi là một bước chuyển hình trạng, nếu q∈F thì xem như quá trình xử lý kết thúc hay C1qZD1 là hình trạng cuối cùng. - Nếu δ là hàm đơn trị thì T được gọi là máy tất định(đơn định) - Nếu δ là hàm đa trị thì T được gọi là máy không tất định(không đơn định) - Đơn vị nhớ: Là ô nhớ chứa một kí hiệu, nếu dùng mã nhị phân thì đơn vị nhớ là 1 bit. - Đơn vị thời gian: Là thời gian để thực hiện một bước hoạt động cơ bản (bước chuyển hình trạng). Nhận xét: Máy Turing có cấu tạo cực kì đơn giản nhưng lại làm được mọi việc liên quan tới tính toán các phép tính. Từ mô hình này có thể định nghĩa ra phép cộng (mã hóa dạng nhị phân) bằng cách dịch chuyển đầu đọc 0, 1 và từ đó định nghĩa ra các phép tính khác. 5
- Giáo trình Lý thuyết thuật toán-Bộ môn Khoa học máy tính-2010 1.2.2. Máy xử lý thuật toán viết bằng ngôn ngữ tựa ALGOL - Đơn vị nhớ: Một ô nhớ chứa trọn vẹn một dữ liệu. - Đơn vị thời gian: Thời gian để thực hiện một phép tính cơ bản trong số học hay logic như cộng, trừ, nhân, chia, gán, so sánh… 1.3. Khái niệm thuật toán và độ phức tạp của thuật toán 1.3.1. Thuật toán(Algorithm) Thuật toán được hiểu đơn giản là một dãy hữu hạn các qui tắc. Với cấu tạo và hoạt động của máy Turing, ta có thể định nghĩa một cách hình thức thuật toán chính là một máy Turing. Ta đã có 2 mô hình tính toán là máy Turing và máy xử lý thuật toán viết bằng ngôn ngữ tựa ALGOL. Ứng với hai mô hình tính toán này có 2 cách biểu diễn thuật toán: + Thuật toán được biểu diễn bằng ngôn ngữ máy Turing. + Thuật toán được biểu diễn bằng ngôn ngữ tựa ALGOL. 1.3.2 Chi phí phải trả cho một quá trình tính toán và các khái niệm về độ phức tạp thuật toán 1.3.2.1. Chi phí phải trả cho một quá trình tính toán Thường quan tâm tới chi phí thời gian và chi phí không gian (bộ nhớ) - Chi phí thời gian của một quá trình tính toán là thời gian cần thiết để thực hiện một quá trình tính toán. + Với máy Turing: Chi phí thời gian là số bước chuyển hình trạng từ hình trạng đầu đến hình trạng kết thúc. + Với thuật toán tựa Algol: Chi phí thời gian là số các phép tính cơ bản cần thực hiện trong quá trình tính toán. - Chi phí không gian của một quá trình tính toán là số ô nhớ cần để thực hiện một quá trình tính toán. Gọi A là một thuật toán tương ứng với một mô hình tính toán Gọi e là bộ dữ liệu vào đã được mã hóa theo cách nào đó Khi đó thuật toán A tính trên dữ liệu e cần phải trả một giá nhất định bao gồm 2 giá: + tA(e) là giá thời gian + lA(e) là giá bộ nhớ Cùng một thuật toán A, xử lý trên các bộ dữ liệu khác nhau thì sẽ có giá khác nhau. Ví dụ 2: Cho dãy số nguyên S={x1,x2,…xn}, số phần tử n. 6
- Giáo trình Lý thuyết thuật toán-Bộ môn Khoa học máy tính-2010 Tìm số lớn nhất của dãy ? Bài toán được biểu diễn như sau. Input: Dãy số nguyên S={x1,x2,…xn}, n Ouput: Số lớn nhất Max=max{xi} của S. Thuật toán A: Begin Max:=x1; For i:=2 to n do If xi>Max then Max:=xi; End. * Xét bộ dữ liệu vào e1={4, 0, 9, 1, 5} lA(e1)=5+1+1+1=8 (số biến vào:6, số biến ra:1, số biến phụ:1) tA(e1)=5+1=6 vì thực hiện 1 phép tính max:=4 thực hiện 1 phép tính vì x2=0max=4 nên max:=9 thực hiện 1 phép tính x4=1
- Giáo trình Lý thuyết thuật toán-Bộ môn Khoa học máy tính-2010 Trong ví dụ trên TA(n) =1+2(n-1) = 2n-1. Độ phức tạp trung bình Là tổng số các độ phức tạp khác nhau ứng với các bộ dữ liệu chia cho tổng số. Độ phức tạp tiệm cận Thuật toán A với đầu vào n gọi là có độ phức tạp O(f(n)) nếu ∃ hằng số C, N0: TA(n) ≤ C.f(n) , ∀ n ≥ N0. Tức là TA(n) có tốc độ tăng là O(f(n)) Độ phức tạp đa thức(Polynomial) Thuật toán được gọi là có độ phức tạp đa thức nếu tồn tại đa thức P(n) mà TA(n) ≤ C.P(n) , ∀ n ≥ N0. Thuật toán đa thức Thuật toán được gọi là đa thức nếu độ phức tạp về thời gian trong trường hợp xấu nhất của nó là đa thức. Việc đánh giá đúng độ phức tạp của bài toán là một vấn đề hết sức phức tạp. Vì vậy người ta thường quan tâm đến việc đấnh giá độ phức tạp thời gian trong trường hợp xấu nhất của bài toán. Một số đơn vị đo tốc độ tăng: - O(1): Hầu hết các chỉ thị của chương trình đều được thực hiện một lần hay nhiều nhất chỉ một vài lần⇒Thời gian chạy của chương trình là hằng số. - O(logN): Thời gian chạy của chương trình là logarit, tức là thời gian chạy của chương trình tiến chậm khi N lớn dần. - O(N):Thời gian chạy là tuyến tính. Đây là tình huống tối ưu cho một thuật toán phải xử lý N dữ liệu nhập. - O(NlogN): Thời gian chạy tăng dần lên cho các thuật toán mà giải một bài toán bằng cách tách nó thành các bài toán con nhỏ hơn, sau đó tổ hợp các lời giải. - O(N2): Thời gian chạy là bậc 2, trường hợp này chỉ có ý nghĩa thực tế cho các bài toán tương đối nhỏ. Thời gian bình phương thường tăng dần trong các thuật toán phải xử lý tất cả các cặp phần tử dữ liệu (2 vòng lặp lồng nhau). - O(N3): Thuật toán xử lý các bộ ba của các phần tử dữ liệu (3 vòng lặp lồng nhau)⇒ ý nghĩa với các bài toán nhỏ. - O(2n) , O(n!), O(nn): Thời gian thực hiện thuật toán là rất lớn do tốc độ tăng của các hàm mũ. 1.4. Cách tính độ phức tạp 8
- Giáo trình Lý thuyết thuật toán-Bộ môn Khoa học máy tính-2010 1.4.1. Các quy tắc cơ bản a) Quy tắc cộng: Nếu T1(n) và T2(n) là thời gian thực hiện 2 chương trình P1, P2 và T1(n)=O(f(n)), T2(n)=O(g(n)) thì thời gian thực hiện của đoạn 2 chương trình đó nối tiếp nhau là T(n)=O(max(f(n),g(n)) Ví dụ: Lệnh gán x:=5 tốn một hằng thời gian ≈ O(1). Lệnh đọc dữ liệu READ(x) tốn một hằng ≈ O(1). Thời gian thực hiện cả 2 lệnh trên nối tiếp nhau là O(max(1,1))=O(1). b) Quy tắc nhân: Nếu T1(n) và T2(n) là thời gian thực hiện 2 đoạn chương trình P1, P2 và T1(n)=O(f(n)), T2(n)=O(g(n)) thì thời gian thực hiện của 2 đoạn chương trình đó lồng nhau là T(n)=O(f(n).g(n)). c) Quy tắc tổng quát để phân tích một chương trình - Thời gian thực hiện của mỗi lệnh gán, READ, WRITE là O(1) - Thời gian thực hiện của một chuỗi tuần tự các lệnh được xác định bằng quy tắc cộng⇒Thời gian này là thời gian thi hành một lệnh nào đó lâu nhất trong chuỗi lệnh. - Thời gian thực hiên cấu trúc IF là thời gian lớn nhất thực hiện câu lệnh sau THEN hoặc ELSE và thời gian kiểm tra điều kiện, thường thời gian kiểm tra điều kiện là O(1). - Thời gian thực hiện vòng lặp là tổng (trên tất cả các lần lặp) thời gian thực hiện thân vòng lặp. Nếu thời gian thực hiện thân vòng lặp không đổi thì thời gian thực hiện vòng lặp là tích số lần lặp với thời gian thực hiện thân vòng lặp. Ví dụ 3: Tính thời gian thực hiện đoạn chương trình: Begin {lặp n-1 lần}. 1. for i:=1 to n-1 do 2. for j:=n downto i+1 do {thực hiện (n-i)lần,mỗi lần O(1)⇒ 9
- Giáo trình Lý thuyết thuật toán-Bộ môn Khoa học máy tính-2010 O((n-i).1)=O(n-i). 3. if a[j-1]>a[j] then begin đổi chỗ (a[i],a[j]). 4. temp:=a[j-1]; O(1) 5. a[j-1]:=a[i]; 6. a[j]:=temp; end. End. n −1 n(n − 1) Độ phức tạp T(n)= ∑ (n − i ) = =O(n2). 2 i =1 Chú ý: Độ phức tạp thuật toán không chỉ phụ thuộc vào kích thước, thời gian mà còn phụ thuộc vào tính chất của dữ liệu vào. Ví dụ 4: Thuật toán sắp xếp dãy số nguyên tăng dần. Nếu dãy nhập vào đã có thứ tự thì thời gian thực hiện khác với khi nhập vào dãy chưa có thứ tự 1.4.2. Độ phức tạp của các chương trình đệ quy Với các chương trình chương trình đệ quy, trước hết ta cần thành lập các phương trình đệ quy, sau đó giải các phương trình đệ quy. Nghiệm của phương trình đệ quy là thời gian thực hiện chương trình đệ quy đó. a)Thành lập phương trình đệ quy: Phương trình đệ quy là một phương trình biểu diễn mối liên hệ giữa T(n) và T(k) trong đó T(n) là thời gian thực hiện với kích thước dữ liệu nhập là n, T(k) là thời gian thực hiện với kích thước dữ liệu nhập là k, k
- Giáo trình Lý thuyết thuật toán-Bộ môn Khoa học máy tính-2010 End. Gọi T(n) : Thời gian thực hiện tính n! T(n-1) : Thời gian thực hiện tính (n-1)! Thực hiện một lệnh gán Giai_thưa:=1 ⇒ O(1) ⇒ T(0)=C1 Trường hợp n = 0 Trường hợp n>0 ⇒ Gọi đệ quy Giai_thua(n-1) tốn T(n-1) thời gian Sau khi có kết quả của việc gọi đệ quy, phải nhân kết quả đó với n và gán cho Giai_thua, thời gian thực hiện phép nhân và phép gán là một hằng C2. Vậy ta có phương trình đệ quy là : nếu n=0 C1 T(n)= nếu n>0. T(n-1) + C2 *Ví dụ 6: Xét thủ tục Mergesort sau: Function Mergesort(L:List;n:Integer):List; Var L1,L2:List; Begin If n=1 then return(L) Else Begin Chia L thành 2 nửa L1,L2 ,mỗi nửa có độ dài n/2 Return(Merge(Mergesort(L1,n/2), Mergesort(L2,n/2)); End; End; Hàm Mergesort nhận một danh sách có độ dài n và trả về một danh sách đẫ được sắp xếp. Thủ tục Merge nhận 2 danh sách đẫ được sắp L1, L2 mỗi danh sách có độ dài n/2 trộn chúng lại với nhau để được một danh sách gồm n phần tử có thứ tự ⇒ Thời gian thực hiện Merge các danh sách có độ dài n/2 là O(n). - Gọi T(n) là thời gian thực hiện Mergesort 1 danh sách có n phần tử T(n/2) là thời gian thực hiện Mergesort 1 danh sách có n/2 phần tử Ta có phương trình đệ quy : 11
- Giáo trình Lý thuyết thuật toán-Bộ môn Khoa học máy tính-2010 nếu n =1 C1 T(n)= nếu n>1 2T(n/2) + C2n Trong đó: - C1 là thời gian phải tốn khi L có độ dài bằng 1 - Trường hợp n>1 , thời gian Mergesort được chia làm 2 phần: + Phần gọi đệ quy Mergesort 1 danh sách có độ dài n/2 là T(n/2) + Phần thứ 2 bao gồm phép thử n>1, chia danh sách thành 2 nửa và Merge, ba thao tác này có thời gian không đổi ⇒ Thời gian thực hiện là C2n b. Giải phương trình đệ quy: Phương pháp truy hồi: Dùng đệ quy để thay thế bất kì T(m) với m1 được thay thế bởi biểu thức của T(1). Vì T(1) luôn là hằng nên ta có công thức của T(n) chứa các số hạng chỉ liên quan tới n và các hằng số. *Ví dụ 7: Giải phương trình: nếu n=1 C1 T(n)= 2T(n/2) + C2n nếu n>1 n Ta có T ( n ) = 2T + C 2 n 2 n n n T ( n ) = 22T + C 2 + C 2 n = 4T + 2C 2 n 4 4 2 n n n T ( n ) = 42T + C 2 + 2C 2 n = 8T 8 + 3C 2 n 8 4 n T ( n ) = 2 i T i + iC 2 n 2 Giả sử n=2k quá trình suy rộng này sẽ kết thúc khi i=k ⇒ T ( n ) = 2 k T (1) + kC 2 n Vì 2k=n ⇒ k=logn và với T(1) = C1 ⇒ T ( n ) = C1 n + C 2 n log n ) Vậy thời gian thực hiện thuật toán là O(nlogn) 12
- Giáo trình Lý thuyết thuật toán-Bộ môn Khoa học máy tính-2010 Định lý: (Về nghiệm của phương trình truy hồi) Cho a, b, c nguyên, dương. Khi đó nghiệm của phương trình truy hồi: = 1 b Õ u nn T(n) = n aT( ) + bn Õ un > 1, = ck n n c Có dạng: O( n) nÕ u < c a n = c T(n) = O ( n log c n) Õ u a nl ca ) Õ u > c og O ( na 1.5. Thuật toán không đơn định đa thức(Nodeterministic Polynomial NP) Với nhiều bài toán tối ưu tổ hợp vẫn chưa tìm được các thuật toán đơn định chạy trong thời gian đa thức, trong khi đó nếu cho phép dùng thuật toán không đơn định thì lại dễ dàng chỉ ra các thuật toán chạy trong thời gian đa thức. Ta xét bài toán sau đây: Bài toán xếp balô 0-1(KNASPACK) - Input: 1 balô có thể tích B; n đồ vật có thể tích a1,a2,…,an . - Output: Tìm nhóm đồ vật đặt vừa khít balô. *Cách 1: Phương pháp Vét toàn bộ cần số phép thử các khả năng là: C n + C n + ...C n −1 + Cn ≈ 2n 1 2 n n Độ phức tạp tính toán là O(2n ). *Cách 2: Diễn tả thuật toán không đơn định ta cần dùng 3 hàm: - CHOICE(a1,a2,…an): Chọn một trong số n giá trị. - SUCCESS: Nếu có một điều kiện thỏa mãn. - FAILURE: Nếu điều kiện không thỏa mãn. Khi đó bài toán trên có thể diễn đạt như sau: ∑ ai = B . Liệu có thể tồn tại tập chỉ số T ⊂ {1,2,…,n} mà i∈T Thuật toán: For i:=1 to n do xi:= CHOICE({0,1}); {phép toán lựa chọn một trong 2 giá trị} n ∑x a if =B then SUCCESS i i i =1 else FAILURE; 13
- Giáo trình Lý thuyết thuật toán-Bộ môn Khoa học máy tính-2010 - Giá phải trả về thời gian : + Trường hợp SUCCESS: Thời gian ít nhất để thực hiện SUCCESS . + Trường hợp FAILURE: Chính là thời gian tối đa. Thuật toán trên trở thành không đơn định đa thức, số phép tính thực hiện là 2*n+2. Bài toán Xếp balô mở rộng (Tên trộm tham lam) Input: Một ba lô có thể tích B, n đồ vật có thể tích: a1, a2,…an , giá trị tương ứng của các đồ vật là: p1, p2,…pn ∑ ai ≤ b và ∑ p Ouput: Có tồn tại tập T ⊂ {1,2,…,n} sao cho đạt max ?. i i∈T i∈T Bài toán xếp balô giá trị nguyên: Input: Một ba lô có thể tích B, n đồ vật có thể tích: a1, a2,…an , giá trị tương ứng của các đồ vật là: p1, p2,…pn Số lượng mỗi loại đồ vật là không hạn chế, x i nguyên là số lượng loại đồ vật i. n n ∑ ai xi ≤ B và ∑ pi xi Ouput: Tìm nhóm đồ vật thoả mãn đạt max ?. i =1 i =1 Mối quan hệ về tính đa thức giữa mô hình Turing và mô hình tựa Algol Định lí 1: Thuật toán trên máy Turing là đa thức thì thuật toán trên tựa Algol tương ứng cũng là đa thức, ngược lại chưa chắc. Ví dụ 8: Tính S=2 2 . n x:=2; for i:=1 to n do x:=x*x; x2 Ta có i:=1 : x2 * x2 = x 2 i:=2 : 2 x4 * x4 = x 2 i:=3 : 3 … n −1 n −1 i:=n : x2 * x2 = x2 . n + Trên máy Turing : Dữ liệu vào 2 2 mã nhị phân là: [log2 2 2 ] +1 ≈ 2n , độ phức tạp n n là O(2n) + Thuật toán tựa Algol : Độ phức tạp 2n+1 ≈ O(n) . Định lí 2 : Nếu thuật toán tựa Algol là đa thức và trong thuật toán chỉ có các phép toán cơ bản( +, -, *, /, so sánh,gán, AND, OR…) và dữ liệu vào phải có độ phức tạp 14
- Giáo trình Lý thuyết thuật toán-Bộ môn Khoa học máy tính-2010 đa thức theo quan niệm 2(độ dài mã) thì thuật toán (trên máy Turing) tương ứng là đa thức. Ví dụ: Input: Dãy số a1,a2,…an, n. Output: Sắp xếp theo chiều giảm dần. For i:=1 to n do Begin j:=i; for k:=i+1 to n do if ak>aj then j:=k; TAM:=ai; ai:=aj; aj:=TAM; End; Độ phức tạp tính toán: - Dữ liệu: n+1 ≈ O(n). - Bộ nhớ: (n+1)+4=n+5 ≈ O(n) (vào) (i,j,k,tam) n −1 +4(n-1) =n2+3n-4 ≈ O(n2). - Thời gian: 2((n-1)+(n-2)+…+2+1)+4(n-1) = 2n. 2 ⇒ Thuật toán là đa thức ⇒ Thực tế giải được. 1.5.1. Sự phân lớp các bài toán. Với một bài toán cho trước có 2 khả năng xảy ra: + Không giải được hoặc + Giải được bằng thuật toán. - Trường hợp bài toán giải được bằng thuật toán cũng chia làm 2 loại: + Thực tế giải được: Được hiểu là thuật toán xử lý trong thời gian đủ nhanh, thực tế cho phép, đó là thuật toán có độ phức tạp thời gian là đa thức. +Thực tế khó giải: Được hiểu là thuật toán xử lý trong nhiều thời gian, thực tế khó chấp nhận, đó là thuật toán có độ phức tạp thời gian là trên đa thức (hàm mũ). Do đó, ta có sự phân lớp các bài toán do 2 tác giả Cook và Karp đề xuất năm 1970- 1971 như sau: - P : Là lớp các bài toán có thể giải được bằng thuật toán đơn định trong thời gian đa thức (Deterministic polynomial). 15
- Giáo trình Lý thuyết thuật toán-Bộ môn Khoa học máy tính-2010 Ví dụ: Bài toán về tính liên thông của đồ thị có thể giải đuợc nhờ thuật toán với thời gian tính là O(n2)⇒ Thuộc lớp P NP : Là lớp các bài toán có thể giải được bằng thuật toán không đơn định trong thời gian đa thức. Hay, là lớp các bài toán mà mọi nghiệm giả định đều có thể được kiểm chứng trong thời gian đa thức (Nondeterministic polynomial).. Ví dụ: Bài toán kiểm tra một dãy đỉnh của đồ thị G có là chu trình Hamilton hay không có thể thực hiện sau thời gian đa thức ⇒ Thuộc lớp NP ⇒ P ⊆ NP Nhưng hiện nay chưa chứng minh được P là tập con thực sự của NP, vấn đề P = NP? hiện là một trong số các vấn đề mở nổi tiếng nhất và cũng đắt giá nhất trong Toán học và trong Tin học lý thuyết. 1.5.2. Khái niệm “dẫn về được” (Phép quy dẫn): Cho hai bài toán A, B Định nghĩa1: Bài toán A được gọi là “dẫn về được” bài toán B sau thời gian đa thức nếu có một thuật toán đa thức để giải bài toán B thì cũng có một thuật toán đa thức để giải bài toán A. Nghĩa là: Bài toán B “khó hơn” bài toán A hay A “dễ hơn” B hay A là trường hợp riêng của B. Kí hiệu A ∝ B. Phép quy dẫn có tính chất bắc cầu: A ∝ B và B ∝ C ⇒ A ∝ C. Tư tưởng quy dẫn đã giải thích vai trò quan trọng của lớp bài toán P. Nếu ta có bài toán A thuộc lớp P và một bài toán B có thể quy dẫn về A, thế thì B cũng thuộc vào P. Nghĩa là P là đóng đối với phép quy dẫn. Định nghĩa 2 : Bài toán A được gọi là “khó tương đương” bài toán B nếu A ∝ B và B ∝ A. Kí hiệu A ~ B. 1.5.3 Lớp bài toán NP - khó (NP - hard) và NP - đầy đủ (NP – Complate) a) Bài toán quyết định: Bài toán quyết định là bài toán mà đầu ra chỉ có thể là “Yes” hoặc “No” (Đúng/sai, 0/1, chấp nhận/từ chối). Ví dụ: Bài toán về tính nguyên tố: ” Hỏi số nguyên n có là số nguyên tố hay không?”. Khi đó ta có n = 23 là bộ dữ liệu vào “Yes”, còn n = 24 là bộ dữ liệu vào “ No” của bài toán. b) Bài toán NP – Khó(NP – Hard) Bài toán A được gọi là NP- khó nếu như tồn tại thuật toán đa thức để giải bài toán A thì 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. 16
- Giáo trình Lý thuyết thuật toán-Bộ môn Khoa học máy tính-2010 Hay: A là NP – Khó nếu như B ∝ A, với mọi bài toán B ∈ NP Một cách không hình thức, có thể nói rằng nếu ta có thể giải được một cách hiệu quả một bài toán NP – Khó cụ thể thì ta cũng có thể giải hiệu quả bất kỳ bài toán nào trong NP bằng cách sử dụng thuật toán giải bài toán NP-Khó như là một chương trình con. c) Bài toán NP - đầy đủ(NP – complete, NPC) Một bài toán quyết định A được gọi là NP - đầy đủ nếu như i) A là bài toán trong NP, ii) Mọi bài toán trong NP đều có thể quy dẫn về A. Lưu ý: Khái niệm NP - đầy đủ đòi hỏi bài toán nhất thiết phải có dạng quyết định. Ta có bức tranh tạm thời đầy đủ về phân lớp các bài toán trên hình sau: Hình 2: Sự phân lớp các bài toán c) Phương pháp chứng minh một bài toán là NP - đầy đủ - Cách 1: Theo định nghĩa (rất khó). NP-khó C - Cách 2: áp dụng bổ đề sau: NP NP Bổ đề: Giả sử bài toán A là NP - đầy đủ, bài toán B thuộc NP và bài toán A quy dẫn về B. Khi đó bài toán B cũng là NP - đầy đủ. P Ví dụ 9: Bài toán xếp balô(KNASPACK) ∈ NPC ⇒ Chứng minh bài toán lập lịch ∈ NPC. °Bài toán lập lịch (Bài toán PHẠT): Input: Có n công việc xử lý trên một máy. ri: Thời điểm bắt đầu công việc xử lý i di : Hạn định hoàn thành công việc i. ti : Thời gian xử lý công việc i, ti ≤ di-ri. bi : Thời gian bắt đầu xử lý. ci : Thời gian kết thúc công việc i, ti=ci-bi 17
- Giáo trình Lý thuyết thuật toán-Bộ môn Khoa học máy tính-2010 nếu ci ≤ di , công việc i là xử lý đúng hạn. nếu ci>di , công việc i là xử lý quá hạn(bị phạt). wi : Tiền phạt. Output: Hãy sắp xếp các công việc theo một thứ tự nhất định để theo đó chờ đến lượt xử lý, sao cho lượng tiền phạt là ít nhất. 0 nếu ci ≤ di (đúng hạn) Kí hiệu Ui = 1 nếu ci>di (quá hạn) n ∑ UiWi → min Khi đó yêu cầu : i= 1 n Ta có thể viết bài toán trên ngắn gọn như sau : n 1 ∑ UiWi . Kí hiệu là PHẠT. i= 1 Bài toán này rõ ràng là giải được bằng phương pháp “vét toàn bộ”. Nhưng thực tế khó giải vì nó thuộc lớp NP_đầy đủ. Để chứng minh bài toán “PHẠT” là NP - đầy đủ, chỉ cần chứng minh rằng bài toán KNAPSACK ∝ PHẠT vì ta đã biết KNAPSACK là NP_đầy đủ. Nói một cách khác KNAPSACK là trường hợp riêng của PHẠT. Nhắc lại bài toán KNAPSACK: Input: n đồ vật với thể tích a1,a2,…an cần nhét vào balô có thể tích B. Output: Tìm nhóm đồ vật có thể nhét vừa khít balô trên. ∑ ai = B .) ( ∃ T ⊆ {1,2,…,n} mà i∈T a) Để chứng minh KNAPSACK ∝ PHẠT trước hết ta diễn đạt nó bằng ngôn ngữ của bài toán PHẠT. Cụ thể mỗi vật i ở KNAPSACK được xem là một công việc trong PHẠT, chúng đồng thời được nhập vào hệ thống. Mọi công việc có hạn định như nhau và bằng B. Thời gian ti thực hiện công việc i bằng tiền phạt wi và bằng thể tích ai của vật. Tóm lại ta có thể biểu diễn bài toán như sau: - n công việc đồng thời được xử lý ri =0, ∀ i=1,2,…,n. Input: - mỗi công việc i (1 ≤ i ≤ n ) được biết di=B, ti=wi=ai, ∀ i=1,2,…,n. - máy làm việc liên tục cho đến khi mọi công việc được xử lý xong. - tại mỗi thời điểm máy chỉ xử lý được một công việc. - khi đang xử lý công việc i, không được phép ngắt nó để thực hiện một công việc khác. 18
- Giáo trình Lý thuyết thuật toán-Bộ môn Khoa học máy tính-2010 Output: Hãy lập lịch để máy xử lý các công việc sao cho lượng tiền phạt là ít nhất n ∑ UiWi là nhỏ nhất. i= 1 b) Chứng minh: Giải được PHẠT bằng thuật toán đơn định đa thức thì cũng giải được KNAPSACK bằng thuật toán đơn định đa thức và ngược lại. n n ∑ ∑ °Giả sử giải được PHẠT tức là lịch biểu mà WiUi là nhỏ nhất, vậy thì: i =1 i =1 ∑b =∑a =∑w n WiUi= ∑ ai -b. i i i i =1 ri=0 b di=b -b UiWi = ∑ ai = ∑ ai -b n n ∑ Suy ra ∃ S ⊆ {1,2,…,n} mà i∈S i= 1 i =1 Hay b= ∑ ai - ∑ ai = ∑ ai với T={1,2,…,n}- S. n Như vậy KNAPSACK đã giải i∈T i∈S i =1 được. ∑ ai = b °Ngược lại, giả sử KNAPSACK đã giải được, tức là ∃ T ⊆ {1,2,…,n} mà i∈T hay ∑ ai = ∑ a - ∑ a =b, như vậy ∑ a - ∑ n n n n n UiWi = ∑ ai -b , đây là lượng ∑ UiWi =b ⇒ i i i i∈T i∈S i =1 i =1 i= 1 i= 1 i =1 tiền nhỏ nhất và PHẠT đã giải được. n ∑a *Chú ý: Nếu tất cả n công việc đều quá hạn thì lượng tiền phạt lớn nhất là . i i =1 d) Một số bài toán đã được chứng minh là NP – khó , NP - đầy đủ Để chứng minh một bài toán nào đó là NP-đầy đủ (NP-khó) công việc khó khăn nhất là tìm được một bài toán NP-đầy đủ có thể quy dẫn về nó. Do đó ta cần biết thêm về những bài toán đẫ được chứng minh là NP-đầy đủ, cho đến nay danh mục các bài toán NPC trong các lĩnh vực đa dạng :Logic Bool, đồ thị, số học, lập lịch, trò chơi, otomat…đã lên đến hàng nghìn . Sau đây là một số bài toán đã được chứng minh là NPC: Bµi to¸n 3SAT. 19
CÓ THỂ BẠN MUỐN DOWNLOAD
-
Giáo trình Lý thuyết xác suất và thống kê toán - ĐH Trà Vinh
145 p | 4094 | 1133
-
Giáo trình Lý thuyết thống kê - ĐH Kinh tế Tp.HCM
167 p | 1073 | 274
-
Giáo trình Lý thuyết thống kê - Ths. Đồng Thị Vân Hồng
89 p | 543 | 210
-
Giáo trình lý thuyết thống kê - Nguyễn Hoàng Oanh (chủ biên), Nguyễn Văn Thạch
70 p | 521 | 194
-
Giáo trình về lý thuyết thông tin
228 p | 174 | 97
-
lý thuyết tính toán
0 p | 189 | 88
-
Giáo trình Lý thuyết thống kê và phân tích dự báo: Phần 1 - Chu Văn Tuấn
194 p | 123 | 71
-
Giáo trình Lý thuyết thống kê và phân tích dự báo: Phần 2 - Chu Văn Tuấn
188 p | 87 | 47
-
Giáo trình Lý thuyết xác suất và thống kê toán: Phần 1 - Hoàng Ngọc Nhậm
95 p | 68 | 41
-
Giáo trình Lý thuyết xác suất và thống kê toán: Phần 2 - Hoàng Ngọc Nhậm
149 p | 44 | 31
-
Giáo trình Lý thuyết số
139 p | 32 | 25
-
Giáo trình Lý thuyết thống kê: Phần 2
281 p | 28 | 15
-
Giáo trình Lý thuyết thống kê: Phần 1
238 p | 27 | 15
-
Giáo trình Lý thuyết nhóm (Dùng cho sinh viên ngành Toán học): Phần 1
27 p | 15 | 11
-
Giáo trình Lý thuyết xác suất và thống kê toán học - Phần 1
91 p | 19 | 8
-
Giáo trình lý thuyết đồ thị - Bài 13
0 p | 30 | 6
-
Giáo trình lý thuyết đồ thị - Bài 2
0 p | 25 | 5
-
Giáo trình Lý thuyết thống kê: Phần 1 (dùng cho Trung cấp nghề và Cao đẳng nghề)
29 p | 1 | 0

markdown:
# Giáo trình Lý thuyết thuật toán
Chia sẻ: Phan Thi Ngoc Giau | Ngày: | Loại File: PDF | Số trang:92
lượt xem 58
download
![](http://image.tailieu.vn/document/thumbnail/2012/20120213/augi16/80x100/2351338887639.jpg)
##
Giáo trình Lý thuyết thuật toán
[Vui lòng tải xuống để xem tài liệu đầy đủ](javascript:void(0);)
Download
![](images/down16x21.png)
Giải bài toán có nghĩa là xuất phát từ dữ liệu vào, thực hiện một dãy hữu hạn những thao tác có có sở khoa học thích hợp để tìm được dữ liệu ra theo yêu cầu của bài toán. Độ phức tạp dữ liệu vào của bài toán được hiểu là số lượng dữ liệu vào các bài toán.
![](images/graphics/blank.gif)
Bình luận(0)
[Đăng nhập để gửi bình luận!](javascript:void(0);)
##
Nội dung Text: Giáo trình Lý thuyết thuật toán
- Giáo trình Lý thuyết thuật toán
- Giáo trình Lý thuyết thuật toán-Bộ môn Khoa học máy tính-2010 MỤC LỤC Nội dung Trang Chương 1: Kỹ thuật phân tích đánh giá thuật toán 4 1.1. Khái niệm bài toán và độ phức tạp dữ liệu vào 4 1.1.1. Khái niệm bài toán 4 1.1.2. Độ phức tạp dữ liệu vào của bài toán 4 1.2. Các mô hình tính toán 4 1.2.1. Máy Turing 5 1.2.2. Máy xử lý thuật toán viết bằng ngôn ngữ tựa ALGOL 7 1.3. Khái niệm thuật toán và độ phức tạp của thuật toán 7 1.3.1. Thuật toán(Algorithm) 7 1.3.2 Chi phí phải trả cho một quá trình tính toán và các khái 7 niệm về độ phức tạp thuật toán 1.4. Cách tính độ phức tạp 10 1.4.1. Các quy tắc cơ bản 10 1.4.2. Độ phức tạp của các chương trình đệ quy 11 1.5. Thuật toán không đơn định đa thức(Nodeterministic 14 Polynomial NP) 1.5.1. Sự phân lớp các bài toán. 16 1.5.2. Khái niệm “dẫn về được” (Phép quy dẫn) 17 1.5.3 Lớp bài toán NP - khó (NP - hard) và NP - đầy đủ (NP – 18 Complate) 1.6. Thuật toán xấp xỉ (Heuristic) 22 1.6.1. Các khái niệm 22 1.6.2. Thuật toán ε - xấp xỉ tuyệt đối 24 1.6.3.Thuật toán ε - xấp xỉ 26 1.7. Chứng minh tính đúng đắn của thuật toán 28 1.7.1. Ví dụ: 28 1.7.2. Phương pháp thử 28 1.7.3. Kiểm chứng tính đúng đắn 29 Chương 2: Các thuật toán Sắp xếp 31 2.1. Bài toán sắp xếp 31 2.1.1. Tầm quan trọng của bài toán sắp xếp 31 2.1.2. Sắp xếp trong và sắp xếp ngoài 31 2.1.3. Tổ chức dữ liệu và ngôn ngữ cài đặt 31 2.1.4. Thuật toán sắp xếp 32 2.2. Các phương pháp sắp xếp đơn giản 32 2.2.1. Sắp xếp chọn (Selection Sort) 32 2.2.2. Sắp xếp chèn (InsertionSort) 33 2.2.3. Sắp xếp nổi bọt(Bubble Sort) 35 2.3. Sắp xếp nhanh QUICK SORT 36 2.3.1. Ý tưởng 36 2.3.2. Thiết kế giải thuật 36 2.3.3. Đánh giá độ phức tạp 38 2.4. Sắp xếp kiểu vun đống (Heapsort) 39 2.4.1. Định nghĩa HEAP 39 2.4.2. Sắp xếp kiểu vun đống 40 1
- Giáo trình Lý thuyết thuật toán-Bộ môn Khoa học máy tính-2010 2.4.3. Độ phức tạp tính toán 40 2.5. Sắp xếp hòa nhập (Merge Sort) 43 2.5.1. Ý tưởng 43 2.5.2. Thiết kế giải thuật 44 2.5.3. Đánh giá độ phức tạp 46 2.6. Cấu trúc dữ liệu và giải thuật xử lý ngoài 46 2.6.1. Mô hình xử lý ngoài 46 2.6.2. Đánh giá các giải thuật xử lý ngoài 47 2.6.3. Sắp xêp ngoài - MergeSorting 47 2.6.4. Cải tiến sắp xếp trộn 51 2.6.5. Trộn nhiều đường 52 Chương 3: Kỹ thuật thiết kế thuật toán 54 3.1. Chia để trị 54 3.1.1. Nội dung 54 3.1.2. Một số bài toán áp dụng 55 3.2. Quy hoạch động (Dynamic) 58 3.2.1. Nội dung 58 3.2.2. Ví dụ áp dụng 59 3.3. Phương pháp tham lam (Greedy Method) 63 3.3.1. Bài toán tối ưu tổ hợp 63 3.3.2. Nội dung 64 3.4. Phương pháp nhánh cận (Branch- and- Bound) 68 3.4.1. Nội dung 68 3.4.2. Các bài toán áp dụng 69 Chương 4: Lý thuyết lập lịch 75 4.1. Vấn đề lập lịch tối ưu 75 4.1.1. Bài toán 75 4.1.2. Nhận xét 76 4.1.3. Tình hình giải bài toán lập lịch hiện nay 77 4.2. Phân lớp bài toán lập lịch dạng tĩnh 78 4.2.1. Thông tin về công việc 78 4.2.2. Quan hệ giữa các máy 78 4.2.3. Quan hệ giữa các công việc 79 4.2.4. Một số tiêu chuẩn tối ưu 80 4.2.5. Một số ví dụ 80 4.2.6. Một số thuật toán lập lịch 81 4.3. Một số bài toán lập lịch giải bằng thuật toán lập lịch tối 81 ưu nhanh 4.3.1. Hệ 1,n Cmax 81 4.3.2. Nhóm hệ 1, nLmax và 1, n max 83 T 4.3.3. Hệ 1,nri ≥ 0 max 85 C 4.4. Bài toán lập lịch gia công trên 2 máy, thuật toán Johnson 88 4.4.1. Bài toán 2; F i ≥ 0Cmax 88 r 4.4.2. Thiết kế thuật toán 88 4.4.3. Một số trường hợp riêng có thể dẫn về bài toán 2 máy 91 2
- Giáo trình Lý thuyết thuật toán-Bộ môn Khoa học máy tính-2010 Chương 1 KỸ THUẬT PHÂN TÍCH, ĐÁNH GIÁ THUẬT TOÁN 1.1. Khái niệm bài toán và độ phức tạp dữ liệu vào 1.1.1. Khái niệm bài toán - Thông thường một bài toán được cho dưới dạng sau: + Input: Các dữ liệu vào của bài toán. + Output: Các dữ liệu ra thoả mãn yêu cầu của bài toán. - Giải bài toán có nghĩa là xuất phát từ dữ liệu vào, thực hiện một dãy hữu hạn những thao tác có cơ sở khoa học thích hợp để tìm được dữ liệu ra (kết quả) theo yêu cầu của bài toán. 1.1.2. Độ phức tạp dữ liệu vào của bài toán Có hai quan niệm chủ yếu: Quan niệm 1(quan niệm đơn giản): Độ phức tạp dữ liệu vào của bài toán đựoc hiểu là số lượng dữ liệu vào của bài toán (kích thước của bài toán Quan niệm 2: Là tổng độ dài của mọi dữ liệu vào đã được mã hóa theo một cách nào đó. Ví dụ: Cho dãy số nguyên X={x1,x2,…,xn}. Tìm giá trị lớn nhất trong dãy? Bài toán được biểu diễn như sau: Input : Cho dãy số nguyên X= {x1,x2,…,xn}, số lượng n. Output: Tìm số lớn nhất Max của dãy X. - Theo quan niệm 1 : Kích thước của bài toán là (n+1) - Theo quan niệm 2 : Kích thước của bài toán là + Số tự nhiên xi theo mã nhị phân có độ dài là [log2xi]+1 độ dài VD: xi mã 3 11 [log23]+1=2 5 101 [log25]+1=3 n ∑ +Độ dài dữ liệu của bài toán trên là: [log2xi] +log2n+n+1 i =1 1.2. Các mô hình tính toán Thông tường người ta xét đến 2 mô hình tính toán thông dụng: - Mô hình lí thuyết: Máy Turing. 3
- Giáo trình Lý thuyết thuật toán-Bộ môn Khoa học máy tính-2010 - Mô hình ứng dụng: Máy xử lý thuật toán viết bằng ngôn ngữ tựa Algol ( các ngôn ngữ lập trình bậc cao). 1.2.1. Máy Turing a) Câú tạo: + Bộ nhớ: Gồm một băng tuyến tính vô hạn ở đầu phải, chia thành các ô nhớ, mỗi ô chứa được một kí hiệu nguyên tố. n ô trái (n ≥ 0) được ghi các kí hiệu của xâu vào, phần còn lại ở bên phải được lấp đầy bởi một kí hiệu đặc biệt gọi là kí hiệu trắng B. + Bộ điều khiển: Có hữu hạn trạng thái, tại mỗi thời điểm có một trạng thái xác định. + Một đầu đọc/ viết, nó cho phép tại một thời điểm có thể đọc hay viết ở một ô trên băng. b) Hoạt động: Theo thời gian “rời rạc”, được điều khiển bởi bộ điều khiển. Tùy thuộc vào trạng thái hiện tại và kí hiệu đọc được trên băng mà nó tiến hành một bước chuyển gồm đồng thời 3 động tác sau: 1. Đổi trạng thái trên bộ điều khiển 2. Viết một kí hiệu lên ô đang đọc 3. Chuyển đầu đọc viết sang phải hay trái một ô theo quy định của hàm chuyển. Một cách hình thức, xem máy Turing là một bộ T = (∑, Q, Γ, δ , q0, B,F) Trong đó : Q: Tập hữu hạn các trạng thái. Γ : Tập hữu hạn các kí hiệu trên băng B : Một kí hiệu đặc biệt thuộc Γ gọi là kí hiệu trắng. ∑ : Tập con của Γ , không chứa B, được gọi là bộ chữ vào(kí hiệu kết thúc) q0: Trạng thái đầu F⊆ Q: Tập trạng thái kết thúc. δ : Hàm chuyển trạng thái δ : Q x Γ Q x Γ x {L,R} L, R là các trạng thái: trái, phải 4
- Giáo trình Lý thuyết thuật toán-Bộ môn Khoa học máy tính-2010 Một hình trạng của máy Turing là một xâu có dạng #γ 1q γ 2#, trong đó # là một ký hiệu không thuộc Γ , # gọi là ký hiệu mút ; còn γ 1, γ 2 ∈Γ*, q ∈Q. Hình trạng đầu là #q0w # với w∈∑* Ví dụ 1: Thời điểm t XZ C D p Thời điểm t+1 YZ C1 D1 q (sang phải) Hình 1: Một bước hoạt động của máy Turing Tại thời điểm t máy Turing ở trạng thái p, đầu đọc /viết nhòm vào ô nhớ có kí hiệu là X. Tại thời điểm tiếp theo t+1 (một đơn vị thời gian) máy ở trạng thái q, ký hiệu X đã thay bằng Y, đầu đọc/viết chuyển sang trái hoặc sang phải. δ: d∈{L,R} (p,X)→(q,Y,d) hay viết pX→qYd gọi là một mệnh lệnh của máy T, xâu kí tự CpXD gọi là một hình trạng của máy T. CpXD→C1qZD1 gọi là một bước chuyển hình trạng, nếu q∈F thì xem như quá trình xử lý kết thúc hay C1qZD1 là hình trạng cuối cùng. - Nếu δ là hàm đơn trị thì T được gọi là máy tất định(đơn định) - Nếu δ là hàm đa trị thì T được gọi là máy không tất định(không đơn định) - Đơn vị nhớ: Là ô nhớ chứa một kí hiệu, nếu dùng mã nhị phân thì đơn vị nhớ là 1 bit. - Đơn vị thời gian: Là thời gian để thực hiện một bước hoạt động cơ bản (bước chuyển hình trạng). Nhận xét: Máy Turing có cấu tạo cực kì đơn giản nhưng lại làm được mọi việc liên quan tới tính toán các phép tính. Từ mô hình này có thể định nghĩa ra phép cộng (mã hóa dạng nhị phân) bằng cách dịch chuyển đầu đọc 0, 1 và từ đó định nghĩa ra các phép tính khác. 5
- Giáo trình Lý thuyết thuật toán-Bộ môn Khoa học máy tính-2010 1.2.2. Máy xử lý thuật toán viết bằng ngôn ngữ tựa ALGOL - Đơn vị nhớ: Một ô nhớ chứa trọn vẹn một dữ liệu. - Đơn vị thời gian: Thời gian để thực hiện một phép tính cơ bản trong số học hay logic như cộng, trừ, nhân, chia, gán, so sánh… 1.3. Khái niệm thuật toán và độ phức tạp của thuật toán 1.3.1. Thuật toán(Algorithm) Thuật toán được hiểu đơn giản là một dãy hữu hạn các qui tắc. Với cấu tạo và hoạt động của máy Turing, ta có thể định nghĩa một cách hình thức thuật toán chính là một máy Turing. Ta đã có 2 mô hình tính toán là máy Turing và máy xử lý thuật toán viết bằng ngôn ngữ tựa ALGOL. Ứng với hai mô hình tính toán này có 2 cách biểu diễn thuật toán: + Thuật toán được biểu diễn bằng ngôn ngữ máy Turing. + Thuật toán được biểu diễn bằng ngôn ngữ tựa ALGOL. 1.3.2 Chi phí phải trả cho một quá trình tính toán và các khái niệm về độ phức tạp thuật toán 1.3.2.1. Chi phí phải trả cho một quá trình tính toán Thường quan tâm tới chi phí thời gian và chi phí không gian (bộ nhớ) - Chi phí thời gian của một quá trình tính toán là thời gian cần thiết để thực hiện một quá trình tính toán. + Với máy Turing: Chi phí thời gian là số bước chuyển hình trạng từ hình trạng đầu đến hình trạng kết thúc. + Với thuật toán tựa Algol: Chi phí thời gian là số các phép tính cơ bản cần thực hiện trong quá trình tính toán. - Chi phí không gian của một quá trình tính toán là số ô nhớ cần để thực hiện một quá trình tính toán. Gọi A là một thuật toán tương ứng với một mô hình tính toán Gọi e là bộ dữ liệu vào đã được mã hóa theo cách nào đó Khi đó thuật toán A tính trên dữ liệu e cần phải trả một giá nhất định bao gồm 2 giá: + tA(e) là giá thời gian + lA(e) là giá bộ nhớ Cùng một thuật toán A, xử lý trên các bộ dữ liệu khác nhau thì sẽ có giá khác nhau. Ví dụ 2: Cho dãy số nguyên S={x1,x2,…xn}, số phần tử n. 6
- Giáo trình Lý thuyết thuật toán-Bộ môn Khoa học máy tính-2010 Tìm số lớn nhất của dãy ? Bài toán được biểu diễn như sau. Input: Dãy số nguyên S={x1,x2,…xn}, n Ouput: Số lớn nhất Max=max{xi} của S. Thuật toán A: Begin Max:=x1; For i:=2 to n do If xi>Max then Max:=xi; End. * Xét bộ dữ liệu vào e1={4, 0, 9, 1, 5} lA(e1)=5+1+1+1=8 (số biến vào:6, số biến ra:1, số biến phụ:1) tA(e1)=5+1=6 vì thực hiện 1 phép tính max:=4 thực hiện 1 phép tính vì x2=0max=4 nên max:=9 thực hiện 1 phép tính x4=1
- Giáo trình Lý thuyết thuật toán-Bộ môn Khoa học máy tính-2010 Trong ví dụ trên TA(n) =1+2(n-1) = 2n-1. Độ phức tạp trung bình Là tổng số các độ phức tạp khác nhau ứng với các bộ dữ liệu chia cho tổng số. Độ phức tạp tiệm cận Thuật toán A với đầu vào n gọi là có độ phức tạp O(f(n)) nếu ∃ hằng số C, N0: TA(n) ≤ C.f(n) , ∀ n ≥ N0. Tức là TA(n) có tốc độ tăng là O(f(n)) Độ phức tạp đa thức(Polynomial) Thuật toán được gọi là có độ phức tạp đa thức nếu tồn tại đa thức P(n) mà TA(n) ≤ C.P(n) , ∀ n ≥ N0. Thuật toán đa thức Thuật toán được gọi là đa thức nếu độ phức tạp về thời gian trong trường hợp xấu nhất của nó là đa thức. Việc đánh giá đúng độ phức tạp của bài toán là một vấn đề hết sức phức tạp. Vì vậy người ta thường quan tâm đến việc đấnh giá độ phức tạp thời gian trong trường hợp xấu nhất của bài toán. Một số đơn vị đo tốc độ tăng: - O(1): Hầu hết các chỉ thị của chương trình đều được thực hiện một lần hay nhiều nhất chỉ một vài lần⇒Thời gian chạy của chương trình là hằng số. - O(logN): Thời gian chạy của chương trình là logarit, tức là thời gian chạy của chương trình tiến chậm khi N lớn dần. - O(N):Thời gian chạy là tuyến tính. Đây là tình huống tối ưu cho một thuật toán phải xử lý N dữ liệu nhập. - O(NlogN): Thời gian chạy tăng dần lên cho các thuật toán mà giải một bài toán bằng cách tách nó thành các bài toán con nhỏ hơn, sau đó tổ hợp các lời giải. - O(N2): Thời gian chạy là bậc 2, trường hợp này chỉ có ý nghĩa thực tế cho các bài toán tương đối nhỏ. Thời gian bình phương thường tăng dần trong các thuật toán phải xử lý tất cả các cặp phần tử dữ liệu (2 vòng lặp lồng nhau). - O(N3): Thuật toán xử lý các bộ ba của các phần tử dữ liệu (3 vòng lặp lồng nhau)⇒ ý nghĩa với các bài toán nhỏ. - O(2n) , O(n!), O(nn): Thời gian thực hiện thuật toán là rất lớn do tốc độ tăng của các hàm mũ. 1.4. Cách tính độ phức tạp 8
- Giáo trình Lý thuyết thuật toán-Bộ môn Khoa học máy tính-2010 1.4.1. Các quy tắc cơ bản a) Quy tắc cộng: Nếu T1(n) và T2(n) là thời gian thực hiện 2 chương trình P1, P2 và T1(n)=O(f(n)), T2(n)=O(g(n)) thì thời gian thực hiện của đoạn 2 chương trình đó nối tiếp nhau là T(n)=O(max(f(n),g(n)) Ví dụ: Lệnh gán x:=5 tốn một hằng thời gian ≈ O(1). Lệnh đọc dữ liệu READ(x) tốn một hằng ≈ O(1). Thời gian thực hiện cả 2 lệnh trên nối tiếp nhau là O(max(1,1))=O(1). b) Quy tắc nhân: Nếu T1(n) và T2(n) là thời gian thực hiện 2 đoạn chương trình P1, P2 và T1(n)=O(f(n)), T2(n)=O(g(n)) thì thời gian thực hiện của 2 đoạn chương trình đó lồng nhau là T(n)=O(f(n).g(n)). c) Quy tắc tổng quát để phân tích một chương trình - Thời gian thực hiện của mỗi lệnh gán, READ, WRITE là O(1) - Thời gian thực hiện của một chuỗi tuần tự các lệnh được xác định bằng quy tắc cộng⇒Thời gian này là thời gian thi hành một lệnh nào đó lâu nhất trong chuỗi lệnh. - Thời gian thực hiên cấu trúc IF là thời gian lớn nhất thực hiện câu lệnh sau THEN hoặc ELSE và thời gian kiểm tra điều kiện, thường thời gian kiểm tra điều kiện là O(1). - Thời gian thực hiện vòng lặp là tổng (trên tất cả các lần lặp) thời gian thực hiện thân vòng lặp. Nếu thời gian thực hiện thân vòng lặp không đổi thì thời gian thực hiện vòng lặp là tích số lần lặp với thời gian thực hiện thân vòng lặp. Ví dụ 3: Tính thời gian thực hiện đoạn chương trình: Begin {lặp n-1 lần}. 1. for i:=1 to n-1 do 2. for j:=n downto i+1 do {thực hiện (n-i)lần,mỗi lần O(1)⇒ 9
- Giáo trình Lý thuyết thuật toán-Bộ môn Khoa học máy tính-2010 O((n-i).1)=O(n-i). 3. if a[j-1]>a[j] then begin đổi chỗ (a[i],a[j]). 4. temp:=a[j-1]; O(1) 5. a[j-1]:=a[i]; 6. a[j]:=temp; end. End. n −1 n(n − 1) Độ phức tạp T(n)= ∑ (n − i ) = =O(n2). 2 i =1 Chú ý: Độ phức tạp thuật toán không chỉ phụ thuộc vào kích thước, thời gian mà còn phụ thuộc vào tính chất của dữ liệu vào. Ví dụ 4: Thuật toán sắp xếp dãy số nguyên tăng dần. Nếu dãy nhập vào đã có thứ tự thì thời gian thực hiện khác với khi nhập vào dãy chưa có thứ tự 1.4.2. Độ phức tạp của các chương trình đệ quy Với các chương trình chương trình đệ quy, trước hết ta cần thành lập các phương trình đệ quy, sau đó giải các phương trình đệ quy. Nghiệm của phương trình đệ quy là thời gian thực hiện chương trình đệ quy đó. a)Thành lập phương trình đệ quy: Phương trình đệ quy là một phương trình biểu diễn mối liên hệ giữa T(n) và T(k) trong đó T(n) là thời gian thực hiện với kích thước dữ liệu nhập là n, T(k) là thời gian thực hiện với kích thước dữ liệu nhập là k, k
- Giáo trình Lý thuyết thuật toán-Bộ môn Khoa học máy tính-2010 End. Gọi T(n) : Thời gian thực hiện tính n! T(n-1) : Thời gian thực hiện tính (n-1)! Thực hiện một lệnh gán Giai_thưa:=1 ⇒ O(1) ⇒ T(0)=C1 Trường hợp n = 0 Trường hợp n>0 ⇒ Gọi đệ quy Giai_thua(n-1) tốn T(n-1) thời gian Sau khi có kết quả của việc gọi đệ quy, phải nhân kết quả đó với n và gán cho Giai_thua, thời gian thực hiện phép nhân và phép gán là một hằng C2. Vậy ta có phương trình đệ quy là : nếu n=0 C1 T(n)= nếu n>0. T(n-1) + C2 *Ví dụ 6: Xét thủ tục Mergesort sau: Function Mergesort(L:List;n:Integer):List; Var L1,L2:List; Begin If n=1 then return(L) Else Begin Chia L thành 2 nửa L1,L2 ,mỗi nửa có độ dài n/2 Return(Merge(Mergesort(L1,n/2), Mergesort(L2,n/2)); End; End; Hàm Mergesort nhận một danh sách có độ dài n và trả về một danh sách đẫ được sắp xếp. Thủ tục Merge nhận 2 danh sách đẫ được sắp L1, L2 mỗi danh sách có độ dài n/2 trộn chúng lại với nhau để được một danh sách gồm n phần tử có thứ tự ⇒ Thời gian thực hiện Merge các danh sách có độ dài n/2 là O(n). - Gọi T(n) là thời gian thực hiện Mergesort 1 danh sách có n phần tử T(n/2) là thời gian thực hiện Mergesort 1 danh sách có n/2 phần tử Ta có phương trình đệ quy : 11
- Giáo trình Lý thuyết thuật toán-Bộ môn Khoa học máy tính-2010 nếu n =1 C1 T(n)= nếu n>1 2T(n/2) + C2n Trong đó: - C1 là thời gian phải tốn khi L có độ dài bằng 1 - Trường hợp n>1 , thời gian Mergesort được chia làm 2 phần: + Phần gọi đệ quy Mergesort 1 danh sách có độ dài n/2 là T(n/2) + Phần thứ 2 bao gồm phép thử n>1, chia danh sách thành 2 nửa và Merge, ba thao tác này có thời gian không đổi ⇒ Thời gian thực hiện là C2n b. Giải phương trình đệ quy: Phương pháp truy hồi: Dùng đệ quy để thay thế bất kì T(m) với m1 được thay thế bởi biểu thức của T(1). Vì T(1) luôn là hằng nên ta có công thức của T(n) chứa các số hạng chỉ liên quan tới n và các hằng số. *Ví dụ 7: Giải phương trình: nếu n=1 C1 T(n)= 2T(n/2) + C2n nếu n>1 n Ta có T ( n ) = 2T + C 2 n 2 n n n T ( n ) = 22T + C 2 + C 2 n = 4T + 2C 2 n 4 4 2 n n n T ( n ) = 42T + C 2 + 2C 2 n = 8T 8 + 3C 2 n 8 4 n T ( n ) = 2 i T i + iC 2 n 2 Giả sử n=2k quá trình suy rộng này sẽ kết thúc khi i=k ⇒ T ( n ) = 2 k T (1) + kC 2 n Vì 2k=n ⇒ k=logn và với T(1) = C1 ⇒ T ( n ) = C1 n + C 2 n log n ) Vậy thời gian thực hiện thuật toán là O(nlogn) 12
- Giáo trình Lý thuyết thuật toán-Bộ môn Khoa học máy tính-2010 Định lý: (Về nghiệm của phương trình truy hồi) Cho a, b, c nguyên, dương. Khi đó nghiệm của phương trình truy hồi: = 1 b Õ u nn T(n) = n aT( ) + bn Õ un > 1, = ck n n c Có dạng: O( n) nÕ u < c a n = c T(n) = O ( n log c n) Õ u a nl ca ) Õ u > c og O ( na 1.5. Thuật toán không đơn định đa thức(Nodeterministic Polynomial NP) Với nhiều bài toán tối ưu tổ hợp vẫn chưa tìm được các thuật toán đơn định chạy trong thời gian đa thức, trong khi đó nếu cho phép dùng thuật toán không đơn định thì lại dễ dàng chỉ ra các thuật toán chạy trong thời gian đa thức. Ta xét bài toán sau đây: Bài toán xếp balô 0-1(KNASPACK) - Input: 1 balô có thể tích B; n đồ vật có thể tích a1,a2,…,an . - Output: Tìm nhóm đồ vật đặt vừa khít balô. *Cách 1: Phương pháp Vét toàn bộ cần số phép thử các khả năng là: C n + C n + ...C n −1 + Cn ≈ 2n 1 2 n n Độ phức tạp tính toán là O(2n ). *Cách 2: Diễn tả thuật toán không đơn định ta cần dùng 3 hàm: - CHOICE(a1,a2,…an): Chọn một trong số n giá trị. - SUCCESS: Nếu có một điều kiện thỏa mãn. - FAILURE: Nếu điều kiện không thỏa mãn. Khi đó bài toán trên có thể diễn đạt như sau: ∑ ai = B . Liệu có thể tồn tại tập chỉ số T ⊂ {1,2,…,n} mà i∈T Thuật toán: For i:=1 to n do xi:= CHOICE({0,1}); {phép toán lựa chọn một trong 2 giá trị} n ∑x a if =B then SUCCESS i i i =1 else FAILURE; 13
- Giáo trình Lý thuyết thuật toán-Bộ môn Khoa học máy tính-2010 - Giá phải trả về thời gian : + Trường hợp SUCCESS: Thời gian ít nhất để thực hiện SUCCESS . + Trường hợp FAILURE: Chính là thời gian tối đa. Thuật toán trên trở thành không đơn định đa thức, số phép tính thực hiện là 2*n+2. Bài toán Xếp balô mở rộng (Tên trộm tham lam) Input: Một ba lô có thể tích B, n đồ vật có thể tích: a1, a2,…an , giá trị tương ứng của các đồ vật là: p1, p2,…pn ∑ ai ≤ b và ∑ p Ouput: Có tồn tại tập T ⊂ {1,2,…,n} sao cho đạt max ?. i i∈T i∈T Bài toán xếp balô giá trị nguyên: Input: Một ba lô có thể tích B, n đồ vật có thể tích: a1, a2,…an , giá trị tương ứng của các đồ vật là: p1, p2,…pn Số lượng mỗi loại đồ vật là không hạn chế, x i nguyên là số lượng loại đồ vật i. n n ∑ ai xi ≤ B và ∑ pi xi Ouput: Tìm nhóm đồ vật thoả mãn đạt max ?. i =1 i =1 Mối quan hệ về tính đa thức giữa mô hình Turing và mô hình tựa Algol Định lí 1: Thuật toán trên máy Turing là đa thức thì thuật toán trên tựa Algol tương ứng cũng là đa thức, ngược lại chưa chắc. Ví dụ 8: Tính S=2 2 . n x:=2; for i:=1 to n do x:=x*x; x2 Ta có i:=1 : x2 * x2 = x 2 i:=2 : 2 x4 * x4 = x 2 i:=3 : 3 … n −1 n −1 i:=n : x2 * x2 = x2 . n + Trên máy Turing : Dữ liệu vào 2 2 mã nhị phân là: [log2 2 2 ] +1 ≈ 2n , độ phức tạp n n là O(2n) + Thuật toán tựa Algol : Độ phức tạp 2n+1 ≈ O(n) . Định lí 2 : Nếu thuật toán tựa Algol là đa thức và trong thuật toán chỉ có các phép toán cơ bản( +, -, *, /, so sánh,gán, AND, OR…) và dữ liệu vào phải có độ phức tạp 14
- Giáo trình Lý thuyết thuật toán-Bộ môn Khoa học máy tính-2010 đa thức theo quan niệm 2(độ dài mã) thì thuật toán (trên máy Turing) tương ứng là đa thức. Ví dụ: Input: Dãy số a1,a2,…an, n. Output: Sắp xếp theo chiều giảm dần. For i:=1 to n do Begin j:=i; for k:=i+1 to n do if ak>aj then j:=k; TAM:=ai; ai:=aj; aj:=TAM; End; Độ phức tạp tính toán: - Dữ liệu: n+1 ≈ O(n). - Bộ nhớ: (n+1)+4=n+5 ≈ O(n) (vào) (i,j,k,tam) n −1 +4(n-1) =n2+3n-4 ≈ O(n2). - Thời gian: 2((n-1)+(n-2)+…+2+1)+4(n-1) = 2n. 2 ⇒ Thuật toán là đa thức ⇒ Thực tế giải được. 1.5.1. Sự phân lớp các bài toán. Với một bài toán cho trước có 2 khả năng xảy ra: + Không giải được hoặc + Giải được bằng thuật toán. - Trường hợp bài toán giải được bằng thuật toán cũng chia làm 2 loại: + Thực tế giải được: Được hiểu là thuật toán xử lý trong thời gian đủ nhanh, thực tế cho phép, đó là thuật toán có độ phức tạp thời gian là đa thức. +Thực tế khó giải: Được hiểu là thuật toán xử lý trong nhiều thời gian, thực tế khó chấp nhận, đó là thuật toán có độ phức tạp thời gian là trên đa thức (hàm mũ). Do đó, ta có sự phân lớp các bài toán do 2 tác giả Cook và Karp đề xuất năm 1970- 1971 như sau: - P : Là lớp các bài toán có thể giải được bằng thuật toán đơn định trong thời gian đa thức (Deterministic polynomial). 15
- Giáo trình Lý thuyết thuật toán-Bộ môn Khoa học máy tính-2010 Ví dụ: Bài toán về tính liên thông của đồ thị có thể giải đuợc nhờ thuật toán với thời gian tính là O(n2)⇒ Thuộc lớp P NP : Là lớp các bài toán có thể giải được bằng thuật toán không đơn định trong thời gian đa thức. Hay, là lớp các bài toán mà mọi nghiệm giả định đều có thể được kiểm chứng trong thời gian đa thức (Nondeterministic polynomial).. Ví dụ: Bài toán kiểm tra một dãy đỉnh của đồ thị G có là chu trình Hamilton hay không có thể thực hiện sau thời gian đa thức ⇒ Thuộc lớp NP ⇒ P ⊆ NP Nhưng hiện nay chưa chứng minh được P là tập con thực sự của NP, vấn đề P = NP? hiện là một trong số các vấn đề mở nổi tiếng nhất và cũng đắt giá nhất trong Toán học và trong Tin học lý thuyết. 1.5.2. Khái niệm “dẫn về được” (Phép quy dẫn): Cho hai bài toán A, B Định nghĩa1: Bài toán A được gọi là “dẫn về được” bài toán B sau thời gian đa thức nếu có một thuật toán đa thức để giải bài toán B thì cũng có một thuật toán đa thức để giải bài toán A. Nghĩa là: Bài toán B “khó hơn” bài toán A hay A “dễ hơn” B hay A là trường hợp riêng của B. Kí hiệu A ∝ B. Phép quy dẫn có tính chất bắc cầu: A ∝ B và B ∝ C ⇒ A ∝ C. Tư tưởng quy dẫn đã giải thích vai trò quan trọng của lớp bài toán P. Nếu ta có bài toán A thuộc lớp P và một bài toán B có thể quy dẫn về A, thế thì B cũng thuộc vào P. Nghĩa là P là đóng đối với phép quy dẫn. Định nghĩa 2 : Bài toán A được gọi là “khó tương đương” bài toán B nếu A ∝ B và B ∝ A. Kí hiệu A ~ B. 1.5.3 Lớp bài toán NP - khó (NP - hard) và NP - đầy đủ (NP – Complate) a) Bài toán quyết định: Bài toán quyết định là bài toán mà đầu ra chỉ có thể là “Yes” hoặc “No” (Đúng/sai, 0/1, chấp nhận/từ chối). Ví dụ: Bài toán về tính nguyên tố: ” Hỏi số nguyên n có là số nguyên tố hay không?”. Khi đó ta có n = 23 là bộ dữ liệu vào “Yes”, còn n = 24 là bộ dữ liệu vào “ No” của bài toán. b) Bài toán NP – Khó(NP – Hard) Bài toán A được gọi là NP- khó nếu như tồn tại thuật toán đa thức để giải bài toán A thì 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. 16
- Giáo trình Lý thuyết thuật toán-Bộ môn Khoa học máy tính-2010 Hay: A là NP – Khó nếu như B ∝ A, với mọi bài toán B ∈ NP Một cách không hình thức, có thể nói rằng nếu ta có thể giải được một cách hiệu quả một bài toán NP – Khó cụ thể thì ta cũng có thể giải hiệu quả bất kỳ bài toán nào trong NP bằng cách sử dụng thuật toán giải bài toán NP-Khó như là một chương trình con. c) Bài toán NP - đầy đủ(NP – complete, NPC) Một bài toán quyết định A được gọi là NP - đầy đủ nếu như i) A là bài toán trong NP, ii) Mọi bài toán trong NP đều có thể quy dẫn về A. Lưu ý: Khái niệm NP - đầy đủ đòi hỏi bài toán nhất thiết phải có dạng quyết định. Ta có bức tranh tạm thời đầy đủ về phân lớp các bài toán trên hình sau: Hình 2: Sự phân lớp các bài toán c) Phương pháp chứng minh một bài toán là NP - đầy đủ - Cách 1: Theo định nghĩa (rất khó). NP-khó C - Cách 2: áp dụng bổ đề sau: NP NP Bổ đề: Giả sử bài toán A là NP - đầy đủ, bài toán B thuộc NP và bài toán A quy dẫn về B. Khi đó bài toán B cũng là NP - đầy đủ. P Ví dụ 9: Bài toán xếp balô(KNASPACK) ∈ NPC ⇒ Chứng minh bài toán lập lịch ∈ NPC. °Bài toán lập lịch (Bài toán PHẠT): Input: Có n công việc xử lý trên một máy. ri: Thời điểm bắt đầu công việc xử lý i di : Hạn định hoàn thành công việc i. ti : Thời gian xử lý công việc i, ti ≤ di-ri. bi : Thời gian bắt đầu xử lý. ci : Thời gian kết thúc công việc i, ti=ci-bi 17
- Giáo trình Lý thuyết thuật toán-Bộ môn Khoa học máy tính-2010 nếu ci ≤ di , công việc i là xử lý đúng hạn. nếu ci>di , công việc i là xử lý quá hạn(bị phạt). wi : Tiền phạt. Output: Hãy sắp xếp các công việc theo một thứ tự nhất định để theo đó chờ đến lượt xử lý, sao cho lượng tiền phạt là ít nhất. 0 nếu ci ≤ di (đúng hạn) Kí hiệu Ui = 1 nếu ci>di (quá hạn) n ∑ UiWi → min Khi đó yêu cầu : i= 1 n Ta có thể viết bài toán trên ngắn gọn như sau : n 1 ∑ UiWi . Kí hiệu là PHẠT. i= 1 Bài toán này rõ ràng là giải được bằng phương pháp “vét toàn bộ”. Nhưng thực tế khó giải vì nó thuộc lớp NP_đầy đủ. Để chứng minh bài toán “PHẠT” là NP - đầy đủ, chỉ cần chứng minh rằng bài toán KNAPSACK ∝ PHẠT vì ta đã biết KNAPSACK là NP_đầy đủ. Nói một cách khác KNAPSACK là trường hợp riêng của PHẠT. Nhắc lại bài toán KNAPSACK: Input: n đồ vật với thể tích a1,a2,…an cần nhét vào balô có thể tích B. Output: Tìm nhóm đồ vật có thể nhét vừa khít balô trên. ∑ ai = B .) ( ∃ T ⊆ {1,2,…,n} mà i∈T a) Để chứng minh KNAPSACK ∝ PHẠT trước hết ta diễn đạt nó bằng ngôn ngữ của bài toán PHẠT. Cụ thể mỗi vật i ở KNAPSACK được xem là một công việc trong PHẠT, chúng đồng thời được nhập vào hệ thống. Mọi công việc có hạn định như nhau và bằng B. Thời gian ti thực hiện công việc i bằng tiền phạt wi và bằng thể tích ai của vật. Tóm lại ta có thể biểu diễn bài toán như sau: - n công việc đồng thời được xử lý ri =0, ∀ i=1,2,…,n. Input: - mỗi công việc i (1 ≤ i ≤ n ) được biết di=B, ti=wi=ai, ∀ i=1,2,…,n. - máy làm việc liên tục cho đến khi mọi công việc được xử lý xong. - tại mỗi thời điểm máy chỉ xử lý được một công việc. - khi đang xử lý công việc i, không được phép ngắt nó để thực hiện một công việc khác. 18
- Giáo trình Lý thuyết thuật toán-Bộ môn Khoa học máy tính-2010 Output: Hãy lập lịch để máy xử lý các công việc sao cho lượng tiền phạt là ít nhất n ∑ UiWi là nhỏ nhất. i= 1 b) Chứng minh: Giải được PHẠT bằng thuật toán đơn định đa thức thì cũng giải được KNAPSACK bằng thuật toán đơn định đa thức và ngược lại. n n ∑ ∑ °Giả sử giải được PHẠT tức là lịch biểu mà WiUi là nhỏ nhất, vậy thì: i =1 i =1 ∑b =∑a =∑w n WiUi= ∑ ai -b. i i i i =1 ri=0 b di=b -b UiWi = ∑ ai = ∑ ai -b n n ∑ Suy ra ∃ S ⊆ {1,2,…,n} mà i∈S i= 1 i =1 Hay b= ∑ ai - ∑ ai = ∑ ai với T={1,2,…,n}- S. n Như vậy KNAPSACK đã giải i∈T i∈S i =1 được. ∑ ai = b °Ngược lại, giả sử KNAPSACK đã giải được, tức là ∃ T ⊆ {1,2,…,n} mà i∈T hay ∑ ai = ∑ a - ∑ a =b, như vậy ∑ a - ∑ n n n n n UiWi = ∑ ai -b , đây là lượng ∑ UiWi =b ⇒ i i i i∈T i∈S i =1 i =1 i= 1 i= 1 i =1 tiền nhỏ nhất và PHẠT đã giải được. n ∑a *Chú ý: Nếu tất cả n công việc đều quá hạn thì lượng tiền phạt lớn nhất là . i i =1 d) Một số bài toán đã được chứng minh là NP – khó , NP - đầy đủ Để chứng minh một bài toán nào đó là NP-đầy đủ (NP-khó) công việc khó khăn nhất là tìm được một bài toán NP-đầy đủ có thể quy dẫn về nó. Do đó ta cần biết thêm về những bài toán đẫ được chứng minh là NP-đầy đủ, cho đến nay danh mục các bài toán NPC trong các lĩnh vực đa dạng :Logic Bool, đồ thị, số học, lập lịch, trò chơi, otomat…đã lên đến hàng nghìn . Sau đây là một số bài toán đã được chứng minh là NPC: Bµi to¸n 3SAT. 19
CÓ THỂ BẠN MUỐN DOWNLOAD
-
Giáo trình Lý thuyết xác suất và thống kê toán - ĐH Trà Vinh
145 p |
4094 |
1133
-
Giáo trình Lý thuyết thống kê - ĐH Kinh tế Tp.HCM
167 p |
1073 |
274
-
Giáo trình Lý thuyết thống kê - Ths. Đồng Thị Vân Hồng
89 p |
543 |
210
-
Giáo trình lý thuyết thống kê - Nguyễn Hoàng Oanh (chủ biên), Nguyễn Văn Thạch
70 p |
521 |
194
-
Giáo trình về lý thuyết thông tin
228 p |
174 |
97
-
lý thuyết tính toán
0 p |
189 |
88
-
Giáo trình Lý thuyết thống kê và phân tích dự báo: Phần 1 - Chu Văn Tuấn
194 p |
123 |
71
-
Giáo trình Lý thuyết thống kê và phân tích dự báo: Phần 2 - Chu Văn Tuấn
188 p |
87 |
47
-
Giáo trình Lý thuyết xác suất và thống kê toán: Phần 1 - Hoàng Ngọc Nhậm
95 p |
68 |
41
-
Giáo trình Lý thuyết xác suất và thống kê toán: Phần 2 - Hoàng Ngọc Nhậm
149 p |
44 |
31
-
Giáo trình Lý thuyết số
139 p |
32 |
25
-
Giáo trình Lý thuyết thống kê: Phần 2
281 p |
28 |
15
-
Giáo trình Lý thuyết thống kê: Phần 1
238 p |
27 |
15
-
Giáo trình Lý thuyết nhóm (Dùng cho sinh viên ngành Toán học): Phần 1
27 p |
15 |
11
-
Giáo trình Lý thuyết xác suất và thống kê toán học - Phần 1
91 p |
19 |
8
-
Giáo trình lý thuyết đồ thị - Bài 13
0 p |
30 |
6
-
Giáo trình lý thuyết đồ thị - Bài 2
0 p |
25 |
5
-
Giáo trình Lý thuyết thống kê: Phần 1 (dùng cho Trung cấp nghề và Cao đẳng nghề)
29 p |
1 |
0

Set-Cookie: TLDEVNamespace=gh5fekqecgtm6sp94lscdpk7g3; path=/; domain=.tailieu.vn; HttpOnly

Server: Apache/2.2.31 (CentOS)


text:
Chủ Nhật, ngày 29 tháng 11 năm 2009
TN bàn Chính trị: Bài 4- Dân chủ từ trên xuống
Dân chủ từ trên xuống là một khái niệm xuất sắc, chỉ có ở ta. Số là Đảng và nhà nước có chủ trương trao quyền tự quyết cho nhân dân khi bầu chính quyền cơ sở ở cấp phường, xã. Cái này là học của Tàu, bọn này trao quyền cho nhân dân đã đến cấp thành phố. Nói là trao quyền thực ra chỉ là quyền được bầu cử tự do lãnh đạo của cấp ấy. Và một vị chức sắc của ban tuyên giáo trung ương nói là, sự việc này là thí điểm của mô hình dân chủ từ dưới lên. Thật dễ hiểu, người dân được quyền chọn cho mình Chủ tịch xã,được quyền chọn ra người xứng đáng nhất để phục vụ cho lợi ích của mình, tuy nhiên hội đồng nhân dân lại không được thành lập. Và vị này nói thêm, các cấp còn lại và từ xưa đến nay nước ta theo mô hình "Dân chủ từ trên xuống". Cái hay, cái sáng tạo là chỗ này. Từ trên xuống nghĩa là, bầu thì cứ bầu, nhưng ai trúng là do trên nó đặt chỗ. Bầu chỉ để tiêu bớt tiền ngân sách thôi, chi phí chắc chắn không nhỏ. Và tất nhiên , một ông "Chẳng may" trúng chức thì đố có dám làm trái thằng đưa mình lên, quyền lợi của dân thì có nghĩa gì? quyền lợi của cấp trên mới là quan trọng. Còn ông được dân bầu, làm quan tất phải nhìn lên nhìn xuống, nhưng đã được dân chọn, nhất không thể là loại tham lam ngu xuẩn được, càng không thể là loại bán đất bán nước được.
    Cái hay là như vậy, các ông chủ của đất nước - nhân dân được nô bộc của mình- bên dưới- cai quản, nhưng lại bị hưởng chế độ dân chủ từ trên xuống do bên dưới, công bộc của dân, đặt ra. Trên cho gì, dưới được lấy, trên lấy gì, dưới mất đấy, dưới kêu, trên thích thì nghe, không thích thì bịt tai lại, mà nói nhiều quá là ăn đập, còn làm tới là bị xử ngày, cảnh sát và các lực lượng vũ trang lương cao luôn trung thành với "nô bộc".
    Từ nãy giờ, cứ trên trên, dưới dưới, rồi chủ chủ, tớ tớ, rồi thì chủ thì bị nô bộc nó đập, nó cai quản... loạn hết cả lên, chả hiểu gì cả. Nói tóm lại dân chủ từ trên xuống có dân chủ không, không biết đâu mà lần, có lẽ vì lý do này mà ông chức sắc tuyên giáo kia mới thốt ra miệng cụm từ này "Dân chủ" nhưng là "Dân chủ từ trên xuống". Chế độ mà hiển nhiên người được chọn (bầu)ra sẽ luôn bảo vệ quyền và lợi ích cho tầng lớp thiểu số quan chức và người giàu. Và dĩ nhiên những từ như chuyên chế, phong kiến hay độc tài ... không thể hay bằng "Dân chủ từ trên xuống"
---
hình bên:Tát nước - Nguyễn Trung Liêm, giải nhì cuộc thi biếm họa lần 1
...haiku
Gió nhẹ
Trời mù
Bụi hay sương
---
Sáng đúng giờ
Chiều đúng giờ
Ngủ lơ mơ
Đời công chức
---
Không thứ 7
Không chủ Nhật
Điện thoại cầm tay
Loay hoay tìm đối tác
---
Nước mắt
Mặn môi
Giọt tình đầu
Thương nhớ
---
Tranh:typhokiss_5250-sưu tầm trên diễn đàn thanhdiamanga.org
HHPT bài 4: Tìm hiểu Johan Vermeer qua tác phẩm : thiếu nữ đeo hoa tai ngọc trai
Đây là một tác phẩm lấy cảm hứng từ một bức tranh của Vermeer, một danh họa Hà Lan, thế kỷ 17. Tôi có đọc một vài tác phẩm kiểu này, nhưng đây có lẽ một câu chuyện được kể để lại nhiều một cách giản dị và sâu sắc nhất. Người đọc sẽ được chiêm ngưỡng suy luận của một nhà văn, của một người xem tranh, một nhà nghiên cứu hiện tại trước một tác phẩm của ông - Thiếu nữ đeo hoa tai ngọc trai. Qua tác phẩm và xem lại bức tranh, nhà văn đã đi ngược lại, tìm hiểu quá trình vẽ của họa sĩ, phân tích nội tâm của người mẫu, phân tích ánh sáng, và tách màu của tranh. Không những thế, với tài năng của mình , nhà văn đã dựng lên tính cách của họa sĩ, tính cách của người mẫu, hoàn cảnh ra đời của bức tranh. Và sự suy diễn này phải nói là rất hợp lý, các hành động, các tuyến nhân vật phụ, mối quan hệ và diễn biến của các mối quan hệ, tổng thể ấy đã làm lên một câu truyện hay, đằm thắm. Một ấn tượng giản gị, nó không có kiểu hấp dẫn, lôi cuốn ào ạt như một tác phẩm khác cùng loại như : “Bức họa Maja khỏa thân”, nó như một thứ rượu ngon, lúc đầu thì dịu nhẹ dễ vào, nhưng càng uống càng thấm, càng say. Người đọc còn biết thêm về quá trình pha chế màu, bây giờ những việc này vô cùng đơn giản do công nghệ hóa chất tiên tiến, nhưng ở thời điểm đó thì để có được những màu sắc mong muốn là cả một quá trình tìm tòi công phu, nhiều công sức. Sự điều khiển ánh sáng của họa sĩ để tạo ra một bố cục, hàm ý của bức tranh rất tinh tế. Và không khó khăn lắm, người đọc khi xem lại bức tranh, bìa của sách, sẽ thấy ngay được vẻ đẹp của nó, một bài học về hội họa phương tây./.
P/S: “Bức họa Maja khỏa thân” : hấp dẫn, lôi cuốn, có thể đọc một mạch đến hết. Nhưng không có nhiều ý nghĩa về hội họa. Đơn giản chỉ là một câu chuyện tình lãng mạn, có gắn thêm bức tranh của Francis Goya- họa sĩ Tây Ban nha.
“Người tình tuyệt vời” một câu chuyện nhảm nhí vớ vẩn, văn chương thum thủm – bức tranh “sự ra đời của thần vệ nữ” chỉ là cái cớ. Thiên tài phục hưng Balotteli - chết tí nhầm, là Botticelli- nếu sống lại sẽ vả vỡ mồm tác giả của cuốn bestselet này, hoặc thằng biên tập nó ra tiếng Việt. Nhiều tập, nhiều chữ, tốn giấy, mất công đọc.
“Kiếp sau” của Marc LEVY, về tác phẩm “Thiếu nữ áo đỏ” của Radskin họa sĩ Nga, ông này là kiến trúc sư, qua viết văn, khá ăn khách ở Pháp. Đọc mấy dòng giới thiệu ở bìa, tưởng hay, ai ngờ đọc như ăn phải cơm sạn, cháy, dớt. Nếu ko tiếc mấy chục nghìn cộng thêm giấy, bìa đẹp thì đã cho hóa vàng nó. Tôi nghi là do mấy thằng dịch ở ta dịch ẩu, nhưng cố đọc thêm một chuyện nữa của cha này thì đúng là, không thể chịu nổi, may mà chỉ thuê quyển này. Hồi thằng cha này sang Việt Nam, tôi định lên Hà Nội để tương giày vào mặt nhưng vì sợ công an lên thôi.
“Kafka bên bờ biển” của Haruki Murakami, một câu chuyện hư ảo, đưa người đọc đến những góc sâu nhất của con người. Khác với “Rừng Nauy”- là một tác phẩm thật của Beatle, bức tranh “Kafka bên bờ biển” tên của một bản nhạc, một bức tranh của nhân vật trong chuyện. Murakami là vậy, phù thủy của ngôn ngữ, có lẽ ông viết cáo phó thì khối người sẽ rơi nước mắt.
Thứ Sáu, ngày 27 tháng 11 năm 2009
2012 - một phim gây cảm xúc mạnh
2012 - năm đại họa, phim mới của Roland Emmerich, đơn giản chỉ có thể nói là nó đem đến cho người xem những cảm xúc rất mạnh, trực diện, mừng tủi, hồi hộp đứng tim, sợ hãi và lo lắng, và nhiều day dứt. Cảm xúc đến theo cách thật đơn giản, tình cảm nhiều khi cũng vậy. Để đạt đến mức này, đạo diễn và biên kịch thật tài tình. Tất nhiên kỹ xảo thì không có gì phải bàn, luôn là một đỉnh cao khi Emmerich xây dựng, tuy nhiên cái đáng nói là nó được xử dụng rất hợp lý, cái cách bố trí các cảnh kỹ xảo, liều lượng của chúng làm người xem đi từ lo lắng này đến hồi hộp khác, làm họ nín nặng rồi bật khóc, kỹ xảo đã "diễn xuất" rất tốt. Rồi tình tiết, các mối quan hệ giữa người và người trong phim rất sinh động, chân thật, đậm chất nhân bản cao đẹp, đem đến cho người xem một nội tâm hướng thiện.
    Emmerich từng nổi tiếng với ngày độc lập, (will smith, jeff goblum,) the patriot (mel gibson, helth ledger) ngày kinh hoàng-THE DAY AFTER TOMORROW (dennis quaid), 10000BC..., cốt chuyện các bộ phim của ông có đặc điểm chung là rất mạch lạc, dễ hiểu, nhiều kỹ xảo hoành tráng và đóng vai trò chính, tuy nhiên các câu chuyện nhân sinh lồng vào trong đó có vai trò quan trọng không kém, các câu chuyện đều rất cảm động, cảm xúc nhân vật được miêu tả chân thực và rất nhân văn, rất đẹp. 2012 có lẽ là phim hay nhất cho đến nay của Roland.
Thứ Tư, ngày 25 tháng 11 năm 2009
TN và chuyện chính trị: Bài 3- Nền Cộng Hòa
      Trước khi đăng bài 2: Buôn gì giàu nhất, tôi xin nói về nền cộng hòa, vì tôi nhớ, nước ta trước đây có tên là "Việt Nam Dân Chủ Cộng Hòa",cái tên này tồn tại từ hồi thành lập nước và chỉ được đổi từ năm 1976(hình như vậy), cái tên này rất hay, nó chỉ rõ nước ta (hoặc mục đích) là một nước cộng hòa và có một nền dân chủ. Tìm hiểu về vấn đề này nói chung là nhức đầu và nhiều người, nhất là thanh niên, coi là vớ vẩn, có một ví dụ dễ hiểu đó là bộ phim "Tiến tới nền Cộng Hòa" được chiếu trên VTV gần đây. Đây là một bộ phim rất hay về chủ đề chính trị, mô tả quá trình tìm kiếm một nền cộng hòa, dân chủ của Tôn Trung Sơn. Trong phim ta dễ dàng nhận ra sự so sánh giữa hai thể chế, cộng hòa và chuyên chế. Và cũng mô tả sự biến tướng của chế độ chuyên chế giả làm cộng hòa. Nền cộng hòa nói đơn giản có thể hiểu là một chế độ mà ở đó một tổng thống và một nghị trường gồm các ông nghị (nghị sĩ-gần tương đương như đại biểu quốc hội ở ta) được toàn thể người dân bầu ra, không đề cấp tới đảng phái chính trị nào, miễn là người được bầu chiếm được đa số phiếu. Như ta thấy thể chế này chiếm gần như 4/5 trái đất, chỉ trừ lại một số quốc gia, trong đó có nước ta, và nhà nước chuyên chế kiểu mới Trung Hoa Đại Lục. Nền cộng hòa trong bộ phim trên được Tôn Trung Sơn và đảng Quốc Dân dày công thực hiện và nó trở thành nỗi sợ hãi của chế độ chuyên chế đương thời của Từ Hy Thái Hậu, một con cáo già chính trị. Và khi được hình thành, lúc đầu, sự ưu việt của nó đã được so sánh rất chính xác với sự lạc hậu của nền chuyên chính trước đó. Tuy nhiên trong thời kỳ đầu đầy khó khăn nó đã bị một con cáo già chính trị khác là Viên Thế Khải thao túng và hủy diệt. Ở giai đoạn đầu đó có một quốc hội đúng nghĩa đã được mô tả rất chân thực với đầy đủ các (đại diện)thành phần trong xã hội tham gia, sự phản biện tổng thống, sự minh bạch trong chính sách, và các vấn đề của quốc gia được xem xét công khai bởi các nghị sĩ. Có Ủy ban bầu cử độc lập, tòa án độc lập...vì thế nó là kẻ thù của chế độ chuyên chế, chế độ phong kiến. Viên Thế Khải với với mưu đồ tái lập chế độ cũ, cùng với tài thao lược đã hủy diệt nó không thương tiếc, với một cảnh bắt bớ các nghị sĩ ngay trong một phiên họp. Trở lại cái tên của nước ta hiện nay "Cộng hòa Xã hội Chủ Nghĩa Việt Nam", tôi không dám bàn nhiều tới cái từ cộng hòa trong nó, nhưng cụm từ "Xã hội chủ nghĩa" mà nó mang, là một xã hội trong mơ, là một thiên đường mà Liên Xô là quốc gia đến gần nó nhất-đến thời kỳ quá độ. Còn mô hình kinh tế của nước ta hiện nay, một thầy giáo dạy Kinh Tê Chính trị của tôi từng nói : "Như chủ nghĩa tư bản Mỹ những năm 30", chủ nghĩa tư bản thô bạo.
      Còn nhớ khoảng những năm 80-90, có người đi qua tượng ông Lê Nin, gần Bảo tàng quân đội đã bình rằng:
Ông Lê Nin ở nước Nga
Cớ sao ông lại đi qua nước này
Ông đứng vạch áo chỉ tay:
"Thời ký quá độ, chúng mày còn lâu."
Thứ Hai, ngày 23 tháng 11 năm 2009
Người Hải Phòng xấu xí * : hồi 1- văng tục, chửi bậy
Giữa đường gặp chuyện bất bình (**)
Văng tục quá đỉnh, cả làng nghe chơi
Cái hay cái đẹp của Hải Phòng ta thì nhiều người đã nói và có rất nhiều trên mạng, cái xấu cũng không ít nhưng tìm trên mạng thì ít hơn. Và tôi cũng không biết kể bao nhiêu cho đủ, đầu tiên xin nói về tật văng tục chửi bậy. Phải nói là cực kỳ phổ biến. Ngồi uống bia mà thằng bạn học phổ thông với tôi cứ câu phát ra là nó lại văng kèm ông bà bố mẹ cùng với các bộ phận tế nhị khác rất vô tư thoải mái. Cả bọn góp ý, chỉ một lúc sau nó quên ngay, thế là quay ra phạt, văng một câu nhớ mẹ là 1 cốc. Thế mà hôm ấy nó chỉ bị đúng 1 cốc, thế mới tài. Chúng tôi cùng kết luận, tật chửi bậy văng tục của thằng này có thể sửa được, chỉ là nó có muốn hay không. Rồi thì trên đường, văn hóa giao thông kém nên hay va chạm, nhẹ thì cũng đèo xìu vài cái, nếu mấy thằng mất dạy tông xe bỏ chạy thì người bị đâm sau khi dựng xe dậy cũng xổ theo một tràng dài ấn tượng cho mình và người xung quanh nghe, không biết có bõ tức không, còn nặng, hai bên cùng ngã thì nhất định tranh tài quyền cước, đấm đá ngay. Đỉnh điểm cao trào của tật này chính là những màn chửi đồng thanh trong sân bóng đá. Các địa phương khác hình như cũng thế, nhưng tôi chỉ được chứng kiến giàn giao hưởng Lạch Tray nhà ta hợp xướng thôi, đến sân khách cũng thế. Mục tiêu quen thuộc là trọng tài, kế đến là cầu thủ đội khách, cuối cùng là cầu thủ đội nhà khi hòa, thua hoặc bán độ. 1…2…3… Bán độ, hoặc ĐM trọng tài, một lần lâu rồi, hồi Huỳnh Đức còn đá, cả một nửa khán đài đồng thanh, Huỳnh Đức cởi truồng. Trận HP gặp Sông Lam Nghệ An, sau sự cố bị mai phục ở Vinh tôi không được xem, nhưng chắc chắn các màn chửi rủa là vô tiền khoáng hậu. Không chỉ giai, mà gái ở ta chửi cũng không kém gì. Giọng nữ Hải Phòng vốn có một ít âm vực cao và thanh, khi phát hỏa thì đanh thôi rồi, pháo Bình Đà còn thua xa. Người lớn là vậy, tức điên hơn là khi những lời chửi bậy, văng tục phát ra từ học sinh cấp 1, cấp 2còn cấp 3 thì khỏi nói, và trẻ em 3-5 tuổi. Cái mặt trông ngây thơ, yêu thế mà đã biết chỉ tay ĐM mày, thế mới cay mũi. Các cụ có câu “Con gà tức nhau tiếng gáy”, mới thấy chuyện hơn thua ở lời nói ở ta nó quan trọng như thế nào, thế nên chửi bậy hơi, to hơn, át cả đối thủ là thắng rồi, đâu cần lý lẽ phải trái, luật pháp.
* lấy theo tên, người Việt xấu xí, người Trung hoa xấu xí.
** Con xin lỗi cụ đồ Chiểu
Thứ Tư, ngày 18 tháng 11 năm 2009
HHPT-Bài 3: Chuyện Vangogh
    Nói đến Van gogh, đa số dân ta có lẽ đều lờ mờ đoán ông là họa sĩ, còn ai hay xem bóng đá thì biết ngay ông là người Hà Lan, bởi cái tên của ông, nó bắt đầu bằng chữ Van, như van der sar, van bas ten, van der vart, van buy ten… Ông không được đào tạo một cách bài bản, ông thích vẽ và các kỹ năng thu được là nhờ xem nhiều tranh từ cửa hàng của người anh trai, Theo, từ các bảo tàng. Tự học là chính, các bức vẽ của ông ra đời tự sự bức bối, từ sự thôi thúc nội tại của bản thân. Tranh của ông gần như không theo một trường phái nào, bạn có thể gặp nhiều đặc điểm của các trường phái khác trong tranh ông, ấn tượng, dã thú... đều có cả và ông đặc biệt thích hội họa Nhật Bản. Bức “Hoa diên vĩ” nổi tiếng là kết quả của "mối tình" này, có lẽ vậy mà nó được người Nhật mua với giá khủng khiếp, nghe đâu tới 70-80 tr USD, và nó trở nên nổi tiếng, riêng tôi nó chỉ là một bức rất bình thường trong sự nghiệp của Vangogh. Nó còn được các tay làm truyền hình thực dụng của nước ta đưa vào một game show ăn khách có anh củ Sâm làm MC.
    Cũng như các thiên tài khác, ông là người cực đoan trong tính cách và quan niệm nghệ thuật của mình. Hồi còn là thầy tu ông đau nỗi đau của các con chiên khổ cực, sống cuộc sống lam lũ cùng họ. Nhà thờ tiểu khu thời đó nghi ngờ lòng tốt của Van gogh và bỏ rơi ông, không có điều kiện cống hiến cho nhà thờ ông dồn hết tâm lực của mình vào tranh vẽ, sự day dứt về số phận con người đau đáu mãi trong tranh ông. Tranh của ông thường có bố cục và hình họa đơn giản, những vệt màu đơn giản mạnh mẽ, khốc liệt nhưng khoáng đạt. Bạn có thể cảm thấy điều này khi xem tranh ông (tất nhiên là xem qua sách báo thôi), những nét bút mạnh mẽ, quyết đoán, trực tiếp từ trong nội tâm ông. Người ta thường nói về màu vàng trong trong tranh Van gogh, nhưng không chỉ có vậy, giai đoạn ông buồn bạn sẽ thấy màu nâu trầm tối, giai đoạn ông bức bối bạn sẽ thấy màu vàng nóng bỏng bức hoa hướng dương, nhưng còn có những màu xanh lam tươi mát khi ông vẽ quán cà phê, hay bức đêm đầy sao, hay các bức phong cảnh về đồng lúa, về những cây cầu... Và khi không có điều kiện để ra ngoài vẽ, ông vẽ tĩnh vật, vẽ bầu trời, vẽ tự họa, vẽ chân dung bác sĩ, vẽ chân dung người bệnh. Vẽ bất cứ thứ gì diễn ra trước mắt ông.
    Sống hết mình, trút hết nội tâm lên từng tấm vẽ, như con yến làm tổ, sức lực tài năng của ông cháy đến tận giờ phút cuối cùng của cuộc đời ông. Cũng có thể như Kurt Cobain, sự bế tắc của bản thân trước thực tại xã hội, sự thất vọng quá lớn về sức mạnh của hội họa và tình bạn với Gô-ganh làm ông không còn tình yêu với cuộc sống, bạn có tin như vậy không? Người ta nói rằng ông đã tự sát.
    P/S: Một số phát hiện gần đây được công bố gây chấn động người yêu hội họa, ông không tự sát mà chết bởi súng của một cậu bé cướp cò, và để bảo vệ cậu bé ông đã không nói gì về điều đó
haiku ngày 20/11
Cô giáo, thầy giáo
Ngồi làm báo cáo
Tổng kết quý 3
---
Bằng thật, bằng giả
Thật thật giả giả
Tiền đều mất cả
---
Gió căm căm
Ngồi chống cằm
Chờ mẹ đón
---
Giữa bó hoa
Cài màu trắng
Trong màu trắng
Có màu xanh
---
Trăng thu
Dây điện
Chuột xẻ làm đôi
Thứ Ba, ngày 17 tháng 11 năm 2009
haiku.....
Gió mùa.
Lạnh buốt tay khô.
Tại sao nghệ thuật không dành cho đa số?
  Có một sự thật rằng nhiều người trong chúng ta khi nghe nhạc không lời, nhạc nước ngoài, tranh vẽ hay phim ảnh có cảm thấy hay hay, thinh thích nhưng cắt nghĩa hay chỗ nào, vì sao hay, cụ thể nội dung nói lên điều gì thì không nói được. Một cục ấm ức to tướng chẹn ngay họng mà không sao nhổ ra được. Tôi đã gặp phải cảm giác này rất nhiều lần, từ khi còn bé có thể là từ hồi lớp 8 lớp 9, vì lúc đó tôi bắt đầu nghe nhạc nước ngoài và lần đầu xem phim của Vương Gia Vệ, "Đông Tà Tây Độc" (DTTD) và "Phi hồ ngoại truyện" bây giờ vẫn vậy dẫu có ít hơn vì có Google. Tôi cảm thấy "Đông tà tây độc" nhất định không phải là một phim dở, mặc dù lúc đó tôi đang mê muội những Lý liên kiệt, Quách Tỉnh, Hoàng Dung, thần điêu đại hiệp, linh sơn thần tiễn, Quỉ Bảo.v..v.. Thế giới của DTTD đầy hư ảo, mơ hồ, thướt tha, quyến rũ nhưng khó tính, rất khó tính. Nó làm tôi rất khó chịu vì không cắt nghĩa được nội dung phim nhưng tôi không thể quên được nó, ánh mắt của Lâm thanh Hà, của Trương Quốc Vinh không làm sao tôi quên được. Thật đáng ghét, ko ai nói cho tôi biết vì sao? Với Van gogh cũng vậy, đọc trên báo nhiều, nghe thời sự nhiều, cũng thấy cái gì đó hay hay nhưng hoàn toàn mù tịt. Và chỉ đến khi tôi đọc hết một đêm trắng về cuộc đời ông, cùng rất nhiều lần thử pha màu, tập vẽ cùng với các bạn được đào tạo ở khoa Kiên trúc, tôi mới thực sự thích, và bắt đầu hiểu ông, hiểu tranh của Ông. Cũng như vậy, phải khi buồn bã , cô độc đến cùng cực, và tức giận thì tôi cũng mới lờ mờ thấy khoái thứ âm thanh chói tai của Rock mặc dù ko biết mấy câu tiếng anh trong đó. Rồi phải tìm lời, dịch, nhẩm đi nhẩm lại, tìm hiểu về sứ xở của họ, đời sống của họ thì mới càng yêu họ hơn. Chúng ta đi tiếp cận nền văn hóa đó từ các sản phẩm hoàn chỉnh, thành phẩm cuối cùng lên chỉ có thể thấy "hay hay" chung chung mà thôi. Nên chẳng có gì khó hiểu khi một nhà bào trên Vietnamnet chê bai thậm tệ DTTD khi bản biên tập lại được công chiếu trên màn ảnh rộng. Các nhịp chuyển động nhẹ nhàng chậm rãi, sự bảng lảng và phiêu du của bộ phim đã không được cảm nhận. Những tiếng hét, khói bụi, xa mạc và những bộ mặt buồn nhiều suy tư đã không tìm được tri kỷ. Tất cả chỉ tại sự bó buộc trong tư duy, sự mất gốc về cảm nhận chủ quan trên cơ sở trí thức, sự mất tự do quá lâu trong suy nghĩ đã làm cho chúng ta thiếu bản lĩnh khi đối diện với nghệ thuật đương đại, thói quen nghe, xem những cái đã được mở sẵn, cảm nhận thụ động dưới sự dẫn dắt, lời lẽ của người khác tất cả các thứ tệ hại đó làm chúng ta mơ hồ, ngờ nghệch trước những thành phẩm cuối cùng của nghệ thuật đương đại, và sự bạc nhược tinh thần trước các ý tưởng, quan điểm độc lập và tự do.
Chủ Nhật, ngày 15 tháng 11 năm 2009
Xứ sở tắt mắt hay tệ ăn cắp vặt
    Ai lấy ? bà chè trai tắt mắt, rao khản cổ chẳng mua được gì, sẵn mấy đôi dép nhựa chủ nhà đê ngoài, quơ bỏ thúng. Mấy thằng trẻ con lêu lổng có, mất dạy có, cứ buổi trưa nhằm sân thượng chung cư đi tuốt ăng ten nhôm. Rồi thì các "cán bộ ma xó" thiếu tiền chính hút ngày ngày đi tuần đều đặn, thấy gì vơ lấy. Rồi cũng chẳng hiếm chuyện bạn cùng phòng, người cùng xóm có thói quen mượn đồ bí mật và cũng không trả. Đến cả trong đội ngũ cán bộ cũng không tránh khỏi. Không biết đúng không, nhưng một lần thủ Tướng về nói chuyện với cán bộ và cử chi một huyện ở Hải Phòng ta, khi về quên cái kính ở hội trường, trợ lý quay vội lại tìm mà loáng cái đã không thấy đâu. Ngồi gần ngài toàn cán bộ chủ chốt của huyện, thành phố cả. Mà hỏi thì chả ông nào nhận, cuối cùng công an phải vào cuộc, vì cái kính đó rất quan trọng với ngài TT. Thủ phạm hóa ra lại là một cán bộ trong ủy ban hay hội đồng nhân dân gì đó. Sau đó không có thông tin gì về việc xử lý cán bộ có thói quen cầm nhầm, nhưng ngài TT đã được bài học đắt giá về "Vật bất ly thân" và về sự trong sạch của cán bộ.
    Cái câu "Một mét vuông mấy thằng ăn cắp" nói ra các nhà xã hội học nghe thì buồn nhưng chắc sẽ có ít người phản đối vì nó được dân đúc kết ra mà, một câu tục ngữ thời hiện đại.
Thứ Hai, ngày 09 tháng 11 năm 2009
Tiên sư Thằng Tào Tháo*
    Hôm trước U23 của ta đập vào mặt U23(thực chất là U19) của Tàu 3-1, tôi rất sướng nhưng vẫn bực âm ỉ vì thái độ của Tàu, mình mời U23 mà nó cho U19 sang đá, còn gọi giả vờ là U23. Vậy là ở mức độ quốc gia thằng này cũng dùng hàng giả, hàng nhái để chơi ta. Chuyện này làm tôi nhớ lại một chuyện vài năm trước. Không biết sao dạo ấy máy bay các hãng hàng không Mỹ rớt liên tục, mà Mỹ là quê hương của hãng Boeing nổi tiếng. Trong khi đó Tàu nó làm được máy bay, phóng được tàu vũ trụ. Bộ phận gián điệp kinh tế của FBI và CIA vào cuộc, tìm ra nguyên nhân sau. Chả là hồi đó giá dầu tăng cao, các hãng HK Mỹ tiết kiệm chi phí bảo dưỡng máy bay bằng cách dùng thiết bị và linh kiện của Tàu, Đài Loan để thay thế cho rẻ, còn Tàu thì lúc ấy đang thặng dư mậu dịch với toàn thế giới lên rất lắm tiền, lên xài toàn hàng hiệu Mỹ, lên làm đủ mọi thứ trên trời như trên, thành công cả. Vậy là Máy bay Mỹ sài linh kiện Tàu--> rơi, tàu Vũ Trụ, phi cơ Tàu, dùng linh kiện Mỹ --> bay khỏe. Sau vụ này Mỹ mới thấm câu "Tiền nào của nấy" và "đồ Tàu", từ đó máy bay bớt rơi hẳn. Trở lại trận bóng, trước đó mấy ngày các quan chức và đội tuyển U23 ta mời U23 đội bạn dự tiệc chiêu đãi tại một nhà hàng sang trọng, và tất nhiên trong các món cao lương mỹ vị và đắt tiền không thể không có thực phẩm nhập khẩu từ Trung Quốc, có thể là hải sản đông lạnh, một loại gia vị, hay có cái gì đó trong các món hầm ..v..v.., mà sau đó tất cả mọi người tham dự hôm đó bị Tào tháo rượt một trận tá hỏa. Người nhà ta do có kinh nghiệm lên chỉ xài Becberin, Biseton, orezon, hoặc các thứ thuốc tây khác. Còn các bạn Tàu, sẵn tinh thần quốc gia cao độ lại sẵn có các Viện Đông Y Trung Quốc lên các bạn vào đó chữa, với lời hứa, dứt cơn nhanh và lại còn khỏe hơn trước. Và kết quả như ta thấy U23 Tàu tuy trẻ nhưng thằng nào thằng đấy mặt mũi già câng, thâm hiểm thế mà hôm ấy khi vào trận chỉ biết chạy hùng hục như trâu húc mả, mặt mũi vô hồn, ngu ngơ thấy tệ. Còn bên ta tuy thể hình, thể lực yếu hơn cộng thêm ảnh hưởng của cơn bệnh nhưng đá rất có nét, tấn công sắc sảo, phòng thủ hiệu quả và thắng trận.
      Còn các cụ nhà ta ngoài chuyện bị nó đô hộ trên dưới 1000 năm, chắc nhiều lần bị chơi khăm, bực quá lên mỗi lần cứ vô nhà xí do ăn phải thực phẩm bẩn (có cái của Tàu, cái không) lại lôi thằng Tào Tháo ra réo.
      Bây giờ, đảo thì nó chiếm rồi, trên đất liền, cứ dự án lớn nào là nó thầu hết, cực đông (trà cổ) thì nó thuê 50 năm, cực Bắc thì đóng cọc cắt xén, cử dân sang canh tác hộ, cao điểm Tây nguyên thì có vài chục nghìn mắt một mí xủn xẻng điếc cả tai voi. Hàng hóa "made in china" thì ngập thị trường. Ngoài biển thì tàu chìm, tàu nổi, máy bay lượn như ruồi. Không nói nhưng chóp bu, tướng tá nhà ta chắc nhìn cũng xanh mặt, bây giờ đất đai, tiền của nhiều, đánh nhau thì chết. Tiếc lắm.
Vậy nên, ngoài réo thằng Tào Tháo ra chửi thử hỏi còn làm được gì nó. Hóa ra ở ta AQ là rất , rất nhiều
(*) Một câu trong truyện ngắn của Nam Cao.
Chủ Nhật, ngày 08 tháng 11 năm 2009
__Bài hát “Bà tôi” muốn nói điều gì?
Bà tôi đưa tôi ra đầu làng một mình bà đội cả trời nắng to
Này là gió cuốn mây trôi đưa tôi về làng
Này là bóng nắng liêu xiêu theo tôi đường làng
Làng tôi quanh co quanh co quanh co quanh co
Bà tôi đưa tôi ra đầu làng một mình bà đội cả trời nắng to
Này là gió cuốn mây trôi đưa tôi về làng
Này là bóng nắng liêu xiêu theo tôi đường làng
Làng tôi quanh co quanh co quanh co có sợi rơm khô
Nhớ làng tôi từng dòng mương xanh bay bay bay bay
Nhớ bà tôi một trăm năm rồi ngọn cỏ hóa mây trời
Cười cười một chuỗi trời thử bụng ta
Có mùa thóc lép lợp trên mái nhà
Có mùa hoa cà tự nhiên tím tái
Bà ví lông gà vàng như vườn cải
Ông ví mặt trời như lời mối lái
Ai ví tình yêu như trò nghịch dại
Bà lên Kẻ chợ có buồn được đâu
Ra về lúc lắc héo mòn một xâu
Ra về lúc lắc héo mòn một xâu
Chiều nay tôi đưa bà ra đầu làng, đầu làng mình chợt nổi trận gió to
Chiều nay tôi đưa bà ra đầu làng, đầu làng mình chợt nổi trận gió to
Chiều nay tôi đưa bà ra đầu làng, đầu làng mình chợt nổi trận gió to
Chiều nay tôi đưa bà ra đầu làng, đầu làng mình chợt nổi trận gió to

Thứ Tư, ngày 04 tháng 11 năm 2009
no man land
Một sáng thức dậy
Nằm giữa cánh đồng
Bỗng thấy trên không
Ngập tràn bụi đỏ
Đôi quạ bên đó
Vụt ngang bên đồi
Quàng quạc chơi vơi
Giữa đời hoang vắng
Bầu trời không nắng
Mặt đất không cây
Loang lổ lấp đầy
Có còn đau khổ?
Một vành mây trắng
Lơ lửng giữa trời
Gió thổi không trôi
Ôi!, người, tội nghiệp
Thứ Ba, ngày 03 tháng 11 năm 2009
...haiku...
Suốt năm tháng bốn mùa
Lấp ló chỗ ngã tư
Sưu tầm lời chửi rủa
---
Tòa xử tham nhũng
Quần chúng đứng trông
Đảng viên ngồi đó
---
Người bạn thủ đô
Về thăm thành phố
"Ồ, chim sẻ"
---
Hai bờ sông
Không bóng cây
Toàn cửa cống
---
Giữa cánh đồng
Bát ngát mênh mông
Cao cao Lò gạch
---
Ngừng hót trong lồng
Tóe lửa mắt trông
Mấy thằng mua súng
---
Ăn dở bánh đa
Xa xanh mấy bóng
Nhảy cẫng dọn hàng
---
hình bên: Nhà mặt phố bên sông Kim Ngưu, Hà Nôi, được mắc màn để bớt mùi, tránh bụi và ruồi muỗi

markdown:
![ ](http://3.bp.blogspot.com/_Cc5p7J3DUDo/SxNcbBINhdI/AAAAAAAAAMM/JvhXRRAkyEI/s400/tacnuoc-liem.jpg)
![ ](http://3.bp.blogspot.com/_Cc5p7J3DUDo/SxNcbBINhdI/AAAAAAAAAMM/JvhXRRAkyEI/s400/tacnuoc-liem.jpg)
Dân chủ từ trên xuống là một khái niệm xuất sắc, chỉ có ở ta. Số là Đảng và nhà nước có chủ trương trao quyền tự quyết cho nhân dân khi bầu chính quyền cơ sở ở cấp phường, xã. Cái này là học của Tàu, bọn này trao quyền cho nhân dân đã đến cấp thành phố. Nói là trao quyền thực ra chỉ là quyền được bầu cử tự do lãnh đạo của cấp ấy. Và một vị chức sắc của ban tuyên giáo trung ương nói là, sự việc này là thí điểm của mô hình dân chủ từ dưới lên. Thật dễ hiểu, người dân được quyền chọn cho mình Chủ tịch xã,được quyền chọn ra người xứng đáng nhất để phục vụ cho lợi ích của mình, tuy nhiên hội đồng nhân dân lại không được thành lập. Và vị này nói thêm, các cấp còn lại và từ xưa đến nay nước ta theo mô hình "Dân chủ từ trên xuống". Cái hay, cái sáng tạo là chỗ này. Từ trên xuống nghĩa là, bầu thì cứ bầu, nhưng ai trúng là do trên nó đặt chỗ. Bầu chỉ để tiêu bớt tiền ngân sách thôi, chi phí chắc chắn không nhỏ. Và tất nhiên , một ông "Chẳng may" trúng chức thì đố có dám làm trái thằng đưa mình lên, quyền lợi của dân thì có nghĩa gì? quyền lợi của cấp trên mới là quan trọng. Còn ông được dân bầu, làm quan tất phải nhìn lên nhìn xuống, nhưng đã được dân chọn, nhất không thể là loại tham lam ngu xuẩn được, càng không thể là loại bán đất bán nước được.
    Cái hay là như vậy, các ông chủ của đất nước - nhân dân được nô bộc của mình- bên dưới- cai quản, nhưng lại bị hưởng chế độ dân chủ từ trên xuống do bên dưới, công bộc của dân, đặt ra. Trên cho gì, dưới được lấy, trên lấy gì, dưới mất đấy, dưới kêu, trên thích thì nghe, không thích thì bịt tai lại, mà nói nhiều quá là ăn đập, còn làm tới là bị xử ngày, cảnh sát và các lực lượng vũ trang lương cao luôn trung thành với "nô bộc".
    Từ nãy giờ, cứ trên trên, dưới dưới, rồi chủ chủ, tớ tớ, rồi thì chủ thì bị nô bộc nó đập, nó cai quản... loạn hết cả lên, chả hiểu gì cả. Nói tóm lại dân chủ từ trên xuống có dân chủ không, không biết đâu mà lần, có lẽ vì lý do này mà ông chức sắc tuyên giáo kia mới thốt ra miệng cụm từ này "Dân chủ" nhưng là "Dân chủ từ trên xuống". Chế độ mà hiển nhiên người được chọn (bầu)ra sẽ luôn bảo vệ quyền và lợi ích cho tầng lớp thiểu số quan chức và người giàu. Và dĩ nhiên những từ như chuyên chế, phong kiến hay độc tài ... không thể hay bằng "Dân chủ từ trên xuống"
---
hình bên:Tát nước - Nguyễn Trung Liêm, giải nhì cuộc thi biếm họa lần 1

WARC-Type: response

Content-Type: application/http; msgtype=response

X-XSS-Protection: 1; mode=block

Server: GSE

Cache-Control: private, max-age=0

X-Content-Type-Options: nosniff

Content-Type: text/html; charset=UTF-8


text:
Dự án tiêu biểu
Mẫu thiết kế kiến trúc biệt thự Vinhomes Riverside phong cách mới
Ngắm mẫu thiết kế kiến trúc biệt thự Hoa Anh Đào – Vinhomes Riverside
Thiết kế nội thất biệt thự Vinhomes Riverside – Biệt thự Hoa Phượng
Thiết kế nội thất biệt thự Vinhomes Riverside - Biệt thự Anh Đào 8.37
Thiết kế nội thất biệt thự Vinhomes Riverside - Nhà chị Thủy
Thiết kế nội thất biệt thự Hoa Lan – Nhà anh Quang
Thiết kế nội thất biệt thự Vinhomes Riverside – Nhà anh Hải
Thiết kế nội thất biệt thự Hoa Sữa – nhà anh Việt Anh
Thiết kế nội thất biệt thự Hoa Anh Đào – Nhà Anh Tùng
Dự án Vip
Tin tức
- Zoom cận cảnh không gian sống sang trọng trong thiết kế nội thất biệt thự Ciputra
- 6 cách để bài trí nội thất phòng ngủ nhỏ ấn tượng
- Nội thất biệt thự cao cấp thể hiện đẳng cấp gia chủ
- Ngất ngây với những mẫu thiết kế biệt thự đẹp đầy lôi cuốn
- Đẳng cấp hơn với mẫu nội thất biệt thự hiện đại đầy sang trọng
- Khám phá những mẫu phòng bếp biệt thự “hút hồn” người xem

markdown:
Dự án tiêu biểu
[](http://thietkenoithatbietthuvincomvillage.com/mau-thiet-ke-kien-truc-biet-thu-vinhomes-riverside-phong-cach-moi/)
![ kien-truc-chi-thuy (2)](http://thietkenoithatbietthuvincomvillage.com/wp-content/uploads/2016/01/kien-truc-chi-thuy-2.jpg)
### Mẫu thiết kế kiến trúc biệt thự Vinhomes Riverside phong cách mới
[](http://thietkenoithatbietthuvincomvillage.com/ngam-mau-thiet-ke-kien-truc-biet-thu-hoa-anh-dao-vinhomes-riverside/)
![ kien-truc-chi-nga (1)](http://thietkenoithatbietthuvincomvillage.com/wp-content/uploads/2016/01/kien-truc-chi-nga-1.jpg)
### Ngắm mẫu thiết kế kiến trúc biệt thự Hoa Anh Đào – Vinhomes Riverside
[](http://thietkenoithatbietthuvincomvillage.com/thiet-ke-noi-that-biet-thu-vinhomes-riverside-biet-thu-hoa-phuong/)
![ a-lam](http://thietkenoithatbietthuvincomvillage.com/wp-content/uploads/2015/12/a-lam.jpg)
### Thiết kế nội thất biệt thự Vinhomes Riverside – Biệt thự Hoa Phượng
[](http://thietkenoithatbietthuvincomvillage.com/thiet-ke-noi-that-biet-thu-vinhomes-riverside-biet-thu-anh-dao-8-37/)
![ chi-nga](http://thietkenoithatbietthuvincomvillage.com/wp-content/uploads/2015/12/chi-nga.jpg)
### Thiết kế nội thất biệt thự Vinhomes Riverside - Biệt thự Anh Đào 8.37
[](http://thietkenoithatbietthuvincomvillage.com/thiet-ke-noi-that-biet-thu-vinhomes-riverside-nha-chi-thuy/)
![ chi-thuy](http://thietkenoithatbietthuvincomvillage.com/wp-content/uploads/2015/12/chi-thuy.jpg)
### Thiết kế nội thất biệt thự Vinhomes Riverside - Nhà chị Thủy
[](http://thietkenoithatbietthuvincomvillage.com/thiet-ke-noi-that-biet-thu-hoa-lan-nha-anh-quang/)
![ a-quang](http://thietkenoithatbietthuvincomvillage.com/wp-content/uploads/2015/12/a-quang.jpg)
### Thiết kế nội thất biệt thự Hoa Lan – Nhà anh Quang
[](http://thietkenoithatbietthuvincomvillage.com/thiet-ke-noi-that-biet-thu-vinhomes-riverside-nha-anh-hai-2/)
![ a-hai](http://thietkenoithatbietthuvincomvillage.com/wp-content/uploads/2015/06/a-hai.jpg)
### Thiết kế nội thất biệt thự Vinhomes Riverside – Nhà anh Hải
[](http://thietkenoithatbietthuvincomvillage.com/thiet-ke-noi-biet-thu-hoa-sua-nha-anh-viet-anh/)
![ a-viet-anh](http://thietkenoithatbietthuvincomvillage.com/wp-content/uploads/2015/12/a-viet-anh.jpg)
### Thiết kế nội thất biệt thự Hoa Sữa – nhà anh Việt Anh
[](http://thietkenoithatbietthuvincomvillage.com/thiet-ke-noi-biet-thu-hoa-anh-dao-nha-anh-tung/)
![ a-tung](http://thietkenoithatbietthuvincomvillage.com/wp-content/uploads/2015/12/a-tung.jpg)
### Thiết kế nội thất biệt thự Hoa Anh Đào – Nhà Anh Tùng
Dự án Vip
### Tin tức
-
[Zoom cận cảnh không gian sống sang trọng trong thiết kế nội thất biệt thự Ciputra](http://thietkenoithatbietthuvincomvillage.com/zoom-can-canh-khong-gian-song-sang-trong-trong-thiet-ke-noi-that-biet-thu-ciputra/)
-
[6 cách để bài trí nội thất phòng ngủ nhỏ ấn tượng](http://thietkenoithatbietthuvincomvillage.com/6-cach-de-bai-tri-noi-that-phong-ngu-nho-an-tuong/)
-
[Nội thất biệt thự cao cấp thể hiện đẳng cấp gia chủ](http://thietkenoithatbietthuvincomvillage.com/noi-that-biet-thu-cao-cap-the-hien-dang-cap-gia-chu/)
-
[Ngất ngây với những mẫu thiết kế biệt thự đẹp đầy lôi cuốn](http://thietkenoithatbietthuvincomvillage.com/ngat-ngay-voi-nhung-mau-thiet-ke-biet-thu-dep-day-loi-cuon/)
-
[Đẳng cấp hơn với mẫu nội thất biệt thự hiện đại đầy sang trọng](http://thietkenoithatbietthuvincomvillage.com/dang-cap-hon-voi-mau-noi-that-biet-thu-hien-dai-day-sang-trong/)
-
[Khám phá những mẫu phòng bếp biệt thự “hút hồn” người xem](http://thietkenoithatbietthuvincomvillage.com/kham-pha-nhung-mau-phong-bep-biet-thu-hut-hon-nguoi-xem/)

WARC-Truncated: length

Server: Apache

Connection: close