Teorio de komputado

La teorio de komputado estas la branĉo de komputado, kiu traktas, ĉu kaj kiel komputaj taskoj povas esti kompetente solvitaj per komputilo. La kampo estas dividita en du ĉefajn branĉojn: teorio de komputebleco kaj komplikteorio, sed ambaŭ branĉoj formaligas modelojn de komputado.

Por efektivigi rigoran studadon de komputado, komputosciencistoj laboras kun matematikaj abstraktigoj de komputiloj nomataj modeloj de komputado. Kelkaj tipoj de tiaj modeloj estas uzataj, sed la plej kutimaj estas diversaj specoj de maŝino de Turing. Maŝino de Turing estas konceptebla kiel persona komputilo kun nelimigita memor-kapacito, kvankam ĉiupaŝe ĝi povas atingi nur etan diskretan porcion de de sia memoro. Fakuloj studas la maŝinon de Turing, ĉar ĝi estas simple formulebla, analizebla kaj kutime eblas pruvi la rezultojn, kaj ĉar ĝi prezentas tion, kion multaj konsideras adekvata modelo de la teorie plej pova komputo-kapablo. Dum la nelimigita memor-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, principe povas esti solvita per kutima reala komputilo, kiu havas sufiĉan memoron.

Teorio de komputebleco

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

Teorio de komputebleco 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 teorio de komputebleco. Estas neniu reala diferenco inter la kampoj krom tio, ĉu esploristo konsideras sin kiel fakulo pri komputoscienco aŭ pri matematiko.

Komplik-teorio

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.

Aliaj formalaj difinoj de kalkulado

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

• Lambda kalkulo: Kalkulado estas komenca λ esprimo (aŭ du esprimoj se bezonatas apartigi la funkcion de ĝia enigo) plus finia vico de λ termoj, ĉiu konkludita de la antaŭa termo per unu apliko de Β malpligrandiĝo.

• 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 devas esti apliko de baza funkcio aŭ apliko de funkcia komponado, primitiva rekursio aŭ μ-rekursio al antaŭe difinitaj elementoj de la vico. 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.

• Markova algoritmo: sistemo de manipulado de signovicoj, kiu uzas gramatikecajn regulojn por difini operaciojn sur vicoj de signoj. Ĉi tie la signoj estas ĝeneraligo de literoj, ciferoj ktp.

Aldone al la ĝeneralaj komputaj modeloj, iuj pli simplaj komputaj modeloj estas utilaj por specialaj, limigitaj aplikoj.

Ekzemple, Regulesprimoj, 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

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

Eksteraj ligiloj

• [1] Arkivigite je 2011-04-11 per la retarkivo Wayback Machine 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] Принципы развития теории алгоритмов - Evoluigo-principoj de teorio de algoritmoj