Decidoproblemo: Malsamoj inter versioj
| [kontrolita revizio] | [kontrolita revizio] |
Enhavo forigita Enhavo aldonita
Nova ĝermo, bazita sur la angla artikolo "Decision problem" |
aldonis tekston kaj kategoriojn |
||
Linio 4:
En [[komputebloteorio]] kaj [[komputa komplikteorio]], '''decidoproblemo''' estas demando en iu [[formala sistemo]] kun jes-aŭ-ne respondo, depende de la valoroj de kelkaj enigaj parametroj. Decidoproblemoj tipe prezentiĝas en matematikaj demandoj de [[decideblo (logiko)|decideblo]], t.e., la demando pri la ekzisto de [[efika metodo]] determini la ekziston de iu objekto aŭ ĝian membrecon en aro; kelkaj el la plej gravaj problemoj en matematiko estas [[nedecidebla problemo|nedecidebla]]j.
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 [[algoritma|algoritmo]] 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''.
==Referencoj==
{{Reflist}}
[[Kategorio:Matematiko]]
[[Kategorio:Matematika logiko]]
[[Kategorio:Problem-solvado]]
| |||