algorithm (tsz. algorithms)
Az algoritmus egy véges számú, egyértelműen meghatározott lépésekből álló utasítássorozat, amely egy adott probléma megoldására szolgál. A számítástudomány és a matematika egyik legalapvetőbb fogalma: minden program, minden számítás mögött algoritmusok állnak.
Röviden: egy lépésekből álló terv a probléma megoldására.
Hétköznapi példa: – Recept egy étel elkészítéséhez – Útmutató egy IKEA-bútor összeszereléséhez – Lépésről lépésre módszer egy matematikai egyenlet megoldásához
Egy algoritmus akkor helyes és használható, ha:
| Tulajdonság | Jelentés |
|---|---|
| Végesség | Minden bemenetre véges lépésben leáll |
| Determináltság | Minden lépés egyértelműen definiált |
| Bemenet | 0 vagy több adatot kap |
| Kimenet | Legalább egy eredményt szolgáltat |
| Hatékonyság | Optimálisan használja az erőforrásokat (idő, memória) |
| Típus | Példa |
|---|---|
| Keresési algoritmusok | Bináris keresés, lineáris keresés |
| Rendezési algoritmusok | Buborékrendezés, quicksort, mergesort |
| Graf-algoritmusok | Dijkstra, BFS, DFS, Kruskal |
| Dinamikus programozás | Fibonacci-sorozat, hátizsákprobléma |
| Heurisztikus algoritmusok | A*, genetikus algoritmus |
| Kriptográfiai algoritmusok | RSA, AES, SHA |
| Számelméleti algoritmusok | Prímtényezés, Euklideszi algoritmus |
Cél: két szám legnagyobb közös osztójának (LNKO) meghatározása
1. Adott két szám: a és b
2. Amíg b ≠ 0, ismételd:
- c := a mod b
- a := b
- b := c
3. Ha b = 0, akkor LNKO = a
Az algoritmus elvont leírás, míg a program ennek konkrét megvalósítása egy adott nyelven (pl. Python, C++).
def gcd(a, b):
while b != 0:
a, b = b, a % b
return a
Az algoritmusokat aszerint is értékeljük, hogy mennyi ideig és memóriáig futnak különböző bemenetekre.
| Jelölés | Növekedés |
|---|---|
| O(1) | konstans idő |
| O(log n) | logaritmikus (pl. bináris keresés) |
| O(n) | lineáris |
| O(n log n) | hatékony rendezések |
| O(n²) | lassabb algoritmusok (pl. buborékrendezés) |
| O(2ⁿ) | exponenciális (pl. brute-force kombinációk) |
| Ág | Mit vizsgál |
|---|---|
| Algoritmus-analízis | Futásidő, erőforrás-igény |
| Algoritmus-design | Új algoritmusok tervezése |
| Bonyolultságelmélet | Problémák megoldhatósága, nehézsége (pl. NP-teljes) |
| Párhuzamos algoritmusok | Többmagos számításon való hatékony működés |
| Randomizált algoritmusok | Véletlent is felhasználó algoritmusok |
Az algoritmus egy lépésről lépésre követhető problémamegoldó módszer, amely a számítástudomány alapja. Lehet egyszerű és konkrét, vagy rendkívül elvont és összetett. Minden program, szoftver és számítás valamilyen algoritmus szerint működik – az algoritmusok jelentik a logikai gépezet szívét.