Đại học Lê Quý Đôn - 236 Hoàng Quốc Việt - Hà Nội

Chia sẻ kiến thức mọi mặt của các lớp cao học CNTT, Học viện Kỹ thuật Quân sự




Chào mừng đã đến với forum khmt.123.st
  • Bạn chưa đăng kí (hoặc chưa đăng nhập) nên quyền lợi của bạn sẽ bị hạn chế. Việc đăng kí làm thành viên hoàn toàn miễn phí, sau khi đăngkí bạn có thể post bài, tham gia thảo luận , nhìn thấy link ở những box hạn chế ... và rất nhiều quyền lợi khác. Thủ tục đăng kí rất nhanh chóng và đơn giản, hãy Đăng kí làm thành viên !
  • Nếu bạn quên mật khẩu, xin nhấn vào đây !
  • Nếu bạn gặp trục trặc trong vấn đề đăng kí hoặc không thể đăng nhập, hãy liên hệ với chúng tôi.




  • Xem chủ đề cũ hơn Xem chủ đề mới hơn Go down  Thông điệp [Trang 1 trong tổng số 1 trang]

    Admin

    Admin
    Quản trị viên
    Quản trị viên
    I. Hệ đại diện phân biệt
    Bài toán của chúng ta là:
    Cho n chàng trai, nếu một nhóm k chàng trai bất kì quen với ít nhất k cô gái (1 ≤ k ≤ n).
    Chứng tỏ rằng đây là điều kiện cần và đủ để tổ chức một đám cưới tập thể sao cho mỗi chàng trai cưới một cô gái mình quen
    Có thể mô hình lại bài toán bằng tập hợp. Gọi Si, i = 1, 2, .., n là tập các cô gái mà chàng trai thứ i quen. Khi đó với mọi i1, i2, ..., ik ∈ {1, 2, ..., n} thỏa mãn |Si1 ∪ Si2 ∪ ... ∪ Sik | ≥ k (Điều kiện Hall)
    khi và chỉ khi tồn tại (a1, ..., an) ∈ S1 × S2 × ... × Sn sao cho ai = aj với i = j
    Đây là cũng là nội dung của định lý Hall còn gọi là định lý Đám cưới (Hall’s Marriage Theorem)
    Một bộ (a1, ..., an) như vậy gọi là một hệ đại diện phân biệt cho hệ tập hợp (S1,S2, ...,Sn) (viết tắt là TRAN), phần tử ai ∈ Si gọi là đại diện cho Si, lưu ý rằng ai = aj với i = j. Như vậy nếu như hệ tập (S1, ...,Sn) thỏa mãn điều kiện Hall thì tồn tại một TRAN cho hệ đó và điều ngược lại nếu một hệ có TRAN thì nó thỏa mãn điều kiện Hall. Một TRAN nếu có nói chung là không duy nhất, bài toán cần quan tâm là có bao nhiêu TRAN của một hệ tập hợp cho trước.

    II. Định lý Hall
    Giả sử các tập con S1, S2,..., Sm thoả mãn điều kiện:
    N (Si1 U Si2 U....U Sik) ≥ k (1)
    với mọi 1 ≤ k ≤ m, 1 ≤ i1 < i2 <....< ik ≤ m và mỗi tập con này có ít nhất t phần tử khi đó:

    - Nếu t ≤ m thì họ đang xét có ít nhất số TRAN là t!

    - Nếu t > m thì họ đang xét có ít nhất số TRAN là [You must be registered and logged in to see this image.]

    - Khi (1) có 1 họ con trở thành đẳng thức, thì họ con đó gọi là họ con tới hạn.

    III. Bài trong đề thi
    (Trang 94, bài 32) Một nhóm thợ gồm:
    - Hùng có thể đảm nhận (Gò, hàn, rèn)
    - Dũng có thể đảm nhận (Mạ, rũa, hàn, rèn)
    - Chính có thể đảm nhận (Gò, mạ, rèn)
    - Trung có thể đảm nhận (Rũa, đánh bóng, sơn, rèn)
    - Lan có thể đảm nhận (Rũa, đánh bóng, sơn, mạ)
    - Vân có thể đảm nhận (Đánh bóng, sơn, gò)

    Một công việc cần thực hiện là (Rèn, gò, rũa, mạ, đánh bóng, sơn)
    Hỏi:
    - Có ít nhất bao nhiêu cách phân công công việc mà mỗi thợ thực hiện một công đoạn?
    - Chỉ ra 2 cách phân công, nếu có.



    Được sửa bởi Admin ngày Wed Aug 10, 2011 5:57 am; sửa lần 2.

    https://khmt.123.st

    Admin

    Admin
    Quản trị viên
    Quản trị viên
    Chỉ ra một số TRAN

    [You must be registered and logged in to see this image.]

    https://khmt.123.st

    TuanNghia

    TuanNghia
    Thành viên bắt đầu chia sẻ
    Thành viên bắt đầu chia sẻ
    Thưa anh Admin, theo em, khi làm bài thi thì cứ mỗi TRAN ta sẽ lập một bảng...

    Nhưng theo anh Thứ tự điền tên người và tên công việc như trong bảng có cần có yêu cầu gì không, em không đi học nên không rõ thầy nói sao, Nhưng em nghe nói là phải có thứ tự gì đó.. Mong anh giải thích giúp...

    Ban QT: Hãy trình bày sao cho bài làm dễ xem nhất, còn việc lập 1 bảng hay nhiều bảng tùy cách trình bày của mỗi người, có người chỉ trình bày bằng 1 bảng, mỗi TRAN vẽ bằng một kiểu nét vẽ, ví dụ TRAN1 là nét liền, TRAN2 là nét gạch gạch, TRAN3 là nét chấm gạch...

    nhutaptech

    nhutaptech
    Thành viên bắt đầu chia sẻ
    Thành viên bắt đầu chia sẻ
    Theo định lý HALL thì t ≤ m thì có t!TRAN, vậy với bài toán trên có t! = 2! = 2 TRAN, trong hình vẽ ta chỉ vẽ được duy nhất là 2 cách phân công công việc phải không?

    Ban QT: Bạn cần phân biệt khái niệm "có ít nhất" với khái niệm "" để làm bài và viết cho đúng với yêu cầu đề bài.

    TuanNghia

    TuanNghia
    Thành viên bắt đầu chia sẻ
    Thành viên bắt đầu chia sẻ
    Thưa anh Admin, vì em không đi học nên không chắc chắn lắm, nhưng em nghe nói, bài toán liên quan đến định lý Hall trước hết phải tìm m,k,t.. tức là phải kiểm tra điều kiện áp dụng định lý Hall. Em không đi học nên thực sự không rõ, trước khi kẻ bảng ta cần làm những gì, trình bày ra sao.. mong anh hỗ trợ nhanh vì đã sát ngày thi quá rồi...

    Ban QT: Việc thuộc định lý thì bạn phải thuộc thôi. Công thức tối thiểu nếu viết ra chỉ có 3 dòng có 2 giá trị t!t!/((t-m)! chẳng lẽ lại khó thế. m, t, k đã được chỉ ra có sẵn trong đề bài. Bạn hãy chép định lý ra giấy, xem ví dụ mẫu, viết m, t, k mỗi ký tự 1 dòng. Sau đó dò trong ví dụ mẫu xem nó là gì. Như ví dụ vừa xét thì m → người, t → việc. Cần nhớ ví dụ mẫu để bài khác tương tự. Kẻ như bài mẫu. Lập luận như sách. Còn không thể nhớ nổi thì... làm thơ hoặc một câu dễ nhớ, việc sáng tạo là do bạn. Ví dụ:
    Ta mà nhỏ hơn em thì ta than (Tương ứng với t < m thì t! là có ít nhất giá trị TRAN)
    Ta mà lớn hơn hoặc bằng em thì ta than trên việc ta sẽ trừ bỏ em để than (Tương ứng t ≥ m thì t!/((t-m)!)

    huutaisc

    huutaisc
    Thành viên bắt đầu chia sẻ
    Thành viên bắt đầu chia sẻ
    nhutaptech đã viết:Theo định lý HALL thì t ≤ m thì có t!TRAN, vậy với bài toán trên có t! = 2! = 2 TRAN, trong hình vẽ ta chỉ vẽ được duy nhất là 2 cách phân công công việc phải không?

    Ban QT: Bạn cần phân biệt khái niệm "có ít nhất" với khái niệm "" để làm bài và viết cho đúng với yêu cầu đề bài.

    m=6 , nhung t lam sao bang 2 duoc .
    t la so cong viec, thì no la 3 hay 4 mới đúng nhỉ (ChamChi)

    - Hùng có thể đảm nhận (Gò, hàn, rèn)
    - Dũng có thể đảm nhận (Mạ, rũa, hàn, rèn)
    - Chính có thể đảm nhận (Gò, mạ, rèn)
    - Trung có thể đảm nhận (Rũa, đánh bóng, sơn, rèn)
    - Lan có thể đảm nhận (Rũa, đánh bóng, sơn, mạ)
    - Vân có thể đảm nhận (Đánh bóng, sơn, gò)

    Sponsored content


    Xem chủ đề cũ hơn Xem chủ đề mới hơn Về Đầu Trang  Thông điệp [Trang 1 trong tổng số 1 trang]

    Permissions in this forum:
    Bạn không có quyền trả lời bài viết

     

    Ghi rõ nguồn khi copy các bài viết từ Website này.
    Bản quyền thuộc Khoa học Máy tính. Số lượt truy cập tính đến hiện tại:Website counter
    Modified skin by Nguyễn Anh Cường. Developed by Members of https://khmt.123.st

    Free forum | ©phpBB | Free forum support | Báo cáo lạm dụng | Thảo luận mới nhất