Chủ nhật, Ngày 26 Tháng 3 Năm 2017
Kỷ niệm 107 năm Ngày Quốc tế Phụ nữ (08/3/1910 - 08/3/2017), 1977 năm Cuộc khởi nghĩa Hai Bà Trưng và Ngày Quốc tế Hạnh phúc 20/3
JV color JV color JV color
Joomla Templates and Joomla Extensions by JoomlaVision.Com
  • Truy Cập Tin Nhanh
Tổ chức cán bộ: Lịch thi tuyển viên chức năm học 2016-2017 - Monday, 20 Tháng 3 2017 09:34
Khảo thí & Kiểm định chất lượng: Tài liệu tập huấn thi thpt quốc gia 2017 - Thứ năm, 16 Tháng 3 2017 15:22
Giáo Dục Mầm Non: V/v họp định kỳ Ban hướng dẫn nghiệp vụ GDMN - Thứ ba, 14 Tháng 3 2017 09:36
Khảo thí & Kiểm định chất lượng: Công văn số 1804/UBND-VP: V/v điều chỉnh ngày thi tuyển sinh lớp 10 THPT năm học 2017-2018 - Thứ năm, 09 Tháng 3 2017 15:44
Khảo thí & Kiểm định chất lượng: Thông báo số 311/SGDĐT-KT&KĐCL: Môn thi, ngày thi tuyển sinh lớp 10 THPT năm học 2017-2018 - Thứ tư, 08 Tháng 3 2017 15:00
Giáo Dục Trung Học: Công văn số 302/SGDĐT-KHTC: V/v triển khai việc thực hiện mua sắm tập trung - Thứ tư, 08 Tháng 3 2017 08:55

THÔNG BÁO

newThông báo: new

- Lịch thi Vô địch tin học văn phòng cấp THPT tỉnh Bà Rịa-Vũng Tàu, năm học 2016-2017:
1. Buổi thi 01:
    Bắt đầu từ 8 giờ 00 đến 10 giờ 00 ngày 24/03/2017
2. Buổi thi 02:
    Bắt đầu từ 13 giờ 30 đến 15 giờ 30 ngày 24/03/2017
Địa điểm: Phòng máy vi tính 1-2-3 trường THPT chuyên Lê Quý Đôn
   Hội đồng coi thi và Học sinh dự thi Buổi 01 có mặt tại Hội trường B trường THPT chuyên Lê Quý Đôn lúc 7 giờ 00 ngày 24/03/2017 để làm lễ Khai mạc Cuộc thi
Bảng niêm yết danh sách học sinh dự thi: xem... 
Lịch thi tuyển viên chức năm học 2016-2017
- Thông báo: Lịch ôn tập kiến thức chung lúc 8h00 ngày 14/03/2017 tại trung tâm GDTX Bà Rịa
- Quyết định số 174/QĐ-SGDĐT ngày 08/03/2017 V/v Ban hành Quy trình tổ chức thi và sát hạch kỳ thi Tuyển dụng viên chức các đơn vị sự nghiệp giáo dục trực thuộc Sở Giáo dục và Đào tạo năm học 2016-2017
- Thông báo số 300/TB-SGDĐT ngày 07/03/2017 V/v  Kế hoạch và lịch thi thực hành thi tuyển dụng viên chức các đơn vị sự nghiệp trực thuộc Sở Giáo dục và Đào tạo năm học 2016-2017
- Thông báo số 203/TB-SGDĐT ngày 20/02/2017 Kế hoạch ôn tập, lịch thi kỳ thi tuyển dụng viên chức các đơn vị sự nghiệp trực thuộc Sở Giáo dục và Đào tạo năm học 2016-2017
- Danh sách thí sinh nmiễn thi môn Tin học, ngoại ngữ kỳ thi tuyển viên chức các đơn vị trực thuộc
- Thông báo số 240/TB-SGDĐT ngày 24/02/2017 V/v thí sinh đủ kiều kiện và không đủ điều kiện dự thi viên chức các đơn vị sự nghiệp giáo dục trực thuộc Sở Giáo dục và Đào tạo tỉnh Bà Rịa-Vũng Tàu năm học 2016-2017
- Kế hoạch  số 239/KH-SGDĐT ngày 27/02/2017 V/v Thi tuyển viên chức các đơn vị sự nghiệp giáo dục trực thuộc Sở Giáo dục và Đào tạo tỉnh Bà Rịa-Vũng Tàu năm học 2016-2017
- Lịch thi môn Tin học, Ngoại ngữ: xem chi tiết ...
- Thông báo 174/SGDĐT-TCCB, ngày 13 tháng 02 năm 2017 V/v thông báo số lượng hồ sơ thi tuyển dụng viên chức thời điểm 9 giờ 00 phút ngày 13/02/2017
- Công văn số 1333/SGDĐT-GDTrH: V/v ban hành tiêu chí đánh giá, xếp loại giờ dạy của giáo viên từ năm học 2016 – 2017

Kế hoạch thời gian năm học 2016-2017: Download
- Công văn số 2649/BNV-CCVC: V/v chế độ thôi việc, thuyên chuyển của viên chức
- Công văn số 6255/UBND-SNV: V/v thuyên chuyển viên chức giữa các cơ quan, đơn vị thuộc tỉnh Bà Rịa-Vũng Tàu

Tài liệu hướng dẫn:
- Bài thể dục Buổi sáng: tải về ...
- Bài thể dục Giữa giờ: tải về ...
- Bài võ thuật cổ truyền: tải về ...

Video trao đổi chuyên môn của Thứ trưởng Bộ Giáo dục và Đào tạo: xem tại đây ...
Video Thứ trưởng BGDĐT trả lời các câu hỏi của giáo viên: xem tại đây ...

Phần mềm dùng để họp trực tuyến Trueconf: Download
Phiên bản dùng cho thiết bị di động: Android  hoặc  IOS

- Chấn chỉnh một số nội dung trong việc triển khai phần mềm VNEdu: xem
chi tiết ...
- Các trường có nhu cầu xây dựng website miễn phí liên hệ Phòng CNTT-TBGD Sở GD&ĐT để thực hiện.
- Tài liệu vnEdu: Download

Hướng dẫn quy trình sử dụng Eoffice - Văn phòng điện tử dành cho ngành Giáo dục và Đào tạo tỉnh Bà Rịa - Vũng Tàu.
Tải về ... 
Đề nghị cài lại Eoffice phiên bản 6.1.23. Download

Công văn số
754/UBND: V/v chấm dứt tình trạng dạy thêm, học thêm đối với Giáo dục Tiểu học

BKAV phiên bản client: Download

Thông tin cuộc thi sáng tạo KHKT các cấp

Website thi KHKT tỉnh Bà Rịa-Vũng Tàu: http://thikhoahockythuat.bariavungtau.edu.vn/

Mô hình trường học mới Việt Nam

mohinhmoi

Tài liệu lớp 6 năm học 2015-2016: tải về tại đây ...
Tài liệu hướng dẫn dạy của của giáo viên: tải về ...
Tài liệu tham khảo về các mức đánh giá kiểm tra các bộ môn: tải về ...

THÔNG BÁO TUYỂN SINH CĐ-ĐH 2017

ts2017

DIỄN ĐÀN: DÂN HỎI - SỞ GDĐT TRẢ LỜI

hoi-dap_1

DỊCH VỤ CÔNG TRỰC TUYẾN

Dichvucong

QUẢN LÝ NHÂN SỰ PMIS

pmis Tải bộ cài đặt PMIS: tại đây ...

CÔNG ĐOÀN NGÀNH

CDN2015

THÔNG TIN KHEN THƯỞNG - XỬ PHẠT

- Quyết định số 1507/QĐ-BGDĐT: về việc tặng bằng khen
- Quyết định số 715/QĐ-SGDĐT: về việc tặng Giấy khen cho các trường THPT đạt kết quả cao trong kỳ thi tuyển sinh Đại học năm 2014
- Quyết định số 1647/QĐ-UBND: về việc tặng bằng khen
- Quyết định số 1438/QĐ-UBND: về việc tặng bằng khen
- Quyết định số 1624/QĐ-UBND: về việc tăng cờ thi đua và danh hiệu Chiến sĩ thi đua cấp tỉnh

HỘP THƯ GÓP Ý

Sở Giáo dục và Đào tạo tỉnh Bà Rịa – Vũng Tàu hân hạnh được tiếp nhận những ý kiến đóng góp của quý Thầy cô giáo, quý phụ huynh học sinh và các em học sinh về lĩnh vực Giáo dục và Đào tạo của tỉnh Bà Rịa – Vũng Tàu với mục đích làm cho ngành giáo dục tỉnh nhà ngày càng tốt hơn.
Nội dung góp ý xin mail về địa chỉ:
Xin trân trọng cám ơn!

Văn bản về xử phạt vi phạm hành chính trong lĩnh vực giáo dục:
Joomla Templates and Joomla Extensions by JoomlaVision.Com
  • Web liên kết

  • Tin mới

  • Tin xem nhiều

Joomla Templates and Joomla Extensions by JoomlaVision.Com
  • Góc học tập

  • Lập trình

  • Báo chí

Thông tin liên hệ

cqmoi02
Sở Giáo Dục & Đào Tạo tỉnh Bà Rịa - Vũng Tàu
Địa chỉ: Khối B3 Khu Trung tâm hành chính-chính trị tỉnh; số 198 đường Bạch Đằng, phường Phước Trung, Thành phố Bà Rịa, tỉnh Bà Rịa-Vũng Tàu
Quản trị Website: Phòng Công nghệ Thông tin

Thống kê truy cập

mod_vvisit_countermod_vvisit_countermod_vvisit_countermod_vvisit_countermod_vvisit_countermod_vvisit_countermod_vvisit_countermod_vvisit_countermod_vvisit_counter
mod_vvisit_counterHôm nay11463
mod_vvisit_counterHôm qua23914
mod_vvisit_counterTuần này175092
mod_vvisit_counterTuần trước183971
mod_vvisit_counterTháng này632638
mod_vvisit_counterTháng trước591714
mod_vvisit_counterTất cả35712069
Hiện có 1282 khách Trực tuyến
Home CNTT Lập Trình Phương pháp quy hoạch động

Phương pháp quy hoạch động

In

     tinhoche11_06

 Thực hiện công số 534/SGDĐT-VP: V/v tập huấn kỹ năng lập trình và công tác bồi dưỡng học sinh giỏi Tin học trong hè 2011. Từ ngày 20/7/2011 đến 29/7/2011, tại trường THCS Huỳnh Khương Ninh đã diễn ra 2 đợt tập huấn dành riêng cho 2 khối THCS (20/7/2011 đến 24/7/2011) và THPT (25/7/2011 đến 29/7/2011) do Sở Giáo dục và Đào tạo chủ trì. Nhân dịp này tôi xin chia sẽ với các đồng nghiệp một bài viết sau:

Phương pháp quy hoạch động:

    Phương pháp quy hoạch động dùng để giải bài toán tối ưu có tính chất đệ quy, tức là việc tìm phương án tối ưu cho bài toán đó có thể đưa về tìm phương án tối ưu của một số hữu hạn các bài toán con. Đối với nhiều thuật toán đệ quy, nguyên lý chia để trị (devide and conquer) thường đóng vai trò chủ đạo trong việc thiết kế thuật toán. Để giải quyết một bài toán lớn, ta chia nó thành nhiều bài toán con cùng dạng với nó để có thể giải quyết độc lập. Trong phương pháp quy hoạch động, nguyên lý này càng được thể hiện rõ: Khi không biết cần phải giải bài những toán con nào, ta sẽ đi giải quyết tất cả các bài toán con và lưu trữ những lời giải hay đáp số của chúng với mục đích sử dụng lại theo một sự phối hợp nào đó để giải quyết những bài toán tổng quát hơn. Đó chính là điểm khác nhau giữa Quy hoạch động và phép đệ quy và cũng là nội dung Phương pháp quy hoạch động:tinhoche11_03

 


+Phép đệ quy bắt đầu từ bài toán lớn phân rã thành nhiều bài toán con và đi giải từng bài toán con đó. Việc giải từng bài toán con lại đưa về phép phân rã tiếp thành nhiều bài toán con nhỏ hơn và lại đi giải quyết bài toán nhỏ hơn đó bất kể nó đã được giải hay chưa.
+Quy hoạch động bắt đầu từ việc giải tất cả các bài toán nhỏ nhất (bài toán cơ sở) để từ đó từng bước giải quyết những bài toán lớn hơn, cho tới khi giải được bài toán lớn nhất (bài toán ban đầu).

Sau đây ta sẽ xét một ví dụ đơn giản và rất quen thuộc:
Ví dụ: Dãy Fibonacci là dãy số nguyên dương được định nghĩa như sau:
F[1]=F[2]=1;
Với mọi i: 3<=i: F = F[i-1] + F[i-2]
Hãy tính F[6]

Xét hai cách cài đặt chương trình bằng C++:

 

Code:

* Cách 1 (dùng đệ quy):tinhoche11_08


int F(int i)
{
    if (i<3)
        return 1;
    else
        return F(i-1) + F(i-2);
}
int main()
{
    cout<<F(6);
    return 0;
}

 

Code:

 * Cách 2 (dùng quy hoạch động):tinhoche11_09

//Khai báo biến toàn cục: i

int i;

int main()
{
    F[1]=1; F[2]=1;
    for (int i=3;i<=6;++i)
        F[i]=F[i-1]+F[i-2];
    cout<<F[6];    
    return 0;
}
 

 

Trong cách 1, ta viết một hàm đệ quy F(i) để tính số Fibonacci thứ i. Chương trình chính gọi F(6), nó sẽ gọi tiếp F(5) và F(4) để tính … Quá trình tính toán có thể vẽ như cây dưới đây. Ta nhận thấy để tính F(6) nó phải tính 1 lần F(5), 2 lần F(4), 3 lần F(3), 5 lần F(2), 3 lần F(1).

 

 

tinhoche11_012

 

Cách 2 thì không như vậy. Trước hết nó tính sẵn F[1] và F[2], từ đó tính tiếp F[3], lại tính tiếp được F[4], F[5], F[6]. Đảm bào rằng mỗi giá trị Fibonnaci chỉ phải tính 1 lần.

 

(Cách 2 còn có thể cải tiến thêm nữa, chỉ cần dùng 3 biến tính lại giá trị lẫn nhau).

tinhoche11_04Trước khi áp dụng phương pháp quy hoạch động ta phải xét xem phương pháp đó có thỏa mãn những yêu cầu dưới đây hay không:
+Bài toán lớn phải phân rã được thành nhiều bài toán con, mà sự phối hợp lời giải của các bài toán con đó cho ta lời giải của bài toán lớn.
+Vì quy hoạch động là đi giải tất cả các bài toán con, nên nếu không đủ không gian vật lý lưu trữ lời giải (bộ nhớ, đĩa,…) để phối hợp chúng thì phương pháp quy hoạch động cũng không thể thực hiện được.
+Quá trình từ bài toán cơ sở tìm ra lời giải bài toán ban đầu phải qua hữu hạn bước.

Các khái niệm:
+Bài toán giải theo phương pháp quy hoạch động gọi là bài toán quy hoạch động.
+Công thức phối hợp nghiệm của các bài toán con để có nghiệm của bài toán lớn gọi là công thức truy hồi của quy hoạch động.
+Tập các bài toán nhỏ nhất có ngay lời giải để từ đó giải quyết các bài toán lớn hơn gọi là cơ sở quy hoạch động.
+Không gian lưu trữ lời giải các bài toán con để tìm cách phối hợp chúng gọi là bảng phương án của quy hoạch động.

Các bước cài đặt một chương trình sử dụng quy hoạch động: (Nhớ kỹ)
+Giải tất cả các bài toán cơ sở (thông thường rất dễ), lưu các lời giải vào bảng phương án.
+Dùng công thức truy hồi phối hợp những lời giải của các bài toán nhỏ đã lưu trong bảng phương án để tìm lời giải của những bài toán lớn hơn và lưu chúng vào bảng phương án. Cho tới khi bài toán ban đầu tìm được lời giải.
+Dựa vào bảng phương án, truy vết tìm ra nghiệm tối ưu.

tinhoche11_01Cho đến nay, vẫn chưa có một định lý nào cho biết một cách chính xác những bài toán nào có thể giải quyết hiệu quả bằng quy hoạch động. Tuy nhiên để biết được bài toán có thể giải bằng quy hoạch động hay không, ta có thể tự đặt câu hỏi : “Một nghiệm tối ưu của bài toán lớn có phải là sự phối hợp các nghiệm tối ưu của các bài toán con hay không?”“Liệu có thể nào lưu trữ được nghiệm các bài toán con dưới một hình thức nào đó để phối hợp tìm được nghiệm bài toán lớn”.

Cuối cùng trước khi khảo sát một số bài toán quy hoạch động, ta nhắc lại: Phương pháp tốt nhất để giải quyết mọi bài toán trong tin học là biết sử dụng và phối hợp uyển chuyển nhiều thuật toán, không được lạm dụng hay coi thường bất cứ một phương pháp nào./.