Decidoproblemo: Malsamoj inter versioj
| [kontrolita revizio] | [kontrolita revizio] |
Enhavo forigita Enhavo aldonita
riparis ruĝligo kaj aldonis kelkajn frazojn |
pli da alineojn |
||
Linio 6:
Ekzemple, la problemo “donite du numeroj ''x'' kaj ''y,'' ĉu ''x'' divizoras ''y''?” estas decidoproblemo. La respondo povas esti aŭ ‘jes’ aŭ ‘ne,’ kaj dependas sur la valoroj de ''x'' kaj ''y''. Solvadmetodo por decidoproblemo, donita en [[algoritmo|algoritma]] formo, nomiĝas '''decidoprocedo''' por tiu problemo. Decidoprocedo por la decidoproblemo “donite du numeroj ''x'' kaj ''y,'' ĉu ''x'' divizoras ''y''?” donas la manipuloj kiuj determinas ĉu ''x'' divizoras ''y'', donite ''x'' kaj ''y''. Unu tia algoritmo estas [[longa dividado]], kiu ĉiuj lernantoj devas lerni. Se la cetero estas nulo, la respondo estas 'jes'; alie, ĝi estas 'ne'. Decidoproblemo kiu solveblas per algoritmo, kiel ĉi tiu ekzemplo, nomiĝas ''decidebla''.
La fako de komputa kompliko kategoriigas decideblajn decidoproblemojn laŭ kiel malfacile ili solvendas. "Malfacila", en tiu senco, priskribiĝas laŭ la komputaj rimedoj, kiuj la plej efika algoritmo bezonas por iu problemo. La fako de [[teorio de komputeblo|rikurteorio]], dume, kategoriigas nedecideblajn decidoproblemojn laŭ [[turinga grado]], kiu estas mezuro de la nekomputeblo de ajna solvo. Decidoproblemoj proksime rilatas al [[funkcioproblemo]]j, kiuj povas havi respondojn pli kompleksajn ol simpla "jes" aŭ "ne". Ekvivalenta funkcioproblemo estas "donite du numeroj ''x'' kaj ''y,'' kio estas ''x'' dividita per ''y''?" Ili ankaŭ rilatas al [[problemo de optimumigo|problemoj de optimumigo]], kiuj temas pri trovado de la ''plej bona'' respondo al specifa problemo. Ekzistas normaj teknikoj transformi funkcioproblemojn kaj problemojn de optimumigo en decidoproblemojn, kaj inverse, kiuj ne signife ŝanĝi la komputan malfacilaĵon de ĉi tiuj problemoj. Por tiu kialo, esploro en teorio de komputeblo kaj komplikteorio tipe centras sur decidoproblemojn.
==Difino==
Decidoproblemo estas ajna arbitra jes-aŭ-ne demando sur malfinia aro de enigoj. Pro ĉi tio, tradicie oni egalvalore difinas la decidoproblemon kiel la aro de enigoj por kiu la problemo revenigas jes.
Tiuj enigoj eblas esti [[natura nombro|naturaj nombroj]] aŭ valoroj de iu alia speco, kiel [[ĉeno (komputiko)|ĉeno]]j super la [[duuma sistempo|duuma]] [[alfabeto (komputiko)|alfabeto {0,1}]] aŭ super iu alia finia [[simbolo|simbolaro]]. La subaro de ĉenoj aŭ signovicoj por kiu la problemo revenigas "jes" estas [[formala lingvo]], kaj ofte decidoproblemoj difiniĝas tiamaniere kiel formalaj lingvoj.
Alikaze, per kodigo kiel [[godela numerado]], iu ajn ĉeno povas kodiĝi kiel natura nombro, per kiu decidoproblemo difineblas kiel subaro de la naturaj nombroj.
==Referencoj==
| |||