Wednesday, March 11, 2009
Нэгдүгээр дэвтэр
Оршил
Энэ хэсэгт алгоритмын шинжилгээнд ашиглагддаг математикийн аргуудын тухай мэдээллийг нэгтгэсэн болно. Иймд энэ хэсгийг гүйлгэн уншаад дараа нь хэрэгтэй үед нь эргэн харах хэрэгтэй.
Хоёрдугаар бүлэгт бид функцийн асимптотиктой холбоотой (Θ гэх мэт) болон бусад ойлголт болон тэмдэглэгээнүүдийг үзнэ. Энд бидний зорилго бол ямар нэг шинэ зүйлийн тухай ярих биш тэмдэглэгээ болон нэр томъёогоо нэгтгэх явдал юм.
Гуравдугаар бүлэгт нийлбэрийг бодох болон үнэлэх төрөл бүрийн аргуудын тухай гарна (дэлгэрэнгүйг математик анализын дурын номноос үзэж болно).
Дөрөвдүгээр бүлэг бүтнээрээ рекуррент харьцааг жирийн үнэлгээнд хувиргах тухай юм. Бид ихэнх тохиолдолд хангалттай хэрэг болох энэ төрлийн нэг хувиргалтыг томъёолон, батлах болно. Баталгаа нь хангалттай урт боловч дахиж хэрэглэгдэхгүй тул эхний удаа уншихдаа алгасах хэрэгтэй.
Тавдугаар бүлэгт бид олонлог, харьцаа, функц, граф болон модтой холбоотой төрөл бүрийн ойлголтуудын тодорхойлолт болон тэмдэглэгээг үзнэ.
Зургаадугаар бүлэг хослолын онол болон магадлалын онолын үндсэн ойлголтуудад зориулагдсан. Номын ихэнх хэсэгт энэ материалыг ашиглаагүй тул эхний удаад энэ бүлгийг алгасаад, хэрэгцээтэй үедээ эргэн унших хэрэгтэй.
Энэ хэсэгт алгоритмын шинжилгээнд ашиглагддаг математикийн аргуудын тухай мэдээллийг нэгтгэсэн болно. Иймд энэ хэсгийг гүйлгэн уншаад дараа нь хэрэгтэй үед нь эргэн харах хэрэгтэй.
Хоёрдугаар бүлэгт бид функцийн асимптотиктой холбоотой (Θ гэх мэт) болон бусад ойлголт болон тэмдэглэгээнүүдийг үзнэ. Энд бидний зорилго бол ямар нэг шинэ зүйлийн тухай ярих биш тэмдэглэгээ болон нэр томъёогоо нэгтгэх явдал юм.
Гуравдугаар бүлэгт нийлбэрийг бодох болон үнэлэх төрөл бүрийн аргуудын тухай гарна (дэлгэрэнгүйг математик анализын дурын номноос үзэж болно).
Дөрөвдүгээр бүлэг бүтнээрээ рекуррент харьцааг жирийн үнэлгээнд хувиргах тухай юм. Бид ихэнх тохиолдолд хангалттай хэрэг болох энэ төрлийн нэг хувиргалтыг томъёолон, батлах болно. Баталгаа нь хангалттай урт боловч дахиж хэрэглэгдэхгүй тул эхний удаа уншихдаа алгасах хэрэгтэй.
Тавдугаар бүлэгт бид олонлог, харьцаа, функц, граф болон модтой холбоотой төрөл бүрийн ойлголтуудын тодорхойлолт болон тэмдэглэгээг үзнэ.
Зургаадугаар бүлэг хослолын онол болон магадлалын онолын үндсэн ойлголтуудад зориулагдсан. Номын ихэнх хэсэгт энэ материалыг ашиглаагүй тул эхний удаад энэ бүлгийг алгасаад, хэрэгцээтэй үедээ эргэн унших хэрэгтэй.
Нэгдүгээр бүлэг: Оршил
Энэ бүлэгт бид алгоритмыг байгуулах болон шинжлэхтэй холбоотой үндсэн ойлголт болон аргуудыг эрэмбэлэх хоёр төрлийн алгоритм болох энгийн эрэмбэлэлт буюу оруулж эрэмбэлэх, илүү оновчтой эрэмбэлэлт болох хольж эрэмбэлэх гэсэн хоёр жишээн дээр авч үзнэ.
Эдгээр жишэнүүдээс бид алгоритмуудыг дүрслэхэд ашиглагдах псевдокод, функцийн өсөлтийн хурдны тэмдэглэгээнүүд, алгоритмыг байгуулах “хуваагаад эзэмш” хэмээх арга болон энэ номонд цаашид дайралдах бусад ойлголтуудтай танилцана.
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)...
Эдгээр жишэнүүдээс бид алгоритмуудыг дүрслэхэд ашиглагдах псевдокод, функцийн өсөлтийн хурдны тэмдэглэгээнүүд, алгоритмыг байгуулах “хуваагаад эзэмш” хэмээх арга болон энэ номонд цаашид дайралдах бусад ойлголтуудтай танилцана.
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)...
Өмнөх үг
Энэ номонд алгоритмыг байгуулах болон шинжлэх орчин үеийн аргуудын тухай дэлгэрэнгүй өгүүлнэ. Энд олон алгоритмуудыг авч үзсэн ба тэдгээрийн тухай ойлгомжтой, ямар нэг зүйлийг орхилгүйгээр сайтар тайлбарласан байгаа.
Алгоритмуудыг псевдокод хэлбэрээр бичсэн байгаа ба дунд нь тайлбар хийсэн байгаа тул програмчлалын талаар бага ойлголттой хүнд ч ойлгомжтой байх болно. Номонд төрөл бүрийг алгоритмын ажиллагааг тайлбарласан 260 гаруй зураг бий. Бид алгоритмын үр ашигтай байдалд гол анхаарлаа хандуулсан ба авч үзэж буй алгоритмуудынхаа ажиллах хугацааны үнэлгээг хийсэн байгаа.
Бид нэгдүгээр курсын оюутнуудаас доктор оюутнууд, багш нар хүртэл ашиглаж болохуйц алгоритм болон өгөгдлийн бүтцийг байгуулах тухай сурах бичиг бичихийг хичээлээ. Мөн уг номыг мэргэжлийн програмистууд бие даан үзэж болох юм.
Багш нарт:
Бид уг номыг нэгдүгээр курсын програмчлалын хэл, өгөгдлийн бүтэц болон доктор оюутнуудын үр ашигтай алгоритмын хичээлд ашиглаж болохуйцаар төрөл бүрийн түвшинд ашиглаж болохуйцаар бичсэн. Энд байгаа бүх материал нь нэг семестрт орж амжихааргүй байгаа тул бүлгүүдээс тохирохыг нь сонгон авах хэрэгтэй.
Бүлгүүд нь хоорондоо хамааралгүй байхаар бичигдсэн. Бүлэг нь хамгийн энгийн материалаасаа эхлэх ба хүнд хэсгүүд нь одоор тэмдэглэгдсэн байх буюу бүлгийн сүүл хэсэгт байрласан байна. Эхлэн суралцагчдад орох хичээлдээ бүлгүүдийн эхний хэдэн хэсгийг ороход хангалттай. Харин үлдсэн хэсгүүдийг дараагийн курсуудэд үзэж болно...
Алгоритмуудыг псевдокод хэлбэрээр бичсэн байгаа ба дунд нь тайлбар хийсэн байгаа тул програмчлалын талаар бага ойлголттой хүнд ч ойлгомжтой байх болно. Номонд төрөл бүрийг алгоритмын ажиллагааг тайлбарласан 260 гаруй зураг бий. Бид алгоритмын үр ашигтай байдалд гол анхаарлаа хандуулсан ба авч үзэж буй алгоритмуудынхаа ажиллах хугацааны үнэлгээг хийсэн байгаа.
Бид нэгдүгээр курсын оюутнуудаас доктор оюутнууд, багш нар хүртэл ашиглаж болохуйц алгоритм болон өгөгдлийн бүтцийг байгуулах тухай сурах бичиг бичихийг хичээлээ. Мөн уг номыг мэргэжлийн програмистууд бие даан үзэж болох юм.
Багш нарт:
Бид уг номыг нэгдүгээр курсын програмчлалын хэл, өгөгдлийн бүтэц болон доктор оюутнуудын үр ашигтай алгоритмын хичээлд ашиглаж болохуйцаар төрөл бүрийн түвшинд ашиглаж болохуйцаар бичсэн. Энд байгаа бүх материал нь нэг семестрт орж амжихааргүй байгаа тул бүлгүүдээс тохирохыг нь сонгон авах хэрэгтэй.
Бүлгүүд нь хоорондоо хамааралгүй байхаар бичигдсэн. Бүлэг нь хамгийн энгийн материалаасаа эхлэх ба хүнд хэсгүүд нь одоор тэмдэглэгдсэн байх буюу бүлгийн сүүл хэсэгт байрласан байна. Эхлэн суралцагчдад орох хичээлдээ бүлгүүдийн эхний хэдэн хэсгийг ороход хангалттай. Харин үлдсэн хэсгүүдийг дараагийн курсуудэд үзэж болно...
Алгоритмын үндэс. Томас Кормен, Чарльз Лейзерсон, Рональд Ривест
Манай нэг оюутан энэ номыг орчуулбал надад алтан хөшөө босгож өгнө гэсэн тул юу ч гэсэн эхнээс нь хэдэн бүлэг орчуулав. Гэхдээ өөр бас орчуулж байгаа хүн байвал нэгдэх санаатайгаар вэб дээр бүлэг бүрээс эхний хуудсуудыг нь гаргалаа. Гэнэт бас нэг нөхөр эхнээс нь орчуулж байвал хоёулаа нэг ажлыг давхар хийж шатсан хэрэг болох биз. Уг ном нь 37 бүлэгтэй юм.
Tuesday, March 10, 2009
Monday, March 9, 2009
Saturday, March 7, 2009
ШУТИС, КтМС-ийн 2008-2009 оны хичээлийн жилийн хаврын семестрийн хуваарь
Хуваарийг сканердаж энд оруулснаас хойш зарим өөрчлөлт гарч магадгүйг анхаарна уу.
Monday, March 2, 2009
Вэб дээр програмын эх код тавих
Вэб дээр програмын эх кодыг тэр чигээр нь тавихад олон асуудал гарна. Наад зах нь хоёр тоог харьцуулаад if( a < b ) гээд биччихсэн байхад их багын тэмдгийг html тэг гэж ойлгох гэх мэт. Энэ блогуудын текст редакторууд ч яахав ийм алдаа гаргадаггүй болж. Харин програмынх нь бүх мөр урагшаа шахагдаад уншихад бэрх болох нь олон тул cs200 блог дээр http://www.manoli.net/csharpformat/ сайтыг ашиглан програмын кодоо аятайхан харагдахуйц болгож байлаа. Энэ сайтаар онлайн горимд програмын кодоо форматыг нь (догол мөрүүдийг) алдагдуулахгүйгээр вэб хэлбэрт шилжүүлж болно. Онлайн гэснээс онлайнаар ps-ийг pdf руу хөрвүүлж, онлайнаар кино үзэх гэх мэтээр онлайн үйлчилгээнүүд олширч байгаа нь тун сайн хэрэг юм. Ядаж л баахан конвертер гэсэн програм компьютер дээрээ суулгахгүй, алга болчихоор нь суулгацыг нь хайж давхихгүй. Удахгүй онлайнаар шүд ломбоддог болоосой :) ...
Subscribe to:
Posts (Atom)