EITC/IS/CCTF Тооцооллын нарийн төвөгтэй байдлын онолын үндэс
EITC/IS/CCTF Computational Complexity Theory Fundamentals нь компьютерийн шинжлэх ухааны үндэслэлүүдийн онолын асуудлаарх Европын мэдээллийн технологийн гэрчилгээжүүлэлтийн хөтөлбөр бөгөөд интернетэд өргөн хэрэглэгддэг сонгодог тэгш бус нийтийн түлхүүрийн криптографийн үндэс болдог.
EITC/IS/CCTF Тооцооллын нийлмэл байдлын онолын үндэс хичээлийн хөтөлбөр нь детерминист болон тодорхой бус хязгаарлагдмал төлөвийн машинууд, ердийн хэлүүд, контекстээс ангид дүрмийн болон хэлний онол, автоматын онол, Тьюринг зэрэг үндсэн ойлголтууд дээр компьютерийн шинжлэх ухааны үндэс, тооцооллын загваруудын онолын мэдлэгийг хамардаг. Машинууд, асуудлыг шийдвэрлэх чадвар, рекурс, логик, нарийн төвөгтэй байдал Дараах бүтэц дэх аюулгүй байдлын үндсэн хэрэглээний алгоритмууд нь холбогдох шалгалтыг өгч энэхүү EITC гэрчилгээг авахад бэлтгэх үндэс болох нээлттэй хандалтын видео дидактик контентоор дэмжигдсэн EITCI сертификатын сургалтын хөтөлбөрт бие даан суралцах материалуудыг багтаасан болно.
Алгоритмыг тооцоолох нарийн төвөгтэй байдал нь түүнийг ажиллуулахад шаардагдах нөөцийн хэмжээ юм. Цаг хугацаа, санах ойн нөөцөд онцгой анхаарал хандуулдаг. Асуудлын нарийн төвөгтэй байдал нь түүнийг шийдвэрлэх хамгийн сайн алгоритмуудын нарийн төвөгтэй байдал гэж тодорхойлогддог. Алгоритмуудын шинжилгээ нь тодорхой өгөгдсөн алгоритмуудын нарийн төвөгтэй байдлын судалгаа байдаг бол тооцооллын нарийн төвөгтэй байдлын онол нь хамгийн сайн мэддэг алгоритм бүхий асуудлын шийдлийн нарийн төвөгтэй байдлыг судалдаг. Алгоритмын нарийн төвөгтэй байдал нь түүний шийдэж буй асуудлын нарийн төвөгтэй байдлын хамгийн дээд хязгаарлалт болдог тул хоёр домэйн хоёулаа хоорондоо холбоотой байдаг. Цаашилбал, үр дүнтэй алгоритмыг бүтээхдээ тодорхой алгоритмын нарийн төвөгтэй байдлыг шийдвэрлэх асуудлын нарийн төвөгтэй байдалтай харьцуулах шаардлагатай байдаг. Ихэнх тохиолдолд асуудлын хүндрэлийн талаархи цорын ганц мэдээлэл нь мэдэгдэж байгаа хамгийн үр дүнтэй аргуудын нарийн төвөгтэй байдлаас бага байх явдал юм. Үүний үр дүнд алгоритмын шинжилгээ болон нарийн төвөгтэй байдлын онол хоёрын хооронд маш их давхцал үүсдэг.
Нарийн төвөгтэй байдлын онол нь зөвхөн компьютерийн шинжлэх ухааны үндэс суурь болох тооцооллын загваруудын үндэс суурь болохоос гадна орчин үеийн сүлжээ, ялангуяа интернетэд өргөн тархсан сонгодог тэгш хэмт бус криптографийн (нийтийн түлхүүрийн криптограф гэж нэрлэгддэг) үндэс суурийг тавихад чухал үүрэг гүйцэтгэдэг. Нийтийн түлхүүрийн шифрлэлт нь олон тооны тоог анхны хүчин зүйл болгон хуваах гэх мэт зарим тэгш бус математикийн бодлогуудыг тооцоолоход хэцүү байдаг (энэ үйлдэл нь нарийн төвөгтэй байдлын онолын ангилалд хэцүү асуудал юм, учир нь шийдвэрлэх боломжтой үр дүнтэй сонгодог алгоритмууд байдаггүй. Бодлогын оролтын хэмжээ ихсэхийн хэрээр экспоненциал бус харин олон гишүүнт байдлаар нөөцийг масштаблах замаар, энэ нь мэдэгдэж буй анхны хүчин зүйл рүү үржүүлэх маш энгийн урвуу үйлдлээс ялгаатай. Энэхүү тэгш бус байдлыг нийтийн түлхүүрийн криптографийн архитектурт ашиглах (нийтийн түлхүүрээс хялбархан тооцоолох боломжтой нийтийн түлхүүрийн хоорондох тооцооллын тэгш бус хамаарлыг тодорхойлох замаар, харин хувийн түлхүүр нь нийтийн түлхүүрээс хялбархан компьютер байж чадахгүй. нийтийн түлхүүрийг зарлаж, бусад харилцааны талуудад өгөгдлийг тэгш хэмт бус шифрлэхэд ашиглах боломжийг олгох ба дараа нь зөвхөн холбогдсон хувийн түлхүүрээр шифрлэгдэх боломжтой бөгөөд гуравдагч этгээдэд тооцоолох боломжгүй, ингэснээр харилцаа холбоог аюулгүй болгоно).
Тооцооллын нарийн төвөгтэй байдлын онолыг голчлон компьютерийн шинжлэх ухаан, алгоритмын анхдагчид, тухайлбал, дэлхийн 1939-р дайнд холбоотнууд ялахад чухал үүрэг гүйцэтгэсэн нацист Германы оньсого шифрийг задлахад чухал үүрэг гүйцэтгэсэн Алан Тюринг зэрэг хүмүүсийн ололт дээр тулгуурлан боловсруулсан. Нууцлагдмал мэдээллийг илрүүлэхийн тулд өгөгдөлд (голчлон шифрлэгдсэн харилцаа холбоо) дүн шинжилгээ хийх тооцооллын процессыг зохион бүтээх, автоматжуулахад чиглэсэн крипт шинжилгээ нь криптографийн системийг зөрчиж, ихэвчлэн цэргийн стратегийн ач холбогдолтой шифрлэгдсэн харилцааны агуулгад нэвтрэхэд ашиглагддаг. Энэ нь мөн анхны орчин үеийн компьютеруудын хөгжлийг хурдасгасан крипто-анализ байсан (эхэндээ код задлах стратегийн зорилгод хэрэглэж байсан). Британийн Колоссыг (орчин үеийн анхны электрон болон программ хангамжийн компьютер гэж үздэг) өмнө нь Мариан Режевскийн бүтээсэн оньсого шифрийг задлахад туслах зорилгоор зохион бүтээсэн электрон тооцоолох төхөөрөмж болох Польшийн "бөмбөг"-ийг Польшийн тагнуулынхан Их Британид хүлээлгэн өгчээ. XNUMX онд Польш улс Германд эзлэгдсэний дараа олзлогдсон Германы Enigma шифрлэлтийн машин. Энэхүү төхөөрөмжийн үндсэн дээр Алан Тюринг Германы шифрлэгдсэн холбоог амжилттай таслахын тулд илүү дэвшилтэт аналогийг бүтээж, улмаар орчин үеийн компьютер болгон хөгжүүлсэн.
Алгоритмыг ажиллуулахад шаардагдах нөөцийн хэмжээ нь оролтын хэмжээнээс хамаарч өөр өөр байдаг тул нарийн төвөгтэй байдлыг ихэвчлэн f(n) функцээр илэрхийлдэг бөгөөд энд n нь оролтын хэмжээ, f(n) нь хамгийн муу тохиолдлын нарийн төвөгтэй байдал ( n хэмжээтэй бүх оролтод шаардагдах нөөцийн хамгийн их хэмжээ) эсвэл дундаж тохиолдлын нарийн төвөгтэй байдал (n хэмжээтэй бүх оролт дээрх нөөцийн дүнгийн дундаж). n хэмжээтэй оролтод шаардагдах энгийн үйлдлүүдийн тоог ихэвчлэн цаг хугацааны нарийн төвөгтэй байдал гэж тодорхойлдог бөгөөд үндсэн үйлдлүүд нь тодорхой компьютер дээр тогтмол цаг зарцуулдаг бөгөөд өөр машин дээр ажиллахад зөвхөн тогтмол хүчин зүйлээр өөрчлөгддөг гэж үздэг. n хэмжээтэй оролтод алгоритмд шаардагдах санах ойн хэмжээг орон зайн нарийн төвөгтэй байдал гэж нэрлэдэг.
Цаг бол хамгийн түгээмэл нөөц гэж үздэг. "Төвөгтэй байдал" гэсэн нэр томъёог шалгуур үзүүлэлтгүйгээр ашиглах үед энэ нь ихэвчлэн цаг хугацааны нарийн төвөгтэй байдлыг илэрхийлдэг.
Уламжлалт цаг хугацааны нэгжүүд (секунд, минут гэх мэт) нь сонгосон компьютер, технологийн дэвшлээс хэт хамааралтай тул нарийн төвөгтэй байдлын онолд ашигладаггүй. Жишээлбэл, өнөөдрийн компьютер 1960-аад оны компьютерээс хамаагүй хурдан алгоритмыг гүйцэтгэж чаддаг ч энэ нь алгоритмын төрөлхийн чанараас илүүтэй компьютерийн техник хангамжид гарсан технологийн ололттой холбоотой юм. Нарийн төвөгтэй байдлын онолын зорилго нь алгоритмын төрөлхийн цаг хугацааны хэрэгцээ буюу алгоритм нь аливаа компьютерт тавих үндсэн хугацааны хязгаарлалтыг тооцоолох явдал юм. Тооцооллын явцад хэдэн үндсэн үйлдлийг гүйцэтгэснийг тоолох замаар үүнийг хийдэг. Эдгээр процедурыг тодорхой машинд тогтмол цаг зарцуулдаг (өөрөөр хэлбэл, оролтын хэмжээ тэдгээрт нөлөөлдөггүй) гэж үздэг тул тэдгээрийг үе шат гэж нэрлэдэг.
Өөр нэг чухал нөөц бол алгоритмыг гүйцэтгэхэд шаардагдах компьютерийн санах ойн хэмжээ юм.
Өөр нэг түгээмэл хэрэглэгддэг нөөц бол арифметик үйлдлийн хэмжээ юм. Энэ хувилбарт "арифметикийн нарийн төвөгтэй байдал" гэсэн нэр томъёог ашигладаг. Тооцооллын явцад гарч буй тоонуудын хоёртын дүрслэлийн хэмжээн дэх дээд хязгаарлалт мэдэгдэж байгаа тохиолдолд цаг хугацааны нарийн төвөгтэй байдал нь ерөнхийдөө арифметикийн нарийн төвөгтэй байдлын тогтмол хүчин зүйлийн үржвэр юм.
Тооцооллын явцад ашигласан бүхэл тоонуудын хэмжээ нь олон аргын хувьд хязгаарлагдахгүй бөгөөд арифметик үйлдлүүд нь тодорхой цаг хугацаа шаарддаг гэж үзэх нь бодитой бус юм. Үүний үр дүнд битийн нарийн төвөгтэй байдал гэж нэрлэгддэг цаг хугацааны нарийн төвөгтэй байдал нь арифметикийн нарийн төвөгтэй байдлаас хамаагүй өндөр байж болно. Жишээлбэл, nn бүхэл тоон матрицын тодорхойлогчийг тооцоолох арифметик хүндрэл нь стандарт техникийн хувьд O(n^3) байна (Гауссын арилгах). Тооцооллын явцад коэффициентүүдийн хэмжээ экспоненциалаар нэмэгдэж болзошгүй тул ижил аргуудын битийн нарийн төвөгтэй байдал нь n-д экспоненциал байна. Хэрэв эдгээр аргуудыг олон модультай арифметиктай хамт ашиглавал битийн нарийн төвөгтэй байдлыг O(n^4) болгож бууруулж болно.
Албан ёсны хэллэгээр битийн нарийн төвөгтэй байдал нь алгоритмыг ажиллуулахад шаардагдах бит дээр хийх үйлдлүүдийн тоог хэлнэ. Энэ нь ихэнх тооцооллын парадигмд тогтмол хүчин зүйл хүртэл цаг хугацааны нарийн төвөгтэй байдлыг тэнцүүлдэг. Компьютерт шаардагдах машины үгэн дээрх үйлдлийн тоо нь битийн нарийн төвөгтэй байдалтай пропорциональ байна. Тооцооллын бодит загваруудын хувьд цаг хугацааны нарийн төвөгтэй байдал ба битийн нарийн төвөгтэй байдал нь ижил байдаг.
Эрэмбэлэх, хайхад ихэвчлэн авч үздэг нөөц бол оруулгуудын харьцуулалтын хэмжээ юм. Хэрэв өгөгдөл сайн зохион байгуулагдсан бол энэ нь цаг хугацааны нарийн төвөгтэй байдлын сайн үзүүлэлт юм.
Бүх боломжит оролтууд дээр алгоритм дахь алхамуудын тоог тоолох боломжгүй юм. Оролтын нарийн төвөгтэй байдал хэмжээ нь өсдөг тул үүнийг ихэвчлэн оролтын n хэмжээтэй (битээр) илэрхийлдэг тул нарийн төвөгтэй байдал нь n-ийн функц юм. Гэсэн хэдий ч ижил хэмжээтэй оролтын хувьд алгоритмын нарийн төвөгтэй байдал нь ихээхэн ялгаатай байж болно. Үүний үр дүнд янз бүрийн нарийн төвөгтэй функцуудыг тогтмол ашигладаг.
Хамгийн муу тохиолдлын нарийн төвөгтэй байдал нь n хэмжээтэй бүх оролтын бүх нарийн төвөгтэй байдлын нийлбэр бөгөөд дундаж тохиолдлын нарийн төвөгтэй байдал нь n хэмжээтэй бүх оролтын бүх нарийн төвөгтэй байдлын нийлбэр юм (энэ нь утга учиртай, учир нь өгөгдсөн хэмжээний боломжит оролтын тоо хязгаарлагдмал). "Төвөгтэй байдал" гэсэн нэр томъёог нэмэлт тайлбаргүйгээр ашиглах үед хамгийн муу цаг хугацааны нарийн төвөгтэй байдлыг харгалзан үздэг.
Хамгийн муу болон дундаж тохиолдлын нарийн төвөгтэй байдлыг зөв тооцоолоход хэцүү байдаг. Цаашилбал, машин эсвэл тооцооллын парадигмын аливаа өөрчлөлт нь нарийн төвөгтэй байдлыг бага зэрэг өөрчилдөг тул эдгээр тодорхой утгууд нь практик хэрэглээ багатай байдаг. Цаашилбал, n-ийн жижиг утгын хувьд нөөцийн хэрэглээ чухал биш тул хэрэгжүүлэхэд хялбар байх нь жижиг n-ийн хувьд бага төвөгтэй байдлаас илүү сонирхолтой байдаг.
Эдгээр шалтгааны улмаас өндөр n-ийн хувьд нарийн төвөгтэй байдлын зан төлөвт хамгийн их анхаарал хандуулдаг, өөрөөр хэлбэл n-д хязгааргүй ойртох үед түүний асимптот шинж чанарт анхаарлаа хандуулдаг. Үүний үр дүнд нарийн төвөгтэй байдлыг илэрхийлэхийн тулд том O тэмдэглэгээг ихэвчлэн ашигладаг.
Тооцооллын загварууд
Хэсэг хугацааны туршид хийгддэг чухал үйлдлүүдийг тодорхойлохоос бүрдэх тооцооллын загварыг сонгох нь нарийн төвөгтэй байдлыг тодорхойлоход чухал ач холбогдолтой. Тооцооллын парадигмыг тусгайлан тайлбарлаагүй тохиолдолд үүнийг заримдаа олон соронзон хальсны Тюринг машин гэж нэрлэдэг.
Тооцооллын детерминистик загвар нь машины дараагийн төлөвүүд болон гүйцэтгэх үйлдлүүд нь өмнөх төлөвөөр бүхэлдээ тодорхойлогддог загвар юм. Рекурсив функцууд, ламбда тооцоолол, Тюринг машинууд нь анхны детерминист загварууд байсан. Санамсаргүй хандалтын машинууд (мөн RAM-машин гэгддэг) нь бодит компьютерийг дуурайлган дуурайлган хийх түгээмэл загвар юм.
Тооцооллын загвар тодорхойлогдоогүй тохиолдолд олон соронзон хальсны Тюринг машиныг ихэвчлэн төсөөлдөг. Олон соронзон хальсны Тюринг машинууд дээр цаг хугацааны нарийн төвөгтэй байдал нь ихэнх алгоритмуудын RAM машинуудынхтай адил байдаг ч санах ойд өгөгдлийг хэрхэн хадгалахад ихээхэн анхаарал хандуулах шаардлагатай байж магадгүй юм.
Тооцооллын тодорхой бус загварт, тухайлбал, детерминистик бус Тьюрингийн машинууд гэх мэт тооцооллын зарим үе шатанд янз бүрийн сонголтыг хийж болно. Нарийн төвөгтэй байдлын онолд бүх боломжит хувилбаруудыг нэгэн зэрэг авч үздэг бөгөөд тодорхой бус цаг хугацааны нарийн төвөгтэй байдал нь хамгийн сайн сонголтыг үргэлж хийх үед шаардагдах хугацаа юм. Өөрөөр хэлбэл, тооцооллыг шаардлагатай олон (ижил) процессорууд дээр зэрэг хийх бөгөөд детерминистик бус тооцооллын хугацаа нь эхний процессорын тооцооллыг дуусгахад зарцуулсан хугацаа юм. Энэхүү параллелизмыг жишээ нь Шорын жижиг бүхэл тоонуудын хүчин зүйлчлэл гэх мэт тусгай квант алгоритмуудыг ажиллуулах үед давхардсан орооцолдсон төлөвүүдийг ашиглан квант тооцоололд ашиглаж болно.
Ийм тооцооллын загвар нь одоогоор хэрэгжих боломжгүй байсан ч энэ нь онолын ач холбогдолтой, ялангуяа "олон гишүүнт цаг" ба "детерминистик бус олон гишүүнт цаг"-ыг ашиглан нарийн төвөгтэй байдлын ангиуд хамгийн багадаа дээд талд байгаа эсэхийг асуудаг P = NP асуудалтай холбоотой. хил хязгаар нь адилхан. Детерминистик компьютер дээр NP-алгоритмыг дуурайхад "экпоненциал хугацаа" шаардлагатай. Хэрэв даалгаврыг детерминистик бус систем дээр олон гишүүнт хугацаанд шийдвэрлэх боломжтой бол энэ нь NP хүндрэлийн ангилалд хамаарна. Хэрэв асуудал нь БЦГ-т байгаа бөгөөд бусад БЦГ-ын асуудлаас хялбар биш бол түүнийг NP-бүрэн гэж хэлнэ. Цүнхний асуудал, аялагч худалдагчийн асуудал, Булийн сэтгэл ханамжийн асуудал нь бүгд NP-ийн бүрэн комбинаторын бодлого юм. Хамгийн алдартай алгоритм нь эдгээр бүх асуудлын хувьд экспоненциал нарийн төвөгтэй байдаг. Хэрэв эдгээр асуудлуудын аль нэгийг детерминист машин дээр олон гишүүнт хугацаанд шийдэж чадвал бүх NP бодлогыг олон гишүүнт хугацаанд мөн шийдэж болох ба P = NP бий болно. 2017 оны байдлаар P NP нь БЦГ-ын асуудлын хамгийн муу нөхцөл байдлыг шийдвэрлэхэд үндсэндээ хэцүү, өөрөөр хэлбэл сонирхолтой оролтын уртыг харгалзан үзэх боломжтой аливаа боломжит хугацаанаас (арван жил) илүү урт хугацаа шаарддаг гэсэн үг юм.
Зэрэгцээ болон тархсан тооцоолол
Зэрэгцээ болон тархсан тооцоолол нь бүгд нэгэн зэрэг ажилладаг олон процессоруудад боловсруулалтыг хуваах явдал юм. Төрөл бүрийн загваруудын үндсэн ялгаа нь процессоруудын хооронд өгөгдөл дамжуулах арга юм. Процессоруудын хооронд өгөгдөл дамжуулах нь ихэвчлэн зэрэгцээ тооцоолоход маш хурдан байдаг бол тархсан тооцооллын процессоруудын хооронд өгөгдөл дамжуулах нь сүлжээгээр дамждаг тул харьцангуй удаан байдаг.
N процессор дээрх тооцоолол нь хамгийн багадаа нэг процессор дээр зарцуулсан хугацааны N-ийн хувийг авдаг. Бодит байдал дээр зарим дэд даалгавруудыг зэрэгцүүлэх боломжгүй бөгөөд зарим процессорууд өөр процессороос үр дүнг хүлээх шаардлагатай болдог тул онолын хувьд энэ хязгаарт хэзээ ч хүрч чадахгүй.
Гол төвөгтэй асуудал бол процессорын тоогоор тооцоолох хугацааны үржвэр нь нэг процессор дээр ижил тооцоолол хийхэд шаардагдах хугацаатай аль болох ойр байхаар алгоритм боловсруулах явдал юм.
Квантын тооцоолол
Квантын компьютер нь квант механикт суурилсан тооцооллын загвартай компьютер юм. Сүмийн-Тюрингийн дипломын ажил нь квант компьютерийн хувьд үнэн бөгөөд квант компьютер шийдэж чадах аливаа асуудлыг Тьюрингийн машинаар шийдэж болно гэсэн үг юм. Гэсэн хэдий ч зарим ажлыг онолын хувьд цаг хугацааны нарийн төвөгтэй байдал багатай сонгодог компьютер биш харин квант компьютер ашиглан шийдэж болно. Практик квант компьютерийг хэрхэн хөгжүүлэхийг хэн ч мэдэхгүй тул одоогоор энэ нь онолын хувьд хатуу юм.
Квантын нарийн төвөгтэй байдлын онолыг квант компьютерээр шийдэж болох янз бүрийн төрлийн асуудлыг судлах зорилгоор бүтээсэн. Энэ нь квант компьютерийн халдлагыг тэсвэрлэх чадвартай криптографийн протоколуудыг бий болгох үйл явц болох пост квант криптографид ашиглагддаг.
Асуудлын нарийн төвөгтэй байдал (доод хязгаар)
Асуудлыг шийдэж болох алгоритмуудын нарийн төвөгтэй байдал, түүний дотор нээгдээгүй арга техник нь асуудлын нарийн төвөгтэй байдал юм. Үүний үр дүнд асуудлын нарийн төвөгтэй байдал нь түүнийг шийдэж буй аливаа алгоритмын нарийн төвөгтэй байдалтай тэнцүү байна.
Үүний үр дүнд том O тэмдэглэгээнд өгөгдсөн аливаа нарийн төвөгтэй байдал нь алгоритм болон дагалдах асуудлын аль алиных нь нарийн төвөгтэй байдлыг илэрхийлдэг.
Нөгөөтэйгүүр, асуудлын нарийн төвөгтэй байдлын талаар энгийн бус доод хязгаарыг олж авах нь ихэвчлэн хэцүү байдаг бөгөөд үүнийг хийх стратеги цөөхөн байдаг.
Ихэнх асуудлыг шийдвэрлэхийн тулд бүх оролтын өгөгдлийг унших ёстой бөгөөд энэ нь өгөгдлийн хэмжээтэй пропорциональ цаг хугацаа шаарддаг. Үүний үр дүнд ийм асуудлууд нь наад зах нь шугаман төвөгтэй, эсвэл том омега тэмдэглэгээнд Ω(n)-ийн нарийн төвөгтэй байдалтай байдаг.
Компьютерийн алгебр, тооцооллын алгебрийн геометр зэрэг зарим асуудлууд маш том шийдэлтэй байдаг. Гаралт нь бичигдсэн байх ёстой тул нарийн төвөгтэй байдал нь гаралтын хамгийн их хэмжээгээр хязгаарлагддаг.
Ангилах алгоритмд шаардагдах харьцуулалтын тоо нь шугаман бус доод хязгаартай Ω(nlogn) байна. Үүний үр дүнд хамгийн сайн эрэмбэлэх алгоритмууд нь хамгийн үр дүнтэй байдаг, учир нь тэдгээрийн нарийн төвөгтэй байдал нь O(nlogn) юм. n байгаа нь баримт! n зүйлийг зохион байгуулах арга замууд нь энэ доод хязгаарт хүргэдэг. Учир нь харьцуулалт бүр n-ийн цуглуулгыг хуваадаг! дарааллыг хоёр хэсэг болгон хуваахад бүх дарааллыг ялгахад шаардагдах N харьцуулалтын тоо нь 2N > n! байх ёстой бөгөөд энэ нь Стирлингийн томъёогоор O(nlogn) гэсэн үг юм.
Асуудлыг өөр асуудал болгон багасгах нь нарийн төвөгтэй байдлын хязгаарлалтыг бууруулах нийтлэг стратеги юм.
Алгоритм боловсруулах
Алгоритмын нарийн төвөгтэй байдлыг үнэлэх нь дизайны үйл явцын чухал элемент бөгөөд энэ нь хүлээгдэж буй гүйцэтгэлийн талаар хэрэгтэй мэдээллийг өгдөг.
Орчин үеийн компьютерийн хүчин чадлын экспоненциал өсөлтийг урьдчилан таамагласан Мурын хуулийн үр дүнд алгоритмын нарийн төвөгтэй байдлыг үнэлэх нь ач холбогдол багатай болно гэсэн буруу ойлголт байнга гардаг. Энэ нь буруу, учир нь эрчим хүчний өсөлт нь асар их хэмжээний өгөгдлийг (том өгөгдөл) боловсруулах боломжийг олгодог. Жишээлбэл, номын ном зүй гэх мэт хэдэн зуун оруулгын жагсаалтыг цагаан толгойн дарааллаар эрэмбэлэх үед аливаа алгоритм секунд хүрэхгүй хугацаанд сайн ажиллах ёстой. Нөгөөтэйгүүр, нэг сая оруулгад (жишээлбэл, том хотын утасны дугаарууд) O(n2) харьцуулалтыг шаарддаг үндсэн алгоритмууд нь 10-ын хурдтай гурван цаг зарцуулагдах триллион харьцуулалт хийх шаардлагатай болно. секундэд сая харьцуулалт. Нөгөө талаас Түргэн эрэмбэлэх, нэгтгэх эрэмбэлэх нь зөвхөн nlogn харьцуулалт шаарддаг (эхнийх нь дундаж нарийн төвөгтэй байдал, сүүлийнх нь хамгийн муу тохиолдлын нарийн төвөгтэй байдал). Энэ нь n = 30,000,000-ийн хувьд ойролцоогоор 1,000,000 харьцуулалтыг гаргадаг бөгөөд энэ нь секундэд 3 сая харьцуулалт хийхэд ердөө 10 секунд зарцуулагдана.
Үүний үр дүнд нарийн төвөгтэй байдлыг үнэлэх нь хэрэгжүүлэхээс өмнө олон үр ашиггүй алгоритмуудыг арилгах боломжийг олгоно. Үүнийг мөн бүх боломжит хувилбаруудыг туршихгүйгээр нарийн төвөгтэй алгоритмуудыг тохируулахад ашиглаж болно. Нарийн төвөгтэй байдлыг судлах нь нарийн төвөгтэй алгоритмын хамгийн үнэтэй алхамуудыг тодорхойлох замаар хэрэгжилтийн үр ашгийг нэмэгдүүлэх хүчин чармайлтыг төвлөрүүлэх боломжийг олгодог.
Баталгаажуулалтын сургалтын хөтөлбөртэй дэлгэрэнгүй танилцахын тулд та доорх хүснэгтийг өргөжүүлж, дүн шинжилгээ хийж болно.
EITC/IS/CCTF Тооцооллын нарийн төвөгтэй байдлын онолын үндсэн гэрчилгээ олгох сургалтын хөтөлбөр нь видео хэлбэрээр нээлттэй хандалтын дидактик материалыг иш татдаг. Сургалтын үйл явц нь сургалтын хөтөлбөрийн холбогдох хэсгүүдийг хамарсан алхам алхмаар бүтцэд (хөтөлбөр -> хичээл -> сэдэв) хуваагдана. Оролцогчид цахим сургалтын интерфейсийн Асуулт ба хариултын хэсгээс хариултуудыг авч, илүү хамааралтай асуултуудыг асууж болно. Домэйн мэргэжилтнүүдтэй шууд, хязгааргүй зөвлөгөө өгөх нь платформын нэгдсэн онлайн мессежийн систем, түүнчлэн холбоо барих маягтаар дамжуулан авах боломжтой.
Баталгаажуулалтын журмын талаарх дэлгэрэнгүй мэдээллийг шалгана уу Хэрхэн ажилладаг.
Анхан шатны туслах сургалтын хөтөлбөр унших материал
С.Арора, Б. Барак, Тооцооллын төвөгтэй байдал: Орчин үеийн хандлага
https://theory.cs.princeton.edu/complexity/book.pdf
Хоёрдогч туслах сургалтын хөтөлбөр унших материал
О.Голдрейх, Нарийн төвөгтэй байдлын онолын танилцуулга:
https://www.wisdom.weizmann.ac.il/~oded/cc99.html
Дискрет математикийн сургалтын хөтөлбөрийг уншихад туслах материалууд
Ж.Аспнес, Дискрет математикийн тухай тэмдэглэл:
https://www.cs.yale.edu/homes/aspnes/classes/202/notes.pdf
График онолын талаархи сургалтын хөтөлбөрийг уншихад туслах материалууд
R. Diestel, Графикийн онол:
https://diestel-graph-theory.com/
EITC/IS/CCTF Computational Complexity Theory Fundamentals програмын бүрэн оффлайн бие даан суралцах бэлтгэл материалыг PDF файлаар татаж авна уу.
EITC/IS/CCTF бэлтгэх материал – стандарт хувилбар