EITC/IS/CCTF Тооцооллын нарийн төвөгтэй байдлын онолын үндэс

Алгоритмыг ажиллуулахад шаардагдах нөөцийн хэмжээ нь оролтын хэмжээнээс хамаарч өөр өөр байдаг тул нарийн төвөгтэй байдлыг ихэвчлэн 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 секунд зарцуулагдана.

Үүний үр дүнд нарийн төвөгтэй байдлыг үнэлэх нь хэрэгжүүлэхээс өмнө олон үр ашиггүй алгоритмуудыг арилгах боломжийг олгоно. Үүнийг мөн бүх боломжит хувилбаруудыг туршихгүйгээр нарийн төвөгтэй алгоритмуудыг тохируулахад ашиглаж болно. Нарийн төвөгтэй байдлыг судлах нь нарийн төвөгтэй алгоритмын хамгийн үнэтэй алхамуудыг тодорхойлох замаар хэрэгжилтийн үр ашгийг нэмэгдүүлэх хүчин чармайлтыг төвлөрүүлэх боломжийг олгодог.