Wikiszótár

determinisztikus algoritmus

Magyar

Kiejtés

  • IPA: [ ˈdɛtɛrministikuʃɒlɡoritmuʃ]

Főnév

determinisztikus algoritmus

  1. (matematika)

Determinisztikus algoritmus

A determinisztikus algoritmus olyan algoritmus, amely adott bemenet esetén mindig ugyanazt az eredményt adja, és végrehajtása során a lépések pontosan meghatározottak. Minden lépés előre definiált és nem tartalmaz véletlenszerűséget vagy bizonytalanságot.


Jellemzők

  1. Előre meghatározott viselkedés:

Az algoritmus végrehajtása teljesen kiszámítható.

  1. Konzisztens eredmény:

Ugyanarra a bemenetre mindig ugyanazt az eredményt adja.

  1. Idő- és térbonyolultság:

Az algoritmus idő- és tárhasználata rögzített, a bemenettől függően.


Példák determinisztikus algoritmusokra

  1. Keresési algoritmus:

Pl. Lineáris vagy bináris keresés.

  1. Rendezési algoritmusok:
    • Buborékrendezés (Bubble Sort)
    • Kiválasztásos rendezés (Selection Sort)
    • Beszúró rendezés (Insertion Sort)
    • Gyorsrendezés determinisztikus pivottal.
  2. Gráf algoritmusok:
    • Dijkstra algoritmus (legrövidebb út keresése)
    • BFS (szélességi keresés)
    • DFS (mélységi keresés).


1. Példa: Lineáris keresés

A lineáris keresés adott lista elemeiben keres egy konkrét értéket.

Python Implementáció

def linear_search(arr, target):
    """
    Determinisztikus lineáris keresés.
    
    :param arr: Lista, amelyben keresünk.
    :param target: Keresett érték.
    :return: Az érték indexe, ha megtalálható, különben -1.
    """
    for i in range(len(arr)):
        if arr[i] == target:
            return i
    return -1

# Példa használat
arr = [1, 3, 5, 7, 9, 11]
target = 7
result = linear_search(arr, target)

if result != -1:
    print(f"Az érték ({target}) megtalálható az {result}. indexen.")
else:
    print(f"Az érték ({target}) nincs a listában.")

Kimenet: 

Az érték (7) megtalálható az 3. indexen.

2. Példa: Buborékrendezés

A buborékrendezés egy determinisztikus algoritmus, amely az elemeket növekvő sorrendbe rendezi.

Python Implementáció

def bubble_sort(arr):
    """
    Determinisztikus buborékrendezés.
    
    :param arr: Rendezendő lista.
    :return: A rendezett lista.
    """
    n = len(arr)
    for i in range(n):
        for j in range(n - i - 1):
            if arr[j] > arr[j + 1]:
                arr[j], arr[j + 1] = arr[j + 1], arr[j]
    return arr

# Példa használat
arr = [64, 34, 25, 12, 22, 11, 90]
print("Eredeti lista:", arr)
sorted_arr = bubble_sort(arr)
print("Rendezett lista:", sorted_arr)

Kimenet: 

Eredeti lista: [64, 34, 25, 12, 22, 11, 90]
Rendezett lista: [11, 12, 22, 25, 34, 64, 90]

3. Példa: Dijkstra algoritmus

A Dijkstra algoritmus egy determinisztikus algoritmus, amely egy gráfban keresi meg a legrövidebb utat egy forráscsúcsból.

Python Implementáció

import heapq

def dijkstra(graph, start):
    """
    Determinisztikus Dijkstra algoritmus a legrövidebb út keresésére.
    
    :param graph: Szomszédsági lista gráf reprezentáció.
    :param start: A kezdő csúcs.
    :return: A legrövidebb utak hossza a start csúcsból.
    """
    distances = {node: float('infinity') for node in graph}
    distances[start] = 0
    pq = [(0, start)]  # Prioritási sor: (távolság, csúcs)

    while pq:
        current_distance, current_node = heapq.heappop(pq)
        if current_distance > distances[current_node]:
            continue

        for neighbor, weight in graph[current_node]:
            distance = current_distance + weight
            if distance < distances[neighbor]:
                distances[neighbor] = distance
                heapq.heappush(pq, (distance, neighbor))

    return distances

# Példa gráf
graph = {
    'A': [('B', 1), ('C', 4)],
    'B': [('A', 1), ('C', 2), ('D', 5)],
    'C': [('A', 4), ('B', 2), ('D', 1)],
    'D': [('B', 5), ('C', 1)],
}

start = 'A'
result = dijkstra(graph, start)

print(f"Legrövidebb utak a {start} csúcsból:")
for node, distance in result.items():
    print(f"{node}: {distance}")

Kimenet: 

Legrövidebb utak a A csúcsból:
A: 0
B: 1
C: 3
D: 4

Összegzés

A determinisztikus algoritmusok:

  1. Mindig ugyanazt az eredményt adják ugyanarra a bemenetre.
  2. Könnyen megvalósíthatók és ellenőrizhetők.
  3. Fontos példák: keresési algoritmusok, rendezési algoritmusok, gráfalgoritmusok.

A fentebb bemutatott Python példák (lineáris keresés, buborékrendezés, Dijkstra algoritmus) demonstrálják, hogy hogyan működnek a determinisztikus algoritmusok a gyakorlatban.

Fordítások

Tartalom

További információk

A lap eredeti címe: „https://hu.wiktionary.org/w/index.php?title=determinisztikus_algoritmus&oldid=3480717”