Энэ бүлэгт бид алгоритмыг байгуулах болон шинжлэхтэй холбоотой үндсэн ойлголт болон аргуудыг эрэмбэлэх хоёр төрлийн алгоритм болох энгийн эрэмбэлэлт буюу оруулж эрэмбэлэх, илүү оновчтой эрэмбэлэлт болох хольж эрэмбэлэх гэсэн хоёр жишээн дээр авч үзнэ.
Эдгээр жишэнүүдээс бид алгоритмуудыг дүрслэхэд ашиглагдах псевдокод, функцийн өсөлтийн хурдны тэмдэглэгээнүүд, алгоритмыг байгуулах “хуваагаад эзэмш” хэмээх арга болон энэ номонд цаашид дайралдах бусад ойлголтуудтай танилцана.
1.1. Алгоритм
Алгоритм (Algorithm) гэдэг нь оролт эсвэл аргумент гэж нэрлэгдэх анхны өгөгдлүүдийг (input) хүлээн авч гаралт дээрээ үр дүнг (output) гаргадаг тооцоолох процедурын формаль бичлэг юм.
Алгоритмыг ямар нэг тооцоолох бодлогыг (computational problems) шийдэхийн тулд зохиодог. Бодлогын тавил нь бодлогын шийдэл ямар нөхцлүүдийг хангаж байх ёстойг томъёолдог ба харин бодлогыг шийдэж буй алгоритм нь эдгээр нөхцлүүдийг хангах объектийг олдог.
Энэхүү бүлэгт бид эрэмбэлэлтийн бодлогыг (sorting problem) авч үзэх ба учир нь энэ бодлого практик ач холбогдол ихтэйгээс гадна төрөл бүрийн ойлголт, аргуудыг үзүүлэхэд тохиромжтой байдаг. Уг бодлогыг дараах байдлаар тодорхойлдог:
Оролт: n гишүүнтэй дараалал (a1, a2, ..., an).
Гаралт: нөхцлийг хангах анхны дарааллын сэлгэмэл болох ( ).
Жишээ нь эрэмбэлэлтийн алгоритмын оролт <31, 41, 59, 26, 41, 58> байхад гаралт нь <26, 31, 41, 41, 58, 59> байх ёстой.
Эрэмбэлэгдэх гэж буй дарааллыг эрэмбэлэлтийн бодлогын оролт (instance) гэнэ.
Олон алгоритмуудад эрэмбэлэлтийг завсрын шат болгон ашигладаг. Эрэмбэлэлтийн олон алгоритмууд байдаг ба тодорхой тохиолдолд алийг нь сонгох вэ гэдгийг эрэмбэлэх дарааллын уртаас, дараалал хэр зэрэг эрэмбэлэгдсэн байгаагаас болон ямар санах ойг (шуурхай санах ой, диск, соронзон тууз) хэрэглэж байгаагаас хамааруулан шийднэ.
Хэрэв алгоритм тухайн бодлогын дурын боломжит оролт бүрийн хувьд ажиллаж дуусаад шаардлагыг хангах үр дүн гаргадаг бол түүнийг зөв (correct) алгоритм гэнэ. Иймд тохиолдолд тухайн алгоритм уг тооцоолох бодлогыг шийдэж байна (solves) гэж хэлдэг. Буруу алгоритм нь (зарим оролтын хувьд) дуусахгүй байж болох ба эсвэл буруу үр дүн гаргадаг. (Хэрэв ийм тохиолдлуудын тоо нь харьцангуй бага бол уг алгоритм нь тийм ч муу алгоритм биш байж болно. Ийм алгоритмыг бид 33-р бүлэгт том анхны тоог хайх үедээ үзэх болно. Гэвч энэ нь онцгой тохиолдол юм.)
Алгоритмыг монгол, англи хэл дээр эсвэл програмчлалын хэл бүр машины хэл дээр ч бичиж болох ба гол нь тооцоолох процедур тодорхой байх ёстой.
Бид алгоритмыг бичихдээ Паскаль, Си, Алгол хэлүүдийг санагдуулах псевдокодыг (pseudocode) ашиглана. Ялгаа нь гэвэл бид зарим газарт ойлгомжтой байлгах зорилгоор алгоритмын үйлдлийг үгээр бичих болно. Үүнээс гадна алдаа боловсруулах гэх мэт алгоритмтой онц холбогдолгүй технологийн деталиудыг орхисон.
Оруулж эрэмбэлэх
Оруулж эрэмбэлэх (insertion sort) аргыг богино дарааллыг эрэмбэлэхэд ашигладаг. Яг ийм аргаар бид гартаа байгаа хөзрийг эрэмбэлдэг: зүүн гартаа эрэмбэлэгдсэн хөзрүүдийг барьж байгаад баруун гараараа ээлжит хөзрийг авч баруунаас зүүн тийш уг шинэ хөзрийн байж болох байрлалыг хайж олдоод оруулдаг (зураг 1.1)...
No comments:
Post a Comment