Randomized algorithms: Таны программ хэр сайн ажиллах нь таны азаас хамаарна.

ulziikhishig

• 2025-05-17
• algorithm, probability, randomization, randomness, магадлал, санамсаргүй алгоритм

Азад итгэн код бичнэ гэдэг утгагүй юм шиг. Гэхдээ та магадлалын онолыг мэддэг бол энэ нь тийм ч утга учиргүй зүйл биш болж таарна. Энэхүү нийтлэлээр детерминистик буюу тодорхой алгоритмын гүйцэтгэлийг давсан санамсаргүй алгоритмуудыг авч үзэх болно.

Санамсаргүй алгоритм нь оролтын өгөгдлүүдээс гадна санамсаргүй тоон цувааг ашиглан шийдвэр гаргах процесстоо ашигладаг. Нэг үгээр хэлбэл оролтын утга яг адилхан байхад гаралтын утга өөр байж болно гэсэн үг. Тиймээс бид магадлалын онолын ойлголтуудыг ашиглан уг алгоритмын үр дүнг хэмждэг. Оролтын утга нь яг адилхан байсан ч гэсэн ажиллах хугацааг нь санамсаргүй хувьсагчаар төлөөлүүлж авч үзэх болно.

Санамсаргүй алгоритм нь:

1. Ажиллах хурд болон эзлэх зай нь тодорхой алгоритмуудыг бодвол хамаагүй үр ашигтай байдаг.
2. Энэ төрлийн алгоритмуудыг ойлгоход мөн хэрэгжүүлэхэд маш хялбар байдаг.

Санамсаргүй алгоритмыг 2 ангилна.

Монте Карло алгоритм
Хурдан ажилладаг ч баталгаатай үнэн хариу өгдөггүй. Гол санаа нь аналитик шийдэл олоход хэцүү эсвэл боломжгүй тохиолдолд олон тооны санамсаргүй түүвэр үүсгэж, тэдгээрийг ашиглан ойролцоо шийдэл олоход оршино.

Лас Вегас алгоритм
Монте Карло алгоритмыг бодвол удаан. Лас Вегасын алгоритм нь хэзээ ч буруу хариу өгдөггүй. Хэрвээ хариуг олвол тэр нь зөв байна.

Энэхүү алгоритм өргөн ашиглагддаг салбарууд

• Machine Learning – модел сургах үедээ санамсаргүй сонголт ашгиглах: Random forest
• Криптограф – санамсаргүй түлхүүр үүсгэх
• Компьютер график – гэрэлтүүлгийн хуурамч загварчлал
• Тоглоомын хөгжил – азын систем, эсвэл хүний шийдвэр дууриах

Санамсаргүй алгоритм нь магадлалын онолын тулгуур дээр суурилсан, орчин үеийн алгоритмын онолын чухал салбар юм. Эдгээр нь заримдаа “эрсдэлтэй” мэт харагдах ч оновчтой хэрэглэвэл маш үр ашигтай, тооцооллын хувьд ухаалаг шийдлийг санал болгодог. Судалгааны түвшинд, санамсаргүй алгоритм нь NP-hard асуудлуудын ойролцоо шийдлийг олох, том өгөгдлийн боловсруулалт, машин сургалтын дэд бүтэц зэрэгт чухал үүрэг гүйцэтгэсээр байна.

SKIP LIST ALGORITHM

Жишээ болгон би та нарт нэгэн алгоритмын жишээг танилцуулъя.

Энгийн list нээс хайлт хийх хугацаа нь хоёртын хайлтыг ашиглан Log(n) болж багасч болно.Гэхдээ динамик листний хувьд хоёртын хайлт хийх боломжгүй буюу заавал нэг node–р дамжин нөгөөд хүрэх юм. Тиймээс  insert, delete үйлдлүүд нь n хугацаа шаардана. санамсаргүй алгоритмын ашиглан бид энэхүү үзүүлэлтийг сайжруулж  insert, delete, search  үйлдлүүдийг log(N) хугацаан гүйцэтгэж болдог.

Энэхүү алгоритмын  хэрэгжүүлэлт маш энгийн.Та санамсаргүй өндөртэй лист үүсгэх бөгөөд тухайн элеменийн өндөр нь хэд байхыг successive 0.5 магадлалаар шийдэх юм.

Хэрвээ та энэхүү үзэгдлийн магадлалыг авч үзвэл тухайн шатанд байх  элементийн   хэмжээ нь доорх шатны элементийн тооноос 2 дахин бага байх юм. Тиймээс ч энэхүү алгоритмын expexted result нь  insert, delete, search хугацаа нь log(n) байдаг.