Algoritmusok
Dátum
Authors
Folyóirat címe
Folyóirat ISSN
Kötet címe (évfolyam száma)
Kiadó
DOI
Absztrakt
Az algoritmus a matematika és az informatika fontos fogalma. Az elméleti informatika egyes részterületei foglalkoznak velük, így az algoritmuselmélet, a bonyolultságelmélet, és a kiszámíthatóságelmélet. Az algoritmusok formálisan többféleképpen is reprezentálhatók. Ezek az algoritmusok, mint absztrakt objektumtól a konkrét számítógépi programig terjednek. Turing-géppel formális definíció adható az algoritmus fogalmára: Egy probléma megoldására adott utasítássorozat akkor tekinthető algoritmusnak, ha van egy vele ekvivalens Turing-gép, ami minden megoldható bemenetre megáll. A Markov-algoritmus, a Post-féle rendszer, a lambda-kalkulus és a kombinátor logika ugyanabba a kiszámítási osztályba tartozik, mint a Turing-gép.