Teorio de komputado

El Vikipedio, la libera enciklopedio
Saltu al: navigado, serĉo

La teorio de kalkulado estas la branĉo de komputiko kiu traktas ĉu kaj kiel kompetente problemoj povas esti solvitaj per komputilo. La kampo estas dividita en du ĉefaj branĉoj: komputebleca teorio kaj komplikteorio, sed ambaŭ branĉoj alpaŝas formalajn modelojn de kalkulado.

Por plenumi rigoran studon de kalkulado, komputilo-sciencistoj laboras kun matematikaj abstraktaĵoj de komputiloj nomataj kiel modelo de kalkulado. Estas kelkaj formulaĵoj uzataj, sed la plej kutime ekzamenata estas la maŝino de Turing. Maŝino de Turing povas esti konceptita kiel labortabla persona komputilo kun malfinia memora kapacito, kvankam ĝi povas atingi tiun memoron nur en malgrandaj diskretaj buloj. Komputikistoj studas la maŝinon de Turing ĉar ĝi estas simple formulebla, povas esti analizita kaj kutime eblas pruvi la rezultojn, kaj ĉar ĝi prezentas tion kion multaj konsideras kiel la plej pova ebla "modera" modelo de kalkulado. Dum la malfinia memora kapacito povus esti konsiderata nefizika atributo, por ajna problemo reale solvata per maŝino de Turing la memoro uzata ĉiam estas finia, do ajna problemo, kiu povas esti solvita per maŝino de Turing povis esti solvita per kutima reala komputilo, kiu havas sufiĉan memoron.

Komputebleca teorio[redakti | redakti fonton]

Komputebleca teorio traktas unuavice la demandon ĉu problemo estas entute solvebla per komputilo. La problemo de haltado estas unu el la plej gravaj rezultoj en komputebleca teorio, ĉar ĝi estas ekzemplo de konkreta problemo kiu estas kaj facile formulebla kaj kiun neeblas solvi per maŝino de Turing. Multo de komputebleca teorio konstruiĝas sur la rezulto pri la problemo de haltado.

Komputebleca teorio estas proksime rilata al la branĉo de matematika logiko nomata kiel rekursia teorio, kiu forprenas la limigon de studado nur modelojn de kalkulado kiuj estas proksimaj al fizike realigeblaj. Multaj matematikistoj kiuj studas rekursian teorion nomas ĝin kiel komputebleca teorio. Estas neniu reala diferenco inter la kampoj krom ĉu esploristo konsideras sin kiel rilatantan al komputikomatematiko.

Komplik-teorio[redakti | redakti fonton]

Komplikteorio konsideras ne nur ĉu problemo entute povas esti solvita perr komputilo, sed ankaŭ kiel kompetente la problemo povas esti solvita. Du ĉefaj aspektoj estas konsiderataj: tempa komplikeco kaj spaca komplikeco, kiuj estas respektive kiu kvanto da paŝoj necesas por plenumi la kalkuladon, kaj kiu kvanto da memoro estas bezonata por plenumi la kalkuladon.

Por analizi bezonatajn tempon kaj spacon por donita algoritmo, oni esprimas la kvanton de la tempo aŭ spaco kiel funkcio de la amplekso de la enigo-problemo. Ekzemple, trovo de aparta nombro en longa listo de nombroj iĝas ju pli pezan des pli la listo estas longa. Se estas n nombroj en la listo, tiam se la listo estas ne ordigita aŭ indeksita en ia maniero, tiam oni eble devos kontroli ĉiun nombron por trovi la nombro kion oni celas. Oni tial diras, ke por solvi ĉi tiun problemon, la komputilo bezonas plenumi kvanton de paŝoj kreskas lineare laŭ la amplekso de la problemo.

Por simpligi tiun problemon, komputistoj uzas la notacion granda O, kiu permesas al funkcioj esti komparitaj kvazaŭ tiel ke apartaj aspektoj de maŝina aparataro ne bezone estas konsiderataj, sed konsiderante nur la asimptotan konduton de la problemoj, kiam la problemoj iĝas grandajn. Do en nia antaŭa ekzemplo oni povas diri, ke la problemo postulas O(n) paŝojn por solvado.

Eble la plej grava malferma problemo entute en komputiko estas la demando ĉu problemoj de certa larĝa klaso nomata kiel NP povas esti solvataj kompetente. Ĉi tiu estas diskutita plu en komplikecaj klasoj P kaj NP.

Alia formalaj difinoj de kalkulado[redakti | redakti fonton]

Krom maŝino de Turing, aliaj ekvivalentaj modeloj de kalkulado uzatas (pri la ekvivalenteco vidu en tezo de Church-Turing).

  • Rekursiaj funkcioj: kalkulado estas rekursia funkcio, kio estas ĝia difinanta vico, iu ajn enigo-valoro(j) kaj vico de rekursiaj funkcioj troviĝantaj en la difinanta vico kun enigoj kaj eligoj. Tial ekzemple, se en la difinanta vico de rekursia funkcio f(x) la funkcioj g(x) kaj h(x,y) aperas, tiam termoj de formo 'g(5)=7' aŭ 'h(3,2)=10' povas aperi. Ĉiu termo en ĉi tiu vico bezonas esti apliko de baza funkcio aŭ sekvo de la elementoj pli supre per uzo de komponaĵo, primitiva rekursio aŭ μ rekursio. Ekzemple se f(x)=h(x,g(x)), tiam por ke aperu 'f(5)=3', termoj kiel 'g(5)=6' kaj 'h(3,6)=3' devas okazi pli supre. La kalkulado finiĝas nur se la fina termo donas la valoron de la rekursia funkcio aplikata al la enigoj.

Aldone al la ĝeneralaj komputaj modeloj, iuj pli simplaj komputaj modeloj estas utilaj por specialaj, limigitaj aplikoj. Regulesprimoj, ekzemple, estas uzataj por precizigi liniajn ŝablonojn en Unikso kaj en iuj programlingvoj kiel Perl. Alia formalismo matematike ekvivalento al regulesprimoj, finiaj aŭtomatoj estas uzataj en cirkvita dizajno kaj en iuj specoj de problemo-solvado. Ĉirkaŭteksto-liberaj gramatikoj estas uzataj por precizigi programlingvan sintakson. Ne-determinismaj aŭtomatoj estas alia formalisma ekvivalento al ĉirkaŭteksto-liberaj gramatikoj. Primitivaj rekursiaj funkcioj estas difinita subklaso de la rekursiaj funkcioj.

Malsamaj modeloj de kalkulado havas la kapablon fari malsamajn taskojn. Unidirekta ebleco mezuri la povo de komputa modelo estas studi la klason de formalaj lingvoj, kiujn la modelo povas generi; tio kondukas al la hierarkio laŭ Ĉomski de lingvoj.

Plua legado[redakti | redakti fonton]

  • Hartley Rogers, Jr, Teorio de Rekursie Funkcioj kaj Efika Komputebleco, MIT Press, 1987, ISBN 0-262-68052-1 (broŝuro)

Eksteraj ligiloj[redakti | redakti fonton]

  • [1] Komputebleca logiko: teorio de interaga kalkulado. TTT fonto pri ĉi tiu subjekto.
  • http://th-algoritmov.narod.ru/
  • [2] А.Китаев, А.Шень, М.Вялый. Классические и квантовые вычисления - Klasikaj kaj kvantumaj komputadoj
  • [3] Миниэнциклопедия по теории сложности и комбинаторным алгоритмам - Eta enciklopedio pri komplikteorio kaj kombinatoraj algoritmoj
  • [4] Лекции по теории сложности и комбинаторным алгоритмам - Pri komplikteorio kaj kombinatoraj algoritmoj
  • [5] Принципы развития теории алгоритмов - Evoluo de teorio de algoritmoj