deterministic algorithm (tsz. deterministic algorithms)
A deterministic algorithm (magyarul: determinisztikus algoritmus) olyan algoritmus, amely ugyanazon bemenet esetén mindig pontosan ugyanazt a végrehajtási sorrendet és ugyanazt a kimenetet adja. Minden döntési lépése előre meghatározott, és nem használ véletlenszerűséget.
Egy algoritmus determinista, ha minden egyes lépése egyértelműen meghatározott, és a bemenettől egyértelműen meghatározható a következő állapota.
Más szóval:
| Algoritmus | Leírás |
|---|---|
| Bubble sort | Mindig ugyanabban a sorrendben hasonlítja össze és cseréli az elemeket |
| Binary search | Középső elem alapján halad balra vagy jobbra egy rendezett listán |
| Euclidean algorithm | Két szám legnagyobb közös osztójának meghatározása lépésről lépésre |
| Depth-First Search (DFS) | Determinisztikus, ha az elágazási sorrend is meghatározott |
A deterministic Turing machine (DTM) olyan elméleti számítási modell, amelyben:
Ez a modell az alapja a P osztály (polinomiális időben determinisztikusan megoldható problémák) definíciójának.
| Típus | Leírás |
|---|---|
| Deterministic | Egyértelmű lépések, egy eredmény |
| Non-deterministic | Több lehetséges lépés → „több univerzum kipróbálása egyszerre” (elméleti modell) |
| Randomized (véletlenített) | Véletlenszámokat is használ → kimenet változhat, még ha a bemenet azonos is |
| Probléma | Determinisztikus algoritmus | Véletlenített alternatíva |
|---|---|---|
| Rendezés | MergeSort, BubbleSort | Randomized QuickSort |
| GCD | Euclidean algorithm | – |
| Prímszűrés | Szita algoritmus (Eratosthenész) | Miller–Rabin teszt |
| Keresés | Lineáris vagy bináris keresés | Véletlen mintavételezés |
| Fogalom | Jelentés |
|---|---|
| Deterministic algorithm | Egy algoritmus, amely mindig ugyanúgy viselkedik ugyanazon bemenetre |
| Tulajdonságai | Előre meghatározott, nem használ véletlenséget |
| Előnyei | Megbízható, tesztelhető, replikálható |
| Példák | Rendező algoritmusok, keresési algoritmusok, GCD kiszámítása |