EITC/IS/CCTF Bingehên Teoriya Tevliheviya Hesabkirinê

Ji ber ku mîqdara çavkaniyên ku ji bo xebitandina algorîtmayek hewce dike bi mezinahiya têketinê diguhere, tevlihevî bi gelemperî wekî fonksiyonek f (n) tê diyar kirin, ku n mezinahiya têketinê ye û f (n) an tevliheviya rewşa herî xirab e ( mîqdara herî zêde ya çavkaniyên ku li ser hemî têketinên mezinahiya n hewce ne) an tevliheviya navînî (navgîniya mêjera çavkaniyan li ser hemî têketinên mezinahiya n). Hejmara operasyonên bingehîn ên pêwîst li ser têketinek mezinahiya n bi gelemperî wekî tevliheviya demê tête diyar kirin, ku tê bawer kirin ku operasyonên seretayî li ser komputerek taybetî demek domdar digire û dema ku li ser makîneyek cûda têne xebitandin tenê ji hêla faktorek domdar ve diguhezin. Mîqdara bîra ku ji algorîtmayek li ser têketina mezinahiya n hewce dike wekî tevliheviya cîhê tê zanîn.

Dem çavkaniya herî gelemperî ye ku tê hesibandin. Dema ku têgîna "tevlihevî" bê pîvan tê bikar anîn, ew bi gelemperî behsa tevliheviya demê dike.

Yekîneyên kevneşopî yên demê (çirk, hûrdem, û hwd) di teoriya tevliheviyê de nayên xebitandin ji ber ku ew pir bi komputera bijartî û pêşkeftina teknolojiyê ve girêdayî ne. Mînakî, komputerek îro dikare algorîtmayek ji komputerek ji salên 1960-an pir zûtir bimeşîne, lêbelê, ev ji ber pêşkeftinên teknolojîk ên di hardware ya komputerê de ne ji kalîteya xwerû ya algorîtmê ye. Armanca teoriya tevliheviyê ev e ku hewcedariyên dema xweyî yên algorîtmayan, an jî tixûbên demê yên bingehîn ên ku algorîtmayek li ser her komputerê ferz dike, bihejmêre. Ev bi jimartina çend operasyonên bingehîn di dema hesabkirinê de pêk tê. Van proseduran bi gelemperî wekî gavan têne binav kirin ji ber ku ew têne hesibandin ku wextê domdar li ser makîneyek taybetî digirin (ango, ew ji hêla mîqdara têketinê ve bêbandor in).

Çavkaniyek din a girîng hêjeya bîranîna komputerê ye ku ji bo pêkanîna algorîtmayan hewce dike.

Çavkaniyek din a ku pir caran tê bikar anîn mîqdara operasyonên jimartinê ye. Di vê senaryoyê de, têgîna "tevliheviya arîtmetîk" tê bikar anîn. Tevliheviya demê bi gelemperî ji hêla faktorek domdar ve hilbera tevliheviya arîtmetîk e, heke astengiyek jorîn li ser mezinahiya temsîla binar ya hejmarên ku di dema hesabkirinê de çêdibin were zanîn.

Mezinahiya hejmarên bêkêmasî yên ku di dema hesabkirinê de têne bikar anîn ji bo gelek rêbazan ne sînordar e, û ne rast e ku meriv bihesibîne ku operasyonên arîtmetîk demek diyarkirî hewce dike. Wekî encamek, tevliheviya demê, ku wekî tevliheviya bit jî tê zanîn, dibe ku ji tevliheviya jimartinê pirtir be. Zehmetiya arîtmetîk a jimartina diyarkera nn matrixek tevhejmar, wek nimûne, ji bo teknîkên standard O(n^3) e (hilberîna Gaussian). Ji ber ku dibe ku mezinahiya hevberan di dema hesabkirinê de bi berferehî berfireh bibe, tevliheviya bitê ya heman rêbazan di n-yê de berbiçav e. Ger van teknîkan bi jimareya pir-modular re bi kar bînin, tevliheviya bit dikare bibe O(n^4).

Tevliheviya bit, di warê fermî de, behsa hejmara operasyonên li ser bit-an dike ku ji bo xebitandina algorîtmayek hewce ne. Ew di piraniya paradîgmayên hesabkirinê de tevliheviya demkî heya faktorek domdar wekhev dike. Hejmara operasyonên li ser peyvên makîneyê yên ku ji hêla komputeran ve têne xwestin bi tevliheviya bit re têkildar e. Ji bo modelên rastîn ên hesabkirinê, tevliheviya demê û tevliheviya bit bi vî rengî yek in.

Çavkaniya ku bi gelemperî di veqetandin û lêgerînê de tê hesibandin, miqdara berhevokan e. Ger dane baş hatine rêz kirin, ev nîşanek baş a tevliheviya demê ye.

Li ser hemî têketinên potansiyel, jimartina hejmara gavên di algorîtmayekê de ne mimkûn e. Ji ber ku tevliheviya têketinê bi mezinahiya wê re zêde dibe, ew bi gelemperî wekî fonksiyonek mezinahiya têketinê n (bi bit) tê destnîşan kirin, û ji ber vê yekê tevlihevî fonksiyonek n-yê ye. Lêbelê, ji bo danûstendinên heman-pîvan, tevliheviya algorîtmayek bi giranî cûda dibe. Wekî encamek, cûrbecûr fonksiyonên tevliheviyê bi rêkûpêk têne bikar anîn.

Tevliheviya rewşa herî xirab ji bo hemî pîvana n têketinê berhevoka hemî tevliheviyê ye, dema ku tevliheviya navînî ji bo hemî pîvana n têketinê berhevoka hemî tevliheviyê ye (ev têgihîştî ye, ji ber ku hejmara têketinên gengaz ên mezinahiyek diyar e. dawî). Dema ku peyva "tevlihevî" bêyî ku bêtir were pênase kirin were bikar anîn, tevliheviya dema herî xirab tê hesibandin.

Tevliheviya rewşa herî xirab û navînî bi rengekî rast tê hesibandin dijwar e. Wekî din, van nirxên tam xwedan serlêdana pratîkî ya hindik in ji ber ku her guhertinek di paradîgmaya makîneyê an hesabkirinê de dê tevliheviyê hinekî cûda bike. Wekî din, karanîna çavkaniyê ji bo nirxên piçûk ên n-yê ne girîng e, ji ber vê yekê hêsaniya pêkanînê bi gelemperî ji tevliheviya kêm ji bo n-ya piçûk balkêştir e.

Ji ber van sedeman, herî zêde bal tê kişandin ser tevgera tevliheviyê ya ji bo n-ya bilind, ango tevgera wê ya asîmptotîk her ku n nêzî bêdawîbûnê dibe. Wekî encamek, nîşana O ya mezin bi gelemperî tête bikar anîn ku tevliheviyê nîşan bide.

Modelên Hesabkirinê

Hilbijartina modelek hesabkirinê, ku ji diyarkirina operasyonên bingehîn ên ku di yekîneyek demê de têne kirin pêk tê, di destnîşankirina tevliheviyê de girîng e. Gava ku paradîgmaya hesabkirinê bi taybetî nayê ravekirin carinan ev yek wekî makîneyek Turing a pir-tape tê binav kirin.

Modelek diyarker a hesabkirinê ew e ku tê de rewşên paşîn ên makîneyê û operasyonên ku têne kirin bi tevahî ji hêla rewşa berê ve têne diyar kirin. Fonksiyonên paşveger, hesabê lambda, û makîneyên Turing modelên yekem ên diyarker bûn. Makîneyên gihîştina rasthatî (wekî makîneyên RAM jî têne zanîn) ji bo simulasyona komputerên cîhana rastîn paradîgmayek populer in.

Dema ku modela hesabkirinê neyê diyarkirin, bi gelemperî makîneyek Turing a pir-tape tê texmîn kirin. Li ser makîneyên Turing-ê yên pir-tape, tevliheviya demê ji bo pir algorîtmayan wekî makîneyên RAM-ê ye, her çend ji bo bidestxistina vê wekheviyê jî baldariyek girîng di bîranînê de çawa tête hilanîn.

Vebijarkên cûrbecûr dikarin di hin gavên hesabkirinê de di modelek ne-determînîst a hesabkirinê de, wek makîneyên Turing ên ne diyarker, bêne çêkirin. Di teoriya tevliheviyê de, hemî vebijarkên mimkun di heman demê de têne hesibandin, û tevliheviya dema ne-determînîst ew e ku dema ku bijartinên çêtirîn her gav têne çêkirin hewcedariya wextê hewce dike. Ji bo ku bi rengek din were gotin, hesabkirin bi heman rengî li ser çend pêvajoyên (yeksan) yên ku hewce ne tê kirin, û dema hesabkirina ne-determînîst dema ku pêvajoya yekem digire da ku hesabkirinê temam bike. Dema ku algorîtmayên kuantûmê yên pispor dimeşînin, wek mînak faktorkirina jimareyên piçûk ên piçûk ji aliyê Shor ve, ev paralelîzim dikare di hesabkirina kuantûmê de bi karanîna rewşên tevlihevkirî yên serperekirî were bikar anîn.

Tewra ku modelek hesabkerî ya weha niha ne pêkan be jî, girîngiya wê ya teorîkî heye, nemaze di derbarê pirsgirêka P = NP de, ku dipirse gelo çînên tevliheviyê ku bi karanîna "dema pirnomî" û "dema pirnomî ya ne-determînîst" têne hilberandin wekî herî hindik jorîn. sînor yek in. Li ser komputerek diyarker, simulkirina algorîtmayek NP-ê "dema berbiçav" hewce dike. Ger karek li ser pergalek ne-determînîst di dema pirnomî de were çareser kirin, ew ji çîna dijwariya NP ye. Ger pirsgirêkek di NP-ê de be û ji pirsgirêkên din ên NP-ê ne hêsantir be, tê gotin ku ew NP-temam e. Pirsgirêka Knapsack, pirsgirêka firoşkerê gerok, û pirsgirêka têrbûna Boolean, hemî pirsgirêkên hevbeş ên NP-tevahî ne. Algorîtmaya herî naskirî ji bo van hemî pirsgirêkan tevliheviyek berbiçav heye. Ger yek ji van pirsgirêkan di dema pirnomî de li ser makîneyek diyarker were çareser kirin, wê hingê hemî pirsgirêkên NP dikarin di dema pirnomî de jî werin çareser kirin, û P = NP dê were damezrandin. Ji sala 2017-an ve, bi berfirehî tê texmîn kirin ku P NP, tê vê wateyê ku rewşên herî xirab ên pirsgirêkên NP-ê bi bingehîn dijwar in ku werin çareser kirin, ango, ji her demek gengaz (dehsalan) pir dirêjtir digire ku bi dirêjahiya têketina balkêş tê dayîn.

Computing paralel û belavkirî

Hesabkirina paralel û belavbûyî dabeşkirina pêvajoyê li ser gelek pêvajoyên ku hemî di heman demê de dixebitin vedihewîne. Cûdahiya bingehîn di navbera modelên cihêreng de rêbaza şandina daneyan di navbera pêvajokeran de ye. Veguheztina daneyê di navbera pêvajokeran de bi gelemperî di hesabkirina paralel de pir zû ye, di heman demê de veguheztina daneyê di navbera pêvajokeran de di hesabkirina belavbûyî de li seranserê torê tête kirin û bi vî rengî bi giranî hêdîtir e.

Hesabkirina li ser N-yê pêvajokeran bi kêmanî rêjeya N-ya dema ku li yek pêvajoyek digire digire. Di rastiyê de, ji ber ku hin binekarûbar nikarin werin paralel kirin û dibe ku hin pêvajo hewce bike ku li benda encamek ji pêvajoyek din bin, ev bendek îdeal a teorîkî dê çu carî neyê bidestxistin.

Pirsgirêka tevliheviya sereke bi vî rengî pêşxistina algorîtmayan e da ku hilbera dema hesabkirinê ji hêla hejmara pêvajoyan ve bi qasî ku gengaz nêzik be ji dema ku hewce dike ji bo pêkanîna heman hesabkirinê li ser pêvajoyek yekane.

Hesabkirina kuantumê

Komputera kuantûmê komputerek bi modela hesabkirinê ya li ser bingeha mekanîka kuantumê ye. Teza Church–Turing ji bo komputerên quantum rast e, tê vê wateyê ku her pirsgirêkek ku komputerek quantum dikare çareser bike jî dibe ku ji hêla makîneya Turing ve were çareser kirin. Lêbelê, dibe ku hin peywir bi teorîkî bi karanîna komputerek kuantûmê ne ji komputerek klasîk a bi tevliheviya demkî ya pir kêm kêm were çareser kirin. Heya nuha, ev bi hişkî teorîkî ye, ji ber ku kes nizane meriv çawa komputerek kuantumek pratîkî pêş dixe.

Teoriya tevliheviya quantumê ji bo lêkolînkirina cûreyên cûda yên ku ji hêla komputerên quantum ve têne çareser kirin hate afirandin. Ew di krîptografiya post-quantum de tê bikar anîn, ku ev pêvajoya afirandina protokolên krîptografî ye ku li hember êrişên komputera quantum berxwedêr in.

Tevliheviya pirsgirêkê (sînorên jêrîn)

Kêmasiya tevliheviya algorîtmayan ku dibe ku pirsgirêkê çareser bike, tevî teknîkên nedîtî, tevliheviya pirsgirêkê ye. Wekî encamek, tevliheviya pirsgirêkek bi tevliheviya her algorîtmayek ku wê çareser dike wekhev e.

Wekî encamek, her tevliheviyek ku di nîşeya O ya mezin de hatî dayîn tevliheviyek hem algorîtmayê û hem jî pirsgirêka pêvekirî temsîl dike.

Ji hêla din ve, bidestxistina tixûbên jêrîn ên ne-tewre li ser tevliheviya pirsgirêkê bi gelemperî dijwar e, û ji bo vê yekê çend stratejiyên hene.

Ji bo çareserkirina pir pirsgirêkan, pêdivî ye ku hemî daneyên têketinê werin xwendin, ku bi mezinahiya daneyan re dem digire. Wekî encamek, pirsgirêkên weha bi kêmanî tevliheviya xêzikî, an jî, di nîşana omega mezin de, tevliheviyek Ω(n) heye.

Hin pirsgirêk, wekî yên di cebraya kompîturê û geometriya cebrî ya hesabker de, xwedî çareseriyên pir mezin in. Ji ber ku divê hilber were nivîsandin, tevlihevî ji hêla mezinahiya herî zêde ya hilberê ve tê asteng kirin.

Hejmara danberhevên ku ji bo algorîtmayek birêkûpêk hewce ne, sînorê jêrîn ê Ω(nlogn) heye. Wekî encamek, algorîtmayên cûrbecûr çêtirîn çêtirîn in ji ber ku tevliheviya wan O(nlogn) ye. Rastiya ku n hene! awayên birêxistinkirina n tiştan ber bi vê sînorê jêrîn ve diçe. Ji ber ku her danberhev vê berhevoka n dabeş dike! emir dike du perçe, jimara N berawirdkirinên ku ji bo ferqkirina hemî rêzan hewce ne, divê 2N> n!, bi formula Stirling ve O(nlogn) destnîşan dike.

Kêmkirina pirsgirêkek ji pirsgirêkek din re stratejiyek hevpar e ji bo bidestxistina astengiyên tevliheviyê yên kêm.

Pêşveçûna algorîtmayê

Nirxandina tevliheviya algorîtmê hêmanek girîng a pêvajoya sêwiranê ye ji ber ku ew agahdariya kêrhatî li ser performansa ku dibe ku were hêvî kirin peyda dike.

Gelek caran têgihiştinek e ku, wekî encama qanûna Moore, ku pêşbîniya mezinbûna berbiçav a hêza komputera nûjen dike, nirxandina tevliheviya algorîtmayan dê kêmtir têkildar bibe. Ev nerast e ji ber ku hêza zêde destûrê dide hilberandina mîqdarên mezin ên daneyê (daneyên mezin). Mînakî, her algorîtmayek divê di kêmtirî saniyeyekê de baş bixebite dema ku bi alfabetîk navnîşek çend sed navnîşan, wek bîbliyografyaya pirtûkekê, rêz dike. Ji hêla din ve, ji bo mîlyonek navnîşan (mînak, hejmarên têlefonê yên bajarek mezin), algorîtmayên bingehîn ên ku muqayesekirina O(n2) hewce dike divê trîlyonek danberhevan pêk bînin, ku dê sê demjimêran bi leza 10 bidomîne. mîlyon danberhev di çirkeyê de. Ji aliyek din ve, cûrbecûr zû û yekbûyî, tenê berhevokên nlogn hewce dike (wek tevliheviya rewşa navîn ji bo ya pêşîn, wekî tevliheviya rewşa herî xirab ji bo ya paşîn). Ev dora 30,000,000 berawirdkirinê ji bo n = 1,000,000 çêdike, ku dê tenê 3 çirkeyan bi 10 mîlyon danberhevan di çirkekê de bigire.

Wekî encamek, nirxandina tevliheviyê dibe ku rê bide ji holê rakirina gelek algorîtmayên bêserûber berî bicîhkirinê. Di heman demê de ev dikare were bikar anîn da ku algorîtmayên tevlihev baş bikşîne bêyî ceribandina hemî guhertoyên gengaz. Lêkolîna tevliheviyê dihêle ku bi destnîşankirina gavên herî biha yên algorîtmayek tevlihev ve balê bikişîne ser hewildana ji bo zêdekirina karbidestiya pêkanînê.