Hotline: 024.62511017

024.62511081

  Trang chủ   Sản phẩm   Phần mềm Dành cho nhà trường   Phần mềm Hỗ trợ học tập   Kho phần mềm   Liên hệ   Đăng nhập | Đăng ký

Tìm kiếm

School@net
 
Xem bài viết theo các chủ đề hiện có
  • Hoạt động của công ty (726 bài viết)
  • Hỗ trợ khách hàng (498 bài viết)
  • Thông tin tuyển dụng (57 bài viết)
  • Thông tin khuyến mại (80 bài viết)
  • Sản phẩm mới (216 bài viết)
  • Dành cho Giáo viên (549 bài viết)
  • Lập trình Scratch (3 bài viết)
  • Mô hình & Giải pháp (156 bài viết)
  • IQB và mô hình Ngân hàng đề kiểm tra (127 bài viết)
  • TKB và bài toán xếp Thời khóa biểu (242 bài viết)
  • Học tiếng Việt (183 bài viết)
  • Download - Archive- Update (289 bài viết)
  • Các Website hữu ích (70 bài viết)
  • Cùng học (92 bài viết)
  • Learning Math: Tin học hỗ trợ học Toán trong nhà trường (78 bài viết)
  • School@net 15 năm (154 bài viết)
  • Mỗi ngày một phần mềm (7 bài viết)
  • Dành cho cha mẹ học sinh (124 bài viết)
  • Khám phá phần mềm (122 bài viết)
  • GeoMath: Giải pháp hỗ trợ học dạy môn Toán trong trường phổ thông (36 bài viết)
  • Phần mềm cho em (13 bài viết)
  • ĐỐ VUI - THƯ GIÃN (363 bài viết)
  • Các vấn đề giáo dục (1210 bài viết)
  • Bài học trực tuyến (1037 bài viết)
  • Hoàng Sa - Trường Sa (17 bài viết)
  • Vui học đường (275 bài viết)
  • Tin học và Toán học (220 bài viết)
  • Truyện cổ tích - Truyện thiếu nhi (180 bài viết)
  • Việt Nam - 4000 năm lịch sử (97 bài viết)
  • Xem toàn bộ bài viết (8223 bài viết)
  •  
    Đăng nhập/Đăng ký
    Bí danh
    Mật khẩu
    Mã kiểm traMã kiểm tra
    Lặp lại mã kiểm tra
    Ghi nhớ
     
    Quên mật khẩu | Đăng ký mới
     
    Thành viên có mặt
    Khách: 10
    Thành viên: 0
    Tổng cộng: 10
     
    Số người truy cập
    Hiện đã có 92487149 lượt người đến thăm trang Web của chúng tôi.

    Lịch sử phần mềm xếp thời khóa biểu TKB (15): thuật toán tinh chỉnh tối ưu đầu tiên: OpCX/OpDPR

    Ngày gửi bài: 04/01/2013
    Số lượt đọc: 21122

    thời khóa biểuNhư vậy một trong những bài toán chính của việc tối ưu hóa dữ liệu là thiết kế các thuật toán tinh chỉnh dữ liệu tối ưu.

    Không phải ngay từ đầu bài toán "tối ưu hóa" các thuật toán tinh chỉnh dữ liệu đã được đặt ra rõ ràng như ngày hôm nay.


    Năm 2007, phiên bản TKB 6.5 đã đưa vào được khái niệm các tiêu chí đánh giá thay đổi dữ liệu GV (12 tiêu chí dã nói trong các phần trước). Từ phiên bản này trở đi các lệnh tinh chỉnh dữ liệu chính như CX, Push Out, Move To sẽ có thêm bảng đánh giá kết quả thực hiện lệnh bằng các tiêu chí trên cho từng GV bị thay đổi của lệnh.

    Năm 2008, phiên bản TKB 7.0 đã đưa thêm vào các tiêu chí đánh giá một TKB GV bằng cách đưa vảo tiêu chí đánh giá 1 tiết học là xấu hay tốt (10 tiêu chí) và 12 tiêu chí đánh giá định lượng và yêu cầu của GV. Cũng trong TKB 7.0 đã đưa ra khái niệm các tiêu chí Chuyển tiết tối ưu (10 tiêu chí, đã nói trong phần trước). Như vậy phải đến 2 năm sau đó, năm 2009, các công việc chuẩn bị cho việc thiết kế chính thức một thuật toán tinh chỉnh tối ưu mới được đặt ra cụ thể. Thuật toán mà chúng tôi chọn để thiết kế là thuật toán CX và DPR.

    Hai thuật toán CX và DPR có nhiều điểm chung, thực chất CX là một trường hợp riêng của DPR.

    Mô hình đơn giản của thuật toán DPR như sau:

    Giả sử cần chuyển 1 tiết học trên thời khóa biểu của một giáo viên A từ vị trí này sang vị trí khác (do yêu cầu của A). Việc chuyển này được viết thành mô hình như sau:

    P0 ---> P1 (1)

    Nếu vị trí tiết học tại P1 (môn học, lớp, giáo viên) có thể chuyển ngay về P0 thì quá trình (1) sẽ kết thúc ngay:

    P0 --> P1 --> P0 (2)

    Nhưng thực tế không bao giờ xảy ra như vậy, do đó thể thực hiện được bài toán (1) sẽ phải kéo theo thực hiện một dây biến đổi:

    P0 --> P1 --> P2 --> .... --> PN (3)

    Chính xác hơn ở đoạn cuối của (3) phải viết đầy đủ là PN --> P0, tuy nhiên tôi sẽ bỏ qua cách viết này.

    Như vậy bản chất của một thuật toán tinh chỉnh dữ liệu thời khóa biểu là muốn có (1) phải thực hiện (3).

    Thuật toán này được gọi là "tối ưu" nếu toàn bộ các dịch chuyển trung gian Pi-1 --> Pi phải là tối ưu.

    Sau một thời gian mò mẫm thử nghiệm, năm 2009, chúng tôi đã thành công trong việc thiết kế một thuật toán tinh chỉnh tối ưu như vậy. Thuật toán này là một mở rộng trực tiếp của 2 thuật toán CX, DPR và chúng tôi đặt tên thuật toán mới là OpCX/OpDPR.

    Tháng 7 năm 2009, phiên bản TKB 7.5 ra đời với một thuật toán tinh chỉnh tối ưu mới: OpCX/OpDPR. Thật là kỳ diệu vì khi sử dụng thuật toán này, trên các bảng đánh giá tiêu chí mà chúng tôi đưa ra, hầu hết các đánh giá giáo viên trung gian là "Xanh" tức là Tốt lên.
    OpCX/OpDPR là thuật toán tinh chỉnh tối ưu đầu tiên của Công ty School@net cũng như của Việt Nam đã thực hiện được yêu cầu sau:

    - Khi thực hiện thuật toán này thành công cho 1 GV A, tất cả các giáo viên bị thay đổi thời khóa biểu khác B, C, ..., Z sẽ không bị "xấu đi", chỉ có thể bằng hoặc tốt lên.

    Phần mềm TKB 7.5 ra đời với thuật toán tinh chỉnh tối ưu OpCX/OpDPR đã gây 1 tiếng vang lớn và được các nhà trường đón nhận.

    Tuy nhiên hãy còn 1 thuật toán nữa chưa tối ưu được, đó là thuật toán FPR.


    Bùi Việt Hà, Công ty Công nghệ Tin học Nhà trường

    School@net



     Bản để in  Lưu dạng file  Gửi tin qua email


    Những bài viết khác:



    Lên đầu trang

     
    CÔNG TY CÔNG NGHỆ TIN HỌC NHÀ TRƯỜNG
     
    Phòng 804 - Nhà 17T1 - Khu Trung Hoà Nhân Chính - Quận Cầu Giấy - Hà Nội
    Phone: 024.62511017 - 024.62511081
    Email: kinhdoanh@schoolnet.vn


    Bản quyền thông tin trên trang điện tử này thuộc về công ty School@net
    Ghi rõ nguồn www.vnschool.net khi bạn phát hành lại thông tin từ website này
    Site xây dựng trên cơ sở hệ thống NukeViet - phát triển từ PHP-Nuke, lưu hành theo giấy phép của GNU/GPL.