computational problem

computational problem (tsz. computational problems)

1. (informatika, mesterséges intelligencia)

A computational problem (számítási probléma) egy formális kérdés, amely bemenet(ek) alapján valamilyen kimenetet (választ) vár. Ez az informatikai és algoritmikus gondolkodás legalapvetőbb fogalma, amelyre az algoritmusok, programozás és bonyolultságelmélet épül.

Egy számítási probléma egy lehetséges bemenetekből álló halmazhoz (pl. bináris stringek) egy kimeneti értéket rendel – lehet döntési, konstrukciós vagy optimalizálási jellegű.

Formálisan:

• Egy számítási probléma ${\textstyle P}$ egy függvény:

  $${\displaystyle P:\Sigma ^{*}\rightarrow \Sigma ^{*}}$$

  ahol ${\textstyle \Sigma }$ egy ábécé (pl. bináris: ${\textstyle \{0,1\}}$), és ${\textstyle \Sigma ^{*}}$ minden lehetséges string.

Probléma	Bemenet	Kimenet
Prímszám-ellenőrzés	Egy szám ${\textstyle n}$	Igen/Nem
Összeadás	Két egész szám ${\textstyle a,b}$	${\textstyle a+b}$
Sudoku megfejtés	Részben kitöltött tábla	Kitöltött, szabályos tábla
Legnagyobb közös osztó	Két szám ${\textstyle a,b}$	${\textstyle \gcd(a,b)}$
Travelling Salesman	Városok és távolságok	Legrövidebb körút hossza
Rendezés	Lista	Rendezett lista

Egy probléma megoldása egy algoritmus, amely:

• Végrehajtható lépésekből áll,
• Minden bemenetre választ ad (ha a probléma teljesen definiált),
• Eldönti, kiszámítja vagy optimalizálja a kívánt célt.

def sort_problem(lst):
    return sorted(lst)

print(sort_problem())
# → 

Ez egy konstrukciós probléma: a bemenet egy lista, a kimenet a megfelelően rendezett verzió.

• computational problem - Szótár.net (en-hu)
• computational problem - Sztaki (en-hu)
• computational problem - Merriam–Webster
• computational problem - Cambridge
• computational problem - WordNet
• computational problem - Яндекс (en-ru)
• computational problem - Google (en-hu)
• computational problem - Wikidata
• computational problem - Wikipédia (angol)