text:
- 92 trang
- Lượt xem: 95
- Download: 50
Giáo trình Lý thuyết thuật toán
Chia sẻ: augi16
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.
Thể loại:Khoa Học Tự Nhiên » Toán học
Chủ đề liên quan:
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=0<max=4 nên không làm gì thực hiện 2 phép tính x3=9>max=4 nên max:=9 thực hiện 1 phép tính x4=1<max=9 nên không làm gì thực hiện 1 phép tính x5=5<max=9 nên không làm gì ⇒Tổng cộng thực hiện: 6 phép tính * Xét bộ dữ liệu vào e2={2, 7, 8, 11, 17} ta có: lA(e2)=8 tA(e2)=1+4.2 = 9 Như vậy với e1≠ e2 chi phí xử lý của A trên e1 và e2 là khác nhau. b) Các khái niệm về độ phức tạp của thuật toán Độ phức tạp trong trường hợp xấu nhất Cho một thuật toán A với đầu vào n, khi đó: - Độ phức tạp về bộ nhớ trong trường hợp xấu nhất được định nghĩa là: LA(n) = max{lA(e)║│e│≤n} Tức là chi phí lớn nhất về bộ nhớ. Trong ví dụ trên: Dữ liệu vào: n+1, ra:1, phụ:1 nên LA(e)=n+3. - Độ phức tạp thời gian trong trường hợp xấu nhất được định nghĩa là : TA(n) = max{tA(e)║│e│≤n} Tức là chi phí lớn nhất về thời gian. 7
- 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<n. Để thành lập phương trình đệ quy ta căn cứ vào chương trình đệ quy. Ví dụ 5: Hàm tính giai thừa viết bằng giải thuật đệ quy sau: Function Giai_thua(n:Integer):Integer; Begin If n=0 then Giai_thua:=1 Else Giai_thua:=n*Giai_thua(n-1); 10
- 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 m<n vào phía phải của phương trình cho đến khi tất cả T(m) với m>1 đượ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
Tài liệu liên quan

markdown:
92 trang
Lượt xem: 95
Download: 50
# Giáo trình Lý thuyết thuật toán
Chia sẻ:
[augi16](http://tailieu.vn/user/augi16)
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)
![](images/graphics/blank.gif)
## Thể loại:
[Khoa Học Tự Nhiên](http://tailieu.vn/khoa-hoc-tu-nhien/)» [Toán học](http://tailieu.vn/khoa-hoc-tu-nhien/toan-hoc/)
## Chủ đề liên quan:
**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=0<max=4 nên không làm gì thực hiện 2 phép tính x3=9>max=4 nên max:=9 thực hiện 1 phép tính x4=1<max=9 nên không làm gì thực hiện 1 phép tính x5=5<max=9 nên không làm gì ⇒Tổng cộng thực hiện: 6 phép tính * Xét bộ dữ liệu vào e2={2, 7, 8, 11, 17} ta có: lA(e2)=8 tA(e2)=1+4.2 = 9 Như vậy với e1≠ e2 chi phí xử lý của A trên e1 và e2 là khác nhau. b) Các khái niệm về độ phức tạp của thuật toán Độ phức tạp trong trường hợp xấu nhất Cho một thuật toán A với đầu vào n, khi đó: - Độ phức tạp về bộ nhớ trong trường hợp xấu nhất được định nghĩa là: LA(n) = max{lA(e)║│e│≤n} Tức là chi phí lớn nhất về bộ nhớ. Trong ví dụ trên: Dữ liệu vào: n+1, ra:1, phụ:1 nên LA(e)=n+3. - Độ phức tạp thời gian trong trường hợp xấu nhất được định nghĩa là : TA(n) = max{tA(e)║│e│≤n} Tức là chi phí lớn nhất về thời gian. 7
- 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<n. Để thành lập phương trình đệ quy ta căn cứ vào chương trình đệ quy. Ví dụ 5: Hàm tính giai thừa viết bằng giải thuật đệ quy sau: Function Giai_thua(n:Integer):Integer; Begin If n=0 then Giai_thua:=1 Else Giai_thua:=n*Giai_thua(n-1); 10
- 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 m<n vào phía phải của phương trình cho đến khi tất cả T(m) với m>1 đượ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
![](images/graphics/blank.gif)
## Tài liệu liên quan

Server: Apache/2.2.3 (CentOS)


text:
GIỚI THIỆU TRƯỜNG THCS THỤY SƠN 15:38 | 28/02/12
Tên trường: Trường THCS Thụy Sơn
Địa chỉ: Thụy Sơn - Thái Thụy – Thái Bình.
Điện thoại: 0363.855.455
Email: thuyson2@.thaithuy.edu.vn
DI TÍCH LỊCH SỬ, VĂN HÓA CẤP QUỐC GIA ĐỀN HẠ ĐỒNG
1. Thông tin chung về di tích lịch sử, văn hóa cấp quốc gia trên địa bàn
1.1. Tên di tích: Đền Hạ Đồng
1.2. Loại công trình: Cấp quốc gia.
1.3. Loại di tích: Đền thờ
1.4. Đã xếp hạng di tích lịch sử, văn hóa cấp quốc gia theo quyết định số 1214/VHCB ngày 30 tháng 10 năm 1990.
1.5. Địa chỉ di tích: Thôn Hạ Đồng, xã Thụy Sơn, huyện Thái Thụy, tỉnh Thái Bình.
1.6. Ảnh di tích (từ 7 - 10 ảnh, trong đó có hình ảnh học sinh đang chăm sóc di tích; lưu ý: chọn chế độ ảnh có độ phân giải cao để ảnh có độ nét)
2. Tóm lược thông tin về di tích (khoảng 2 trang A4)
a.Vài nét về lịch sử- Văn hoá hương ấp Hạ Đồng.
Theo truyền thuyết, tổ khai cơ vùng đất phía tây Bến Tuần (nay thuộc xã Thụy Liên) là thân bào của phò mã Mai An Tiêm đời Hùng Vương quê vùng Đường Hào bộ lạc Dương Tuyền ( nay thuộc Mĩ Hào, tỉnh Hưng Yên) cụ Mai Công Phúc là bậc đại nhân, đại từ được Thục An Dương Vương mời về thành Cổ Loa ban cho tước lộc…Vì ước vọng dân có ruộng cày, khai hoá biên cương khắp vùng biên ải cụ đã xin vua đi tuần du khắp vùng Dương Tuyền ( Hải Dương), Lục Hải( Thái Bình), Nam Định và cả bộ Cửu Chân (Thanh Hoá). Khi tới cửa Thù Nương thấy có dải đất phù sa sát sông gần biển nhưng cao ráo đã dâng sớ xin dẫn con em đi khai mở, theo tấm mộc bài tìm được tại cánh đồng Đa Bối thôn Bái Thượng xã Thụy Phúc khắc năm Triệu Long thứ 12 (1269) thì cửa Trà Linh xưa là cửa Thù Nương. Buổi đầu gồm trai đinh họ Mai, họ Hà, sau đó họ Nguyễn, họ Trần, họ Đặng, họ Lê từ các nơi cùng về bạt sú, chặt lau, bạt cồn, san bãi lập động xá trên vùng cửa biển Diêm Điền gọi là Hạ Động ( nay là Hạ Đồng).
Đất lành chim đậu “ Địa phát thánh linh” tương truyền ngày 10-5 năm Mậu Dần Nguyễn Công làng Hạ Động sinh được trang ngọc nữ đặt tên là Cống Nương đẹp như ngọc, dáng tựa tiên sa. Vua An Dương Vương đi tuần thú vùng Lục Hải ghé bến Hạ Động thấy Cống Nương đẹp bèn đón về triều phong làm Hoàng phi và sinh hạ được hoàng tử Công Uy.
Từ thời thượng cổ Hạ Động đã nổi tiếng nhiều đình, nhiều miếu nhưng còn đơn sơ…sau đời Mạc sang đời Lê đã được xây dựng khang trang hơn. Năm 1788 cuộc tấn công phá chiến lũy Hạ Động của Hoàng Viết Tuyển và Nguyễn Như Thái đền, đình, chùa Hạ Động chìm trong biển lửa. Sang đầu chiều Nguyễn (1802) được dựng lại đơn sơ. Năm 1889 được lý trưởng bá hộ Ngô Các họp những người có chức sắc trong làng mở rộng khuôn viên của đình làng rộng 8 sào 5 thước và khuôn viên chùa rộng trên 1 mẫu, Linh Quang tự rộng tới 10 gian. Trong kháng chiến chống Pháp đền đã bị phá hủy nhiều, đến năm 1988 đã được phục hồi và tu sửa xây dựng lại 2 tòa đại bái, cung thờ Mai tướng công, dựng lăng đền hoàng tử Công Uy…
b. Các vị thờ tại đền Hạ Động. Hiện nay đền Hạ Đồng thờ 5 vị thần linh đó là: Mai Công Phúc, Nam Hải đại vương, hoàng phi Cống Nương, hoàng tử Công Uy và Công thần hộ quốc Đặng Công Kỳ.
- Tiểu sử bản cảnh thành hoàng Mai Công Phúc: Thần họ Mai tự Công Phúc sinh ngày 06-3 năm Mậu Dần đời Hùng Duệ Vương con cháu chi thứ phò mã Mai An Tiêm quê ấp Đường Hào, bộ Dương Tuyền từ nhỏ đã nổi tiếng thông minh học một biết mười. Lớn lên văn võ song toàn dân bộ lạc tôn làm thủ lĩnh. Khi Thục An Dương Vương được vua Hùng Duệ Vương truyền ngôi dời đô về Cổ loa muốn liên kế hiền tài gốc Lạc Việt đã mời Mai Công Phúc về kinh, phong làm lạc tướng phò tá Thục An Dương Vương. Một ngày Mai Công tới cửa Thù Nương vào sâu cách biển vài dặm có nhiều cồn cao, gò lớn, cây cối mọc chen như rừng dài rộng đến vài chục dặm xét có thể khai khẩn thành đất sinh tụ hàng trăm hộ liền dâng sớ xin vua cho mở ấp. Vua khen quan Lạc tướng có chí lớn, biết nhìn xa trông rộng nên chuẩn tấu. Quan Lạc tướng họ Mai lên Phong Châu, về Đường Hào vào Cửu Chân gọi con cháu họ Mai, ngoại tộc họ Hà quy tập về mở ấp vùng hà lưu sông đặt tên là Hạ Động. Chỉ qua vài năm mấy trăm mẫu đất được phát quang, đất chua mặn thành mật điền đời sống của dân được nâng lên. Ngày 10-8 năm Tân Tỵ, Mai Lạc tướng tạ thế được nhân dân làng Hạ Động lo hậu sự đàng hoàng. Đời vua Lê Cảnh Hưng gia ân khắp lượt phúc thần và Mai Công Phúc được vua phong là tuế thờ tự vân hành vũ thứ thiên quan hộ quốc cứu dân thượng đẳng tôn thần và hiện được thờ tại đền Hạ Đồng và là thành hoàng của làng.
- Nam Hải đại vương: Thần họ Thục tên Phán con cháu Lạc Long Quân cai quản vùng biển phía bắc, liền với biên giới Ai Lao. Đời Hùng vương thứ 18 là vua Hùng Duệ Vương không có con trai, vua cho là ý trời liền triệu Thục Phán về và trao ấn tín, Thục Phán đứng trên tảng đá thề “ Vâng theo ý trời, lời di huấn Triệu tổ Long Quân dù ngoại tộc nhưng sẽ trung thành với cơ nghiệp họ Hùng”. Hùng Duệ Vương băng hà, Thục Phán hợp nhất Âu Việt với Văn Lang( Lạc Việt) lập nước Âu Lạc, bầy tôi dâng hiệu An Dương Vương. Sau khi bị cha con Triệu Đà lừa và bị mất nước ông đã nhẩy xuống bể Nam Hải tự tử ngày 12-8. Các vua đời sau đã cấp sắc thần cho An Dương Vương là Nam Hải Đại Vương.
- Cống nương hoàng phi và hoàng tử Công Uy:
Cụ Nguyễn Công quê làng Hạ Động nếp nhà thuần hậu tổ phụ nối đời tu nhân tạo phúc ân đức trùm một vùng, lòng thành thấu đến thiên đình, Ngọc Hoàng sai thần Long vương cho công chúa đầu thai vào họ Nguyễn. Ngày 10-5 năm Đinh Mùi khuê phòng của phu nhân tự nhiên rực sáng, không gian đầy ắp khí thơm, họ Nguyễn sinh được quý nữ đặt tên là Cống Nương. Là trưởng nữ trong nhà Nguyễn Công rất yêu con gái dạy con đúng đạo, truyền đủ nghề, lớn lên xinh đẹp vô cùng. Bấy giờ Vua An Dương Vương đi tuần thú đến làng Hạ Động thấy có người con gái có sắc đẹp nghiêng nước, nghiêng thành ngỏ lời xin đón về cung và phong làm Hoàng phi. Ngày 12-7 năm Bính Thìn Hoàng phi sinh Hoàng tử đặt tên là Công Uy, lớn lên Hoàng Tử được Vua cha cho Cao Lỗ truyền võ nghệ và quan Lạc Hầu dạy nghi lễ, Hoàng tử học một biết mười. Bấy giờ Triệu Đà cất quân xâm lược nước ta, bị vua An Dương Vương đem nỏ thần đánh cho đại bại, Triệu Đà mang biểu xin cầu hòa, dạm hỏi công chúa Mị Châu cho Trọng Thủy. Vua hỏi hoàng tử Công Uy, hoàng tử thưa trước điện “ hai nước hiếu hòa thì tốt, hai nhà thông gia thì được còn cho Thái tử nước người làm rể thực chất chẳng khác gì đưa thám mã vào nhà, phúc họa khó lường…”. Sau khi thất thủ Vua An Dương Vương cùng con gái chạy chốn, hoàng tử Công Uy sai người đưa mẹ về nánh nạn tại Hạ Động rồi đem quân đi bảo vệ Vua cha. Khi tới cửa bể Quỳnh Lưu thì được tin Vua cha đã trẫm mình tại cửa biển Nam Hải, Hoàng tử cũng định nhẩy xuống biển từ tử, nhưng rồi nghĩ đến mẫu thân nên làm lễ cúng vua cha rồi rút quân về Hạ Động. Trọng Thủy sau khi giúp Triệu Đà đánh bại An Dương Vương biết vợ đã chết liền viết thư về Hạ Động xin lỗi Vương Phi và hoàng tử Công Uy nhưng bị Vương Phi xé thư và mắng tên phò mã phản phúc, còn Hoàng tử Công Uy đem quân đánh Trọng Thủy và bị quân Trọng Thủy phản công quân lính của hoàng tử bị chết trên cánh đồng Hạ Động, hoàng tử Công Uy liền thét lên “ nước mất con vua sao còn có thể sống, ta theo phụ hoàng đây” rồi rút gươm tuẫn tiết vào ngày 10 tháng chạp năm Bính Ngọ, vì đau buồn mà Hoàng phi lâm bệnh hơn 9 tháng sau Hoàng Phi cũng qua đời vào ngày 12 tháng 9 năm Đinh Mùi.
-Công thần hộ quốc Đặng Công Kỳ: Đặng Công Kỳ người Hạ Động đậu cử nhân võ trong niên hiệu Cảnh Hưng, từng làm võ quan giữ tuần An Lệnh cửa Diêm Điền sau được thăng chức Quản Bưu Đình. Tháng 6 năm Bính Ngọ (1786) Nguyễn Huệ đem quân Phú Xuân diệt họ Trịnh đàng ngoài, tiếp đó vua Lê Hiển Tông băng hà, Lê Chiêu Thống nối ngôi …theo lệnh trung ương hoàng đế Nguyễn Nhạc, Bắc Bình vương Nguyễn Huệ đem công chúa Ngọc Hân trở về Nam nên Bắc Hà rối loạn, Trịnh Bồng trở lại ép Lê Chiêu Thống phong vương, đất nước rơi vào cảnh chiến tranh nội bộ. Nghĩa quân của Quản Bưu Đình giữ thành Lũy Sành vào tận bản doanh Đình Đông Linh và Hạ Động. Ngày 10-7 năm ấy tướng quân Quản Bưu Đình được gọi hàng, ông thét lớn “ Tôi trung bất phò nhị chúa” rồi khoác áo xông vào tử chiến. Đời Nguyễn khen ông là bậc “ Giúp nước, cứu dân” năm Thành Thái thứ 4 và Khải Định thứ 9 có sắc phong thần liệt quan Quản Bưu Đình “ Hộ quốc cứu dân, lầm trước linh ứng, dực bảo trung hưng tôn thần”.
3. Một số hoạt động nhà trường đã và đang thực hiện chăm sóc di tích lịch sử, văn hóa nói trên
Năm học 2008-2009 Bộ giáo dục phát động phong trào thi đua: “ Xây dựng trường học thân thiện, học sinh tích cực” trong giai đoạn 2008-2013. Trong nội dung của phong trào thi đua có 5 nội dung trong đó có nội dung : “Học sinh tham gia tìm hiểu, chăm sóc và phát huy giá trị các di tích lịch sử, văn hóa, cách mạng ở địa phương”. Nhà trường đã yêu cầu các em học sinh viết bài tìm hiểu về di tích lịch sử qua các tiết ngoại khóa về môn GDCD để các em hiểu được di tích lịch sử ở địa phương từ đó các em có ý thức chăm sóc và bảo vệ.
Nhà trường đã giao cho chi đoàn chỉ đạo các em đội viên chăm sóc khu di tích lịch sử.
Các em học sinh ở khu vực Hạ Đồng được phân công hàng tuần ra quét dọn khu di tích lịch sử.
4. Đề xuất kiến nghị:
ĐC Hiệu trưởng cung cấp chính xác thêm các thông tin sau:
1. Họ và tên hiệu trưởng: Nguyễn Thị Hiệp .
Chuyên ngành đào tạo: ĐHSP khoa toán - năm tốt nghiệp đại học: 2008
ĐT cố định: 0363855895 ĐT Di động: 0979236278
Địa chỉ email: c2hiepthuyson
2. Họ và tên Tổng phụ trách Đội : Bùi Thị Thu Hằng
Chuyên ngành đào tạo ĐHVHNT năm tốt nghiệp: 2010.
ĐT cố định: ………………… ĐT di động: 01683993816
Địa chỉ email: c2hangthuyson.
3. Địa chỉ trường: Thôn Nhạo Sơn, xã Thụy Sơn, huyện Thái Thụy, tỉnh Thái Bình.
ĐT cố đinh: 0363855455.
HIỆU TRƯỞNG
(Ký tên)
Nguyễn Thị Hiệp
Trường THCS Thụy Sơn
Xin để lại Email, Thông tin liên hệ sau phần nội dung, Ban giám hiệu sẽ trả lời bạn sớm nhất!
Cảm ơn bạn rất nhiều!
© Bản quyền thuộc Phòng Giáo dục - Đào tạo Thái Thụy.
Xem tốt nhất ở độ phân giải 1024 x 768 pixel với trình duyệt IE7+, Firefox 2+, Google Chrome
Phát triển bởi DONGPHUONG JSC

WARC-Type: response

Content-Type: application/http; msgtype=response

Server: Apache

X-Powered-By: Servlet 2.5; JBoss-5.0/JBossWeb-2.1

Set-Cookie: COOKIE_SUPPORT=true; Expires=Sat, 22-Aug-2015 07:51:20 GMT; Path=/

Liferay-Portal: Liferay Portal Standard Edition 5.2.3 (Augustine / Build 5203 / May 20, 2009)

Content-Encoding: gzip

Connection: close


text:
Đang truy cập : 2
Hôm nay : 609
Tháng hiện tại : 29980
Tổng lượt truy cập : 2134739
Tác giả bài viết: Thiên Hương
Nguồn tin: www.lethuy.edu.vn
Theo dòng sự kiện
Xem tiếp...
Những tin mới hơn
Những tin cũ hơn
Tài khoản
Mật khẩu
© Website chính thức của Trường TH số 1 Hồng Thuỷ.
Địa chỉ: Hồng Thuỷ - Lệ Thuỷ - Quảng Bình
Điện thoại: 0523.950052
Developed by Ngọc Tình

WARC-Truncated: length

Content-Language: vi

Cache-Control: private, pre-check=0, post-check=0, max-age=0

Pragma: no-cache

Content-Encoding: x-gzip

Vary: Accept-Encoding

Set-Cookie: nv3c_Hdo5c_sess=51e650345e53d6a61e39ab19310fd556918874618; path=/; domain=.thso1hongthuy.edu.vn; HttpOnly

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


text:
Ngắm ảnh sex đẹp của em gái xinh Nhật Bản Aino Sishi đi tắm biển cởi quần chip khoe mông và bướm đẹp xinh của mình với những sợi lông mu đầy ấn tượng và hấp dẫn bạn nhé. Hy vọng em gái Nhật Bản này sẽ mang lại sự hài lòng cho bạn về vẻ đẹp ngây thơ của em ấy.
Đây là bộ ảnh sex của Aino Sishi trong danh sách diễn viên JAV đầy hấp dẫn sẽ được Tophinh.com cập nhật thường xuyên. Các bạn nhớ đón xem những bộ ảnh nóng bỏng đủ thể loại của các em gái xinh Nhật Bản Aino Sishi nhé.
Đầu tiên là bộ ảnh sex khoe mông gợi cảm đứng trên bờ biển đầy khêu gợi.
Gái xinh chân dài Nhật Bản cởi luôn cái quần chip của mình để show cái lồn đẹp hấp dẫn.
Ảnh đẹp em gái tạo dàng xì teen dễ thương.
Ngắm gái xinh với đôi chân thon đẹp mịn màng.
Em không mặc bikini đi tắm biển mà mặc những bộ đồ nội y sexy đầy gợi dục.
Hấp dẫn với bộ ảnh sex đẹp như thiên thần của em.
Ngắm thân thể đẹp đầy hấp dẫn.
Ảnh sex gái xinh Nhật Bản luôn được các chuyên gia phân tích là hot nhất thế giới.
Cô em từ từ show cái lồn của mình ra.
Xem ảnh sex đẹp khoả thân giữa trời, biên rộng mênh mông.
Ảnh sex tuyệt đẹp đầy khiêu khích của em Nhật Bản Aino Sishi, đón xem kho ANH SEX cùng Tophinh nhé bạn.

markdown:
## Ngắm ảnh sex đẹp của em gái xinh Nhật Bản Aino Sishi đi tắm biển cởi quần chip khoe mông và bướm đẹp xinh của mình với những sợi lông mu đầy ấn tượng và hấp dẫn bạn nhé. Hy vọng em gái Nhật Bản này sẽ mang lại sự hài lòng cho bạn về vẻ đẹp ngây thơ của em ấy.
Đây là bộ ảnh sex của Aino Sishi trong danh sách diễn viên JAV đầy hấp dẫn sẽ được Tophinh.com cập nhật thường xuyên. Các bạn nhớ đón xem những bộ ảnh nóng bỏng đủ thể loại của các em gái xinh Nhật Bản Aino Sishi nhé.
Đầu tiên là bộ
**ảnh sex** khoe mông gợi cảm đứng trên bờ biển đầy khêu gợi.
Gái xinh chân dài Nhật Bản cởi luôn cái quần chip của mình để show cái lồn đẹp hấp dẫn.
Ảnh đẹp em gái tạo dàng xì teen dễ thương.
Ngắm gái xinh với đôi chân thon đẹp mịn màng.
Em không mặc bikini đi tắm biển mà mặc những bộ đồ nội y sexy đầy gợi dục.
Hấp dẫn với bộ
*ảnh sex* đẹp như thiên thần của em.
Ngắm thân thể đẹp đầy hấp dẫn.
Ảnh sex gái xinh Nhật Bản luôn được các chuyên gia phân tích là hot nhất thế giới.
Cô em từ từ show cái lồn của mình ra.
Xem ảnh sex đẹp khoả thân giữa trời, biên rộng mênh mông.
Ảnh sex tuyệt đẹp đầy khiêu khích của em Nhật Bản Aino Sishi, đón xem kho
[ANH SEX](http://tophinh.com/anh-sex/) cùng Tophinh nhé bạn.

Content-Type: text/html

Set-Cookie: __cfduid=d97a554b8ce006397dc1856da9b6f07ac1408693916821; expires=Mon, 23-Dec-2019 23:50:00 GMT; path=/; domain=.tophinh.com; HttpOnly

Vary: User-Agent,Accept-Encoding

Server: cloudflare-nginx