Pojęcie algorytmu i struktur danych

1.1 Co to jest algorytm

Algorytm – to uporządkowana sekwencja dokładnie określonych kroków lub instrukcji przeznaczona do wykonania konkretnego zadania lub rozwiązania określonego problemu. Każdy krok algorytmu powinien być zrozumiały i jednoznaczny, a jego wykonanie powinno prowadzić do określonego wyniku w skończonym czasie.

Po co nam algorytm:

• Rozwiązywanie problemów: Algorytmy pozwalają systematycznie podchodzić do rozwiązywania różnych zadań, od prostych operacji matematycznych po skomplikowane problemy obliczeniowe.
• Automatyzacja procesów: Algorytmy są niezbędne do automatyzacji zadań w oprogramowaniu, co pozwala komputerom wykonywać powtarzające się działania bez ingerencji człowieka.
• Optymalizacja zasobów: Dobrze zaprojektowane algorytmy pomagają efektywnie wykorzystać zasoby, takie jak czas wykonania i pamięć operacyjna.
• Powtarzalność i niezawodność: Algorytmy zapewniają powtarzalność i przewidywalność wyników, co jest ważne dla tworzenia niezawodnego oprogramowania.

Przykłady:

• Dziennie zadania: Na przykład, algorytm porannej rutyny – obudzić się, umyć zęby, przygotować śniadanie itp.
• Operacje matematyczne: Algorytm znajdowania największego wspólnego dzielnika (NWD) dwóch liczb.
• Programy komputerowe: Algorytmy sortowania (np. sortowanie bąbelkowe) i wyszukiwania (np. wyszukiwanie binarne).

1.2 Co to jest struktura danych

Struktura danych – to sposób organizacji i przechowywania danych w taki sposób, aby można było je efektywnie używać i przetwarzać. Różne struktury danych są przeznaczone do różnych typów zadań i operacji.

Dlaczego potrzebujemy struktur danych:

• Efektywne zarządzanie danymi: Struktury danych pozwalają zorganizować dane tak, aby można było do nich szybko i efektywnie uzyskać dostęp, zmieniać i usuwać.
• Optymalizacja algorytmów: Różne struktury danych są odpowiednie dla różnych algorytmów, a właściwy wybór struktury danych może znacznie zwiększyć wydajność algorytmu.
• Wygoda programowania: Używanie właściwych struktur danych sprawia, że kod jest bardziej zrozumiały, łatwiejszy w utrzymaniu i rozszerzaniu.
• Rozwiązywanie specyficznych zadań: Niektóre struktury danych są przeznaczone do rozwiązywania określonych zadań, takich jak hash-tabele do szybkiego wyszukiwania czy drzewa do danych hierarchicznych.

Przykłady:

• Tablice: Zbiór elementów jednego typu, do których można uzyskać dostęp za pomocą indeksu.
• Listy powiązane: Kolekcja elementów, z których każdy zawiera odnośnik do kolejnego elementu.
• Stos: Kolekcja elementów z zasadą LIFO (Last In, First Out).
• Kolejka: Kolekcja elementów z zasadą FIFO (First In, First Out).

1.3 Znaczenie algorytmów i struktur danych w programowaniu

Ważne! Nawet jeśli piszesz prostą stronę internetową lub prosta aplikację mobilną, używasz skomplikowanych algorytmów i struktur danych. Aplikacja działa na systemie operacyjnym, strona – w przeglądarce, a aby te rzeczy działały szybko i niezawodnie, stosuje się tam standaryzowane algorytmy i struktury danych.

Znaczenie algorytmów:

• Podstawowa zasada programowania: Algorytmy są podstawą każdej aplikacji, określając, jak dane będą przetwarzane w celu uzyskania pożądanego wyniku.
• Wydajność i efektywność: Optymalne algorytmy zapewniają szybsze wykonanie programów i efektywne wykorzystanie zasobów.
• Rozwiązywanie trudnych zadań: Algorytmy pozwalają rozwiązywać trudne problemy obliczeniowe, które są niemożliwe do rozwiązania ręcznie.
• Uniwersalność: Wiele algorytmów można stosować w różnych dziedzinach, takich jak sortowanie, wyszukiwanie, kompresja danych i kryptografia.

Znaczenie struktur danych:

• Organizacja danych: Struktury danych pozwalają efektywnie organizować i zarządzać danymi, co jest kluczowe dla tworzenia wydajnych programów.
• Wsparcie dla algorytmów: Różne struktury danych są optymalne dla różnych algorytmów, a właściwy wybór struktury danych może znacznie poprawić wydajność programu.
• Skalowalność: Dobrze zaprojektowane struktury danych pozwalają łatwo rozszerzać i modyfikować programy.

1.4 Przykłady prostych algorytmów

Algorytm znajdowania maksimum w tablicy:

Ten algorytm znajduje największą wartość w zadanej tablicy liczb.

Kroki algorytmu:

1. Przyjmij pierwszy element tablicy jako maksymalną wartość.
2. Przejdź przez wszystkie pozostałe elementy tablicy:
3. Jeśli bieżący element jest większy niż bieżąca maksymalna wartość, zaktualizuj maksymalną wartość.
4. Po przejściu wszystkich elementów zwróć znalezioną maksymalną wartość.

Implementacja w Pythonie:

def find_max(arr):
    # Zakładamy, że pierwszy element jest maksymalny
    max_val = arr[0]
    # Przechodzimy przez wszystkie elementy tablicy
    for num in arr:
        # Jeśli bieżący element jest większy niż max_val, aktualizujemy max_val
        if num > max_val:
            max_val = num
    # Zwracamy znalezione maksimum
    return max_val

# Przykład użycia:
# numbers = [4, 2, 9, 7, 5, 1]
# result = find_max(numbers)
# Output: 9

Algorytm sortowania bąbelkowego:

Ten algorytm sortuje tablicę, kolejno porównując i wymieniając sąsiednie elementy, jeśli są one w niewłaściwej kolejności.

Kroki algorytmu:

1. Rozpocznij od pierwszego elementu tablicy.
2. Porównaj bieżący element z następnym.
3. Jeśli bieżący element jest większy niż następny, zamień je miejscami.
4. Przejdź do następnego elementu i powtórz kroki 2-3, aż dojdziemy do końca tablicy.
5. Powtarzaj kroki 1-4, aż przy jednym przejściu przez tablicę nie zostanie dokonana żadna wymiana elementów.

Implementacja w Pythonie:

def bubble_sort(arr):
    n = len(arr)
    # Przechodzimy przez wszystkie elementy tablicy
    for i in range(n):
        # Ostatnie i elementy są już posortowane
        for j in range(0, n - i - 1):
            # Porównujemy sąsiednie elementy
            if arr[j] > arr[j + 1]:
                # Zamieniamy elementy miejscami, jeśli są w niewłaściwej kolejności
                arr[j], arr[j + 1] = arr[j + 1], arr[j]
    return arr

# Przykład użycia:
# numbers = [64, 34, 25, 12, 22, 11, 90]
# sorted_numbers = bubble_sort(numbers)
# Output: [11, 12, 22, 25, 34, 64, 90]