Ընտրող հարսնացուի առաջադրանք

Վիքիպեդիայից՝ ազատ հանրագիտարանից
Jump to navigation Jump to search

Ընտրող հարսնացուի առաջադրանք (որոշման կայացման խնդիր), գիտական առաջադրանք, որն առաջին անգամ ձևակերպվել է 1960 թվականին Մարտին Գարդների կողմից:

Անգլալեզու գիտական գրականության մեջ հանդիպում է նաև քարտուղարի առաջադրանք տարբերակը:

Ձևակերպում[խմբագրել | խմբագրել կոդը]

Առաջադրանքը կարելի է ձևակերպել հետևյալ կերպ[1].

  1. Հարսնացու փնտրում է իր համար ամուսին, ընդորում գոյություն ունի միայն մեկ թափուր տեղ:
  2. Կա թեկնածուների հայտնի թիվ՝ :
  3. Հարսնացուն պատահական սկզբունքով շփվում է թեկնածուների հետ՝ ամեն մեկի հետ միայն մեկ անգամ:
  4. Յուրաքանչյուր թեկնածուի պարագայում հայտնի է, թե նա արդյոք լավն է կամ վատն է նախորդ թեկնածուից:
  5. Հերթական թեկնածուի հետ շփման արդյունքում հարսնացուն պետք է կամ մերժի, կամ ընդունի թեկնածուի առաջարկությունը: Եթե ընդունվի առաջարկությունը, ապա գործընթացը դադարեցվում է, իսկ եթե հարսնացուն մերժի թեկնածուին, ապա հարսնացուն այլևս չի կարող վերադառնալ նրա մոտ:
  6. Նպատակն է ընտրել լավագույն թեկնածուին:

Լուծում[խմբագրել | խմբագրել կոդը]

1963 թվականին Ռուսաստանի գիտությունների ակադեմիայի ակադեմիկոս Եվգենի Դինկինը առաջ քաշեց առաջադրանքի լուծումը՝ մասնավոր դեպքի համար: Առաջադրանքի ընդհանուր լուծումը 1966 թվականին հայտնաբերել է Սաբիր Հուսեյնզադեն:

Առաջադրանքի նկատմամբ մեծ ուշադրություն է դարձվել հատկապես այն պատճառով, որ օպտիմալ ռազմավարությունը ունի հետաքրքիր յուրահատկություն: Եթե հավանական թեկնածուների թիվը բավականին շատ է (օրինակ 100-ից ավելին), ապա օպտիմալ ռազմավարությունը կկայանա նրանում, որ մերժվեն բոլոր առաջին (որտեղ ՝ լոգարիթմի բնական հիմնավորումը) թեկնածուները և հետո ընտրվի այն առաջինը, որը նախորդներից ամենալավը կլինի[2]: -ի ավելացման դեպքում լավագույն թեկնածուի ընտրության հավանականությունը ձգտում է , այսինքն մոտ 37 %:

Հետաքրքիր փաստեր[խմբագրել | խմբագրել կոդը]

Ռուսաստանի գիտությունների ակադեմիայի թղթակից-անդամ Բորիս Բերեզովսկին հայցվող գիտությունների դոկտորի գիտական աստիճանի համար գրված «Նախագծային որոշումների ընդունման ալգորիթացումը և դրանց կիրառման տեսական հիմքերի մշակումը» վերնագրով ատենախոսության մեջ ընդհանրական կերպով անդրադարձել է ընտրող հարսնացուի առաջադրանքին:

Ծանոթագրություններ[խմբագրել | խմբագրել կոդը]

  1. С. М. Гусейн-Заде, Разборчивая невеста, с. 3-4, М.: МЦНМО, 2003
  2. С. М. Гусейн-Заде, Разборчивая невеста, с. 18, М.: МЦНМО, 2003

Արտաքին հղումներ[խմբագրել | խմբագրել կոդը]

  • С. М. Гусейн-Заде Разборчивая невеста. — МЦНМО, 2003. — Т. 25. — 20 с. — (Библиотека «Математическое просвещение»). — ISBN 5-94057-076-3
  • С. М. Гусейн-Заде. Разборчивая невеста. Видео-лекция. Малый мехмат, МГУ, 30.11.2002.
  • И. Р. Высоцкий, И. В. Ященко Задачи заочных интернет-олимпиад по теории вероятностей и статистике —  МЦНМО, 2017, с.255, 275 — ISBN 978-5-4439-1136-6