Algoritmus, szisztematikus eljárás, amely - véges számú lépésben - választ ad egy kérdésre vagy egy probléma megoldására. A név az Al-Khwarizmi 9. századi muszlim matematikus, az Al-Khwarizmi „Al-Khwarizmi a hindu számítás művészetéről” című aritmetikai értekezésének latin fordításából, az Algoritmi de numero Indorum-ból származik.
számítástechnika: algoritmusok és összetettség
Az algoritmus egy speciális eljárás egy jól meghatározott számítási probléma megoldására. Alapvető fontosságú az algoritmusok fejlesztése és elemzése
Csak véges esetekkel vagy értékekkel kapcsolatos kérdések vagy problémák esetén mindig létezik algoritmus (legalábbis elvben); a válaszok értékeit tartalmazó táblázatból áll. Általában nem olyan triviális eljárás, hogy válaszoljunk olyan kérdésekre vagy problémákra, amelyeknél végtelen számú esetet vagy értéket kell figyelembe venni, például: „A természetes szám (1, 2, 3, …) prím?” vagy „Mi az a és b természetes számok legnagyobb közös osztója?” Ezek közül a kérdések közül az első egy decidable nevű osztályhoz tartozik; egy algoritmust, amely igen vagy nem választ ad, döntési eljárásnak nevezzük. A második kérdés egy kiszámíthatóságú osztályhoz tartozik; egy algoritmust, amely egy adott számú válaszhoz vezet, számítási eljárásnak nevezzük.
Algoritmusok léteznek sok ilyen kérdés végtelen osztályához; Az Euclid Elements, kb. 300 mp-en jelentek meg, tartalmazott egyet a két természetes szám legnagyobb közös osztójának megtalálására. Minden általános iskolás diákot hosszú osztásban vesznek részt, ami algoritmus arra a kérdésre, hogy „Ha egy természetes számot elosztunk egy másik b természetes számmal, mi a hányados és a fennmaradó rész?” Ennek a számítási eljárásnak a segítségével választ kaphat az eldönthető kérdésre: „b osztja-e az a-t?” (a válasz igen, ha a fennmaradó érték nulla). Ezen algoritmusok ismételt alkalmazása végül megkapja a választ a „Van egy prím?” Kérdésre. (Nem válasz akkor, ha az 1 osztható egy kisebb természetes számmal is, az 1-en kívül).
Időnként nem létezhet algoritmus a végtelen problémák osztályának megoldására, különösen akkor, ha az elfogadott módszerre további korlátozások vonatkoznak. Például két Euclid korából származó, csak iránytű és egyenes vonalú (jelölet nélküli vonalzó) használatával járó két problémát - egy szög megvágását és egy adott körnek megfelelő területű négyzet felépítését - évszázadok óta kezelik, mielőtt lehetetlennek bizonyultak.. A 20. század fordulóján, a befolyásos német matematikus, David Hilbert 23 problémát javasolt a matematikusok számára az elkövetkező században. A listáján szereplő második probléma a számtani axiómák konzisztenciájának vizsgálatát kérte. A legtöbb matematikusnak nem volt kétsége afelől, hogy ezt a célt valóban elérje 1931-ig, amikor az osztrák születésű logikus Kurt Gödel megmutatta azt a meglepő eredményt, hogy léteznie kell olyan aritmetikai javaslatoknak (vagy kérdéseknek), amelyeket nem lehet bizonyítani vagy megcáfolni. Lényegében minden ilyen állítás olyan meghatározási eljáráshoz vezet, amely soha nem ér véget (ezt a feltételt nevezzük megállási problémának). Alan Turing az angol matematikus és logikus, az angol matematikus és logikus, szigorúan meghatározta az algoritmus lazán érthető fogalmát, és sikertelen erőfeszítéseket tett annak megállapítására, hogy mely állítások legalább megoldatlanok. Bár Turing bebizonyította, hogy léteznie kell megválaszthatatlan javaslatoknak, az általános célú algoritmus-gépek, vagyis a Turing-gépek lényeges tulajdonságainak leírása a számítógépes tudomány alapjává vált. Manapság a dönthetőség és a kiszámíthatóság kérdése központi jelentőségű a számítógépes program megtervezésében - ez egy speciális algoritmus.
